jemalloc Profiling 采样与去偏原理深度剖析：无偏估计、方差分析与 jeprof 兼容实现

导读

本文以 placeholderkv（Valkey）仓库中内嵌的 jemalloc 依赖文档 PROFILING_INTERNALS.md 为骨架，系统讲解 jemalloc 堆剖析（heap profiling）背后的数学原理与工程实现：为什么采样是无偏的、如何用方差评估不同采样策略、为什么最终选择按字节（per-byte）采样，以及 jeprof 输出为何"输入是错的、输出是对的"。读完本文，你将理解 heap dump 中每个数字的真实含义，掌握"先逐样本去偏、再聚合"的正确数据分析姿势，并能通过源码验证 jemalloc 的几何分布采样、lg_prof_sample 配置项与 prof_unbias_map_init() 去偏映射的实现细节。

一、背景：为什么需要采样

在 placeholderkv 这类高吞吐的键值数据库上，jemalloc 承担全部内存分配路径。启用 heap profiling 时，每一次被剖析的分配都需要：

1. 回溯调用栈（walk the stack）拿到 stack trace；
2. 分配存储记录该 stack trace；
3. 把记录挂到某个"profile dump 时能找到"的位置——而 dump 可能发生在另一个线程上，因此通常还要加锁。

这些开销与一次分配的平均成本相比非常可观。因此 jemalloc 只对一部分分配采样，接受数据不完整，再用数学手段"补回来"：采样率可以在精度与性能之间权衡，这即是 PROFILING_INTERNALS.md 中"Sampling"一节的出发点。

二、实现工具箱中的三个技巧

2.1 快速伯努利采样：用几何分布代替逐次抛硬币

即使只是一个 coinflip(p) 函数，相对 jemalloc 的快速路径而言也相当昂贵——它需要随机数生成和浮点运算。文档引用了 Vitter (1987) 的思路：如果大量 coinflip 共享同一个参数值，就可以一次随机数生成换取多次抛硬币。

具体做法是：从几何分布中采样，把结果初始化成一个计数器；计数器每次分配递减，减到 0 时 coinflip 返回 true 并重新初始化内部计数器。这样随机数生成次数从"每次逻辑抛硬币一次"降为"每次命中（heads）一次"。由于采样预期很稀疏，这是很大的收益。

源码级验证位于 src/prof.c 的 prof_sample_new_event_wait()：

/*
 * Compute sample interval as a geometrically distributed random
 * variable with mean (2^lg_prof_sample).
 *
 *                      __        __
 *                      |  log(u)  |                     1
 * bytes_until_sample = | -------- |, where p = ---------------
 *                      | log(1-p) |             lg_prof_sample
 *                                              2
 */
uint64_t r = prng_lg_range_u64(tsd_prng_statep_get(tsd), 53);
double u = (r == 0U) ? 1.0 : (double)r * (1.0/9007199254740992.0L);
return (uint64_t)(log(u) /
    log(1.0 - (1.0 / (double)((uint64_t)1U << lg_prof_sample))))
    + (uint64_t)1U;

这里 bytes_until_sample（距下次采样的字节数）即服从参数 p = 1 / 2^lg_prof_sample 的几何分布，平均值为 2^lg_prof_sample。实现细节也很讲究：随机数 r 可能恰好为 0，为避免 log(0)，把 u 置为 1.0，使 u 均匀分布于 (0, 1]；并且用"取 floor 后加 1"代替取 ceiling，防止 u = 1.0 时 bytes_until_sample 变成 0。此外 prof_sample_postponed_event_wait()（src/prof.c）在推迟采样时仍按全新等待时间计算，注释明确指出：若直接推迟到下一次分配，当紧跟重入（reentrancy）的分配总是来自同一调用栈时会产生采样偏差。

2.2 快速路径 / 慢速路径思维

大多数程序的分配呈偏斜分布：小分配数量远多于大分配，但更短命、占堆内存比例更低。文档给出的观察是：

• 如果把"小"定义为"jemalloc 放入 slab 的分配"，"大"定义为其余分配，小分配的出现频率常是大分配的数百倍，但二者占用的堆空间大约各半；
• 小分配通常便宜得多（常便宜 20~30 倍）：更容易命中线程缓存（thread caches）、更少触发 mmap、用户填充也更便宜。

