1. 介绍

最终一致性或者一致性问题是分布式场景不得不考虑的问题。在实现的方式上也有多种策略。下图是一个比较完整的总结。总结了分布式场景保证最终一致性的一些策略:

该图很多策略都是来源于cassandra,建议查阅相关资料,方便理解下图。可以参考Cassandra中的各种策略的内容。

主要掌握以下几种保证最终一致性的技术:
(1) 逆熵
这是一种备份之间的同步机制。节点之间定期互相检查数据对象的一致性,这里采用的检查不一致的方法是 Merkle Tree;
(2) 读修复
客户端读取某个对象的时候,触发对该对象的一致性检查;
举例:
读取Key A的数据时,系统会读取Key A的所有数据副本,如果发现有不一致,则进行一致性修复。

如果读一致性要求为ONE,会立即返回离客户端最近的一份数据副本。然后会在后台执行Read Repair。这意味着第一次读取到的数据可能不是最新的数据;如果读一致性要求为QUORUM,则会在读取超过半数的一致性的副本后返回一份副本给客户端,剩余节点的一致性检查和修复则在后台执行;如果读一致性要求高(ALL),则只有Read Repair完成后才能返回一致性的一份数据副本给客户端。可见,该机制有利于减少最终一致的时间窗口。
(3) 提示移交

对写操作,如果其中一个目标节点不在线,先将该对象中继到另一个节点上,中继节点等目标节点上线再把对象给它;
举例:
Key A按照规则首要写入节点为N1,然后复制到N2。假如N1宕机,如果写入N2能满足ConsistencyLevel要求,则Key A对应的RowMutation将封装一个带hint信息的头部(包含了目标为N1的信息),然后随机写入一个节点N3,此副本不可读。同时正常复制一份数据到N2,此副本可以提供读。如果写N2不满足写一致性要求,则写会失败。 等到N1恢复后,原本应该写入N1的带hint头的信息将重新写回N1。

(4) 分布式删除
单机删除非常简单,只需要把数据直接从磁盘上去掉即可,而对于分布式,则不同,分布式删除的难点在于:如果某对象的一个备份节点 A 当前不在线,而其他备份节点删除了该对象,那么等 A 再次上线时,它并不知道该数据已被删除,所以会尝试恢复其他备份节点上的这个对象,这使得删除操作无效。Cassandra 的解决方案是:本地并不立即删除一个数据对象,而是给该对象标记一个hint,定期对标记了hint的对象进行垃圾回收。在垃圾回收之前,hint一直存在,这使得其他节点可以有机会由其他几个一致性保证机制得到这个hint。Cassandra 通过将删除操作转化为一个插入操作,巧妙地解决了这个问题。

2. Anti_Entropy(逆熵)

Gossip算法又被称为反熵(Anti-Entropy),熵是物理学上的一个概念,代表杂乱无章,而反熵就是在杂乱无章中寻求一致,这充分说明了 Gossip的特点:在一个有界网络中,每个节点都随机地与其他节点通信,经过一番杂乱无章的通信,最终所有节点的状态都会达成一致。 在采用Gossip的系统中加入有的节点因宕机而重启或有新节点加入,经过一段时间后,这些节点的状态也会与其他节点达成一致。Gossip可以用于众多能接受“最终一致性”的领域:失败检测、路由同步、Pub/Sub、动态负载均衡。 但Gossip的缺点也很明显,冗余通信会对网路带宽、CPU资源造成很大的负载。
图A是反熵设计的超级简略图。图上可以看到同步写来保障数据最终一致,然后再同步读。整个过程是同步调用的。

Anti-Entropy 机制被用来保证在不同节点上的备份(replica)都持有最新版本。

由于涉及的处理很大,一般情况下,这种机制只用于永久性的错误恢复,而不用于普通的 read repair。如同 amazon dynamo一样。

另外,为了将节点间的数据传输降到最低,在实际数据传输前,各节点交换的是自己那份数据的 message digest。实现中将采用 MerkleTree (其叶子节点存储的是数据文件,而非叶子节点存储的是其子节点的 Message Digest)。
处理流程

 1. recover过程从 Node A 创建一个repair session

 2. recover过程从 Node A 开始 repair

 3. Node A从请求信息中得到数据 replica所在的节点(例子中,除了 Node A外,还有 Node B 和 Node C)

 4. 迭代这个 replica 节点列表

    4.1.通过本地的消息服务发送 anti-entropy 请求到 Node B

        4.1.1 Node B接收并执行请求

    4.2.通过本地的消息服务发送 anti-entropy 请求到 Node C

       4.2.1 Node C接收并执行请求

    4.3.通过本地的消息服务发送 anti-entropy 请求到 本地 Node A(自己)

       4.3.1本地 Node A接收并执行请求

 5. 初始化 MerkleTree

 6. 对每行数据计算其 hash 值并加入到 merkleTree(哈希树)

 7. 各节点将自己的MerkleTree作为 anti-entropy response 送给本地的消息服务

    7.1各节点的本地的消息服务将 anti-entropy response 返回给 Node A 的消息服务

 8. Node A收集各个 anti-entropy response 中的MerkleTree与本地的 MerkleTree (4.3.1 收到为本地的) 的不同 (diff)

 9. 如果需要, 通过 pipelineOut向 远程节点发送更加新的数据

 10. 如要需要,通过 pipelineIn向远程节点请求理加新的数据

总结:

  1. 缺点:网络冗余通信大
  2. 适用场景:最终一致性,恢复永久性错误
  3. 实现思路:哈希树、每个node都和别的node通信(造成网络冗余通信)。整个过程是同步调用的

3. 同步写结合异步写来做冗余

这里同步写了1个node,然后异步写给其他节点。当发生故障的时候通过hinted handoff来恢复。这个恢复技术详情见理解Hinted Handoff

3.1 同步写1个,异步写多个

同步写加异步写,恢复的时候可以采用如下技术:

  1. Hinted Handoff
  2. Read Repair(通过对其他节点读取摘要信息完成读修复)

3.2 同步写多个,异步写多个

4. 主从复制

5. 2PC和PAXOS