作者：明神特烦恼
公众号：明神特烦恼

交易池，一般称为mempool、txpool，用于缓存交易信息、为共识模块提供交易集输入。

带着问题读代码：
1）传入的交易请求结构是什么，交易池是否会补充参数？
2）交易入池前检查有哪些？
3）存储大量交易的数据结构是什么，是map 还是 链表 ？
4）交易池支持的索引是什么，是否支持根据txid检索交易信息？还有哪些检索条件？
5）提供给共识模块的交易集合如何选择？
6）何时增加交易、清除交易？

（这里分析batch类型，不分析single）

第一个问题：传入的交易请求结构是什么，交易池是否会补充参数？

1）问题延续

    很多的区块链系统会考虑在交易请求过来后，会补充时间戳参数、txid参数等。区块链系统一般不会相信客户端发送过来的交易时间参数，因为客户端是有可能被篡改的。txid的生成方式不一定，要根据具体设计，一般采用随机数 or 交易内容hash 方式生成。
    一般的区块链系统中交易结构包括：合约所属链ID、合约名称、交易类型、调用方式、输入参数。

2）长安链请求参数

type TxRequest struct {
    // header of the request
    Header *TxHeader `protobuf:"bytes,1,opt,name=header,proto3" json:"header,omitempty"`
    // payload of the request, can be unmarshalled according to tx_type in header
    Payload []byte `protobuf:"bytes,2,opt,name=payload,proto3" json:"payload,omitempty"`
    // signature of [header bytes || payload bytes]
    Signature []byte `protobuf:"bytes,3,opt,name=signature,proto3" json:"signature,omitempty"`
}

// header of the request
type TxHeader struct {
    // blockchain identifier
    ChainId string `protobuf:"bytes,1,opt,name=chain_id,json=chainId,proto3" json:"chain_id,omitempty"`
    // sender identifier
    Sender *accesscontrol.SerializedMember `protobuf:"bytes,2,opt,name=sender,proto3" json:"sender,omitempty"`
    // transaction type
    TxType TxType `protobuf:"varint,3,opt,name=tx_type,json=txType,proto3,enum=common.TxType" json:"tx_type,omitempty"`
    // transaction id set by sender, should be unique
    TxId string `protobuf:"bytes,4,opt,name=tx_id,json=txId,proto3" json:"tx_id,omitempty"`
    // transaction timestamp, in unix timestamp format, seconds
    Timestamp int64 `protobuf:"varint,5,opt,name=timestamp,proto3" json:"timestamp,omitempty"`
    // expiration timestamp in unix timestamp format
    // after that the transaction is invalid if it is not included in block yet
    ExpirationTime int64 `protobuf:"varint,6,opt,name=expiration_time,json=expirationTime,proto3" json:"expiration_time,omitempty"`
}

结论：发现在交易池中并未有如何参数补充！！！

为了证实该结论：打开go sdk代码，查看客户端发送时封装的交易字段。发现确实客户端填充所有字段。

// 构造Header
    header := &common.TxHeader{
        ChainId:        cc.chainId,
        Sender:         sender,
        TxType:         txType,
        TxId:           txId,
        Timestamp:      time.Now().Unix(),
        ExpirationTime: 0,
    }

此处留下思考点一：由于客户端传入Timestamp参数，如果交易时间填入未来的一个时间，会有何影响。（在入池前校验时会阐述）

第二个问题：交易入池前检查有哪些？

1）问题延续

    一般的区块链系统会做的校验：数据格式、txid冲突、发送者身份验证、链与合约是否存在......

2）长安链入池前检测

    数据格式校验：Txid长度及格式验证、时间戳正确性验证、发送者身份字段是否为空值验证等。
    权限验证：根据访问策略判断该发送者是否有权限发送该交易。
    交易池满：长安链处理机制，会定时将txQueue中的交易打包成batch供共识模块使用，如果交易发送tps过高，在未生成batch时txQueue 已经到达maxTxCount 上限会报错。
    交易过期验证：TxHeader.Timestamp是否超过一定范围，如果时间过早或者过晚返回错误。（解决思考点一）

    txTimestamp := tx.Header.Timestamp
    chainTime := utils.CurrentTimeSeconds()
    if math.Abs(float64(chainTime-txTimestamp)) > poolconf.MaxTxTimeTimeout(p.chainConf) {
        p.log.Errorw("the txId timestamp is error", "txId", tx.Header.GetTxId(), "txTimestamp", txTimestamp, "chainTimestamp", chainTime)
        return commonErrors.ErrTxTimeout
    }

    Txid是否存在于其他Batch中：交易队列每个一段时间将交易集合打包成batch，供共识模块使用。如果该Txid已存在于其他Batch中，则返回错误。
    Txid是否存在于数据库（已落块）: 如果该Txid已经落块，则返回错误。

此处留下思考点二：如果同一批次中有冲突的Txid如何处理。

第三个问题：存储大量交易的数据结构是什么，是map 还是 链表 ？

• 长安链交易信息分为两类：普通交易信息、配置交易信息，区别：配置交易优先打包为Batch，一笔交易构成一个Batch。
• 长安链从数据结构上分为两类：交易缓存（txQueue）、Batch缓存（commonBatchPool），其中txQueue数据结构为无锁队列， commonBatchPool数据结构为排序map。这两个数据结构后续单独分析，目前可当做黑盒模块。
• 每隔500毫秒 会从队列中拉取一批交易生成batch，存储到commonBatchPool中。在转化为batch中涉及关键流程：

