分布式共识算法

· 2022-01-03 · # 算法 # 分布式

开篇

首先提大分布式系统你的第一印象是什么
试想一下心目中的分布式系统的特点，大胆总结下：

系统可用角度：无单点故障，保证系统可用性
系统性能角度：通过负载均衡，可以充分发挥集群节点的性能
系统扩展角度：基于集群可扩展能力可以持续扩展横向能力，增加节点来支持更高需求的场景

这些都可以归纳为分布式系统出现的意义以及解决的问题，反推回来，随着数据规模和服务计算能力需求越来越高，之前的单个节点已经无法满足系统的计算和存储要求，并且随着摩尔定律面对自然法则越来越乏力这些现实的问题。基于这些就不难理解分布式系统出现的意义了

当然类似人类社会，当团队规模从几十增长至几万时，带来是生产能力的规模提升，同时也要面对这各种协作和沟通的问题。也就上学那会会告诉你1+1=2。所以在整个生产组织的提效上，制度和规则是必须的

分布式系统也是类似，计算存储能力提升的同时也带了这些问题：

节点通信延迟：服务连接、请求超时等各种未及时响应的问题
节点故障/恢复：节点甚至机房宕机导致服务不可用
网络分区-脑裂：机房网络问题，导致数据不一致
拜占庭问题：存在恶意节点，恶意行为
这些问题基于环境是否置信又可以分为两类。1，2，3都是在可置信情况下，4则是在非置信情况下
而在共识算法的出现完善后都可以得到解决，而在一些其他应用比如区块链的研究，共识算法也是非常重要的基础，在我看来，共识可以理解为两个层面：

点的层面：也就是多个节点就某个数据达成一致共识
先的层面：即多个节点对多个数据的顺序达成一致共识
接下来我们看看在算法的演进过程中又是如何解决上面的问题的

算法演变

拜占庭问题

拜占庭错误是莱斯利·兰伯特在《拜占庭将军问题》中提出的一个错误模型，这个模型的场景是在一个完全不可信的场景，也是在分布式领域中最为复杂以及经典的容错模型了。当然简单解释就是节点存在着恶意行为

故事背景

类似投票裁决的场景，在<<鱿鱼游戏>>里男主第一次在进入比赛后进行了一场投票选举：Y or N来决定是否继续游戏，大家私下各自商量着自己的决定，如果有人背叛了同伴，开始从中误导分离这个团队，自己最后临时改变了策略，那么就可能直接影响着最终结果
我们简化为最小可解释模型就是：二忠一叛问题
假设三人团队中A，B，C商量这是否继续游戏，按照“少数服从多数”来表决，所以有两人一致就可以了

算法流程

假设大家内部意见并不一致，在内部讨论时，我们正常的预期是这样的：

可以看到无论是选择继续游戏还是放弃游戏，结果都是：三人的最终达成一致投票结果是一样的

那么如果中间(假设是B)有人有起了小心思，就会是接下来这样：

我们从各自视角看下结果
A: 2Y + 1N
C: 2N + 1Y
显然这直接干扰了A，C两位的最终选择，可想而知，结果肯定有个人是被骗了(原地心态爆炸)

解决方案

这个问题后来有了两种解决算法，分别是口头版和签名版，目的就是协调整个团队(集群)的一致

口信消息型

3人太少了，再拉一位D入伙，也就是变成了4人的协商
几人约定，如果没有收到其他人的结果，就执行统一默认的：比如放弃游戏(N)
最终进行两轮商议投票
这个方案是兰伯特论文里阐述的：[The Byzantine Generals Problem]https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/
最终整体流程是这样的：
Round 1
新入伙的D作为指挥官(proposer)，将作战信息发送发送其余三位
原本团队的成员A,B,C 将收到的消息作为结果，如果没收到执行默认
Round 2
原本团队成员A,B,C 分别发送消息给其他两位成员(除去新加入的D)
最终，原本团队按照之前原则“少数服从多数”，执行最终投票结果
对于一叛问题，在这个方案里，叛徒要么存在原来团伙，要么存在新加入的D，因此两种情况我们分别讨论下：

