问题标签 [paxos]

我正在研究 Paxos 提出的简单论文，并且我正在努力解决这样一个事实，即如果 2 个提议者以更高的提议数量相互竞争，Paxos 不能保证进度，并且正如论文中所建议的那样，为了保证进度，必须是杰出的提议者选择这使他成为领导者。

但是问题来了，因为人们建议使用 Paxos 来选举杰出的提议者，这再次需要领导者来保证进度。

我知道给定的场景可能是特定于实现的，例如，如果给进程选择的区分集是有序的，我的意思是 P1 集 < P2 集。

但我想了解在实际实现中这是如何处理的？

为什么 Paxos 需要两个阶段（prepare/promise+ accept/accepted）而不是一个阶段？也就是说，仅使用prepare/promise部分，如果提议者已收到大多数接受者的回复，则选择该值。

问题是什么，是破坏安全还是破坏活力？

论文CORFU: A Distributed Shared Log以伪代码形式展示了该协议，该协议不验证删除消息。引用论文：

这意味着我们可以删除尚未写入的页面。这也意味着客户端可以使用过时的集群配置删除页面。这是否意味着论文中提出的协议可能会丢失删除？

根据论文 CORFU 保留删除地址的高水印作为内存空间优化。如果我们可以丢失删除，那么高水位线将不会移动，我们将耗尽内存。

如果我们使用 CORFU 进行状态机复制，我们可以对状态机进行快照并删除快照之前的日志。如果我们可以丢失删除，那么日志实际上将永远增长。

而不是仅仅应用删除而不进行验证，一个实现不会简单地使删除具有幂等性，但如下验证它们：

还是会以某种方式损害安全性或性能？

我正在阅读Paxos 变得简单的论文，但被困在 P2 ^b的证明部分。

规则 P2 ^b的内容：

如果选择值为 v 的提案，则任何提案者发布的每个编号较高的提案都具有值 v。

这是 Leslie Lamport 的证明部分：

为了发现如何满足 P2 ^b，让我们考虑如何证明它成立。我们假设某个编号为 m 且值为 v 的提案被选中，并表明任何编号为 n > m 的提案也具有值 v。我们将通过对 n 使用归纳来简化证明，因此我们可以证明编号为 n 的提案在附加假设下具有值 v ，即每个提案都以 m 中的数字发布。. (n - 1) 的值为 v ，其中 i 。. j 表示从 i 到 j 的数字集。要选择编号为 m 的提案，必须有一些由大多数接受者组成的集合 C，使得 C 中的每个接受者都接受它。将此与归纳假设相结合，选择 m 的假设意味着：

C 中的每个接受者都接受了一个编号为 m ..(n - 1) 的提案，并且任何接受者接受的每个编号为 m ..(n - 1) 的提案都具有值 v

所以归纳过程是：

• 基本情况：选择了值为v的提案m
• 归纳步骤：任何编号为m ..(n-1) 的提案都具有值v

为什么它意味着：

C 中的每个接受者都接受了一个编号为 m ..(n − 1) 的提案

我只是无法弥合差距，为什么C中的每个接受者都需要接受编号为m..(n-1)的提案？

P1保证接受者必须接受收到的第一个提案， P2 ^a保证只有具有所选值的编号较高的提案才能被接受者接受，但我只是不明白隐含声明的重点。

谁能告诉我为什么提案 ID 在 Paxos 中必须是唯一的？我认为这个proposalId需要唯一的原因是我们需要用它来拒绝旧的提案并对最大投票进行排序。所以如果我们做第一阶段：acceptor 只接受大于promisedId 的proposal 并且是增量的，它仍然可以保证一致性。

我们假设proposer A 向acceptors 提出一个proposal（proposalId x, value y），然后他得到了多数人的批准，另一个proposer B 具有相同的proposal id(x) 发出一个proposal request，这个proposer B 会被拒绝，对吧? 最终，我们仍然可以达到一致性，对吧？

