从零实现高并发内存池：三层架构设计与性能优化实践

1. 项目概述为什么我们需要一个自己的高并发内存池如果你写过C服务端程序或者参与过任何对性能有要求的系统开发肯定对内存分配这件事又爱又恨。爱的是new和delete用起来太方便了恨的是当你的服务QPS每秒查询率冲上几万甚至几十万的时候你会发现CPU时间片很大一部分都消耗在了malloc和free上。这可不是危言耸听标准库的默认内存管理器比如glibc的ptmalloc为了通用性和健壮性做了很多额外工作比如线程锁、内存合并、向操作系统申请/归还内存等。在单线程或者低并发场景下这些开销可以忽略不计但一旦进入高并发世界锁竞争和系统调用就成了性能的“阿喀琉斯之踵”。这时候“内存池”就从一个优化选项变成了一个必需品。它的核心思想很简单预分配一大块内存自己来管理分配和释放避免频繁向操作系统“伸手”更避免多线程争抢同一把“锁”。而“高并发内存池”就是专门为多线程环境设计的它的目标是在海量线程同时申请和释放内存时依然能保持高效和低延迟。这个项目就是要从零开始亲手打造一个这样的轮子。它不只是为了面试时能侃侃而谈更是为了让你深入理解内存管理的底层逻辑知道那些成熟的开源组件比如Google的tcmalloc、Facebook的jemalloc到底在解决什么问题。2. 核心设计思路三层架构解耦并发与效率一个优秀的高并发内存池绝不能是简单的一个大链表。我们需要一个清晰的分层架构将不同粒度的内存管理职责分开这样才能在并发、速度和内存利用率之间找到最佳平衡点。业界主流的设计包括我们这个项目借鉴的tcmalloc思想普遍采用三层结构Thread Cache线程缓存、Central Cache中心缓存和Page Cache页缓存。2.1 第一层Thread Cache —— 线程独享的“零锁”快车道这是应对高并发的第一道也是最重要的一道防线。它的设计目标是让每个线程绝大部分的内存申请和释放操作都在自己的“地盘”上完成完全无锁速度最快。2.1.1 自由链表与对齐规则Thread Cache本质上是一个哈希桶数组每个桶里挂着一个自由链表Free List。这个链表管理着一批固定大小的内存块。那么内存块大小如何设定这里就引入了“对齐”的概念。我们不能为每一个字节大小都单独设立一个桶那样桶的数量会爆炸。常见的做法是采用“分段对齐”或“大小类”策略。例如我们可以这样设计对于小内存比如小于等于256字节采用8字节对齐。那么桶的大小就是 8 16 24 32 ... 256。这样一共有 256 / 8 32 个桶。对于中等内存比如256B ~ 2048B采用更大的对齐数比如64字节。桶的大小就是 256 320 384 ... 2048。每个线程都有自己的Thread Cache对象它内部的这些自由链表就是该线程私有的。当线程需要申请内存时先根据申请大小向上对齐到某个桶的大小然后直接从这个桶的自由链表中弹出一个内存块。没有锁没有竞争就像从自己的口袋里掏钱一样快。释放内存也是同理直接还回对应的自由链表。注意这里有一个关键技巧为了能快速将释放的内存块挂回自由链表我们通常会在每个内存块的头部或尾部嵌入一个指针指向下一个空闲块。这就是所谓的“隐式链表”。申请时我们返回的是内存块的用户可用地址这个地址通常比实际分配的块地址偏移了几个字节用于存储管理信息。2.1.2 慢启动与批量转移如果线程自己的自由链表空了怎么办或者链表太长占用了太多内存怎么办这就引出了“慢启动”和“批量转移”机制。当Thread Cache的某个桶链表为空时它不会只向中央缓存要一个块而是要一小批比如一次要5-20个。反之当链表长度超过某个阈值比如一次批量转移数量的两倍它就会将一部分块比如一半还回中央缓存。这种批量化操作减少了层间交互的频率提升了整体效率。2.2 第二层Central Cache —— 全局共享的“物资中转站”Central Cache是全局唯一的所有线程共享。它的作用是承上启下从Page Cache申请大块内存以“页”为单位然后切分成固定大小的小块分配给各个Thread Cache同时也回收来自Thread Cache返还的过多内存块。2.2.1 桶结构与Span管理Central Cache同样是一个哈希桶结构桶的大小分类与Thread Cache完全一致一一对应。但桶里挂的不是单个内存块而是一个个Span对象。什么是Span它是内存管理的基本单位代表一段连续的、以页为大小的内存。一个Span可能包含多个页比如1页4KB或8KB取决于系统。每个Span对象管理着一大块连续内存这块内存已经被切分成了符合当前桶大小的多个小块并以自由链表的形式组织起来。当Thread Cache来申请内存时Central Cache从对应桶的某个Span的自由链表中拔出一批小块给它。由于所有线程都可能访问Central Cache所以这里的操作是需要加锁的。但我们的优化思路是锁的粒度要细。不是给整个Central Cache加一把大锁而是给每个桶单独加一把锁桶锁。这样不同大小的内存申请之间就不会相互阻塞。2.2.2 伙伴系统与内存合并的雏形Central Cache在向Page Cache申请内存时以及管理Span时已经开始为第三层的页级内存合并做准备了。它需要记录每个Span的起始页号、页数量等信息。当Thread Cache返还一批内存块使得某个Span的所有小块都空闲时Central Cache就可以将这个Span完整地归还给Page CachePage Cache则有机会将其与相邻的空闲Span合并成更大的连续空间减少内存碎片。2.3 第三层Page Cache —— 操作系统的“对接人”Page Cache是内存池与操作系统虚拟内存打交道的边界。它管理着以页为单位的大块内存。它的核心数据结构是一个哈希映射或更高效的结构如基于页号的映射用于记录每一页内存属于哪个Span。2.3.1 伙伴系统Buddy System的精髓Page Cache的核心算法是伙伴系统。它将所有空闲内存按照2的幂次页数1页2页4页8页...组织成不同的链表。当Central Cache申请N页内存时Page Cache会寻找一个大于等于N的最小2的幂次页块。如果找到则分配如果没找到则向上一级更大的2的幂次块寻找找到后将其对半分裂一部分用于分配另一部分挂入对应的空闲链表。例如申请3页内存。Page Cache会先找4页的链表如果有则取出一块4页的Span将其分裂成两个2页的伙伴Buddy。一个2页Span分配给Central Cache另一个2页Span挂入2页空闲链表。这个过程递归进行直到得到满足要求的最小块。2.3.2 合并与归还操作系统当Central Cache归还一个完整的Span给Page Cache时Page Cache会尝试将其与它的“伙伴”合并。伙伴是指起始地址相邻、大小相同、并且同属于一个更大2的幂次块分裂出来的两个Span。如果伙伴也是空闲的就将它们合并成一个更大的2的幂次页块并挂到更大的空闲链表中。这种合并能有效对抗外部碎片。如果合并后得到非常大的连续空闲内存块比如达到128页或一个预设阈值Page Cache可以考虑通过系统调用如madvise或VirtualFree/munmap将其真正归还给操作系统降低内存池的整体占用。这是一个平衡策略频繁归还会增加系统调用开销长期持有又会增加进程的内存占用。3. 关键数据结构与接口实现拆解理解了架构我们来看看支撑这个架构的核心数据结构如何实现。这里会涉及一些C技巧和底层内存操作。3.1 自由链表FreeList的巧妙实现自由链表需要支持快速的头插释放和头删申请。我们通常用一个指针_freeList指向链表头。但前面提到我们需要在内存块本身存储“下一个”指针。这里有一个经典技巧使用嵌入指针Embedded Pointer或联合体Union。// 方法一嵌入指针在对象内存前部 class FreeList { private: void* _freeList nullptr; // 指向第一个空闲块 public: void Push(void* obj) { // 将obj插入链表头部 *(void**)obj _freeList; // 在obj地址处写入_next指针 _freeList obj; } void* Pop() { if (_freeList nullptr) return nullptr; void* obj _freeList; _freeList *(void**)_freeList; // 从obj地址处读取_next指针 return obj; } };注意*(void**)obj这个操作它将obj这个地址解释为一个指向指针的指针然后解引用意思就是“把obj开始的sizeof(void*)个字节当作一个指针值来用”。这样我们就在用户不可见的块头部存储了链表指针而返回给用户的是obj地址本身用户可用空间。3.2 Span对象的设计Span是管理连续页内存的核心。struct Span { PAGE_ID _pageId 0; // 起始页号 size_t _n 0; // 页的数量 Span* _next nullptr; // 用于Central Cache或Page Cache中的链表 Span* _prev nullptr; size_t _objSize 0; // 被切分成的小对象大小Central Cache用 size_t _useCount 0; // 已被分配出去的小对象计数 FreeList _freeList; // 管理切分后的小对象自由链表Central Cache用 bool _isUsed false; // 是否已被使用 };_pageId是关键它是一个逻辑页号通过它和页大小可以计算出实际的起始地址。_useCount用于判断一个Span上的所有小块是否都已归还。当_useCount减为0时意味着这个Span可以回收给Page Cache。3.3 大小对齐与桶映射计算我们需要一个高效的函数将用户申请字节数bytes映射到对应的桶索引并计算出对齐后实际分配的大小alignSize。// 假设对齐规则128B按8对齐1024B按16对齐8KB按128对齐... size_t RoundUp(size_t bytes) { if (bytes 128) return _RoundUp(bytes, 8); else if (bytes 1024) return _RoundUp(bytes, 16); else if (bytes 8 * 1024) return _RoundUp(bytes, 128); // ... 更大的可能直接走Page Cache或系统堆 else return _RoundUp(bytes, 1 PAGE_SHIFT); // 按页对齐 } size_t Index(size_t bytes) { // 根据对齐规则计算索引建立映射表是更高效的做法 static std::arraysize_t, MAX_BYTES s_size_class_index; // 预计算填充s_size_class_index... return s_size_class_index[bytes]; }在实际项目中我们通常会预先计算好一个映射数组s_size_class_index将[1, MAX_BYTES]范围内的每一个字节数直接映射到桶索引用空间换时间保证O(1)的映射速度。3.4 线程局部存储TLS实现Thread Cache如何让每个线程都拥有自己独立的Thread Cache实例C11提供了thread_local关键字这是最简洁的方式。class ThreadCache { public: // 申请内存 void* Allocate(size_t size); // 释放内存 void Deallocate(void* ptr, size_t size); private: FreeList _freeLists[NUM_FREELIST]; // 自由链表数组 }; // 每个线程拥有自己的实例 static thread_local ThreadCache* tls_thread_cache nullptr; // 获取本线程的ThreadCache ThreadCache* GetThreadCache() { if (tls_thread_cache nullptr) { tls_thread_cache new ThreadCache(); } return tls_thread_cache; }这样每个线程第一次调用GetThreadCache()时都会创建自己的实例后续访问都是无锁的。注意线程退出时这个指针需要被清理否则会内存泄漏。我们可以实现一个线程退出回调或者依赖一些智能的生命周期管理但注意thread_local对象的析构顺序问题。4. 核心流程的代码级走读让我们跟踪一次典型的小内存申请和释放流程看看三层之间如何协作。4.1 申请内存流程用户调用void* ptr new MyObject;(假设MyObject大小为24字节)。编译器会调用operator new在我们的项目中这个全局的operator new被重载了它会调用我们内存池的公共分配接口。公共接口调用GetThreadCache()-Allocate(24)。ThreadCache::Allocate(24)计算对齐大小和对齐后大小。假设24字节按8对齐后还是24。通过Index(24)找到对应的自由链表桶假设索引是2。调用_freeLists[2].Pop()。如果成功直接返回这个内存块地址。流程结束全程无锁。如果失败链表为空进入FetchFromCentralCache流程。ThreadCache::FetchFromCentralCache(2, 24)计算本次要从Central Cache批量获取多少个对象。这里采用“慢启动”算法初始值可能是1之后每次短缺时按一定规则增加。调用CentralCache::GetInstance()-FetchRangeObj(start, end, batchNum, 24)。CentralCache::FetchRangeObj根据对象大小24找到对应的桶索引也是2。给这个桶加锁桶锁。遍历该桶下的Span链表寻找一个有足够空闲块的Span。从找到的Span的自由链表中弹出batchNum个对象通过输出参数start和end返回一个链表。更新该Span的_useCount。如果这个Span被取空了_useCount等于总块数可能需要将其从链表中移除或做标记。释放桶锁。返回实际获取到的对象数量。ThreadCache拿到这批对象链表start~end将第一个对象返回给用户。将剩余的对象start-next到end插入到自己的_freeLists[2]链表中丰富自己的缓存。如果Central Cache对应桶里也没有空闲的Span那么Central Cache需要向Page Cache申请新的内存。CentralCache::NewSpan(size_t n)(n是需要的页数)计算需要多少页才能切分出足够多的24字节对象。一页4KB能切出约170个可能只需要1页。调用PageCache::GetInstance()-NewSpan(n)。PageCache::NewSpan在对应n页大小的空闲链表中查找。如果找到直接返回这个Span。如果没找到向更大的2的幂次链表查找比如找2n页的。找到后将其分裂成两个n页的伙伴Span。一个返回另一个挂入n页空闲链表。如果一直找到最大块都没有则通过系统调用如mmap或VirtualAlloc向操作系统申请一大块内存比如一次申请128页将其组织成一个Span并插入对应链表然后递归执行上述分裂过程。更新页号到Span的映射关系_idSpanMap[pageId] span。Central Cache拿到新的Span后将其切分成一个个24字节的小块并串成自由链表挂到该Span的_freeList上。将这个Span挂到对应大小24字节的桶链表中。然后重复第6步从中分配对象给Thread Cache。4.2 释放内存流程用户调用delete ptr;。重载的operator delete调用内存池释放接口并传入对象大小现代C可以通过operator delete(void* ptr, std::size_t size)获取大小或者需要用户稍作封装。释放接口调用GetThreadCache()-Deallocate(ptr, 24)。ThreadCache::Deallocate根据大小24找到索引2。将ptr插入_freeLists[2]链表。检查_freeLists[2]的长度是否超过某个阈值比如之前慢启动达到的批量值。如果未超过释放结束。线程缓存自己消化了。如果超过则调用ListTooLong(_freeLists[2], 24)准备将一部分内存块还给Central Cache。ThreadCache::ListTooLong从自己的链表中取出一批对象比如一半构成一个链表。调用CentralCache::ReleaseListToSpans(ptrList, 24)。CentralCache::ReleaseListToSpans遍历链表中的每一个对象指针obj。关键步骤通过对象地址找到其所属的Span。这是通过PageCache维护的_idSpanMap实现的。计算obj的地址对应的页号pageId然后查映射表_idSpanMap[pageId]就能找到管理它的Span。将obj插入到其所属Span的自由链表中。该Span的_useCount减1。如果_useCount减为0说明这个Span的所有小块都已归还。此时Central Cache可以将这个完整的Span从桶链表中摘下调用PageCache::ReleaseSpanToPageCache(span)将其归还。PageCache::ReleaseSpanToPageCache尝试向前向后合并伙伴Span。计算当前Span的伙伴Span的页号检查伙伴是否空闲且在Page Cache管理中。如果伙伴空闲则将两个Span合并成一个更大的Span。将合并后的Span挂到对应大小的空闲链表。如果合并后得到的Span非常大比如达到了128页可以考虑调用munmap或VirtualFree将其归还给操作系统。5. 性能优化关键点与避坑指南实现一个能跑的内存池不难但实现一个高性能、稳定的内存池细节决定成败。5.1 锁粒度的极致优化从全局锁到桶锁再到无锁绝对避免全局锁这是高并发内存池的“死刑”。一旦用全局锁所有线程的内存操作都将串行化。Central Cache使用桶锁这是最关键的优化。为每一个大小类即每一个哈希桶配备独立的锁。这样申请8字节和申请64字节的线程完全不会阻塞。锁的竞争被限制在申请同一大小内存的线程之间而这部分竞争后续会被Thread Cache的批量操作进一步缓解。Thread Cache完全无锁依赖thread_local这是性能的保障。Page Cache的锁策略Page Cache的访问频率相对较低主要在大块内存分配/释放和合并时。可以对其内部数据结构如空闲链表、页号映射表使用一把读写锁或更精细的锁。由于伙伴系统的合并操作可能涉及不同大小的链表设计锁时需要小心死锁。一种常见做法是使用一把大锁保护整个Page Cache因为其操作频率低竞争通常不激烈。更复杂的实现可以为每一组伙伴链表或每一阶设置锁。5.2 内存碎片与利用率博弈内部碎片由于对齐策略我们分配的内存块可能比用户申请的大。比如申请24字节对齐到24字节假设8字节对齐内部碎片为0申请30字节对齐到32字节则有2字节内部碎片。这是用空间换时间管理效率和换空间连续性便于合并的权衡。对齐粒度越大内部碎片可能越多但管理开销越小。外部碎片指空闲内存总量足够但因为不连续而无法满足大块申请。伙伴系统通过按2的幂次分配和合并能有效减少外部碎片但无法完全消除。对于特别大的内存申请比如超过一个阈值如256KB很多内存池会选择直接调用mmap/VirtualAlloc分配用完后直接munmap/VirtualFree不进入池中管理避免大块内存占用池空间并产生碎片。利用率监控可以在Span中记录总块数和已用块数在Central Cache或全局层面统计不同大小类的内存利用率。对于长期利用率极低的桶可以考虑动态调整对齐策略或回收策略。5.3 针对常见场景的调优参数Thread Cache 慢启动阈值这个值决定了Thread Cache每次从Central Cache获取对象的数量增长快慢。初始值设小点如1增长因子可以设为1.5或2。太激进会导致单个线程占用过多内存太保守会增加访问Central Cache的频率。Thread Cache 最大缓存长度即ListTooLong的阈值。这个值通常与慢启动达到的稳定值相关可以是其2倍。它控制了线程私有的“惰性”值越大线程越倾向于持有内存内存释放回全局池的速度越慢但线程自身分配速度越快。Page Cache 向操作系统申请的块大小一次申请多大如128页需要平衡系统调用开销和内存占用量。申请块越大平均每次系统调用的开销越小但可能导致内存池持有过多暂时用不到的内存。Page Cache 归还操作系统的阈值当空闲块连续多大时如256页才考虑归还给操作系统。频繁归还会增加munmap调用不归还会使进程RSS常驻内存集居高不下。5.4 调试与排查技巧内存池的Bug往往表现为难以重现的崩溃、内存损坏或泄漏。以下工具和技巧至关重要地址消毒剂AddressSanitizer, ASan在开发阶段务必开启ASan。它能检测出堆缓冲区溢出、使用释放后内存、重复释放等大部分内存错误。编译时加上-fsanitizeaddress选项。自定义的调试信息在Span或内存块头部添加魔术字Magic Number、分配线程ID、分配时间戳等信息。在释放时进行校验可以快速定位哪次分配的内存被非法写坏了。断言Assert在关键位置加入断言例如检查自由链表指针是否有效、Span的_useCount是否溢出等。日志系统实现一个轻量级、可分级如Debug、Info、Error的日志系统记录关键事件如向操作系统申请/释放大内存、Span分裂合并、Thread Cache批量转移等。通过日志可以复盘异常情况下的内存池状态。单元测试与压力测试编写多线程随机大小、随机生命周期的分配/释放测试让线程数远超CPU核心数长时间运行观察内存增长是否稳定以及性能是否符合预期。6. 与现有开源方案tcmalloc/jemalloc的对比与思考自己实现一遍后再去看tcmalloc或jemalloc的源码或设计文档你会更有感触。tcmalloc我们的项目主要借鉴了tcmalloc的早期设计思想。现代的tcmalloc更加复杂和精细例如引入了“转移缓存”Transfer Cache作为Thread Cache和Central Cache之间的又一个层级进一步减少了锁竞争。它对大小类的划分也更细并且针对小对象256B有极其优化的路径。其Page Heap对应我们的Page Cache管理也更为复杂。jemallocjemalloc的设计哲学略有不同。它采用了“arena”的概念每个arena管理独立的内存区域线程会绑定到特定的arena这同样是为了减少竞争。jemalloc在碎片控制上口碑更好尤其对于长时间运行、内存分配模式多变的应用程序。我们的“轮子”的价值虽然比不上这些工业级产品的成熟度和优化深度但自己实现一遍的价值在于彻底理解原理纸上得来终觉浅绝知此事要躬行。通过编码你会对每一层的数据结构、锁竞争点、碎片来源有刻骨铭心的认识。定制化潜力你可以根据自己应用的特定内存分配模式例如你知道你的应用只频繁分配几种固定大小的对象进行极端优化这可能比通用内存池更高效。面试与学习的黄金项目它几乎涵盖了C面试的所有高频考点多线程、锁、数据结构、内存管理、系统编程、性能优化。能清晰阐述这个项目胜过死记硬背十道八股文。最后一个提醒在生产环境中除非你有极强的信心和充分的测试否则建议使用成熟的tcmalloc或jemalloc。它们经过了Google、Facebook等超大规模服务的验证。我们这个项目的目的是学习和理解是为了在必要时有能力对其进行定制或深度调优而不是盲目地替换掉久经考验的基础组件。把轮子造一遍是为了更好地使用和选择轮子。