内存优化总结: ptmalloc、tcmalloc 和 jemalloc

邵锐

2023-12-01

1. 内存优化总结: ptmalloc、tcmalloc 和 jemalloc

1.1. tcmalloc, jemalloc 和 ptmalloc 对比

ptmalloc 是 glibc 的内存分配管理
tcmalloc 是 google 的内存分配管理模块
jemalloc 是 BSD 的提供的内存分配管理

其中, jemalloc 性能最高, tcmalloc 次之, ptmalloc 性能最差。

1.2. 需求

系统的物理内存是有限的, 而对内存的需求是变化的, 程序的动态性越强, 内存管理就越重要, 选择合适的内存管理算法会带来明显的性能提升。

比如 nginx, 它在每个连接 accept 后会 malloc 一块内存, 作为整个连接生命周期内的内存池。当 HTTP 请求到达的时候, 又会 malloc 一块当前请求阶段的内存池, 因此对 malloc 的分配速度有一定的依赖关系。(而 apache 的内存池是有父子关系的, 请求阶段的内存池会和连接阶段的使用相同的分配器, 如果连接内存池释放则请求阶段的子内存池也会自动释放)。

1.3. 目标

内存管理可以分为三个层次, 自底向上分别是:

操作系统内核的内存管理
glibc 层使用系统调用维护的内存管理算法
应用程序从 glibc 动态分配内存后, 根据应用程序本身的程序特性进行优化, 比如使用引用计数 std::shared_ptr, apache 的内存池方式等等。

当然应用程序也可以直接使用系统调用从内核分配内存, 自己根据程序特性来维护内存, 但是会大大增加开发成本。

本文主要介绍了 glibc malloc 的实现, 及其替代品

一个优秀的通用内存分配器应具有以下特性:

额外的空间损耗尽量少
分配速度尽可能快
尽量避免内存碎片
缓存本地化友好
通用性, 兼容性, 可移植性, 易调试

1.4. 现状

目前大部分服务端程序使用 glibc 提供的 malloc/free 系列函数, 而 glibc 使用的 ptmalloc2 在性能上远远弱后于 google 的 tcmalloc 和 facebook 的 jemalloc。而且后两者只需要使用 LD_PRELOAD 环境变量启动程序即可, 甚至并不需要重新编译。

1.5. glibc ptmalloc2

ptmalloc2 即是我们当前使用的 glibc malloc 版本。

1.5.1. ptmalloc 原理

上图是 x86_64 下 Linux 进程的默认地址空间, 对 heap 的操作, 操作系统提供了 brk() 系统调用, 设置了 Heap 的上边界; 对 mmap 映射区域的操作, 操作系统供了 mmap() 和 munmap() 函数。

因为系统调用的代价很高, 不可能每次申请内存都从内核分配空间, 尤其是对于小内存分配。而且因为 mmap 的区域容易被 munmap 释放, 所以一般大内存采用 mmap(), 小内存使用 brk()。

1.5.2. 多线程支持

Ptmalloc2 有一个主分配区 (main arena), 有多个非主分配区。非主分配区只能使用 mmap 向操作系统批发申请 HEAP_MAX_SIZE(64 位系统为 64MB) 大小的虚拟内存。当某个线程调用 malloc 的时候, 会先查看线程私有变量中是否已经存在一个分配区, 如果存在则尝试加锁, 如果加锁失败则遍历 arena 链表试图获取一个没加锁的 arena, 如果依然获取不到则创建一个新的非主分配区。
free() 的时候也要获取锁。分配小块内存容易产生碎片, ptmalloc 在整理合并的时候也要对 arena 做加锁操作。在线程多的时候, 锁的开销就会增大。

1.5.3. ptmalloc 内存管理