我对“一致性”一词感到困惑。它已在许多不同的环境中使用，即分布式系统、内存模型和数据库。People/Wikipedia 在同一页面中总结了所有不同的一致性模型。但我真的不认为它们被用来描述同一个问题。

例如，顺序/放松/弱/严格/处理器一致性等在内存模型中是有意义的（由现代架构和现代语言编译器提供）。另一方面，顺序/最终一致性在分布式系统中有意义（当您尝试构建复制状态机时）。类似 Paxos/raft 的共识算法可以帮助你建立 SC 模型，而 DynamoDB 是 EC 模型的一个例子。

但是，在构建复制日志时谈论发布/弱一致性以及谈论内存模型中的最终一致性确实没有意义。

就传统的关系数据库而言，它让我更加困惑。由于在 ACID 模型中，一致性似乎意味着不同的概念。它只要求在事务之后，数据库应该处于有效/一致的状态。但是，ACID 的隔离部分听起来更像是 Consistency Model，特别是 Sequential 一致性模型。

我在这里有什么误解吗？或者计算机人只是喜欢滥用术语和混淆人们......

如果我错了，请纠正我，即使只是小细节。我真的很想正确理解这些概念。谢谢 ： ）

看了paxos和raft论文后，我有以下困惑：paxos论文只描述了对单个日志条目的共识，相当于raft算法的leader选举部分。在 raft 的 leader 选举中，paxos 的方法相对于简单的随机超时方法有什么优势？

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

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

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

Paxos 算法（http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf）中有一点我不明白。这是关于如何处理差距的，论文描述了两种方法：

领导者以及学习领导者知道的所有命令的任何其他服务器现在可以执行命令 1-135。但是，它不能执行它也知道的命令 138–140，因为尚未选择命令 136 和 137。领导者可以将客户端请求的接下来的两个命令作为命令 136 和 137。相反，我们通过提出作为命令 136 和 137 的特殊“no-op”命令来立即填补空白，使状态保持不变. （它通过执行共识算法实例 136 和 137 的阶段 2 来做到这一点。）一旦选择了这些无操作命令，就可以执行命令 138-140。

1. 执行客户端请求的下两个命令
2. 特殊的“no-op”命令

已经提到了第二个选项为什么使用 no-op 来填补 paxos events 之间的空白是合法的。

我的问题是关于第一个问题。在我看来，接下来的两个命令会违反一致性，因为后面发生的实例可能具有较小的序列号。那么为什么它仍然是合法的呢？

在 HappyFunPizzaCorp 中，我们有一个 POS 系统，它生成两个事件：new_order事件和payment事件。这两个事件都包含一个用于交叉引用的披萨order_id键。

两个事件都被发送到一个交换器TheExchange。new_order事件总是在payment事件之前发出。

我们是一个非常繁忙的地方，例如每秒销售 100000 个比萨饼，因此不能选择串行处理所有记录。

所以问题是我们如何并行处理我们的工作负载，同时仍然保证在同一个披萨的事件new_order之前处理事件？payment

具有多个消费者的简单队列是行不通的。我们得到消费者之间的循环行为，因此事件可能与同一个披萨payment的事件同时处理。new_order

另一种解决方案是使用分片交换并将order_id用作分片键。虽然这听起来不错，但我们现在在队列之间有了一些内在的并行性，我们的消费者如何连接？我们可以有一组预定义的队列来防止由于重新分片而导致消息之间的重新分片和并行性。但是如果我们有多个消费者实例，他们如何决定使用哪些队列来消费数据。最重要的是，我们希望自动扩展我们的消费者。

我们当前的解决方案是使用共识协议（通过 zookeeper 的 raft/paxos）来确定每个消费者进程应该服务的队列数量和队列。我们在系统中有一个预设的（大量）分片队列，它们不应该改变。队列的消费者是排他的（最多提供一次交付保证），他们通过共识协议协调哪些队列应该由谁服务。

虽然这个设置似乎可以工作，但它似乎过于复杂，我想知道是否有我们缺少的参考解决方案。