LevelDB 源码阅读：Arena 区域分配器

顺着 MemTable 里被 = delete 的拷贝控制一路往下追，我掉过好几层，最后撞到了它底下整块内存的地板：Arena。它是一个很小、很专一的分配器，里面几乎每一个设计决定都是在回答同一个问题——MemTable 的跳表到底需要从内存里得到什么？

本文走读 util/arena.h 与 util/arena.cc，不仅讲清代码做了什么，也讲清那些常量和内存序选择为什么是这样。

1. Arena 是什么

Arena（util/arena.h:16）是一个 bump allocator（指针碰撞式区域分配器）：

一次性批量申请大块内存；
分配时只移动指针（O(1)、无锁、无系统调用）；
所有内存在析构时一次性整块释放。

它是为 MemTable 的 SkipList 节点做高性能内存管理而存在的。核心契合点：SkipList 节点频繁分配、但从不单独释放（节点一旦插入永不删除，直到整个 MemTable 销毁），所以根本不需要通用堆的 per-node free。

2. 核心成员（`arena.h`）

成员	类型	作用
`blocks_`	`std::vector<char*>`	持有的所有大块，默认每块 `kBlockSize = 4096`
`alloc_ptr_`	`char*`	当前块的分配游标
`alloc_bytes_remaining_`	`size_t`	当前块剩余空闲字节
`memory_usage_`	`std::atomic<size_t>`	已用内存统计（唯一原子成员）

析构 ~Arena：遍历 blocks_ 逐个 delete[]，即”整块释放”。

3. 两条分配路径

快速路径 `Allocate`（`arena.h:55-67`）

if (bytes <= alloc_bytes_remaining_) {   // 当前块放得下？
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
}
return AllocateFallback(bytes);          // 放不下 → 开新块

绝大多数小分配在此满足，热路径极快。

慢速路径 `AllocateFallback`（`arena.cc:20-36`）

在”当前块放不下 bytes”时触发，两种策略：

策略 A（小对象，bytes <= kBlockSize/4）：开一整块新 kBlockSize(4KB) 当当前块，从中切出 bytes。代价：旧块剩余 alloc_bytes_remaining_ 被废弃。收益：新块剩余可用、只一次 new、局部性好。
策略 B（大对象，bytes > kBlockSize/4）：用 AllocateNewBlock(bytes) 开一块刚好 bytes 大小的专属块返回，不设为当前块。代价：多一次 new。收益：旧块剩余被保留，且不会制造半满新块。

注：AllocateNewBlock（arena.cc:58-64）真正 new char[] 并累加 memory_usage_ 原子计数器。

4. 关键推导：1/4 阈值的本质

AllocateFallback 触发时（当前块放不下 bytes），旧块剩余 alloc_bytes_remaining_ 被抛弃——这是真正”浪费”的空间。

严格推导每次换块丢弃的碎片上界：

alloc_bytes_remaining_ < bytes        （放得下就不进 fallback）
bytes <= kBlockSize/4                  （走策略 A 才抛弃旧块）
⇒  waste = alloc_bytes_remaining_ < kBlockSize/4

即运行中因换块而丢弃的碎片，严格小于 1/4 个块。

对应三类对象：

> 1/4 块：策略 B，单独开块，主块零浪费；
== 1/4 块：策略 A，4 个恰好铺满一块 4KB，无瑕疵；
< 1/4 块：策略 A，可能开新块，旧块剩余被弃，但被弃量 < 1/4 块。

为什么是 1/4 而非别的

核心是内部碎片 vs 分配开销的平衡：

阈值太高（如 1/2）→ 中等对象也走策略 B，产生大量零散小 new 块，blocks_ 膨胀、局部性变差；
阈值太低（如 1/16）→ 稍大对象也塞进整块 4KB，剩 3KB+ 大概率用不上 → 严重浪费。

1/4 是针对 LevelDB 负载（小节点为主、偶有大 value）调出的经验启发式，注释明说意图：“avoid wasting too much space in leftover bytes”（别在剩余字节里浪费太多空间）。

具体数值：kBlockSize = 4096，4096/4 = 1024 字节 = 1KB。阈值用表达式 kBlockSize/4 写，随 kBlockSize 自动缩放；4096 能被 4 整除，无整数除法精度损失。

两个注脚