这一"快速路径/慢速路径"的动力学，是后文选择 per-byte 采样策略的核心论据。

三、无偏空间占用估计：一个（几乎）通用的框架

文档给出了一个关键结论：只要采样策略满足两个条件——

1. 一个分配是否被采样，与其他分配是否被采样相互独立；
2. 每个分配都有非零的采样概率；

那么某个调用栈的存活分配占用字节数就可以被如下无偏估计：

$$\sum_i S_i I_i \frac{1}{\mathrm{E}[I_i]}$$

其中下标遍历该栈的所有存活分配，$S_i$ 是第 $i$ 个分配的大小，$I_i$ 是该分配是否被采样的示性随机变量。由于 $S_i$ 与 $\mathrm{E}[I_i]$ 都是常数（程序分配是固定的，随机的是采样决策），取期望后得到 $\sum_i S_i$，正是我们想要的值。对"分配次数"的统计也可以做类似推导。

这个框架的通用性值得强调：它只要求采样决策之间独立，并不要求它们独立于之前的分配、总字节数等。因此以下看似"花哨"的策略都能装进该框架得到无偏估计：

• 程序启动阶段以高于后续分配的速率采样；
• 偶数下标分配比奇数下标采样更频繁（只要没有任何分配采样概率为 0）；
• 允许线程声明"高采样优先级"并以更高速率采样。

四、评估采样策略：方差才是关键

并非所有采样策略都同样好。在无偏估计器之间，方差越小，均方误差（MSE）越低。对上述估计器做方差分解：

$$\mathrm{Var}\left[\sum_i S_i I_i \frac{1}{\mathrm{E}[I_i]}\right] = \sum_i S_i^2 \frac{1 - \mathrm{E}[I_i]}{\mathrm{E}[I_i]}$$

（推导中利用了 $I_i$ 为伯努利变量、$\mathrm{Var}[I_i] = \mathrm{E}I_i$，以及独立性假设消去交叉项。）这一公式是后续比较两种候选策略的标尺：在其余条件相同的前提下，方差越低的策略越好。

五、两种候选采样策略的数学对比

出于避免快速路径开销的考虑，jemalloc 倾向于使用第二节的"伯努利-几何"技巧，候选计数器有两个：每次分配抛一次硬币，或每字节抛一次硬币。

5.1 按分配采样（per-allocation）

选定一个大数 $N$，每个分配以 $1/N$ 概率被采样。套用方差公式：

$$\sum_i S_i^2 \frac{1 - \frac{1}{N}}{\frac{1}{N}} = (N-1) \sum_i S_i^2$$

即一个大小为 $Z$ 的分配向方差贡献 $(N-1)Z^2$。方差随大小呈二次增长，这是该策略的致命伤。

5.2 按字节采样（per-byte）

选定速率 $R$，每个字节以 $1/R$ 概率被选中（被选中时采样其所属分配）。大小为 $Z$ 的分配被采样概率为：

$$1-(1-\frac{1}{R})^{Z}$$

其方差贡献为：

$$Z^2 \frac{(1-\frac{1}{R})^{Z}}{1-(1-\frac{1}{R})^{Z}}$$

实际场景中 $R$ 很大，可用指数近似：

$$Z^2 \frac{e^{-Z/R}}{1 - e^{-Z/R}}$$

5.3 关键区间行为

• $Z$ 远小于 $R$：利用 $e^x \approx 1+x$，方差贡献约为 $RZ$——随大小线性增长，而不是二次增长；
• $Z$ 与 $R$ 同量级：当 $Z/R = \ln 2 \approx 0.693$ 时 $\frac{e^{-Z/R}}{1 - e^{-Z/R}} = 1$，方差项接近 $Z^2$；
• $Z$ 远大于 $R$：方差贡献趋近于 0。

两种策略的差异一目了然：per-allocation 让大分配贡献 $(N-1)Z^2$ 的方差，而 per-byte 把方差压到近似 $RZ$，且采样样本向慢速路径的大分配倾斜。

