Bitcoin Core 集群內(nèi)存池設(shè)計詳解線性化、費用率圖表與 RBF 的源碼級解析【免費下載鏈接】bitcoinBitcoin Core integration/staging tree項目地址: https://gitcode.com/GitHub_Trending/bi/bitcoin本文以 Bitcoin Core 的 mempool-design.md 設(shè)計文檔為核心完整講清算法側(cè)的集群內(nèi)存池cluster mempool體系如何把內(nèi)存池事務(wù)建模為有向圖、如何用線性化 塊chunk組織出最優(yōu)出塊順序、如何用費用率圖表feerate diagram統(tǒng)一驅(qū)動挖礦、淘汰與 RBF 替換判定。讀完后你將理解 v31.0 起 Bitcoin Core 內(nèi)存池策略的數(shù)學(xué)基礎(chǔ)并能對應(yīng)到TxGraph、cluster_linearize等源碼模塊中的具體實現(xiàn)。1. 內(nèi)存池的事務(wù)圖模型從 parent/child 到 cluster設(shè)計文檔首先給出的核心抽象是把內(nèi)存池中所有未確認交易視為一張有向圖directed graph。若交易 B 花費spend了交易 A 創(chuàng)建的輸出即存在一條從 B 指向 A 的邊——此時 B 是 A 的子交易childA 是 B 的父交易parent。在此之上文檔定義了遞歸擴展概念祖先ancestors遞歸地包含其父交易、父交易的父交易……即所有直接或間接為其出資確認前提的交易后代descendants遞歸地包含其子交易、子交易的子交易……集群cluster圖的連通分量即集合中任意兩個交易都可沿邊雙向互達。某個交易的集群由該交易、其祖先與后代、以及這些交易的祖先與后代遞推構(gòu)成——因此集群里不僅包含父子還包含祖孫、兄弟、遠房表親等一切相關(guān)交易。這一抽象在源碼中直接落地為TxGraph類src/txgraph.h。其頭文件注釋明確寫道圖內(nèi)的連通分量稱為 clusterwhenever one transaction is reachable from another, through any sequence of is-parent-of or is-child-of relations, they belong to the same cluster與文檔定義一一對應(yīng)。接口層提供了GetCluster()、GetAncestors()、GetDescendants()等函數(shù)src/txgraph.h#L139-L158并且設(shè)計上刻意兼容只存儲依賴傳遞閉包的實現(xiàn)——即若 B 花費 C它不區(qū)分A 花費 B和A 同時花費 B 與 C。底層數(shù)據(jù)結(jié)構(gòu)DepGraphsrc/cluster_linearize.h印證了這一點每個事務(wù)的 Entry 只保存三樣?xùn)|西——單個費用率、全部祖先集合、全部后代集合用位集生產(chǎn)實現(xiàn)為BitSet64見 src/txgraph.cpp#L110表示。直接父子關(guān)系并不顯式存儲而是通過GetReducedParents()/GetReducedChildren()從祖先/后代集合中推斷出來src/cluster_linearize.h#L211-L243。需要提醒的是文檔中所有size相關(guān)量都是策略術(shù)語vsize 指經(jīng) sigops 調(diào)整后的虛擬大小BIP 141 大小與 sigop 大小的最大值詳見同目錄的 mempool-terminology.md。2. 線性化與 chunk為整個集群構(gòu)造最優(yōu)出塊順序文檔的第二個核心概念是線性化linearization。每個集群cluster被排序成一個拓撲有效的順序topologically valid order即任何交易都不會出現(xiàn)在其祖先之前。目標是構(gòu)造這樣的線性化費用率最高的子集排在最前其次是剩余交易中費用率次高的子集依此類推。文檔把這類子集稱為chunk塊并指出一個關(guān)鍵性質(zhì)一個線性化中的 chunks 總是按單調(diào)遞減的費用率排列。這一算法在源碼中是SpanningForestStateSFLspanning-forest linearization實現(xiàn)于 src/cluster_linearize.h。其工作過程可以概括為初始所有依賴邊均為非激活狀態(tài)每個交易自成一塊反復(fù)在依賴邊上激活/去激活即合并/拆分 chunk直到狀態(tài)達到topological且optimal——optimal 的判據(jù)是不存在一條激活依賴其頂部 chunk 費用率嚴格高于底部 chunk 費用率。文檔注釋中給出了定理式結(jié)論whenever the state is optimal, the produced linearization will also be optimal (in the convexified feerate diagram sense)即狀態(tài)最優(yōu)可證明輸出線性化在凸化費用率圖表意義下最優(yōu)若仍有預(yù)算進一步把等費用率的 chunk 拆分為最小成分minimal state最終按費用率從高到低輸出各 chunkchunk 內(nèi)部按拓撲序排列。整個過程受成本模型約束SFLDefaultCostModelsrc/cluster_linearize.h#L476-L545為每個操作建立了基于 2026 年 2 月多機基準測試擬合的整數(shù)成本表達式每個成本單位約合 0.52.5 納秒對應(yīng)TxGraph構(gòu)造參數(shù)中的acceptable_cost——決定每個集群最多投入多少優(yōu)化算力best effort only, not a strong guarantee見 src/txgraph.h#L20-L46 的類注釋。chunk 的計算本身非常簡潔見ChunkLinearization()src/cluster_linearize.h#L446-L464沿線性化逐個處理交易只要新交易與已吸收部分的合并費用率仍高于上一個 chunk就把它吸收進來從而保證 chunk 費用率序列嚴格單調(diào)遞減。文檔還指出跨集群的合并方式給定兩個或多個已線性化的集群把各自按費用率排好的 chunks 做歸并排序merge sort即得到并集上線性化。這與TxGraph::GetMainStagingDiagrams()注釋中the combined respective feerate diagrams, including chunks from all clusterssrc/txgraph.h#L169-L173的語義一致——全內(nèi)存池的線性化天然由所有集群的 chunks 歸并而成。3. 費用率圖表比較兩個線性化的統(tǒng)一標尺文檔定義了費用率圖表feerate diagram以累計大小cumulative size為橫軸、累計費用cumulative fee為縱軸沿 chunk 逐塊推進繪制出的折線圖。它是比較兩個線性化優(yōu)劣的統(tǒng)一工具文檔給出三種比較結(jié)論不可比incomparable兩者互不包含——存在某些尺寸點 A 的累計費用更高也存在其他尺寸點 B 更高等價equivalent在所有尺寸點上累計費用完全相同嚴格更優(yōu)strictly better可比且至少存在一個尺寸點其中一方累計費用嚴格更高。這個比較在實現(xiàn)上就是CompareChunks()基于FeeFrac精確的分數(shù)型費用率表示src/util/feefrac.h實現(xiàn)避免浮點誤差干擾策略判定。測試 src/test/rbf_tests.cpp#L489-L497 顯式驗證了三種結(jié)論std::is_lt、std::is_gt與std::partial_ordering::unordered對應(yīng)不可比。文檔最后給出的理論注腳值得保留這一目標本質(zhì)上是**最大比率閉包問題maximal-ratio closure problem**的一個實例與露天礦開采open pit mining領(lǐng)域的最大權(quán)閉包問題密切相關(guān)——這也解釋了 SFL 算法中top/bottom頂部/底部術(shù)語的由來。4. 挖礦與淘汰線性化同一張表的頭尾兩端文檔Mining/eviction一節(jié)說明了線性化的兩大用途區(qū)塊構(gòu)建mining構(gòu)造區(qū)塊模板時從線性化前端依次選取 chunks內(nèi)存池淘汰eviction需要為內(nèi)存池騰出空間時從線性化后端逐塊淘汰。即同一份按費用率降序的 chunks 序列頭端喂給出塊尾端喂給淘汰兩者互為鏡像。源碼中這兩個方向各有一個入口出塊端TxGraph::GetBlockBuilder()返回一個BlockBuilder迭代器通過GetCurrentChunk()取當(dāng)前建議納入的 chunk 及其費用率Include()/Skip()前進src/txgraph.h#L180-L201。注意Skip()的語義Further chunks from the same cluster as the current one will not be reported anymore——跳過某 chunk 后同集群的后續(xù) chunk 不再報告保證拓撲一致性。礦工側(cè)調(diào)用點在 src/node/miner.cpp#L302 的GetBlockBuilderChunk()。淘汰端GetWorstMainChunk()返回主圖中最后一個 chunk 及其費用率src/txgraph.h#L202-L206且特意以逆拓撲序返回每個交易排在所有其后代之前保證直接刪除這批交易不會留下懸掛的依賴鏈。5. Replace-by-fee用費用率圖表取代簡單費用規(guī)則文檔的 RBF 一節(jié)指出了一個歷史缺陷在集群內(nèi)存池實現(xiàn)之前替換replacement判定存在兩類錯誤——即使替換會讓內(nèi)存池對礦工更有利也可能被拒絕反之新交易比被替換交易更不受礦工歡迎時替換卻可能被放行。集群內(nèi)存池帶來了更嚴格的判據(jù)比較替換前后整個內(nèi)存池的費用率圖表僅當(dāng)替換使圖表嚴格更優(yōu)strictly better時才接受。文檔給出直觀解釋簡單情形下替換交易的費用率和費用都應(yīng)當(dāng)高于被替換交易但當(dāng)某些交易存在未確認父交易時不存在一個可以簡單描述的必須支付多少費用才能成功替換一組交易的公式唯一的判據(jù)就是結(jié)果內(nèi)存池的費用率圖表在某個尺寸點變好且在任何尺寸點都不變差。源碼中這條路徑清晰可查ImprovesFeerateDiagram()src/policy/rbf.cpp#L127-L140對變更集changeset計算替換前后兩個 chunk 序列再用CompareChunks()斷言新圖表std::is_gt舊圖表否則拒絕并返回 insufficient feerate: does not improve feerate diagram該比較依賴TxGraph的staging 圖機制StartStaging()建立一份主圖的工作副本在副本上施加替換后調(diào)用GetMainStagingDiagrams()取回兩份圖表且自動剔除兩邊完全相同的集群因為不影響比較結(jié)果判定失敗則AbortStaging()丟棄、成功則CommitStaging()src/txgraph.h#L109-L120此外仍有傳統(tǒng) BIP 125 規(guī)則并行生效替換交易必須支付不低于原交易的費用且新增費用必須按增量中繼費incremental relay feerate覆蓋其自身帶寬PaysForRBF()src/policy/rbf.cpp#L100-L125以及影響范圍上限MAX_REPLACEMENT_CANDIDATES{100}個獨立集群src/policy/rbf.h#L24-L26。完整的 RBF 替換規(guī)則文檔見 mempool-replacements.md。6. 內(nèi)存池限制為什么必須約束集群規(guī)模文檔Mempool limits一節(jié)給出了兩方面的動機兩者共同指向限制集群從而限制 chunk的最大規(guī)模接近最優(yōu)的區(qū)塊構(gòu)建需要小 chunk。按費用率降序選取 chunk 構(gòu)建區(qū)塊模板時只有當(dāng)任意 chunk 的最大尺寸遠小于區(qū)塊大小貪心選取才接近最優(yōu)。若單個 chunk 過大可能因裝不下而浪費區(qū)塊空間避免淘汰的級聯(lián)效應(yīng)。內(nèi)存池淘汰時不希望因為一筆可能很小的新交易越過尺寸上限就一次性驅(qū)逐大量無關(guān)交易——限制集群規(guī)模能兜住這種尾部風(fēng)險計算復(fù)雜度約束。對某交易做線性化所需的計算量隨集群內(nèi)交易數(shù)多項式增長只有限制集群交易數(shù)才能保證在合理時間內(nèi)找到良好理想情況下最優(yōu)的線性化。由此得出的硬性規(guī)則是文檔給出的最重要可驗證事實之一提交到內(nèi)存池的交易不得使任何集群超過集群上限每集群最多 64 筆交易、總計最多 101 kvB。這兩個數(shù)字在源碼中有多處一致定義可以逐一核驗常數(shù)值定義位置DEFAULT_CLUSTER_LIMIT64默認集群交易數(shù)上限src/policy/policy.h#L72DEFAULT_CLUSTER_SIZE_LIMIT_KVB101默認集群大小上限kvBsrc/policy/policy.h#L74MAX_CLUSTER_COUNT_LIMIT64允許的硬上限BitSet位集尺寸也由此決定src/txgraph.h#L18mempool_limits結(jié)構(gòu)cluster_count{DEFAULT_CLUSTER_LIMIT}、cluster_size_vbytes{DEFAULT_CLUSTER_SIZE_LIMIT_KVB * 1000}src/kernel/mempool_limits.h#L20-L22運行節(jié)點上可以用getmempoolinfoRPC 觀察當(dāng)前生效的limitclustersizesrc/rpc/mempool.cpp#L1093。調(diào)試參數(shù)-limitclustercountn允許調(diào)小計數(shù)上限默認 64最大 64DEBUG_ONLY 類別在 src/init.cpp#L690 注冊、在 src/node/mempool_args.cpp#L110-L111 校驗不得超過MAX_CLUSTER_COUNT_LIMIT——注意該上限是硬性的不能通過參數(shù)放大超過 64因為TxGraph的位集實現(xiàn)以 64 為容量。當(dāng)超限發(fā)生時TxGraph會進入oversized狀態(tài)多數(shù)查詢接口對 oversized 圖不可用但所有 mutator 始終可用且Trim()會按快速盡力策略移除交易含其后代直到恢復(fù)滿足集群限制src/txgraph.h#L122-L178。7. 相關(guān)背景與延伸閱讀文檔末尾的 References/Notes 給出了兩條線索一是該實現(xiàn)自v31.0起隨 cluster mempool 方案PR#33629合入二是費用率圖表在挖礦、淘汰與替換判定三處的統(tǒng)一使用原理。在倉庫內(nèi)理解本文時可沿以下路徑繼續(xù)深入src/txgraph.h 與 src/txgraph.cpp內(nèi)存池事務(wù)圖的完整接口與實現(xiàn)包括 main/staging 雙層圖、chunk 劃分保證與BlockBuildersrc/cluster_linearize.hSFL 線性化算法全文含大段算法性質(zhì)證明式注釋以及DepGraph傳遞閉包結(jié)構(gòu)src/txmempool.h / src/txmempool.cpp內(nèi)存池主體如何持有m_txgraph并把它接入選入、淘汰與 RBF 流程src/test/cluster_linearize_tests.cpp、src/test/txgraph_tests.cpp、src/test/rbf_tests.cpp線性化最優(yōu)性、TxGraph 行為與圖表比較的單元測試src/test/fuzz/txgraph.cpp 用隨機模擬圖對TxGraph全部接口做等價性 fuzzsrc/bench/txgraph.cppTxGraph 基準測試可觀察線性化在 64 交易、100000 vB 集群規(guī)模下的實際開銷mempool-terminology.md 與 packages.md費用/大小術(shù)語約定以及 package 提交如何與集群限制共存例如static_assert(DEFAULT_CLUSTER_LIMIT MAX_PACKAGE_COUNT)保證單個 package 永遠不會撐爆集群見 src/policy/packages.h#L29。8. 小結(jié)集群內(nèi)存池設(shè)計把內(nèi)存池該怎么排從一堆啟發(fā)式規(guī)則收斂為一張統(tǒng)一的數(shù)學(xué)對象——按費用率單調(diào)遞減分塊、跨集群歸并的全局線性化。它同時回答了三個問題礦工從頭部拿 chunk 出塊、節(jié)點從尾部丟 chunk 淘汰、RBF 用前后兩張費用率圖表的嚴格優(yōu)劣比較決定替換成敗。而64 筆 / 101 kvB的集群限制則是讓整個體系在時間復(fù)雜度與出塊質(zhì)量上都可控的工程護欄。這套機制自 v31.0 起成為 Bitcoin Core 內(nèi)存池策略的骨架理解它即理解當(dāng)前版本交易中繼、出塊與替換行為的第一性原理?！久赓M下載鏈接】bitcoinBitcoin Core integration/staging tree項目地址: https://gitcode.com/GitHub_Trending/bi/bitcoin創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考