分布式一致性算法介绍_分布式数据库一致性算法

目录

1、Zab协议

2、raft协议

3、gossip

---

       分布式数据一致性简单点理解就是在多个节点中同一时间视图时数据值是一致的。大体上可以将这些算法分为强一致性与弱一致性。

• 强一致性      

        zab协议（zk基于该协议实现了主备模式的系统架构，不保证线性一致性）

        raft协议（该协议是实现etcd高可靠的基础，大名鼎鼎的k8s就使用了etcd保存集群中所有的网络配制和对象的状态信息）

        paxos

•    弱一致性

      gossip协议（这个应用在redis cluster中）

    下面对上述算法进行简要的介绍。

1、Zab协议

       Zab 协议的全称是 ZooKeeper 原子广播协议（ZooKeeper Atomic Broadcast Protocol），目前Zookeeper基于该协议作为共识算法实现了主备模式的系统架构，并以此保证其集群中各个副本数据之间的一致性。Zab协议的原理大致分为选举(Leader election)、发现(discovery)、同步（synchronization）与广播（broadcast），但在zk的具体实现中，只有三个阶段：leader选举阶段，数据恢复阶段和广播阶段，将发现和同步两部分合并成为数据恢复阶段了。 

       在zk中，所有的写请求都是由leader服务器协调处理，如果写请求连接到follower节点，则会向leader转发请求，leader收到请求后，基于类似的2PC 当过半数节点写入成功，leader会再次向集群广播commit消息并提交。如果是读请求，则直接从当前节点中读取数据。

    zk中的节点类型有

• LOOKING：进入 Leader 选举状态；
• LEADING：某个节点成为 leader 并负责协调事务 ；
• FOLLOWING：当前节点是 Follower，服从 Leader 节点的命令并参与共识；
• OBSERVING：Observer 节点是只读节点，用于增加集群的只读事务性能，不参与共识与选举

      消息广播

       主要是针对于写请求，当任意节点收到写请求时，最终都会转发给leader节点。leader节点对生成对应的事务提案，并生成zxid（zxid是一个64位数字，高32位表示当前leader的epoch【类似于raft的term，即任期】，低32位是一个单增的计算器【每个epoch从0开始计数】），然后将提案广播给其他节点，其他节点收到请求以事务日志形式写入本地磁盘成功后反馈ack响应。当收到超过半数的ack响应后，则回复客户端写入成功，并向集群发送commit消息，提交事务。当各节点收到commit后，会完成事务的提交，数据写到数据副本中。

      在实际中，leader会收到多个写请求，为了统计每个写请求来自于follower的ack反馈数，在leader服务器中会为每个follower维护一个消息队列，然后将需要广播的提案依次放入到队列中，并基于FIFO的规则 发送消息。leader只需要统计每个zxid对应的提案超过半数有ack反馈就行，无需等待全部的follower节点。

崩溃恢复

     崩溃恢复即是包含有两个阶段：一是leader选举，另一个是数据恢复阶段。为了保证集群的数据强一致性，zab协议需要通过以下两个特性来保证：

•  已经在leader服务器上提交的事务最终被所有服务器提交

     这个特性很容易保证，毕竟zab协议中只要超过半数节点写入数据并ack响应，leader才会回复client写操作成功。

• 丢弃只在leader上提出但没有被提交的事务

    （1）如果leader在第一阶段崩溃了，如广播提案时崩溃，或者等待半数follower的ack响应期间崩溃。 这一阶段其实没有向客户端回复写入成功，以及向集群发送commit。因此从客户端角度来说没有收到leader节点的写操作成功响应，这种事务是失败的。从follower角度来说，由于没有收到commit命令，因此没有任何一个follower节点提交数据

   （2）在第二阶段发送commit后回复客户端写入成功前崩溃，这个过程稍微复杂一点。我猜想是通过超时机制以及客户端业务保证，这个后期再验证一下（要求rpc请求实现幂等性即可，也即实现内部的去重机制） 。

leaer选举阶段

       在leader选举阶段，集群中的服务器的节点状态都是LOOKING，每个节点向集群中的其他节点发送消息（包含epoch,zxid）。在选举初始阶段，每个节点都会将自己作为投票对象，并向集群广播投票信息。为了达成选举一致性，避免无休止的选举，zab总体保证拥有最新数据的服务器当选leader。具体规则如下：

1. 比较epoch，取其大者作为新的选举服务器，如相同进入2
2. 比较zxid，取其大者作为新的选举服务器，如果相等进入3
3. 比较服务器的myid(每一个节点都拥有一个唯一标识 ID myid ，这是一个位于 [1,255] 之间的整数，myid 除了用于标识节点身分外，在 Leader 选举过程中也有着一定的作用),也是取大者

    一旦某个节点拥有半数以上的投票，则会切换成leader，其他节点自动变为follower。

数据恢复阶段

   当leader选举成功后，follower与leader建立长连接，并进行数据同步。当数据恢复阶段结束后，zk集群才能正式对外提供事务服务，也就是进入了上文所说的消息广播阶段。

操作顺序性保证

    zab协议是基于主备模式的原子广播协议，最终实现了操作的顺序性。在zab协议中，所有副本的数据都是以主节点为准，主节点采用2PC提交，向follower节点同步数据。如果leader节点发生故障，则数据（日志）最完备的节点当选为leader。其次，zab实现了FIFO队列，保证消息处理的顺序性。总之，zab协议实现了一切以leader为准的专政模式和严格的FIFO顺序提交日志来保证操作的有顺序性的。

    从上面的描述，对zab协议总结几点：