六、为什么最终选择按字节采样

文档从快速路径/慢速路径动力学出发，给出了三条理由，我们在 src/prof.c 与 src/prof_data.c 的源码中都能看到对应落点：

1. per-allocation 的方差二次增长代价高昂：当堆中有不可忽略的字节落在大分配上（实践中很常见）时，这种策略会显著抬高方差；
2. per-byte 把更多样本投向大分配，而这些分配本身已处于慢速路径，采样开销占比更小；
3. jemalloc 本来就按字节驱动多个 ticker（如 tcache gc），并把"已分配字节数"作为用户可见统计量——按字节记账的书箱（bookkeeping）是必须做的，per-byte 采样几乎零额外成本。

这正是在 jemalloc 中实际采用的方案。Heap dump 记录分配大小与采样率 $R$，jeprof 用除以 $1 - e^{-Z/R}$ 的方式去偏。严格说，框架建议的除数应是 $1-(1-1/R)^Z$，但实践中 $R$ 很大、$e^{-Z/R}$ 是足够好的近似且计算更快；也可以等价地看作把采样直接视为一个泊松过程的自然结果。

6.1 源码佐证：去偏映射与默认参数

src/prof_data.c 的 prof_unbias_map_init() 正是按上述公式构造去偏映射：

double div_val = 1.0 - exp(-sz / rate);
double unbiased_sz = sz / div_val;

并在 src/prof_data.c 的 dump 路径中以 scale_factor = 1.0 / (1.0 - exp(-ratio)) 应用该因子。

采样率通过 lg_prof_sample 配置，其默认值定义在 include/jemalloc/internal/prof_types.h：

#define LG_PROF_SAMPLE_DEFAULT	19
#define LG_PROF_INTERVAL_DEFAULT	-1

即默认平均每 $2^{19}$ = 524288 字节采样一次；lg_prof_interval 默认 -1 表示禁用按间隔触发的 dump。配置解析位于 src/jemalloc.c，通过 MALLOC_CONF 环境变量中的 lg_prof_sample 与 lg_prof_interval 项设置，例如：

MALLOC_CONF=prof:true,lg_prof_sample:20

另外，dump 文件的命名规则可在 src/prof_sys.c 中看到："%s.%d.%zu.json"，即 prof_prefix.pid.<序号>.json（prof_prefix 由 prof_prefix 配置项指定，src/prof_sys.c）。

七、对 Heap Dump 使用者的两个重要告诫

7.1 栈出现次数 ≠ 分配频率

一个栈出现的次数是另一个的两倍，并不代表它分配频率是对方的两倍。 文档给出经典反例：程序里只有两种分配栈——栈 A 每次分配 8 字节、出现一百万次；栈 B 每次分配 8 MB、只出现一次。若采样率 $R$ 约为 1 MB，期望中栈 A 出现约 8 次、栈 B 出现 1 次。从 dump 上看栈 A "仅比栈 B 频繁 8 倍"，实际上却是一百万倍。因此原始计数必须结合分配大小与采样率一起解读，绝不能把出现次数直接当作分配频次的比例。

7.2 必须先逐样本去偏，再做聚合

手工解析 heap dump 做跨栈或跨运行聚合时，"先去偏再求和"与"先求和再去偏"结果天差地别。复用上例：若从一百万台机器收集 dump，得到栈 A 出现 800 万次（每次 8 字节）、栈 B 出现 100 万次（每次 8 MB）。若先求和：栈 A 合计 64 MB，栈 B 合计 8 TB；此时去偏因子几乎不改变这两个数字，于是 sum-then-unbias 会严重低估栈 A 实际分配的内存量。正确的顺序永远是：对每个样本按其大小与采样率去偏，然后把去偏后的值累加。

八、未来探索方向：方差最小化问题

框架本身相当通用，但作为工程决策，jemalloc 只关心足够简单的策略——即分配被采样的概率只取决于其大小。任务是：为每个大小类 $Z$ 选择概率 $p_Z$。文档指出，真正限制方差降低的是采样本身昂贵这一事实，所以要在"给定最大采样率 $P$"的约束下最小化方差：

