高并发的内存池

---

项目介绍：实现了高并发的内存池，对于多个线程来说申请内存的效率大幅度提高

使用技术：C++，window的API

内存池：一种动态内存分配的技术。内存池就是在真正使用内存之前，先申请分配一大块内存留作备用，当程序员申请内存时，从池中取出一块动态分配，当程序员释放内存时，将释放的内存在放入池内，再次申请内存可以取出来再用。在释放内存的时候，尽量与周边空闲的内存块进行合并。当内存池不够大的时候，自动扩大内存池，从操作系统中申请更大的内存池。对于通常情况下，直接使用new，delete，malloc，free等API申请分配内存和释放内存，当程序长时间运行时，由于申请的内存块的大小不一定，频繁使用会造成大量的内存碎片从而降低程序的性能。

并发内存池：

现在很多的开发环境都是多核多线程的，在申请内存的场景下，必然存在激烈的锁竞争问题。

需要考虑的问题：

1. 内存碎片

2. 性能问题

3. 多核多线程环境下，锁竞争问题

concurrent memory pool主要是由以下三部分构成：

• thread cache：线程缓存是每一个线程独有的，用于小于64K的内存的分配，线程从这里申请内存不需要进行加锁，每一个线程独享一个cache。这就是高效和并发的地方

• cantral cahce：中心缓存是所有线程所共享的，thread cach按照需要从central cache中获取内存。central cache周期性的回收thread cache内存，避免一个线程占用了太多的内存，而其他线程内存吃紧。达到了内存分配在多个线程中更均衡的按需调度的目的。cantral cache是所有线程从这里申请内存，所以存在着竞争的问题，需要加锁。作用：均衡资源（加锁）

• page cache：页缓存是对于central cache来说内存不够的时候，给central cache分配出一定数量的页，将这些页切割成大小相等的内存块分配给central cache。

当thread cache中的内存归还给central cache的时候，如果central cache中的span满足归还条件的话，就将这个span归还给page cache，然后page cache在将归还回来的内存合并成更大的页。

thread cache：

原理图：

申请内存：

1. 当申请的内存大于64KB的话，直接使用malloc申请内存。此外当申请内存byte <= 64KB时在thread cache中申请。根据byte计算出需要在数组中的那个自由链表中申请内存，如果自由链表中有内存块的话，从_freelist[i]直接Pop拿出内存块使用，时间复杂度是O(1)，没有锁竞争

2. 当自由链表_freelist[i]中没有内存块的时候，则批量从central cache中申请一定数量的内存块，插入到自由链表，并且返回一个内存块

释放内存：

1. 当释放内存小于64KB时，将内存释放会thread cache中，计算byte在数组中的位置，将内存块push到_freelist[i]上

2. 当链表长度过长，则回收一部分内存块到central cache

 

控制在12%左右的内碎片浪费
[1,128]             8byte对齐     _freelist[0,16)
[129,1024]          16byte对齐    _freelist[16,72)
[1025,8*1024]       128byte对齐   _freelist[72,128)
[8*1024+1,64*1024]  512byte对齐   _freelist[128,240)
                                
内碎片的计算方法：
对于7/8;15/(128+16);127/(1024+128);511/(8*1024+512);
对于进行哈希映射的数组的大小是240
240 = (128/8) + (1024-128)/16 + (8*1024-1024)/128 + (64*1024-8*1024)/512

 

central cache：

原理图：

申请内存：

1. 当申请的内存小于64Kb的时候，当thread cache中没有内存时，就会批量向central cache申请一些内存对象，central cache数组中每个元素是 _spanlist，每个 _spanlist下面都挂着一个个的span，从span中取出内存块来给thread cache。这个过程是要加锁的

   1. 当_spanlist[i]中有span时，并且span中是不为空的话，直接从这个span中获取内存块，否则向page cache申请一个span对象，span对象中是一些以页为单位的内存，切成需要的内存大小，并链接起来，挂到span中

2. 当申请的内存大于64KB小于128页的时候，直接去PageCache中申请内存。这个过程需要加锁

