比特币源码解析-数据结构-交易池

简介

当交易被广播并且被矿工接收到时，矿工就把交易加入到本地的交易池中，每个矿工又会对自己的交易池设置相应的限制，来保证交易数量不会过多，矿工在打包交易到区块中时，也会根据一定优先顺序来选择交易，从而获得尽量的交易费。

对于交易池主要介绍两个结构CTxMemPoolEntry和CTxMemPool，第一个是交易池中每一个元素的基本结构，第二个是整个交易池包含的所有信息。

文件名//txmempool.h

class CTxMemPoolEntry
class CTxMemPool

CTxMemPoolEntry

/** 
 * CTxMemPoolEntry stores data about the corresponding transaction, as well
 * as data about all in-mempool transactions that depend on the transaction
 * ("descendant" transactions).
 *
 * When a new entry is added to the mempool, we update the descendant state
 * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for
 * all ancestors of the newly added transaction.
 * --------------------------------------------
 * CTxMemPoolEntry是用于存储交易和该交易的所有子孙交易
 * 当一个新的entry添加到mempool中时，我们更新它的所有子孙状态和祖先状态
 */

class CTxMemPoolEntry
{
private:
    CTransactionRef tx;        // 交易引用 
    CAmount nFee;              // 交易费用 !< Cached to avoid expensive parent-transaction lookups
    size_t nTxWeight;          // 交易大小 !< ... and avoid recomputing tx weight (also used for GetTxSize())
    size_t nUsageSize;         // 内存使用大小 !< ... and total memory usage
    int64_t nTime;             // 时间戳 !< Local time when entering the mempool
    unsigned int entryHeight;  // 区块高度 !< Chain height when entering the mempool
    bool spendsCoinbase;       // 前一个交易是否是coinbase!< keep track of transactions that spend a coinbase
    int64_t sigOpCost;         // !< Total sigop cost
    int64_t feeDelta;          // 调整交易的优先级 !< Used for determining the priority of the transaction for mining in a block
    LockPoints lockPoints;     // 交易最后的所在区块高度和打包的时间 !< Track the height and time at which tx was final

    // Information about descendants of this transaction that are in the
    // mempool; if we remove this transaction we must remove all of these
    // descendants as well.
    // 子孙交易信息，如果我们移除一个交易，必须同时移除它的所有子孙交易
    uint64_t nCountWithDescendants;  //子孙交易的数量 !< number of descendant transactions
    uint64_t nSizeWithDescendants;   //自损交易的大小 !< ... and size
    CAmount nModFeesWithDescendants; //交易费用总和（包括当前交易）!< ... and total fees (all including us)

    // Analogous statistics for ancestor transactions
    // 祖先交易信息
    uint64_t nCountWithAncestors;
    uint64_t nSizeWithAncestors;
    CAmount nModFeesWithAncestors;
    int64_t nSigOpCostWithAncestors;

public:
    CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee,
                    int64_t _nTime, unsigned int _entryHeight,
                    bool spendsCoinbase,
                    int64_t nSigOpsCost, LockPoints lp);

    const CTransaction& GetTx() const { return *this->tx; }
    CTransactionRef GetSharedTx() const { return this->tx; }
    const CAmount& GetFee() const { return nFee; }
    size_t GetTxSize() const;
    size_t GetTxWeight() const { return nTxWeight; }
    int64_t GetTime() const { return nTime; }
    unsigned int GetHeight() const { return entryHeight; }
    int64_t GetSigOpCost() const { return sigOpCost; }
    int64_t GetModifiedFee() const { return nFee + feeDelta; }
    size_t DynamicMemoryUsage() const { return nUsageSize; }
    const LockPoints& GetLockPoints() const { return lockPoints; }

    // Adjusts the descendant state.
    // 更新子孙状态
    void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount);
    // Adjusts the ancestor state
    // 更新祖先状态
    void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps);
    // Updates the fee delta used for mining priority score, and the
    // modified fees with descendants.
    // 更新feeDelta, 并且修改子孙交易费用
    void UpdateFeeDelta(int64_t feeDelta);
    // Update the LockPoints after a reorg
    // 更新lockPoint
    void UpdateLockPoints(const LockPoints& lp);

    uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
    uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
    CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; }

    bool GetSpendsCoinbase() const { return spendsCoinbase; }

    uint64_t GetCountWithAncestors() const { return nCountWithAncestors; }
    uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
    CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
    int64_t GetSigOpCostWithAncestors() const { return nSigOpCostWithAncestors; }

    mutable size_t vTxHashesIdx; //!< Index in mempool's vTxHashes
};

