交易打包是在addPackageTxs函数，在src/miner.cpp里。在解析它之前，先看一下它用到的重要数据结构。

//对交易池中每个交易进行再打包，用于计算包含祖先交易的费率，便于用来排序
struct CTxMemPoolModifiedEntry {
    //显式构造函数，参数只需要一个txiter，其实就是CTxMemPoolEntry
    explicit CTxMemPoolModifiedEntry(CTxMemPool::txiter entry)
    {
        iter = entry;
        nSizeWithAncestors = entry->GetSizeWithAncestors();
        nModFeesWithAncestors = entry->GetModFeesWithAncestors();
        nSigOpCostWithAncestors = entry->GetSigOpCostWithAncestors();
    }

    int64_t GetModifiedFee() const { return iter->GetModifiedFee(); }
    uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
    CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
    size_t GetTxSize() const { return iter->GetTxSize(); }
    const CTransaction& GetTx() const { return iter->GetTx(); }

    CTxMemPool::txiter iter;
    uint64_t nSizeWithAncestors;
    CAmount nModFeesWithAncestors;
    int64_t nSigOpCostWithAncestors;
};

接下来是几个辅助结构：

//第一个比较运算子，只是简单地比较内存地址，用来作索引
struct CompareCTxMemPoolIter {
    bool operator()(const CTxMemPool::txiter& a, const CTxMemPool::txiter& b) const
    {
        return &(*a) < &(*b);
    }
};

//用于提取交易（CTxMemPoolEntry）的运算子
struct modifiedentry_iter {
    typedef CTxMemPool::txiter result_type;
    result_type operator() (const CTxMemPoolModifiedEntry &entry) const
    {
        return entry.iter;
    }
};

//第二个比较运算子，比较的是包含祖先交易的费率（fee/size），如果相等，就比较交易Hash
//这里的祖先交易是指在交易池里还未被确认的
//这个运算子定义在txmempool.h里
class CompareTxMemPoolEntryByAncestorFee
{
public:
    template<typename T>
    bool operator()(const T& a, const T& b) const
    {
        double a_mod_fee, a_size, b_mod_fee, b_size;

        GetModFeeAndSize(a, a_mod_fee, a_size);
        GetModFeeAndSize(b, b_mod_fee, b_size);

        //变除为乘，小而管用的运算技巧
        double f1 = a_mod_fee * b_size;
        double f2 = a_size * b_mod_fee;

        if (f1 == f2) {
            return a.GetTx().GetHash() < b.GetTx().GetHash();
        }
        return f1 > f2;
    }

    //获取费率（fee/size），用于排序
    template <typename T>
    void GetModFeeAndSize(const T &a, double &mod_fee, double &size) const
    {
        //两种算法，取其小
        double f1 = (double)a.GetModifiedFee() * a.GetSizeWithAncestors();
        double f2 = (double)a.GetModFeesWithAncestors() * a.GetTxSize();

        if (f1 > f2) {
            mod_fee = a.GetModFeesWithAncestors();
            size = a.GetSizeWithAncestors();
        } else {
            mod_fee = a.GetModifiedFee();
            size = a.GetTxSize();
        }
    }
};

OK，可以引出交易打包使用的多重索引集合：

typedef boost::multi_index_container<
    CTxMemPoolModifiedEntry, //集合中的项目类型就是CTxMemPoolModifiedEntry
    boost::multi_index::indexed_by<
        boost::multi_index::ordered_unique<
            modifiedentry_iter,  //唯一性索引，基于内部的CTxMemPoolEntry
            CompareCTxMemPoolIter  //地址比较运算子
        >,
        //第二个索引，非唯一性，基于包含祖先交易的费率
        boost::multi_index::ordered_non_unique<
            //使用ancestor_score作为索引tag，它是一个空结构，定义在txmempool.h里
            boost::multi_index::tag<ancestor_score>,
            boost::multi_index::identity<CTxMemPoolModifiedEntry>,
            CompareTxMemPoolEntryByAncestorFee  //包含祖先交易的费率比较运算子
        >
    >
> indexed_modified_transaction_set;
//下面是两个迭代子，分别对应两个索引
typedef indexed_modified_transaction_set::nth_index<0>::type::iterator modtxiter;
typedef indexed_modified_transaction_set::index<ancestor_score>::type::iterator modtxscoreiter;

交易打包简要流程图

详细解析见以下源码和注释：