用户请求分配的内存在 ptmalloc 中使用 chunk 表示, 每个 chunk 至少需要 8 个字节额外的开销。用户 free 掉的内存不会马上归还操作系统, ptmalloc 会统一管理 heap 和 mmap 区域的空闲 chunk, 避免了频繁的系统调用。
ptmalloc 将相似大小的 chunk 用双向链表链接起来, 这样的一个链表被称为一个 bin。Ptmalloc 一共维护了 128 个 bin, 并使用一个数组来存储这些 bin(如下图所示)。
ptmalloc 结构图
数组中的第一个为 unsorted bin, 数组中从 2 开始编号的前 64 个 bin 称为 small bins, 同一个 small bin 中的 chunk 具有相同的大小。small bins 后面的 bin 被称作 large bins。

当 free 一个 chunk 并放入 bin 的时候, ptmalloc 还会检查它前后的 chunk 是否也是空闲的, 如果是的话, ptmalloc 会首先把它们合并为一个大的 chunk, 然后将合并后的 chunk 放到 unstored bin 中。另外 ptmalloc 为了提高分配的速度, 会把一些小的 (不大于 64B) chunk 先放到一个叫做 fast bins 的容器内。

在 fast bins 和 bins 都不能满足需求后, ptmalloc 会设法在一个叫做 top chunk 的空间分配内存。对于非主分配区会预先通过 mmap 分配一大块内存作为 top chunk, 当 bins 和 fast bins 都不能满足分配需要的时候, ptmalloc 会设法在 top chunk 中分出一块内存给用户, 如果 top chunk 本身不够大, 分配程序会重新 mmap 分配一块内存 chunk, 并将 top chunk 迁移到新的 chunk 上, 并用单链表链接起来。如果 free() 的 chunk 恰好与 top chunk 相邻, 那么这两个 chunk 就会合并成新的 top chunk, 如果 top chunk 大小大于某个阈值才还给操作系统。主分配区类似, 不过通过 sbrk() 分配和调整 top chunk 的大小, 只有 heap 顶部连续内存空闲超过阈值的时候才能回收内存。
需要分配的 chunk 足够大, 而且 fast bins 和 bins 都不能满足要求, 甚至 top chunk 本身也不能满足分配需求时, ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。

1.5.4. ptmalloc 分配流程

1.5.5. ptmalloc 的缺陷

后分配的内存先释放, 因为 ptmalloc 收缩内存是从 top chunk 开始, 如果与 top chunk 相邻的 chunk 不能释放, top chunk 以下的 chunk 都无法释放。
多线程锁开销大, 需要避免多线程频繁分配释放。
内存从 thread 的 areana 中分配, 内存不能从一个 arena 移动到另一个 arena, 就是说如果多线程使用内存不均衡, 容易导致内存的浪费。比如说线程 1 使用了 300M 内存, 完成任务后 glibc 没有释放给操作系统, 线程 2 开始创建了一个新的 arena, 但是线程 1 的 300M 却不能用了。
每个 chunk 至少 8 字节的开销很大
不定期分配长生命周期的内存容易造成内存碎片, 不利于回收。 64 位系统最好分配 32M 以上内存, 这是使用 mmap 的阈值。

1.6. tcmalloc

tcmalloc 是 Google 开源的一个内存管理库, 作为 glibc malloc 的替代品。目前已经在 chrome、safari 等知名软件中运用。
根据官方测试报告, ptmalloc 在一台 2.8GHz 的 P4 机器上 (对于小对象) 执行一次 malloc 及 free 大约需要 300 纳秒。而 TCMalloc 的版本同样的操作大约只需要 50 纳秒。

1.6.1. 小对象分配

tcmalloc 为每个线程分配了一个线程本地 ThreadCache, 小内存从 ThreadCache 分配, 此外还有个中央堆 (CentralCache), ThreadCache 不够用的时候, 会从 CentralCache 中获取空间放到 ThreadCache 中。
小对象 (<=32K) 从 ThreadCache 分配, 大对象从 CentralCache 分配。大对象分配的空间都是 4k 页面对齐的, 多个 pages 也能切割成多个小对象划分到 ThreadCache 中。
tcmalloc 小对象类型链表
小对象有将近 170 个不同的大小分类 (class), 每个 class 有个该大小内存块的 FreeList 单链表, 分配的时候先找到 best fit 的 class, 然后无锁的获取该链表首元素返回。如果链表中无空间了, 则到 CentralCache 中划分几个页面并切割成该 class 的大小, 放入链表中。