CTxMemPool

/**
 * 交易内存池，保存所有在当前主链上有效的交易。
 * 当交易在网络上广播之后就会被加入交易池。
 * 但并不是所有的交易都会被加入，例如交易费太小的，或者“双花”的交易或者非标准交易。
 * 内存池中通过一个boost::multi_index类型的变量mapTx来排序所有的交易，
 * 按照以下四个标准：
 * - 交易Hash
 * - 交易费（包括所有的子孙交易）
 * - 在mempool（内存池）中的时间
 * - 挖矿分数
 * 为保证交易费的正确性，当新交易被加进mempool时，我们必须更新该交易的所有祖先交易信息，而这个操作可能会导致处理速度变慢，所以必须对更需祖先的数量进行限制。
 */
class CTxMemPool
{
private:
    uint32_t nCheckFrequency; //!< Value n means that n times in 2^32 we check. 内存检测 表示在2^32时间内检查的次数
    unsigned int nTransactionsUpdated; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation
    CBlockPolicyEstimator* minerPolicyEstimator;

    uint64_t totalTxSize;      //!< sum of all mempool tx's virtual sizes. Differs from serialized tx size since witness data is discounted. Defined in BIP 141.
                               // 内存中所有mempool中交易的虚拟大小，不包括见证数据

    uint64_t cachedInnerUsage; //!< sum of dynamic memory usage of all the map elements (NOT the maps themselves)
                               // map中元素使用的动态内存大小之和

    mutable int64_t lastRollingFeeUpdate;
    mutable bool blockSinceLastRollingFeeBump;
    mutable double rollingMinimumFeeRate; //!< minimum fee to get into the pool, decreases exponentially
                                          // 进入内存池pool需要的最小费用

    void trackPackageRemoved(const CFeeRate& rate);

public:

    static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing

    typedef boost::multi_index_container<
        CTxMemPoolEntry,
        boost::multi_index::indexed_by<
            // sorted by txid 根据交易哈希排序
            boost::multi_index::hashed_unique<mempoolentry_txid, SaltedTxidHasher>,
            // sorted by fee rate 根据交易费用排序
            boost::multi_index::ordered_non_unique<
                boost::multi_index::tag<descendant_score>,
                boost::multi_index::identity<CTxMemPoolEntry>,
                CompareTxMemPoolEntryByDescendantScore
            >,
            // sorted by entry time 根据进入交易池时间排序
            boost::multi_index::ordered_non_unique<
                boost::multi_index::tag<entry_time>,
                boost::multi_index::identity<CTxMemPoolEntry>,
                CompareTxMemPoolEntryByEntryTime
            >,
            // sorted by fee rate with ancestors 根据祖先交易费用排序
            boost::multi_index::ordered_non_unique<
                boost::multi_index::tag<ancestor_score>,
                boost::multi_index::identity<CTxMemPoolEntry>,
                CompareTxMemPoolEntryByAncestorFee
            >
        >
    > indexed_transaction_set;

    mutable CCriticalSection cs;
    indexed_transaction_set mapTx;

    typedef indexed_transaction_set::nth_index<0>::type::iterator txiter;
    std::vector<std::pair<uint256, txiter> > vTxHashes; //!< All tx witness hashes/entries in mapTx, in random order
                                                        // 所有交易见证数据的哈希
    struct CompareIteratorByHash {
        bool operator()(const txiter &a, const txiter &b) const {
            return a->GetTx().GetHash() < b->GetTx().GetHash();
        }
    };
    typedef std::set<txiter, CompareIteratorByHash> setEntries;

    const setEntries & GetMemPoolParents(txiter entry) const;
    const setEntries & GetMemPoolChildren(txiter entry) const;
private:
    typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap;

    struct TxLinks {
        setEntries parents;
        setEntries children;
    };

    typedef std::map<txiter, TxLinks, CompareIteratorByHash> txlinksMap;
    txlinksMap mapLinks;

    void UpdateParent(txiter entry, txiter parent, bool add);
    void UpdateChild(txiter entry, txiter child, bool add);

    std::vector<indexed_transaction_set::const_iterator> GetSortedDepthAndScore() const;

public:
    indirectmap<COutPoint, const CTransaction*> mapNextTx;
    std::map<uint256, CAmount> mapDeltas;

    /** Create a new CTxMemPool.
     *  创建新的交易池    
     */
    explicit CTxMemPool(CBlockPolicyEstimator* estimator = nullptr);

