事件驱动Hotstuff

    Basic HotStuff ->  Chained HotStuff         // 流水线进步吞吐   ->  Event-driven HotStuff    // Safety与Liveness解耦, 实现更简洁

事件驱动hs将实现分为了两局部, 其中负责Liveness性能(如选举, 超时, 同步view)的称为Pacemaker. 另一部分负责Safety, 次要通过Msg来更新节点状态, 笔者将这部分称为StateMachine。

Pacemaker

struct Pacemaker{    qc_high // 所见过最高的、已投票的QC    b_leaf  // 叶子节点}

Pacemaker的动作:

  • update_qc_high()如果新qc比pm持有的qc更高，那么更新qc_high和b_leaf.
  • on_beat(cmd)，如果本节点是新leader，通过调用sm.on_propose()来创立叶子并且将其播送给所有replica。
  • on_next_sync_view(), 向leader发送NewViewMSG带上本人的qc_high
  • on_recv_new_view(), 当leader收到NewView时, 如果附带的qc比本人持有的qc更高，就更新qc_high和b_leaf.

StateMachine

sturct StateMachine{    Vmapper     // node 到它的投票汇合的映射    vheight     // 最新的, 本人已投票的节点的高度, 等同于view number    b_lock      // 锁定的节点    b_exec      // 最初一个已执行的节点}

StateMachine的动作:

  • create_leaf()创立叶子节点
  • update(b*)更新节点b*及其父节点b'', b', b. 并且更新b_lock = b', 执行b
  • on_commit(b), 递归执行b
  • on_recv_proposal(b_new), 如果b_new.height比本人的vheight要高，而且满足SAFENODE()谓词, 就签名并且回复。随后更新b_new状态
  • on_recv_vote(), 计算门限签名和qc, 并且调用pacemaker.update_qc_height()
  • on_propose()， 创立叶子并且将其播送，随后返回叶子。

一次无故障的提交流程

  1. 首先下层app把新的cmd交付给hotstuff node。
  2. replica依据某种自定义形式生成proposal, 也就是node b_new。
  3. 在on_recv_new_view()中, replica把node发送给leader。
  4. leader.pacemaker挑选出最高的node, 调用on_beat()将其播送给所有replica。
  5. replica受到NewViewMSG后会调用on_recv_proposal(), 如果新node的高度更高而且满足SafeNode()谓词, 那么会返回本人的签名。无论是否承受新node, on_recv_proposal()都会调用update(b_new)。
  6. leader通过on_recv_vote()来计算门限签名, 调用pm.update_qc_high()来更新qc_high。
  7. replica期待b_new提交。这须要间断三个节点b <- b' <- b'', 如果b被提交了, 那么之前的节点也会提交。
  8. b_new被提交, 执行cmds。
  9. replica告知客户端cmds已执行。

其余

为何SAFENODE(b_new)为假也调用update(b_new)

update(b_new)并没有对b_new做任何动作。此时b_new处于Prepare阶段, 可能是个歹意的proposal。

但收到到b_new节点时, replica能够晓得, b_new的三个先人b, b', b''的别离进入了Decide, Commit, PreCommit阶段, 因而它做如下动作:

  1. 如果b'比已锁定的b_lock要更高(等价于viewNumebr更大), 那么锁定b'
  2. 如果b, b', b''三者间断, 那么递归提交b 及其之前的节点。

justify.node与parent的区别

联合下面能够看到, 实际上b, b', b''三者可能不间断:

 c1 <- b <- a1 <- a2 <- b' <- b1 <- b2 <- b''      _________________      __________// 所谓ancesty gap, leader超时导致进入下一个阶段

如上图: b''.justify.node == b', 而b''.parent == b2.
当on_commit(b'')时, 会顺次提交b1 <- b2 <- b''。

从执行过程来看: 创立新节点时会将pacemaker.qc_high作为新节点的justify, 那么qc_high何时更新? 通过以下路径调用pacemaker.update_qc_high()更新:

  • leader: on_recv_vote(), 计算出qc后得悉b_new曾经被承受了, 因而更新本人的。
  • replica: on_recv_proposal() -> update(b_new) -> update_qc_high(b_new.justify)。replica投给b_new了, 天然也就确认了b_new.justify。

pacemaker.qc_high与sm.vheight

这两个变量不是对应的。vheight在节点投票给b_new后更新为b_new.height. 一般来说qc_high.node.height <= vheight

参考资料

  1. hotstuff paper
  2. event-driven hotstuff in go
  3. https://zhuanlan.zhihu.com/p/...