对齐的微小溢出：AllocateAligned 为对齐加 slop（≤ align-1 ≤ 7 字节），极端情况被弃量可能略超 1/4 块，可忽略；非对齐 Allocate 严格 < 1/4。
尾块开销：析构时最后一块可能没用完，最多接近一整块——这是”临终”开销，不在 1/4 阈值控制范围内。

5. 对齐处理 `AllocateAligned`（`arena.cc:38-56`）

const int align = (sizeof(void*) > 8 ? sizeof(void*) : 8);
static_assert((align & (align - 1)) == 0, "Pointer size should be a power of 2");
size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1);
size_t slop = (current_mod == 0 ? 0 : align - current_mod);
char* result = alloc_ptr_ + slop;

align 的取值：现实平台（32/64 位）sizeof(void*) 为 4 或 8，max(., 8) 后恒为 8；> 8 分支仅为未来 >64 位指针平台留余量。
下限 8 的原因：32 位构建里 void* 本身只需 4 字节对齐，但节点含 AtomicPointer 和 8 字节序列号，强制 ≥8 保证 8 字节量安全对齐。
static_assert((align & (align-1)) == 0)：2 的幂判定经典写法。它守住”& (align-1) 当取模”那套对齐计算的前提——只有 align 是 2 的幂时，x & (align-1) 才等价于 x % align，align - (x % align) 才正确给出对齐填充。否则编译期报错，避免运行时算出错误对齐偏移。

6. 内存序：`memory_usage_` 为什么用 `relaxed`

memory_usage_ 的 fetch_add（分配时）与 load（读统计时）都用 relaxed。

现状安全：读点都在 db/db_impl.cc 的写者路径、持 DBImpl::mutex_ 下执行；fetch_add 也在写者线程持锁。实践中单线程碰此字段。
本质正确：std::atomic 的 relaxed 仍保证该变量自身的原子性（RMW 不撕裂、load 不撕裂）。它唯一不做的是不与其他内存建立 happens-before。而 memory_usage_ 只是独立近似统计值（函数名 ApproximateMemoryUsage），不充当同步标志、不”发布”任何其他非原子数据，所以不需要顺序约束。
用 seq_cst/acquire/release 只多花同步成本，不带来正确性收益。

`arena.h` 的 TODO 解答

arena.h 里”only this member is atomic, others aren’t locked. Is this OK?” → OK，有意为之：

alloc_ptr_ / alloc_bytes_remaining_ / blocks_ 只有分配线程碰（实际持 MemTable 写锁），无需原子；
唯独 memory_usage_ 被别的线程当统计读，所以单独 atomic 即可。做成 atomic 也是便宜的防御性选择。

7. 与 MemTable / SkipList 的关系

SkipList 构造时传入 Arena*（skiplist.h:48），节点用 arena_->AllocateAligned(...) 分配。
节点永不单独删除 → Arena “整块释放”模型完美契合，零碎片、无 per-node free。
MemTable 因持有 arena 分配、永不释放的跳表节点，且被多处引用计数（Ref()/Unref()），所以 memtable.h 显式 = delete 拷贝构造/赋值——只能按指针共享/转移，不能按值拷贝。

8. 联系 DDIA（数据密集型应用系统设计）

Arena 是 region-based memory management 的经典实现，服务于 LSM-tree 的内存组件 MemTable。
体现书里”为特定工作负载定制数据结构”思想：针对”大量短命对象、整体释放”场景，让写入路径的节点分配近乎零开销、零碎片（编译器、游戏引擎也常用同类分配器）。
与 DDIA 第 3 章 LSM-tree 内存组件语义呼应：MemTable 写满后不是”复制”而是整体冻结/转移（DBImpl 把它 swap 成 imm_），这种所有权整体转移的模型天然排斥值拷贝。

9. 下一步阅读路线

Arena 是 MemTable 的底座，建议继续：

db/skiplist.h：并发跳表 —— 节点如何用 AllocateAligned 分配、无锁插入/查找逻辑；
LevelDB 源码阅读：MemTable —— internal key 怎么编码进节点、Add/Get 实现；
LevelDB 源码阅读：MemTable 刷盘与 SSTable 格式 —— mem_ 写满后发生什么、SSTable 如何落盘布局；
回到主线：MemTable → WAL(log) → SSTable(table/block) → Compaction(version_set)。