MongoDB 内置 TCMalloc 的 Temeraire 巨页感知分配器设计解析【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo导读Temeraire法语意为鲁莽、大胆也是一系列英国主力战舰的名字是 TCMalloc 中面向透明巨页Transparent HugePages, THP重新设计的页堆分配器。本文基于当前仓库中 Temeraire 设计文档系统讲解它的设计目标、核心数据结构RangeTracker、HugeAllocator、HugeCache、HugePageFiller、HugeRegion、HugePageAwareAllocator以及热/冷分配提示hot/cold hints机制。读完本文你将理解 MongoDB 等大型服务进程为何能借助 Temeraire 同时获得更低的页堆内存占用、更高的巨页利用率和可控的分配速度损失并能够结合仓库源码深入验证每一项设计。本文全部路径均为仓库根目录相对路径源码位于 src/third_party/tcmalloc/dist/tcmalloc/配套文档位于 src/third_party/tcmalloc/dist/docs/。Temeraire 的设计还曾以论文Beyond malloc efficiency to fleet efficiency: a hugepage-aware memory allocator发表于 OSDI 2021该论文不属于本仓库内容此处仅作背景说明。一、设计目标为什么要在巨页上重新设计分配器传统上TCMalloc 的PageHeap在把内存交还给操作系统时使用MADV_DONTNEED之类的madvise()调用这种释放方式完全不考虑透明巨页的边界导致碎片化的释放会破坏巨页的完整性。Temeraire 的设计目标因此分为三点大幅缩小页堆pageheap。PageHeap在尝试MADV_DONTNEED之后仍会因为内部碎片保留大量内存。Temeraire 希望回收其中相当一部分理想情况下节省超过 90%虽然不指望普遍达到但多种合成负载表明页堆节省 50% 是合理的目标。大幅提升巨页使用率。ReleaseMemoryToSystem中的madvise()不考虑巨页实际阻碍了大部分 RAM 以完整巨页形态保留。业界已有服务通过禁用 release等手段获得显著的性能提升——这正是 Temeraire 试图在分配器层面系统化解决的问题。合理的分配速度。这实际上是一个非目标non-goalTemeraire 不追求与PageHeap::New的速度持平而是接受在真实页分配上的速度损失换取更好的巨页利用率和更低的空间开销只求避免灾难性的速度回退。文档明确接受两类额外时间开销更激进的释放整页整页地释放巨页增加重新背衬backing内存的成本更精细、更昂贵的选择为每一次请求挑选更合适的落点。从源码看这一设计被编码在 huge_page_aware_allocator.h 的类注释中An implementation of the PageAllocator interface that is hugepage-efficient. Attempts to pack allocations into full hugepages wherever possible, and aggressively returns empty ones to the system.一种对巨页高效的 PageAllocator 实现尽可能把分配打包进完整巨页并激进地把空巨页交还系统。这正是减小页堆 提高巨页率两个目标的直接体现。二、整体设计一条分配请求的三段式路径Temeraire 的算法更准确地说是决定了算法的数据结构按分配大小被清晰地划分为组件。一次分配请求的典型路径如下足够小且已有空间直接放进一个现有的、已背衬backed的、部分空闲的巨页中把分配塞进去。超过单个巨页、但又不足以简单向上取整到整巨页用 best-fit最佳适配放进若干个更大的 slab区域中这些 slab 的分配可以跨越巨页边界按需为分配背衬巨页。足够大向上取整到最近的巨页倍数取整产生的额外空间可供更小的分配使用。释放deallocation则只需判断某次分配属于 1)、2)、3) 中的哪一类并把对应的被分配对象标记为空闲即可。文档特别强调每个组件都有相当详细的单元测试且由于代码力求零初始化可行zero initializable大多数组件都模板化在tcmalloc::SystemRelease函数上。这一点可以在 huge_page_aware_allocator.h 中看到StaticForwarder::ReleasePages最终调用SystemRelease(ptr, size)。下面按组件逐个展开。三、基础数据结构Bitmap与RangeTrackerRangeTracker及其底层实现Bitmap是贯穿上述所有组件的辅助类两者都非常简单Bitmap一个定长模板化位图提供快速的置位/清位操作以及范围range操作并广泛支持搜索与迭代——这正是std::bitset无法胜任的原因。从 range_tracker.h 的源码可见其核心接口GetBit/SetBit/ClearBit、CountBits、SetRange/ClearRange、ClearLowestBit、NextFreeRange、FindSet/FindClear含前向与反向版本内部以size_t bits_[kWords]存储。RangeTracker本质上是带使用统计的Bitmap最重要的统计量是最长连续空闲位区间longest_free。它提供基于空闲区间做 best-fit 分配的方法同时保持统计正确。构造时longest_free_初始化为N全空见 range_tracker.hFindAndMark(n)负责在满足n longest_free()的前提下按 best-fit 找到并标记n个空闲位。由于RangeTracker/Bitmap出现在HugePageAwareAllocator的几乎每一次分配/释放路径上而且以多种方式出现两者都必须相当快。实现已做了合理优化但文档也坦言可能还有更多提升空间。仓库中还有对应的性能基准与单元测试可供验证单元测试range_tracker_test.cc基准测试range_tracker_benchmark.cc四、底层背衬HugeAllocator与HugeCache这一组类负责提供已背衬或未背衬的、按巨页对齐的巨页范围用于满足足够大或尺寸恰好合适的请求并为其他组件提供可继续切分的原始内存。4.1HugeAllocator近乎平凡的分配器HugeAllocator几乎可以说是平凡的从SysAllocator请求任意大的、巨页大小的块保持这些块未背衬unbacked并跟踪可用的未背衬区域由于内容全部未背衬这里不需要追求完美的空间效率——只付出虚拟内存和元数据成本但仍会尽量节俭避免 VSS 被过度放大也不需要特别快因为它远离任何热路径而且在分配完一个范围后马上就会产生不小的背衬成本。源码中 huge_allocator.h 的注释与接口直接印证了这一点HugeAllocator假设拿到的巨页都是未背衬的提供Get获得n个与其他调用互不重叠的未背衬巨页与Release归还范围。唯一棘手的地方在于作者必须手写一些精巧的数据结构。本希望直接从SysAllocator抓取 GB 级大块、用位图管理但太多测试对SysAllocator的细节有脆弱依赖如果 TCMalloc 总是请求远超当前用量最低需求的内存这些测试就会崩溃。因此改为跟踪相对较小的范围实现了一棵合并相邻范围的平衡树虽然繁琐但相当高效。4.2HugeCache热缓存HugeCache是HugeAllocator之上一个非常简单的包装器唯一目的是缓存少量已背衬的单个巨页范围作为热缓存应对快速分配又快速释放一个 2 MiB 块的场景。文档坦承不确定该缓存是否必要但它没带来多少复杂度且能在一些潜在的对抗性场景中显著帮忙因此选择保留。它目前会基于历史行为尝试估计最优缓存大小这个特性保留或去掉都很容易。源码中 huge_cache.h 的实现细节与之对应kCacheTime为 1 秒缓存时间的 2 倍被用作看起来武断的窗口通过MaybeShrinkCacheLimit/ShrinkCache动态调整上限usage_tracker_、off_peak_tracker_、size_tracker_三个窗口跟踪器均为kCacheTime * 2共同支撑缓存是否过大的判断基线缓存为10 个巨页easily wiped away很容易被清空。五、核心组件HugePageFiller小分配的打包器HugePageFiller接收小于一个巨页的小请求并尝试把它们高效地打包进巨页。绝大多数二进制文件的分配几乎全部是小分配此处指经过采样、中央缓存等过滤后真正到达页堆的请求因此它是空间开销的最大消费者也是最重要的组件。核心目标让活跃分配尽可能落在最小的一组巨页内从而负担得起让所有被使用的巨页保持完整背衬并激进地释放空巨页。关键挑战避免巨页内部空闲空间的碎片化。1 页的请求最常见但 4、8 甚至 50 页的请求也不少见。大量1 页大小的空闲区对后类请求毫无用处否则就得为新的大请求申请数量惊人的新巨页。解决方案在每个巨页上建立一个按碎片程度而非空闲总量排序的堆式数据结构用最长空闲区间一个巨页能容纳的最大分配作为碎片度量如果一个巨页有长度为 8 的空闲区间绝不用它来满足更小的请求除非所有可用巨页的空闲区间都同样长。这样能精打细算地把长区间留给真正需要它们的请求并让它们随相邻分配被释放而得以增长。在最长空闲区间相等的组内堆按分配次数对数分桶排序倾向于从更满的巨页中分配。文档给出的直觉是任何大小的分配在任意时刻被释放的概率近似相等一阶近似而要让一个巨页变空需要它上面的所有分配都被释放——与其寄希望于 5 个 1 页分配同时释放概率 P⁵不如寄希望于 1 个 10 页分配释放概率 P。因此分配次数多的巨页更值得优先分配。此外HugePageFiller还包含作为最后手段的释放大部分已空巨页的支持subrelease。从源码看HugePageFiller的实现确实是一组固定链表 位图的加速结构huge_page_filler.h模板类构造参数包含HugePageFillerAllocsOption稀疏/密集 span 是否分开记账与chunks_per_alloc每个巨页对应一个PageTracker其中RangeTrackerkPagesPerHugePage.raw_num() free_跟踪空闲区间、BitmapkPagesPerHugePage.raw_num() released_by_page_跟踪逐页释放状态见 huge_page_filler.hkNumLists kPagesPerHugePage.raw_num() * kChunks决定堆链表数量见 huge_page_filler.h对外 API 刻意只有TryGet / Put / Contribute三个动作TryGet只做尝试而不保证成功成功与否由调用方决定是否新开巨页这简化了不同上下文的使用并改善了可测试性见 huge_page_filler.hContribute还会接收来自多巨页分配尾部的 donated捐赠巨页对它们区别对待。六、HugeRegion中等大小分配的落点1 GiB 大区域HugeAllocator覆盖超大请求、HugePageFiller覆盖微小请求中间地带呢特别是那些放不进一个巨页、又不应简单取整到巨页倍数的请求例如 2.1 MiB。这类请求糟糕地常见如果取整到 4 MiB会产生不可接受的 slack剩余浪费而在当前大多数二进制中大块分配恰恰占据其分配的主体靠 Filler 消化这些 slack 是远远不够的。解决方案一个大得多的区域region用 best-fit 把这些块放进一大段跨越巨页边界的巨页范围里维护一组这样的区域从碎片最严重的一个开始分配与 Filler 的策略类似主要区别区域默认保持未背衬Filler 几乎完全处理已背衬巨页当某个请求命中区域时才按需背衬对应巨页一旦某巨页重新变空便激进地取消背衬unback。几个重要细节区域当前为 1 GiB非常大。理由假设整个二进制分配了大量尺寸为 S如 2.1 MiB的、Filler 装不下又不整除区域大小 M 的请求会浪费多少空间大约需要R N / (M / S)个区域每个区域放floor(M/S)个分配尾部闲置。如果M/S个分配恰好蹭到区域最后一个巨页每个区域会浪费约一个巨页总共浪费R个巨页。结论区域越大这类浪费越小。最初区域是 32 MiB这个效应非常明显。更大的区域还意味着一个二进制只需极少数区域可以更少操心区域集合的组织方式。不尝试复用已背衬但未使用的范围也不偏好拥有这类范围的区域。这基本是投入产出问题作者想做但看不到在不把数据结构搞得更复杂的情况下实现的办法目前测试中这未构成大问题。注意RangeTracker有低地址偏向会在一定程度上把分配向区域低端压实缓解该问题。源码完全印证了这些设计huge_region.h 中kRegionSize HLFromBytes(1024 * 1024 * 1024)即 1 GiB、kNumHugePages kRegionSize.raw_num()内部用RangeTrackerkRegionSize.in_pages().raw_num() tracker_做跟踪MaybeGet/Put提供按需背衬与释放语义BetterToAllocThan用longest_free()比较实现从最碎片化的区域分配策略。6.1 补充文档《Regions Are Not Optional》仓库中另有一篇配套文档 regions-are-not-optional.md专门论证HugeRegion的必要性曾有人质疑它是过早优化。其核心是一个三难困境Trilemma必须支持任意合理大小的分配——抱歉tcmalloc 在你大量使用某尺寸时会爆炸是不可接受的必须能用巨页背衬大部分、理想情况下全部堆内存希望严格约束堆的全局空间开销。考虑比巨页大、但取整误差又显著的请求 Rᵢ取整到巨页边界对 110 个巨页的分配会引入显著开销既不能取消背衬最后一个巨页的未用尾部违反要求 2也不能假设这类请求稀少、会有大量小分配来填充尾部违反要求 1而且对广泛使用的二进制而言这在经验上是错误的。因此结论是必须以某种形式支持多个 Rᵢ 连续分配即把 R₁ 的尾部当作 R₂ 的开头。HugeRegion的全部工作就是这件事。文中还给出两个补充说明为什么区域那么大因为它有效。虚拟地址空间几乎是免费的。并补充128 MiB 与 512 MiB 也表现合理但没有更换尺寸的强烈理由仓库不支持 VSS 上限场景。没有 HugeRegion 会怎样5 MiB、6.1 MiB、10.1 MiB 等任意超过 2 MiB 且不能忽略尾部的分配只要构成堆使用的重要组成部分都会产生不可接受的开销。七、总装HugePageAwareAllocator如何路由请求HugePageAwareAllocator容纳上述所有组件并在它们之间路由同时负责与 TCMalloc 其余部分对接例如上述类都不需要、也不使用 Span。类注释与接口见 huge_page_aware_allocator.h它继承PageAllocatorInterface通过New(Length n, SpanAllocInfo)分配、支持按align页边界对齐。7.1 大小策略如何为一次请求选择子分配器采用基于大小的策略小分配直接交给HugePageFiller按需向 Filler 添加巨页。略大的分配仍小于一个完整巨页先尝试Filler但如果当前没空间就不扩张 Filler转而到区域中找空闲空间。若区域和 Filler 都没有空间优先扩张 Filler因为它的块更小。理由如果二进制只有比如¾ 巨页的分配我们不希望 Filler 巨大但 ¼ 空着而在能轻松把小分配与大分配打在一起的更合理二进制里我们宁愿用 Filler 打包而不是用区域。放不进巨页的分配直接交给区域真正巨大的分配则直接交给HugeAllocator。策略 1) 与 2) 之间的切换点只是调优决定任何选择都能产出可用的二进制。半个巨页是随意选定的实践表明效果不错。7.2 背衬backing处理来自HugeAllocator或HugeRegion某些时候的分配需要背衬扩张HugePageFiller的巨页也需要。背衬并非免费页堆分配实践上不算昂贵但它在锁内进行锁竞争很重要。当前做法是依赖应用程序访问来背衬内存并假定返回的内存已被背衬为记账目的跟踪某次分配是否由先前未背衬的内存满足该信息被送到释放 pageheap 锁的时点从而在锁外背衬避免锁竞争——相比在返回给应用前显式背衬这一改动带来了明显的性能差异。文档还补充了锁纪律的总体说明这里刻意不在持有 pageheap 锁时背衬内存见 huge_page_aware_allocator.h 的注释。八、利用热/冷提示hot/cold hintsTCMalloc 提供hot_cold变体的new/分配接口应用程序可用它提示某次分配会被多频繁地访问动机如果一些频繁访问的分配与不频繁访问的数据放在一起内核可能因为整页热而把较大的页判为热即便其中多数分配并不热。通过显式指定 hot/cold 提示TCMalloc 可以把分配分开改善热堆的数据局部性并提升**内存分级memory tiering**的效果——把冷堆放在更慢但更便宜的内存层级。后端实现TCMalloc将页堆一分为二bifurcates把冷分配与热分配分开存储避免两者落在同一个巨页上热/冷信号被编码进 size class据此决定使用哪个页堆同时把独立的冷堆标记为MADV_NOHUGEPAGE使冷分配落在原生大小native-sized的页上。这样做的意图是避免冷分配占用巨页从而把巨页资源留给热堆。在 page_allocator.h 的接口中可以看到页堆按标签分区的骨架文档中给出的 page_allocator.cc 即冷热页堆分裂的实现位置位于本仓库 src/third_party/tcmalloc/dist/tcmalloc/page_allocator.cc。HugePageAwareAllocatorOptions中的MemoryTag taghuge_page_aware_allocator.h正是这一分区机制的载体不同标签如冷/热/正常会路由到对应的页堆实例。九、总结与进一步阅读Temeraire 用一个清晰的三段式结构解决了传统页堆在巨页面前的三大顽疾HugePageFiller用按最长空闲区间分桶的堆把小分配紧密打包进巨页HugeRegion用 1 GiB 大区域优雅地消化 2.1 MiB 这类夹心分配HugeAllocatorHugeCache负责底层巨页的背衬与热缓存最后由HugePageAwareAllocator按大小策略统一路由并借助 hot/cold 提示让冷分配主动让出巨页。这套设计以可接受的分配速度损失换来页堆内存的大幅缩减与巨页利用率的大幅提升正是 MongoDB 等大型服务赖以在高负载下控制驻留内存、提升吞吐的底层基础。感兴趣的读者可以继续深入以下仓库文件主设计文档docs/temeraire.md本文所依据的原始文档区域必要性论证docs/regions-are-not-optional.md位图与区间跟踪实现tcmalloc/internal/range_tracker.h 及测试 tcmalloc/internal/range_tracker_test.cc、基准 tcmalloc/internal/range_tracker_benchmark.cc巨页分配与缓存tcmalloc/huge_allocator.h、tcmalloc/huge_cache.h小分配打包核心tcmalloc/huge_page_filler.h中等分配区域tcmalloc/huge_region.h总装与路由tcmalloc/huge_page_aware_allocator.h冷热页堆分裂tcmalloc/page_allocator.cc关联文档索引docs/README.md【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考