分布式共识问题

点击上方疾风先生可以订阅哦

在讲述分布式的共识问题之前,我们先了解下什么是拜占庭将军问题, 其次从拜占庭将军问题来认识什么是分布式共识问题,与分布式一致性的区分在哪里?然后推演分布式共识问题产生的原因以及解决共识问题的策略算法有哪些,对应的适用场景有哪些?接下来我们可以带着疑问来逐步揭开上述问题的本质.另外这里要先说明一点,这里讲述的服务节点不可用包含网络超时/服务节点出现故障/网络通信被伪造等情况.

拜占庭将军问题

拜占庭一般性问题

• 拜占庭军队中的每一个师都有自己的将军,并且由该将军负责指挥作战
• 现在拜占庭军队中的将军存在一些叛徒,将军们可以通过信使进行相互沟通作战方案
• 现在对拜占庭军队要求是:

1. 所有忠实的将军都能够采取相同的作战计划.
2. 少数叛徒不会使忠诚的将军们采取错误的计划从而导致最终的作战失败.

问题重述

• 所有忠诚的将军都得到同样的信息，他们将以某种方式得到同样的决定.
• 一个忠诚的将军发出的信息应该被所有其他忠诚的将军所采用.

什么是拜占庭将军问题

基于上述的问题的理解,假设现在拜占庭军队中有三个师,每个师都有自己的将军,现在要准备开始作战计划攻打城池,现在需要满足上述讲到的要求,即保证每个师的忠诚将军都能够采取相同的作战计划以防止被叛徒信息误导采取错误的决定.此时需要每个师派发行使进行通信协商,同时为了保证协商存在可靠性,即下面的半数投票的可靠性.

少数服从多数的投票可靠性

• 每个师的将军可以发表自己对作战方案的计划,并通过信使通知其他师的将军们
• 其次,每个师的将军接收到其他师的将军们的作战方案时候,采取默认少数服从多数的方案作为作战方案执行.

这个时候我们可以看到,每一个师的将军都能够提供方案,说明是具备作战的指挥权的,相对地,其他师的将军就作为副官,负责执行作战方案.于是对于一个拜占庭将军问题可以进行以下归纳.

拜占庭将军问题

我们可以将问题进行简化为一系列由一个指挥官和多个副官组成的问题,即拜占庭将军问题:

• 如果所有的副官都是忠诚的,那么他们必然遵循相同的作战命令
• 如果指挥官是忠诚的,那么所有忠实的副官也都会遵循其所发出的命令

简而言之,拜占庭将军问题就是如何在可能存在有叛徒的情况下,采取合适的通信机制来保证忠诚的将军能够达成共识采取一致的作战计划.

不可能的结果

如果忠实于将军的将军少于或等于2/3，则不存在解决方案.

分布式共识问题

什么是分布式共识问题

基于拜占庭将军问题的分析,我们将其翻译为分布式系统相关的术语,并对其进行阐述如下:

• 拜占庭将军: 即分布式系统的服务节点
• 忠诚的拜占庭将军: 即分布式系统服务正常运作的服务节点
• 叛变的拜占庭将军: 出现故障并发送误导信息的服务节点
• 信使被杀: 服务节点之间出现通信故障,导致信息丢失
• 信使被间谍替换: 服务节点进行网络通信过程中信息被黑客攻击,通信存在劫持以及信息伪造

而分布式共识问题就是在分布式系统中,我们要如何保证系统服务节点之间的通信接收到的消息指令都是可靠且一致的.

分布式共识与一致性区分

在讲述分布式的共识与一致性之前,我们先来看下上述的图解,用户发起请求向分布式系统集群服务请求资源然后服务资源给予响应,这个时候我们考虑以下的场景:

• 首先,用户A先发起一个事务操作的请求到集群服务,这个时候集群服务接收到事务操作请求,这个时候问题来了,集群服务存储节点谁来负责处理事务请求的操作,进行事务操作之后数据如何同步到各个服务节点上,即集群服务节点如何对事务请求操作达成共识.
• 其次,用户B发起一个非事务的读取请求到集群服务中,此时读取到数据应当是A进行事务操作之后最新的数据,也就是集群服务节点需要保证给到用户B的数据是最新修改的数据,即服务节点的一致性问题.

从上述可以看到,对于分布式系统的共识与一致性问题其实关注的点不一样的,即:

