raft-rust 0.1.0

//! 实现 Raft 分布式共识协议。
//!
//! 细节参见 Diego Ongaro 的原始文献：
//!
//! * Raft 论文：<https://raft.github.io/raft.pdf>
//! * Raft 学位论文：<https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf>
//! * Raft 网站：<https://raft.github.io>
//!
//! Raft 是一组计算机就某些数据达成一致的协议——更简单地说，就是复制数据。
//! 它与 [Paxos] 和 [Viewstamped Replication] 大致等价，但规定更明确、更易理解。
//!
//! Raft 有三个主要性质：
//!
//! * 容错：只要多数节点（>50%）仍在运行，系统就能容忍节点故障。
//!
//! * 线性一致性（强一致性）：客户端写一旦被接受，对所有客户端可见——他们不会看到过期数据。
//!
//! * 持久性：只要多数节点仍在，写就不会丢失。
//!
//! 做法是选出单一领导者节点，由它服务客户端请求并向其它节点复制写操作。
//! 请求在被严格多数（quorum）确认后执行。若领导者失败，则选出新领导者。
//! 集群通常有 3 个及以上节点，因为两节点集群无法容忍故障（1/2 不是多数，会导致脑裂）。
//!
//! 值得注意的是，Raft 不提供水平扩展。客户端请求由单一领导者处理，容易成为瓶颈，
//! 且每个节点保存完整数据副本。系统通常通过把数据分片到多个 Raft 集群，并在其间
//! 使用分布式事务协议来解决，但这超出了本文范围。
//!
//! 本实现基本遵循 Raft 论文，但与多数实现一样做了一些小的取舍。
//!
//! [Paxos]: https://www.microsoft.com/en-us/research/uploads/prod/2016/12/paxos-simple-Copy.pdf
//! [Viewstamped Replication]: https://pmg.csail.mit.edu/papers/vr-revisited.pdf
//!
//! Raft 日志与状态机
//! =================
//!
//! Raft 维护一条有序命令日志，包含客户端提交的任意写命令。它通过把日志复制到
//! 多数节点来尝试达成共识。成功后，日志到该点为止视为已提交且不可变。
//!
//! 一旦提交，日志中的命令会在每个节点上顺序应用到本地状态机。Raft 本身不关心
//! 状态机与命令是什么——可以是 SQL 数据库，也可以是任何东西。Raft 只是把不透明
//! 命令交给不透明状态机。
//!
//! 每条日志含索引、领导者任期（见下节）与命令。例如：
//!
//! Index | Term | Command
//! ------|------|------------------------------------------------------
//!   1   |   1  | CREATE TABLE table (id INT PRIMARY KEY, value STRING)
//!   2   |   1  | INSERT INTO table VALUES (1, 'foo')
//!   3   |   2  | UPDATE table SET value = 'bar' WHERE id = 1
//!   4   |   2  | DELETE FROM table WHERE id = 1
//!
//! 状态机必须是确定性的，使所有节点达到相同状态。Raft 会在所有节点上以相同顺序
//! 应用相同命令；若命令有非确定行为（随机数、外部通信等），会导致状态分叉与结果不一致。
//!
//! 本库中，Raft 日志由 `Log` 管理，本地保存在 `storage::Engine` 中。
//! 状态机接口是 `State` trait。详见各自文档。
//!
//! 领导者选举
//! ==========
//!
//! Raft 节点可处于三种状态（角色）：跟随者、候选人、领导者。
//! 本库建模为 `Node::Follower`、`Node::Candidate`、`Node::Leader`。
//!
//! * 跟随者：从领导者复制日志。可能尚不知道领导者。
//! * 候选人：在选举中竞选领导者。
//! * 领导者：处理客户端请求并向跟随者复制写操作。
//!
//! Raft 的根本保证是：任意时刻至多有一个**有效**领导者（旧的、已被替换的领导者
//! 可能仍以为自己是领导者，例如在网络分区时，但它们做不了什么）。
//! 该保证通过领导者选举协议强制执行。
//!
//! Raft 把时间划分为任期（term），任期是单调递增的数字。更高任期总是优先于更低任期。
//! 一个任期内至多一个领导者，且不能更换。节点跟踪其已知最后任期并落盘
//! （见 `Log.set_term_vote()`）。节点间消息带有当前任期（`Envelope.term`）——
//! 旧任期被忽略，未来任期会使节点成为该任期的跟随者。
//!
//! 节点以无领导者的跟随者起步。若收到领导者消息（当前或未来任期），则跟随它。
//! 否则等待选举超时（数秒），成为候选人并发起选举。
//!
//! 候选人把任期加 1，并向所有节点发送 `Message::Campaign` 请求投票。
//! 节点以 `Message::CampaignResponse` 回复是否授予选票。一个任期内节点只能投一票
//! （经 `Log.set_term_vote()` 落盘），先到先得；候选人隐式投自己。
//!
//! 候选人获得多数票（>50%）后成为领导者。它向所有节点发送 `Message::Heartbeat`
//! 声明领导权，收到的节点都成为跟随者（不论原先投给谁）。领导者约每秒发送一次心跳。
//! 新领导者还会向日志追加一条空条目，以便安全提交此前任期的条目（论文 5.4.2 节）。
//!
//! 新领导者日志中必须包含所有已提交条目（否则集群会丢数据）。为此，授予选票还有
//! 一个条件：候选人的日志至少与投票者一样新。因为条目必须复制到多数才提交，
//! 这保证只有日志已包含全部已提交条目的候选人才能赢得多数票（论文 5.4.1 节）。
//!
//! 也可能没有候选人获胜，例如平票或多数节点离线。选举超时后，候选人再次提升任期
//! 并发起新选举，直到选出领导者。为避免频繁平票，节点使用不同的随机选举超时
//! （论文 5.2 节）。
//!
//! 类似地，若跟随者在一个选举超时内未收到领导者消息，会成为候选人并发起选举。
//! 只要领导者在运行且连通，周期性心跳会阻止这种情况。与领导者断连的节点会不断
//! 独自发起选举，直到网络恢复，届时会在其任期举行新选举（打断当前领导者）。
//!
//! 复制与共识
//! ==========
//!
//! 领导者收到客户端写请求时，经 `Log.append()` 追加到本地日志，并以
//! `Message::Append` 发送给所有同伴。跟随者尝试持久追加到本地日志，并以
//! `Message::AppendResponse` 响应。
//!
//! 一旦多数确认追加，领导者经 `Log.commit()` 提交该条目，应用到本地状态机，
//! 并把结果返回客户端。它会在下一次心跳的 `Message::Heartbeat.commit_index` 中
//! 通知跟随者，以便它们也应用——但这不是正确性所必需的（它们成为领导者时会提交并应用；
//! 否则不必应用）。
//!
//! 跟随者可能无法追加：不可达、落后，或日志分叉（论文 5.3 节）。
//! `Append` 含被复制条目前一条的索引与任期，即 `base_index` 与 `base_term`。
//! 索引/任期对唯一标识命令；若两份日志有相同索引/任期对，则到该条目为止日志相同
//! （论文 5.3 节）。若 base 匹配跟随者日志，则追加（可能替换冲突条目），否则拒绝。
//!
//! 跟随者拒绝 append 时，领导者必须找到双方日志中的公共条目以恢复复制。
//! 做法是发送仅含 base 索引/任期、不含条目的 `Message::Append` 探测——
//! 逐个递减索引探测，直到跟随者响应匹配，再发送含缺失条目的 `Append`（论文 5.3 节）。
//! 用 `Progress` 结构跟踪每个跟随者的 `match_index` 与 `next_index`。
//!
//! 若 `Append` 消息或响应丢失，领导者还会在每次 `Heartbeat` 中发送 `last_index` 与任期。
//! 若跟随者日志中没有该索引/任期对，会在 `HeartbeatResponse` 中说明，
//! 领导者可像 append 被拒时一样开始探测其日志。
//!
//! 客户端请求
//! ==========
//!
//! 客户端请求以 `Message::ClientRequest` 提交给本地 Raft 节点。只在领导者上处理，
//! 但跟随者会代理到领导者（学位论文 6.2 节）。为避免消息重放的复杂问题
//! （学位论文 6.3 节），内部不重试请求，并在领导者/任期变更以及选举时以
//! `Error::Abort` 明确中止。
//!
//! 写请求 `Request::Write` 追加到 Raft 日志并复制。领导者用 `Write` 结构跟踪请求
//! 及其日志索引。命令提交并应用到本地状态机后，领导者按日志索引查找写请求并把结果
//! 发给客户端。确定性错误（如外键冲突）也返回客户端；非确定性错误（如 IO 错误）
//! 必须让节点 panic，以免状态分叉。
//!
//! 读请求 `Request::Read` 只在领导者执行，不必经 Raft 日志复制。但为确保线性一致性，
//! 领导者必须与多数确认自己仍是领导者。否则别处可能已选出新领导者并执行了写操作。
//! 做法是为每次读分配递增序列号，用 `Read` 结构跟踪请求，并立即发送带最新序列号的
//! `Read` 消息。跟随者用序列号响应，多数确认后执行读并把结果返回客户端。
//!
//! 实现取舍
//! ========
//!
//! 为简单起见，本实现只覆盖正确可用的最小 Raft，省略了生产系统需要的若干高级机制：
//!
//! * 无租约：为保证线性一致性，每次读都要求领导者与跟随者确认自己仍是领导者。
//!   可用预定义时间间隔的领导者租约避免（论文 8 节、学位论文 6.3 节）。
//!
//! * 已实现联合共识成员变更（论文 6 节）：`Request::ChangeMembership`。
//!
//! * 已实现 Pre-vote 与 CheckQuorum（可通过 `Options` 关闭）。
//!
//! * 无快照：新节点或落后节点须通过复制并重放整份日志追赶，而不能发送状态机快照
//!   （论文 7 节）。
//!
//! * 无日志截断：因不支持快照，整份 Raft 日志须永久保留以追赶新/落后节点，
//!   导致存储占用过大（论文 7 节）。
//!
//! * 无请求重试：领导者变更或消息丢失时不重试客户端请求，并积极中止，
//!   以规避消息重放问题（学位论文 6.3 节）。
//!
//! * 无拒绝提示：若跟随者日志分叉，领导者逐条探测直到找到匹配。
//!   复制协议可用拒绝提示扩展（论文 5.3 节）。