1.6.2. CentralCache 分配管理

大对象 (>32K) 先 4k 对齐后, 从 CentralCache 中分配。 CentralCache 维护的 PageHeap 如下图所示, 数组中第 256 个元素是所有大于 255 个页面都挂到该链表中。
tcmalloc-pageheap
当 best fit 的页面链表中没有空闲空间时, 则一直往更大的页面空间则, 如果所有 256 个链表遍历后依然没有成功分配。则使用 sbrk, mmap, /dev/mem 从系统中分配。
tcmalloc PageHeap 管理的连续的页面被称为 span.
如果 span 未分配, 则 span 是 PageHeap 中的一个链表元素
如果 span 已经分配, 它可能是返回给应用程序的大对象, 或者已经被切割成多小对象, 该小对象的 size-class 会被记录在 span 中
在 32 位系统中, 使用一个中央数组 (central array) 映射了页面和 span 对应关系, 数组索引号是页面号, 数组元素是页面所在的 span。在 64 位系统中, 使用一个 3-level radix tree 记录了该映射关系。

1.6.3. 回收

当一个 object free 的时候, 会根据地址对齐计算所在的页面号, 然后通过 central array 找到对应的 span。
如果是小对象, span 会告诉我们他的 size class, 然后把该对象插入当前线程的 ThreadCache 中。如果此时 ThreadCache 超过一个预算的值 (默认 2MB), 则会使用垃圾回收机制把未使用的 object 从 ThreadCache 移动到 CentralCache 的 central free lists 中。
如果是大对象, span 会告诉我们对象锁在的页面号范围。假设这个范围是 [p,q], 先查找页面 p-1 和 q+1 所在的 span, 如果这些临近的 span 也是 free 的, 则合并到 [p,q] 所在的 span, 然后把这个 span 回收到 PageHeap 中。
CentralCache 的 central free lists 类似 ThreadCache 的 FreeList, 不过它增加了一级结构, 先根据 size-class 关联到 spans 的集合, 然后是对应 span 的 object 链表。如果 span 的链表中所有 object 已经 free, 则 span 回收到 PageHeap 中。

1.6.4. tcmalloc 的改进

ThreadCache 会阶段性的回收内存到 CentralCache 里。解决了 ptmalloc2 中 arena 之间不能迁移的问题。
Tcmalloc 占用更少的额外空间。例如, 分配 N 个 8 字节对象可能要使用大约 8N * 1.01 字节的空间。即, 多用百分之一的空间。Ptmalloc2 使用最少 8 字节描述一个 chunk。
更快。小对象几乎无锁, >32KB 的对象从 CentralCache 中分配使用自旋锁。并且 > 32KB 对象都是页面对齐分配, 多线程的时候应尽量避免频繁分配, 否则也会造成自旋锁的竞争和页面对齐造成的浪费。

1.6.5. 性能对比

1.6.5.1. 官方测试

测试环境是 2.4GHz dual Xeon, 开启超线程, redhat9, glibc-2.3.2, 每个线程测试 100 万个操作。

上图中可以看到尤其是对于小内存的分配, tcmalloc 有非常明显性能优势。

上图可以看到随着线程数的增加, tcmalloc 性能上也有明显的优势, 并且相对平稳。

1.6.5.2. github mysql 优化

github 使用 tcmalloc 后, mysql 性能提升 30%

1.7. Jemalloc

jemalloc 是 facebook 推出的, 最早的时候是 freebsd 的 libc malloc 实现。目前在 firefox、facebook 服务器各种组件中大量使用。

1.7.1. jemalloc 原理