• 分布式共识问题:回归到事务请求操作的思考层面,就拿扣减库存的分布式事务为例,它必须保证并发的原子性操作,那么此时我们就需要对共享资源进行加锁互斥保证集群中只有一个节点能够进行事务操作;其次当服务节点完成事务操作之后,还需要进行数据同步到冗余服务节点上,那么进行事务操作的服务节点必须向集群其他节点发起数据同步操作并等待响应(是不是类似于上述的拜占庭将军问题);另外关于分布式共识还包含通过原子组播的方式处理进程对消息传递的顺序一致性.
• 分布式一致性: 通过上述的查询请求操作,即对于集群冗余服务的数据副本之间对外表现的数据是一致的,类似于JDK中的valotile机制,保证在多核CPU处理器上读取到数据是最新修改的.(后续再单独说明分布式的一致性)

分布式共识问题:即为了达到共识,每个进程都发出自己的提议(propose),最终通过共识算法,所有正确运行的进程决定(decide)相同的值,如下图所示:

在上面的图示可以看出,不同的进程p0,p1,p2以及p3分别输入一个数据值,然后通过执行程序来处理并交换输入值,保证最终输出的数据值都是一致的.即不同进程的输入值通过自身相同的一套程序进行交换处理输入数据并最终都输出一致的数据v.

分布式共识特性

摘录分布式共识的英文阐述如下:

1. Termination: Every non-faulty process must eventually decide
2. Agreement: The final decision of every non-faulty process must be identical
3. Validity: If every non-faulty process begins with the same initial value v, then their final decision must be v

• 终止: 每个非故障的进程最终必须作出提案的决策
• 协议: 每一个非故障的进程最终作出的提案决策都必须是一致的
• 有效性: 如果每一个非故障的进程均以相同的初始化值v作为提案的输入,那么最终提案决策的输出都必须为v.

对于分布式共识应用场景有:

• 集群服务节点的Master/Leader选举策略
• 集群服务节点进程加锁资源互斥
• 集群中某一个服务节点故障的判定策略
• 时钟相位同步问题
• ATC服务(Air Traffic Control): 空中交管控制系统,即所有的在空飞机都看到画面都是一致的(Air traffic control system: all aircrafts must have the same view)

关于ATC可以参考:

https://science.howstuffworks.com/transport/flight/modern/air-traffic-control.htm

共识问题推演及解决方案

问题推演

基于拜占庭将军问题,现假设有三个军队的将军,现在准备拟定攻城的计划,三位将军对此开始进行各自计划的拟定(进攻或者是撤退的策略)并由信使负责消息的传递,最终通过“少数服从多数”原则来决定最终的决策方案.

正常情况

三个军的将军都是忠诚的,那么对于发出进攻或者是撤退的策略最终应当是一致的.

A将军此时发起决策提案为进攻,对于B和C正常接收到的信息是进攻;B将军发起的决策提案为撤退,对于A和C正常接收到的信息为撤退,C将军发起的决策提案为进攻,那么这个时候对于A和B看到的提案为进攻,这个时候我们分别思考A,B,C三位将军接收到的提案为:

A将军: 自己进攻的提案 + B将军的撤退提案 + C将军的攻击提案,因此最终决定进攻.

B将军:自己撤退的提案 + A将军的进攻提案 + C将军的进攻提案,因此最终决定也是进攻.

C将军: 自己进攻的提案 + B将军的撤退提案 + A将军的进攻提案,因此最终决定也是进攻.

但是这个时候我们需要看到上述决策成功需要满足要求:

1.所有的将军都是忠诚的 2.在上述的半数投票过程中,需要满足参与投票的将军个数为2n+1,不然无法决定投票结果.

二忠一叛问题

如果三个将军中有一个将军出现问题,那么此时的情况又被变成如下的情况:

1.其中一个将军为叛徒 2.其中一个将军的信使被间谍替换 3.其中一个将军的信使中途被杀

如果其中一个将军为叛徒抑或是C将军的信使被间谍替换,假设为C将军叛变,那么此时产生的情况如下:

A将军: 自己进攻的提案 + B将军的撤退提案 + C将军的攻击提案,因此最终决定进攻.

B将军:自己撤退的提案 + A将军的进攻提案 + C将军的撤退提案,因此最终决定是撤退.

C将军: 因为自己本身是叛军,当然在战场上肯定也是撤退.

这个时候三位将军采取最终方案是不一致的,这样会导致A将军直接受到伏击被敌军歼灭;

如果C将军的信使中途被截杀,那么此时产生的情况如下:

A将军: 只接收到B将军的撤退提案 + 自己攻击的提案, 这个时候是无法进行决策

