问题标签 [raft]

etcd 使用的 Raft 算法和 Zookeeper 使用的 ZAB 算法都是使用复制日志来更新状态机。

我想知道是否可以通过简单地使用领导者选举和版本化值来设计一个类似的系统。以及为什么这些系统决定使用复制日志。

如果我们有以下设置，我就是我的例子

• 机器 A（Leader），包含版本 1
• 机器 B（跟随者），包含版本 1
• 机器 C（跟随者），包含版本 1

写入将是这样的：

1. 机器 A 接收写入请求并存储待处理的写入 V2
2. 机器 A 向机器 B 和机器 C 发送准备请求
3. 追随者（机器 B 和机器 C）向领导者（机器 A）发送确认
4. 领导者（机器 A）从机器的 quorum 收到确认后，它知道 V2 现在已提交，并向客户端发送成功响应
5. Leader（机器 a）向 Follower（机器 A 和机器 B）发送 finalize 请求，通知他们 V2 已提交，V1 可以被丢弃。

为了使该系统正常工作，在获得领导者租赁后领导者发生变化时，领导者机器必须通过在接受请求之前从节点的法定人数中读取来获取最新的数据版本。

斯坦福大学的 Raft 幻灯片 ( https://ramcloud.stanford.edu/~ongaro/userstudy/raft.pdf ) 表明 Raft 处理以下故障模型：故障停止（不是拜占庭）、延迟/丢失消息。这是否意味着在某些故障恢复情况下，它可能变得不一致，或者它对故障恢复故障具有弹性？

当领导者在所有追随者更新提交索引之前崩溃时会发生什么？

例如，节点 A、B、C 构成集群：

• 只有 A 和 B 活着，A 是领导者

• A 将一个条目（假设它是 entry1）复制到 B 并从 B 获得成功的结果

• A 提交 entry1，并在向 B 发送心跳消息之前崩溃（这将导致 B 更新其提交索引）

• C现在上线

我的问题是：

• C会被选为新的领导者吗？如果是这样，那么 entry1 丢失了吗？而且，如果A以后重新加入，它的数据会不会和其他人不一致？

我知道筏规范说：

Raft 使用一种更简单的方法，它保证从选举的那一刻起，每个新领导者上都存在之前任期内所有已提交的条目，而无需将这些条目转移给领导者。

但是这里的entry1可能不被认为是committent entry？因为B没有得到老leader的确认（leader的心跳）。那么C有机会成为新的领导者吗？

• 如果B成为新的leader，那么它应该如何处理entry1？

我正在尝试实现分布式 Multimap。该映射使用状态机，只要将提交写入底层集群的日志（如果重要，则为 raft 集群），就会触发该状态机。我遇到的问题是在传统的分布式映射中，一旦删除命令已提交到集群中所有机器的日志或更新提交已放置在大多数节点上，您就可以将提交标记为压缩。在这种情况下，日志中的多个提交可能会影响与单个键关联的一组值。我想合理有效地压缩日志条目，这在我的解释中意味着选择会导致 Multimap 当前状态的最小条目集是系统崩溃并且重播日志中的非压缩提交。

我目前最好的解决方案是一个贪心算法，它选择对当前状态贡献最多值的提交，然后在第一次提交存在的情况下选择对状态贡献最大的提交，依此类推，直到提交的子集代表整个当前状态被选中。然后将未选择的提交标记为压缩。

我希望有人可以提出更有效的解决方案，因为贪心算法肯定不是最理想的，应该注意算法性能很重要，并且此处理是在单个线程上执行的。

谢谢！

在 raft 的论文文档第 6.4 章中，它给出了绕过 Raft 日志进行只读查询并仍然保持线性化的步骤：

1. 如果领导者尚未将其当前任期内的条目标记为已提交，则它会一直等到这样做。领导者完整性属性保证领导者拥有所有已提交的条目，但在其任期开始时，它可能不知道那些是哪些。要找出答案，它需要从其任期内提交一个条目。Raft 通过让每个领导者在其任期开始时将一个空白的 no-op 条目提交到日志中来处理这个问题。一旦这个无操作条目被提交，领导者的提交索引在其任期内将至少与任何其他服务器一样大。
2. 领导者将其当前提交索引保存在局部变量 readIndex 中。这将用作查询操作所针对的状态版本的下限。
3. 领导者需要确保它没有被它不知道的新领导者取代。它发出新一轮的心跳并等待大多数集群的确认。一旦收到这些确认，领导者就知道在发送心跳的那一刻，领导者不可能存在更长的任期。因此，当时 readIndex 是集群中任何服务器所见过的最大提交索引。
4. 领导者等待其状态机至少前进到 readIndex；这足以满足线性化。
5. 最后，领导者针对其状态机发出查询，并用结果回复客户端。

我的问题：

a）对于第1步，是否仅适用于刚刚选举出领导者时的情况？因为只有新领导者没有为当前任期提交条目。并且由于 no-op 条目对于找出当前提交的条目是必要的，那么实际上这一步在选举完成时总是需要的，但不仅限于只读查询吗？换句话说，通常，当领导者活动一段时间时，它必须在其任期内提交条目（包括无操作条目）。

b) 对于第 3 步，这是否意味着只要领导者需要提供只读查询，就会发送一个额外的心跳，而不管当前未完成的心跳（已发送但尚未收到主要响应）或下一个预定的心跳？

