分布式共识协议Paxos本质是一次写入寄存器？ - maheshba


在系统中，我们通过抽象来处理复杂性。对于任何系统，都存在三个关键问题：

  • 它实现了什么抽象？
  • 这种抽象的设计空间是什么？
  • 为什么这个抽象有用？

在这篇文章中，我们将回答 Paxos 的前两个问题。
本文档并不打算取代 Paxos 论文。
 
Paxos 实现了一次写入寄存器：
Paxos 是一个实现共识的协议。这意味着它实现了一个称为一次写入寄存器（或 WOR）的逻辑对象。WOR 有一个简单的 API：您可以写入一次；你可以多次阅读它。字面上伪代码如下：
class WOR{
    public:
        //success means some write succeeded;
        //read after a write to see what was written.
        void write(std::string payload);
        //throw an exception if unwritten
        std::string read();
}

WOR 对于并发访问是安全的。它是可线性化的，或者可交换地，是强一致的。换句话说你的实现必须表现得好像你有一个很大的锁（不管它是如何实现的）。
WOR 是一个用于达成共识的 API。共识可以隐藏在许多其他 API 之后，但 WOR 是它的最小 API。
理解共识只是一种对象对系统构建者有一些有用的含义。
  • 只需检查它们的 API，您就可以立即发现其他系统中是否存在共识。例如，具有简单 put/get API 的键值存储不一定实现共识（您不能在顶部实现 WOR）；而有条件的 put/get API 确实实现了共识（您可以在顶部实现 WOR）。
  • 当构建一个需要共识的真实系统时，你可以依赖一些现有系统作为 WOR 的临时实现（例如，一些现有的带有条件 puts 的键值存储）；使整个堆栈运行；然后用共识协议干净地替换它。
  • 您可以在 WOR 实现中出现故障（接下来出现）时，将与分布式系统中的共识相关的复杂性与系统的所有其他复杂性彻底隔离开来。

 
Paxos使用法定仲裁quorums机制实现了一个一次写入寄存器以实现容错：
共识的全部意义在于在出现故障的分布式系统中做有用的事情。通常让人们失望的是确切的故障模型。
这是 Paxos 使用的模型。机器可以任意重启；但它们具有持久存储，并且会恢复。更令人担忧的是，它们可能会因爆炸而失败（丢失它们存储的所有位）。
我们将共识建模为一个逻辑对象：WOR。考虑一个系统，其中客户端正在访问 WOR，而 WOR 又存储在存储服务器集群上。
实现一次写入寄存器（我们称之为WOR-server）的一种简单方法是让单个服务器将值存储在 RAM 中并通过 RPC 公开 WOR API。但这并不持久；如果服务器重新启动，该值将丢失。一个稍微好一点的解决方案是将数据存储在磁盘上，这样它就不会在重新启动时丢失。但是如果服务器爆炸，你就会丢失数据。
因此，如果机器爆炸，WOR-server——单服务器设计——是不耐用的。为了获得对爆炸机器的持久性，我们需要跨服务器复制数据。但是很明显，如果所有的服务器都可以爆炸，就没有办法获得持久性。所以我们需要对爆炸服务器的数量做一个假设。
Paxos 假设只有少数服务器会爆炸；等价地，为了容忍 F 个爆炸的服务器，Paxos 需要 2F+1 个服务器。这直接导致了基于仲裁的协议。为了持久地写入数据，我们只需要将其存储在大多数法定人数的服务器上。我们假设只有少数人会爆炸；所以至少一个未爆炸的服务器将包含数据。
所以我们到达了WOR-quorum：写入 WOR 的客户端可以简单地将数据写入法定服务器（每个服务器都运行单服务器WOR-服务器设计）。从 WOR 读取需要客户端转到法定服务器。这样的解决方案是持久的。
在 Paxos 中，服务器被称为接受者；写入值的客户端称为提议者。
在只有一个客户端不会失败的系统中，我们就完成了。但在实际系统中，我们通常希望多个客户端同时访问 WOR；每个客户端都可以自己重新启动或爆炸。
这将我们带到了 Paxos 协议。
 
Paxos 实现了一个一次写入寄存器，使用法定仲裁quorums机制进行容错和两阶段锁定进行并发控制：
在WOR-quorum 中，当两个以上的客户端同时写入一个仲裁时，我们最终会在不同少数接受者上得到不同的值。防止这种情况的一种方法是首先锁定接受者，然后写入它们（并解锁它们）。
锁定很棘手有两个原因。首先，您可能会遇到死锁；以严格的顺序获取锁以防止死锁会增加延迟。其次，分布式系统中的锁定有一种新的故障模式：客户端在获取锁定后可能会崩溃。
Paxos 通过一种锁窃取形式为这两个问题提供了解决方案。锁有版本号或编号；编号较高的锁可以覆盖编号较低的锁。客户将选择一个唯一的锁号；然后尝试用它锁定法定人数。
如果接受者被解锁，或者用一个较小的数字锁定，则锁获取成功；如果接受者被更高的数字锁定，则失败（在这种情况下，锁定客户端可以使用更高的锁定数字重试）。锁不是建议性的；写入基于锁号，如果锁被盗，则在接受器处将失败。
现在进入了微妙之处：
  • 完成中的写入：回想一下，我们假设少数服务器会爆炸。如果客户端锁定了大多数服务器；无法访问剩余的少数；并且发现一个值已经写在那个多数的单个接受者上，它必须假设这个值也被写在了不可访问的少数并被确认回了一些老客户。因此，唯一的前进道路是新客户端将该值作为自己的值并将其写入可访问的大多数。如果存在多个这样的值，客户端必须选择具有最高关联锁号的值。
  • 活锁Livelock：显然上面的协议可以活锁，如果两个客户端不断互相窃取锁。这个问题在理论上是不可能解决的：FLP 结果（早于 Paxos 协议）表明，对于容错共识，你不能同时拥有活性和安全性。Paxos 中的 Livelock 是 FLP 结果在行动中的真实示例。
  • 不同的锁定/写入仲裁：事实证明，您可以锁定一些多数仲裁并写入另一个多数仲裁；两个阶段的法定人数不必相同。（但是对未锁定接受器的写入必须被解释为先锁定再写入，否则您会遇到此错误）。灵活的 Paxos 进一步指出，如果较低的持久性是可以接受的，则写入仲裁不一定必须是多数。
  • 预锁定：客户端可以在写入值时预锁定仲裁以避免往返。为了提供对锁定的细粒度控制，我们可以显式地向 WOR 公开一个名为 lock() 的额外 API。如果客户端与恰好位于同一组接受器上的多个 WOR 交互，我们可以预先锁定整批 WOR。预锁定涵盖了 MultiPaxos 中的关键优化，我们将在稍后讨论。

所以这是最终的 WOR API：
class WOR{
    public:
        //lock a quorum
        int lock();
        //success means some write succeeded;
        //read after a write to see what was written.
        //throws an exception if you lost the lock.
        void write(std::string payload, int lockId);
        //throw an exception if unwritten
        std::string read();
}

  
作者mahesh是 Facebook 的一名软件工程师；之前是耶鲁大学的副教授，以及 VMware Research 和 Microsoft Research Silicon Valley 的研究员。