原创

分布式基础(三)——分布式理论之分布式一致性:共识问题

前两章,我介绍完了分布式系统的两个重要基本理论——CAP理论BASE理论,本章我们就要来看看分布式理论中最核心的问题——共识问题。

共识问题是分布式领域最复杂的一个容错模型,只有搞懂它,你才能掌握常用的各种共识算法,才能在设计分布式系统时,根据业务场景的特点选择适合的算法。

那么,什么是共识问题呢?

简单的讲,共识问题就是分布式系统需要解决的一个核心问题:在一个可能发生机器宕机、网络异常、数据篡改的环境下,如何让分布式系统中的所有节点快速准确的对某个数据值达成一致,且不会破坏整个系统的一致性

Leslie Lamport曾在论文《 The Byzantine Generals Problem》中抽象出来一个著名的例子—— 拜占庭将军问题,用来通俗的描述共识问题(然并卵,并没有描述清楚),并给出了解决该问题的两类方案。

事实上,解决共识问题的算法一共可以分为两大类:拜占庭容错算法(Byzantine Fault Tolerance,BFT)故障容错算法(Crash Fault Tolerance,CFT)

在存在恶意节点行为的场景中(比如区块链技术),必须使用拜占庭容错算法(Byzantine Fault Tolerance,BFT)。而在分布式系统中,最常用的是故障容错算法(Crash Fault Tolerance,CFT)。CFT 解决的是分布式系统中存在故障,但不存在恶意节点的场景下的共识问题,也就是说,这个场景可能会丢失消息,或者有消息重复,但不存在错误消息,或者伪造消息的情况。

本章,我就先来讲讲Leslie Lamport所描述的拜占庭将军问题,后续章节,我会详细讲解解决共识问题的两类算法。

一、拜占庭将军问题

拜占廷帝国(Byzantine Empire),也就是东罗马帝国,是欧洲历史上最悠久的国家。东罗马帝国国土辽阔,它的都城便是大名鼎鼎的君士坦丁堡。公元1453年,奥斯曼帝国苏丹——穆罕默德二世,率军攻克君士坦丁堡,标志着拜占廷帝国的正式灭亡,之后君士坦丁堡被改为名为“伊斯坦布尔”,也就是如今土耳其的一个核心城市。

由于拜占廷帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信使传递消息。在打仗的时候,所有将军必须达成一致的共识,才能更好地赢得胜利。但是,在军队内有可能存有叛徒暗通敌国,扰乱将军们的决定,也有可能信使被敌人截杀并替换。

这时候,在已知有成员不可靠的情况下,要战胜敌国,必须半数以上的将军达成一致,那么其余的忠诚将军如何达成一致的“攻打”或“撤退”协议呢?



1.1 二忠一叛

为了帮助大家理解,我对该问题进行简化:假设我们一共就只有三个将军,决策是否要攻打某座城市。 将军们按照“少数服从多数”的原则投票表决,只要半数以上(两个人)的意见一致就可以了。

在没有叛徒和间谍干扰的情况下非常简单,比如将军A和B决定进攻,C决定撤退:



那么最终的结果如下,所有将军都会同时进攻:

  • A看到的是,撤退:进攻 =1:2;
  • B看到的是,撤退:进攻 =1:2;
  • C看到的是,撤退:进攻 =1:2。

可是,问题来了: 一旦有人在暗通敌国,就会出现作战计划不一致的情况。比如将军B被敌国收买了,他向将军A发送了“进攻”的消息,向将军C发送了“撤退”的消息:



那么最终的结果如下

  • A看到的是,撤退:进攻 =1:2;
  • C看到的是,撤退:进攻 =2:1。

按照少数服务多数原则,只有A会发起进攻,相当于A被叛将B出卖了,A必然战败。 叛将B通过发送误导信息,非常轻松地干扰了A和C的作战计划,导致这两位忠诚将军被敌国逐一击败。这就是所谓的二忠一叛难题。

针对上述问题,Leslie Lamport在论文中给出了两种解决方案:口信消息解决方案(A solution with oral message)签名消息解决方案(A solution with signed message)

二、口信消息解决方案

口信消息解决方案,新增了一位将军参与作战计划讨论,并执行作战指令。这样,原来3 位将军的作战讨论就变为了 4 位将军的作战讨论,这能够增加讨论中忠诚将军的数量。 然后,4位将军还约定:如果没有收到命令,就执行预设的默认命令,比如“撤退”。

最后,最关键的是整个决策过程变成了两轮:

第一轮

  • 先发送作战信息的将军作为指挥官Leader,其他的将军作为副官。
  • 指挥官将他的作战信息发送给每位副官。
  • 每位副官,将从指挥官处收到的作战信息作为自己的作战指令;如果没有收到作战信息,将把默认命令(比如“撤退”)作为作战指令。