3. 当申请的内存大于128页的时候，就直接去系统申请内存，申请内存的时候是以页为单位的。这个过程需要加锁

释放内存：

1. 当thread cache过长或者线程销毁的，则会将内存释放会central cache，释放回来时--usecount。当usecount减到0时，则表示所有对象都回到了span，则将span释放回page cache，page cache中会对前后相邻的空闲页进行合并，这个过程需要加锁

 

page cache：

原理图：

申请内存：

1. 当central cache向page cache申请内存的时候，先检测对应位置有没有span，如果有直接返回这个span，如果没有的话则向更大页寻找一个更大的span，如果找到分裂成两个span

2. 如果找到128page都没有合适的span,则向系统使用mmap、brk或者是VirtualAlloc等方式申请128page span挂在_pagelist数组里面，然后再次重复步骤一

释放内存：

1. 如果central cache释放一个span，则依次寻找span前后的pageid的span，看是否可以进行合并，如果合并继续向前找，直到找不到可以合并的了，或者如果此次合并大于128page。这样就可以将切小的内存合并收缩成大的span，减少内存碎片。这个过程需要加锁，因为有可能是某一个线程申请的内存是大于64K但是小于128页的，这个归还的时候，也是直接归还到页上，才是就有可能造成多个线程进行访问。

小结：总共有四次加锁的过程

1. 线程缓存到中心缓存申请内存。这是加的是桶锁，因为有可能多个线程需要的内存空间是不一样大的，所以需要访问的span链表也是不一样的，只需要当访问同一个span链表的时候在进行加锁就好了

2. 线程缓存将内存块释放到中心缓存。这个也是增加的桶锁，只有是访问的是同一个span链表的时候才会加锁

3. 线程直接到页缓存申请内存。对于到缓存申请内存页的时候，有可能会造成对多个页进行操作改变，所以此时要在最外面增加一个锁

4. 从中心缓存释放span到页缓存。将span释放到页缓存的时候，会对多个span进行合并，从而也就会改变多个span所以要在最外面增加一个锁

• 对于项目的申请内存的流程图

• 对于项目的释放内存的流程图

优点：

• 高并发：

  • 高并发是因为对于每一个线程都有着自己的一个线程缓存，当每一个线程申请内存的时候就不需要每次要到系统申请内存直接到自己的线程缓存上申请内存就好了。就不会牵扯到多个线程访问同一份资源，就达到了高并发的目的，使用到了静态的TLS

• 提高效率：

  • 每一次使用内存的时候，提前将内存都已经分配好了，直接用内存就不需要再次从系统申请内存了。也就是减少了调用系统调用函数的次数，从而提高了效率。并且有着中心缓存还进行多个线程之前的均衡，不会让一个线程占用着许多个内存不使用，导致其他的线程想要申请内存的时候申请不到内存的情况。当一个线程内部的内存块大于一个水位线的时候，就将内存全都释放到中心缓存中

• 解决了内存碎片：

  • 对于该项目将内存碎片控制在大约12%左右，关键就是对于外碎片进行了减少，因为对于线程缓存不使用的内存就会归还到中心缓存的一个span上，而中心缓存的span上的内存只要没有线程使用的话，就将这个span再次归还到页缓存上，归还到页缓存的时候就会对多个span进行合并，从而将小的内存合并成大的内存

 

项目测试：

【注意】：在测试的时候需要使用relase模式（发行版本）来进行测试，采用这个模式对于自己书写的程序，编译器可以对其尽可能的优化，从而达到的性能也就是最好的。

以下测试均是在VS2017下进行测试得出。

插图：Concurrentmempool测试

测试1：50个线程，100轮，每轮1000次，每次申请1024byte

测试2：10个线程，100轮，每轮1000次，每次申请1024byte

测试3：10个线程，100轮，每轮100次，每次申请528384byte

测试4：10个线程，100轮，每轮1000次，每次申请10byte

测试5：50个线程，100轮，每轮100次，每次申请10byte

测试6：1个线程，100轮，每轮100次，每次申请524288byte

 

项目不足：

• 当前项目还是没有完全脱离使用malloc。