    /**
     * If sanity-checking is turned on, check makes sure the pool is
     * consistent (does not contain two transactions that spend the same inputs,
     * all inputs are in the mapNextTx array). If sanity-checking is turned off,
     * check does nothing.
     * 
     * 如果卡其了sanity-check, 那么check函数将会保证pool的一致性，
     * 即不包含双花交易，所有的输入都在mapNextTx数组中。
     * 如果关闭了sanity-check，那么check函数什么都不做
     */
    void check(const CCoinsViewCache *pcoins) const;
    void setSanityCheck(double dFrequency = 1.0) { nCheckFrequency = static_cast<uint32_t>(dFrequency * 4294967295.0); }

    // addUnchecked must updated state for all ancestors of a given transaction,
    // to track size/count of descendant transactions.  
    // addUnchecked()方法必须首先更新交易的祖先交易状态，     
    // First version of addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
    // then invoke the second version.
    // 第一个addUnchecked(...)函数用于调用 计算内存池祖先交易的方法-->CalculateMemPoolAncestors(),
    // 然后再调用第二个addUnchecked
    // Note that addUnchecked is ONLY called from ATMP outside of tests
    // and any other callers may break wallet's in-mempool tracking (due to
    // lack of CValidationInterface::TransactionAddedToMempool callbacks).
    bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool validFeeEstimate = true);
    bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate = true);

    void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN);
    void removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags);
    void removeConflicts(const CTransaction &tx);
    void removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight);

    void clear();
    void _clear(); //lock free 锁释放
    bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb);
    void queryHashes(std::vector<uint256>& vtxid);
    bool isSpent(const COutPoint& outpoint) const;
    unsigned int GetTransactionsUpdated() const;
    void AddTransactionsUpdated(unsigned int n);
    /**
     * Check that none of this transactions inputs are in the mempool, and thus
     * the tx is not dependent on other mempool transactions to be included in a block.
     * 检查交易输入是否在当前的内存池中，交易并非独立的包含区块的内存池交易中
     */
    bool HasNoInputsOf(const CTransaction& tx) const;

    /** Affect CreateNewBlock prioritisation of transactions */
    // 影响创建新的CreateNewBlock关于交易的优先级 
    void PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta);
    void ApplyDelta(const uint256 hash, CAmount &nFeeDelta) const;
    void ClearPrioritisation(const uint256 hash);

