2021-05-08

Raft 协议和区块链

Views: 1150 | Add Comments

我还没有发现有人把 Raft 协议和区块链关联到一起讨论, 但是经过仔细分析, 穿透问题的本质之后, Raft 和区块链技术具有非常多的共同点. 可以整理出一个表格:

Raft 区块链 通用
日志 区块 Entry, Node, 节点, 记录
日志序列 区块链 Chain, 链表(前向指针)
选举: Leader 可产生日志 算力: 任意节点付出成本产生区块 Leader
Term 分叉 Branch
基于 Quorum 立即 Commit 立即相信最长的链条 Consensus, 共识
一经 Commit, 不可撤销 随时转而相信新的最长的链条 Commit, Rollback

Raft 和区块链的不同概念, 其实往往对应到通用技术里面的一个共同的概念.

节点是什么?

日志, 区块, 节点, 记录等等这些名词, 有着相似的意思, 都是链表(后文介绍)中的节点, 节点中会附加一些信息, 例如, SQL 语句, 具体看使用场景.

Chain 的作用是什么?

Raft 的日志序列的作用是显然, 就像照葫芦画瓢那样, 日志序列就是葫芦, 而结果就是瓢. 只要按顺序把日志重放一遍, 就能产生相同的结果. 例如对着两个空的数据库执行相同的一序列 SQL 语句, 最终两个数据库中的数据将是一模一样的.

区块链的作用不那么显然了, 如果把区块链的链(Chain)看作是葫芦的话, 那么目前还找不到瓢. 瓢是什么? 账本? 记什么账? 记比特币的账? 交易历史? 什么的交易历史? 这就是为什么说区块链技术缺少落地应用, 除了虚拟币, 大家短期还找不到现实生产应用场景.

不同于常见的链表数据结构, Raft 和区块链的链表结构, 通过前向指针来组成一个链条. 常见的链表是前一个节点指向后一个节点, 而日志序列和区块链是后一个节点指向前一个节点. Raft 日志序列中的指针是隐性的, 通过连续的整数 index 来确定前后关系, 例如是 index=3 的节点是 index=2 的节点的后一个节点.

Chain 如何增长?

现实生活中, 数据库中的数据需要根据实现的生产活动, 不断地增删改查, 意味着日志序列需要不断地增长, 每一次增删改操作都等价于往日志序列末尾添加一条记录(查操作在工程实践上一般会做优化, 不修改日志序列).

Raft 通过制定选举规则, 选出 Leader, 然后限定只有 Leader 才能往日志序列(链表)末尾添加新记录.

区块链系统中的所有成员, 基于算力(花费时间做大量的计算)产生新的记录添加到链表末尾.

Branch 为何出现?

Raft 由 Leader 产生日志, 只有 Leader 才能往链表的尾部增加节点. 但是, 某一时刻, 有可能出现两个"自认"的 Leader. 例如某个 Leader(term=1) 被网络隔离时, 其它成员选出了新的 Leader(term=2), 但旧 Leader 并不知晓, 所以旧 Leader 仍然可能往链表的尾部增加节点, 由此, 造成链表产生了分叉. 由于新旧 Leader 的 Term 不相同, 所以, 可以用 Term 来表示分叉.

有避免旧 Leader 错误认知的方法, 从而在源头上避免分叉. 例如, 通过带有时间限制租约机制(Lease), 可以让旧 Leader 在新 Leader 产生之前, 主动放弃 Leader 身份, 避免旧 Leader 产生错误的认知. 这里不讨论如何避免 Raft 日志序列产生分叉, 我们只讨论产生分叉之后, 如何处理.

区块链的每一个成员都能往链表尾部增加节点, 所以, 区块链无法像 Raft 那样避免分叉.

共识是什么?

由于分叉可能出现, 因此需要有共识, 以决定哪一个分叉才是"真"的, 其它的都是"假"的, 应该丢弃.

Raft 的 Leader 通过统计所有成员的分叉情况, 选出大多数人(Majority)都包含的那个分叉, 然后下结论, 宣布(Commit)那个分叉是真的, 其它的都是假的. 因为下结论需要基于 Majority, 基于鸽笼理论, Raft 能避免错误的自认的 Leader 下结论, 具体细节大家可以看 Raft 的细节文档.

Raft 的结论一旦确立(Commit), 就不能再修改. 有两种机制可以保证这个条件, 一是主观上要求 Leader 不要更改自己的决定, 二是客观上通过 Majority 保证新的 Leader 也会做相同的决定.

区块链没有所谓的结论, 因为没有 Leader, 所以没有谁能宣布(Commit)什么为真, 什么为假. 每一个节点都认为自己所看到的是真的, 即节点认定自己所看到的最长的分叉是真的. 因此, 区块链的节点一会儿看到这条分叉最长, 一会儿看到那条分叉最长, 它的观点会不断地摇摆, 有点像三姓家奴.

表面看起来, 如果区块链的节点(区块)上面保存的是 SQL 语句, 我们绝对不能执行这些语句, 因为我们没法确定真伪. 不过, 实际上, 由于节点的产生依赖算力, 节点针对越长的分叉, 再改变观点的可能性就越小, 所以, 我们可以基于成本考量, 认为带有 N 个区块"尾巴"的节点, 不会再被证明为假, 这样, 当一个节点后面跟着 N 个区块之后, 我们就可以放心地执行上面保存的 SQL 语句了. 这种策略不是绝对的, 只是我们基于科学分析得出的概率结论, 本来就没有绝对的.

我们能学到什么?

日志序列(日志复制状态机)是 Raft 总结出来的一个非常重要的概念, 这个概念反映了事物的本质, 也即有序, 串行化. 而乱序, 空洞, 不连续等等, 都是事物的中间不稳定状态, 最终事物应该向有序演化.

Related posts:

  1. Raft 为什么不能直接 commit 前任的日志?
  2. Raft ReadIndex 有什么神奇之处?
  3. Raft 选主优化之 PreVote
  4. Paxos和Raft读优化 – Quorum Read 和 Read Index
  5. 再谈 Paxos 和 Raft
Posted by ideawu at 2021-05-08 22:19:31 Tags:

Leave a Comment