《云计算技术系列丛书 云原生分布式存储基石： etcd深入解析》—1.2.4拜占庭将军问题

1.2.4　拜占庭将军问题

       拜占庭将军问题（The Byzantine Generals Problem或Byzantine Failure）是一个共识问题。Byzantine Failure这个概念最早是由Leslie Lamport于1980年发表的“Reaching agreement in the presence of faults”论文中提出的。

       拜占庭位于如今土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国幅员辽阔，出于防御的原因，每个军队都相隔甚远，将军与将军之间只能靠信差来传递消息。发生战争时，拜占庭军队内所有将军必需达成共识，决定是否攻击敌人。但是军队内可能存在叛徒和敌军的间谍扰乱将军们的决定，因此在进行共识交流时，结果可能并不能真正代表大多数人的意见。这时，在已知有成员不可靠的情况下，其余忠诚的将军如何排除叛徒或间谍的影响来达成一致的决定，就是著名的拜占庭将军问题[4]。

       拜占庭将军问题是对现实世界的模型化。由于硬件错误、网络拥塞、连接断开或遭到恶意攻击等原因，计算机和网络可能会出现不可预料的行为。拜占庭错误（Byzantine Failure）在计算机科学领域特指分布式系统中的某些恶意节点扰乱系统的正常运行，包括选择性不传递消息，选择性伪造消息等。很显然，拜占庭错误是一个overly pessimistic模型（最悲观、最强的错误模型），因为这种错误在实际环境里很罕见。那么为什么还要研究这个模型呢？因为如果某个一致性协议能够保证系统在出现N个拜占庭错误时，依旧可以做出一致性决定，那么这个协议也就能够处理系统出现N个其他任意类型的错误。

       反之，进程失败错误（fail-stop Failure，如同宕机）则是一个overly optimistic模型（最乐观、最弱的错误模型）。这个模型假设当某个节点出错时，这个节点会停止运行，并且其他所有节点都知道这个节点发生了错误。提出这个错误模型的意义在于，如果某个一致性协议在系统出现N个进程失败错误时都无法保证做出一致性决定，那么这个协议也就无法处理系统出现N个其他任意类型的错误。

       Fred Schneider在前面提到的那篇论文中指出了这样一个基本假设：一个RSM系统要容忍N个拜占庭错误，至少需要2N+1个复制节点。如果只是把错误的类型缩小到进程失败，则至少需要N+1个复制节点才能容错。

       综上所述，对于一个通用的、具有复制状态机语义的分布式系统，如果要做到N个节点的容错，理论上最少需要2N+1个复制节点。这也是典型的一致性协议都要求半数以上（N/2+1）的服务器可用才能做出一致性决定的原因。例如，在一个5节点的服务器集群中要求至少其中3个可用；如果小于3个可用，则会无法保证返回一致的结果。

       但是不是只要满足上文提到的2N+1个要求就能保证万无一失了呢？很不幸，答案是否定的。