-1

我有几个关于 multi-paxos 的问题

  1. 每个实例都有自己的提案编号和接受的选票和接受的值吗？还是所有实例共享同一个提案号，一个完成后，另一个开始？

  2. 如果所有实例共享相同的提案编号，考虑以下情况，服务器 A 发送提案，并且接受者返回接受的 instanceId，可能大于或小于提案的实例 ID，那么提案将做什么？使用该 instanceId 及其接受阶段的值？然后增加它自己的instanceId，等待下一轮，然后用它自己的值重新提案？如果是，那么之前接受的值什么时候被删除，因为如果没有被删除，接受者将再次返回这个intanceId和值，那么它似乎是一个循环

4

1 回答 1

2

Multi-Paxos 有一个模糊的描述，因此两个人可能会基于它构建两个不同的系统，在一个系统的上下文中，答案是“否”，而在另一个系统的上下文中，答案是“是”。

方法#1 - “不”

Mindset：Paxos 是一个用于构建一次写入寄存器的两阶段协议。Multi-Paxos 是一种如何在它们之上创建日志的技术。

构建日志的一种可能方法是

  1. 创建一个完全独立的一次性写入寄存器数组，并使用初始值初始化第一个寄存器。

  2. 根据新记录，我们应该：

    A) 猜测X空寄存器的索引 ( ) 并尝试在此处写入虚拟记录（如果已使用，则选择具有更高索引的寄存器并重试）。

    B）开始将虚拟记录写入每个小于X索引的寄存器，直到我们找到一个填充了非虚拟记录的寄存器。

    C）根据它计算一个新记录（例如，一个记录可能有一个序数，我们可以用它来计算新记录的序数；由于一些寄存器是用虚拟记录填充的，所以序数不等于索引）并将其写入X+1寄存器。如果发生冲突，我们应该从步骤 重新启动程序A)。

  3. 要读取日志，我们应该从第一条记录开始写入虚拟值，并且在每次冲突时，我们应该增加索引并重试，直到写入成功，这表明已到达日志的末尾。

当然，这种方法有很多开销，所以请把它当作一个顶层概述 Multi-Paxos 是什么。

日志是一个强大的概念，我们可以将其用作构建分布式状态机的秘诀——只需将每条记录视为一个更新命令。不幸的是，在某些情况下，也有很多开销。例如，如果您想构建一个键/值存储并且您只关心当前值而不是不需要历史记录，并且可能需要实施垃圾收集以从日志中删除过去的版本以优化存储成本。

方法 #2 - “是”

Mindset：可重写寄存器作为 Multi-Paxos 的高度优化版本。

如果您从描述的方法开始，使用应用程序创建键/值存储，然后迭代其他方法以消除开销，例如，通过动态进行垃圾收集，那么最终您可能会想出如何更新的想法一次写入寄存器可重写。

在这种情况下，每个实例都使用相同的选票号码，因为所有实例都被折叠成一个可重写实例。

我在Paxos 的工作原理一文中描述了这种方法，并在Gryadka项目中用 500 行 JavaScript 实现了它。此外， Greg Rogers和Tobias Schottdorf对 TLA+ 进行了独立检查。

于 2017-10-11T14:55:48.297 回答