问题标签 [paxos]

在Paxos made simple Lamport 中描述了算法的阶段 2 (a) 如下：

如果提议者从大多数接受者那里收到对其准备请求（编号为 n）的响应，那么它会向这些接受者中的每一个发送一个接受请求，以获取编号为 n 且值为 v 的提议，其中 v 是最高-在响应中编号的提案，或者如果响应报告没有提案，则为任何值。

• 这是否意味着提议者可以在收集到大多数接受者的响应后立即发送接受请求，而不管他们的提议编号如何？（我发现引用的强调部分暗示了这一点，因为所有相同编号的提案都应该具有相同的价值，对吧？）
• 或者提议者是否需要来自大多数接受者的具有相同提议编号的响应？（意味着编号为m（小于n）的响应不计入编号为n的响应的多数）

“非全日制议会”第 3.3.6 节建议，可以安全地更改议会成员（以及因此决定的法定人数），“让通过法令时使用的议会成员在法令中由法律指定n-3"。

翻译成更常见的 MultiPaxos 术语，这意味着接受者集成为复制状态机状态的一部分，由添加或删除接受者的提议更改。槽 N 的法定人数将从决定槽 N-3 时的状态中定义的接受者集合中获取。

Lamport 没有为这个决定提供任何理由，虽然他的下一段说必须小心处理更改并描述了算法的最终失败，但它失败的原因与这个特定问题无关。

这是确保一致性的充分保障吗？如果有，有哪些文献支持它？

在paxos算法中，wiki中有一段描述：

阶段 2a：接受请求

如果 Proposer 从 Quorum of Acceptor 收到足够多的 Promise，它需要为其提案设置一个值。如果任何 Acceptor 之前接受过任何提案，那么他们会将其值发送给 Proposer，Proposer 现在必须将其提案的值设置为与 Acceptor 报告的最高提案编号相关联的值。如果到目前为止没有任何 Acceptor 接受提案，那么 Proposer 可以为其提案选择任何值。 [17] Proposer 向Acceptor 的Quorum 发送一个Accept Request 消息，并为其提议选择值。

假设提议者向五个接受者发送 Propose(4) 并接收回 Ack(abc, 2)、Ack(abc, 2) 和 Ack(xyz, 3)，它必须发送 Accept(xyz, 4)。

我的问题是：

1. 如果提议者最后必须发送 Accept(xyz,4)，那么当提议者使用自己的值发送接受请求时，例如。接受（qwe，n）？

2. 发送 Ack(xyz,3) 的接受者在看到新接受时会做什么，为什么？

谢谢

I am going to implement a key value store with multi Paxos. I would have several nodes, one of which is the primary node. This primary node receive update requests and replicate values to slave nodes.

My question is how the primary node (or leader) is selected? Can I still use the Paxos algorithm? If so, do you think it is necessary to abstract the paxos implementation to a single unit that could be used not only by the replication unit but also the leader election unit？</p>

If I use the node with the least id to be the leader? How can I implement the master lease?

Thanks for any answers.

下面的问题是严肃的，而不是轻浮的。我缺乏分布式系统方面的经验，但我确实了解 Basic Paxos 的工作原理以及领导者选择为何有用。不幸的是，我的理解还不够深入，无法理解以下问题。

在论文Consensus on Transaction Commit的第 8 页（链接 PDF 的第 11 页）中，我们有以下声明。

选择一个唯一的领导者就相当于解决了共识问题。

如果这句话是真的，而且 Paxos 的目的是达成共识，为什么 Paxos 本身一般不用于领导选举？

此外，同一篇论文也支持描述了稳定领导者选举论文的领导者选举算法。

如果这两个问题是等价的，并且同一篇论文支持不同的领导者选举算法，为什么不使用其他算法来解决一般共识问题而不是 Paxos？

我对使用 Paxos 算法感到困惑。似乎 Paxos 可以用于这样的场景：多个服务器（一个集群，我假设每个服务器都有 3 个角色，proposer、acceptor、leaner）需要保持相同的命令序列以实现一致性和备份。我假设有一些客户端向该服务器发送命令（客户端可能并行发送）。每次命令由一个 Paxos 实例分派到多个服务器时。

