Dynamo是Amazon开发的分布式键值存储系统，它采用去中心化、松散耦合，由数百个服务组成的面向服务架构，只提供简单的键/值(key/value)方式的数据访问接口，不支持复杂的查询。最初用于支持购物车应用、S3服务，Facebook对照其论文实现了一个开源的分布式数据库Cassandra。
设计原则与系统假设
-
查询模型： 通过唯一的key访问对应的value。内部存储的value为Blob对象(二进块对象)，对象较小(通常小于1MB)，没有横跨多个key的操作，也不需要关系方案的relational schema。
-
ACID属性：Amazon的经验表明，在保证ACID的数据存储时往往有很差的可用性。Dynamo的目标应用程序是高可用性，弱一致性(ACID中的”C”)。Dynamo不提供任何数据隔离保证，只允许单一的键值更新。
-
效率：严格的延时要求，满足SLA保证(在客户端每秒500个请求负载高峰时，99.9%的响应时间为300ms)。
-
增量的可扩展性。可以灵活增加一些存储主机，来提高系统的服务能力。
-
节点对称性、去中心化：系统采用P2P架构，每个节点都是对等的、有相同的责任。
-
多节点间合并冲突：由于系统中各节点是对等的，所以在并发写同一个数据项时，各个节点的数据可能不一致。需要考虑：何时协调冲突，谁来协调冲突？Dynamo的目标是一个永远可写的数据存储(即”写”的高可用)，所以协调冲突的复杂性推给了”读”，以确保”写”永远不会拒绝。由客户应用程序来执行协调冲突，可以用简单的”last write wins”策略，也可根据应用的特点来决定协调冲突的方法。
数据分布
采用改进的一致性哈希算法。传统的一致性哈希算法思想：给系统中每个结点随机分配一个token，这些token构成一个哈希环。执行数据存放操作时，先计算key的哈希值，然后存放到顺时针方向第一个大于等于该哈希值的token所在的结点上。这个算法的优点是节点的增删只会影响到在哈希环中相邻的节点，对其它节点没有影响。考虑到不同节点的异质性(节点的处理能力有差异)，Dynamo使用了改进的一致性哈希算法。算法思想：每个物理节点根据其性能的差异分配不同数量的token，每个token对应一个”虚拟节点”。每个虚拟节点的处理能力相当，并随机分布在哈希环中。存取时，根据key计算出token，然后找到此token对应的虚拟结点的物理节点。
成员检测：Gossip协议 + 种子结点
为了找到数据所属的结点，系统中每个结点需要知道集群中所有结点的信息，客户端也需缓存这些信息，所以需要一种机制来维护更新结点的缓存信息。Dynamo采用了Gossip协议 + 种子结点。所有节点通过Gossip协议的方式从其他节点中任意选择一个与之通信的节点，如果连接成功，双方交换各自保存的集群信息。Gossip协议的细节不讲述，需要了解的Google一下。
为了处理逻辑分裂(具体定义参考论文)的异常，增加了一个第三方的种子结点来同步所有结点的信息。新节点加入时首先与种子结点交换集群信息，从而对集群有了认识。所有结点也会定期与种子结点交换集群信息，从而发现新结点的加入。
复制与一致性
为了实现高可用和可靠性，数据被复制成N份存于多台主机中。除了本地存储其范围内的每个结点，协调员节点(coordinator)复制数据到环上key对应token的顺时针方向的N-1个物理节点。
NWR
考虑到多副本复制带来的延时，Dynamo提出了NWR机制。N表示复制的备份数，R指成功读操作最少的节点数，W指成功写操作最少的节点数。只要满足W+R > N，就可以保证当存在不超过一台机器故障的时候，至少能读到一份有效的数据。如果应用重视读效率，可以设置W=N，R=1; 如果应用需要在读/写之间权衡，一般可设置成N=3, W=2, R=2。
冲突协调：向量时钟(vector clock)
为了解决多个节点更新同一条数据带来不一致的问题，Dynamo引入了向量时钟来尝试解决冲突。向量时钟是(node,counter)对列表(node表示节点，counter是一个计数器，初始为0，节点每次更新操作加1)，每个对象的每个版本与一个(node,counter)对列表 关联。通过检查向量时钟，可以判断一个对象的两个版本是平行分支或有因果顺序。如果第一个时钟对象上的计数器小于等于第二个时钟对象的计数器，那么第一个是第二个的祖先，可以被忽略。否则，这两个变化认为是冲突，要求协调。
客户端协调两个冲突版本的方法通常有两种，一种是通过客户端逻辑来解决，比如购物车应用; 另一种常见的策略是”last write wins”，即选择时间戳最新的版本，然而，这个策略依赖集群内节点之间的时钟同步算法，不能完全保证准确性。
容错
数据回传(Hinted Handoff)
如果N个副本所存的N个物理节点中，第i 台机器宕机，则原本写入该机器的数据会转移到机器N(顺时针的下一个结点)，如果在指定的时间内主机i重新提供服务，则机器N会通过Gossip协议发现，并将暂存的数据回传给机器i。
Merkle树 同步
如果超时了一定的间隔，机器i还是处理宕机状态，则会认为是永久下线了，此时需要从其它副本同步数据。为了更快地检测副本之间的不一致性，并减少传输的数据量，Dynamo采用了Merkle树。Merkle树是一个哈希树，其叶子结点是各个key的哈希值，树中较高的父结点均为其各自孩子节点的哈希。该树的优点是树的每个分支可以独立检测(是否一致)，而不需要下载整个树或数据集，有效地减少了检测一致性带来的数据传输量。每台机器对每个范围的的数据维护一颗Merkle树，机器同步时首先传输Merkle树信息，然后只同步从根结点到叶子的所有节点值均不相同的文件。
读取修正
在机器运行异常时，各个节点存储的副本可能不一致。客户端在读取数据时，会从多个结点获取多份数据，如果获取数据的版本不同，则会启动异步的读取修正任务：合并多个副本的数据，并使用合并后的结果更新各个结点上过期的副本。
读写流程
Dynamo写入数据时，首先，根据一致性哈希算法计算出每个数据副本所在的存储节点，其中一个副本作为本次写操作的协调者。接着，协调者并发地向所有其他副本发送写请求，每个副本将接收到的数据写入本地，协调者也写入到本地。当某个副本写入成功后，回复协调者。如果某个副本写入失败，协调者会将它加入重试列表不断重试。等到W-1个副本回复写入成功，协调者回复客户端写入成功。之后，还会继续等待或重试，直到所有副本写入成功。
Dynamo读取数据时，首先，根据一致性哈希算法计算出每个数据副本所在的存储节点，其中一个副本作为本次写操作的协调者。接着，协调者根据负载策略选择R个副本，并发地向它们发送读请求。每个副本读取数据，并回复协调者读取结果。当R-1个副本(加上协调者是R个副本)回复读取成功后，协调者回复客户端。注意，如果R个副本中若有不一致，要根据冲突处理规则合并，用合并后的结果回复给客户端。读取过程中，若发现某些副本中的数据太旧，则会异步发起一个读取修改操作，使用合并后的结果更新旧的数据。
讨论
Dynamo采用无中心结点的P2P设计，优点是机器宕机不需要停写服务，也减少了对工程师个人能力的依赖，减少了系统整体风险。缺点是数据的访问只保证弱一致性，极大地影响了上层应用设计，也使异常情况下的测试变成更加困难。总体上看，Dynamo为了”写”的高可用 牺牲了 一致性，使得它的应用场景有限，后续的很多系统，采用了其它设计思路以提供更好的一致性。主流的分布式系统一般都带有中心结点，这样可以简化设计，减少实现的复杂度。Dynamo不适合直接模仿，但其综合使用了各种分布式技术，可以适当地借鉴。
参考
《Dynamo: Amazon’s Highly Available Key-Value Store》论文
《分布式系统工程实践》
Amazon Dynamo – 纠结的设计
《大规模分布式存储系统》