高级分布式系统-第6讲分布式系统的容错性--进程的容错

分布式系统的容错原则既适用于硬件，也适用于软件。两者的主要区别在于硬件部件的同类复制相对容易，而软件组件在运行中的同类复制（进程复制）涉及到更为复杂的分布式操作系统的容错机制。

以下是建立进程失效容错机制的一些基本原则：

容忍进程失效的关键是把多个同样的进程组织到一个组中。

进程组的关键特性是当信息发送到组本身时，组中所有的成员都接受它。

进程组是动态的。可以创建组与删除组，一个进程可以加入或离开一个组，一个进程可以是多个组的成员。

平等组和等级组是组的两种常见的结构形式

平等组：组中所有的进程都是平等的，没有指挥，所有的决定都是共同协商产生的。

优点：对称结构，没有单独的失败点；缺点：协商过程比较复杂。

等级组：组中存在等级关系，存在担任全组协调的角色（协调者进程）和承担其他工作的角色（工作者进程）。当外部向组产生一个服务请求时，由协调者决定分发任务给哪个工作者。

优点：只要协调者在运行就可以独自做决定；缺点：协调者失效会导致组崩溃。

组成员的管理

等级组适合集中式管理，由一个组服务器保持所有组及其中成员的信息，并承担组的创建、删除、成员加入/离去等管理功能。

这种方法直接、有效、容易实现，但集中式管理存在单一失效导致组崩溃的风险。

平等组适合采用分布式管理方法，通过可靠的多播及相互交换信息实现成员的管理。

分布式管理的机制比较复杂，通信开销大。如离开一个组需要向所有成员发送一个消息，同时还要要求其他成员关注该离开成员的通信响应，以及离开与加入的消息同步问题等。

进程复制与故障掩盖

通过复制进程将它们组织在一个组中，可以构建一个容错的组取代一个脆弱的进程。

容错的等级组中，主进程的复制通常以主进程后备协议的形式出现。这种情况下，如果主进程崩溃，后备进程执行一些选举算法来选择一个新的主进程。（双模热备）

容错的平等组中，成员都是相同的复制进程，通常采用表决机制实现容错。如果组能够经受k个成员进程的故障还能完成规定功能，那么就称为k容错。

如果这些成员进程是故障静默的，那么具有k+1个成员进程就能够提供k容错。如果成员进程发生的是同步的确定性故障，那么至少需要具有2k+1个成员进程才能够获得k容错。（如果k=1，就成为三模冗余表决系统。）

进程间的协议

分布式协议算法的一般目的是使所有的非故障进程就一些问题达成一致，而且在有限的步骤内就达成一致。

两军问题

两军问题：在假定通信不可靠的情况下，两个运行良好的进程之间即使只就1位信息达成协议也是非常困难的。

问题描述：两只分处两地的蓝军必须协商同时向红军发起进攻才能获得胜利，但它们的通信方式只能派通信兵在两只蓝军之间传送信息。经过证明，由于通信兵在传送信息的过程中存在被红军俘获而不能实现消息传送任务的风险，两只蓝军最终不可能达成一致的进攻协议。

拜占庭将军问题

拜占庭将军问题：在假定通信可靠、进程运行存在故障的情况下，在存在m个故障进程的系统中，只有存在2m+1个正确工作的进程才能达成协议。即如果存在m个故障进程的系统，那么所有的进程总数必须3m+1，或者说要有2m+1个正确工作。

如何理解？

参考文章：拜占庭将军问题_拜占庭问题-CSDN博客

拜占庭将军问题概述

拜占庭帝国在攻击敌方城堡时，在地方城堡外驻扎了多个军队，每个军队都有各自的将军指挥，将军们只能通过信使进行沟通。在观察敌情之后，他们必须制定一个共同的计划，如进攻或者撤退，只有当半数以上的军队都发起进攻才能取得胜利。然而这其中的一些将军可能是叛徒，就会阻止将军们达成一致的行动计划；另外，传递消息的信使也可能是叛徒，他们可以进行篡改和伪造消息或者不进行消息的传递。

三将军问题

首先把问题简化一下，假设只有三个拜占庭将军，分别为A、B、C，他们要讨论的只有一件事情：明天是进攻还是撤退。为此，将军们需要依据“少数服从多数”原则投票表决，只要有两个人意见达成一致就可以了。

举例来说，A和B投进攻，C投撤退：

那么A的信使传递给B和C的消息都是进攻；

B的信使传递给A和C的消息都是进攻；

而C的信使传给A和B的消息都是撤退。

如此一来，三个将军就知道进攻方和撤退方的具体比例，因此可以达成行动的一致。

但是如果三个将军出现一个叛徒，就会导致将军间的一致的达成遭到破坏。当其中A和B做出相反的决策时，第三个将军的决策就格外重要了，当他向两个将军发出不同的决策消息，就会导致两个将军做出不同的决策，从而导致了结果的不一致。

如何揪出三将军中的叛徒？

先说结论：我们无法抓到这个叛徒。

为何呢？举例来说明：

还是上面的例子，假设A与B是忠诚的将军，C是叛徒将军。忠诚的将军经历了上次战役的失败，就已经发觉他们中出现了叛徒，但是并不知道具体是谁。依旧是上面投票的例子，A投进攻，B投撤退，C传递给A和B两种不同的消息。

现在，我们从忠诚将军A的视角来看一下，他是如何做决策的。

A现在知道另外两人中可能有一个是叛徒，他收到了B的撤退消息和C的进攻消息，他应该如何分辨呢？于是，A打算问一下B，“我从C那儿收到的是进攻，你从C那儿收到的是什么？”因为B是忠诚的将军，他不会伪造信息，B会告诉A收到的是撤退。C发送了两条不同的消息，A现在也发现了这个问题，但是A现在就可以判断C是叛徒了么？可悲的事情发生了，尽管忠诚的B说了实话，但是A反而对他产生了怀疑。因为从A的视角来看，B和C的说法不一致，他无法判断：

到底是第一次发送了两条不同消息的C是叛徒呢?

还是明明C初次告知了B的是进攻，B却和A说C告知的是撤退，B是叛徒呢?

在三个将军中最多有一个叛徒的前提下，A现在唯一能明确的是，他们中间确实出了一个叛徒，但却无法信赖两个人中的任何一个。同样的情况，也出现在B身上，两个忠诚的将军彼此间产生了隔阂。而可以任意进行信息造假的叛徒C，此时只需要再次进行消息伪造：和A说“B告知我的消息是进攻”，和B说“A告知我的消息是撤退”，如此一来，就可以进一步把信息搞混，从而隐藏了自己是叛徒的真相。

综上：在拜占庭三将军问题中，出现一个叛徒的情况，在叛徒可以任意伪造消息的情况下，他始终无法被发现。更通用的：如果存在m个叛徒将军，当将军数量少于等于3m时，叛徒就无法被发现，整个系统的一致性也无法达成。