Amazon的Dynamo研究

2024-03-20 08:08
文章标签 研究 amazon dynamo

本文主要是介绍Amazon的Dynamo研究,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Amazon的Dynamo研究

许多开源项目一种非开源项目,在做高并发的存储设计的时候都会用consistent  hashing算法。这其中包括Memcached[1],以及Amazon的dynamo[2],所以先说说consistent  hashing,那么,什么事一致性哈希呢?

我将使用amazon的dynamo中Key/value 来作为例子。传统的数据存储都是采用的数据库的形式,但是数据库的strong consistence导致availability很受限,很难满足amazon的高availability的要求,因为amazon要求任何时候,对任何客户,购物服务必须是availability,为了应对这种场景,amazon开发出了自己的dynamo系统。在dynamo中,各个数据都是通过主key进行检索的,即通过主key来检索出整个object(例如二进制的blob或者可读的clob)的,但是无论是何种场景,object中的数据都不是直接可以得到的,所以dynamo不支持想数据库的关联形式等复杂的检索。


至此,就不难想象,即使基本思想就是,通过对key进行hash,来找到其对应的cache的位置,然后从cache中读取value。

那么,怎么由key计算出对应的存储cache的host呢。amazon就是在consistent hashing做了一些变种。


简单想法

如果现在有5台机器,很容易想象出找到一台host的suanfa其实是 hostNo = key%5; 这种hash有一种致命的问题,就是加入新的机子,和移除一台机子的时候导致整个缓存的失效,容错性非常差,所以在实际中是没法使用的。

一致性哈希

所以可能的hash值组成一个闭环,所有的hash值将所在0和计算机所能表示的最大值之间(对于32位机,可以认为是2^32-1),就是说0~2^32-1~0组成一个闭环。

主机到hash值的映射

如果现在有5台机器,很容易想象出找到一台host的suanfa其实是 hostNo = key%5; 这种hash有一种致命的问题,就是加入新的机子,和移除一台机子的时候导致整个缓存的失效,容错性非常差,所以在实际中是没法使用的。


一致性hash就是说将所有可能的hash值组成一个环,这个环是0~2^32-1~0。

而对每台机子进行hash,比如对机子的主机名,ip或者mac地址进行hash,然后会得各自的hash值。

我们就以mac地址来作为例子来说明吧,由于每个mac地址是不重复的,那么hash出来的结果也是不重复的。

这样你的5台机子就得到了5个hash值,分别是:

hashValueA = hash(macA);

hashValueB =hash(macB)

hashValueC =hash(macC)

hashValueD =hash(macD)

hashValueE =hash(macE)

现在假如这个五个hash值的大小分别是hashValueA<hashValueB<hashValueC<hashValueD<hashValueE。那么这5个hash值将所有的hash值分成了5段,分别是,

( hashValueA, hashValueB ], ( hashValueB, hashValueC ], ( hashValueC, hashValueD ], ( hashValueD, hashValueE ], ( hashValueE, hashValueA ].

Object到主机的映射

这时候,假如你有一个对象,你怎么决定应该把它存到那台host上面呢?

好的,hashValue = object.hash(),这样你得到了一个hash值,算法很见到,就是找到比hashValue大得第一个host的hash值。

现在假如 hashValue > hashValueC  ,但是 hashValue < hashValueD 。

这就意味着,hashValue应该映射到hostD上。

一致性哈希分析

加入一台新机子

而当你加入一台新机子,比如hostF的时候,只需要移动很小一部分的cache,现在假如hashValueF > hashValueE,那么这时候,对象(hashValueE,hashValueF]的cache值存储于hostA上面,这时候我们需要把它移动到hostF上面。

删除一台机子

通过一致性,这样每当一台机子down机的时候,只是影响到很小的一部分hash值的cache的命中。

现在假设hostD挂掉了,那什么只有hash位于( hashValueC, hashValueD ]的这些对象受到影响。

但是这时候仍然会造成cache的数据的丢失。可见一致性hash解决了scalability的问题,但是没有解决Availability的问题以及consistency的问题。


Dynamo的Replica for Availability

Dynamo通过Replica来实现Availability。也就是说把数据放在cache到对台host上面,而不是只是一台host,这样当一台机子失效时,可以通过去其他的机子读取数据来保证availability。

Dynamo采用的是consistent hash的变种。每当存储一份数据时,consistent hash只是把数据放在hash值比本身大的第一台host上面,而dynamo会将数据存储到前N台host上面。还以前面的例子来说明(即object的hash值hashValue满足, hashValue > hashValueC  ,但是 hashValue < hashValueD ),假设这时候N是3,那么应该将这份数据存储到主机D, E, A三台机子上面,而不是仅仅存储到主机D上面,这就保证了availability。

