paxakos

帕萨科斯是基于莱斯利·兰伯特的 Paxos 的分布式一致性算法的纯 Rust 实现。它使得分布式系统能够在出现故障的情况下，在其网络中一致地修改共享状态。

用法

为了使用帕萨科斯，需要实现 traits LogEntry、State、NodeInfo 和 Communicator。前两者描述了将在网络中复制的状态以及对其可用的操作。后者描述了您的网络中的节点以及它们之间的通信方式。

下面是两个 部分 实现的 LogEntry 和 State。其他两个 trait 更抽象，这里不会展示。请参考示例以获得更全面的了解。

use std::collections::HashSet;
use std::convert::Infallible;

use paxakos::{LogEntry, State};
use uuid::Uuid;

#[derive(Clone, Copy, Debug, serde::Deserialize, serde::Serialize)]
pub enum CalcOp {
    Add(f64, Uuid),
    Div(f64, Uuid),
    Mul(f64, Uuid),
    Sub(f64, Uuid),
}

impl LogEntry for CalcOp {
    type Id = Uuid;

    fn id(&self) -> Self::Id {
        match self {
            CalcOp::Add(_, id)
            | CalcOp::Div(_, id)
            | CalcOp::Mul(_, id)
            | CalcOp::Sub(_, id) => {
                *id
            }
        }
    }
}

#[derive(Clone, Debug)]
pub struct CalcState {
    applied: HashSet<Uuid>,
    value: f64,
}

impl State for CalcState {
    type Context = ();

    type LogEntry = CalcOp;
    type Outcome = f64;
    type Effect = f64;
    type Error = Infallible;

    fn apply(
        &mut self,
        log_entry: &Self::LogEntry,
        _context: &mut (),
    ) -> Result<(Self::Outcome, Self::Effect), Self::Error> {
        if self.applied.insert(log_entry.id()) {
            match log_entry {
                CalcOp::Add(v, _) => {
                    self.value += v;
                }
                CalcOp::Div(v, _) => {
                    self.value /= v;
                }
                CalcOp::Mul(v, _) => {
                    self.value *= v;
                }
                CalcOp::Sub(v, _) => {
                    self.value -= v;
                }
            }
        }

        Ok((self.value, self.value))
    }

    fn freeze(&self, _context: &mut Self::Context) -> Self::Frozen {
        self.clone()
    }
}

动机

Rust 是一种很好的语言，可以用来实现高效和真正可靠的、容错的服务。虽然已经存在几种 Rust 实现的一致性算法，但它们要么过于简单，要么不完整，或者它们的 API 对于作者来说不够易用。

优先级

项目优先级如下。

1. 正确性

   最高优先级是 正确性，在一致性算法的上下文中，这要求 稳定性、一致性 和 活性。

   • 稳定性 意味着一旦节点得知日志条目 a 已被追加到分布式日志中，它将永远不会得知另一个条目 b 应该在它的位置。
   • 一致性 意味着帕萨科斯网络中的所有节点都同意其共享日志的内容。虽然节点可能暂时落后，即它们的日志可能比其他节点短，但它们的日志必须在其他方面等效。
   • 活跃性意味着系统不会陷入停滞，即始终会取得进展（假设没有竞争/一定程度的合作）。

2. 简洁性

   Paxakos 通过提供少量正交原语来追求简洁。明确地说，目标不是任意限制复杂性。目标是拥有无纠缠的原语；以尽可能少的复杂性提供相同的特性。

3. 人体工程学

   使用 Paxakos 应该尽可能愉快，同时不牺牲正确性或简洁性。目前这个领域最大的挑战是构建时间。如果您有其他顾虑，请提出问题。

特性

Paxakos 是一个 Multi-Paxos 实现。它支持成员更改、并发以及获取和安装快照。

成员更改

State 特性公开了 cluster_at 方法。通过实现它，可以做出 任意 的成员更改。不施加任何限制，确保任何转换的安全性取决于用户和实现者。

并发

Multi-Paxos 允许多个回合并发解决。这可以通过实现 State 的 并发 方法来利用。

请注意，当启用并发时，日志中可能会出现间隙。必须在应用其后条目之前关闭这些间隙。这通常通过附加无操作条目来完成。提供了一个自动执行此操作的实用程序，但其 API 远未稳定。

快照

节点可以对其当前状态进行快照。结果是应用特定的 State 以及 pakakos 特定的信息的组合。这些快照可用于优雅地关闭和重启，引导已加入集群的节点或赶上落后的节点。

装饰

Decoration 特性的实现可以提供可重用的功能，但并不需要使用。Paxakos 随带提供了一些装饰（见下文）。

心跳（heartbeats 标志）

心跳装饰会定期发送心跳消息。

自动填充（autofill 标志）

有时分布式日志中会出现间隙。例如，由于 并发 或丢失的消息。在这种情况下，autofill 装饰将填充间隙，隐式地赶上节点或将队列中的日志条目应用到状态中。

跟踪领导权（track-leadership 标志）

领导权跟踪装饰推断出哪些节点是集群的领导者。

确保领导权（实验性，ensure-leadership 标志）

与心跳类似，确保领导权的装饰将在一段时间内没有领导权后附加日志条目。然而，此装饰的目标是确保存在领导者。

自动委派（实验性，delegation 标志）

Delegate 装饰允许自动委派附加操作，通常到领导者节点。

自动赶上（实验性，catch-up 标志）

当节点启动或安装快照时，它很可能落后。CatchUp 装饰将轮询其他节点，直到节点赶上。

一致性验证（实验性，verify 标志）

