项目背景

这个项目的原型是google的开源项目tcmalloc 线程缓存的malloc,可以实现多线程内存管理，用于替代系统的内存分配相关的函数，go语言直接使用它作为自己内存分配器。

内存池技术通过预分配和复用内存块，减少频繁调用系统API（如malloc/free）带来的性能损耗。高并发场景下，传统内存管理存在锁竞争和内存碎片问题，如图1蓝色区域就是外碎片问题，内碎片问题是因为内存对齐等因素而未使用的内存空间，内存池通过线程本地缓存和分层设计提升分配效率。

图1：使用分配和释放进程地址空间

项目整体架构

• 本项目主要分为三层架构：threadcache、centralcache、pagecache

• 分层缓冲：从快到慢，从小到大的三层缓存结构

• 无锁优化：threadcache无锁，减少锁竞争

• 批量操作：减少跨层访问次数

• 内存复用：回收的内存优先复用，减少系统调用

图2：高并发内存池三层架构

• 分配流程

图3：分配流程

分配流程遵循 “Threadcache → Centralcache → Pagecache → 操作系统” 的层级结构，优先从离线程最近的缓存中分配，只有当前层无法满足需求时，才逐级向上申请内存。

• 回收流程

图4：回收流程

回收流程遵循 “Threadcache → Centralcache → Pagecache” 的逐级归还机制。小对象优先回收到线程本地缓存中，提高效率；当缓存过多或整个 span 空闲时，再逐级归还并合并内存，降低碎片率。

核心设计

• 对齐规则与内碎片控制问题

因为内存对齐，实际分配的大小往往比用户请求大，这里就会产生一定内碎片问题，为了平衡管理效率和内存浪费，采用分段对齐策略：

图5：分段对齐策略

下面代码可以实现向上完整取整，实际13byte, 向上取整16byte。

static inline size_t _Index(size_t bytes,size_t align_shift)
    {
        return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;  
    }

假设 bytes = 13, alignNum = 8:

// 步骤分解:
alignNum = 8 = 0b00001000
alignNum - 1 = 7 = 0b00000111
~(alignNum - 1) = ~7 = 0b11111000   // 对齐掩码

bytes + alignNum - 1 = 13 + 7 = 20 = 0b00010100

// 与运算:
0b00010100 (20)
& 0b11111000 (~7)
= 0b00010000 (16)

ThreadCache：线程本地缓存

每个线程独享的无锁缓存，处理小对象（如<256KB）的快速分配/释放。采用自由链表（FreeList）管理不同大小的内存块，避免跨线程竞争。

class ThreadCache
{
    public:
        void* Allocate(size_t size);
        void Deallocate(void*ptr,size_t size);
        void* FetchfromCentralCache(size_t index,size_t size);
        void listToolong(FreeList& list,size_t size);//合并内存        
    private:
        FreeList _freelist[NFREELISTS];
};
// Linux GCC/Clang 使用 __thread
// 不同线程访问到的是不同的“那一份”
// 线程之间互不影响，不需要锁
extern  __thread ThreadCache* pTLSThreadCache;

图6：threadcache结构图

threadcache解决的是锁竞争的问题，每个thread独占一个cache,这和其他内存池的不一样的地方

在多线程环境下，锁的产生是因为多个线程要竞争访问同一块共享数据。使用 __thread ThreadCache* pTLSThreadCache 的目的，是把“线程私有的分配/释放上下文”挂在 TLS 上，从而实现每个线程一份 ThreadCache。这在高并发内存分配器里是核心设计点。

• 慢启动与批量申请

  void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
  {
      // 满开始的反馈调节算法
      // NumMoveSize(size) 给出“天花板”，GetMaxsize() 给出“当前自适应上限”,
      size_t batchnum = std::min(
                    _freelist[index].GetMaxsize(), 
                    SizeClass::NumMoveSize(size));
      // 如果相等的话，就说明下回可能还需要，这里就将最大值加1
      if(_freelist[index].GetMaxsize() == batchnum)
      {
      _freelist[index].GetMaxsize() += 1;
      }
  }

• _freelist[index].GetMaxsize()：当前自由链表允许单次批量申请的最大值（动态自适应，初始通常为1）。

• SizeClass::NumMoveSize(size)：根据对象大小计算出的“理论最佳批量数”（天花板，防止一次申请过多）。

• 取两者较小值作为本次实际申请的数量 → 避免超出系统限制。

其实也就是小对象多申请，大对象少申请。类似于TCP网络拥堵控制算法。

CentralCache：中心缓存

• 整体结构

全局共享的中心资源池，采用桶锁（每个大小类独立锁）减少冲突。当ThreadCache不足时，从CentralCache批量获取内存块；释放时归还多余内存块。

centralcache也是一个哈希桶结构，他的哈希桶的映射关系跟threadcache是一样的。不同的是他的每个哈希桶位置挂是spanList链表结构，不过每个映射桶下面的span中的大内存块被映射关系切成了一个个小内存块对象挂在span的自由链表中。

