分布式一致性算法

作者 dengchengchao@outlook.com发表于

一直想写篇文章总结下分布式一致性算法，但是这个东西细节实在太多…每次捋一半就卡住。

这篇文章，是第三次重写。

本文只是总结各个分布式算法之间的易同，前提是需要对各个算法有一定的理解。

分布式一致性算法是为了解决集群中主从服务数据如何同步而提出来的算法，由于不同的业务场景需要的面对的问题不一样，因为有很多不同的协议，比如raft,paxos,zab等。

共识性算法Paxos

说到分布式算法，最出名的便是Paxos，Paxos给人留下的印象是难以理解，一头雾水。

想要理解Paxos，需要明白它要解决什么问题：Paxos是一种共识性算法，是用来解决多个进程并发对同一个值进行写入的时候，如果让这个值能实现统一。

比如说对于同一个值x，同时存在两个客户端，一个客户端希望设置x=1，另外一个客户端希望设置x=2，那如何让一个集群中达到一个共识，使得所有的服务都能统一保存使得x=1或者x=2或者x先等于1，再等于2。这便是Paxos能解决的问题。

Paxos的核心思想是两段提交相互辅助，第一段类似加锁的过程，第二段对一段加锁的数据进行辅助传播，使得数据最终在系统中达到一致。

在Paxos算法中，主要通过“先请求先得，后请求则协助先请求”的思想，比如上述请求过程，如果A客户端先请求x=1,然后B客户端在请求过程中发现已经有客户端提交了x=1的请求，则客户端B会修改自己的请求，也设置x=1，来协助实现共识，在此之后，客户端B可以重新提交自己的请求。

Paxos虽然能使得数据在系统中达到一致，但是离应用到工程中，还有很多细节的问题，比如常见的系统不仅仅是修改数据，更多是追加数据，更进一步，Paxos为了能达到共识，并发写数据只有一个能写成功，后面的数据需要重试，这样对于高并发的系统来说，会降低性能。

工程化一致性算法

分布式一致性算法，想要将Paxos工程化，还需要解决很多问题，如果直接就将Paxos应用到工程中，还有很多细节问题需要解决。接下来一一探索：

首先，是每个客户端都能处理请求还是Leader-Follower结构，如果每个客户端都处理请求，那么可能会存在并发问题，性能会降低，而且开发难度会更高，因此目前大多数系统采用的都是Leader-Follower结构。

使用Leader-Follower结构会有存在一个问题，谁来做Leader?当选Leader应该具备哪些条件？怎么让各个客户端达到Leader的共识？

解决完Leader的问题，还有就是Leader和Follower同步问题：Leader处理完数据后，是直接返回客户端处理成功（异步），还是等所有数据同步到所有Follower之后，才返回成功（同步）。如果异步处理，则有可能会出现丢消息的可能，如果同步处理，则系统性能过低，同时如果某个时刻崩溃一个Follower，这个时候是忽略还是等待？如果忽略，那么它又重启后应该怎么处理，如果等待，那么系统的容灾性又过低。一般的处理方法，就是忽略，因为系统都是采用的大多数同步策略，因此只要系统崩溃数量小于一半，系统就能正常运行，当其重启后，通过Leader为其补全丢失的数据。

同时，采用大多数策略可能存在以下问题：ABC3个服务器，通过大多数策略依次写入1,2两条数据，此时有可能出现： A 上数据为：1 , B上的数据为：1 2 ，C上的数据为:2，那么此时如果服务B崩溃，那么不管选择谁为Leader，都会导致丢消息。常规的解决方案便是要求数据的写入必须是有序的，当C写入数据2的时候，他需要检查1是否写入，如果未写入则需要先同步1。这样能保证B崩溃时，C有全部数据。

最后，当一个Leader崩溃时，另外一个Follower当选Leader，当前系统可能存在数据很不一致的情况。极端的情况：ABCDE系统中，一直只有ABC3个系统数据完全同步，D和E完全没有任何数据，某个时刻BC崩溃了，那这个时候A作为Leader，D和E缺少太多数据，A每次请求都无法获取大多数客户端的ACK，应该怎么处理？