比如：在内存池自身的数据结构的管理当中，比如spanlist中的Span结构还是使用new Span的操作完成，而new的底层就是malloc。还有就是对于使用STL库中的unordered_map的时候，就间接使用了空间配置器。对于空间配置器底部申请内存的时候，是使用了一级空间配置器和二级空间配置器，对于一级空间配置器是使用malloc实现的。

二级空间配置器：当申请内存的时候是先到自由链表中查看是否有内存，如果有内存的话就直接使用内存，没有内存的时候就要到内存池申请内存。

1. 一般是申请20个块内存，

2. 如果不够20块的话有多少块申请多少块。

3. 如果连一块都没有的话就将所有的内存都挂到自由链表上去。然后内存池再去堆申请内存

   1. 申请到内存之后再次分配给程序

   2. 没有申请到内存的话，就到自由链表上看有没有比要申请的这一块内存池大的内存，如果有的话就直接将这一块的内存释放到内存池，然后再申请内存

   3. 最后就是调用一级空间配置器

 

解决方案：

• 项目中增加一个定长的ObjectPool的对象池，对象池的内存直接使用brk，virtuallAlloc向系统内存申请，new Span替换成对象池申请内存。对于STL中的unordered_map也是使用一个对象池来分配内存就好了。这样就完全脱离了malloc，就可以替换到malloc

 

平台及兼容性：

• Linxu等系统下，需要将VIrtuallAlloc替换为brk

• X64系统下，实现支持不足。不如：id查找Span的映射，我们使用的是map<id, Span*>。在64位系统下，这个数据结构在性能和内存等方面都是撑不住的。使用基数树

 

替换系统的malloc和free：

• 在以上测试中，当前实现的并发的内存池比malloc/free是更加高效的。但是我们如何将我们写的代码替换到系统调用呢？

• 对于不同的系统平台替换的方式是不同的。对于Linux下使用weak alias的方式进行实现的

• 对于其他的平台可以使用hook技术来进行实现

 

扩展知识：

• 线程TLS（thread local storage）

  • 为了保证效率，我们使用thread local storage保存每一个线程本地的ThreadCache指针，这样的话就会在thread cache中申请内存不需要加锁

对于TLS分为两种，一种是静态的TLS，另外一种是动态的TLS，我们这里使用的是静态的TLS，对于每一线程创建的时候都会有着自己的一个线程缓存。

static _declspec(thread) ThreadCache* tls_threadcache = nullptr;

• 内存碎片分为：内碎片和外碎片

  • 内碎片：比如要申请10byte的内存，但是申请了16byte这个时候用不到这么多的内存，就会导致6byte内存造成了浪费，6字节就是内碎片

  • 外碎片：对于堆上开辟的空间没有全部还回来，导致还回来的字节不连续，申请不出更大的空间

  • 该内存池，每次归还内存的时候都会检查器左右周边有没有空闲的内存。如果有的话，就会进行合并内存，将小的内存合并成大的内存，这样就解决了外内存碎片的问题

• 从Window系统申请/释放内存

  • 从Window系统上申请内存的时候，以按照页的大小进行分配内存的，返回申请的起始地址

  • 从Window系统上释放内存的时候，只需要知道申请的起始地址

  //申请内存
  void* ptr = VirtualAlloc(NULL, (NPAGES - 1) << PAGE_SHIFT, \
          MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
      if (ptr == nullptr)
      {
          throw std::bad_alloc();
      }
  ​
  //释放内存
  VirtualFree(ptr, 0, MEM_RELEASE);
      if (ptr == nullptr)
      {
          throw std::bad_alloc();
      }

   

总的思想：对于在该内存池中，从系统申请的内存就会一直存在于这个内存池中，不会再归还给系统，从系统申请内存的时候是按页进行申请的，对于归还内存的时候，只需要判断该内存在哪一个页中，直接归还给包含这个页的span。我们做的只是将申请来的内存进行标记从而来使用内存。只是逻辑上对于内存池的分配

 

项目源码：https://github.com/YKitty/CurrentmentMemory/tree/master/memPool