分布式数据一致性算法

 在分布式系统中，多个数据节点保持数据一致的一种协议.

强一致性协议:

paxos、raft、zab

弱一致性协议:

gossip

已实现的例子

• Google的Chubby分布式锁服务，采用了Paxos算法
• etcd分布式键值数据库，采用了Raft算法
• ZooKeeper分布式应用协调服务，Chubby的开源实现，采用ZAB算法
• TIDB SERVER 主从region同步使用了raft协议
• kafka的consumer group参考了paxos的选举过程、redis主从集群选主等都类似

 PAXOS算法

目前完整的paxos协议由于参与角色过多，而精简为multi-paxos(其中 N和M 都是在集群中同步且唯一的,它的生成自增ID)。

1. 若集群中没有Leader，则在集群中选出一个节点并声明它为第M任Leader。
2. Leader准备一个N号提案   
3. Leader询问Acceptor中的多数派是否接收过N号的提案，如果都没有进入下一步，否则本提案不被考虑
4. Acceptor开始表决，Acceptor无条件同意从未接收过的N号提案，达到多数派同意后，进入下一步
5. Learner记录提案

RAFT算法

Raft算法将一致性问题分解为两个的子问题，Leader选举和状态复制;

Leader节点，负责发出提案。Follower追随者节点，负责同意Leader发出的提案，在没有leader的时候，参与竞选.

• Leader选举

1. 每个Follower都持有一个定时器
2. 当定时器时间到了而集群中仍然没有Leader，Follower将声明自己是Candidate并参与Leader选举，同时将消息发给其他节点来争取他们的投票，若其他节点长时间没有响应Candidate将重新发送选举信息
3.  集群中其他节点将给Candidate投票
4. 获得多数派支持的Candidate将成为第M任Leader（M任是最新的任期）
5. 在任期内的Leader会不断发送心跳给其他节点证明自己还活着，其他节点受到心跳以后就清空自己的计时器并回复Leader的心跳。这个机制保证其他节点不会在Leader任期内参加Leader选举。
6. 当Leader节点出现故障而导致Leader失联，没有接收到心跳的Follower节点将准备成为Candidate进入下一轮Leader选举
7. 若出现两个Candidate同时选举并获得了相同的票数，那么这两个Candidate将随机推迟一段时间后再向其他节点发出投票请求，这保证了再次发送投票请求以后不冲突

• 状态复制

1.  Leader负责接收来自Client的提案请求
2. 提案内容将包含在Leader发出的下一个心跳中
3. Follower接收到心跳以后回复Leader的心跳
4. Leader接收到多数派Follower的回复以后确认提案并写入自己的存储空间中并回复Client
5. Leader通知Follower节点确认提案并写入自己的存储空间，随后所有的节点都拥有相同的数据
6. 若集群中出现网络异常，导致集群被分割，将出现多个Leader
7. 被分割出的非多数派集群将无法达到共识，即脑裂，如图中的A、B节点将无法确认提案(不通过的原因是同意的数量不满足集群节点 N/2 +1),即其中分裂出来的小集群最多只有一个小集群的数量超过生效数量标准.
8. 当集群再次连通时，将只听从最新任期Leader的指挥，旧Leader将退化为Follower，如图中B节点的Leader（任期1）需要听从D节点的Leader（任期2）的指挥，此时集群重新达到一致性状态

 ZAB算法

ZAB也是对Multi Paxos算法的改进，大部分和raft相同,和raft算法的主要区别：

1. 对于Leader的任期，raft叫做term，而ZAB叫做epoch
2. 在状态复制的过程中，raft的心跳从Leader向Follower发送，而ZAB则相反。

Gossip算法

Gossip算法每个节点都是对等的，即没有角色之分。Gossip算法中的每个节点都会将数据改动告诉其他节点（类似传八卦）。有话说得好："最多通过六个人你就能认识全世界任何一个陌生人"，因此数据改动的消息很快就会传遍整个集群。

• Anti-Entropy（反熵）：以固定的概率传播所有的数据
• Rumor-Mongering（谣言传播）：仅传播新到达的数据

Anti-Entropy

Anti-Entropy 的主要工作方式是：每个节点周期性地随机选择其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异。Anti-Entropy 这种方法非常可靠，但是每次节点两两交换自己的所有数据会带来非常大的通信负担，以此不会频繁使用。

Anti-Entropy 使用“simple epidemics”的方式，所以其包含两种状态：susceptible 和 infective，这种模型也称为 SI model。处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点；处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。

Rumor-Mongering

Rumor-Mongering 的主要工作方式是：当一个节点有了新的信息后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新信息。直到所有的节点都知道该新信息。因为节点之间只是交换新信息，所有大大减少了通信的负担。

Rumor-Mongering 使用“complex epidemics”方法，相比 Anti-Entropy 多了一种状态：removed，这种模型也称为 SIR model。处于 removed 状态的节点说明其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。

因为 Rumor 消息会在某个时间标记为 removed，然后不会发送给其他节点，所以 Rumor-Mongering 类型的 gossip 协议有极小概率使得更新不会达到所有节点。

一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。

gossip 协议的通讯方式

不管是 Anti-Entropy 还是 Rumor-Mongering 都涉及到节点间的数据交互方式，节点间的交互方式主要有三种：Push、Pull 以及 Push&Pull。

• Push：发起信息交换的节点 A 随机选择联系节点 B，并向其发送自己的信息，节点 B 在收到信息后更新比自己新的数据，一般拥有新信息的节点才会作为发起节点。
• Pull：发起信息交换的节点 A 随机选择联系节点 B，并从对方获取信息。一般无新信息的节点才会作为发起节点。
• Push&Pull：发起信息交换的节点 A 向选择的节点 B 发送信息，同时从对方获取数据，用于更新自己的本地数据。