• span结构

struct span
{
    size_t _pageId;//页号
    size_t _n;//页的数量，某个 span 覆盖了多少页。
    span*_next=nullptr;//span的双向链表结果
    span*_prev=nullptr;
    size_t _usecount;//切好的小块内存，被分配给thread cache 如果_usecount==0，说明所有的小块内存全部回收了
    size_t _objectsize=0;
    void* _freelist;//切好的小块内存的回收的自由链表
    bool _isUse=false;//是否在被使用
};

span单位是页，单位是一般为8kb(2^13)，这里就存在一个问题：

如果是32位机器：2^32/2^13=2^19页，如果是64位机器：2^64/2^13=2^51页，页号的类型的选择就需要选择了，这里经过查阅发现，size_t的类型大小随着操作系统的位数变化而变化，32位操作系统->32位的size_t,所以这里先不变化，size_t满足不同系统下页号的存储。

• 从span切分对象

start = _span->_freelist;
end = start;
while(i < batchnum-1 && Nextobj(end))
{
    end = Nextobj(end);
    i++;
    actualnum++;
}
_span->_freelist = Nextobj(end);
Nextobj(end) = nullptr;
_span->_usecount += actualnum;

当 centralcache 从 pagecache 获取到一个全新的 span（连续若干页内存）时，这个 span 还没有被切分成小块对象。此时需要将其大块内存按指定的对象大小（size）切割成一个一个的小块，并用每个小块的前 4/8 字节作为 next 指针将它们串联成一个自由链表，挂到 span->_freelist 上。

• 回收对象到span

void* next = Nextobj(start);                     // 保存下一个对象
span* span = PageCache::GetInstance()->MapobjectSpan(start);
Nextobj(start) = span->_freelist;                // 当前对象的 next 指向原链表头
span->_freelist = start;                         // 新链表头指向当前对象
span->_usecount--;                               // 减少使用计数

当 threadcache 批量归还一批对象时，centralcache 需要将这些对象重新挂回它们原本所属的 Span 中。每个对象通过其内存地址找到对应的 span（利用页号到 span 的映射）。

如果某个 span 的 _usecount 变为 0，说明该 span 的所有对象都已归还，centralcache 会将该 span 从当前桶中移除，并整体归还给 pagecache，以便 pagecache 进行相邻空闲页的合并。

PageCache：页级缓存

以页（如4KB）为单位管理大内存，通过span（连续页的集合）进行分配。负责span的切分、合并及向系统申请/释放内存，使用全局锁保护结构。

当centralcache向pagecache申请内存时，pagecache先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。比如：申请的是4页page，4页page后面没有挂spam，则向后面寻找更大的span，假设在10页page位置找到一个span，则将10页page span分裂为一个4页page span和一个6页page span。

如果找到spanList[128]都没有合适的span，则向系统使用mmap、brk或者是VirtualAlloc等方式申请128页page span挂在自由链表中，再重复1中的过程。

• 分配span

span* PageCache::NewSpan(size_t k)   // 获取一个 k 页的 span
{
    assert(k > 0);
    // 大于 128 页：直接向系统申请
    if (k > NPAGES - 1) {
        void* ptr = SystemAlloc(k);
        span* _span = _spanpool.New();
        _span->_pageId = (size_t)ptr >> PAGE_SHIFT;
        _span->_n = k;
        _idSpanMap[_span->_pageId] = _span;
        return _span;
    }
    // 1. 先检查对应页数的桶是否有空闲 Span
    if (!_spanlist[k].Empty()) {
        return _spanlist[k].Popfront();
    }
    // 2. 向更大页数的桶寻找，找到后切分
    for (size_t i = k + 1; i < NPAGES; i++) {
        if (!_spanlist[i].Empty()) {
            span* nspan = _spanlist[i].Popfront();   // 大 Span
            span* kspan = _spanpool.New();           // 切出来的小 Span
            kspan->_pageId = nspan->_pageId;
            kspan->_n = k;
            nspan->_pageId += k;                      // 大 Span 起始页号后移
            nspan->_n -= k;                           // 大 Span 剩余页数
            _spanlist[nspan->_n].PushFront(nspan);    // 剩余部分放回对应桶
            // 记录大 Span 的首尾页映射（用于后续合并）
            _idSpanMap[nspan->_pageId] = nspan;
            _idSpanMap[nspan->_pageId + nspan->_n - 1] = nspan;
            // 记录小 Span 的所有页映射（用于 Central Cache 回收时定位）
            for (size_t j = 0; j < kspan->_n; j++) {
                _idSpanMap[kspan->_pageId + j] = kspan;
            }
            return kspan;
        }
    }
    // 3. 所有桶都没有空闲，向系统申请 128 页大块
    span* bigspan = _spanpool.New();
    void* ptr = SystemAlloc(NPAGES - 1);
    bigspan->_pageId = (size_t)ptr >> PAGE_SHIFT;
    bigspan->_n = NPAGES - 1;
    _spanlist[bigspan->_n].PushFront(bigspan);
    // 递归调用，这次会走切分逻辑
    return NewSpan(k);
}