但是要保证保证了availability,那么consistency就要受到牺牲。

Dynamo的Replica for Availability

Dynamo使用gossip协议来发现数据中的不一种性,而通过vector clock来尽量的解决冲突。

并通过Quorum的方法来实现一定程度的最终一致性。

这部分会在以后补充。


引文

  1. http://memcached.org/
  1. http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf







这篇关于Amazon的Dynamo研究的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/828811

相关文章

一种改进的red5集群方案的应用、基于Red5服务器集群负载均衡调度算法研究

转自: 一种改进的red5集群方案的应用: http://wenku.baidu.com/link?url=jYQ1wNwHVBqJ-5XCYq0PRligp6Y5q6BYXyISUsF56My8DP8dc9CZ4pZvpPz1abxJn8fojMrL0IyfmMHStpvkotqC1RWlRMGnzVL1X4IPOa_  基于Red5服务器集群负载均衡调度算法研究 http://ww

生信圆桌x生信分析平台:助力生物信息学研究的综合工具

介绍 少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 生物信息学的迅速发展催生了众多生信分析平台,这些平台通过集成各种生物信息学工具和算法,极大地简化了数据处理和分析流程,使研究人员能够更高效地从海量生物数据中提取有价值的信息。这些平台通常具备友好的用户界面和强大的计算能力,支持不同类型的生物数据分析,如基因组、转录组、蛋白质组等。

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

研究人员在RSA大会上演示利用恶意JPEG图片入侵企业内网

安全研究人员Marcus Murray在正在旧金山举行的RSA大会上公布了一种利用恶意JPEG图片入侵企业网络内部Windows服务器的新方法。  攻击流程及漏洞分析 最近,安全专家兼渗透测试员Marcus Murray发现了一种利用恶意JPEG图片来攻击Windows服务器的新方法,利用该方法还可以在目标网络中进行特权提升。几天前,在旧金山举行的RSA大会上,该Marcus现场展示了攻击流程,

Science Robotics 首尔国立大学研究团队推出BBEX外骨骼,实现多维力量支持!

重复性举起物体可能会对脊柱和背部肌肉造成损伤,由此引发的腰椎损伤是工业环境等工作场所中一个普遍且令人关注的问题。为了减轻这类伤害,有研究人员已经研发出在举起任务中为工人提供辅助的背部支撑装置。然而,现有的这类装置通常无法在非对称性的举重过程中提供多维度的力量支持。此外,针对整个人体脊柱的设备安全性验证也一直是一个缺失的环节。 据探索前沿科技边界,传递前沿科技成果的X-robot投稿,来自首尔国立

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

vue原理分析(六)--研究new Vue()

今天我们来分析使用new Vue() 之前研究时,只是说是在创建一个实例。并没有深入进行研究 在vue的源码中找下Vue的构造函数 function Vue(options) {if (!(this instanceof Vue)) {warn$2('Vue is a constructor and should be called with the `new` keyword');}thi

《中国全屋智能行业发展现状与投资前景研究分析报告》

报告导读:本报告从国际全屋智能发展、国内全屋智能政策环境及发展、研发动态、供需情况、重点生产企业、存在的问题及对策等多方面多角度阐述了全屋智能市场的发展,并在此基础上对全屋智能的发展前景做出了科学的预测,最后对全屋智能投资潜力进行了分析。  订购链接:https://www.yxresearch.com/ 第一章全屋智能行业概念界定及发展环境剖析 第一节全屋智能行业相关概念界定 一、智能家

中国生态环境胁迫数据(栅格/县域尺度)-为研究生态环境压力提供数据支撑

中国生态环境胁迫矢量数据(2000-2010年) 数据介绍 2000-2010年中国生态环境胁迫数据为2000-2010年中国范围内人口、农业生产等生态环境胁迫因子的空间分布图,包括人口密度、农药使用强度、化肥施用强度。数据可用于分析全国生态环境胁迫因子及其对生态环境造成的压力的空间特征,主要通过社会经济统计资料获得,为县域尺度空间数据。 存储容量31.01 GB文件数量6数据类型栅

研究纹理采样器在像素级别的采样位置

问题 【纹理采样器】是一个基础的概念。假设有一个正方形面片,顶点的UV范围是0.0~1.0,那么在这个正方形面片上采样一张纹理时,会呈现出完整的纹理。 但我现在关注的问题是,在像素级别上,采样的位置是怎样的。具体来讲:对于UV值是(0.0,0.0)的点,它对应的采样位置是纹理最左上角像素的中心?还是纹理最左上角像素的左上角?即,下面左右哪个是正确的情况? 在宏观上,尤其是像素较多的时候,二者