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 的状态机状态:

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

代码分享计时器

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

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

MQ 监听转发

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

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

状态机

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

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

从 MQ 消息的视角看状态机

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

消息来源分为两大类:

来源于 Network,即其他节点消息:

SignedProposal,接到已经签名的 proposal ,判断自身是否有权利投票、判断高度、验证签名、验证该轮是否为此节点提出 proposal 、发送该 proposal 下的 block transaction 给 auth 验证交易是否正常等一系列验证操作,最后给 计时器发送一个计时消息,转至状态。

RawBytes,接到对 proposal 的投票消息,根据投票的轮数不同分别处理,如果数据正常,则分别进入和状态。

来源于本地其他模块:

RichStatus,消息来自于 chain ,根据传输过来的状态表达的含义有多种,如果高度等于上一次共识高度,则表明块落盘成功,bft 状态由更改为; 如果高度等于上一次共识高度 - 1,则说明落盘出现了异常,bft 重新将上一次的共识结果发送到 MQ(如果还保留着的话)。同时根据 Richstatus 中的共识列表、prev_hash 等重要信息更新自身的信息。

VerifyBlockResp,消息来自于 Auth,Auth 接到 bft 发的交易信息并验证后,返回结果,如果验证无误,移除待验证交易列表中对应的交易,并将该 proposal 序列化到磁盘,状态切换为, 检查投票信息,如果投票信息已经大于 2/3 了,那么随即转入状态;如果验证失败,清除待验证交易信息,并广播,投空票,转入状态,检查投票信息,如果投票信息已经大于 2/3 了,那么随即转入状态。

BlockTxs 消息来自于 Auth,chain 落盘成功后的 Richstatus 消息 Auth 接到后,清除交易池中对应的交易,并从交易池中按一定顺序打包一份新的交易,发送给 bft。bft 接到消息后,先序列化到本地,再判断这个高度和轮数是否是自己出块,如果是,验证必要信息后生成一个新的 proposal,广播给整个链,发送计时消息。

从计时器的角度看状态机

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

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

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

总结

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180527G1G8NK00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券