构建鲁棒分布式系统的新算法

EPFL研究人员开发了一种新的分布式算法，首次解决了影响大多数当前部署的共识协议的关键性能和可靠性问题之一。这项工作已经发表在第29届操作系统原理研讨会论文集上。

一致性问题是分布式系统的基本问题之一。它允许一组机器维护数据的多个副本并一致地更新它们，即使部分机器可能出现故障。

以三个服务器为例，它们需要存储三个数据副本，并跟踪信息的任何更新，以便所有三个服务器保持一致。如果一台服务器发生故障，其余两台服务器必须保持数据一致，并允许更新正常进行，就像没有发生故障一样。

当前最先进的共识协议依赖于一个计算机节点在任何给定时间被指定为leader，持续监督和处理任何数据更新。如果leader失败了，另一个节点会醒来并接管，但这是一个挑战。

EPFL计算机与通信科学学院(IC)去中心化与分布式系统实验室(DEDIS)负责人Bryan Ford教授解释说:“如果leader失败或网络不好，经典共识协议的问题是，如何决定超时应该有多大或多小，这是一个非常棘手的问题。

“如果你把目标设定得太大，那么当一个leader失败时，你可能要等很长时间，整个系统也就完蛋了。另一方面，要考虑是否将超时设置得太短——这才是真正的灾难发生的地方。”

“假设旧的leader没有失败，假设网络比你想象的要慢一些，下一个leader来试图接管，但所有现有协议的工作方式，新leader的行动将取消旧leader的行动，因此它不能再完成它所做的工作，所有的工作都白费了。这些问题可能会导致严重的可靠性问题，如果出现故意拒绝服务攻击，这些基于领导者的协议可能会完全失败。”

为了克服这些挑战，DEDIS的研究人员一直在研究一种很少使用的共识算法，即异步共识协议。与当前基于leader的协议不同，它们的异步同类协议不容易受到leader失败和拒绝服务攻击的影响。但是，在正常条件下，优先异步协议的效率要低得多，这是它们几乎从未部署的原因之一。

Ford说，他们的QuePaxa协议第一次改变了这种动态。“我们提出了一个双赢的办法。QuePaxa的新颖和独特之处在于，它是一种异步共识协议，最终实现了与在正常网络条件下广泛部署的基于leader的协议相当的效率。在正常情况下，QuePaxa在网络带宽方面同样快速、高效、低延迟和低成本。”

新算法的设计方式是，每次通常由一名leader领导取得进展的任务，但第二名leader可以在同一轮中加入并提供帮助，而不会干扰第一个leader。第三个leader甚至可以加入进来，帮助另外两个人更快地完成工作。会有一些冗余的努力，但非leader不会破坏性地干预。短暂的延迟不会像目前的协议那样导致leader取消彼此的工作。

QuePaxa的另一个优点是，它在恶劣条件下也非常强大，如网络嘈杂、通信延迟高、网络延迟变化不可预测或蓄意拒绝服务攻击。

“在这种情况下，现有的共识协议将彻底失效。QuePaxa将继续下去；它将更加强大，”他继续说道。“在任何对性能、可靠性或易受此类攻击性有重大担忧的地方，出于稳健性的原因，我认为这将改变游戏规则，这应该是新的标准共识协议。”

DEDIS团队已经构建了QuePaxa的开源原型，该原型可在GitHub存储库中获得。新协议已经在SOSP进行了工件评估审查，同行评审人员已经测试了其能力。