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
Last updated
Was this helpful?