高并发内存池（四）：Page Cache结构设计

发布于：2025-05-14 ⋅ 阅读:(13) ⋅ 点赞:(0)

目录

一，项目整体框架回顾

 Thread Cache结构

Central Cache结构

二，Page Cache大致框架

三，Page Cache申请内存实现

Central Cache向Page Cache申请内存接口

从Page Cache中获取span接口

Page Cache加锁问题

申请内存完整过程

源码：

一，项目整体框架回顾

首先，项目整体可以划分为三层：Thread Cache，Central Cache和Page Cache.

 Thread Cache结构

第一层thread cache是每个线程独有的，每个线程都有一份自己的thread cache对象，来完成自己的申请内存和释放内存的工作。

结构特点：

thread cache是一个类似于哈希桶的结构，每个位置上挂着的都是一些小块内存，这些小块内存是以自由链表的形式组织在一起的。当申请内存空间时，都是从对应的位置（对应的哈希桶）中头删一个内存块，返回给上层使用。

为了使每个线程只看到自己的thread cache的对象，用到了线程局部存储机制。所谓线程局部存储，本质上是一种存储变量 的方法，这个变量在它所在的线程内可以访问，其他线程访问不到。这样就实现了每个线程独享一个thread cache

申请内存：

由于每个线程独享一个thread cache，所以可以直接找thread cache申请内存，不需要加锁。这里就会涉及到thread cache的内存对齐规则，当需要申请的内存大小是n时，我们需要计算出其对应的两个值：实际申请的内存块大小（对齐数），对应在哪个桶中（也就是哪个位置）。

如果对应的桶中还有小块内存，也就是对应的桶不为空时，直接返回一个 内存块给上层。

如果对应的桶中没有内存块，或者已经分配完了，则此时就需要向下一层Central Cache申请。

Central Cache结构

Central Cache为thread Cache提供服务。当thread cache内存不够时，会向Central Cache申请。

所以Central Cache是需要加锁的，但是不是给整体的Central Cache加锁，而是对某个桶加锁。

结构特点：

Central Cache结构与thread cache结构很像，也是哈希桶结构.只不过thread cache管理的是小块内存，而Central Cache管理的内存块更大，在这里称作是span。

一个span，管理的是以页为单位的内存块，一页按照8KB来计算。不同位置上的span大小不一样。

所以Central Cache每个位置上挂的是一个一个的span，span的大小是按照页来计算的。

为thread cache分配内存：

由于thread cache和Central Cache的内存对齐规则是一样的，当thread cahce对应位置上没有小块内存时，就会来找Central Cache申请，申请的位置是一样的。这也就是为什么要将Central Cache设计的和thread cahce一样，申请内存时，直接找相同的位置即可。

而Central Cache每个位置上都是span结构，总不能把整个span返回给thread cache吧。

所以，在span内部，是将一个大的内存块，切分成小内存块，然后使用自由链表管理起来。

所以，总体申请内存的过程如下：

thread cahce对应的位置没有内存了，会像Central Cache申请，会来到相同的位置。这里会存在多个线程并发访问的问题，需要加锁，也就是对当前位置（桶）加锁即可，不需要对整个Central Cache加锁。

然后查看这个位置上的span链表，找到一个有内存块的span，也就是非空的span。从中切分一些返回给thread cache，然后将第一个内存块返回该上层使用，剩下的插入到thread cache对应位置中。

下次再申请时，直接找thread cache，因为无锁，申请高高效。

但是，如果Central Cache对应位置的内存也是用完了，此时就需要像下一层Page Cache申请

二，Page Cache大致框架

Page Cache是为上层Central Cache提供服务的，当 Central Cache对应位置没有内存时，就需要像Page Cache申请。

而Central Cache每个位置上挂的是一个span结构，在给 Central Cache分配内存的时候，返回的应该也是一个span结构。所以Page Cache每个位置上挂的也是一个一个的span。

和Central Cache一样，Page Cache每个位置上都是span链表，大致结构如下：

如上图所示，Page Cache也是一个类似于哈希桶的设计。它与thread cache和Central Cache不同 ，它们两个还需要采用什么麻烦的内存对齐规则，才能找到对应的位置（桶）。

Page Cache相当于是直接定址法的哈希结构，1页就映射1号桶，2页就映射2号桶......

因为上层最多一层申请256KB。而128页位置的span大小是128*8KB，所以分为128页够用了。 

如果Central Cache申请的span大小是n页的，就去n号位置找（具体的分配过程在代码部分讲解）

三，Page Cache申请内存实现

Page Cache也是所有的线程共享的，和Central Cache一样，需要设计成单例模式。

//和Central Cache一样，设计成单例模式
class PageCache
{
public:
	PageCache() = delete;
	PageCache(const PageCache&) = delete;
	PageCache operator=(const PageCache&) = delete;

	//获取单例对象
	static PageCache* GetInstance()
	{
		return &_sInst;
	}
	//给Central Cache分配一个span
	//参数size表示该span的大小，即该span包含多少个页
	span* NewSpan(size_t size);

private:
	SpanList _pageList[NPAGENUM];
	static PageCache _sInst;
};

Central Cache向Page Cache申请内存接口

在上一篇文章中，实现了thread cahce向Central Cache申请内存的接口。

大致思路是：

先找到对应Central Cache中的位置，然后遍历该位置，找一个非空的span，然后将给span中的一些内存块切分出来，第一块返回给上层使用，剩下的让thread cache保存着。

在代码部分，获取一个非空的span时，只是调用了对应的接口，没有完全实现，因为 这部分和Page Cache有关。

现在我们需要实现这个接口，也就是获取到对应位置的一个非空span。

上图是Central Cache的大致结构，要找一个非空的span，就需要遍历整个 spanlist。

如果找到一个非空的span，就直接返回该span。

如果找不到，也就是当前位置为空，或者所有的span都已经分配出去了，此时就需要向一层Page Cache申请对应大小的span，我们可以直接调用Page Cache提供的接口（在后面实现）。

  • thread cache内存不足时，Central Cache会分配更多的内存给thread cache。
  • 同样的，Central Cahce对应位置的span都为空时，Page Cache也会分配更多的内存给Central Cache。
  • 所以，此时我们需要计算分配多大的span合适，也就是span包含多少个页。在thread cache向Central Cache申请内存的时候，使用的是慢开始反馈调节算法，每次分配的个数呈现出慢增长的趋势。
  • 我们知道现在想要申请的内存块大小是size。我们可以计算出Central Cache给thread cache分配的最大个数n，就是上限个数（也就是在满开始反馈调节算法中使用到的）
  • 然后我们就可以计算出需要分配的总字节数n*size。
  • 最后看看n*size包含多少个页，采用向上对齐。size_t num=n*size/8KB，这样就可以计算出页的大小。

当从Page Cache申请到一个span后，这个 span是一个大块内存。我们需要进行切分，切分成小块内存，使用自由链表管理起来。

 

完整代码如下： 

//thread chache向Central Cache申请内存时，获取的内存块的个数的上限
static size_t NumMoveSize(size_t size)
{
	assert(size > 0);
	//MAX_BYTES是256KB
	int num = MAX_BYTES / size;

	//size较大时，num的结果可能是1，num=2，多分配一个
	if (num < 2)
		num = 2;

	//size较小是，num的结果可能很大，甚至上万个
	//512相当于一个上限
	if (num >= 512)
		num = 512;

	return num;
}	
//现在知道要申请的内存块大小是size，计算分配多大的span合适
	//也就是计算span，是管理多少页的
	static size_t NumPageSize(size_t size)
	{
		//首先计算，thread cache向Central Cache申请时的上限个数
		size_t num = NumMoveSize(size);

		//计算总的字节数
		size_t byte = num * size;
		byte >>= PAGE_SHIFT;//除以 8KB，计算出页数

		if (byte == 0)
			byte = 1;

		return byte;
	}
//从对应的哈希桶，也就是spanlist中，获取一个非空的span
span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{
	//list就是对应的哈希桶
	//从这个桶中查找一个非空的span，返回
	//如果这个桶没有span了，则需要向下层 Page Cache申请

	//遍历这个spanlist,spanlist是带头双向循环链表结构
	auto it = list.Begin();
	while (it != list.End())
	{
		if (it != nullptr)
		{
			//找到非空的span，也就是Central Cache层还有span，直接返回
			return it;
		}
		else
		{
			it = it->_next;
		}
	}

	//走到这，说明该spanlist已经没有空闲的span了,需要向下层申请
	//这里就会面临向下层申请多大的span合适
	//太大，可能浪费太多，太小，可能会导致频繁的申请
	//所以，这里和thread cache向Central Cache申请内存类似，需要计算一个合适的值
	//参数代表申请的span的大小
	span* sp = PageCache::GetInstance()->NewSpan(SizeClass::NumPageSize(size));

	assert(sp);
	//从Page Cache获取到一个span后，将该span进行切分
	//切成小块内存，形成自由链表，小块内存的大小就是申请时候的size

	//计算这个span总的大小
	//页数*一页的大小(8KB)
	size_t bytes = sp->_n << PAGE_SHIFT;

	//根据sp的起始页号，推断出这个sp的起始地址
	//一页是8KB，第几个页乘以8KB即可推导出起始地址
	char* start = (char*)(sp->_pageID << PAGE_SHIFT);
	char* end = start + bytes;//end指向整个span的结尾

	//切分，每一个内存块的大小是size并以自由链表的形式组织在一起
	//先将第一块切下来，尾插到自由链表中
	sp->_freelist = start;
	start += size;

	//进行尾插
	void* tail = sp->_freelist;
	while (start < end)
	{
		NextObj(tail) = start;//尾插一个start
		tail = start;//tail中心指向尾
		start += size;
	}
	//sp的结构已经设置好了，现在将它分配给Central Cache
	//将它插入到对应的哈希桶中，也就是参数中的list
	list.pushFront(sp);

	//至此，返回的span，就是一个包含小块内存的结构
	return sp;
}

接下来，就需要实现Page Cache的NewSpan接口了。

从Page Cache中获取span接口

	//参数k表示该span的页数，即该span包含多少个页
	span* NewSpan(size_t k);

从Page Cache中获取一个span，span的大小为k页。

而在上面的内容中，我们了解到Page Cache是一个直接定址法的哈希桶。

所以想申请大小为size页的span，直接去对应size位置的桶找即可。

  1. 但这里与前面不同，thread cache对应位置为空时，会找下一层申请，Central Cache为空时，也会找下一层申请。但是如果Page Cache对应某个位置为空时，他会去下面的位置继续找，直到找到一个非空的。比如，当访问Page Cache的3号桶 为空时，会继续找比他更大的桶，假设7号桶非空，那么此时就会将7号桶切成3页和4页，然后将4页挂到4号桶上，3页返回给Central Cache。
  2. 但是如果整个Page Cache都为空，那么此时就会像下一层申请，也就是像操作系统申请一大块的空间。

从一个大小为n页的span中，切分出大小为k的span。

可以总结为以下3步：假设申请的span为k页。

  1. 先去Page Cache对应的位置（下标为k）查找是否有span。如果有 ，直接返回该span。
  2. 如果没有，去找更大的span，从下标为k+1开始遍历整个Page Cache，如果找到了一个非空span，将该span进行切分，一部分返回，另一部分重新挂到Page Cache对应的位置上。
  3. 如果遍历Page Cache也没有找到一个非空的span，就需要向操作系统申请。一次申请128页大小的空间。

还有一个问题，就是如果向操作系统申请了一大块空间，如何将这一大块空间挂到Page Cache对应的位置。本质就是将这一大块空间使用span管理起来。然后将span挂到对应的位置上即可。

向操作系统申请内存，返回的是这块内存的起始地址，是一个指针类型。需要根据返回的地址，计算出这 个大块内存对应的起始页号。如下图：

完整代码如下：

//win64中包含了win32和win64的定义
//win32中只包含了win32的定义
#ifdef _WIN64
typedef unsigned long long  PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif

//申请的内存上限
static const size_t  MAX_BYTES = 256 * 1024;
//自由链表的个数，也就是哈希桶的个数
static const size_t  NFREELISTS = 208;
//Page Cache哈希桶的个数，下标从1开始
static const size_t  NPAGENUM = 129;

//一页的大小(指数)
static const size_t  PAGE_SHIFT = 13;

// 直接去堆上申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
		void* ptr = VirtualAlloc(0, kpage * (1 << 12), MEM_COMMIT | MEM_RESERVE,
			PAGE_READWRITE);
#else
		// linux下调用brk mmap等
#endif
		if (ptr == nullptr)
			throw std::bad_alloc();
	return ptr;
}

//给Central Cache分配一个span
//参数k表示该span的大小，即该span包含多少个页
span* PageCache::NewSpan(size_t k)
{
	//查看下标为k的位置是否有span
	if (!_pageList[k].Empty())
	{
		//直接返回
		return _pageList[k].PopFront();
	}

	//遍历下面的位置，切分出大小为k页
	for (int i = k + 1; i < NPAGENUM; i++)
	{
		if (!_pageList[i].Empty())
		{
			//找到一个非空的，开始切分
			span* kspan = new span;
			span* nspan = _pageList[i].PopFront();//拿到一个span

			kspan->_pageID = nspan->_pageID;
			kspan->_n = k;

			nspan->_pageID += k;
			nspan->_n -= k;
			//将n-k页的span，头插到n-k的桶中
			_pageList[nspan->_n].pushFront(nspan);

			return kspan;
		}
	}

	//走到这里说明没有大块的span了，需要找操作系统申请
	//直接要一个128页的span
	span* bigspan = new span;
	void* ptr = SystemAlloc(NPAGENUM - 1);//128页

	span* sp = new span;
	sp->_pageID = (PAGE_ID)ptr >> (PAGE_SHIFT);//起始页号
	sp->_n = NPAGENUM - 1;//页的个数

	//从操作系统申请到内存后，再递归调用自己一次获取span
	return NewSpan(k);
}

Page Cache加锁问题

Page Cache也是所有线程共享的，在高并发环境下，会存在线程安全问题，所以是需要加锁的。

在Central Cache中，使用的是桶锁，每个线程申请内存时，到对应位置的桶去申请内存，所以加的是桶锁。

Page Cache也是哈希桶结构，当然也可以设计成桶锁，每个桶有一把锁。但是通过上面申请内存的过程，我们有可能不是只针对某一个桶，而是去遍历下面所有的桶，所以如果设计成桶锁的结构，就会面临频繁的申请锁和释放锁，导致系统频繁的进行保存上下文和切换上下文的操作，效率太低。

所以在向Page Cache申请内存时，需要将整个结构加锁。

申请内存完整过程

每个线程启动时，首先向对应的thread cache申请内存，不需要加锁，如果有内存，直接返回给上层使用。

如果不存在，会向Central Cache申请，需要加锁，使用的是桶锁，Central Cache会多分配几个给thread cache。

如果Central Cache也为空，此时会找到一下层Page Cache，需要对整个结构进行加锁。

注意：在Central Cache层使用桶锁后，如果来到下一层Page Cache，就需要将该锁解开。

因为有可能会有其他线程向Central Cache归还内存。

源码：

ConcurrentMemoryPool · 小鬼/高并发内存池 - 码云 - 开源中国

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布