亚马逊的key-value模式的存储平台 Dynamo
Dynamo是亚马逊的key-value模式
的存储平台
,可用性和扩展性都很好,性能
也不错:读写访问中99.9%的响应时间都在300ms内[1]。
数据
划分
按分布式
系统
常
用的哈希算法切分数据,分放在不同的node上。Read操作时,也是根据key的哈希值寻找对应的node。Dynamo使用了Consistent
Hashing算法,node对应的不再是一个确定的hash值,而是一个hash值范围,key的hash值落在这个范围内,则顺时针沿ring找,碰
到的第一个node即为所需。
Dynamo对Consistent Hashing算法的改进在于:它放在环上作为一个node的是一组机器(而不是memcached把一台机器作为node),这一组机器是通过同步机制保证数据一致的。
以上图为例,node1其实包含了多台机器,在一个node里宕了一台机或增加一台机,并不影响整个Dynamo对key的寻找。
如果一个ring内的访问量大了,则可以在两个node间加入一个新node以缓解压力,这时会影响到其后继node的hash范围,需要调整数据。假设
一个ring中原本只有node2、node3、node4,在加入新的node1之后,原先从node2查询的部分key将改为从node1查
询,node1和node2中的数据就需要调整,主要是node1从node2中提取出属于它的数据,这样做需要选取性能压力不高的时候。
数据同步
Dynamo的一个node中的同步是由client端来“解决
”的,使用所谓的(N, R, W)模型,其中,N表示node中机器的总数,R表示一个读请求需要的机器参与总数,W代表一个写请求需要的机器参与总数,这些值由client端配置。
例如,一个node有5台机器(N=5),client发出写请求——广播到5台机,如果收到3个“写完成”的返回消息,即认为写成功
(W=3);client发出读请求——还是广播到5台机,如果收到2个“读完成”的返回消息,即认为读成功(R=2)。对于数据十分重要的应用
(如金融),配置可以为(5, 5, 5),即要求node中所有机器的写都成功;而对于数据读写访问量极高的应用,配置可以为(5, 1, 1)。
通常W不等于N,于是,在某些情况下一个node内的机器上的数据可能会有不一致,这时Dynamo是通过将多个Read的返回结果“合并”来得出最终结果的,使用了所谓Object Version和Vector clock的技术
,即跟踪一个Object在不同机器上的版本变化,以确保当多个Read请求结果返回不一致时,能够更具其版本信息得出正确的结果。 Dynamo的这种做法是一种折衷,即为了同时保证读和写的效率,写操作不要求绝对同步,而把不同步可能产生的后果推给了读操作。
数据恢复
Dynamo的一个node中一台机器建有一个Merkle
Tree,当两台机器不一致时(如一台机器宕机一段时间),通过这个tree结构,可以快速定位不一致的Object来恢复数据。Merkle
Tree又叫Hash
Tree,它把key分成几个range,每个range算出一个hash值,作为叶子,再一层层合并计算上去,这样,从root开始比较hash值,就
可以快速找到哪几段range中的hash值变化了。
入门
基础
Dynamo的意思是发电机,顾名思义,这一整套的方案
都像发电机一样,源源不断地提供服务
,永不间断。以下内容看上去有点教条,但基本上如果你要理解原理,这每一项都是必须知道的。[2]
CAP原则
先来看历史,Eric A.
Brewer教授,Inktomi公司的创始人,也是berkeley大学的计算机教授,Inktomi是雅虎搜索现在的台端技术核心支持。最主要的是,
他们
(Inktomi公司)在最早的时间里,开始研究分布计算。CAP原则的提出,可以追溯到2000年的时候(可以想象有多么早!),Brewer教授在一
次谈话中,基于他运作Inktomi以及在伯克利大学里的经验,总结出了CAP原则(文末参考资料中有其演讲资料链接)。图一是来自Brewer教授当年
所画的图:
下载
(22.48 KB)
2010-10-17 23:56
图一:CAP原则当年的PPT
Consistency(一致性):即数据一致性,简单的说,就是数据复制到了N台机器,如果有更新,要N机器的数据是一起更新的。
Availability(可用性):好的响应性能,此项意思主要就是速度。
Partition tolerance(分区容错性):这里是说好的分区方法,体现具体一点,简单地可理解为是节点的可扩展性。
定理:任何分布式系统只可同时满足二点,没法三者兼顾。
忠告:架构
师不要将精力浪费在如何设计
能满足三者的完美分布式系统,而是应该进行取舍。
DHT——分布式哈希表
DHT(Distributed Hash Table,分布式哈希表),它是一种分布式存储寻址方法的统称。就像普通的哈希表,里面保存了key与value的对应关系,一般都能根据一个key去对应到相应的节点,从而得到相对应的value。
这里随带一提,在DHT算法中,一致性哈希作为第一个实用的算法,在大多数系统中都使用了它。一致性哈希基本解决了在P2P环境
中最为关键的问题 ——如何在动态的网络
拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息,并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中。至于一致性哈希的细节就不在这里详细说了,要指明的一点是,在Dynamo的数据分区方式之后,其实内部已然是一个对一致性哈希的改造了。
进入Dynamo的世界
有了上面一章里的两个基础介绍之后,我们开始进入Dynamo的世界。
Dynamo的数据分区与作用
在Dynamo的实现中提到一个关键的东西,就是数据分区。
假设我们的数据的key的范围是0到2的64次方(不用怀疑你的数据量会超过它,正常甚至变态情况下你都是超不过的,甚至像伏地魔等其他类Dynamo系
统是使用的
2的32次方),然后设置一个常数,比如说1000,将我们的key的范围分成1000份。然后再将这1000份key的范围均匀分配到所有的节点(s个
节点),这样每个节点负责的分区数就是1000/s份分区。
如图二,假设我们有A、B、C三台机器,然后将我们的分区定义了12个。
下载
(10.15 KB)
2010-10-17 23:56
图二:三个节点分12个区的数据的情况
因为数据是均匀离散到这个环上的(有人开始会认为数据的key是从1、2、3、4……这样子一直下去的,其实不是的,哈希计算出来的值,都是一个离散的结
果),所以我们每个分区的数据量是大致相等的。从图上我们可以得出,每台机器都分到了三个分区里的数据,并且因为分区是均匀的,在分区数量是相当大的时
候,数据的分布会更加的均匀,与此同时,负载也被均匀地分开了(当然了,如果硬要说你的负载还是只集中在一个分区里,那就不是在这里要讨论的问题了,有可
能是你的哈希函数
是不是有什么样的问题了)。
为什么要进行这样的分布呢,分布的好处在于,在有新机器加入的时候,只需要替换原有分区即可,如图三所示:
下载
(13.34 KB)
2010-10-17 23:56
图三:加入一个新的节点D的情况
同样是图二里的情况,12个分区分到ABC三个节点,图三中就是再进入了一个新的节点D,从图上的重新分布情况可以得出,所有节点里只需要转移四分之一的
数据到新来的节点即可,同时,新节点的负载也伴随分区的转移而转移了(这里的12个分区太少了,如果是1200个分区甚至是12000个分区的话,这个结
论就是正确的了,12个分区只为演示用)。
从Dynamo的NRW看CAP法则
在Dynamo系统中,第一次提出来了NRW的方法。
N:复制的次数;
R:读数据的最小节点数;
W:写成功的最小分区数。
这三个数的具体作用是用来灵活地调整Dynamo系统的可用性与一致性。
举个例子来说,如果R=1的话,表示最少只需要去一个节点读数据即可,读到即返回,这时是可用性是很高的,但并不能保证数据的一致性,如果说W同时为1的
话,那可用性更新是最高的一种情况,但这时完全不能保障数据的一致性,因为在可供复制的N个节点里,只需要写成功一次就返回了,也就意味着,有可能在读的
这一次并没有真正读到需要的数据(一致性相当的不好)。如果W=R=N=3的话,也就是说,每次写的时候,都保证所有要复制的点都写成功,读的时候也是都
读到,这样子读出来的数据一定是正确的,但是其性能大打折扣,也就是说,数据的一致性非常的高,但系统的可用性却非常低了。如果R + W >
N能够保证我们“读我们所写”,Dynamo推荐使用322的组合。
Dynamo系统的数据分区让整个网络的可扩展性其实是一个固定值(你分了多少区,实际上网络里扩展节点的上限就是这个数),通过NRW来达到另外两个方 向上的调整。
Dynamo的一些增加可用性的补救
针对一些经常可能出现的问题,Dynamo还提供了一些解决的方法。
第一个是hinted handoff数据的加入:在一个节点出现临时性故障时,数据会自动
进入列表中的下一个节点进行写操作,并标记为handoff数据,在收到通知需要原节点恢复时重新把数据推回去。这能使系统的写入成功大大提升。
第二个是向量时钟来做版本控制:用一个向量(比如说[a,1]表示这个数据在a节点第一次写入)来标记数据的版本,这样在有版本冲突的时候,可以追溯到出
现问题的地方。这可以使数据的最终一致成为可能。(Cassandra未用vector clock,而只用client
timestamps也达到了同样效果。)
第三个是Merkle tree来提速数据变动时的查找:使用Merkle tree为数据建立索引,只要任意数据有变动,都将快速反馈出来。
第四个是Gossip协议:一种通讯协议,目标是让节点与节点之间通信,省略中心节点的存在,使网络达到去中心化。提高系统的可用性。
分享到:
相关推荐
Amazon Dynamo 是一种分布式键值存储系统,由亚马逊公司开发并应用于其内部的多个服务中,后来演变成Amazon DynamoDB,成为AWS(亚马逊网络服务)的一部分,提供云中的NoSQL数据库服务。Dynamo的设计理念强调高可用...
Dynamo虽然不直接作为Web服务对外开放,但它和其他Amazon的分布式技术一起支撑着如亚马逊简单存储服务(Amazon S3)等关键Web服务。因此,Dynamo的成功对于整个亚马逊的业务稳定性具有至关重要的作用。 ### 研究与...
【标题】"国外技术干货:amazon-dynamo-sosp2007.zip" 指向的是一个关于Amazon Dynamo的深度解析资源包,该资源可能包含了2007年在SOSP(Symposium on Operating Systems Principles)会议上发表的亚马逊Dynamo论文...
亚马逊运行一个全球性的电子商务平台,为数以百万计的顾客提供服务,在峰值时间会使用分布在世界各地的数万台服务器。出于性能、可用性和效率的考虑,亚马逊平台有着严格的操作要求,为了支持平台的可持续发展,系统...
亚马逊的迷你发电机 ================================================== ======= Dynamo(键值存储)的简化版,内容包括: ID空间分区/重新分区。 基于环的路由 节点加入 基于仲裁的复制 发生故障后从复制的...
在解析这篇标题为“amazon-dynamo-sosp2007.pdf”的文档内容时,我们首先关注的是分布式键值存储系统Dynamo的核心技术和设计理念。Dynamo由亚马逊公司开发,是其核心服务之一,特别针对高可用性进行设计,以便能够...
《构建SimpleDynamo:模拟Amazon Dynamo的键值存储系统》 在当今的分布式系统领域,Amazon Dynamo是一款备受瞩目的键值存储系统,以其高可用性、可扩展性和一致性而闻名。SimpleDynamo项目则旨在通过Java语言,为...
在深入了解Cassandra数据库之后,再次回顾Amazon Dynamo的论文,本文旨在探讨两者之间的架构差异及其潜在的问题。经过一系列的实践经验和理论分析,本文作者得出了一些关于Dynamo架构的负面结论,并结合当前...
### Dynamo:Amazon的高可用性键-值存储系统 #### 原著:Werner Vogels #### 翻译: quest.run **背景与概述** Amazon 的 Dynamo 是一款为解决大规模、高可用性键-值存储需求而设计的系统。Dynamo 的目标在于为...
【DBGUI:Amazon Dynamo DB 图形界面工具】 DBGUI 是一个专为 Amazon Dynamo DB 设计的图形用户界面(GUI)工具,它允许用户通过直观的界面与 Dynamo DB 进行交互,而无需编写复杂的代码。这个项目始于 2013 年 6 ...
炸药用于Golang的Amazon Dynamo DB Mock驱动程序以测试数据库交互安装go get github.com/gusaul/go-dynamock用法示例访问获取常规示例和公共api参考。DynamoDB配置首先,将dynamodb配置更改为使用dynamodb接口。 ...
简单发电机这是 Amazon Dynamo 样式键值存储的简化版本。去做: 分区, 复制, 故障处理实施的步骤第 1 步:编写内容提供程序就像之前的任务一样,内容提供者应该实现所有的存储功能。 例如,它应该创建服务器和...
Simple Amazon Dynamo - Replicated Key-Value Storage 基于 Amazon Dynamo 架构的简化版本的分布式键/值存储。 该系统在 Android 平台上实现为通用内容提供者,它使用链复制和故障处理技术。 该系统同时保证了线性...
用于键值存储的Amazon Dynamo的简化版本 复制的键值存储提供3个主要功能:- 分区 复写 故障处理 分区:-分区可在系统中存在的各个节点之间提供负载平衡。 SHA-1加密哈希函数用于按字典顺序对键值对进行分区。 这与...
SimpleDynamo-venkatsvpr 是一个基于Java实现的分布式键值存储系统,它受到了Amazon Dynamo设计思想的深刻影响。Dynamo是亚马逊内部广泛使用的高可用、高性能、分布式的数据库服务,其设计理念强调了容错性、可扩展...
亚马逊S3 API Dynamo介绍 亚马逊的S3(Simple Storage Service)是一个功能强大的云存储服务,而Dynamo则是在其背后作为核心存储技术之一。为了设计和实现分布式的、高可靠的企业云存储平台,技术人员可以借鉴Dynamo...
**DynamoDB** 是亚马逊开发的一种完全托管的高性能NoSQL数据库服务,它提供了一种高度可扩展、低延迟的数据存储解决方案。本项目旨在实现 Dynamo 的一个简化版本,以帮助理解其核心机制,主要包括三个方面:**分区**...
Dynamo是由亚马逊(Amazon)开发的一种分布式键值存储系统,旨在为大规模在线服务提供高可用性、强一致性和可扩展性的数据存储解决方案。这篇论文是云计算领域的经典之作,对后来的NoSQL数据库设计产生了深远影响。 ...
### Dynamo:Amazon的高可用键值存储系统 #### 概述与背景 Dynamo是由Amazon开发的一款高度可扩展且高可用性的键值存储系统。它为Amazon的核心服务提供了支持,帮助其实现了“始终在线”的体验。由于Amazon作为...