关于数据库:TCMalloc-技术细节详解

TCMalloc 是 Google 开发的 gperftools 中的一款内存调配工具，在 Golang 等诸多出名我的项目中均有应用。明天咱们一起走近技术细节，解密它的高效内核。

一、总体架构

TCMalloc 依照内存大小区间划分为小 / 中 / 大三类，由不同的数据结构进行治理。

通过 SizeMap，还能够对小内存持续细分。SizeMap 将用户申请的不超过 256K 的内存大小映射到 85 种对齐的大小类型（size class），最小 8 字节，最大 256K，并记录了大小类型到 num_objects_to_move、class_to_pages 的映射关系。（这两个整型数值的意义详见后文）大块间断的内存依照 Page (8K) 为最小单位进行追踪，一个或多个间断的 Page 形成一个 Span。Page ID 与 Span 的映射关系由 Page Map（通过 radix-tree 实现，如下图）进行保护。

一个 Span 可能作为一块间断的中 / 大内存间接调配给用户应用，也可能决裂成小内存块（object）放到 Central Cache 或者 Thread Cache 中，再调配给用户。Span 构造体记录一个 Span 的详细信息，它包含：

1. start 和 length：记录 Span 蕴含的 Page 范畴
2. prev 和 next：Span 类型的指针，用于将 Span 连接成 Spanlist
3. objects：记录 Span 决裂成的小内存块的链表
4. span_iter_space：记录 Span 在 SpanSet（Page Heap 中的 Span 汇合）中的迭代器，不便 Span 从 SpanSet 中移除
5. sizeclass 示意 Span 决裂成的小内存块的大小类型（0 示意没有决裂成小内存）
6. refcount 示意 Span 决裂成的小内存块的援用计数，即调配给 Thread Cache 应用的 object 数量
7. location 枚举变量记录 Span 所在的地位（pageID 相邻且 location 雷同的闲暇 Span 能够合并成更大的 Span）

TCMalloc 的总体架构以及申请开释内存的流程如下图所示，其中 System Allocator 应用的是 mmap 和 sbrk：

二、Central Cache 与 Thread Cache

小内存（Size≤256 K）通过 Thread Cache 和 Central Cache 调配，每个线程都有一个 Thread Cache，所有线程共享一个 Central Cache。

它们都由 85 条固定大小类型（最小 8 字节，最大 256K）的 freelist 形成。freelist 蕴含雷同大小类型的 object 形成的链表，并应用嵌入式指针连贯以进步内存利用率。

调配小内存的流程如下：

1. 通过 Size Map 将其大小映射到相应的大小类型
2. 在 Thread Cache 中查找该大小类型对应的 freelist
3. 如果 freelist 不为空，咱们从列表中删除第一个 object 并返回它。因为线程内不存在内存的并发申请，这个过程无需取得任何锁

如果 Thread Cache 的 freelist 为空：

1. 咱们从 Central Cache 中该大小类型的 freelist 即 Central freelist 上获取一堆 object（因为 Central Cache 由所有 Thread 持锁并发拜访，内存在 Thread Cache 和 Central Cache 之间传递时，每次传递 num_objects_to_move 个 object，以进步内存传递的效率）
2. 将它们放在 Thread Cache 的 freelist 中
3. 将新获取的 object 之一返回给申请者

如果 Central freelist 也是空的：

1. 咱们以 Page 为单位从 Page Heap 调配一系列间断 Page（即一个 Span），具体的 Page 数是从 SizeMap 获取的该大小类型的 class_to_pages 值
2. 将这些 Page 拆分为该大小类型的一组 object
3. 将新的 object 放在 Central freelist 中
4. 和以前一样，将其中一些 object 移到 Thread Cache 的 freelist 中

上述的流程在实现上有很多重要的细节：
每条 Central freelist 通过 empty 和 nonempty 两条链表记录从 Page Heap 获取的 Span，empty 示意 Span 全副传递给了 Thread Cache。Span 先决裂成该大小类型的 objects 并挂在 nonempty 上，refcount 初始值为 0，当 object 传递给 Thread Cache 时 refcount 减少。

