从零实现高并发内存池

目录

一、项目介绍

二、什么是内存池？

1.池化技术

2.内存池

3.内存池解决的问题

三、malloc本身就是内存池

四、定长内存池

五、高并发内存池整体框架

六、thread cache

七、central cache

八、page cache

---

一、项目介绍

当前项目是实现一个高并发的内存池，他的原型是google的一个开源项目tcmalloc，tcmalloc全称 Thread-Caching Malloc，即线程缓存的malloc，实现了高效的多线程内存管理，用于替代系统的内存 分配相关的函数（malloc、free）。 我们这个项目是把tcmalloc最核心的框架简化后拿出来，模拟实现出一个自己的高并发内存池，目的就 是学习tcamlloc的精华，这种方式有点类似我们之前学习STL容器的方式。当前另一方面，难度的上升，我们的收获 和成长也是在这个过程中同步上升。 另一方面tcmalloc是全球大厂google开源的，可以认为当时顶尖的C++高手写出来的，他的知名度也是 非常高的，不少公司都在用它，Go语言直接用它做了自己内存分配器。所以很多程序员是熟悉这个项 目的，那么有好处，也有坏处。好处就是把这个项目理解扎实了，会很受面试官的认可。坏处就是面试 官可能也比较熟悉项目，对项目会问得比较深，比较细。如果你对项目掌握得不扎实，那么就容易碰钉子。

二、什么是内存池？

1.池化技术

要明白什么是内存池，先要明白池化技术：池化技术是指程序现象系统申请过量的资源，然后自己管理的一种技术。之所以要有池化技术是因为每次向系统申请资源都会由开销，不如一次性申请过量资源，提高程序效率。在计算机中，有很多使用“池”这种技术的地方，除了内存池，还有连接池、线程池、对象池等。以服务 器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端 的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。

2.内存池

内存池指的就是预先喜爱那个操作系统申请一块足够大的内存，当程序想要申请内存时，不是直接向操作系统申请内存，而是从内存池中获取。同时，程序释放内存时也不是将内存返还给操作系统，而是将内存返还给内存池。等程序退出时，内存池才将自己管理的内存全部释放。

3.内存池解决的问题

内存池主要解决的是效率问题和内存碎片问题。效率问题在池化技术中已经讲过，内存碎片问题场景如下：进程地址空间被申请了多块空间，一段时间后有些空间被释放了，但是有些空间仍在使用中，这就会导致许多不连续的内存空间，即内存碎片（外碎片）。内存碎片会导致程序无法申请连续大块的内存空间。

三、malloc本身就是内存池

C/C++中动态申请内存是通过malloc来完成的，但实际上malloc并不是直接从堆上申请空间的，malloc本身也是一个内存池。使用malloc动态申请内存时，它会向操作系统申请一块较大的内存空间，再将该内存空间分配给程序使用。malloc的实现方式有很多种，不同平台的的实现方式也不同。

既然malloc本身已经是一个内存池，那为什么还要学习tcmalloc呢？

tcmalloc相比于malloc更加强大：

• 高性能：tcmalloc通过减少内存占用和优化内存分配策略，提高了内存分配的效率和速度，特别是在高并发情况下，能够显著提升性能并降低系统的负载。
• 低锁竞争：tcmalloc采用线程局部缓存（Thread Local Cache）策略，为每个线程维护一个小型的内存池，使得小对象的分配和释放都可以在本地完成，避免了全局锁的竞争，从而提高了并发性能。
• 减少内存碎片：tcmalloc通过高效的内存回收策略和大小类映射（size-class mapping）策略，有效减少了内存碎片，提高了内存利用率。
• 额外功能：tcmalloc还提供了一些额外的功能，如内存泄漏检查、内存使用统计等，有助于开发者更好地管理和优化内存使用。

四、定长内存池

定长内存池是一种高效管理和分配固定大小内存块的技术，也是是一种简单内存池。学习定长内存池可以了解到简单内存池是如何控制的，为后续的tcmalloc的学习奠定基础。

定长内存池核心思想：