第二轮

  • 除了第一轮的指挥官外,剩余的 3 位将军将分别作为指挥官,向另外 2 位将军发送作战信息。
  • 然后这 3 位将军按照“少数服从多数”,执行收到的作战指令。

为了帮助大家直观理解整个解决方案,我来演示一下作战信息的协商过程。而且,我会分别以忠诚将军和叛徒将军作为指挥官Leader为例来演示, 这样可以完整地演示叛徒将军对作战计划干扰破坏的可能性。

忠诚将军作为Leader

我们假设新增了一位将军M,在第一轮协商中,M作为Leader指挥官率先发起的作战指令是“进攻”:



在第二轮作战信息协商中,A、B、C分别作为指挥官,向另外 2 位发送作战信息“进攻”,因为B已经叛变了,所以,为了干扰作战计划,他就对着干,发送“撤退”作战指令:



最终,各位将军收到的作战信息如下:

  • A看到的是,撤退:进攻 =1:2;
  • C看到的是,撤退:进攻 =1:2;

那么按照原则,A、C、M一起执行作战指令“进攻”,实现了作战计划的一致性,保证了作战的胜利。

叛徒将军作为Leader

那么,如果叛将B先作为Leader发送作战信息,干扰作战计划,结果会有所不同吗?我们来具体看一看。

在第一轮作战信息协商中,B向M发送作战指令“进攻”,向A、C发送作战指令“撤退”:



然后,在第二轮作战信息协商中,A、C、M分别作为指挥官,向另外两位发送作战信息:



最终,各位将军收到的作战信息如下:

  • A看到的是,撤退:进攻 =2:1;
  • C看到的是,撤退:进攻 =2:1;
  • M看到的是,撤退:进攻 =2:1;

那么按照原则,A、C、M一起执行作战指令“撤退”, 实现了作战计划的一致性。也就是说,无论叛将B如何捣乱,A、C、M都执行一致的作战计划,保证作战的胜利 。


这个解决方案,Leslie Lamport在论文中给出了一个定理:如果叛将人数为 m,则将军总人数不能少于 3m + 1 ,此时需要进行m+1轮协商,那么拜占庭将军问题就可以解决

这个算法的前提是:叛将人数 m 是已知的,m 决定了递归循环的次数(也就是说,叛将数 m 决定了将军们要进行多少轮作战信息协商),即 m+1 轮(所以在上面的示例中,存在1个叛将的情况下,需要进行两轮协商)。

在二忠一叛的问题中,由于存在 1 位叛将,所有必须增加 1 位将军,转换为 4 位将军协商共识,这样才能实现忠诚将军的一致性作战计划。

三、签名消息解决方案

那么有没有办法在不增加将军人数的前提下,直接解决二忠一叛的难题呢? 有的,这就是签名消息解决方案。

所谓签名消息,就是说:

  • 忠诚将军发送的消息指令无法伪造,而且对他消息的内容进行任何更改都会被发现;
  • 任何人都能验证将军发送的消息真伪。

该方案中,率先发送作战信息的将军依然作为指挥官Leader,其他的将军作为副官,必须接受并广播Leader的指令。

举个例子,如果忠诚将军A先发起“进攻”指令,那么他就作为指挥官Leader, 一旦叛将B修改或伪造收到的作战信息,那么C在接收到B的作战信息时,会发现A的作战信息被修改,就认为B已叛变,此时将忽略来自B的作战信息,最终执行A发送的作战信息:



如果叛将B率先发送误导的作战信息,那么,A和C按照一定规则(比如取中间的指令)在排序后的所有已接收到的指令中(比如撤退、进攻)中选取一个指令,进行执行,最终执行一致的作战计划:



通过签名机制约束叛将的叛变行为,任何叛变行为都会被发现,也就会实现无论有多少忠诚的将军和多少叛将,忠诚的将军们总能达成一致的作战计划。

四、总结

拜占庭将军问题其实是对计算机世界中的分布式场景进行了模拟:

  • 忠诚的将军,你可以理解为正常运行的计算机节点 ;
  • 叛变的将军,你可以理解为出现故障并会发送误导信息的计算机节点;
  • 信使被杀,可以理解为通讯故障、信息丢失;
  • 信使被间谍替换,可以理解为通讯被中间人攻击,攻击者在恶意伪造信息和劫持通讯。

拜占庭将军问题描述的是最困难的,也是最复杂的一种分布式故障场景:除了存在故障行为,还存在恶意行为的一个场景。

我们应该根据实际的系统场景选择合适的算法,如果能确定该环境中各节点是可信赖的,不存在篡改消息或者伪造消息等恶意行为(例如 DevOps 环境中的分布式路由寻址系统),推荐使用非拜占庭容错算法;反之,推荐使用拜占庭容错算法。

正文到此结束
本文目录