复习Amazon Dynamo设计的一点分享

Author：文初

Email：[e-mail]

Blog：http://blog.csdn.net/cenwenchu79

 

         什么是Dynamo? Dynamo是Amazon的高效Key-Value存储基础组件（类似于现在被广泛应用的Memcached Cache），当前被用于Amazon很多系统中作为状态管理组件。在2007年年底Amazon的CTO就写了一篇介绍Dynamo设计的文章，今年年底又在日志中提出了对于那篇文章的一个补充：“Eventual consistency”。这也让我再次仔细的去回顾了一下Dynamo的设计思想，其中很多设计技巧是当前分布式系统设计也可以借鉴的。

         在说几个设计技巧以前先说几个分布式设计的需求和概念。

1．  Eventual consistency。这个概念在阿里系中支付宝架构设计贯彻的最彻底，记得看鲁肃的关于支付宝事务处理中提出的软事务的概念其实就是Eventual consistency的一种表现。对于系统设计来说，系统中的事件往往都会相互关联，孤立的事件在当前的互联网行业中变得微乎其微。事件与事件之间存在着一系列的约束和因果关联，就需要靠事务来保证。事务的特质就是ACID，而ACID在当前分布式系统设计的模式下常常会和可用性以及高效性产生冲突。ACID中其他三者都很好理解，而C “一致性”往往是初学者比较难以理解的一个特质。用银行存款操作的比喻就较为容易理解，银行帐户在操作前有100元，存入了50元以后，就有了150元，操作前和操作后保持了银行帐户的一致性，存入50元以后帐户仅仅增加了50元，总额没有超过150或者少于150，在常规看来是在正常不过的了，但是试想，如果有两个操作在一个瞬间作操作，一个需要给账户增加50元，一个要给账户增加30元，前一个操作是基于100元的基础增加，后一个也是基于100元增加，然后后一个操作晚于前一个操作提交，那么最后帐号里面就只有130，这就是可以认为银行帐号在两次操作以后出现了状态不一致性。一致性就好比自然界平衡，降水、蒸发维持生态平常。Eventual consistency其实是对一致性的一种延展，过程中允许部分不一致，但是在事务处理结束或者有限的时间内保持事务的一致性。一句话简单概括就是：“过程松，结果紧，最终结果必须保持一致性”。

2．   可用性，容错性，高效性。这三个非功能性需求在当前架构设计中已经成为最基本的设计要求，但三者常常在设计中又存在矛盾。容错性要高就需要作更多额外的工作，而更多的额外工作必将降低高效的特点，同时额外工作也会间接增加系统复杂度进而影响可用性。在设计中协调者三者的关系，没有什么准则可以遵循，只有根据实际的系统状况来判断如何达到最好的效果，在后面的Dynamo的三个参数配置设计就可以看到通过配置如何平衡三者关系并且将组件应用到上层系统中。

3．  分布式设计中两类一致性问题：单点数据读写一致性问题和分布式数据读写一致性问题。前者通常通过数据存储的服务端控制即可（类似于DB的控制），后者通常通过消息传播的方式来实现（类似于JGroup在多播通道传播同步消息）。

4．  冲突解决。这个我想大部分开发者每天都会接触到，代码控制（SVN）就是版本控制发现冲突的具体体现。冲突检测通常最简单采用last write的方式，也就好比数据库的解决方式，谁最后修改就以谁的为准。其他冲突检测和版本合并就十分复杂，有些不得不靠人工干预。这点也是在数据一致性通过多版本方式来解决的时候遇到的问题。

 

Dynamo设计中的学习点

 

1．  Consistent hashing算法支持分布式多节点

简单hash算法：N为node数量。处理主键为key的节点为：key.hashValue() mod N。

Consistent hashing算法：环状结构。虚拟节点来替换实体节点被分配到环状某一位置上（根据处理能力不同可以将一个实体节点映射到多个虚拟节点上）。主键为key的节点position = hash(key),在环上按照顺时针查找value大于position的第一个虚拟节点，由它对应的实体节点处理。下图中k就优先由虚拟节点 B来处理。

 

 

 