结合上面的疑问，我们可以梳理出以下问题：

目前大多数流行的分布式系统，都使用的类似Multi-Paxos算法，只让Leader提出提议，解决高并发冲突的问题。同时，要将分布式一致性算法工程化，还需要面临以下问题：

  • Leader和Follower之间如何进行数据同步？
  • 如何保证同步的效率？

  • Leader如何选举？

    • 按什么条件选举？
    • 如何达到共识？
  • 如何保证切换Leader后，数据不丢失？
  • 如何发现Leader已经挂掉？
  • 如何解决Leader假死问题？
  • 如何保证消息的顺序性？

接下来，按问题解决方案，依次对比各个算法。

ZAB

ZAB(Zookeeper Atomic Broadcast)协议是Zookeeper用来进行主从同步的协议。

  • Leader和Follower之间如何进行数据同步？

    Leader和Follower之间的数据同步有点类似于2PC的过程，不过ZAB只需要过半数据返回ACK即可开始进入提交阶段，这样做一是为了效率，二是因为后面有新的Leader当选后进行数据同步阶段从而保证数据不被丢失。

  • 如何保证同步的效率？

    同Paxos一样，ZAB只选择每次保证过半数量的实例能和Leader完成数据同步，即可返回Client提交成功信息，剩下的实例可以进行异步提交。过半提交的效率基于完全异步提交和完全同步提交之间，同时这种只用提交到一半的策略，可以是的系统最大允许一半的实例宕机系统依然能运行。

  • Leader如何选举？

    • 按什么条件选举？

    在ZAB算法中，Leader的选举比较随意，只要能达到共识即可，当选举完成后，需要查找当前follower中，所有最新的数据，然后同步给Leader，然后再由Leader同步给其他Follower，但是Zookeeper在实践过程中发现，只要直接选择拥有当前最新的数据的Follower作为Leader，就免去了查找当前最新的数据的那一步，于是在Zookeeper中，Leader的选举条件，便变成了选择当前拥有最新数据的Follower作为Leader。

    ZAB通过每条数据中的zxid来标记数据的id,zxid的前32位表示当前数据传输时，Leader的任期，任期越大，数据越新。后32位表示当前数据的index，index越大，表示数据越多。由此可以看出来，只要zxid越大，就说明数据越多，那么在选举Leader的时候，选择zxid最大的那个即可。

    • 如何达到共识？

    ZAB在选举的时候，通过(服务标识,zxid)的格式组成一个投票(Vote),每个实例只要收到投票后，会和自己上一次的投票进行对比，如果此次投票的zxid比上一次大，就将此次投票的信息记录下来，同时更新自己的投票信息，再发送出去。

    这样会带来一个问题就是，投票信息会不断的更新，同时再网络不好的情况下，可能会产生错误的选举。

    例如：分别有ABC 3个服务器，包含的zxid分别为1,2,3在选举的时候，由于服务C网络波动，它的选票迟迟没有发送出来，因此B获取到A和自己的选票的之后，就会成为Leader候选者。正是因为这样的问题，zab在进行Leader选举时，会多等待200ms。

    这种问题发生的概率非常小，因为服务C在发现无法和AB通信之后，会立即尝试重新连接

    只要一个服务的选票达到半数，就可以成为Leader，超过半数，能有效的防止脑裂。

    回想ZAB的选举过程，是不是很像Paxos， 第一轮投票，第二轮更新投票。

  • 如果保证切换Leader后，数据不丢失？

    这一点其实在上面已经说了，ZAB通过选择过程中，选取拥有数据最多的Leader，在选举完Leader之后，增加了一步同步阶段，在当选后，需要将自身所有的数据同步到大多数Follower之后，才能开始对外提供服务，通过有两种方式DIFF和SNAP

    这里想要说下，很多资料都表明，为了使Leader同步的数据保证正确，ZAB保证：

    • Leader已经Commite的消息，一定要同步到其他服务器中。
    • Leader未Commite的消息，保证要丢弃。

    让人纠结的是新的Leader怎么知道这条消息究竟有没有提交？如果这个消息在第一阶段完成后，还没来的及发送commite消息，就挂掉，那么集群中其他服务器都不知道这条消息已经提交。

    比较有说服力的说话是，当新的Leader当选后，会检查当前是否大多数Follower都有这条消息，如果有，就提交，如果没有，就丢弃。

    但是查看Zookeeper的源码，发现同步消息阶段并没有这一步，而是直接选择最大的zxid然后开始同步。其实这也能理解，因为一般这这个过程正好Leader挂掉，客户端便会收到异常，异常恢复之后，需要客户端自己检查当前操作是否已经完成，这样设计起来也更加简单。

  • 如何发现Leader已经挂掉？

    Zookeeper的实现比较简单，Follower和Leader会互相进行心跳检查，当leader发现不能连接大多数follower之后，会进入LOOKING状态，进行选举。同样当follower发现检测到leader之后，也会进入LooKING状态。

  • 如何解决Leader假死问题？

    假死问题的出现一般都是时间跳跃或者大型GC暂停，使得当前Leader与其他Follower失去连接，此时其他Follower会选举新的Leader。而当这个Leader恢复过来之后，整个系统中就会出现两个Leader，从而出现脑裂的情况。此时Zookeeper做了一下两个操作：

    • 通过epoch来过滤之前Leader发送的消息
    • follower选举新的Leader之后，会断开和这个Leader的心跳连接，这个Leader在心跳超时之后，便会进入LOOKING状态，从而变为Follower。
  • 如何保证消息的顺序性？

    Zookeeper通过TCP协议加上本身的维护了本地的消息队列，使得消息只会按顺序被处理。同时每条消息中，zxid都是递增的，因此follower也可以判断此条消息的顺序，从而判断是否需要接受此条消息。