//交易选择算法：按照交易费率（包含未被确认的祖先交易）排序
//拟入块的交易需要更新其祖先、子孙相关信息，又不能影响交易池中原始信息，
//因此需要一个新的mapModifiedTx来存储处理过的交易信息
//打包过程中，不断从mapModifiedTx和mapTx中抽取费率最高的交易，
//选择其中费率更高的进行打包，并完成相关处理
void BlockAssembler::addPackageTxs(int &nPackagesSelected, int &nDescendantsUpdated)
{
    //mapModifiedTx存储是的待入块的交易，按照预定索引排序
    //并根据其祖先、子孙交易的入块情况，更新交易关联信息（大小、费率等）
    indexed_modified_transaction_set mapModifiedTx;
    //入块失败的交易存在这里，防止重复操作
    CTxMemPool::setEntries failedTx;

    //对已经入块的交易，其子孙交易加入mapModifiedTx。
    //若子孙交易已入块则不作处理，否则，减去已入块交易的Size、FeeRate等
    //inBlock是txiter的集合（setEntries），存储的是所有已入块的交易
    UpdatePackagesForAdded(inBlock, mapModifiedTx);

    //mi，MempoolItem，用来迭代整个交易池里的所有交易
    CTxMemPool::indexed_transaction_set::index<ancestor_score>::type::iterator mi = mempool.mapTx.get<ancestor_score>().begin();
    CTxMemPool::txiter iter;

    //限定区块将满时添加交易的尝试次数，确保在交易过多时及时结束打包过程
    const int64_t MAX_CONSECUTIVE_FAILURES = 1000;
    int64_t nConsecutiveFailed = 0;

    //按照包含祖先费率排序，逐个迭代交易
    while (mi != mempool.mapTx.get<ancestor_score>().end() || !mapModifiedTx.empty())
    {
        //如果已经在mapModifiedTx、inBlock或failedTx中，跳过去不处理
        if (mi != mempool.mapTx.get<ancestor_score>().end() &&
                SkipMapTxEntry(mempool.mapTx.project<0>(mi), mapModifiedTx, failedTx)) {
            ++mi;
            continue;
        }

        //下一个待处理的交易，是从mapTx选呢？还是从mapModifiedTx选？
        bool fUsingModified = false;

        modtxscoreiter modit = mapModifiedTx.get<ancestor_score>().begin();
        if (mi == mempool.mapTx.get<ancestor_score>().end()) {
            //mapTx已经空了，就从mapModifiedTx选
            iter = modit->iter;
            fUsingModified = true;
        } else {
            //没空的话，比较一下mapTx和mapModifiedTx的当前项
            iter = mempool.mapTx.project<0>(mi);
            if (modit != mapModifiedTx.get<ancestor_score>().end() &&
                    CompareTxMemPoolEntryByAncestorFee()(*modit, CTxMemPoolModifiedEntry(iter))) {
                //mapModifiedTx当前项费率更高，选它了
                iter = modit->iter;
                fUsingModified = true;
            } else {
                //mapModifiedTx空了，或者没有mapTx当前项费率高，就用mapTx的
                ++mi;
            }
        }

        //inBlock检查前面已经做过了，这里的iter肯定不在inBlock里
        assert(!inBlock.count(iter));

        uint64_t packageSize = iter->GetSizeWithAncestors();
        CAmount packageFees = iter->GetModFeesWithAncestors();
        int64_t packageSigOpsCost = iter->GetSigOpCostWithAncestors();
        if (fUsingModified) {
            packageSize = modit->nSizeWithAncestors;
            packageFees = modit->nModFeesWithAncestors;
            packageSigOpsCost = modit->nSigOpCostWithAncestors;
        }

        if (packageFees < blockMinFeeRate.GetFee(packageSize)) {
            //少于最低费用，退出
            return;
        }

        if (!TestPackage(packageSize, packageSigOpsCost)) {
            if (fUsingModified) {
                //TestPackage主要是检查区块大小有没有超标
                //如果超了，最后一个从mapModifiedTx选的，那么从中删掉它，移到failedTx里
                mapModifiedTx.get<ancestor_score>().erase(modit);
                failedTx.insert(iter);
            }

            ++nConsecutiveFailed;

            if (nConsecutiveFailed > MAX_CONSECUTIVE_FAILURES && nBlockWeight >
                    nBlockMaxWeight - 4000) {
                //最多重试次数到了，区块也快满了，退出循环
                break;
            }
            continue;
        }

        //找到iter的所有祖先
        CTxMemPool::setEntries ancestors;
        uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
        std::string dummy;
        mempool.CalculateMemPoolAncestors(*iter, ancestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
        //只需要未被确认的祖先，已入块的都去掉
        onlyUnconfirmed(ancestors);
        ancestors.insert(iter);

        //确认交易终结状态，包括锁定点和见证
        if (!TestPackageTransactions(ancestors)) {
            if (fUsingModified) {
                mapModifiedTx.get<ancestor_score>().erase(modit);
                failedTx.insert(iter);
            }
            continue;
        }

        //交易可以入块，重试次数清零
        nConsecutiveFailed = 0;

        //交易及其所有祖先，先排好序
        std::vector<CTxMemPool::txiter> sortedEntries;
        SortForBlock(ancestors, sortedEntries);
        //逐个入块，并从mapModifiedTx中删除
        for (size_t i=0; i<sortedEntries.size(); ++i) {
            AddToBlock(sortedEntries[i]);
            mapModifiedTx.erase(sortedEntries[i]);
        }

        ++nPackagesSelected;

        //所有已入块交易的子孙交易，更新相关信息
        nDescendantsUpdated += UpdatePackagesForAdded(ancestors, mapModifiedTx);
    }
}

OK，打包过程就是这样。下一节研究工作量证明（POW）。

欢迎转载，请注明出处。