MyBlog

【Paper】Dynamo: Amazon’s Highly Available Key-value Store

last modified: 2020-12-02 19:23

The technology is designed to give its users the ability to trade-off cost, consistency, durability and performance, while maintaining high-availability.

Many of the techniques used in Dynamo originate in the operating systems and distributed systems research of the past years: DHTs, consistent hashing, versioning, vector clocks, quorum, anti-entropy based recovery, etc.

from All Things Distributed

一、Partitioning

  1. Consistent hash，将数据按Key hash到一个ring上，将node放到ring上，则每个key由顺时针的node负责
  2. Virtual node，1. 数据均匀分布，2. 充分利用不同性能的物理节点，论文中的Heterogeneity

二、Replication

  • 副本数为N
  • 每个key，将由其顺时针的1个节点，和N-1个该节点的后继节点负责。所有节点构成”Preference list”
  • Preference list：
    • 由存储指定Key的所有节点，构成一个list
    • 必须是物理节点（一个key的副本，不能在同一台物理机上面）

三、Versioning

  • 因为Replica之间的数据是异步复制的，因此存在数据不一致（最终一致性）
  • 由于副本存在，同一个key可能被两个node分别修改，value可能存在冲突，Dynamo使用的Vector clock解决冲突
  • Vector clock
    • (node, counter) pairs列表
                 Write handle by Sx                       Reconciled and written by Sx
----> D1([Sx,1]) ----> D2([Sx,2]) ----> D3([Sy,1],[Sx,2]) ----> D5([Sx,3],[Sy,1][sz,1])
Write handle by Server-x          Write handle by Sy
                                  ----> D4([Sz,1],[SX,2])
                                  Write handle by Sz
  • 在应用中通过版本信息解决冲突。传统的存储中，一般在写阶段，使用加锁或Last write wins来解决冲突。Dynamo为了得到Always writeable能力，将冲突解决下放到Applications读的阶段。

四、Quorum

Dynamo提供客户端选择数据一致性级别的能力，可以通过配置R+W>N Quorum算法牺牲性能，达到数据强一致。

五、Failures

  • Hinted Handoff/Sloppy Quorum（处理临时节点失效）

    • Amazon有一些使用场景，如用户加购物车，需要请求任何情况下都要成功，这类场景可以开启Sloppy Quorum
    • Sloppy Quorum: 当一节点不可用，它负责的Replica将写入到Preference list其它节点。这里一处坑存在，如果开启了Sloppy Quorum，会使R+W>N Quorum读失效。例如：写A，复制到B,C，现在1R、3W保证强一致性读，若B节点失效（假设A/D与结点B网络出问题），则Sloppy Quorum会使数据临时写到D，此时读B会得到一条旧版本的数据，失去了强一致保障，Cassandra中默认是关闭了Sloppy Quorum。
    • Hinted Handoff: 当不可用节点恢复后，数据搬移回原节点（如上面的D搬回到B，写到D的数据会带一个Hinted B的信息，写入临时表，表示这条数据是B的，我临时保管。D不停Ping B，B恢复后搬回数据。）

  • Replica Synchronization（处理永久节点失效）

    • Merkle trees for anti-entropy, 解决的是节点间数据不一致探测的效率O(logN)
    • 每个数据range一个merkle tree

  • Membership and Failure Detection

    • Dynamo的Paper没有描述清楚如何进行Failure detection
    • 分开处理2种情况，一种是主动新节点加入和旧节点下线。第二种是失败检测导致的节点剔除

关于基于Gossip协议的节点Membership维持，在Dynamo论文中没有讨论实现细节，但另一篇SWIM论文中，对一种Membership的实现细节，有完整阐述。