三步分配策略：

• 直接分配：如果请求页数超过 128 页（k > NPAGES-1），直接向操作系统申请（SystemAlloc），不经过 Page Cache 的桶管理。

• 桶内查找与切分：先从 _spanlist[k] 中取（精确匹配）。如果没有，则从 k+1 到 127 号桶依次查找第一个非空桶。找到一个大 Span 后，将其分裂成两个：一个恰好 k 页（返回给 Central Cache），另一个剩余页数（挂回对应的桶）。分裂后需要维护 页号到 Span 的映射：大 Span 只记录首尾页（用于后续合并时快速前后查找）。小 Span 记录其所有页的映射（因为 Central Cache 回收时可能从任意页号来查找 Span）。

• 系统补充：如果所有桶都为空，则向系统申请一个 128 页的超大 Span，挂到 _spanlist[127]，然后递归调用 NewSpan(k)，必然命中切分逻辑

• 页号到span的映射

class RadixPageMap
{
private:
    static constexpr size_t ROOT_BITS = 12;
    static constexpr size_t MID_BITS = 12;
    static constexpr size_t LEAF_BITS = 11;
    static constexpr size_t ROOT_LENGTH = 1 << ROOT_BITS;
    static constexpr size_t MID_LENGTH = 1 << MID_BITS;
    static constexpr size_t LEAF_LENGTH = 1 << LEAF_BITS;
    struct Leaf
    {
        std::atomic<void*> values[LEAF_LENGTH];
    };

    struct MidNode
    {
        std::atomic<Leaf*> leaves[MID_LENGTH];
    };

    struct RootNode
    {
        std::atomic<MidNode*> children[ROOT_LENGTH];
    };

为了替代 unordered_map 在热路径中的哈希查找开销，我将页号到 Span 的映射改成了固定层级的基数树存储结构，本质上就是维护一张 PAGE_ID -> Span* 的稀疏映射表。

• 回收span与合并

void PageCache::ReleaseSpanToPagecache(span* span) {
    // 1. 超大Span直接归还系统
    if (span->_n > 128) {
        SystemFree((void*)(span->_pageId << PAGE_SHIFT));
        return;
    }
    // 2. 清除旧映射
    for (size_t i = 0; i < span->_n; ++i)
        _idSpanMap.erase(span->_pageId + i);    
    // 3. 向前合并（反复）
    while (TryMergePrev(span)) { /* 合并并继续 */ }    
    // 4. 向后合并（反复）
    while (TryMergeNext(span)) { /* 合并并继续 */ }
    // 5. 挂回桶，标记空闲
    _spanlist[span->_n].PushFront(span);
    span->_isUse = false;
    // 6. 重建映射
    for (size_t i = 0; i < span->_n; ++i)
        _idSpanMap[span->_pageId + i] = span;
}

• 超过128页的Span直接归还操作系统。

• 清理当前Span的所有旧映射。

• 向前合并：反复检查前一页所属Span是否空闲且合并后不超128页，若是则合并（更新起始页号、累加页数），并移除被合并Span。

• 向后合并：类似地，反复合并后续空闲Span。

• 合并完成后，将新Span挂回对应页数的桶，标记为空闲，并重建所有页的映射（确保后续地址能正确找到Span）。

性能测试结果

在性能测试阶段，我使用 4 个线程进行并发分配与释放测试。每个线程执行 10 轮操作，每轮进行 10000 次小对象分配与释放，总计约 400000 次操作。测试结果表明，根据测试结果计算，高并发内存池相比系统默认内存分配器的综合性能提升约为 7.5～7.7 倍。

测试场景	高并发内存池消耗	malloc/free消耗	性能提升
第一组4线程测试	21ms	161ms	约7.67倍
第二组4线程测试	245ms	1848ms	约7.54倍

项目中遇到的问题

• 批量申请优化

• 采用批量申请与慢启动策略，ThreadCache 按 size class 成批从 CentralCache 获取对象，减少小对象逐次申请带来的共享层锁竞争与访问频率。

• Span 合并后映射更新问题

合并Span需同步更新所有子Span的映射关系，通过遍历Radix树对应节点解决。

• unordered_map 到 Radix Tree 的优化

哈希表在大量页号时性能下降，基数树通过固定层级（如3层）实现稳定查询时间。

后续优化

• 扩展性：支持动态SizeClass调整
• 后续方向：实现自适应批量申请策略，同时优化PageCache的锁竞争（如分层锁）

附件

• 项目代码：https://github.com/bbbbkkk/concurrentpool