最终结果(不包含D的投票结果)：
A：2Y+1N
C: 2Y+1N

最终结果：
A,B,C都是：2N+1Y
如果D给的信号是2Y+1N，则A,B,C的结果就是2Y+1N，也就是说还是会达成一致
可以看到无论B怎么操作A,C都是达成一致(Y or N)
方案总结
可以看到无论叛徒存在哪方都不能使得团队产生分歧，最终都可以达成一致
当然这个算法是有一定前提的：
叛徒个数x是已知的
叛徒为x，则忠诚人数不小于3x+1
叛徒个数x决定了需要进行多少轮的协商
显然这个算法存在几点问题：

需要引入额外人员(节点)参与，不过此我们可以通过签名消息也就是第二种解决方案来解决这个问题
并且对叛徒(不可信节点)是已知可控的，因此叛徒太多，需要O(n^(x+1))的消息，网络开销太高，因此实际应用中用的是PBFT(下面会介绍)
达成一致的结果也许并不是想要的，比如真是场景需要就Y达成一致，但最终还是会得到非预期的结果

签名消息型

这个算法也有一定前提：

每个人的签名无法伪造，而且就算伪造后可以被发现
每个人都可以验证别人的签名和本人是否匹配
在这样的前提下，再来分析上面的两种情况
对于A(忠)发起请求，由于B伪造了A的请求，对于C就可以校验后进行忽略，因此最终A,C结论都是Y
对于B(叛)发起请求，由于A,C接收到的不同指令但指令集合一样，所以可以根据一定规则(排序)进行选取
介绍了算法流程，那么又是如何实现签名消息的验证即加密解密的呢，毕竟这是这个算法的前提
具体可以参考https里数字签名、证书的实现 https://www.zhihu.com/question/52493697/answer/1600962734
总结来说就是使用非对称加密对消息内容进行摘要，其他成员基于已有公钥进行解密比对

PBFT

场景描述

实际上上面讨论的拜占庭问题的解决方案都是理论化的基础，也存在诸多问题，核心还是说在叛徒存在的场景下如何就达成一致，但最终是在有叛徒(伪造节点)情况下具体什么结果是无法控制的。
因此这个算法的真正落地是在PBFT的应用，在区块链(公有链场景)的实际场景就已经有很多的使用
PBFT也是在口信型和签名型的基础之上进行改进落地的，因此算法的消息也是签名消息

算法流程

这里我们以基本规模为例，1客户端+1主节点+3备份节点+1问题节点(节点3)
先看下宏观的基本流程

客户端发送消息给主节点
主节点广播请求给其他节点，节点执行pbft的三阶段共识算法
节点处理三阶段流程后，返回消息给客户端
客户端收到来自f(问题节点数)+1个节点的相同消息后，代表共识已经成功完成

核心三阶段

客户端向主节点发起请求，主节0收到客户端请求，接着向其他节点发送

pre_prepare阶段

主节点发送消息后，节点1，2，3接收到消息后进入Prepare阶段，并分别广播消息给其他节点

prepare阶段

进入prepare节点后，当某个节点接收到2f(f为问题节点数)个一致的消息后，会进入提交阶段，而问题节点的表现就是对其他节点的请求无影响

Commit 阶段

进入提交阶段后吗，各节点分别广播消息给其他节点，相当于说我已经准备开始执行指令了
最后，当节点收到2f+1的验证通过的消息(包括自己)，这时也就意味着大都数节点已经达成共识，那么就可以执行执行，并最终返回给客户端成功执行消息

而对于客户端而言，如果收到了f+1个相同的响应消息，说明各个节点已经达成了共识。当然，如果超过超时时间，客户端也可以重新发送请求

Paxos

解决了置信问题，没人捣乱了，那么接下来大家就可以坐下来商量下如何达成共识了

这里就不得不提Paxos算法了，现在我们接触到的共识算法都是基于此改进的
而在Lamport提出的Paoxs提出包含了两种，Basic Paxos & Multi-Paxos

Basic Paxos 算法：多节点如何就某个值达成共识
Multi Paxos 思想：执行多个 Basic Paxos ，就一系列的值达成共识
先来说Basic Paxos描述的是多个成员节点如何基于一个值达成共识，这可以被看作共识算法的最小实现