为了不便地在 Thread Cache 和 Central Cache 之间进行 num_objects_to_move 个内存块的传递，每条 Central freelist 上都有一个定长 64 的插槽数组 tc_slots_，存用于放从 Thread cache 回收的 objects，数组元素为 TCEntry，每个 entry 记录 num_objects_to_move 个 object 的头尾指针，即一次挪动的 objects 放在一个插槽里。

通过 max_cache_size=min(64, 1M/(num_objects_to_move*size_bytes))，每条 Central freelist 就能把 tc_slots_ 总大小限度在 1M 以内，插槽数不超过 64 个且有一个初始的 cache_size（≤max_cache_size）。

Central freelist 收到 thread cache 交还的 objects 后，如果 Central Cache 还有空间，即 freelist 还有插槽可用（即 used<cache_size），或者能让随机一条其余 size class  的 Central freelist 的 cache_size 缩小，使得本条 freelist 的 cache_size 减少且不超过 max_cache_size（只须要随机到的这条 Central freelist 的 cache_size>0 就能满足）。

把这些 objects 插入闲暇的插槽；否则把 objects 逐个开释给对应的 Span，Span 的 refcount 也相应地缩小，当 refcount 为 0 时，阐明整个 Span 都是闲暇的，将其开释回 Page Heap 中。

Thread Cache 向 Central Cache 申请内存时，会优先从插槽数组 tc_slots_ 获取，如果 tc_slots_ 为空，再从 nonempty 链表上的 Span 中获取。

另外，为了使线程能够疾速获取 Thread Cache，Thread Cache 的指针被保留在了 __thread 润饰的动态变量 threadlocal_data_ 中。该修饰符示意对于每一个线程，都有一个线程本地的动态变量，线程之间互不烦扰。为了主动销毁 Thread Cache，应用 pthread 的 pthread_key_create 接口注册 DestroyThreadCache 办法，该办法将在线程完结时执行以销毁 Thread Cache。

三、Page Heap

超过 256K 的内存以及 Central Cache 以 page 为单位申请的内存都由 Page Heap 调配。

Page Heap 有 128 对 SpanList，别离搁置内存大小 1 page 到 128 page 的 Span。超过 128 page 的 Span 则放在一对 SpanSet（应用 std::set，底层是用红黑树实现的）中治理。

当申请 K 个 page 的内存时，从第 K 对 SpanList 开始搜寻，如果该对 SpanList 为空，查看下一对 SpanList，以此类推。

如果找到长度 ≥K 的 Span，则切出长度为 K 的 Span 返回，残余局部被从新插入适合的 SpanList 中。如果没有 SpanList 能够满足调配，则通过 std::set 提供的 upper_bound 接口，从 SpanSet 中找到大于等于 K 个 page 的最小 Span，同样切割后进行返回，残余局部依据大小插入 SpanSet 或适合的 SpanList。

如果没有找到满足需要的 Span，将通过 System Allocator 从零碎获取内存后反复上述搜寻过程。从 System Allocator 获取内存时，如果理论须要的内存不满 1M，先尝试申请 1M 内存；如果申请失败，再尝试申请理论须要的内存大小。

在上述流程的实现中，咱们仍然找到了一些有意思的细节：

一对 SpanList，蕴含 normal 和 returned 两条链表，搜寻时先查找 normal，如果 normal 为空，再查找 returned。从 System Allocator 获取的或从 Central Cache 偿还的闲暇 Span 挂在 normal 上，从 normal 上开释给操作系统的 Span 挂在 returned 上。

这里应用了一个非凡的技巧来进步 Page Heap 的效率：returned 上的 Span 并没有真的被开释，只是应用 MADV_FREE 标记了这块内存，内核会等到内存缓和时才真正将其开释。在真正开释之前，这块内存仍然能够随时复用。SpanSet 同理。

开释给 Page Heap 的 Span 会尽可能合并：Span 构造体中记录了 Span 的 Page 范畴以及它的 location（位于 normal 还是 returned 链表中）。当一个 Span 被开释回 Page Heap  时，假如 Page 范畴是 [p, q]，咱们查找 Page p-1 和 q+1 所在的 Span。

如果有相邻且 location 雷同的闲暇 Span，就将它（们）与 Span[p, q] 合并。合并成的 Span 依据大小被插入到适合的 SpanList 中或 SpanSet 中。这样的解决对缩小内存碎片颇有帮忙。