for i := 0; i < int(p.batchMaxSize); {
        if val, ok, _ := p.txQueue.Pull(); ok {
            tx := val.(*commonPb.Transaction)
            if _, ok := txIdToIndex[tx.GetHeader().GetTxId()]; ok {
                continue
            }
            txs = append(txs, tx)
            txIdToIndex[tx.GetHeader().GetTxId()] = int32(i)
            i++
            continue
        }
        select {
        case <-timer.C:
            return txs, txIdToIndex
        default:
            time.Sleep(10 * time.Millisecond)
        }
    }

    也就是说 同一批次中的交易集合如果有txid冲突会直接过滤掉，不会出现同一个batch txid冲突的情况。解决思考点二的问题。

此处留下思考点三：如果这笔交易如此方式丢失，那么客户端无法知晓、底层平台无法知晓，是否考虑将其扔到event处理模块，或者简单打一条日志，防止无法追踪。

第四个问题：交易池支持的索引是什么，是否支持根据txid检索交易信息？还有哪些检索条件？

• 长安链数据结构：batchTxIdRecorder为有锁map，Key：batchid Value:map<txid, txIndex>
• 在入池前检测章节中提到会检测Txid是否存在于其他Batch中，检测方式通过batchTxIdRecorder数据结构进行遍历判断txid是否存在。

此处留下思考点四：batchTxIdRecorder 用于txid检测，每次需要遍历Map，可否可以创建txid 与batchid的对应关系？

第五个问题：提供给共识模块的交易集合如何选择？

• 提案者要求获取交易集合
• 交易池从有序mapcommonBatchPool中获取一个批次交易，将其从commonBatchPool移除，放入pendingBatchPool中，pendingBatchPool数据结构为有锁map，Key：batchid Value：TxBatch。

第六个问题：何时增加交易、清除交易？

经过上面的分析、学习，该问题需要被丰富，修改问题如下：

第六个问题：txQueue、commonBatchPool、batchTxIdRecorder、pendingPool何时增加、何时删除？

txQueue：

• add：通过rpc接口接收客户端交易。
• delete：定时任务将txQueue交易打包成Batch。

commonBatchPool：

• add：定时任务将txQueue交易打包成Batch；其他节点广播的Batch；生成新区块时为进行调度生成读写集的交易；从交易池获取的交易数量超过一次共识的交易最大值；构造Block发生错误等。
• delete：将Batch发送给共识模块；写块完成时；自己的提案块并没有被接受，处理其他提案块时，此处留下思考点五，自己提案的块没有被接受，为啥不直接将交易batch放回commonBatchPool；提案时batch内容都无效。

pendingPool：

• add: 将Batch发送给共识模块。
• delete: 与commonBatchPool delete时机一致。

batchTxIdRecorder：

• add: 与commonBatchPool add时机一致;与pendingPool delete时机一致。

    对于思考点四，不是逻辑问题，是如何优化执行更加高效，没有进行大量压力测试的人没有发言权，相信技术团队已经充分考虑及实践。

交易池工作流程图

官方参考：chainmaker-go/module/txpool/images

PS：流程设计图与代码仓库绑定是比较好的方式，随着代码的更替，设计图可能也会改变，通过代码版本进行管理比较方便且一致。
本来想画一个流程图，发现官方有设计图，偷偷地See过来。

chainmaker-txpool-flow.png

对比实现

    俗话说得好，没有对比就没有伤害。这里我们来分析一下diem的实现方式，这个名字可能会比较陌生，他还有个曾用名叫Libra。本来想找fabric作对比，fabric整体设计将背书、提案等流程分离，不好做对比，因此选择diem。
    diem交易池数据结构主要集中在TransactionStore
    - transactionsHashMap，结构为Key：账户地址，Value：Map<seqNo，交易信息>，交易唯一标识可以使用账户地址 + seqNo标识
    - priority_indexBTree，排序的内容可直接指向transactions, 交易原始数据在transactions，排序工作交给priority_index，排序方式按照交易先来后到
    - expiration_time_indexBTree，排序的内容可直接指向transactions, 交易原始数据在transactions，时间维度索引在expiration_time_index。diem 会定期调用mempool的gc函数，来清理已经过期的交易。

pub(crate) fn new(config: &MempoolConfig) -> Self {
        Self {
            // main DS
            transactions: HashMap::new(),

            // various indexes
            system_ttl_index: TTLIndex::new(Box::new(|t: &MempoolTransaction| t.expiration_time)),
            expiration_time_index: TTLIndex::new(Box::new(|t: &MempoolTransaction| {
                Duration::from_secs(t.txn.expiration_timestamp_secs())
            })),
            priority_index: PriorityIndex::new(),
            timeline_index: TimelineIndex::new(),
            parking_lot_index: ParkingLotIndex::new(),

            // configuration
            capacity: config.capacity,
            capacity_per_user: config.capacity_per_user,
        }
    }

   通过对比diem发现几点不同：
   1）两者虽然每笔交易都有过期时间，但使用方式不同。长安链作为交易准入依据，只要进去区块链系统就OK。diem是会在共识前进行持续监测。
   2）存储元信息的数据结构不同，长安链使用txQueue，是一个无锁并发map，不支持检索（因为检索工作在batch），只进行排序。diem使用BTree 排序 + 根据Txid进行检索。还是那句话，没有进行大量压力测试的人没有发言权。

    至此交易池整理流程、数据结构等已经分析完毕，交易池功能不复杂，更多的是效率上的考量。下一小节将分析txQueue、commonBatchPool的数据结构。