场景描述

为了方便理解，所以现在是这么个场景，在一个分布式集群中，集群有A,B,C 3个节点组件，基于集群的变量KV信息的更新需要达成一致
简单来说就是多节点更新某个Key，其他节点就此Key的Value达成一致

角色对象

在几乎所有的共识算法中，我们都会接触到这几类角色，他们存在的意义是一样的，因此需要提前在整个上下文中达成一定共识

提议者(Proposer): 提议想达成共识的值，在生产场景中可以客户端也可以是接受到客户端请求的节点
协调者(Coordinator): 转发提议消息以及协调和保存结果确认，通常存在于二阶段提交
接受者(Acceptor): 对于提议者的提案会参与协商并存储结果值最终更新自身的状态机
学习者(Learner): 接受最终协商后的结果，在一些算法中也叫做Folllwer，被动接受协商后结果

为了方便理解和描述，对于提案都有自己的编号以及提案内容，我们以P[n,v]标识一个提案
n标识提案编号(唯一标识)，通常是生成自增id，v标识提案内容比如{ K:'SEC_KV_AUTH，V:1}

问题思路

基于这样场景的需求，核心就是能达成结果一致，是不是可以立马联想到二阶段提交，这也是最简单直接的方式了，事实上Paxos也是这么做的
但是他们都会存在这样的问题：

同步阻塞： prepare阶段在资源预留期间，其他事务是无法修改此资源的，需要等待至事务结束
协调节点故障：如果prepare阶段结束后，协调节点宕机，那么其他节点资源将会被锁定无法释放
数据不一致：还是协调节点故障，只不过是在提交commit部分节点后故障，那么就会存在节点收不到commit命令而和其他节点数据不一致
基于上面的问题，其实也有很多解决方案，比如三阶段提交或者TCC(Try-Confirm-Cancel)事务模式(事实上，Paxos也是这么做的)，具体可以参照阿里的Seata和公司内部的ByteTx 的TCC事务模式的实现

和数据库层面的事务操作所不同的是，TCC需要业务实现各自的确认(Confirm)和撤销(Cancel)操作，并且是幂等的，因为请求都会有失败重试

算法流程

Prepare阶段

基于以上背景，根据时间线准备阶段流程是这样的：

客户端1提交提案，版本号基于时间递增，假设版本好号为V1
节点A,B,C是参与协商节点，A,B 收到了客户端1提案消息，分别表示I'm ready，并返回当前接受的最大版本号V1，最终返回[Yes,V1]
客户端2提交提案，假设版本为V3
节点A,B收到了客户端2的提案，并且之前提案1还没通过，而且又大于之前的提案版本，因此开始接受客户端2的提案
节点C第一次收到客户端提案，版本为V3，因此就提案3进行回复并返回当前接受的最大版本号V3
节点C最后收到了客户端1的提案，但是因为已经接受了提案V3版本号更大的提案，因此不做处理

Accept阶段

接受阶段是在收到了大都数节点的成功回复后发起的，随着时间演进：

客户端1收到了A,B的回复[Yes,V1]，多数ready后发起请求[1,data1]
接收者A,B,C此时接受的最大提案都是V3，因此对于客户端1的请求进行拒绝
客户端2收到了来自A,B,C的所有回复[Yes,V3]，多数ready后发起请求[3,data3]
接收者A,B,C根据请求和自己接受的提案版本比对后，通过最终提案[3,data3]

Multi-Paxos

场景描述

基于二阶段提交达成了单个值的共识，而在实际场景中，面对诸多的数据，我们需要对多个Value达成一致
所以是不是多次执行Paxos算法即可，在一定数据规模下讲是可以的，需要达成一致的值较多，多次的Paxos算法就会存在问题

多节点集群下，多节点多提案就会引发冲突，因此提案协商的成功率就会下降
基于二阶段，本身的通讯次数就会很多，多节点情况下，节点的通讯延时就会被进一步放大

算法思路

为了解决多提案者的情况，结合数据库的Master-Slave模式，可以引入领导者节点，由领导者作为提案者
至于领导者如何选举，这个则需要根据各自服务的需求来实现，因为每个系统对于领导者的判断标准不一样，而选举算法最直接的可以基于Basic Paxos来实现，而如果领导者节点故障，则进行新一轮选举
基于领导者，就可以对Paxos的二阶段进行优化的，也就是省去了准备阶段。因为不存在了提案冲突这个问题，节点通讯数量也降低了，离目标又进了一步
至于一致性实现就和Basic Paxos的二阶段的接收阶段就没什么区别了，依旧按照"多数原则"

算法总结

Multi-Paox是在之前的基础之上引入了领导者来进行优化，从而实现多次执行Basic Paxos的效果。这个思想在很多的变种算法和场景都有所运用，比如接下来要说的Raft

ZAB

场景描述

在开篇一开始，我们说过共识问题的线的层面就是需要解决如何就多个节点的对多个数据的顺序达成一致，
很多场景不仅需要对值的一致性进行保证，而对于值的顺序也有一定的要求，比如ZK因为底层作为目录树的设计，目录是有父子关系的也就是说有一定的依赖关系，因此就必须保证一定的顺序性，此时基于Multi-Paxos的算法就无法满足了
因此zookeeper就是基于ZAB协议实现的(当然了Raft也可以实现)，那么在ZAB又是如何实现执行顺序的

算法流程

为了说明这个问题，我们模拟这个场景：集群中存在4个节点A，B，C，D，其中A作为领导进行提案X，Y对应的唯一事务标识符为<1,1>&<1,2> ，格式为<epoch,counter>
其中类似raft中的任期思想<1,2>表示任期1，计数为2

主节点收到客户端请求，生成唯一事务id的消息请求<1,1>:X & <1,2>:Y，并按循序广播给各节点
因为主节点基于TCP协议顺序发送提案消息，因为Node B,C,D接收到的也是顺序消息
主节点接收到基于某一提案，比如X的多数节点的成功响应(暂无提案)后开始提交提案X
因为在同一任期内的提案是递增的，因此提交时会根据事务大小进行提交
各节点收到提交提案消息，执行成功后返回给LeaderA
主节点LeaderA收到多数执行成功回复后响应给客户端

算法总结

ZAB在之前Multi-Paxos的思想上，对提案实现了消息的事务唯一和递增，通过提交提案时比较事务标识符的大小而保证了指令的顺序性，最终实现想要的共识线层面

Raft

作为现在共识算法的首选，相对也最为成熟，如今的云原生的大环境下，很多大型系统都选用了Raft作为核心共识算法，比如tikv、Etcd、Consul等
因此在掌握了以上的结论后，再分析下Raft的核心实现，会发现很多结论都得到了验证

领导者选举

上面说过领导者选举，完全可以基于Basic Paxos来实现，只是每个系统的定义标准不一样，在Raft的选举过程中，定义了几种状态

Leader：处理写请求，管理日志复制和连接其他节点的心跳检测
Follwer：接收Leader的消息，必要时需要推荐自己当选Candiator
Candidate: 当领导者有故障后，发送选举消息，此时相当于选举提案人
选举的详细过程动画演示 http://thesecretlivesofdata.com/raft/

大致概总结下就是：

初始状态，所有节点都是Follwer状态，并且每个节点的超时时间是随机的，这里的超时时间简单了说就是等待领导者的心跳请求的超时时间
节点A超时时间最少，因此最先变为候选人并增加自己的任期编号为1，开始向其他节点发起投票RPC请求，进行Leader选举
B,C节点接收到任期为1的消息，因为之前没有收到该任期内的消息，因此可以投票给节点A(认为可以理解为二阶段的提案版本)
A在选举超时时间(相对会比较大)内收到多数投票，则成为Leader，并开始定时发送心跳信息给其他节点(证明自己活着，不要再选举了)，选举结束
如果网络等问题产生选举超时，重置超时时间，并开始新一轮选举
基于领导者开始发起指令提案，依据多数原则达成一致后Leader实现指令的共识并提交状态机返回客户端
其他follower节点根据心跳信息或者日志复制RPC消息应用Leader最新提交的日志项

当然在选举的过程中，可能会遇见这类问题(这两个问题在动画演示中其中也都解释了)
问题1：目前是一个candidate进行选举，如果有多个，比如2个候选人同时发起投票进行选举

此时会等待进行下一轮选举，按照超时时间，可能就是节点A发起了下一任期的投票了

问题2：遇到网络分区异常，也就是通常说的脑裂问题，会出现多leader情况，如何解决

如上图所示，CDE和AB被划分在两个网络分区，两个分区分别进行了选举，推选C&B为各自Leader
分区故障前
不过由于AB分区提交的提案无法得到大多数节点响应，因此是无法进行commit的
CDE分区因为可以得到大多数节点影响，因此可以正常得到正常提交
故障恢复后
节点A,B由于LeaderB，发现比自己Term更高的消息，因此会退出Leader并和节点A同步最新的日志项，最终不同分区节点的Log Entry保持一致

问题3：ZAB & Raft都可以实现顺序性，主要区别是什么

一致性：从系统本身实现角度出发，ZAB实现了最终一致性，Raft读写都从Leader实现强一致性
事务表示方式：zab用的是epoch和count的组合来唯一表示一个值, 而raft用的是term和index
Leader选举方式：也就决定了选举方式不一样。Raft基于每个节点设置不同的超时时间来自行发起选举，并且每个节点每任期中只会投票一次。ZAB每个节点在任期内可以发起多次投票，遇到更大的则更新并分发给其他节点。综合来说，Raft的选举效率更高
超时选举方式：Raft只有follower会检测Leader的心跳超时，超时则触发选举，ZAB中Leader也会检测是否收到半数节点的心跳回复超时并触发选举

问题4：想实现这样的领导者模型的算法，需要怎么实现
根据Raft和ZAB的整体实现，不难得出，这类共识算法的实现条件：
领导者选举->指令共识(二阶段提交)->日志复制应用->日志恢复

Log entry复制

集群中选举好了Leader就可以进行正常的协调通信了，而这个过程就可以理解为对日志项的复制和应用到状态机的过程

日志项内容

指令：用户指定的数据，也就是需要达成一致的数据，通常由客户端提供
索引值：日志项对应的物理索引值，可以理解为基于索引可以在连续的日志中查找到具体日志内容
任期编号：创建日志的领导者的编号(很关键，用于数据比对同步和数据修复)

Hashicorp Raft Log Code

type Log struct {        // Index holds the index of the log entry.
        Index uint64
        // Term holds the election term of the log entry.
        Term uint64
        // Type holds the type of the log entry.
        Type LogType
        // Data holds the log entry's type-specific data.
        Data []byte
        // Extensions holds an opaque byte slice of information for middleware. It        Extensions []byte
        // AppendedAt stores the time the leader first appended this log to it's
        AppendedAt time.Time
}

日志复制同步

在Raft中领导者是强制跟随者直接复制自己的日志项用来处理不一致的日志。这也是强领导者模型的优势
当领导者和跟随者日志产生diff时，根据日志项的任期和索引来进行一致性检查，并通过日志复制RPC
复制并更新不一致的日志项，这里不做详细展开

Quorum NWR

场景描述

理解了Raft算法的整个过程，其实已经能够满足绝大多数的应用场景了，而在一些场景我们其实更想自定义的实现，而Quorum 机制是分布式场景中常用的，用来保证数据安全，并且在分布式环境中实现最终一致性的投票算法。在一些企业级应用的InfluxDB、Cassandra都有运用此类算法

算法流程

首先需要明白NWR的三要素

N：副本数，也就是一份数据集有多少副本，这些副本会分布在不同的节点
W：写一致性级别，表示写入W个副本才能算是完成写操作
R：读一致性级别，表示读取一个数据对象需要读取R个副本并返回最新的那份数据

以读取Data2数据为例，此时副本数N=3，如果需要实现强一致性，则设置W=2&R=2即可
此时满足W(2)+R(2)>N(3)
因此如果W+R<=N，可以推出，整个系统可以保证最终一致性，即可能返回旧数据
整体和抽屉原理一样，还是比较容易理解的

而在实际的生产环境中，一致性级别通常也会被定义为诸如all、one、quorum(大多数)这些级别来分别应对不同的数据需求场景

TimeLine

1987年 ACM论文提出Gossip protocol ，用于分布式数据库系统中各个副本节点同步数据
1989年莱斯利·兰伯特提出Paxos，使其获得2013年图灵奖
1999年 Miguel Castro和Barbara Liskov在发表的论文[2]中首次提出PBFT算法
2006年 Paxos算法在Google的研发团队才在生产环境中落地，但初期算法实现并并未成熟
2007年 ZAB随着zooKeeper的开发而应运而生
2013年斯坦福大学迭戈·安加罗（Diego Ongaro）和约翰·奥斯特霍德（John Ousterhout）深入研究Paxos协议后提出了 Raft

维度总结

经过上面算法的慢慢演进，最终我们根据拜占庭容错、一致性、性能、系统可用性总结如下

	拜占庭容错	一致性	性能	系统可用性
2PC	否	强一致性	低	低
TCC	否	最终一致性	低	低
Paxos	否	强一致性	中	中
PBEF	是	-	低	中
ZAB	否	最终一致性	中	中
Raft	否	强一致性	中	中
Quorum NWR	否	强一致性	中	中

场景实践

生产实践

Etcd 原生化

Etcd 本身作为云原生最热门存储的基础，应用场景十分广泛，包括服务发现、分布式锁、配置存储和分布式协调。而在Raft在Etcd中的作用也举足轻重，我觉得可以一起看下内部是如何结合使用的
整体架构

在etcd的架构设计中，etcd基于raft算法实现了节点间的数据复制、数据一致从而实现服务的高可用

指令执行

首先我们先看下在etcd中一条KV写请求的执行过程

client端通过负载均衡算法选择一个etcd节点并发起grpc调用
调用过程中会经过一系列的拦截器进行请求过滤
经过Quota配额模块，根据请求QPS、当前db限额、存储容量决定是否超限
1. 超限后集群产生告警并禁止继续写入(默认db配额2G，禁止请求写入日志并同步其余节点)
请求通过后，进入KVServer核心处理层，此时作为内部raft层的客户端向raft层提交提案
发起提案前会经过鉴权等检查并生成提案id
提案内容就是本次请求需要执行的指令，比如"put key value"
发起请求后等待raft层消息结果通知
raft层内部经过RaftHttp网络模块进行指令转发，多数节点通过后，提交日志状态
指令包含了任期编号、索引信息、提案内容、日志类型等
半数节点通过(持久化)后，通过channel返回可执行提案
etcdserver从channel读取提案内容，传递给Apply模块进行提案内容执行
Apply模块基于MVCC模块执提案内容并更新最终状态机
经过上面的流程，可以看到etcd内部是如何基于raft实现数据写入的，那么又是如何保证数据一致的

服务可用性保证

机制一：领导者选举
Leader节点crash后，Follower节点因为收不到心跳信息，开始发起投票，进行新Leader选举
为避免同时竞选，引入随机的等待发起选举时间
Crash的Leader节点启动后，再次成为Follower节点并同步Leader最新日志
机制二：日志复制规则
Leader收到提案消息为此生成日志条目，然后遍历Follower列表和日志的应用进度信息，并为每个Follower生成追加类型的RPC消息，消息中包含Follower需要复制的日志条目
同时，日志的复制还遵循以下规则：

如果日志在某个任期中已经被提交(提交后可能还未通知Follower)，这个条目不会删除并且会应用到新Leader
追加日志中包含应用的前日志条目信息来进行一致性检查，直到匹配到一致日志条目才会追加
机制三：选举规则保证安全
如果Leader Crash后，剩余Follower并不是都可能成为新Leader，选举投票规则还会基于
收到投票请求的前后顺序
发起投票的节点应用的日志数据是否是最新的
发起投票的节点应用的任期是否是最大的，每个节点在每个任期只能有一个投票权
最终投票需要半数以上节点支持
基于Raft的这些特性和实现机制最终保证了etcd服务的数据一致性和服务高可用

代码实践

Raft实现
[Hashicorp Raft] https://github.com/hashicorp/raft