《Verify》装饰将定期检查所有节点之间是否一致。与多数节点不一致的节点将将其状态驱逐以减少传播的可能性。

租约

集群通常会拥有共享资源，在访问之前必须加锁。为了应对节点故障，租约会在刷新之前超时。此类锁通常被称为“租约”。

租约器（实验性，leaser标志）

Leaser使获取、刷新和释放租约与调用take_lease一样方便。只要持有返回值，租约就会刷新。

释放器（实验性，releaser标志）

释放器装饰确保超时的租约被清除，释放底层资源。

主租约（实验性，master-leases标志）

主租约是一种允许被动本地读取的机制。更全面的描述可以在Paxos Made Live中找到。

协议

本节描述了Paxakos协议。它基本上是一个典型的多Paxos协议。多Paxos将Paxos泛化到可以运行多轮，其中每一轮代表分布式日志中的一个槽位。节点可以向这些槽位提出日志条目。活性属性保证了集群在每个轮次最终会收敛到一个提出的条目。

协议的一个核心组件是协调数字。这些通常被称为“提案数字”。然而，因为它们在整个协议中都被使用，Paxakos使用了更抽象的术语。

将条目追加到分布式日志需要以下五个步骤。

1. 准备 (RoundNum, CoordNum)

   为了使一个节点能够将条目追加到分布式日志中，它必须首先成为该轮次的领导者。如果它已经认为自己是该轮次的领导者，它将跳到步骤3。

   为了成为某轮次的领导者，节点将发送一个包含轮次号和协调数字的prepare消息。协调数字被选择得

   • 高于任何先前遇到的协调数字
   • 并且保证不会被另一个节点使用。

   前者对于活性很重要。后者对于稳定性和一致性是必需的，并且通过利用cluster_at返回的节点的确定性顺序来实现。

2. 投票

   当一个节点收到一个prepare请求时，它会检查它是否没有接受过一个协调数字更高的先前此类请求。如果有，它将回复冲突。如果没有，节点将弃权，即选择不投票，或者它发送回一个承诺，即不会接受任何协调数字低于给定值的更多提案。

   1. 承诺 (Vec<(RoundNum, CoordNum, LogEntry)>)

      承诺是一组三元组，每个三元组由一个轮次号、一个协调数字和一个日志条目组成。它可以理解为“我承认你成为领导者的请求并给你我的投票。然而，作为回报，你必须尊重我之前做出的这些承诺。”

   2. 冲突 (CoordNum, Option<(CoordNum, LogEntry)>)

      发送拒绝信息时，包含迄今为止观察到的最大协调数。对于特殊情况，如果该轮已经收敛且节点仍然有可用信息，它也将发送该信息。

   3. 弃权 A

      节点选择弃权。默认情况下，节点永远不会弃权。这可以通过提供自定义的 Voter 实现来更改。类型参数 A 由 Communicator::Abstain 和 Voter::Abstain 定义。

3. 提议 (RoundNum, CoordNum, LogEntry)

   当一个节点发送了一个 prepare(r, c) 请求并且收到了来自法定多数的承诺（包括它自己的），它将相信自己成为了所有轮次 r.. 的领导者。它现在可以使用 c 作为协调数来开始提议任何这些轮次的日志条目。

   唯一的限制是它必须尊重它所收到的承诺。如果有多个承诺包含相同轮数的三元组，具有最大协调数的那个获胜。（具有相同轮次和协调数的三元组也将具有相同的日志条目。）

4. 投票

   当一个节点收到一个提议时，它会检查它是否做出了任何冲突的承诺。如果有，它将回应冲突。如果没有，它可以选择接受或拒绝提议并相应地回复。

   1. 接受 Y / 拒绝 N

      默认情况下，节点接受所有提议，使用 Y = ()。这可以通过提供自定义的 Voter 实现来更改。参数类型 Y 和 N 由 Communicator::Yea，Communicator::Nay，Voter::Yea 和 Voter::Nay 定义。

   2. 冲突 (CoordNum, Option<(CoordNum, LogEntry)>)

      参见 2.2。

5. 提交 (RoundNum, CoordNum, LogEntry::Id) / 通过ID提交 (RoundNum, CoordNum, LogEntry)

   在收到法定多数的接受后，该轮已经收敛到提议的条目。领导者节点将本地提交条目并通知其他节点。发送接受的节点将只收到日志条目的ID，其他节点将收到完整的条目。

项目状态

本节检查了paxakos的不同方面，包括它们的进展情况以及缺少或需要改进的内容。

☀️ 共识实现 ☀️

paxakos的核心算法经过充分测试并且已经进行了大量实践。有理由对其正确性有信心。

⛅ 被动模式 ⛅

被动模式 已实现并进行了初步测试。还需要进行彻底的测试。

⛅ 序列化 ⛅

快照序列化基于serde并且仍在发展中。

⛅ API稳定性 ⛅

API相当稳定，没有理由预期会有大的变化。装饰品可能需要重新设计，以便它们的配置 可以 移入到 State。

⛅ 效率 ⛅

Paxakos支持并发，并实现了一个（目前尚处于基础阶段）的主租赁机制。假设采用将委托给当前主节点的方案，这种组合具有很高的效率。

未来方向

这是一个副项目。我将在我有时间的情况下（不分先后）着手以下工作。

• 测试
• 添加注释和文档
• 完善现有装饰
• 实现读取委托的装饰
• 找到一种方法来检测和响应节点被遗留的情况
• 更新沙盒
  • 允许配置CatchUp和Verify
  • 可视化CatchUp
  • 添加主租赁装饰
  • 添加委托装饰

许可：GPL-3.0-only