ConcurrentMemoryPoll: 本项目是实现一个高并发内存池，参考了Google的开源项目tcmalloc实现的简易版，其功能就是实现高效的多线程内存管理。

# 🎄项目介绍

## ◎项目来源

本项目实现了一个高并发内存池，参考了Google的开源项目tcmalloc实现的简易版；其功能就是实现高效的多线程内存管理。由功能可知，高并发指的是高效的多线程，而内存池则是实现内存管理的。
[tcmalloc源码](https://github.com/google/tcmalloc)

## ◎内存池相关知识

### 1、池化技术

**池化技术就是程序先向系统申请过量的资源，并将这些资源管理起来，避免频繁的申请和释放资源导致的开销**。

内存池可以使用池化技术来维护可用内存块的链表。当程序需要分配内存时，内存池会从链表中分配一个可用的内存块。如果没有可用的内存块，内存池会从操作系统申请更多的内存，并将新分配的内存块添加到链表中。当程序释放内存时，内存池会将内存块添加回链表中，以便将来使用。

池化技术可以有效地减少内存碎片，因为它可以将多个小内存块组合成更大的内存块，这样就可以分配更大的连续内存空间，并减少碎片。此外，池化技术还可以提高内存使用效率，因为它可以快速分配和释放内存，而无需每次都调用操作系统的内存分配和释放函数。

### 2、内存池

**内存池指的是程序预先向操作系统申请足够大的一块内存空间；此后，程序中需要申请内存时，不需要直接向操作系统申请，而是直接从内存池中获取；同理，程序释放内存时，也不是将内存直接还给操作系统，而是将内存归还给内存池**。当程序退出（或者特定时间）时，内存池才将之前申请的内存真正释放。

### 3、内存池主要解决的问题

由上可知，内存池首要解决的是效率问题，其次从系统的内存分配器角度出发，还需要解决内存碎片的问题。那么什么是内存碎片问题呢？

内存碎片分为外碎片和内碎片。

- 外碎片由下图所示：对于程序员申请的内存，可能因为频繁的申请和释放内存导致内存空间不连续，那么就会出现明明由足够大的内存空间，但程序员却申请不出连续的空间出来，这便是外碎片问题了。
- 内碎片则是由于一些对齐的需求，导致分配出去的内存空间无法被利用，比如本项目中的`Round(Size)`对size进行的对齐。

### 4、malloc

C语言中动态申请内存是通过malloc函数去申请内存的，但是实际上malloc并不是直接向堆申请内存的，而**malloc也可以使用内存池来管理内存分配**，在某些情况下，操作系统或C语言标准库可能会使用内存池来管理堆内存，以提高内存分配效率。当程序将malloc管理的内存池中内存全部申请完时，malloc函数就会继续向操作系统申请空间。

# 🎄设计思路

## ◎第一阶段–设计一个定长的内存池

我们知道malloc函数申请内存空间是通用的，即任何场景下都可以使用，但是**各方面都通用就意味着各方面都不顶尖**，那么我们可以设计一个定长内存池来保证特定场景下的内存申请效率要高于malloc函数。
![image-20221231222658167](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231222658167.png)

### 适应平台的指针方案

在这里，我们想取出一块对象内存中的前4个字节（32位系统）或者8个字节（64位系统）的内存来存储一个指针指向下一块释放回来的自由对象内存，那么在这里为了不作平台系统的判断，可以使用一个小技巧，即将对象内存强转成`void**` 的类型，那么**再对这个二级指针类型解引用就可以取出当前对象的前4个字节（32位系统）或8个字节（64位系统）**。

由此，我们就可以设计出**定长内存池**的对象：

> 定长内存池池的基本思想是在程序运行时预先分配一大块内存，然后在需要使用某个对象时，从这块内存中分配给它。当对象不再使用时，将它归还给对象池，供其他对象使用。这样做的好处在于减少了内存分配和释放的次数，从而减少了内存碎片的产生，并降低了内存分配的开销。
>

## ◎第二阶段–高并发内存池整体框架设计

现代开发环境大多都是多核多线程，那么在申请内存的场景下，必然存在激烈的锁竞争问题。其实，malloc本身就已经足够优秀了，但本项目的原型tcmalloc将在多线程高并发的场景下更胜一筹。

而本项目实现的内存池将考虑以下几方面的问题：

- 1.性能问题
- 2.多线程场景下的锁竞争问题
- 3.内存碎片问题

concurrent memory pool（并发内存池），主要有以下3个部分组成：

### 1.线程缓存（thread cache）

线程缓存是每个线程独有的，用于小于256kb内存的分配。那么对于每一个线程从thread cache申请资源，就**无需考虑加锁问题，每个线程独享一个缓存（cache）**，这也是并发线程池高效的地方。

### 2.中心缓存（central cache）

中心缓存有所有线程所共享，thread cache 按需从central cache处获取对象，而central cache在合适的时机从thread cache处回收对象从而避免一个线程占用太多资源，导致其他线程资源吃紧，进而**实现内存分配在多个线程更加均衡的按需调度**。由于所有thread cache都从一个central cache中取内存对象，故central cache是存在竞争的，也就是说从central cache中取内存对象需要加锁，但我们在central cache这里用的是桶锁，且只有thread cache中没有对象后才会来central cache处取对象，因此锁的竞争不会很激烈。

### 3.页缓存（page cache）

页缓存是中心缓存上一级的缓存，存储并分配以页为单位的内存，central cache中没有内存对象时，会从page cache中分配出一定数量的page，并切割成定长大小的小块内存，给central cache。当page cache中一个span的几个跨度页都回收以后，page cache会回收central cache中满足条件的span对象，并且合并相邻的页，组成更大的页，从而缓解内存碎片（外碎片）的问题。

![image-20221231222738763](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231222738763.png)

## ◎第三阶段–三级缓存的具体实现

### 1.Thread Cache框架构建及核心实现

thread cache是**哈希桶结构**，每个桶是一个根据桶位置映射的挂接内存块的自由链表，每个线程都会有一个thread cache对象，这样就可以保证线程在申请和释放对象时是无锁访问的。

![image-20221231222810584](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231222810584.png)

#### 🌕申请与释放内存的规则及无锁访问

- 申请内存

1. 当内存申请大小size不超过256KB，则先获取到线程本地存储的thread cache对象，计算size映射的哈希桶自由链表下标i。
2. 如果自由链表_freeLists[i]中有对象，则直接Pop一个内存对象返回。
3. 如果_freeLists[i]中没有对象时，则批量从central cache中获取一定数量的对象，插入到自由链表并返回一个对象。

**释放内存**
1.当释放内存小于256kb时将内存释放回thread cache，计算size映射自由链表桶位置i，将对象Push到_freeLists[i]。
2.当链表的长度过长，则回收一部分内存对象到central cache。

**tls - thread local storage**
线程局部存储（tls），是一种变量的存储方法，这个变量在它所在的线程内是全局可访问的，但是不能被其他线程访问到，这样就保持了数据的线程独立性。而熟知的全局变量，是所有线程都可以访问的，这样就不可避免需要锁来控制，增加了控制成本和代码复杂度。

#### 🌕管理内存对齐和映射等关系

##### ▶计算对齐大小映射的规则

thread cache中的哈希桶映射比例比非均匀的，如果将内存大小均匀划分的话，则会划分出大量的哈希桶，比如256kb如果按照8byte划分，则会创建32768个哈希桶，这就有较大的内存开销；而如果按照更大的字节划分，那么内存开销虽然减少了，但照顾到的场景也少了，且会产生内碎片问题。

那么参考tcmalloc项目，为了保证内碎片的浪费整体控制在10%左右进行的区间映射，同时没有那么大的开销。使用`RoundUp` 函数的将输入的 `size` 对齐到一个固定的对齐值。对齐值是根据 `size` 的大小而定的，它分成了五个区间：

- 如果 `size` 位于 `[1,128]` 之间，那么 `size` 将被对齐到 8 字节。
- 如果 `size` 位于 `[128+1,1024]` 之间，那么 `size` 将被对齐到 16 字节。
- 如果 `size` 位于 `[1024+1,8*1024]` 之间，那么 `size` 将被对齐到 128 字节。
- 如果 `size` 位于 `[8*1024+1,64*1024]` 之间，那么 `size` 将被对齐到 1024 字节。
- 如果 `size` 位于 `[64*1024+1,256*1024]` 之间，那么 `size` 将被对齐到 8192 字节。

> 这个函数内部使用了另外一个静态函数 `_RoundUp` 来实际计算对齐后的值。

也就是说，对于1byte到128byte的内存对象，按照8byte对齐，划分为下标0-15号的哈希桶，而129byte到1kb的内存对象，按照16byte对齐，划分下标16-71号的哈希桶，以此类推，最终划分为0-207号总共208个哈希桶，这样就保证了内存较小的开销，同时各个对齐关系中内碎片浪费控制在10%左右，比如129byte到144byte区间，取144byte的内存对象，浪费率为(144 - 129) / 144 = 10.42%,当然对于最开始的1byte申请8byte内存对象，虽然浪费高达87.5%，但考虑到最终内碎片浪费了7byte，对比后续内碎片一次浪费7kb来说可以忽略不计了。

这便是申请的内存对象大小对齐的映射关系，这个关系在后续central cache及page cache中仍有应用，因此可以将其定义在头文件common.h中，以后内存大小对齐的管理。

#### 🌕自由链表的设计

在有了上面的基础之后，我们来设计自由链表，其实就是实现一个单链表，方便插入删除，同时标识链表长度 _size以方便后续释放流程，以及定义 _maxSize来保住thread cache一次申请对象批次的下限。

#### 🌕thread cache框架构建

在有了上述基础后，我们来搭建thread cache的框架，其实就是一个哈希桶，每个桶中挂接着自由链表对象。

`_declspec(thread)`是一个Windows平台专用的关键字，用于声明线程局部存储（TLS）变量。在这里，它声明了一个指向`ThreadCache`对象的指针变量`pTLSThreadCache`，该变量的值对于每个线程来说都是独立的，可以使线程在向thread cache申请内存对象的时候实现无锁访问。

```c
class ThreadCache
{
public:
	// 申请和释放内存对象
	void* Allocate(size_t size);
	void Deallocate(void* ptr, size_t size);

// 从中心缓存获取对象
	void* FetchFromCentralCache(size_t index, size_t size);

// 释放内存时，如果自由链表过长，回收内存到CentralCache中心缓存
	void ListTooLong(FreeList& list, size_t size);
private:
	// 哈希桶，每个桶中挂接着自由链表对象
	FreeList _freeLists[NFREELIST];
};

// pTLSThreadCache是一个指向ThreadCache对象的指针，每个线程都有一个独立的pTLSThreadCache
// 可以使线程在向thread cache申请内存对象的时候实现无锁访问
static _declspec(thread) ThreadCache* pTLSThreadCache = nullptr;
```

### 2.central cache框架构建及核心实现

central cache也是一个哈希表结构，其映射关系与thread cache是一样的，不同的是central cache的哈希桶位置所挂接的是SpanList链表结构，不过每个桶下的span对象被切分成了一块块小内存挂接在span对象的自由链表freeList中。

![image-20221231222905082](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231222905082.png)

> 图稍微有点不对，sapn链是带头双向循环链表，最后不该指向NULL，应该指向头。

#### 🌕申请与释放内存规则

- 申请内存
  1.当thread cache中没有内存后，就会向central cache中申请大块内存。这里的申请过程采用的是类似网络tcp协议拥塞控制的慢开始算法，而central cache中哈希映射的spanlist下挂着的span则向thread cache提供大块内存，而从span中取出对象给thread cache是需要加锁的，这里为了保证效率，提供的是桶锁。

##### ▶慢开始算法

线程缓存从中央缓存获取内存块的数量是按照“慢开始反馈调节算法”递增的：

> 1、最开始不会一次向central cache一次批量要太多，因为要太多了可能用不完
> 2、如果你不要这个size大小内存需求，那么batchNum就会不断增长，直到上限
> 3、size越大，一次向central cache要的batchNum就越小
> 4、size越小，一次向central cache要的batchNum就越大

```c
// 预计获取的批次数量
size_t batchNum = min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
if (_freeLists[index].MaxSize() == batchNum)
    _freeLists[index].MaxSize() += 1;
```

举个例子，线程申请7块大小相同的内存，第一次申请的批次数量为1块，第二次再来申请时，此时thread cache的自由链表下已经没有空闲的内存了，则又需要继续向central cache申请内存，申请的批次数量为2块，第3次直接从thread cache的自由链表中获取内存块；第4次再申请时，则需要向central cache申请内存，此时申请的批次数量为3块，挂接在thread cache的自由链表下，直到第7次来申请内存时，向central cache申请的内存批次数量为4，这时线程取走一块内存，则挂接在thread cache的自由链表下还有3块空闲的内存。

2.当central cache中映射的spanlist下所挂接的所有span对象都没有内存后，则需要向page cache申请一块新的span对象，central cache拿到这块span对象后会按照所管理内存的大小将span对象划分成多块，再挂接到central cache的审判list中；然后再从这块新申请的span对象中去内存分配给thread cache。

3.在这里，为了方便后续的回收，span对象每分配出一块内存，其成员变量`_useCount`就++；相反thread cache每释放归还一块内存后，`_useCount`就–。

**释放内存**
当thread_cache过长或者线程销毁，则会将内存释放回central cache中的，释放回来时–`_useCount`。当`_useCount`变为0后，说明所有分配出去的内存都归还回来了，那么就将这个span对象归还给page cache，page cache会对归还回来的span进行前后页合并。

#### 🌕管理多个大块内存的跨度结构Span及SpanList

在上面我们知道central cache的哈希桶下挂接着的是跨度结构Span对象，其实Span对象是管理以页为单位的大块内存的结构体。而为了方便后续回收span对象到page cache，需要将任意位置span对象从spanlist中删除，那么将spanlist定义为一个双向链表更好一些。

#### 🌕central cache框架构建

在明确了span与spanlist的定义描述后，也不能设计出central cache的框架结构，central cache是一个哈希表结构，其映射的是spanlist与哈希桶位置（内存大小）的关系。

其次，在这里我们将central cache设计为饿汉式单例模式，类的唯一实例在程序启动时就已经被创建出来，并且在整个程序的生命周期内都只有这一个实例。**饿汉式优点是线程安全，因为实例在程序启动时就已经被创建，在整个程序的生命周期内都只有这一个实例，不会存在多线程竞争的情况**。

```c
class CentralCache
{
public:
	// 单例模式的定义，作用：获取唯一实例的静态方法
	static CentralCache* GetInstance()
	{
		// &_sInst 返回 _sInst 对象的地址，因为 _sInst 是一个静态变量
		// 所以它的地址是固定的，其他代码也可以通过该地址访问 _sInst 对象
		return &_sInst;
	}

// 获取一个非空的span
	Span* GetOneSpan(SpanList& list, size_t byte_size);

// 从中心缓存获取一定数量的对象给ThreadCache线程缓存
	size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size);

// 将一定数量的对象释放到中心缓存的span跨度
	void ReleaseListToSpans(void* start, size_t byte_size);
private:
	SpanList _spanLists[NFREELIST];
private:
	// 构造函数和一个拷贝构造函数私有化
	CentralCache()
	{}

CentralCache(const CentralCache&) = delete;

// 定义一个静态的变量 _sInst，该变量保存着 CentralCache 类的唯一实例
	static CentralCache _sInst;
};
```

### 3.page cache框架构建及核心实现

page cache与前两级缓存略有不同，其映射关系不再是哈希桶位置与自由链表或spanlist的映射，而是页号与spanlist的映射，这里我们设计的是128页的page cache。
![image-20221231223109247](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231223109247.png)

#### 🌕申请与释放内存

- 申请内存
  1.当central cache向page cache申请内存时，page cache先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。比如：申请的是1页page，1页page后面没有挂span，则向后面寻找更大的span，假设在100页page位置找到一个span，则将100页page的span分裂为一个1页page span和一个99页page span。

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

3.需要注意的是central cache和page cache 的核心结构都是spanlist的哈希桶，但是他们是有本质区别的，**central cache中哈希桶，是按跟thread cache一样的大小对齐关系映射的，他的spanlist中挂的span中的内存都被按映射关系切好链接成小块内存的自由链表。而page cache 中的spanlist则是按下标桶号映射的，也就是说第i号桶中挂的span都是i页内存**。

- 释放内存
  如果central cache释放回一个span，则依次寻找span的前后page id的没有在使用的空闲span，看是否可以合并，如果合并继续向前寻找。这样就可以将切小的内存合并收缩成大的span，减少内存碎片。

##### ▶直接向堆申请或释放以页为单位的大块内存

这里我们为了避免使用malloc及free函数接口去向堆申请和释放内存，因此使用系统调用接口直接向堆申请和释放内存。这里的系统调用接口在window下为`VirtualAlloc`与`VirtualFree`系统调用接口；在Linux系统下为`mmap`与`munmap`，`brk`与`sbrk`两对系统调用接口。

##### ▶Span跨度结构以页为单位管理从堆申请的内存

我们向堆申请内存后会返回这块内存的起始地址，那么我们将这个地址看作一个无符号整型，将其除以8*1024作为Span结构的_pageId，再将申请内存时用的页号赋给 _n,这里为了方便后续回收分配出去的Span跨度结构，我们使用STL的`unordered_map`来构建 _pageId与Span对象的映射关系。

#### 🌕page cache框架构建

与central cache类似的是，page cache也是单例模式；不过page cache加的不是桶锁，而是整级加的一把大锁，即每次central cache向page cache申请内存时，page cache都要加锁防止出现安全问题。

```c
class PageCache
{
public:
	static PageCache* GetInstance()
	{
		return &_sInst;
	}

// 获取从对象到span的映射
	Span* MapObjectToSpan(void* obj);

// 释放空闲span回到Pagecache，并合并相邻的span
	void ReleaseSpanToPageCache(Span* span);

// 获取一个k页的span
	Span* NewSpan(size_t k);

std::mutex _pageMtx;
private:
	SpanList _spanLists[NPAGES];// PageCache自己的双链表哈希桶，映射方式是按照页数直接映射
	ObjectPool<Span> _spanPool;

// std::unordered_map<PAGE_ID, Span*> _idSpanMap;
	TCMalloc_PageMap1<32 - PAGE_SHIFT> _idSpanMap;

PageCache()
	{}
	PageCache(const PageCache&) = delete;

static PageCache _sInst;
};
```

# 🎄细节与性能优化

## ◎使用定长内存池配合脱离使用new

我们定义一个Span结构体时是new一个对象，但new的本质是malloc，而本项目是不依赖malloc的，因此我们可以运用我们自己实现的定长内存池来脱离new的使用。
对于Page Cache，由于要多次定义Span结构，因此我们定义一个特化Span对象的定长内存池：

```c
//定义定长的span内存池以脱离使用new
ObjectPool<Span> _spanPool;
```

## ◎解决内存大于256kb的申请释放问题

![image-20221222205935804](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221222205935804.png)

1.`ConcurrentAlloc() `时，对于线程申请大于256kb内存的情况， 直接向页缓存申请即可：

2.当然了页缓存的`NewSpan()`正常分配内存的能力也有上限，大于128 page的选择直接向堆申请，这里的128页相当于128 * 8KB = 1M。

3.同样的，`ConcurrentFree()`时，大于256kb的内存的释放就直接释放给页缓存即可：

4.`ReleaseSpanToPageCache(Span* span)`合并页时，若释放的span大于128页，即span的页数大于NPAGES - 1，则直接将内存释放到堆。

## ◎使用基数树进行性能优化

如果我们在Page Cache中使用STL的unordered_map容器来构建_pageId与span的映射关系，那么通过测试发现，当前项目的运行效率是要满于malloc的。
![image-20221231180451722](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231180451722.png)

接下来分析下项目的性能瓶颈：

![image-20221231182356934](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231182356934.png)

分析得到项目在`unordered_map<PAGE_ID, Span*> _idSpanMap;`中的锁竞争上浪费了大量性能，这主要是unordered_map是线程不安全的，因此多线程下使用时需要加锁，而大量加锁导致资源的消耗。

因此，这里参考tcmalloc，使用基数树来进行性能的优化。tcmalloc设计了三种基数树，即一层、二层与三层的基数树，其中一层和二层的基数树是适配32位系统下的，而三层基数树则是适配64位系统。

# 🎄项目总结

## ◎结果演示

可以看到通过基数树优化后的高并发内存池在性能上是要优于malloc函数的。

![image-20221231210331578](https://typora-1310561439.cos.ap-guangzhou.myqcloud.com/image-20221231210331578.png)

## ◎项目对比malloc性能高的原因

**malloc底层是采用边界标记法将内存划分成很多块，从而对内存的分配与回收进行管理**。简单来说，**malloc分配内存时会先获取分配区的锁**，然后根据申请内存的大小一级一级的去获取内存空间，最后返回。

所以在高并发的场景下，malloc在申请内存时需要加锁，以避免多个线程同时修改内存分配信息，这会导致性能下降。而内存池可以通过维护自由链表来分配内存，避免了加锁的开销。

总结出本项目效率相对较高的3点原因：

- 1.第一级thread cache通过tls技术实现了无锁访问。
- 2.第二级central cache加的是桶锁，可以更好的实现多线程的并行。
- 3.第三级page cache通过基数树优化，有效减少了锁的竞争。

## ◎项目扩展及缺陷

1.实际上在释放内存时由thread cache将自由链表对象归还给central cache只使用了链表过长这一个条件，但是实际中这个条件大概率不能恰好达成，那么就会出现thread cache中自由链表挂着许多未被使用的内存块，从而出现了线程结束时可能导致内存泄露的问题。

>  解决方法就是使用动态tls或者通过回调函数来回收这部分的内存，并且通过申请批次统计内存占有量，保证线程不会过多占有资源。

2.可以将这个项目打成静态库或动态库替换调用系统调用malloc，不同平台替换方式不同。 基于unix的系统上的glibc，使用了weak alias的方式替换。具体来说是因为这些入口函数都被定义成了weak symbols，再加上gcc支持 alias attribute，所以替换就变成了这种通用形式：

```cpp
void* malloc(size_t size) THROW attribute__ ((alias (tc_malloc)))
```

因此所有malloc的调用都跳转到了tc_malloc的实现。有些平台不支持这样的东西，需要使用hook的钩子技术来做。参考：[hook](https://www.cnblogs.com/feng9exe/p/6015910.html)

## ◎收获与总结

1.锻炼debug能力；

2.了解了池化技术；

3.学习了三级缓存自顶向下的设计方案；

4.单例设计模式在具体项目的应用、慢增长算法以及基数树等。

林慢慢/ConcurrentMemoryPoll

简介

发行版

贡献者

近期动态

林慢慢/ConcurrentMemoryPoll .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

林慢慢/ConcurrentMemoryPoll