$$\text{Minimize} \quad \sum_Z Z^2 l_Z \frac{1-p_Z}{p_Z} \qquad \text{s.t.} \quad \sum_Z a_Z p_Z \leq P$$

其中 $a_Z$ 是大小为 $Z$ 的分配所占比例，$l_Z$ 是大小为 $Z$ 的分配在 heap dump 时刻仍存活的比例。忽略不依赖 $p_Z$ 的项后，目标退化为最小化 $\sum_Z Z^2 l_Z \frac{1}{p_Z}$。对特定程序，$l_Z$ 与 $a_Z$ 可直接从现有统计内省设施（stats introspection）精确获得，于是这变成一个相当易解的凸优化问题（可表述为二阶锥规划）。文档作者坦言：把 $p_Z$ 直接暴露成调优参数在当前阶段并非值得投入的开发方向，但"当前策略离最优有多远"是值得思考的问题。

九、实现现实：jeprof 的历史偏差与"将错就错"的兼容技巧

文档坦诚地指出，前述"美好的故事"至少部分是个谎言。历史沿革如下：

1. jeprof（从 pprof 抄来的逻辑）最初存在上文第七节描述的 sum-then-unbias 错误；
2. 当前版本的 jemalloc 在内部逐分配执行去偏，始终追踪"无偏数字应当是多少"；
3. 但把这些无偏数字直接输出会破坏 jeprof 及大量已部署工具（它们都抄了 jeprof 的旧逻辑）的兼容性；
4. 于是 jemalloc 反其道而行：既然 dump 时知道 jeprof 最终要报告什么数字，就精心挑选输出值，使 jeprof 用它的旧公式算出来的结果恰好等于真实的无偏值。

这段数学实现在 src/prof_data.c 的 prof_do_unbias() 中，注释给出了完整的推导脉络：jeprof 的去偏公式是

$$c_{out} = c_{in} \cdot \frac{1}{1-\exp(-s_{in}/c_{in}/R)}, \qquad s_{out} = s_{in} \cdot \frac{1}{1-\exp(-s_{in}/c_{in}/R)}$$

jemalloc 只需反解出要输出的 $c_{in},s_{in}$（src/prof_data.c：y = s_out * (1.0 - exp(-x / R))，其中唯一的"聪明之处"是一次变量代换让指数项约掉）。prof_unbias_map_init() 中构造的 prof_unbiased_sz 与 prof_shifted_unbiased_cnt 两张映射表（src/prof_data.c）正是为此服务的预计算。

这样做的一个直接后果是：jeprof 及相关工具的输出是正确的，但它们的输入（原始 dump 数据）是不正确的——对直接阅读原始 profiling dump 的读者而言可能相当困惑，这也解释了为什么理解本文的数学背景对正确使用 jemalloc profiling 至关重要。

十、实践要点小结

• 采样配置：通过 MALLOC_CONF 设置 prof:true 与 lg_prof_sample（默认 19，即约每 512 KiB 采样一次，见 include/jemalloc/internal/prof_types.h），lg_prof_interval 控制按字节间隔自动 dump；
• 几何分布采样：每次触发采样后按 bytes_until_sample = |log(u)/log(1-p)| + 1 重置计数器（src/prof.c），一次随机数生成换取多次分配；
• 去偏公式：每个大小为 $Z$、采样率为 $R$ 的样本，真实字节数以 $1\mathrm{/}(1-e^{-Z\mathrm{/}R})$ 放大（src/prof_data.c）；
• 聚合纪律：永远"先逐样本去偏、后求和"；
• 解读纪律：栈的出现次数不能直接当作分配频率比例，务必结合大小与采样率。

结语

从无偏估计的数学框架，到按字节采样的工程选型，再到为兼容 jeprof 而精心设计的"输出反算"技巧，jemalloc 的 profiling 是一个把统计学正确性与工程效率揉合到极致的系统。本文所述的核心推导均可在 PROFILING_INTERNALS.md 与其对应的 src/prof.c、src/prof_data.c 实现中找到第一手依据；对于在 placeholderkv 上做内存剖析的开发者，理解这套采样-去偏机制是正确解读 heap dump 的前提。