ChainCluster 无大链 Trace 基线

English

概述

为评估 ChainCluster 优化在「无大 chain cluster」场景下的表现，我们生成了无大链 trace。该 trace 在原始 trace 基础上，通过添加额外的 ADD_DEP 边，消除了所有 size ≥ 3 的 chain-shaped cluster，仅保留 size=2 的 chain 和单例 cluster。

改写脚本仅消除 size≥3 的 chain，size=2 的 chain 被保留。因此 trace 中仍有数百个 size-2 chain cluster，chaincluster 分支仍能从中获益。

生成 trace 的步骤

1. 工具

使用脚本 contrib/txgraph_tracing/rewrite_trace_no_chain_clusters.py，位于 bitcoin/bitcoin chaincluster_time_mem_bench 分支。

2. 命令

# 单进程（默认）
python3 contrib/txgraph_tracing/rewrite_trace_no_chain_clusters.py \
  <input_trace> <output_trace>

# 多进程加速（推荐 15–20 核）
python3 contrib/txgraph_tracing/rewrite_trace_no_chain_clusters.py \
  --jobs 15 \
  <input_trace> <output_trace>

3. 改写策略

• size ≥ 3 的 chain cluster：添加 first → third 边（如 A→B→C 变为 A→B、A→C、B→C），打破链式结构
• size = 2 的 chain：保持不变

4. 本次生成结果

输入： 原始 trace（约 552 MB，1,763,516 个 commits）

输出： 改写后的 trace

额外 ADD_DEP 边数： 43,074

验证： python3 contrib/txgraph_tracing/analyze_trace.py <trace_file>

Cluster 分布（analyze_trace.py）

峰值状态（27,512 笔交易，8,582 个 cluster）

• Chain cluster 中的交易数： 8,770（31.9%）
• Non-chain cluster 中的交易数： 18,742（68.1%）

峰值要点

• 582 个 size-2 chain cluster（1,164 笔交易）仍在使用 ChainClusterImpl
• Size≥3 的 cluster 均为 non-chain（改写成功）

对比测试

对比脚本见 bitcoin/bitcoin chaincluster_time_mem_bench 分支。

命令

TXGRAPH_TRACE_FILE=/path/to/txgraph.trace.4.5days.final.nochain.copy \
  ./contrib/compare_before_vs_chaincluster.sh getmain

GetMainMemoryUsage（Cluster::TotalMemoryUsage）实测结果

GetMainMemoryUsage 基于 TxGraph 内部的 Cluster::TotalMemoryUsage，用于衡量 TxGraph 内存占用。测量方法详见 ChainCluster 内存对比：三种测量方法。

差异： chaincluster 少用 92,648 bytes（约 3.2%）。

时间性能实测结果

上表为各 entry point 的 CPU 时间求和（μs）。墙钟时间（整段 replay 的实际耗时，含 I/O 等）单独测量：Baseline 10 s，ChainCluster 10 s，差异 0 s（0%）。CPU 时间差异：chaincluster 快约 21%（TOTAL μs）。

分析

为何仍有约 21% CPU 时间提升？

改写脚本仅消除 size≥3 的 chain，size=2 的 chain 被保留。582 个 size-2 chain 在 chaincluster 分支中使用 ChainClusterImpl，获得：

1. O(N) 快速路径：相比 GenericClusterImpl 的 O(N²) 线性化
2. 更少内存：约 20 字节/交易 vs 约 40 字节/交易

DoWork、CommitStaging、IsOversized 等路径上均有明显加速。

无大链 trace 上的 GetMainMemoryUsage

在无大链 trace 上，chaincluster 的 TxGraph 内存（GetMainMemoryUsage）比 before_chaincluster 少约 3.2%。582 个 size-2 chain 受益于 ChainClusterImpl 的紧凑表示（约 20 字节/交易 vs 约 40 字节/交易）。

与原始 trace 的对比

原始 trace 峰值有 889 个 size≥2 的 chain cluster；无大链 trace 仅保留 582 个 size-2 chain。若进一步消除 size-2 chain，可得到「完全无 chain cluster」的基线。

总结

无大链 trace 通过 43,074 条额外 ADD_DEP 边消除了所有 size≥3 的 chain cluster，仅保留 582 个 size-2 chain。时间性能：chaincluster 的 CPU 时间快约 21%（墙钟相近）；GetMainMemoryUsage：chaincluster 少用约 3.2% 的 TxGraph 内存。size-2 chain 在时间和内存上均有收益。

测试环境

上述结果在测试机上测得。

硬件

宿主机系统

Docker 容器