// 演示用 KV 状态机
pub mod kv;
// Raft 持久化日志（crate 内私有）
mod log;
// 联合共识成员配置
pub mod membership;
// 节点间消息与客户端请求类型
mod message;
// 角色状态机与 Node 驱动
mod node;
// 客户端 session 写去重
pub mod session;
// 应用状态机 trait
mod state;

// 选举超时默认区间类型
use std::ops::Range;
// tick 墙钟间隔
use std::time::Duration;

// 导出日志条目与索引类型
pub use log::{Entry, Index, Key, Log};
// 导出成员配置类型
pub use membership::{Membership, MembershipEntry, MembershipState};
// 导出协议消息与状态查询类型
pub use message::{Envelope, Message, ReadSequence, Request, RequestID, Response, Status};
// 导出节点与运行参数
pub use node::{Node, NodeID, Options, Term, Ticks};
// 导出会话包装状态机与编码辅助
pub use session::{encode_session, SessionState};
// 导出状态机 trait
pub use state::State;

/// Raft tick 的时间间隔，即 Raft 的时间单位。
// 约 100ms 一拍，心跳/选举超时以 tick 计
pub const TICK_INTERVAL: Duration = Duration::from_millis(100);

/// 领导者心跳间隔（以 tick 计）。
// 模块内默认；可被 Options 覆盖
const HEARTBEAT_INTERVAL: Ticks = 4;

/// 默认选举超时范围（以 tick 计）。为避免选举平票，节点在此区间内随机取值。
// 半开区间 [10, 20)
const ELECTION_TIMEOUT_RANGE: Range<Ticks> = 10..20;

/// 单条 Append 消息中最多发送的日志条目数。
// 限制单次 RPC 体积，避免大包阻塞
const MAX_APPEND_ENTRIES: usize = 100;