利用malloc申请一个大块内存，对该内存进行分配与管理，释放内存时将释放的内存使用自由链表进行链接管理。自由链表是一个指针，指向第一个释放的内存块，此后每个内存块的前4/8个字节存储后续被释放内存块的地址，形成链表。

代码框架：

定长内存池是一个类模板，由传入的模板类型T决定每次分配的内存大小是多少。成员变量包含大块内存_memory、自由链表_freeList和大块内存剩余可分配字节数_remainBytes。成员函数包含申请内存函数New和释放内存函数Delete。

代码实现细节：

• _memory的类型是char* _memory，这样便于内存分配后通过指针加sizeof(T)使得_memory指针后移。因为分配大块内存分割并非真正地将大块内存切成许多小块内存，而是利用解引用不同指针类型访问的字节数不同这一特性来分配大块内存，T* obj = (T*)_memory，尽管指针obj指向的仍是大块内存_memory，但是解引用obj时只能访问sizeof(T)个字节，即分配到的字节数。分配完成后将_memory+=sizeof(T)。
• _freeList的类型是void* freeList，因为使用void*可以使自由链表兼容任意数据类型的内存块，即使定长内存池的设计是针对特定类型T，但是使用void*更加灵活。
• _remainBytes的存在是为了解决当大块内存剩余内存不够分配一个T类型大小字节时，重新利用malloc向系统申请大块内存给_memory（对于余下的不够分配的一个T类型大小字节的空间，无需处理，丢弃即可）。
• 释放的内存块头插到自由链表中，关键是如何取到释放内存块的前4/8个字节用于存储下一个释放内存快的地址。使用*(int*)obj是访问释放内存块的前4个字节，仅在32位平台下适用，因此要使用*(void**)obj，访问的字节数是void*类型大小，32位下访问4字节，64位下访问8字节。
• 申请内存首先要先从自由链表中取内存，这样更加高效地利用内存空间。
• 如果T的类型大小小于一个指针的大小，那么分配的内存块在释放进入自由链表时,就无法利用前4/8个字节存储下一个释放内存块的地址了。因此当T类型大小为char等此类大小小于一个指针的类型，至少为它们分配一个指针类型大小的内存块。
• 对于已经一段已经分配好的内存空间或者即将释放的内存空间，通常要调用定位new表达式和显示调用析构函数用于初始化内存空间和清理内存空间。

定长内存池源码： 

#pragma once
#include <iostream>
using std::cout;
using std::endl;template<class T>
class ObjectPool
{
private:char* _memory = nullptr;//大块内存void* _freeList = nullptr;//自由链表size_t _remainBytes = 0;//大块内存剩余可分配字节数
public://申请内存T* New(){T* obj = nullptr;if (_freeList){obj = (T*)_freeList;_freeList = *(void**)obj;//void* next = *((void**)_freeList);//obj = (T*)_freeList;//_freeList = next;}else{if (_remainBytes < sizeof(T))//剩余内存不够分配一个T类型大小字节时，重新申请大块内存给_memory{_memory = (char*)malloc(128 * 1024);//每次分配128字节的大块内存if (_memory == nullptr)//malloc失败：抛异常throw std::bad_alloc();_remainBytes = 128 * 1024;}obj = (T*)_memory;//如果T的类型大小小于一个指针的大小，那么分配的内存块在释放进入自由链表时,就无法利用前4/8个字节存储下一个释放内存块的地址了//因此当T类型大小为char等此类大小小于一个指针的类型，至少为它们分配一个指针类型大小的内存块size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);_memory += objSize;_remainBytes -= objSize;}//定位new表达式初始化分配好的内存空间new(obj)T;return obj;}//释放内存void Delete(T* obj){//显示调用析构函数清理即将释放的内存空间obj->~T();//释放的内存块头插到自由链表中//*(int*)obj = nullptr;   仅在32位平台下适用*(void**)obj = _freeList;_freeList=obj;}
};

定长内存池性能测试代码：

