两军问题


想象一下山谷中有一座城市。在山谷的两边,各有一支军队。左边的山上站着爱丽丝将军和她的军队;右边的山上是鲍勃将军和他的军队。爱丽丝和鲍勃都想占领这座城市,但双方都没有足够的军队单独行动。因此,爱丽丝和鲍勃必须同时攻打这座城市,这样才有机会拿下这座城市。
1.png

然而,问题来了,爱丽丝和鲍勃只能经过山谷发送信息来交流。负责传递信息的信使有可能被城里的军队俘虏。同时,爱丽丝和鲍勃只有在确信对方会同时进攻的情况下才会真的发起进攻,那么,爱丽丝和鲍勃该如何协调他们的进攻呢?

假设爱丽丝决定采取主动行动。她给鲍勃发送了一条信息,内容如下:

“让我们在5月17日发起进攻。让信使把你的回复发过来。——爱丽丝”
2.png

如果信使没能通过,爱丽丝就不会进攻,显然鲍勃也不会。如果消息到达鲍勃,他将发送他的回复:

“好吧,就这么办。就在5月17日!——鲍勃。”
3.png

现在是有趣的部分来了,鲍勃的回复是否能收到并不重要。不管怎样,鲍勃都不会攻击。记住,因为鲍勃只有在确信爱丽丝也会攻击的情况下才会进攻。鲍勃知道爱丽丝只有在得到他的回复后才会攻击,但是鲍勃不知道他的回复是否送到了爱丽丝那里。如果没有,她就不会进攻,如果他不带她进攻,他的军队就会全军覆没。因为鲍勃不知道他的信息是否收到了,所以他就这么等着,什么也不会发生。

这种情况,我们能做点什么吗?来我们试着改一下策略,就是,让鲍勃要求爱丽丝发送确认信,表示她收到了他的回复。因此,发了这封信:

“好吧,就这么办。是5月17日!同时,请你再发送另一封信来确保你收到了这封信。——鲍勃。”

现在爱丽丝发送消息,鲍勃发送他的回复,爱丽丝准备发送她收到了他的回复的确认消息。但她意识到,她无法知道他是否会得到确认。如果他拿不到,他就不会进攻,她的军队就会被打败。所以她决定发出这样的信息:

“我明白你的回答。请再发送一封信使来确认这个确认。——爱丽丝”

总结一下,现在我们有了一条消息、一个回复、一个回复的确认和一个确认的确认。
4.png

5.png

假设鲍勃收到确认信息并准备发送确认信息的确认信息。但是等等!他意识到他没有办法知道爱丽丝是否会得到确认。如果她没有得到它,她就不会进攻,所以鲍勃决定发送:

“我确认你的确认。请再发送一封信来确认这个确认。——鲍勃。”

明白这是怎么回事了吗?不管我们添加多少层级的确认,最后一个发送信息的人永远不可能知道那个信息是否通过了。因此,最后一个送信的人永远不会相信对方会发起进攻,所以也永远不会进攻。

放松的两位将军

上面这个问题叫做“两位将军的问题”,这个问题是无解的。那,是否存在较少的约束规则,这样问题是不是就可解了?如果答案是否定的,本文就没法继续下去了;是的,确实存在的。如果我们取消双方将军必须百分百确信对方会进攻的条件,意思就是如果我们改变一些其他的点,我们就可以在大多数情况下解决这个问题。虽然我们仍然无法完全保证两名将军都会进攻,但至少我们可以相当肯定他们会这么做。

在这个问题的新版本中,爱丽丝是领导。她决定什么时候攻击,一旦她决定了什么时候攻击,无论如何她都会攻击。如果鲍勃得到一条消息说他应该在特定的时间进行进攻,他就必须这样做。我们继续来看这个例子。

爱丽丝决定进攻。她知道她不可能100%肯定鲍勃也会攻击她,但她笃定鲍勃99%会。爱丽丝知道信使穿过山谷需要多长时间,她也知道信使被抓住的可能性。
6.png

知道了这两件事,她计算出多少个信使能使信息以99%的概率通过并送达。然后,她计算发送这么多信使需要多长时间,从而来设定足够的攻击时间来满足这一点。
接下来爱丽丝发送了一个带有以下消息的信使:

“下周四上午9点袭击。请派信使回来,确认你收到了这条消息。”

然后,爱丽丝等待足够的时间,让信使到达鲍勃,并让鲍勃的确认信使到达她这里。如果信使到达,爱丽丝停止发送信使,爱丽丝和鲍勃都在等待,直到下周四上午9点他们协同攻击。

如果确认消息没有到达,爱丽丝发送另一个具有相同消息的信使:

“下周四上午9点袭击。请派信使回来,确认您收到了这条消息。”

她会不断重复这个过程,直到收到回复,或者是在下周四上午9点,在这个时间,不管消息是否通过,她都会攻击。因为爱丽丝选择了未来足够充裕的时间(基于消息的失败率),有99%的机会至少有一个信使在攻击时间之前到达鲍勃。