B将军: 只接收到A将军的攻击提案 + 自己撤退的提案, 这个时候也无法进行决策

C将军: 接收到A将军的攻击提案 + 自己的攻击提案 + B将军的撤退提案,采取攻击提案.

这个时候可以看到A,B,C三位将军最后做决策的时候将无法保证最终的提案一致性而采取相同的行动.

问题小结

通过上述的分析,我们将其转化为分布式系统集群三个服务节点A,B,C之间可能存在的问题如下:

当向分布式系统集群服务发起事务操作请求的时候,如果这个时候存在服务节点发生故障(信使被截杀)抑或是服务节点在消息通信过程被劫持,整个集群服务节点将无法对当前的事务请求操作采取一致性的行动.

口头消息的解决方案

无签名的口头消息要求以及含义

• A1:每个服务节点发送的每条消息都能够被正确接收

1.连接两个服务节点之间的通信介质的故障与服务节点发生的故障是无法区分的.如超时网络不通/服务节点宕机均为不可用等均视为服务节点不可用 2.如果出现线路故障表示分布式系统中的集群服务节点多了一个不可用的服务节点.

• A2:集群服务节点知道消息发送者的信息

不需要通过网络交换就能知道消息发送者的信息

• A3:能够检测到集群其他服务节点的心跳

需要有超时机制

口头消息的算法

算法定义

基于上述的假设,现有一个算法函数major满足fn=(V1,V2,...Vn-1),该函数表示集群服务节点中每个节点一个提案值vi,fn表示集群中vi占过半投票对应的提案值v,而口头消息解决算法有一个前提条件,那就是集群服务节点不可用的个数m必须满足m<n/3,(n为当前集群服务节点的总数),也就是集群服务节点总数n最小值为n=3m+1.而对于算法的描述存在两种选择如下:

• 如果v的提案值存在那么就执行提案值v的动作,否则采取默认的行为(撤退)
• 其次,假设vi 为上述(V1,V2,...Vn-1)一系列有序的集合数据的中位数,那么就执行vi的提案

算法描述

现对于3m+1的集群服务节点选举一个具备指挥权的服务节点作为leader,其他节点作为replicate,这个时候存在以下两种情况:

当m=0时,即不存在服务节点不可用时,其算法执行的策略为:

• leader节点向每个replicate节点发送其提案指令v
• 所有replicate节点接收到其提案指令v的消息时执行,如果没有收到执行默认的“撤退”行为.

当m>0时,其执行的算法如下:

• leader节点向每个replicate节点发送其提案指令v
• 所有replicate节点接收到提案指令v的消息时作为执行命令的提案vi,如果没有收到消息则把默认的“撤退”行为作为其执行的提案vi,并此时的服务节点作为一个新的leader向其他n-2个服务节点(除了服务自身节点以及其对应的leader节点)发起提案vi
• 对于replicate节点(V1,V2,...Vn-1),假设当前服务节点为V1,那么V1节点在经过上述步骤2的操作之后,也会接收到其他服务节点(V2,V3,...Vn-1)节点的消息提案,分别设置对应值为v2,v3,...vn-1,其中每一个节点发送过来的提案值都是采取上一步的动作,除了其中的不可用的服务节点.

经过上述的算法,对于存在m个不可用或者是不可靠的服务节点,需要经过m+1次的递归发起提案请求,同时可以递归推导得出O(m)调用(n-1)次递归独立执行O(m-1).

口头消息解决方案分析

基于上述的分析,如果仅有上述的集群服务的3个节点,基于口信消息的方案是无法解决拜占庭将军问题的,现分析如下:

现在我们从拜占庭军队的三位将军A,B,C选举一位将军来作为指挥官负责总体的作战方案,比如选举A将军作为指挥官,如下:

在上述的图解示例中,对于B将军而言不论是A将军还是C将军叛变,其对于A和C将军接收到的方案都无法分辨出谁真谁假,这个时候B将军是无法作出最终作战的决策方案,从侧面说明消息要达到交互的一致性在分布式的集群中只有3个服务节点要是无法做到.

基于此,我们需要将军队多划出一个独立军队,产生一个新的指挥官,而A,B,C作为副官,负责执行提案策略.这个时候基于上述的算法就有以下情况.

从上述可以看出,如果是C将军为叛变将,指挥官以及A和B将军会采取进攻的策略,对于B将军而言,接收到指挥官以及A将军为进攻的策略,接收到C将军为撤退的策略,进攻与撤退以2:1胜出最终的决策,同理对于A将军也一样;而如果是指挥官是叛变的话,那么对于A,B,C三位将军最终通过投票得出的结果是采取撤退的策略,因此不论是哪种结果对于忠诚的将士而言最终采取的行动是一致的.