#include "ObjectPool.h"
#include <vector>
#include <ctime>
struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode():_val(0), _left(nullptr), _right(nullptr){}
};
void TestObjectPool()
{// 申请释放的轮次const size_t Rounds = 5;// 每轮申请释放多少次const size_t N = 100000;size_t begin1 = clock();std::vector<TreeNode*> v1;v1.reserve(N);for (size_t j = 0; j < Rounds; ++j){for (int i = 0; i < N; ++i){v1.push_back(new TreeNode);}for (int i = 0; i < N; ++i){delete v1[i];}v1.clear();}size_t end1 = clock();ObjectPool<TreeNode> TNPool;size_t begin2 = clock();std::vector<TreeNode*> v2;v2.reserve(N);for (size_t j = 0; j < Rounds; ++j){for (int i = 0; i < N; ++i){v2.push_back(TNPool.New());}for (int i = 0; i < N; ++i){TNPool.Delete(v2[i]);}v2.clear();}size_t end2 = clock();cout << "new cost time:" << end1 - begin1 << endl;cout << "object pool cost time:" << end2 - begin2 << endl;
}
int main()
{//ObjectPool<int> pool;//int* ptr1 = pool.New();//int* ptr2 = pool.New();//*ptr1 = 10;//*ptr2 = 20;//pool.Delete(ptr1);//pool.Delete(ptr2);TestObjectPool();return 0;
}

五、高并发内存池整体框架

在多核多线程环境下申请内存时一定会有锁竞争问题，在这样的环境下使用malloc申请内存时就需要加锁。但是我们这个以tcmalloc为原型的高并发内存池项目会在多核多线程的环境中更胜一筹。

高并发内存池的整体框架如下，由三个部分组成：

• thread cache：每有一个线程就创建一个线程缓存thread cache，用于申请小于256KB的内存，这样的话多线程申请内存就不需要加锁，非常高效。
• central cache：中心缓存central cache是所有线程共享的，thread cache按需从central cache中获取内存，central cache在合适时机也会回收thread cache中的内存，避免一个线程占用太多内存导致其他线程内存不足。thread cache从central cache获取内存是存在竞争的，需要加锁，但是由于central cache使用的是桶锁，并且只有当thread cache中内存不足时才会从central cache中获取内存，因此这里竞争不是很激烈。
• page cache：页缓存page cache中的内存是以页为单位进行存储和分配的。当central cache中的内存不足时，会向page cache获取内存。page cache会分配出一定数量的page，并将这些page切割成定长大小的小块内存，分配给central cache。当一个span的几个跨度页的对象都回收以后，page cache会回收central cache中满足条件的span对象，并且合并相邻的页，组成更大的页，以此减少内存碎片。

六、thread cache

thread cache整体结构

thread cache是哈希桶结构的，每个桶存放的是一个按内存对齐规则映射的自由链表。thread cache中有208个自由链表，因此要使用一个数组管理这些自由链表。thread cache只支持申请小于等于256KB的内存空间，不同于定长内存池，thread cache不知道用户要申请多大的内存空间（1 ~ 256*1024字节都有可能），因此thread cache必须建立存放不同大小内存块的不同自由链表，而1 ~ 256*1024需要创建262144个不同的自由链表，这样开销非常大。thread cache使用了内存对齐规则来解决这个问题。

内存对齐规则

申请内存空间为size，size范围是[1,128]向8byte对齐，1~8byte都申请为8byte；9~16byte都申请为16byte；17~24byte都申请为24byte；......；121~128byte都申请为128byte。有0~15号共计16个自由链表。内存浪费率最高为7/8=87.5%。

size范围是[128+1,1024]向16byte对齐，129~144byte都申请为144byte；145~160byte都申请为160byte；161~176byte都申请为176byte；......；1009~1024byte都申请为1024byte。有16~71号共计56个自由链表。内存浪费率最高位为15/144=10.38%。

size范围是[1024+1,8*1024]向128byte对齐，1025~1152byte都申请为1152byte；1153~1280byte~都申请为1280byte；1281~1408byte都申请为1408byte；......；8961~8192byte都申请为8192byte。有72~127号共计56个自由链表。内存浪费率最高为127/1152=11.0%。

