Author：文初
Email：wenchu.cenwc@alibaba-inc.com
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 clock只是提供了一种手段来解决多版本的问题，至于客户端解决冲突还是服务端解决冲突这个需要根据具体情况来选择。
3． load balance的几种模式。
a. 客户端实施load balance。采用客户端包来实现分发算法，同时配置分发节点情况。Memcached Cache客户端使用的一种基本方式。
b. 服务端硬件实现load balance。
c. 客户端改进模式。配制节点以及算法都可以采用集中的Master来管理和维护，包括心跳检测等手段由Master来实现。当然支持Master失效的容错性策略实施。
d. 服务端模式改进。采用preference list来分离接受和处理任务的节点。
首先采用A模式可以防止B模式在单点的情况下出现的不可用风险，也可以减轻高并发下单点的压力，提高效率（这点淘宝的同学有和我提到过，他们采用的“软负载”方式）。但是A模式会增加对于客户端包的依赖性，对于扩展和升级都会有一定的限制。
其次B模式是最省心的方式，扩展性也比较好，但是就是在上面提到的单点问题会有所限制。
C方式是对于A方式的一种改进，我以前的一篇文章中提到过，这样可以提高A的可扩展性以及可维护性，减小对于客户端包的依赖，但是增加了系统复杂度，同时Master也是会有单点的问题，不过问题不大（失效的情况下就是退化到了A模式）。
D方式是解决服务端简单的分发而导致处理的不均衡性，其实这种模式也可以改进客户端的算法。因为通过Hash算法未必能够将压力分摊均匀，就好比一些处理需要耗时比较久一些处理耗时比较少，系统对于key的映射不均衡等等问题，不过在Dynamo中描述的并不很明确，其中的算法还是要根据实际情况来做的。
4． 三个参数平衡可用性和容错性。
在Dynamo系统中通过三个参数（N，R，W）来实现可用性和容错性的平衡。对于数据存储系统来说，Dynamo的节点采用冗余存储是保证容错性的必要手段，N就代表一份数据将会在系统多少个节点存储。R表示在读取某一存储的数据时，最少参与节点数，也就是最少需要有多少个节点返回存储的信息才算是成功读取了该数据内容。W表示在存储某一个数据时，最少参与节点数，也就是最少要有多少个节点表示存储成功才算是成功存储了该数据，通常情况下对于N的复制可以阻塞等待也可以后台异步处理，因此W可以和N不一致。这里的R,W的配置仅仅表示参与数量的配置，但是当环状节点其中一个失效的时候，会递推到下一个节点来处理。
很明显的R,W的数字越大直接会影响系统的性能和可用性，但是R,W越大却能够保证容错性的增强。因此如何配置N,R,W成为平衡容错性和可用性的一种重要方式。对于一个系统结构中，节点本身稳定性较高的情况下，将R,W配置的较小，提升系统的可用性。对于节点稳定性不可靠的情况下，适当增大R,W配置，提升系统的容错性，同时也对可用性有一定帮助。
另一方面，从读写能力和业务操作读写比例修改R,W的配置来优化系统的性能。对于读操作十分密集写相对来说较少的情况来说，配置R=1,W=N，则可以实现高读引擎，系统只要还有一个节点可以读取数据就可以读到数据。对于写比较频繁的情况来说，那么可以配置R=N,W=1实现高写引擎，系统只要还有一个节点可以写入，就可以保证业务写入的正常，不过读取数据进行冲突解决会比较复杂一些。
除了配置这三个参数以外，通过读写配置本地缓存的方式可以提高系统整体性能以及容错性。
5． 异步处理容错数据复制
当一个数据存储节点出现问题以后，数据存储交由给下一个节点处理，此时除了在下一个节点存储数据内容以外，还会记录下原本数据所应该存储的节点以及当前存储的节点和数据内容，可以放在后台的数据库或者存储中，后台定时处理这些记录，将数据迁移并且删除复制任务。
这部分在我优化Memcache客户端的时候采用的是客户端集群配置lazy复制的方式，当发现配置成集群的节点中优先处理节点没有数据就考虑从其他节点获取，如果存在就异步复制，不过这种方式对于有timestamp的数据就会有问题。
6． 采用merkle tree来交验节点存储数据一致性。每一个节点所处理的key range将会被保存在本地节点中，通过tree的方式在组织存储，通过对比节点之间的tree可以快速高效的判断出是否有数据不同步需要异步复制和同步。
Merkle tree的具体算法和使用方式可以参看BT交验改进的文章来学习一下，这片文章写得很通俗易懂，推荐一下：http://www.cnblogs.com/neoragex2002/archive/2006/04/26/385077.html
以上的都是自己看Dynamo设计中觉得对自己比较有帮助的内容，其中一些思想可能会和原有设计有些出入，各位仅作参考。