口头消息通信小结

对于我们分布式互联网而言,一般在企业内部的集群机器而言,由于对外存在防火墙以及安全的网关校验,因此对于企业服务内部都是采取当前的算法策略来解决我们集群服务选举,进程互斥以及分布式事务等问题提供解决方案的思路.对于口信消息的算法,一般用于系统容错故障但不存在恶意攻击的服务节点,即CFT算法,这个场景可能会丢失消息,或者有消息重复,或者是顺序一致性处理等场景,其对应的常用算法有Paxos算法、Raft算法、ZAB协议.

签名消息的解决方案

这个时候我们发现上述的解决方案需要在原有的集群服务中增加一个leader节点作为整个集群具备指挥权的服务节点.那么是否可以考虑不需要进行加服务节点就能够解决服务节点之间的共识问题呢?这个时候就需要运用到我们的签名消息解决方案.

实现签名消息的要求以及含义

• A4: 基于上述无签名消息的要求以及含义基础上,需要满足以下条件:

1.集群服务节点之间的消息通信无法被伪造,任何被伪造的消息都能够被检测出来 2.每一个服务节点都能够核实消息签名的真实身份.

消息签名的算法

算法要求

基于上述A4的要求,如果存在m个不可用的服务节点,那么整个集群的服务节点个数必须是不少于m+2,否则无法得到问题的解决.该算法为空洞(可以考虑反证法推导).

算法的定义

我们定义一个函数fn=choice(V)表示有序的集合中存在签名的消息元素v,如果集合中只有一条消息元素v,那么fn=v.

• 如果集合V中仅包含一个元素v,则choice(V)=v
• 如果集合为空,那么执行默认的“撤退”行为,即choice(V)=RETREAT.

算法描述

在该算法中,指挥权的服务节点向其他服务节点发送一个按照一定规则签名的消息到其他服务节点中,其他服务节点接收到消息之后将其签名添加到有序的签名消息中并进行发送到其他服务节点中,其他服务节点以此类推.如果存在服务节点“叛变”,必须有效地接收签名的消息,并对签名消息生成多份副本,然后再将这些副本进行签名然后发送到其他节点中.最后不论副本是如何得到,其中单条签名的消息要么是被通过副本拷贝要么是与单条签名一致并正确分发过来的消息.

• 指挥权的服务节点对消息进行签名并发送到各个服务节点.
• 对于每一个接收签名消息的服务节点:
  • 如果服务节点从指挥节点接收以v:0的签名消息并且还没有接收到其他签名消息的时候,那么对于当前节点i设置选择提案值为choice(V)=v,并且以消息v:0:i
  • 如果服务节点接收到消息形如v:0:j1...:jk并且v并不在集合V中,那么对于当前的服务节点将会把v添加到集合V中并当k<m的时候将以消息为v:0:j1...:jk:i的形式发送到其他服务节点,否则将以消息为v:0:j1...:jk的形式发送到其他服务节点上.
• 最后对于每一个服务节点i,如果没有接收到更多签名消息的时候,服务节点将会遵循选举从有序的集合V中获取提案v并执行.

消息签名算法分析

基于上述的算法,我们仍然用拜占庭将军为例子进行分析如下:

• 在左侧图中,由A将军发起进攻指令,B和C将军均收到A将军发出的指令,如果C将军为叛军,那么必然会篡改消息并进行签名发送给B将军,B将军识别到C将军发送的消息是伪造的,于是直接丢弃C将军的指令,最后执行进攻指令.
• 如果A将军为叛军,此时分别向B和C发送不同的指令,B和C将军接收到消息并存储在一个有序的集合中,即B存储[进攻, 撤退],C存储[撤退,进攻],根据上述的算法,集合中是有序的,那么对于B和C存储的集合指令也应当是有序且一致的,即均为[进攻,撤退]或者是[撤退,进攻]这样的有序集合,然后按照一定的选举策略(比如选举中间值)执行对应的指令,这样也保证了B和C交互的一致性.

签名消息通信小结

最后关于消息签名的算法,从上面我们可以看到是去中心化的一个分布式系统架构服务,因此对于公网环境下执行事务型操作可以考虑使用消息签名的算法,最大优势在于去中心化.

最后感谢花时间阅读,如果有收获欢迎动一动小手指转发或者好看,谢谢!