简单总结：

可以看出来，ZAB通过主从方式进行数据同步，当主挂了之后，从可以立即选举用来代替主。主从之间通过类似2PC来提交消息。当Leader挂掉之后，剩下的Follower通过类似Paxos进行Leader选举，选举完成之后，ZAB还增加了一步数据同步阶段，用来同步新的Leader和各个Follower之间的数据。在ZAB中，zxid是对ZAB中很重要的标识，在数据同步中，通过zxid标识事务的顺序性，在选举过程中，通过zxid标识数据的新旧程序，在client和server连接过程中，通过zxid标识数据同步进度。

ZAB在CAP中，选择了CP，Zookeeper在选主过程中，无法处理写操作。同时，ZAB的读也不是强一致性的，它只是逻辑一致性，也就是本客户端一定能在任意时刻看到本客户端写入的数据，但是由于数据可能还没来得及同步到其他所有Follower中，因此其他客户端依然有可能读取到过期的数据。

本客户端即使重连也不会读取到旧的数据，因为客户端本身会记录它见过的最大zxid,当重连的时候，会拒绝连接比它旧的zxid的服务端。

Raft

一般在学习Paxos之后，一定会听过Raft，网上的说法都是Raft是Paxos的工程化实现，Raft算法中，描述了很多细节。一般来说，按照Raft就能真正实现一个分布式系统，ZAB的实现和Raft比较像，但是又有一定的区别，接下来，依然通过以上问题来解析Raft协议。

  • Leader和Follower之间如何进行数据同步？

    在Raft中，客户端只有Leader会对外提供服务，当连接到的是Follower,那么Follower会将请求转发到Leader。当Leader接收到Client的请求之后，会进行一个类似2PC的提交过程，首先Leader将数据发送给所有Follower，然后如果等待超过半数Follower发送了ACK回复之后，Leader便会更新commitIndex，并回复客户端。在每一次Leader发送给Follower的心跳过程中，Leader会将commiteIndex同步给其他Follower。

  • 如何保证同步的效率？

    和ZAB一样，每次同步只用同步超过半数Follower即可返回成功。

  • Leader如何选举？

    • 按什么条件选举？

    由于需要同步数据，因此对于Leader来说，Raft要求选举出来的Leader需要拥有当前最新的数据，Raft在选举的时候，会带上最后一条日志记录的term_id和index，当其他节点收到消息时，会和自己当前的term_id和index进行对比，只有大于等于自己的数据，则拒绝投票

    • 如何达到共识？

    这里Raft和ZAB有一定的区别，Raft中，每个服务端只有一次投票的机会，这样有可能会造成投票被瓜分，Raft的解决方案是每个服务端在触发选举前，需要先等待随机时间，然后再发出选票。

    Raft的共识策略和Paxos也比较像，第一轮先请求投票，其他服务端收到投票后会发送ACK消息并记录下来，当收到的ACK超过一半时，则转换为Leader。过半策略可以避免脑裂的问题。

  • 如何保证切换Leader后，数据不丢失？

    这里Raft和ZAB就有很大的区别，ZAB在选举后，会直接进行同步，同步完成后才会开始服务。而Raft在选举完成后就会开始服务，而Leader和Follower之间的数据同步则通过心跳同步Follower当前进度，然后Leader根据进度进行同步数据。

    虽然Raft在当选完成后即可开始服务，但是如果此时发来一个写数据的请求，请求大多数Follower还没有来得及和Leader同步，此时这个请求由于得不到大多数Follower的ACK，那么依然后被阻塞等待。

    同时，由于Raft和ZAB一样，也是通过类似2PC提交过程，因此也会存在还没有来得及发送Commite消息就挂掉的问题，Raft的处理和ZAB相反，Raft会将当前Leader未提交的消息都判定为未提交，同时只有当前term的日志过半了，才会顺便将之前term的日志提交，否则全会丢弃。

  • 如何发现Leader已经挂掉？

    Raft只有Follower在进行检测，如果在规定时间内Follower未收到Leader的心跳，Follower则会转换为candidate,然后发起新的一轮投票。

  • 如何解决Leader假死问题？

    和ZAB一样，Raft规定了term，也就是当前Leader的任期，只有当前任期的Leader才能发起数据请求。

  • 如何保证消息的顺序性？

    在Raft中，通过index标记消息，index为自增的状态，每个follower接受的下一条消息编号只能为index+1。

