藏川线前段

--- 摄于 2017 年 9 月 藏川线前段

CITA系列之共识算法——BFT

考虑了挺久，最后还是决定先将 BFT 模块拿出来讲解，executor 和 chain 在 cita 的流程中都是在最后处理数据和落盘的模块，先讲解数据来源可能会更有利于理解整体思路。我看代码的顺序（chain->jsonrpc->network->executor->auth->bft）与文章的顺序不太一致，导致在看完第三个模块之后才开始有一个整体的概念。这系列文章的目的是帮助读者轻松（不大量阅读源码）的了解 cita 的工作流程，对 cita 有一个完整的整体认知。

BFT

分布式应用绕不过去的话题就是共识算法，甚至可以说，共识算法就是分布式的核心。经典的拜占庭问题、CAP 理论是分布式方面的阶段性总结。我在分布式领域还是个菜鸟， 对整个学术理论的理解几乎都来自于一些经典书籍，对共识算法的了解也仅限于 Raft、TenderMint 这几个比较有名的算法，并且也仅仅是了解流程，代码实现方面几乎没有什么实践性的操作。这一篇文章，仅仅是针对 cita-bft 代码的一些浅层次讲解，更深入的部分，实力有限，理论知识匮乏，就不献丑了。

cita-bft 总体来说是 TenderMint 算法的变种实现，两轮投票后达成共识、投票开始的时候锁住该高度的 block，一轮没有达成共识则进入下一轮（round）投票，直到完成该高度的共识，保证整个链不会分叉。下面这个结构体就是整个 bft 的状态机状态：

pub enum Step {
    Propose,
    ProposeWait,
    Prevote,
    PrevoteWait,
    PrecommitAuth,
    Precommit,
    PrecommitWait,
    Commit,
    CommitWait,
}

bft 的代码实现，就是一个大的状态机，以及一个定时器，状态由链上消息通信以及计时器 timeout 机制推动。

代码分享

计时器

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/votetime.rs#L35

pub struct WaitTimer {
    timer_seter: Receiver<TimeoutInfo>,
    timer_notify: Sender<TimeoutInfo>,
    thpool: ThreadPool,
}

计时器，读写各一个 channel，加上一个线程池，它的任务很简单，接收状态机的计时命令，线程池计时完成后，将超时状态回复给 bft 状态机，bft 根据接收到的投票信息以及当前状态，决定是进入下一个状态还是回滚等操作。

MQ 监听转发

代码：https://github.com/cryptape/cita-bft/blob/develop/src/main.rs#L185

thread::spawn(move || loop {
    let (key, body) = rx_sub.recv().unwrap();
    let tx = mq2main.clone();
    let pool = threadpool.clone();
    pool.execute(move || {
        tx.send((key, body)).unwrap();
    });
});

这个部分也很简单，监听消息，立刻转发给 bft 状态机。

状态机

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/cita_bft.rs#L108

pub struct TenderMint {
    pub_sender: Sender<PubType>,
    pub_recver: Receiver<TransType>,

    timer_seter: Sender<TimeoutInfo>,
    timer_notity: Receiver<TimeoutInfo>,

    params: TendermintParams,
    height: usize,
    round: usize,
    step: Step,
    proof: TendermintProof,
    pre_hash: Option<H256>,
    votes: VoteCollector,
    proposals: ProposalCollector,
    proposal: Option<H256>,
    lock_round: Option<usize>,
    locked_vote: Option<VoteSet>,
    // lock_round set, locked block means itself,else means proposal's block
    locked_block: Option<Block>,
    //tx_pool: Pool,
    wal_log: Wal,
    send_filter: HashMap<Address, (usize, Step, Instant)>,
    last_commit_round: Option<usize>,
    htime: Instant,
    auth_manage: AuthorityManage,
    consensus_power: bool,
    unverified_msg: HashMap<(usize, usize), Message>,
    // VecDeque might work, Almost always it is better to use Vec or VecDeque instead of LinkedList
    block_txs: VecDeque<(usize, BlockTxs)>,
    block_proof: Option<(usize, BlockWithProof)>,