size范围是[8*1024+1,64*1024]向1024byte对齐，8193~9216byte都申请为9216byte；9217~10240byte都申请为10240byte；10241~11264byte都申请为11264byte；......；64513~65536byte都申请为65536yte。有128~183号共计56个自由链表。内存浪费率最高为1023/9216=11.1%。

size范围是[64*1024+1,256*1024]向8*1024byte对齐，65537~73728byte都申请为73728byte；73729~81920byte都申请为81920byte；81921~90112byte都申请为90112byte；......；258049~262144byte都申请为262144byte (256KB)。有184~207号共计24个自由链表。内存浪费率最高为8*1024/73728=11.1%。

综上所述，使用上述的内存对齐规则后自由链表数量从262144减少到了208，大大减少了开销。但随之而来问题是，内存对齐后，例如原本只要开辟1字节空间，对齐到8字节后多开了7字节，这7字节就是内存碎片（内碎片），被浪费掉。好在上述内存对齐规则的内存浪费率很小，除了申请[1,128]内存空间时内存浪费率最高为87.5%，其余的内存浪费率控制在最多10%左右。

thread cache核心思想：

申请内存

线程申请内存时首先根据申请内存的大小size映射找到要从哪个自由链表中申请内存块，如果该自由链表_freeList[i]中不为空，就从中获取内存块，如果_freeList[i]为空，thread cache就要从central cache中获取一定数量的内存块插入到该自由链表中，再从_freeList[i]中获取内存块。

释放内存

当thread cache的某个自由链表中的对齐内存块太多时，超过thread cache向central cache一次获取到的对齐内存块数量n时（此处的n是thread cache中自由链表用于配合慢开始算法的maxsize，并非真正的thread cache一次能获取到的对齐内存块数量），要将n个对齐内存块返还给central cache。

thread cache代码框架

thread cache是一个类，包含的成员变量是一个存储自由链表的数组_freeLists[208]，包含成员函数：申请内存函数Allocate、释放内存函数Deallocate、从中心缓存中获取内存函数FetchFromCentralCache。thread cache类外还有一个TLS声明的线程缓存对象指针，使用TLS声明的变量仅在当前线程内是可全局访问的，可以保证变量在每个线程中是独立的，这样就可以避免使用加锁的方法保证数据独立，以此实现每一个线程都有独立的线程缓存。

在公共头文件Common.h中还要实现一些常用的方法：

• 取出内存块前4/8个字节函数NextObj；
• 管理自由链表的类FreeList，包含的成员变量是一个自由链表_freeList，包含的成员函数有自由链表头插内存块Push、自由链表头删内存块Pop、自由链表判空Empty；
• 内存对齐映射规则类SizeClass，该类其实是将所有关于内存对齐映射的函数统一封装起来，实际使用时并不需要实用类对象调用成员函数，直接将成员函数设置为静态类型。包含计算内存对齐后具体分配多少字节内存空间（对齐块、对象）函数RoundUp、计算内存对齐后所属自由链表序号的函数Index。

七、central cache

central cache整体结构

central cache也是哈希桶结构的，每个桶位置存放的是按内存对齐规则映射的span链表，    central cache中的内存对齐规则和thread cache中的规则相同，这样可以保证当thread cache中第n个自由链表为空时向central cache中的获取内存块时正好也是从第n个span链表中获取。span链表是一个带头双向循环链表，存放的是span对象。span对象本质是一个结构体，用于管理以页为单位的大块内存，包含一个存放对齐内存块的自由链表，计数器use_count记录当前span对象分配出去了多少个对齐内存块，以及大块内存起始页号、页的数量等信息。

每个span链表中的span对象管理的页数量都不同，因为对于较小的对齐内存块，span对象仅需一个页就可以切出许多对齐内存块，对于较大的对齐内存块，span对象需要许多页才能组成一个对齐内存块。假设一页的大小是8KB，对于8byte的对齐内存块，仅需一页就可以切割出1024个8Byte大小的对齐内存块；对于256KB的对齐内存块，需要32页才能组成一个256KB大小的对齐内存块。

central cache核心思想：

申请内存