简单总结：

可以看出来，Raft和ZAB整体上比较相似，整体都是Leader负责写数据，Follower作为备份，当切换Leader的时候，为了保证数据的一致性，则需要数据同步，使得数据可以继续提交。和ZAB相似，Raft也是保证了CP而放弃了A，因为所有数据都需要Leader来处理，因此在选举期间整个系统服务无法使用，当然Raft还有很多其他的细节，当具体实现的时候，还需要细细揣摩。这里为需要理解的是，为什么要有这些步骤。

Redis

Redis针对数据的高可用，提供了一下三种模式：

  • 主从同步： 主负责接受数据请求，从从主那里同步数据。但是都是异步同步，可能丢数据，同时每次新的从加入或断线重连都会导致全量同步，主的压力太大。同时此方式只是用来备份数据，主挂掉后需要手动重启。
  • 哨兵模式： 哨兵模式是在主从的基础上，增加了一个监视Master的哨兵，当Master挂掉之后，哨兵可以自动切换Master，这里的哨兵充当的就是Zookeeper的角色。
  • Redis-Cluster: Redis-Cluster 结合了分片+主从，实现Redis高可用以及负载均衡，Redis-Cluster也有监视Master的功能。

在Redis中，主从同步为全异步，因此这里不再进行分析。接下来看看哨兵模式的选主过程。

Redis Sentinel在Redis起到一个类似Zookeeper的作用，但是Sentinel在集群中不用长期维护Leader，而是每当发现Redis Master宕机后，再通过选举算法选举出一个Sentinel担任Master来执行故障转移流程，Sentinel能这样做的原因是Sentinel不用读写数据，它的工作仅仅是监视Master，然后启动Master 。具体工作流程如下：

标记下线：