    // when snaphsot restore, clear wal data
    is_snapshot: bool,
}

这个结构体非常多 field，共识期间需要维护一堆状态，例如，当前节点是否有投票权利 consensus_power，接到投票后，需要先序列化在本地 wal_log，整个链的共识节点列表，即公钥管理 auth_manage，当前投票的 block locked_block，接到的prev_hash 验证完毕，until_block 验证完毕，交易信息未确认块 unverified_msg，链上各个节点的状态 send_filter，上一个高度的共识结果 block_proof，以及每一次进入投票阶段后，每一轮投票收到的票的 collector。

从 MQ 消息的视角看状态机

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/cita_bft.rs#L1365

消息来源分为两大类：

  1. 来源于 Network，即其他节点消息：
    • SignedProposal，接到已经签名的 proposal ，判断自身是否有权利投票、判断高度、验证签名、验证该轮是否为此节点提出 proposal 、发送该 proposal 下的 block transaction 给 auth 验证交易是否正常等一系列验证操作，最后给 计时器发送一个计时消息，转至 Step::ProposeWait 状态。
    • RawBytes，接到对 proposal 的投票消息，根据投票的轮数不同分别处理，如果数据正常，则分别进入 Step::PrevoteWait 和 Step::PrecommitWait 状态。
  2. 来源于本地其他模块:
    • RichStatus，消息来自于 chain ，根据传输过来的状态表达的含义有多种，如果高度等于上一次共识高度，则表明块落盘成功，bft 状态由 Step::Commit 更改为 Step::CommitWait; 如果高度等于上一次共识高度 - 1，则说明落盘出现了异常，bft 重新将上一次的共识结果发送到 MQ（如果还保留着的话）。同时根据 Richstatus 中的共识列表、prev_hash 等重要信息更新自身的信息。
    • VerifyBlockResp，消息来自于 Auth，Auth 接到 bft 发的交易信息并验证后，返回结果，如果验证无误，移除待验证交易列表中对应的交易，并将该 proposal 序列化到磁盘，状态切换为 Step::Precommit， 检查投票信息，如果投票信息已经大于 2/3 了，那么随即转入 Step::PrecommitWait 状态；如果验证失败，清除待验证交易信息，并广播，投空票，转入 Step::Precommit状态，检查投票信息，如果投票信息已经大于 2/3 了，那么随即转入 Step::PrecommitWait 状态。
    • BlockTxs 消息来自于 Auth，chain 落盘成功后的 Richstatus 消息 Auth 接到后，清除交易池中对应的交易，并从交易池中按一定顺序打包一份新的交易，发送给 bft。bft 接到消息后，先序列化到本地，再判断这个高度和轮数是否是自己出块，如果是，验证必要信息后生成一个新的 proposal，广播给整个链，发送计时消息。
从计时器的角度看状态机

代码：https://github.com/cryptape/cita-bft/blob/develop/src/core/cita_bft.rs#L1261

一般在状态机进入 *Wait 状态的时候，就会发一个计时消息给计时器，根据状态的不同有些是即刻返回超时消息，有些是等待一定时间后返回超时消息。

总体思路就是，在等待其他节点投票结果的过程中，给一个时间限制，在到达时间限定范围后，检查投票是否已经达到 2/3 ，即共识已经达成可以转入下一个状态，如果共识完成，则发送共识结果给 chain，如果没有，则或重发消息，或整体重新开始一轮投票，或当前 proposal 作废，重新开始。

总结

分布式应用的算法有两大类，拜占庭容错和非拜占庭容错，都挺复杂的，学术理论研究和工程实现也各不相同，我对这一块的了解相当匮乏，书也没看几本，论文就更不用说了，惭愧。

不管怎么说，目前 cita-bft 的代码实现讲解还是在磕磕绊绊中完成了，下一篇应该可以进入 executor 了，虽然本系列文章并没有打算深入讲 evm 虚拟机执行交易的过程，但是可以根据下一篇的讲解自行研究嘛。

评论区

加载更多

请登录后评论