central cache中有208个span链表，对应thread cache中的自由链表。当thread cache向central cache中获取内存时，thread cache中哪个自由链表没有对齐内存块时，就到central cache中对应的span链表中获取内存，如果span链表中存在自由链表不为空的span对象，就从该span对象的自由链表中获取对齐内存块，useCount++，获取数量由一种类似于网络tcp协议中拥塞控制的慢开始算法决定；如果span链表中没有span对象或者span对象的自由链表都为空，就要向page cache获取一个span对象。

释放内存

当thread cache中的对齐内存块过多时，就要将内存对齐块还给span对象，每还回来一个内存对齐块给span对象，useCount--，当useCount减至0时就表示所有的内存对齐块都还给span对象了，就可以释放该span对象，返还给page cache，page cache会将前后相邻的空闲页进行合并。

thread cache从central cache获取内存块这个过程是要加锁的，在central cache中的每个桶中都加锁，即桶锁，提高效率。

central cache代码框架

central cache是单例模式

八、page cache

page cache整体结构

page cache也是哈希桶结构，每个桶位置存放的是span链表。但是page cache不同于thread cache和central cache的映射规则，page cache中每个桶位置的span链表是和桶位置直接映射的，即1号桶的span链表存放的都是1页的span对象，8号桶的span链表存放的都是8页的span对象，n号桶的span链表存放的都是n页的span对象。总共有128个桶，即span对象最大存储128页内存空间，因为最大申请的对齐内存块是256KB，128页（一页是8KB）共1024KB，可以分成4个对齐内存块，正好合适。另外page cache中span链表的span对象不含存放对齐内存块的自由链表，当span对象被分配给central cache后，central cache会将这些span对象分割成对齐内存块组成自由链表。

page cache核心思想：

申请内存

当central cache向page cache申请span对象时，首先要确定申请多少页的span对象，申请n页的span对象就到page cache的n号桶中寻找span对象，如果n号桶中没有span对象就要到更大号的桶中寻找span对象并将该span对象分割。例如central cache申请一个2页的span对象，如果page cache的2号桶中有span对象就分配给central cache，如果没有就向3号、4号......128号桶中寻找span对象，假设在5号桶中查找到了span对象，要将该span对象分割成一个2页的span对象和一个3页的span对象，将2页的span对象分配给central cache，3页的span对象插入到3号桶中。如果一直查找到128号桶都没有span对象，page cache就要使用mmap、brk、或者VirtualAlloc等方式向系统申请一个128页的span对象挂到128号128号桶的span链表中。

释放内存

当central cache释放span对象给page cache时，page cache会寻找该span对象的相邻页所在的span，如果这些span对象是空闲的没有被使用，就将它们合并成更大页的span对象，减少内存碎片。

page cache使用的是全局锁，而不是桶锁。因为page cache要进行span对象的分割与合并操作，会涉及多个桶，使用桶锁容易发生死锁问题，且会频繁地对桶进行加锁解锁操作会导致线程频繁被阻塞又唤醒，效率低。死锁示例：线程1要申请64页的span对象，获取到了64号桶锁，但是64号桶中没有span对象，在128号桶中查找到了span对象，要对128号桶加锁；此时线程2要合并两个64页span对象为128位span对象，线程2先对128号桶加锁并且成功获得了128号桶锁。线程1持有64号桶锁等待128号桶锁，线程2持有128号桶锁等待64号桶锁，发生死锁。其实不难看出，只要线程2先对64号桶加锁，再对128号桶加锁就不会产生死锁问题，这就要保证每个线程都要遵循正确锁的顺序。因此page cache使用全局锁就是为了避免复杂的锁顺序管理，以及频繁加锁解锁带来的效率低问题。

page cache代码框架

page cache是单例模式

九、申请超过256KB大小的内存

如果要申请超过256KB大小的内存，就要考虑两种情况（假设申请内存为size）：

size<=128*8*1024，即申请内存小于128页，直接从page cache中申请内存

size>128*8*1024，即申请内存大于128页，向系统堆申请

实际实现时，只要申请内存size>256KB，都向page cache申请span对象，然后在page cache中再做处理：如果申请内存<=NPAGES(128页)，在对应的桶中取span对象；如果申请内存>NPAGES(128页)，直接向系统堆申请一个span对象。