Consistent hashing的优点：（其实主要作用是在虚拟节点以及环状负责制上）

a．  支持不同能力节点的权重设置。由于采用了虚拟节点，通过虚拟节点和实体节点多对一的配置可以实现处理能力权重配置。

b．  新增或者删除节点动态配置成为可能，比较上一种简单算法，由于实体节点的数目直接影响到了hash算法，因此导致新增或者删除节点影响全局数据的重新映射。而Consistent hashing算法不受节点数目影响，它的区间负责以及多节点冗余处理降低动态增减节点的内容失效影响。在一些情况下需要不重新启动而动态的增加或者减少处理节点，因此采用了Consistent hashing的区间负责制，就好比上图key k的内容落在了A和B的区间内，根据规则由B优先来处理，当B失效的时候也可以由C,D来处理，根据环状最近可用节点来选择。如果在B节点和A节点新增一个节点或者删除B节点，影响的数据处理映射也仅仅是是A和B区间内数据。

c．  同时对于压力分摊也有帮助。这个优势还是沿用B来说，新增、删除或者失效一个实体节点，它可能对应的是多个虚拟节点，此时数据压力会分摊到环状其他的多个节点，新增也是同样，这样可以降低压力分摊的风险。

 

Consistent hashing算法其实也可以采用Tree方式来实现,Memcached的客户端版本中就有支持采用Tree的。

 

 

2．  Vector clock管理数据多版本

为什么会存在数据多版本，其实这个在高并发分布式处理中经常会遇到，同时也是容错性和高可用性的一种解决方式。两方面来看，首先在高并发分布式处理过程中，对于单个资源的操作要么采用阻塞方式要么采用多版本方式，前者效率相对较低但是处理简单，后者效率高但是处理复杂。对于容错性和高可用性要求高的情况下，多版本也是一种解决手段，就好比Amazon的购物车就要求任何时候都要支持修改，如果某一些处理节点当前不可用，那么就需要支持多个节点的处理以及数据多点的存储，这样就出现了不同节点数据的不同版本问题。

Vector clock根据操作者的不同为一个对象创建了多个版本计数器，并且通过多个版本计数器来判断这些版本是否属于并行分支还是串行分支，由此来确定是否需要解决冲突。

解决冲突分成两种方式，一种是客户端选择如何解决冲突，一种是服务端解决冲突。前者适用于较为复杂的冲突解决，后者适用于简单的版本冲突解决。不过不论哪一种方式，在Dynamo的处理中，客户端和服务端之间对于对象的操作交互过程都会带有版本历史信息。

 

 

 

       

         上图是描述一个对象D的Vector clock历史状况。首先D被Sx节点处理，那么处理以后产生了第一个版本D1([Sx,1])，然后又被Sx处理了，产生了第二个版本D1([Sx,2])，因此需要判断是否需要版本冲突解决。判断版本冲突主要是检查Vector clock中的多个版本与上一个历史Vector clock的关系，如果历史的和当前的Vector clock中所有的节点版本都是大于等于的关系，那么就认为两个版本不冲突，可以忽略前一个版本。就拿D2和D1来看，里面只有一个Sx的版本记录，对比2大于1，因此就认为可以忽略前一个版本。D3和D4分别是基于D2版本，两个不同节点处理后的结果，根据上面的冲突检测可以认为D3和D4版本无法忽略任何一个版本，因此此时对于D对象来说存在两个版本D3和D4，当Sx从服务端获取到数据以后做处理，此时就产生了三个版本。至于这三个版本由客户端Sx来解决还是服务端后期自动通过后台完成这个就需要根据应用来决定了。

         Vector clockfont-family: 宋体; mso-ascii-font-family: Calibri; mso-hansi-font-family: Calibri; mso-fareast-font-family: 宋体; mso-ascii-theme-font: minor-latin; mso-fareast-theme-font: minor-fareast; mso-hansi-theme-font: minor-latin;