BT

你的观点很重要! 快来参与InfoQ调研吧!

解读NoSQL技术代表之作Dynamo

| 作者 陈臻 关注 0 他的粉丝 发布于 2010年6月17日. 估计阅读时间: 12 分钟 | ArchSummit社交架构图谱:Facebook、Snapchat、Tumblr等背后的核心技术

A note to our readers: As per your request we have developed a set of features that allow you to reduce the noise, while not losing sight of anything that is important. Get email and web notifications by choosing the topics you are interested in.

NoSQL在过去的一年里,逐渐已经成为了家喻户晓的东西,我(54chen)自从去年开始人人网的NoSQL系统Nuclear的研发以来,一直看NoSQL越来越热,越来越引来大家的围观。受InfoQ中文站编辑之托,特作此文,一来作为过去一年的总结,二来希望对NoSQL系统在国内的发展和推广尽绵薄之力。

NoSQL背后的两种模式

NoSQL其实并不是什么妖魔鬼怪,相反,NoSQL的真谛其实应该是Not Only SQL,其产生背景是在数据量和访问量逐渐增大的情况下下,人为地去添加机器或者切分数据到不同的机器,变得越来越困难,人力成本越来越高,于是便开始有了这样的项目,它们的本意是提高数据存储的自动化程度,减少人为干预的时间,让负载更加均匀等。在国际上,真正的代表之作有来自Google的 BigTable 和Amazon 的Dynamo,他们分别使用了不同的基本原理。

MapReduce

这是历史最久的一种模型,典型的代表是BigTable。Map表示映射,Reduce表示化简。MapReduce通过把对数据集的大规模操作分发给网络上的每个节点实现可靠性(Map);每个节点会周期性地把完成的工作和状态的更新报告回来(Reduce)。大多数分布式运算可以抽象为MapReduce操作。Map是把输入Input分解成中间的Key/Value对,Reduce把Key/Value合成最终输出Output。这两个函数由程序员提供给系统,下层设施把Map和Reduce操作分布在集群上运行。

Dynamo

这里我把Dynamo专门归纳成为了一种,其原因是它与MapReduce有很大的不同,自成一派。先说一下历史,Amazon于2006年推出了自己的云存储服务S3,2007年其CTO公布了S3的设计方案,从此江湖中就不再太平了,开源项目一个个如雨后春笋般地出现了。比较常见的有Facebook开发的Cassandra(如果没有记错,在去年浏览他们项目网页的时候,上面还写着他们之中的一个开发人员是Dynamo的设计人员,现在风头紧,去掉了),还有Linkedin的voldemort,而在国内话,有豆瓣网的beansDB,人人网的nuclear等等。这里我主要讨论的也是Dynamo的方案细节。

入门基础

Dynamo的意思是发电机,顾名思义,这一整套的方案都像发电机一样,源源不断地提供服务,永不间断。以下内容看上去有点教条,但基本上如果你要理解原理,这每一项都是必须知道的。

CAP原则

先来看历史,Eric A. Brewer教授,Inktomi公司的创始人,也是berkeley大学的计算机教授,Inktomi是雅虎搜索现在的台端技术核心支持。最主要的是,他们 (Inktomi公司)在最早的时间里,开始研究分布计算。CAP原则的提出,可以追溯到2000年的时候(可以想象有多么早!),Brewer教授在一次谈话中,基于他运作Inktomi以及在伯克利大学里的经验,总结出了CAP原则(文末参考资料中有其演讲资料链接)。图一是来自Brewer教授当年所画的图:

图一: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个。

图二:三个节点分12个区的数据的情况

因为数据是均匀离散到这个环上的(有人开始会认为数据的key是从1、2、3、4……这样子一直下去的,其实不是的,哈希计算出来的值,都是一个离散的结果),所以我们每个分区的数据量是大致相等的。从图上我们可以得出,每台机器都分到了三个分区里的数据,并且因为分区是均匀的,在分区数量是相当大的时候,数据的分布会更加的均匀,与此同时,负载也被均匀地分开了(当然了,如果硬要说你的负载还是只集中在一个分区里,那就不是在这里要讨论的问题了,有可能是你的哈希函数是不是有什么样的问题了)。

为什么要进行这样的分布呢,分布的好处在于,在有新机器加入的时候,只需要替换原有分区即可,如图三所示:

图三:加入一个新的节点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协议:一种通讯协议,目标是让节点与节点之间通信,省略中心节点的存在,使网络达到去中心化。提高系统的可用性。

后记

Dynamo的理论对CAP原则里的可扩展性做到了很方便的实现,通过创造性的NRW来平衡系统的可用性和一致性,增加了系统在实际情况下遇到问题的可选择方案。可以相像,在NoSQL的道路上,这只是个开端,在分布式计算的道路上,已经是MapReduce之后的再次革命。

关于作者
54chen(陈臻),人人网分布式存储研究人员,业余时间混迹于各技术组织且乐此不疲。目前关注实施PHP培训。对flex等前端技术有一点研究。个人技术站点:http://www.54chen.com/ 。可以通过电子邮件 czhttp@gmail.com 联系到他。

参考资料:


给InfoQ中文站投稿或者参与内容翻译工作,请邮件至editors@cn.infoq.com。也欢迎大家加入到InfoQ中文站用户讨论组中与我们的编辑和其他读者朋友交流。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

谢谢分享 by 曹 云飞

CAP原则讲解的很清楚,收获很大 :)

挺好 by jiang rosen

不错的普及教程

CAP该进教科书了 by liu hying

CAP原理该进教科书了。不能让我们的学生觉得ACID就是天理

Re: CAP该进教科书了 by 罗 永明

CAP存在于《分布式系统》的教科书中。。。

我有问题...... by wang keating

12个分区分到ABC三个节点,图三中就是再进入了一个新的节点D,从图上的重新分布情况可以得出,所有节点里只需要转移四分之一的数据到新来的节点即可,同时,新节点的负载也伴随分区的转移而转移了(这里的12个分区太少了,如果是1200个分区甚至是12000个分区的话,这个结论就是正确的了,12个分区只为演示用)。
-----------------------------------------------------------------------------------------
这里3个结点,新加入结点,要分1/4的数据过去。分多少数据跟结点数量有关系,但是跟分区没有关系呀,对吧?你怎么说,分区是1200个结论就正确了呢.....求解答。

Re: 我有问题...... by 陈 臻

这里的结论是:新节点的负载也伴随分区的转移而转移

目标是:加结点后,新加入的机器平分负载

分区越多,粒度越小,单个粒度上承担的负载越趋近于相近,这时候再按这个粒度的数据去转移的时候自然可以认为是四分之一的数据就代表了四分之一的负载过去了。

Re: 我有问题...... by wang keating

恩,这一点,明白了: ) 感谢啊!

顶,同时也希望我们的nuclear具有独特的优势 by (Qieqie) 王志亮

RT

MapReduce? by 易 卓霖

MapReduce是并行框架吧。。是不是应该把MapReduce那一段替换成BigTable

nosql by Xia Roger

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

10 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT