# 高并发内存池

**Repository Path**: li-yishenset/high-concurrency-memory-pool

## Basic Information

- **Project Name**: 高并发内存池
- **Description**: 这是一个C++项目
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-08-06
- **Last Updated**: 2025-03-30

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 三级哈希内存池：基于线程缓存的高效分配器实现

## 介绍
此项目参考tcmalloc的[开源项目](https://gitee.com/mirrors/tcmalloc)，在多线程并发情况下效率很不错，在网上收集了相关的资料来实现这个框架，只是实现了一个简单的版本，主要目的是为了巩固和应用学习过的知识，包括线程库、哈希桶、链表、单例模式等等知识的融合，对知识有了更深的理解。

## 架构设计
这个项目主要分为3层结构：thread cache、central cache、page cache
### Thread Cache
每一个线程都有一个thread cache，主要解决内存分配和锁竞争的问题。当需要分配的内存小于256KB时，线程从这里申请内存不需要加锁，因为每个线程独享一个cache，这也是这个内存池高效的原因。

### Central Cache
所有线程共享，thread cache是按需从central cache中获取，并且这个过程需要加锁，每个哈希桶一把锁。这部分的哈希桶是慢启动逐步增长的方式来设置，每一次给thread cache都是一批内存，避免多次获取内存。如果需要获取内存的size映射的central cache哈希桶位置的Span已经空了，则需要找到PageCache对象申请内存块。

### Page Cache
整体哈希桶一个锁，根据size计算出需要页的数量，然后去对应的桶上获取Span内存块，如果为空，可以向更大的桶获取，并将此内存块切成需要的页的大小返回，剩下的再找对应的桶挂起来。




## 内存申请
### 大于256KB
直接找PageCache按页对齐申请大块内存。

### 小于256KB
找现成的ThreadCache对象，用size计算出对应的哈希桶位置，若有内存块则直接返回一个内存块，否则就向CentralCache申请。ThreadCache向CentralCache的申请过程是一种类似TCP协议拥塞控制的慢开始算法[1]。从CentralCache的SpanList中获取Span，如果对应的SpanList中没有内存，则需要向PageCache申请一个新的Span对象，将Span管理的内存按大小切好作为自由链表链接到一起，再取对象给ThreadCache。

当central cache向page cache申请内存时，page cache先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。比如：申请的是4页page，4页page后面没 有挂span，则向后面寻找更大的span，假设在10页page位置找到一个span，则将10页page span分裂为一个4页page span和一个6页page span。
如果找到_spanList[128]都没有合适的span，则向系统申请128页page span挂在自由链表中，再重复上述过程。

[1]ThreadCache最开始不会一次向central cache要太多，因为太多了可能用不完。当不断向CentralCache请求内存的时候，每次获取的内存块的数量就会越来越多，直到我们设置的上限。



## 数据结构

三层都是哈希桶结构，但是每一层的桶中存的东西都是不一样的。

### Thread Cache
其中包含一个FreeList的数组，按照用户申请内存的大小映射，本质是通过size（要申请内存的大小）映射到对应的数组下标。桶上存的是对应映射大小的内存块对象的自由链表（FreeList）。

![[ThreadCache.png]](/images/ThreadCache.png)

### Central Cache
其中包含一个SpanList的数组，按照Thread Cache申请内存的大小映射，本质是通过size（要申请内存的大小）映射到对应的数组下标。而桶上存的是SpanList链表（Span的头指针），每个Span是一个结构体，里面包含了切好的小块内存的自由链表（FreeList）。不同的映射位置下挂的就是对应不同内存块大小的对象的自由链表。

![[CentralCache.png]](/images/CentralCache.png)

### Page Cache
有一个unordered_map来设置Page和SpanList的映射，每一个桶上存放的是SpanList结构，也就是和CentralCache是同一个结构，但是PageCache中的SpanList是按下标桶号来映射的，即第i号桶中挂的Span都是i页内存。

![[PageCache.png]](/images/PageCache.png)