与 tcmalloc 类似, 每个线程同样在 < 32KB 的时候无锁使用线程本地 cache。
Jemalloc 在 64bits 系统上使用下面的 size-class 分类:
Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]
Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]
Huge: [4 MiB, 8 MiB, 12 MiB, …]
small/large 对象查找 metadata 需要常量时间, huge 对象通过全局红黑树在对数时间内查找。
虚拟内存被逻辑上分割成 chunks(默认是 4MB, 1024 个 4k 页), 应用线程通过 round-robin 算法在第一次 malloc 的时候分配 arena, 每个 arena 都是相互独立的, 维护自己的 chunks, chunk 切割 pages 到 small/large 对象。free() 的内存总是返回到所属的 arena 中, 而不管是哪个线程调用 free()。

上图可以看到每个 arena 管理的 arena chunk 结构, 开始的 header 主要是维护了一个 page map(1024 个页面关联的对象状态), header 下方就是它的页面空间。 Small 对象被分到一起, metadata 信息存放在起始位置。 large chunk 相互独立, 它的 metadata 信息存放在 chunk header map 中。

通过 arena 分配的时候需要对 arena bin(每个 small size-class 一个, 细粒度) 加锁, 或 arena 本身加锁。并且线程 cache 对象也会通过垃圾回收指数退让算法返回到 arena 中。

1.7.2. jemalloc 的优化

Jmalloc 小对象也根据 size-class, 但是它使用了低地址优先的策略, 来降低内存碎片化。
Jemalloc 大概需要 2% 的额外开销。(tcmalloc 1%, ptmalloc 最少 8B)
Jemalloc 和 tcmalloc 类似的线程本地缓存, 避免锁的竞争
相对未使用的页面, 优先使用 dirty page, 提升缓存命中。

1.7.3. 性能对比

1.7.3.1. 官方测试

上图是服务器吞吐量分别用 6 个 malloc 实现的对比数据, 可以看到 tcmalloc 和 jemalloc 最好 (facebook 在 2011 年的测试结果, tcmalloc 这里版本较旧)。

1.7.3.2. mysql 优化

测试环境: 2x Intel E5/2.2Ghz with 8 real cores per socket, 16 real cores, 开启 hyper-threading, 总共 32 个 vcpu。 16 个 table, 每个 5M row。
OLTP_RO 测试包含 5 个 select 查询: select_ranges, select_order_ranges, select_distinct_ranges, select_sum_ranges,

可以看到在多核心或者多线程的场景下, jemalloc 和 tcmalloc 带来的 tps 增加非常明显。

1.8. 参考资料

1.9. 总结

在多线程环境使用 tcmalloc 和 jemalloc 效果非常明显。

当线程数量固定, 不会频繁创建退出的时候, 可以使用 jemalloc; 反之使用 tcmalloc 可能是更好的选择。

1.10. 更好的内存管理 - jemalloc

今年年初由于 facebook 而火起来的 jemalloc 广为人之, 但殊不知, 它在 malloc 界里面很早就出名了。Jemalloc 的创始人 Jason Evans 也是在 FreeBSD 很有名的开发人员。此人就在 2006 年为提高低性能的 malloc 而写的 jemalloc。Jemalloc 是从 2007 年开始以 FreeBSD 标准引进来的。软件技术革新很多是 FreeBSD 发起的。在 FreeBSD 应用广泛的技术会慢慢导入到 linux。

目前 jemalloc 在 firefox 中也在使用。在 firefox2 中出现了内存碎片问题之后, 便在 firefox3 中使用了 jemalloc。在 safari 和 chrome 中使用的是 google 的 tcmalloc。

1.10.1. Jemalloc 的技术特性

Jemalloc 聚集了 malloc 的使用过程中所验证的很多技术。忽略细节, 从架构着眼, 最出色的部分仍是 arena 和 thread cache。(事实上, 这两个与 tcmalloc 的架构几乎相同。Jemalloc only 的部分将会在另一次 posting 中继续探讨。)

