Dynamo

Dynamo

1. Partitioning

(1) 方法一：传统Consistent Hashing(请参考之前的consistent hashing总结)：

• 优点：新节点加入，或旧节点退出时，只影响紧相邻的下一个节点

• 缺点：传统的Consisitent Hashing假设每个node的性能是一样的，而现实中这种方法却有几个问题：

a. 数据分布未必均匀

b.每个机器的性能有差异: 比如机器A的存储是500TB， 机器B的存储是1PB，如果两个机器存储的数据大小一样，则A的负载更大，而B的资源没有被充分利用

c. 负载问题：假如hash环上的某一个节点出现故障，按照先前的算法，则该节点上的数据则全部得迁移到前一节点，这样导致前一节点的负载压力突然变得很大

(2) 方法二：引入虚拟节点的Consistent Hashing

• 优点：根据机器性能方便的调节所负责的虚拟节点数，每个机器节点对应hash环上的多个虚拟节点，这样有助于平衡负载

• 缺点：分片转移时，实现上需要对整个range进行遍历; 加入或删除节点时Merkle tree需要重新计算

(3) 方法三：将数据空间等分

• 优点: 数据空间等分Q份，T个机器节点时，每个机器分得S个分片，其中Q=T*S, 这样每个分片大小固定，可对应单个文件，因此容易加入或删除节点，且容易备份。

2. Replication

3. High Availability for Writes

4. Fault Recovery

(1) Temporary Failures

a. Sloppy Quorum

传统的Quorum机制是有3个参数，N, R, W， N代表所有node的个数，R是读取数据的node个数，而W是写入数据的node个数，只有当W + R > N时，(证明:鸽巢原理)

b. Hinted Handoff

(2) Permanent Failures

a. Mekle trees

5. Membership and Failure Detection

节点之间成员信息的得知都是通过Gossip协议传递的，这部分的分析可参考这里的"节点增删"部分

6. Reference

Dynamo论文介绍：http://catkang.github.io/2016/05/27/dynamo.html