Amazon Dynamo

Posted on May 29, 2016

特点

  • 分布式键值对系统
  • vnode一致性哈希分片
  • P2P
  • NWR可调, CAP动态调整
  • 向量时钟实现写冲突解决

Dynamo 的价值主要在于学术方面, 牺牲了一致性却没换来什么好处(?) 不适合直接模仿


数据分片

  • 改进的一致性哈希(虚拟节点)
  • P2P, 节点间使用Gossip协议定期同步节点信息
  • 每个节点都维护整个集群信息, 客户端也缓存集群信息(smart client). 能实现一次性定位

复制

假设一台pc机平均三年就会有一次失效,不可用。那么当一个一千台机器的集群,基本上每天都有机器坏掉,所以某主机不可用是常态,系统必须可以在这样的情况下继续提供服务

一般工业界认为比较安全的备份数应该是3份


失效转移过程

失效转移策略的目标对象应该都是vnode, 而不应该是节点吧?

N为复制因子, K为数据定位机器(首台?), [K, K+N-1]为复制集, 其中i宕机

  1. 集群往后找一台K+N为临时代替机器, 读写操作由[K, K+i-1] [k+i+1, K+N]负责, (K+N机器貌似只能负责写入, 因为没有老数据同步)
  2. 如果i机迅速恢复, K+N的增量数据需要回传给i机, 叫做 Hinted Handoff
  3. i机超过时间T未恢复, 认定为永久失效, K+N将进行数据同步

读取修复

客户端如果发现副本不一致, 会启动异步读取修复任务, 合并多个副本, 用合并后的副本更新过去副本


一致性

NWR值可调整

  • W+R>N 可保证强一致性

读写流程

读写过程中, 都选择其中一个副本作为协调者, 根据WR值, 由协调中发送读写请求到其他副本, 配合一定的重试和超时机制.

协调者需要解决结果冲突

读过程中如果发现某些副本数据太旧, 会异步发起读取修复操作


数据冲突

问题:

  • 对于同一份数据, 被多个备份节点同时更新不同的逻辑, 节点之间更新顺序无法保证(貌似因为P2P的节点可能存在集群信息不一致)

解决: 向量时钟

  • 向量时钟: [node, counter] node是指处理写出的node, 如果数据是同步过来的, 不会产生新的向量时钟
  • 子节点覆盖祖先节点, 不能完全形成父子节点的, 所有版本需要保留, 由客户端完成冲突解决

示例:

  1. 节点A写入新key, 增加一个版本信息(A,1), 数据同步
  2. 节点A更新key, 生成D2(A,2), D2覆盖D1, 数据同步
  3. 节点B, C 都有数据D2(A,2)
  4. 节点B和C并发写入, 在相互完成同步之前都完成了写入, 分布产生D3(A,2;B,1) 和 D4(A,2;C,1), 在B上, D3覆盖D2, 在C上D4覆盖D2
  5. 此时在互相同步完成之前, 版本: A: D2, B: D3, C: D4 即使N=R, 也只能保证客户端读到了最新的数据, 客户端可以舍弃D2, 但是需要处理D3和D4的冲突 另一种策略是last write wins 即选择时间戳最新的副本, 不过依赖集群时钟同步, 不可靠
  6. 节点同步, A,B,C最终的版本是D5(A,2;B,1;C,1), D5覆盖掉D2, D3, D4

和git合并很类似