1.10.2. Arena

与其像 malloc 一样集中管理一整块内存, 不如将其分成许多个小块来分而治之。此小块便称为 arena。让我们想象一下, 给几个小朋友一张大图纸, 让他们随意地画点。结果可想而知, 他们肯定相互顾忌对方而不敢肆意地画(synchronization), 从而影响画图效率。但是如果老师事先在大图纸上划分好每个人的区域, 小朋友们就可以又快又准地在各自地领域上画图。这样的概念就是 arena。

1.10.3. Thread cache

如果是开辟小块内存, 为使不参照 arena 而直接 malloc, 给各自的线程 thread cache 领域。此 idea 是 google 的 tcmalloc 的核心部分, 亦在 jemalloc 中体现。

再拿上面的例子, 这次给小朋友们除了一张大图纸外, 再各自给 A4 纸一张。这样, 小朋友们在不画大面积的点时, 只在自己的 A4 纸上心情地画即可(no arena seeking)。可以在自己手上的纸上画或涂(using thread cache), 完全不用顾忌别人(no synchronization, no locking), 迅速有效地画。

下图是 jemalloc 的核心 layout。看着复杂, 其实都是上面说明的部分。

最左边的就是 glibc 的 malloc, 最右边的就是 jemalloc。从图表上可以看出, jemalloc 的性能有 glibc 的两倍以上。非常压倒性的性能差异。因此, 使用了 jemalloc 的应用程序自然会快很多。Jemalloc 旁边的就是 tcmalloc。Tcmalloc 的性能与其相差甚微, 低 jemalloc2.1.0 慢 4.5%。图上和 tcmalloc 的 1.4 版本, 而如今它已经到了 1.6 版本, 因此实际上这两者应该是不相仲伯的。Jemalloc 的创始人 jason evans 也意识到这一点, 说在 cpu core 8 以上的计算机上 jemalloc 效率更高。

1.10.4. 给程序员的最后的免费午餐 – kth 分布式技术 lab 的实例

2005 年发表了一篇文章 “免费午餐的时代结束了”。在之前, 程序就算不用费脑子, 随着 cpu 时钟速度增加, 程序性能自己就会上去。但现在不同, 现在 cpu 时钟趋于稳定, 而核数不断地增加。程序员需要适应这样的多线程多进程的环境, 并要开发出适合的程序。文章讲的大概是这样的内容。

6 年之后的如今, 这篇文章完全变成现实了。事实上 cpu 时钟停留在 3GHz, 而核不断上升。现在程序要适应多线程多进程的分布式计算, 速度才能上升。但是这样的程序很难。

现在在多线程的环境下, 给程序员们的最后一道午餐便是 tcmalloc, jemalloc 这样的 malloc library。对于使用多线程的程序而言, 性能会提高数十 %。

共享一下我本人的经验。我本人在 kth 技术研究所分布式技术 lab 中承担 iLock(分布式同步工具, 请参考 google 的 chubby)。在 iLock 中用了 google 的 tcmalloc 的结果, 性能提升了 18~22%。

最大的优点就是你不需要做任何复杂的工作便可得到这样的效果。不需要代码重编译。只需在执行二进制之前, 在 cmd 窗口中输入

$ LD_PRELOAD="tcmalloc 所设置的文件夹 / libtcmalloc.so"

这样在之后执行的应用程序会使用 tcmalloc 或 jemalloc, 从而代替 glibc 标准 malloc(ptmalloc)。这需设置此处, 我们便可得到性能 20% 的提升, 这真可谓是送给我们的最后的免费午餐。

如今, 在分布式技术 lab 中使用 google 的 tcmalloc。原因在于性能上两者差不多, 但 google 的 tcmalloc 所提供的程序分析工具非常 (heap profiler, cpu profiler) 丰富。所以 tcmalloc 可能更方便一些。

一定要使用最新的 malloc 么? 一定要的!