public:
    /** Remove a set of transactions from the mempool.
     *  If a transaction is in this set, then all in-mempool descendants must
     *  also be in the set, unless this transaction is being removed for being
     *  in a block.
     *  Set updateDescendants to true when removing a tx that was in a block, so
     *  that any in-mempool descendants have their ancestor state updated.
     *  ------------------------
     *  从mempool中移除一个交易集合
     *  如果一个交易在这个集合中，那么它的所有子孙交易都必须在集合中，
     *  除非该交易已经被打包到区块中。
     *  如果要移除一个已经被打包到区块中的交易
     *  那么要把updateDesendats设为true
     *  从而更新mempool中所有子孙节点的祖先消息
     */
    void RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN);

    /** When adding transactions from a disconnected block back to the mempool,
     *  new mempool entries may have children in the mempool (which is generally
     *  not the case when otherwise adding transactions).
     *  UpdateTransactionsFromBlock() will find child transactions and update the
     *  descendant state for each transaction in vHashesToUpdate (excluding any
     *  child transactions present in vHashesToUpdate, which are already accounted
     *  for).  Note: vHashesToUpdate should be the set of transactions from the
     *  disconnected block that have been accepted back into the mempool.
     * 
     *  从竞争失败的Block中更新交易信息到mempool
     */
    void UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate);

    /** Try to calculate all in-mempool ancestors of entry.
     *  (these are all calculated including the tx itself)
     *  limitAncestorCount = max number of ancestors
     *  limitAncestorSize = max size of ancestors
     *  limitDescendantCount = max number of descendants any ancestor can have
     *  limitDescendantSize = max size of descendants any ancestor can have
     *  errString = populated with error reason if any limits are hit
     *  fSearchForParents = whether to search a tx's vin for in-mempool parents, or
     *  look up parents from mapLinks. Must be true for entries not in the mempool
     *  
     *  计算mempool中所有的entry的祖先
     *  limitAncestorCount = 最大祖先数量
     *  limitAncestorSize  = 最大祖先交易大小
     *  limitDescendantCount = 任意祖先的最大子孙数量
     *  limitDescendantSize = 任意祖先的最大子孙大小
     *  errString = 超过了任务limit限制的错误提示
     *  fSearchForParents = 是否在mempool中搜索交易的输入
     *  或者从mapLinks中查找，对于不在mempool中的entry必须设为true
     */
    bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true) const;

    /** Populate setDescendants with all in-mempool descendants of hash.
     *  Assumes that setDescendants includes all in-mempool descendants of anything
     *  already in it.  */
    void CalculateDescendants(txiter it, setEntries& setDescendants) const;

    /** The minimum fee to get into the mempool, which may itself not be enough
      *  for larger-sized transactions.
      *  The incrementalRelayFee policy variable is used to bound the time it
      *  takes the fee rate to go back down all the way to 0. When the feerate
      *  would otherwise be half of this, it is set to 0 instead.
      *  ------
      *  进入内存池中的所需的最小交易费
      *  incremental变量用来限制freerate降到0所需的时间
      */
    CFeeRate GetMinFee(size_t sizelimit) const;

    /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
      *  pvNoSpendsRemaining, if set, will be populated with the list of outpoints
      *  which are not in mempool which no longer have any spends in this mempool.
      *  ----
      *  移除所有动态大小超过sizelimit的交易
      *  如果传入了pvNoSpendsRemaining, 那么将返回不在mempool中并且也无任何输出在mempool的交易列表
      */
    void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining=nullptr);

    /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
    //  移除所有在time之前的交易和它的子孙交易，然后返回移除数量
    int Expire(int64_t time);

    /** Returns false if the transaction is in the mempool and not within the chain limit specified. */
    //  如果交易在内存池中不满足the chain limit 将返回false
    bool TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const;

    unsigned long size()
    {
        LOCK(cs);
        return mapTx.size();
    }

    uint64_t GetTotalTxSize() const
    {
        LOCK(cs);
        return totalTxSize;
    }

    bool exists(uint256 hash) const
    {
        LOCK(cs);
        return (mapTx.count(hash) != 0);
    }

    CTransactionRef get(const uint256& hash) const;
    TxMempoolInfo info(const uint256& hash) const;
    std::vector<TxMempoolInfo> infoAll() const;

    size_t DynamicMemoryUsage() const;

    boost::signals2::signal<void (CTransactionRef)> NotifyEntryAdded;
    boost::signals2::signal<void (CTransactionRef, MemPoolRemovalReason)> NotifyEntryRemoved;

private:
    /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
     *  the descendants for a single transaction that has been added to the
     *  mempool but may have child transactions in the mempool, eg during a
     *  chain reorg.  setExclude is the set of descendant transactions in the
     *  mempool that must not be accounted for (because any descendants in
     *  setExclude were added to the mempool after the transaction being
     *  updated and hence their state is already reflected in the parent
     *  state).
     *
     *  cachedDescendants will be updated with the descendants of the transaction
     *  being updated, so that future invocations don't need to walk the
     *  same transaction again, if encountered in another transaction chain.
     *  
     *  用来更新被加入pool中的单个交易的子孙节点
     *  当子孙交易被更新时，cachedDescendants也同时被更新
     */
    void UpdateForDescendants(txiter updateIt,
            cacheMap &cachedDescendants,
            const std::set<uint256> &setExclude);
    /** Update ancestors of hash to add/remove it as a descendant transaction. */
    void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors);
    /** Set ancestor state for an entry */
    //设置一个entry的祖先
    void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors);
    /** For each transaction being removed, update ancestors and any direct children.
      * If updateDescendants is true, then also update in-mempool descendants'
      * ancestor state. */
    //对于每一个要移除的交易，更新他的祖先和他接的孩子        。
    //如果updateDescentdants设为true，那么同时更新mempool中子孙的祖先状态 
    void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants);
    /** Sever link between specified transaction and direct children. */
    void UpdateChildrenForRemoval(txiter entry);

    /** Before calling removeUnchecked for a given transaction,
     *  UpdateForRemoveFromMempool must be called on the entire (dependent) set
     *  of transactions being removed at the same time.  We use each
     *  CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
     *  given transaction that is removed, so we can't remove intermediate
     *  transactions in a chain before we've updated all the state for the
     *  removal.
     *  ---------
     *  对于一个特定的交易，调用removeUnchecked之前，
     *  必须为同时要移除的的交易集合调用UpdateForRemoveFromMempool。
     *  我们使用每个CTxMemPoolEntry中的setMemPoolParents来遍历要移除交易的祖先，
     *  这样能保证我们更新的正确性。
     */
    void removeUnchecked(txiter entry, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN);
};