[数据结构与算法]高并发内存池设计

设计框架

• thread cache:解决锁竞争的问题
• central cache:会发生锁竞争，但是不会很激烈 -> 使得内存在多个线程情况下分配更均衡
• page cache:存储的内存是以页为单位存储及分配的。central cache没有内存对象时，从page cache分配出一定数量的page，并切
  割成定长大小的小块内存，分配给central cache。page cache会回收central cache满足条件的span对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问题。 ->重点解决内存碎片问题

Thread Cache

• Thread Cache对象的结构

  需要有一个哈希表(其实就是一个自由链表数组)，哈希映射中对应的是不同的字节对象大小，桶子下面挂着剩余的内存块的数目

  

• 需要的接口

申请内存：

1. 当内存申请size<=64k时在thread cache中申请内存，计算size在自由链表中的位置，如果自由链表中有内存对象时，直接从FistList[i]中Pop一下对象，时间复杂度是O(1)，且没有锁竞争。
2. 当FreeList[i]中没有对象时，则批量从central cache中获取一定数量的对象，插入到自由链表并返回一个对象。

释放内存：

1. 当释放内存小于64k时将内存释放回thread cache，计算size在自由链表中的位置，将对象Push到FreeList[i].
2. 当链表的长度过长，则回收一部分内存对象到central cache。

线程TLS：

? 为了保证效率，我们使用thread local storage保存每个线程本地的ThreadCache的指针，这样大部分情况下申请释放内存是不需要锁的。

• TLS避免使用锁

1. TLS thread local storage -> 线程本地储存
2. 对于线程来说是全局的，但是每个线程是独立的,因此对变量进行操作的时候，不需要进行加锁 -> 与局部变量的差别是，它的生命周期是全局的
3. Thread Local Storage(线程本地存储1)
   Thread Local Storage(线程本地存储2)
   为什么需要TLS

• 对象大小映射选择

1. 如果想要减少浪费，对应的桶子跨度就应该越小，但是桶子的数量会非常多，比如以8为跨度，64K就有8192个桶子,实在太过庞大，并且内存也被切得越碎

2. 如果增加跨度，势必会增大浪费，比如以8位跨度时，一次最多浪费7个字节，如果增加跨度，浪费的字节数量就在增加

3. 为了兼顾桶子数量，和内碎片优化，可以使用梯度对齐 (在字节数少的时候，浪费少一点，字节数多的时候，可以浪费多一点。比如10个字节浪费9个字节是很多的，1000个字节浪费9个字节就不显得那么多了)，比如使用的字节数小于128时，此时跨度设置为8(小于8有可能构建链表时不能存储指针)，如果跨度设置为16，使用1个字节时，就得浪费15个字节，所以在小字节时的跨度应该小一点

4. 下面给出控制1%-12%左右的内碎片浪费的跨度

    控制在1%-12%左右的内碎片浪费
   [1,128]				8byte对齐   	    freelist[0,16)//编号0-15号桶子  
   [129,1024]			16byte对齐		freelist[16,72)  	最多浪费17字节   浪费率 = 15/(129+15)=10.42%
   [1025,8*1024]		128byte对齐		freelist[72,128)	最多浪费127字节  浪费率 = 127/(1025+127)=11.02%	
   [8*1024+1,64*1024]	1024byte对齐  	freelist[128,184)   最多浪费1023字节 浪费率 = 1023/(1024*9-1)=11.10%
   

5. 按照上述对齐方式，可知最大映射值为64K的桶子数量为 128/8 +(1024-128)/16 + (8192-1024)/128 + (64k-8k)/k=184

6. 映射位置计算方法为

   inline static size_t _Index(size_t bytes, size_t ANumber)//传入对象大小和对齐数
   	{
   		return ((bytes + (1 << ANumber) - 1) >> ANumber) - 1;//对齐最好为2的整数倍，才好进行左移和右移
   	}
   	比如按8对齐，传入的数是3，1<<3=8 -> 8-1=7 ->  (7+对象大小)/8就在下一个位置，所以减去1
   	
   

Central Cache

• Central Cache对象的结构

  1. 结构图

  2. Span：用来管理central cache或者是page cache之中的大块内存，下面只针对central cache之中的span进行描述

     • 一个Span只会被切割给固定大小的对象，因此Span结构中需要一个成员变量描述对象的大小
     • 需要一个usecount统计span被切割成了多少份，当usecount为0时，表示这个span是完好的
     • 当然了，还需要一个memory指针变量保存内存块空间
     • 同时需要将Span定义成双向循环链表，方便插入和删除

  3. SpanList用来管理大块内存

     • 成员变量为一个Span类型的头结点(带头双向循环节点)
     • 提供插入和删除接口

• 需要的接口

申请内存：

1. 当thread cache中没有内存时，就会批量向central cache申请一些内存对象，central cache也有一个哈希映射的spanlist，spanlist中挂着span，从span中切割一批对象给thread cache(thread cache之中挂的内存是已经切好的)，这个过程是需要加锁的。
2. central cache中没有非空的span时，则向上层page cache以页为单位申请内存
3. central cache的span中有一个usecount，分配一个对象给thread cache，就++usecount。usecount用0来表示空闲，这是因为切割成不同的大小，块数是不一样的，所以需要以0表示完整的
4. central cache承上启下，当thread cache的内存还回来时，可以给其它线程用，当span全部回来，又可以向上一级还

释放内存

当thread_cache过长或者线程销毁，则会将内存释放回central cache中的，释放回来时–use_count。当use_count减到0时则表示所有对象都回到了span，则将span释放回pagecache，page cache中会对前后相邻的空闲页进行合并。

Page Cache

• Page Cache 对象结构

• Page Cache 需要的接口

申请内存：

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

释放内存：

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