1. 数据分布: 一致性哈希 + 虚拟节点
1.1 一致性哈希的原理
把key根据某个哈希算法映射到从[0-N)的一个值，将N个值从小到大顺时针组织成一个哈希环，环上有个N个位置， 其中0和N-1首尾相连。从哈希环上选出若干个位置n, 放上svr节点； 对于一个key, 计算出其哈希值，在哈希环上找到其位置，从该位置出发，顺时针遍历，找到下一个svr节点，把数据存放到该节点上, 读取过程类似。一致性哈希解决了采用固定哈希的数据分布系统中节点的加入和退出导致的全量数据再哈希的问题。在一致性哈希中， 节点的加入只涉及到新节点的后继节点上的数据搬迁到新节点； 节点的退出也只涉及到把退出节点上的数据分布到其后继节点。
1.2 一致性哈希的问题
svr节点在哈希环上的位置的选择很关键，随机选择的话，会造成节点的负载不均匀, 不均匀的情况会在新节点的加入和老节点的离开时加剧；原版的一致性哈希算法无法感知svr节点之间的区别，具有不同性能的svr节点可能需要去负责等量数据的存储和访问。
1.3 使用虚拟节点解决
dynamo中引入了虚拟节点(virtual node)。虚拟节点的作用是对哈希环做更细粒度的划分；引入虚拟节点之前，哈希环被N个物理节点划分为N段，每个物理节点负责一段； 引入虚拟节点以后，哈希环被n个虚拟节点划分为n段，每一段对应一个虚节点，n > N, 每个物理节点可以负责n段中的若干段。加入一个新的物理节点时，可根据该节点的配置决定为其分配的虚拟节点的数量； 新加入的节点可以分担多个老节点的负载；当一个物理节点不可用时，可以将负载分摊到多个健康节点上，使负载分布更为均匀。
2. 高可用
高可用通过数据冗余来实现。每个key写入到其所属coordinator上，并且被coordinator复制到N-1个后继节点(顺时针)，也就是一个数据有N个副本(replica), N是per-instance级别可以配置。负责存储某个key的节点列表叫做优先列表(preference list)。dynamo中，从任意一个节点都可以获取一个key的优先列表。为了应对节点失败， 优先列表包含多于N个节点；由于引入了虚拟节点， N个后继节点可能包含多个同属一个物理节点的多个虚拟节点，因此在构造优先列表的时候要保证虚拟节点都属于不同的物理节点。为了维持多个副本的数据一致性，dynamo采用了类quorum的协议，对于一次读，只有优先列表中至少R个节点成功返回数据，才算成功；对于一次写，只有优先列表中至少W个节点成功返回，才算成功。 W + R > N。quorum协议的核心在于交集。
3. 读写逻辑
存储系统 = 数据组织方式 + 读写逻辑。 数据已经通过一致性哈希算法分布到不同的存储节点上，并且为了容灾，冗余到了多个存储节点。dynamo中的读写请求基于http协议。 往dynamo中读写数据，首先需要找到coordinator, coordinator为优先列表中的第一个节点。请求有两种方式可以发送到dynamo, 一是通过load balancer(lb), lb在收到请求时，根据各个节点的负载，选择一个节点A，将请求转发过去，如果A不是coordinator, 则把这个请求转到coordinator上去。
当coordinator收到对一个key的写请求时，先为这个key的新数据生成一个版本向量(version clock), 把该key的新数据写到本地； 然后把这个key的新数据以及新的版本向量写到优先列表的N个排名最高的可达节点，如果至少有W-1个节点响应，则该写操作视为成功。
当coordinator收到对一个key的读请求时，先读取优先列表的N个排名最高的可达节点，获取这个key的所有版本数据; 当收到R个节点的回复时，将获取到的数据返回给客户端。如果获取到的数据存在多个版本，根据版本向量，先合并能够合并的版本，然后将所有无法判断时序关系的版本全部返回给客户端, 让应用自己去做冲突解决。
dynamo中任意一个节点都可以做读请求的coordinator；优先列表中的任意节点都可以做写请求的coordinator; 虽然看起来只允许优先列表中的第一个节点做为写请求的coordinator更加好，这样的话对于落到一个区间内的key的所有写请求，都会被同一个节点处理，容易序列化，不容易产生版本分化；但这种做法会造成负载不均衡。由于每个写之前都会先进行一次读，将读请求中响应最快的那个节点选为接下来的写请求的coordinator。
4. 容灾
4.1 应对节点和网络的暂时故障
使用传统的quorum协议，如果优先列表中的有大于N-W个节点故障了，系统就不可写了; 大于N-R个节点故障，就可能造成写丢失。dynamo使用了一种叫做sloppy quorum的技术来解决这个问题。在sloppy quorum中，所有的读写操作都作用在优先列表的头N个健康节点，这N个健康节点可能并不是key的哈希值所在位置开始的头N个后继节点(有可能有的节点故障了, 或者由于网络分割不可达)。如果优先列表的头N个节点中有不可达的U，则顺着哈希环找到下一个健康节点H, 把本来应该写到U的数据写到H上，并且H在元数据中记录，哪个数据应该是谁的， 当U回来以后， H把这部分不属于他的数据发送给U, 发成功后就删掉。这个过程叫做hinted handoff。通过hinted handoff, dynamo保证数据的读写不会因节点或者网络的暂时故障受到影响。如果把W设置为1，则系统中只要有一个节点存活，就可写。出于数据持久化考虑，一般不这么做。sloopy 的意味着，W和R不一定不保证由重叠。
4.2 应对整个数据中心的故障
dynamo也可以应对整个数据中心的故障。一般，一份数据会被复制到多个数据中心。一个key的优先列表中包含了部署在多个不同数据中心的节点。数据中心通过高速网络连接。
4.3 应对永久性故障
由于数据存在于多个副本上面，要保证数据不丢失，就需要保证副本之间数据的一致性。例如4.1中H在把U的数据还给U之前就永久故障了，这部分数据就丢失了。因此需要及时检测到数据的不一致，并且尽量数据的迁移量。dynamo使用merkle tree来检测副本之间的不一致。merkle tree是个树结构，叶子节点时所有key的value的hash值，非叶子节点存储其子节点的值得hash值。使用merkle tree，不需要拉取所有副本的所有数据，或者整个树结构做对比，merkle tree的每个子树都可以独立对比。例如，如果两个merkle tree的根节点相同，那么所有数据相同；如果根节点不同，则一定有子节点不同，那么可以定位出一条或者多条路径，该路径上的每个节点，在每个merkle tree中值都不同，通过这些路径中的叶子节点，可以定位到两个副本中哪些数据不同。 dynamo为每个虚节点都维护一个merkle tree, 可以以虚节点为粒度来校验副本之间数据的一致性。
5. 其他
使用版本向量来做冲突解决；通过gossip协议和种子节点来扩散成员变更，数据分布等信息，通过统计读写请求的返回来探测是否有节点故障了。使用write buffer来提高写性能，通过让至少一个副本节点来执行durable write来保证数据安全性。通过调节hash环的切割方式来保证数据分布的均匀性(每个节点分配随机数量的token且根据token的值切分，环被均匀切分且每个节点随机分配相同数量的token，环被均匀切分且所有节点等量瓜分所有token); 将coordinator的选择放到客户端来降低延迟(少了至少一次请求转发); 基于请求处理延时来调度后台任务的执行以防止以避免影响服务。
dynamo的设计理念很独特，将可用性和延时始终排在首位，为了保证可写和99.9%的延时，可谓用心良苦。dynamo本身并没有提出什么新的算法或者机制, 版本向量，分布式哈希， merkle tree, quorum, gossip协议都是比较经典的思想了，但其展示了如何如何基于这些经典思想，做一个高度tunable的灵活的系统，展示的权衡的取舍的艺术。个人觉得dynamo的使用门槛会比较高，它要求开发人员能深入理解业务逻辑，基于业务逻辑对多个版本的数据做reason和冲突解决。