• zab实现的是最终一致性。即当写请求过半节点成功后，是不能保证每次都实时的读到最新数据，但能保证在一定的时间范围内，客户端最终能够从服务端上读取到最新的数据状态。
• zab采用的快速领导者选举（fast leader election）,与raft采取的『一张选票，先到先得』算法相比，需要的通讯消息数要多一点，选举也稍微慢一些

   另外，zab协议目前与zk是强耦合的。

一致性保证

      默认情况下，ZooKeeper并不提供线性一致性，也即全局一致的数据视图。如果需要线性一致性，可以通过执行Zookeeper#sync()方法。对于读请求，每一个zk服务器都会对外提供服务，每一个服务器都有一层本地缓存，这也是zk高效的原因之一。zk可以通过线性增加follower节点均衡读压力（但是节点过多，会影响写入的性能，毕竟写请求需要同步到更多的节点）。zk中，与读不同，写入请求是满足线性一致性的。

2、raft协议

    raft对应的论文参考：In Search of an Understandable Consensus Algorithm(https://raft.github.io/raft.pdf)。它是一种基于leader选举的算法，用于保证分布式数据的一致性，它是实现etcd高可靠的基础。在raft协议中，节点的类型有leader, follower, candidate。

服务器的状态

时间被划分为term

在etcd的实现中，节点类型有相应的增加，如preCandidate， learner。

      集群启动时，所有的节点都是follower状态，随后会进入leader选举阶段。当follower节点的选举计时超时后仍然没有leader节点，会先切换为preCandidate身份，然后发送preVote预投票询问其他节点是否愿意参与选举争取他们的投票，如果有超过法定人数的节点响应并表示参与新一轮选举，则该节点会切换到candidate身份，并发起新一轮的选举。与前面的zab协议不同的是，节点类型多了一个预投票机制，通过preVote机制可以阻止失联节点（与现有的leader节点心跳超时）频繁的刷新term值，防止该节点重新加入集群时以更大的term值取代leader，从而影响leader节点的频繁切换（这种情况多发生于节点在不同的网络分区中）。

      learner是etch3.4引入的新节点类型，处于该类型的节点没有vote 权限，不算入Quorum。主要是解决以下问题：

• 新节点加入集群时，需要花费大量的时间同步日志，这可能导致集群无法处理新的语法     

    以上需要说明的有：

• 在一个term内，同一个节点最多能给一个candidate投票.原则是『一张选票，先到先服务』
• 选取心跳的发送是从leader(candidate)发送给follower 
• 选举的timeout是随机的，最先从timeout中恢复发起投票的一方向还在timeout中的其他方请求投票，避免在没有选举合适的leader的case下无限重复选举

状态复制

     一般通过使用复制日志来实现复制状态机。与zab协议一样，leader创建的日志entry已经复制到大多数的服务器上，这个entry就称为已提交。

为了消除上图描述的问题，Raft基于leader当前term的日志entry才通过计算数目来进行提交。

下面介绍一下raft与zab的区别：

• zab是主备模式的系统架构:所有的数据都以leader为准备，raft是状态机系统：仅同步事务命令
• 选主方式：raft比较last_log_index以及last_log_term保证选出的leader已经拥有最完整的数据，zab仅通过节点标识选主，所以需要之后的recovery过程，不过实现中zab也采用了类似于raft的选主方式
• 数据恢复方向：raft，leader拥有最完备的数据，它仅从leader单向到follower补齐log；而zab是双向的，leader需要从follower接收数据生成初始日志
• leader选举效率：raft更高

   脑残问题

•  对于写请求，当存在多个leader时，原先的leader独自在一个区，向其提交的数据得不到Quorum数量的支持永远也提交不成功。向新的leader数据可以提交成功，网络恢复后，旧的leader发现集群中有更新的term存在而自动降级为follower并从新的leader处同步数据达成集群数据的一致。
• 对于读请求，在etch-raft通过一种称为readIndex的机制来实现线性一致读，基本原理：leader节点在处理读请求时，先确定自身leader的地位（过半节点认为自己是leader），然后读取数据。（这里有个疑问：读请求也与写请求一样是重量级，能否有更优化的方案呢？——实际中，在发送心跳时会顺带上最近一个readIndex的ID,如果心跳等到多数派确认，则该ID对应的readIndex请求也得到确认，当然该请求之前的readIndex也变相被确认）

   因此，理论上可以这样理解:在etcd中不存在脑残问题。

一致性保证

     raft可以保证线性一致性读，有以下几种策略：

• 读取也走raft log, 让读取的请求也走一遍raft流程，raft日志是全局严格有序的，读写也必然是有序的，因此当处理到读取的日志的时候，能够保证之前的写入请求都已经处理完成并sync状态机，
• read index：发送心跳时顺带上最近一个readIndex的id
• lease Read:一般follower会在election timeout超时后才会认为leader挂掉，并发起一次新的选举。这里需要考虑服务器的时间

3、gossip

   它是一个无中心的基于流行病传播方式的节点或者进程之间信息交换的协议，简单点就是ping-pong进行广播。

 

关于脑裂及解决方案会持续更新   

 

references:

[1]https://github.com/aCoder2013/blog/issues/36