我们知道下周四上午九点两位将军都有99%的可能发动袭击。我们能增加这个确定数字吗?是的,我们可以。爱丽丝可以通过将攻击时间设置得越来越远而接近100%。然而,如果不将攻击时间设置为无限远的未来,她就永远无法达到100%(这意味着它永远不会发生,所以这是没有用的)。

这里还有一点需要指出。如果我们不在乎攻击是否同时发生,爱丽丝可以发送一条信息:

“现在就发动进攻。发送信使来确认你收到了这条消息。”
7.png

在这种情况下,爱丽丝可以不断地发送消息,直到她收到确认,并等待确认,然后攻击。

这种方法确实保证了双方最终都会攻击,但关键是,他们不会同时攻击。爱丽丝攻击的时间会比鲍勃晚,至少是信使从鲍勃到达爱丽丝那么久,而且,到底晚多久这取决于有多少信使被捕获。

一个更实际的例子

让我们看一个更实际的例子。假设你正在设计一个系统,该系统需要通过第三方服务预订航班,并向用户发送电子邮件说明航班已经预订。

起初,这听起来是个简单的问题。给机票预订系统发送一个网络调用。如果返回OK状态,则发送邮件。如果它返回一个错误状态,就不发送电子邮件(或发送一封说稍后再试的邮件)。
8.png

但请记住,网络调用是不可靠的,所以实际上这就是——放松的两位将军的问题。如果网络调用返回一个OK或一个错误状态,那么我们就没问题了,但是网络调用也可能因为没有收到响应而超时(就像捕获了一个信使一样)。这种情况下我们该怎么做?

就像在放松的两位将军的问题中一样,我们可以继续重试这些消息,直到得到响应。只有得到回应,我们才能决定下一步做什么。如果响应是好的,我们发送电子邮件。如果响应是一个错误,我们就不发送。

你觉得这种方法有什么问题吗?如果网络出了问题,我们没有得到响应怎么办?我们只是不断地重试,潜在地阻塞资源,直到有人注意到问题并手动终止任务吗?

我们可以使用原来的两将军问题的部分解决方案来解决这个问题。我们会添加一个计时器。具体来说,我们可以向重试过程添加超时设定。第一次发送消息预订航班时,我们将启动计时器。然后,我们将不断地重新尝试消息(只要我们没有得到响应),直到计时器计数为零。一旦计时器完成,我们将停止发送消息并采取行动。
9.png

该定时器的长度相当于在给鲍勃的消息中声明攻击时间。如果我们在周三上午9点开始发送消息,而爱丽丝决定在周四上午9点发起攻击,我们有一个24小时的超时定时器。就像设置攻击时间一样,我们可以通过增加超时的长度来增加消息通过的机会。然而,我们必须权衡不让系统过多占用资源来平衡这一点。

我们知道在暂停之后我们会采取行动,但我们还没有说行动是什么。由于没有得到回复,我们不知道航班是否预定了。我们可以发送一封电子邮件说它已经被预订,或者发送一封电子邮件说它可能已经被预订,或者什么也不发送(并记录一个超时错误)。最好的决定是视情况而定,但在我们的情况下,我们会选择发送一封电子邮件,说航班可能已经预订了。用户可以继续下一步了。
10.png

为了让我们的解决方案起作用,我们必须处理另一个复杂的问题,这是由两位将军问题引发的直接后果——在一个不可靠的网络上,信息传递是不可能的。我们可以发送一条消息一次,并希望它到达(但它可能不会),或者我们可以发送一条消息多次。在这种情况下,它可能会到达不止一次(可能很多次)。

假设一个信使在去找鲍勃的路上迷路了。然后另一个信使被派遣并直接到达目的地。在第二个信使到达之后,第一个信使设法找到了去鲍勃那里的路。同样的事情也可能发生在计算机网络上。消息非但不会丢失,反而会在传递过程中卡在缓冲区中。

在我们的机票预订系统中,这可能是一个大问题。如果到达多个消息要求预订一个航班,系统可能会预订多个航班。要解决这个问题,预定航班请求必须是幂等的。等幂的意思是,如果一个请求被多次发出,那么该请求的效果只能出现一次。

有几种方法可以使预定航班请求幂等。一种方法是在请求中包含一个唯一的ID。只要我们的系统在每次重试时发送相同的ID,预定系统就可以存储该ID,并使它忽略它收到的第一个消息以外的所有消息。

添加第二个分布式操作

到目前为止,我们似乎已经解决了所有的问题。然而,如果我们添加第二个分布式操作,我们的系统就会崩溃。如果我们希望我们的系统也能处理酒店预订,会发生什么?新的要求是我们应该一起订机票和酒店。也就是说,只有在航班预订成功的情况下,我们才能预定酒店,或者酒店预订成功的情况下,我们才能预定航班。在我们预订了他们两个之后,我们会发送一封更新状态的电子邮件。

即使忽略超时,都要预订或都不预订的需求也会增加复杂性。我们可以用几种不同的方法来处理这种复杂性,但最直接的方法是确保我们的系统能够处理撤销任意一个操作。这种方法被称为分布式SAGA。