1. 不同的客户端可以向不同的提议者发送不同的命令，对吧？

如果是这样，来自某个客户端的一个命令将引发一个 Paxos 实例。所以，

2. 多个 Paxos 实例可以同时运行？

如果是这样，client-A 向proposer-A 发送“A += 1”命令，client-B 几乎同时向proposer-B 发送“B += 2”命令，我想看到每个服务器都收到了 2命令，“A += 1”和“B += 2”。

然而，

3. 给定 5 个服务器，比如 S1-S5，S1 发送命令“A += 1”和 S5 发送命令“B += 1”，S2 承诺 S1 但是 S3，S4 承诺 S5，所以最后 S3、S4、S5 得到“B + = 1" 但 S1,S2 什么都没有，因为承诺的数量不是多数。似乎 Paxos 根本没有帮助。我们在所有 5 台服务器上都没有得到预期的“A += 1”和“B += 2”？

4. 所以我猜在Paxos的实际应用中，不允许并行Paxos实例？如果是这样，如何避免并行 Paxos 实例，如果我们允许多个客户端和多个提议者，我们似乎仍然需要一个中心化服务器来标记是否有一个 Paxos 正在运行。

5. 另外，我对提议者编号有疑问。我在互联网上搜索，有人声称以下
   是一个解决方案：5 个服务器，给定相应的索引 k(0-4)，每个服务器使用数字 5*i + k 来表示该服务器的第“i”个提案。

对我来说，这似乎完全不符合要求，因为 server-1 的第一个提案编号始终为 1，而 server-4 的第一个提案编号始终为 4，但是 server-4 可能比 server-1 更早提出提案，但它是提案数字更大。

如果我们正在运行 multi-paxos，那么一个节点可能会看到：

这可能是因为：

• 有一个稳定的领导者，但该节点的本地网络下降，否则延迟 +2 和 +3。
• 有一次中断，因此有两次尝试提议，使得 +2 和 +3 是失败的轮次提议

一般来说，分布式有限状态机上的操作不会通勤，因此节点应该按顺序应用所有操作。这意味着节点需要能够区分这两种情况。如果提案轮次失败，则节点没有问题。如果消息丢失，则建议节点应该等到它们出现，否则尝试恢复丢失的数据（例如，请求快照以重新初始化和追赶）。

处理此问题的选项或策略是什么，它们会产生什么开销？

这个问题受到In Paxos 的启发，Acceptor 是否可以在接受了一个值之后再接受一个不同的值？

谁能帮助介绍如何从分布式集群中读取内容？

我的意思是有一个分布式集群，它的一致性是由 Paxos 算法保证的。

在实际应用中，客户端如何读取他们写入集群的内容？

例如，在一个 5 台服务器集群中，可能只有 3 台获得最新数据，而另外 2 台由于网络延迟或其他原因有旧数据。

这是否意味着客户端至少需要读取所有节点中的大多数？在 5 台服务器中，这意味着从至少 3 台服务器读取数据并检查版本号最新的服务器？

如果是这样，看起来很慢，因为您需要阅读 3 份？现实世界如何实现这一点？

为什么multi-paxos被称为multi-paxos？我看不出它是如何“多”的。

Can someone explain me simply the main differences between Operational Transform and CRDT?

As far as I understand, both are algorithms that permits data to converge without conflict on different nodes of a distributed system.

In which usecase would you use which algorithm? As far as I understand, OT is mostly used for text and CRDT is more general and can handle more advanced structures right?

Is CRDT more powerful than OT?

I ask this question because I am trying to see how to implement a collaborative editor for HTML documents, and not sure in which direction to look first. I saw the ShareJS project, and their attempts to support rich text collaboration on the browser on contenteditables elements. Nowhere in ShareJS I see any attempt to use CRDT for that.

We also know that Google Docs is using OT and it's working pretty well for real-time edition of rich documents. Is Google's choice of using OT because CRDT was not very known at that time? Or would it be a good choice today too?

I'm also interested to hear about other use cases too, like using these algorithms on databases. Riak seems to use CRDT. Can OT be used to sync nodes of a database too and be an alternative to Paxos/Zab/Raft?