c) 对于第 4 步，是否仅适用于追随者（对于追随者帮助卸载只读查询处理的情况）？因为在领导者上，提交的索引已经意味着它被应用于本地状态机。

总而言之，正常情况下，leader（活跃一段时间）只需要做第3步和第5步，对吧？

我一直在阅读有关 Raft 的几个文档，并且我得到了关于提交的相互矛盾的信息。我知道一个条目只有在已知存储在大多数服务器中时才能提交，但是还有其他条件吗？我已经读过，当前术语的条目也必须存储在每个服务器中，但其他一些文档对此只字未提。有什么帮助吗？

日志清理会删除对当前状态没有贡献的条目，那么如果慢速追随者或新成员需要它们，如何为这些删除的条目构造 AppendEntries？需要修改 AppendEntries 以便它可以包含不连续的条目？还是改用快照？

我正在用Raft 论文从头学习 Raft ，我无法理解领导者选举过程。我在 5.4.1 中读到，领导者需要在其日志中包含集群的所有已提交条目：

Raft 使用一种更简单的方法，它保证从选举的那一刻起，每个新领导者上都存在之前任期内所有已提交的条目，而无需将这些条目转移给领导者。

Raft uses the voting process to prevent a candidate from winning an election unless its log contains all committed entries.

但后来，据说候选人持有所有提交的条目，如果它至少与大多数其他日志一样最新。确定这个最新的机制是比较最后条目的索引和术语。最后一个条目上具有较高期限的日志将是最新的。

这难道不会导致在没有所有先前提交的条目的情况下选举领导者的情况吗？例如：

在这种情况下，如果服务器 4 发生故障，服务器 2 可能会成为领导者，因为它有一个比大多数人更大的条目。但它不会在其日志中包含第 2 学期的两个已提交条目。对吗？我误解了一些东西，但我能明白它是什么......

最近在写一个使用hashicorp/raft包的分布式系统，系统的每个节点都会做整个工作的一部分。当一个节点发生故障时，它的工作结果会丢失，然后我需要让其他节点重新运行它的工作。但是 hashcorp/raft 没有提供任何 API 来添加回调，我该怎么办？

假设上图中d被选为leader，它将如何处理索引为11和12的日志。在我看来，它应该删除这两个日志，但是我在raft论文中没有找到关于如何处理的任何线索处理类似上述场景的日志。