在 11.9 号清迈的 CKCON 会议上我会做一个关于 CKB 交易池的演讲，这是我准备的 slides Key Upgrades of the CKB Core 。所以这段时间在整理之前做项目的时候写的一些文档，顺便分享到自己的博客上。既然我们整个项目的源码都是公开的，这些文档其实也是可以分享的。

第一次听说 CKB 的读者可以参考这个文档以了解什么是 CKB 以及如何工作的：How CKB Works | Nervos CKB。

我加入 Cryptape 之后一年内做的主要工作，涉及到交易池重构、Replace-by-fee 功能、以及 new-verify。这是第一篇关于交易池重构的文章。

什么是交易池

在 bitcoin 中交易池叫作 mempool，比如 mempool - Bitcoin Explorer 这个网站就很好地展示了其当前的状态。

交易池是 bitcoin 中的一个重要的组件，但感觉专门关于这块的资料很少，只能通过 PR 和邮件列表上的讨论看到一些文档。但交易池非常重要，因为一个交易要上链必须会通过交易池，而其中的交易打包算法涉及到如何选择合适的交易，这里面有很多因素需要考虑，所以在实现上也是比较复杂的。

当一个交易被提交到一个节点时，或者一个节点从网络中同步到交易时，这个交易首先需要被加入到交易池中，交易池里会根据一定的算法去选择下一个需要被打包的交易，另外交易池作为一个缓存，我们需要为其设置一个最大的 size。所以交易池里面最重要的两个操作就是 packaging 和 evicting。

交易池里面的交易存在父子关系，打包的时候需要从交易链的纬度去考虑，后面的 Replace by fee 这些功能也需要关注整个交易的所有子交易。

交易池重构

问题

根据 RFC consensus-protocol 的设计，CKB 里的 tx-pool 采用了两段提交的方式：

相应地在交易池最初实现的时候， ckb 的代码实现中 tx-pool 同样采用了三个独立的队列，具体定义如下：

• pending 交易刚加入到交易池时候的状态，我们每次只能处理不多于 MAX_BLOCK_PROPOSALS_LIMIT 个交易，交易需要先进入 gap 备选，具体代码逻辑在 update_proposals 。
• gap 已经被 proposed 了，但是还不能被打包，需要等一个块后才能被打包，所以这只是内部中间过渡状态。
• proposed 交易可以加入到 block_template.transactions , 最终打包到 block 里，具体代码逻辑在 block_assembler。

实现中 pending 和 gap 同样都是使用了 PendingQueue(LinkedHashMap)，而 proposed 采用了 SortedTxMap(HashMap + BTreeSet) ：

pub struct TxPool {    pub(crate) config: TxPoolConfig,    /// The short id that has not been proposed    pub(crate) pending: PendingQueue,    /// The proposal gap    pub(crate) gap: PendingQueue,    /// Tx pool that finely for commit    pub(crate) proposed: ProposedPool,    ....    pub(crate) expiry: u64,}

这样的实现存在以下问题：

• 我们不容易对所有在交易池中的 entry 做统一排序，这样会存在以下问题：

  • 一个 fee 高的交易可能在 transaction 多的情况下在 pending 阶段一直卡着，因为我们在 pending 和 gap 阶段只是按照时间顺序来处理，只在 proposed 后的打包阶段按照交易费来处理。
  • issue 3942 交易池满了之后，我们需要选择一些 entry 做 evict，我们目前的 evict 逻辑很简单粗暴。我们希望尽量选择最小 descendants...