Sentinel标记下线和ZAB选举Leader流程差不多，当超过半数Sentinel投票该Master已经下线的时候，Master才为真正的下线。不过为了能够更快的发现下线，当其中一个Sentinel发现Master下线时，会将其标记为主观下线，其他Sentinel发现该Master被标记为主观下线后，会将和此Master联系的频率加快。

故障转移：

当一个Master被标记为主观下线后，Sentinel则会将其进行故障转移，Sentinel需要选举其中一个Sentinel来对Master进行故障转移，Sentinel的选举方式和Raft非常相像：

由于没有业务要求，因此这里Sentinel的选举目标是只要能够达到一致即可，由于Sentinel只有一次投票的机会，因此一般是谁先发现Master已经宕机，谁就容易成为Leader，当Sentinel发现Master宕机后，会检查自己是否已经投票，如果没有投票，则发起投票。当收到的ACK数量超过一半时，则认为自己已经成为Leader，则继续进行故障转移，具体细节可以参考Raft。

当选举出Leader之后，就应该对Redis服务器进行选举新的Master,这里的Redis服务由于包含业务，因此选举出来的Master应该数据越多越好，筛选策略如下：

  • 过滤已经下线的从服务器
  • 过滤最近5秒内没有发送过心跳的服务器
  • 删除最近一段时间内没有和Master同步数据的服务器
  • 选择配置的优先级最高的服务器
  • 如果有多个相同优先级，则选择数据偏移量最大的服务器

简单的说，就是在保证选择的服务器最近活跃，数据尽可能多的情况下，选择优先级最高的。

Redis-Cluster的选举方式和上面差不多，都是通过raft选举算法选举的，这里不再赘述。

Kafka

kafka主要是通过Zookeeper来管理集群，Kafka 中的Controller Leader选举就完全依赖于Zookeeper，Follower通过ZK的Watch机制来监控Leader健康情况，当Leader崩溃后，Follower会争相创建临时节点，创建成功的Follower便会成为新的Leader,选举出Controller Leader之后，再由Controller Leader控制选择Broker Leader.

但是由于Kafka业务场景是MQ，会有大量的数据需要同步，因此Leader和Follower的数据同步无法依赖于Zookeeper。详细如下：

Kafka中提出了几个概念：

AR（Assigned Replicas）: 所有副本

ISR（In-Sync Replicas） : 与Leader保持一定的同步进度的副本集合

OSR（Out-of-Sync Replicas）: 与Leader未保持一定的同步进度的副本集合

其中： OSR+ISR=AR

在Kafka中，并没有使用大多数(quorum)的概念，而是使用了ISR管理，在Kafka中，如果想要保证数据的强一致性，则需要规定客户端需要获取ISR中所有客户端的ACK，才能返回成功，Kafka只保证数据不丢失，但是数据可能重复，这给kafka的Leader选举带来了很多的方便性：仅仅依赖于Zookeeper。Kafka通过动态ISR和OSR，使得kafka集群能够容忍最多(N-1)数量的节点崩溃。

Kafka中Leader和Follower中数据同步也需要保证有序性，其通过LEO标识，每次Follower再给Leader发送心跳的时候，会带上自己目前同步的进度（LEO），然后Leader根据进度返回下一条数据。

Kafka之所以能这样设计，是因为Kafka的所有消息都是追加，而不用修改，因此可以很简单的维护集群，但是这样带来的问题的也很明显，数据可能重复，需要客户端手动去重。

总结

可以看到，对于分布式一致性，其实并没有一个通用的解法，Paxos和Raft的核心思想便是多数派（Quorum）,通过多数派能够避免意见不一致的情况。在业务系统中，可以理解Paxos和Raft的核心思想，然后结合自身的业务情况，对算法进行优化和取舍，比如Redis使用Raft算法进行选举，比如ZAB借鉴Raft算法进行数据同步，比如Kafka结合自身的业务情况，定义的ISR集合。

参考文章：

《Zookeeper分布式协同技术详解》

《深入理解Kafka》

https://my.oschina.net/pingpangkuangmo/blog/782702

https://zookeeper.apache.org/doc/r3.5.0-alpha/zookeeperInternals.html