Raft Lite

Raft Lite 是 Raft 协议算法的一个易于理解和形式化验证的实现。它旨在作为那些对理解 Raft 内部工作原理感兴趣的人的学习工具。

Raft 算法在 src/raft_protocol.rs 中实现，这是一个事件循环，处理所有应用请求、Raft 协议消息和定时器事件。您可以在此博客文章中找到这部分内容的详细说明。

模型检查代码在 src/model_check.rs 中。它使用 stateright，一个用于分布式系统的模型检查器。您可以在此博客文章中找到这部分内容的详细说明。

将 Raft Lite 作为库使用

将以下内容添加到您的 Cargo.toml

[dependencies]
raft-lite = "0.2.7"

要将其用于您的项目，您可以使用 RaftConfig 初始化一个 Raft 实例。您与 Raft 实例交互的方式是通过向它发送消息并从它接收消息。消息类型是 Vec<u8>。Raft 协议将保证消息传递是按总顺序进行的。

以下示例展示了如何使用 Raft Lite 实现单值共识。示例在 examples/dinner.rs 中。

use raft_lite::config::{RaftConfig, RaftParams};
use raft_lite::persister::AsyncFilePersister;
use raft_lite::raft::Raft;
use std::path::PathBuf;

#[tokio::main]
async fn main() {
    let guests = vec![
        "localhost:10624".to_string(),
        "localhost:10625".to_string(),
        "localhost:10626".to_string(),
    ];
    let dinner_options = vec![
        b"Ratskeller".to_vec(),
        b"Pizzeria Ristorante Lachoni".to_vec(),
        b"KFC".to_vec(),
    ];

    // spawn a raft instance for each guest
    for i in 0..guests.len() {
        let guests = guests.clone();
        let dinner_options = dinner_options.clone();
        tokio::spawn(async move {
            let mut raft = get_raft_instance(guests.clone(), guests[i].clone());
            // one for broadcast, one for receive
            let (raft_broadcast_tx, mut raft_receive_rx) = raft.run();

            // send dinner option of this guest
            let place = dinner_options[i].clone();
            raft_broadcast_tx.send(place).unwrap();

            // receive dinner options of all guests
            let mut count = 0;
            loop {
                let msg = raft_receive_rx.recv().await.unwrap();
                count += 1;
                if count == 2 {
                    // The last message is the final decision
                    let final_decision = String::from_utf8(msg).unwrap();
                    println!("Guest {}: we'll have dinner at {}!", i, final_decision);
                }
            }
        });
    }
    tokio::time::sleep(tokio::time::Duration::from_secs(5)).await;
}

fn get_raft_instance(peers: Vec<String>, self_addr: String) -> Raft {
    let path: PathBuf = PathBuf::from(format!("./data/dinner]/{self_addr}"));
    let raft_config = RaftConfig::new(
        peers.clone(),
        self_addr.clone(),
        RaftParams::default(),
        Some(path),
    );
    Raft::new(raft_config)
}

对 Raft Lite 运行模型检查

交互式运行

您可以通过运行以下命令来交互式地运行模型检查

cargo run -- -m explore 

如图所示，序列图显示了两个节点被选为具有不同任期的主节点。

在命令行中运行

您也可以在命令行中运行模型检查，以找到给定一定步骤（深度）的所有可能状态和转换。

cargo run -- -m check --depth 10

它将显示所有违反指定 Always 属性的反例，以及满足指定 Sometimes 属性的示例。

我的笔记本电脑在不到1秒的时间内给出了以下输出

$ cargo run -- -m check --depth 10
Checking. states=4, unique=4, depth=1
Checking. states=475674, unique=133824, depth=10
Checking. states=917040, unique=256771, depth=10
Done. states=924710, unique=259150, depth=10, sec=3
Discovered "Election Liveness" example Path[3]:
- Timeout(Id(0), ElectionTimeout)
- Deliver { src: Id(0), dst: Id(1), msg: VoteRequest(VoteRequestArgs { cid: 0, cterm: 1, clog_length: 0, clog_term: 0 }) }
- Deliver { src: Id(1), dst: Id(0), msg: VoteResponse(VoteResponseArgs { voter_id: 1, term: 1, granted: true }) }
Fingerprint path: 13280538127433316798/18417327358524522001/10876327409151634344/11261648250825353397
Discovered "Log Liveness" example Path[6]:
- Timeout(Id(2), ElectionTimeout)
- Deliver { src: Id(2), dst: Id(0), msg: VoteRequest(VoteRequestArgs { cid: 2, cterm: 1, clog_length: 0, clog_term: 0 }) }
- Deliver { src: Id(0), dst: Id(2), msg: VoteResponse(VoteResponseArgs { voter_id: 0, term: 1, granted: true }) }
- Deliver { src: Id(2), dst: Id(2), msg: Broadcast([50]) }
- Deliver { src: Id(2), dst: Id(0), msg: LogRequest(LogRequestArgs { leader_id: 2, term: 1, prefix_len: 0, prefix_term: 0, leader_commit: 0, suffix: [LogEntry { term: 1, payload: [50] }] }) }
- Deliver { src: Id(0), dst: Id(2), msg: LogResponse(LogResponseArgs { follower: 0, term: 1, ack: 1, success: true }) }
Fingerprint path: 13280538127433316798/5012304960666992246/2656658050571602193/12788966706765998312/12610557528799436519/6208176474896103011/7212898540444505159

许可协议

该项目遵循MIT许可证。

相关项目

• StorgataDB：基于Raft Lite构建的分布式键值存储。