我们的航班和酒店预订系统的分布式SAGA是这样的(忽略超时和丢失的消息):首先,我们发送一条消息来预订航班。如果得到错误响应,则中止整个过程。如果航班预订系统返回成功,则发送一条消息预订酒店。如果成功了,我们就完成了,我们可以发送成功的电子邮件。

但是,如果酒店系统返回一个错误,我们必须通过调用航班系统来撤销预订的航班,并发送一条消息告诉它取消我们刚刚预订的航班。这就是所谓的回滚SAGA。在回滚SAGA之后,我们可以发送适当的消息或记录错误。

下面是伪代码:
11.png

在实际实现中,我们实际上不能忽略丢失的消息。在我们的故事中,SAGA如何处理这种可能性?每个分布式操作(预订航班和预订酒店)必须有相应的补偿操作(取消航班预订和取消酒店预订)。我们可以在调用原始操作时使用补偿操作来处理丢失的消息。例如:

我们开启SAGA,并发送预订机票的信息。如果预定系统网络超时,我们可以回滚SAGA,而不是重新尝试。同时,我们使用与原预订航班请求的ID来一起调用航班的取消。

处理超时和消息丢失

你可能已经注意到一个问题。我们不知道预订航班的请求是否通过了。如果没有,我们仍然发送取消航班预订请求么?同样,预订航班请求必须是幂等的,预订航班和取消航班预订的组合必须是可交换的。机票预订系统接收他们的顺序应该是无关紧要的。

如果取消航班预订消息首先到达,那么航班预订系统必须存储请求ID,并随后阻止带有该ID的任何预订航班请求。如果取消航班预订消息在预订航班消息之后到达,那么航班预订系统必须撤消原来的操作。

我们已经通过将问题转移到补偿操作来处理航班预订操作的丢失消息,但是如果补偿操作请求丢失了会发生什么呢?

补偿行为一定不能失败。它们永远不会返回错误代码。这意味着它们失败的唯一方式是超时。因此,我们可以继续重试补偿操作,直到它成功(在实践中,我们可能希望这里有一个超时来放弃,并最终抛出报警,某些地方出了问题)。

如果预订机票成功了,我们就去预订酒店。如果失败,则回滚上一步。如果超时,我们通过调用取消酒店预订来回滚当前步骤,然后回滚上一个步骤,取消SAGA并退出。如果一切顺利,我们继续发送电子邮件。

在伪代码中,我们最后的SAGA是这样的:
12.png

生产系统中的注意事项

对于生产系统,还有一些值得注意的地方。我们已经处理了远程系统的故障,但还没有处理本地系统的故障。我们还需要存储我们在当前事件中的位置节点,以便在系统中途崩溃时能够及时恢复。

此外,大多数关于分布式SAGA的文档都将像我刚才做的那样会提到交换律,但交换律还不够强,不足以描述需要什么。

让我们以SAGA中的一个叫做Increment的动作和它的补偿动作叫做Decrement为例。Increment使数字增加1,Decrement使数字减少1。这些动作合在一起是可交换的。从计数器的0开始,Increment然后Decrement=Decrement然后Increment=0。
0+1-1=0-1+1=0

不管顺序如何,最终的结果都是一样的。但在SAGA中的补偿动作也必须在补偿动作信息到达目的地时才能发挥作用。

也就是说,从0开始,递增然后递减=递减然后递增=递减=0。

我不是说动作和它的补偿动作必须是可交换的,而是说补偿动作必须支配动作。Increment和Decrement也必须都是幂等的,因此无论到达多少条消息(具有相同的ID),只要到达了一个Decrement,最终的结果必须与SAGA开始之前相同。

另一个从0开始的例子:
Increment->Decrement->Increment=0=Decrement->Increment->Decrement

这些属性,对于补偿操作来说Decrement并不是一个好名字。最好叫它“补偿增量(Compensation Increment)”。

实现这个的一种方法是让Compensation Increment与Increment共享它的ID。当服务器处理Compensate Increment时,它将检查是否已经处理了任何具有该ID的Increment消息。如果是,服务器将减少该值以进行补偿。如果不是,则保持值不变。然后,在前面的两种情况下,它都会保存ID,以便将来任何带有该ID的消息都将被忽略。

有些SAGA的文档中还将分布式SAGA中的每个步骤称为事务,但我在这里将它们称为操作,以避免与其他并发控制方法混淆。

关于作者

Seth Archer Brown目前正在写一本名为《计算机网络从零开始》的免费书籍。如果你喜欢本文,那么你会在这边书里也能找到类似的内容。

《计算机网络从零开始》是一场关于庞大计算机网络——互联网内部工作原理的旅行。它完全从头开始(假设完全没有网络知识),使用一个示例系统,该系统允许用户使用弹珠和塑料管(而不是电子信号和线缆)来回发送消息。然后它逐渐发展成类似于60年代早期的最先进的计算机网络。

这本书还在进行中,但在书的最后,它也会概述互联网的现状,以及即将出现的趋势展望。

原文链接:The Two Generals Problem(翻译:伊海峰)

0 个评论

要回复文章请先登录注册