【项目日记】高并发内存池项目---整体框架设计

高并发内存池项目---整体框架设计

1 整体框架

现代很多的开发环境都是多核多线程，在申请内存的场景下，必然会存在激烈的锁竞争问题，锁竞争会有一部分的性能损耗（因为需要阻塞等待）。malloc本身其实已经很优秀，那么我们项目的原型tcmalloc就是在多线程高并发的场景下更胜一筹，效率更加优秀。这次我们实现的内存池需要考虑以下几方面的问题：

1. 性能问题。
2. 多线程环境下，锁竞争问题。
3. 内存碎片问题。

针对这三个问题，将通过三个模块进行分层处理：

• 线程缓存（ThreadCache）
• 中心缓存（CentralCache）
• 页缓存（PageCache）

他们的关系是这样的：

2 线程缓存

• thread cache：线程缓存是每个线程独有的，用于小于256KB的内存的分配，线程从这里申请内存不需要加锁，每个线程独享一个cache，这也就是这个并发线程池高效的地方。没有锁的限制，就不会进行阻塞等待，而是自己使用自己的缓存！

在线程缓存底层，是一个大数组，每个数组是一个自由链表。按照一定规则下将256KB的内存进行对齐分配，共产生208个自由链表！

每次线程申请对于空间的地址，会找到映射的自由链表，并进行取出使用。如果为空了，就向中心缓存中申请！

申请内存：

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

释放内存：

1. 当释放内存小于256k时将内存释放回thread cache，计算size映射自由链表桶位置i，将对象Push到对应自由链表中。
2. 当链表的长度过长，就需要回收一部分内存对象到中心缓存。

3 中心缓存

• central cache：中心缓存是所有线程所共享，thread cache是按需从central cache中获取的对象。central cache合适的时机回收thread cache中的对象，避免一个线程占用了太多的内存，而其他线程的内存吃紧，达到内存分配在多个线程中更均衡的按需调度的目的。
• central cache是存在竞争的，所以从这里取内存对象是需要加锁，首先这里用的是桶锁，其次只有thread cache的没有内存对象时才会找central cache，所以这里竞争不会很激烈。

中心缓存也是一个哈希桶结构，他的哈希桶的映射关系跟线程缓存是一样的。不同的是他的每个哈希桶位置挂是SpanList链表结构，不过每个映射桶下面的span中的大内存块被按映射关系切成了一个个小内存块对象挂在span的自由链表中。

我们默认系统的一页内存是8KB，span管理的大块儿内存实际上是大页内存，可能是一页,两页内存,这个大页内存会被切分为小块儿的内存，8字节对应的哈希桶中会切分为8字节的小块儿内存，这样可以很方便的将小块儿内存分配给线程缓存！

中心缓存就像是线程缓存的弹药包，中心缓存中的链表中每个对象，都是对应线程缓存链表的一个大弹药包，可以供线程内存使用！

申请内存：

1. 当线程缓存中没有内存时，就会批量向中心缓存申请一些内存对象，这里的批量获取对象的数量使用了类似网络tcp协议拥塞控制的慢开始算法；中心缓存也有一个哈希映射的spanlist，spanlist中挂着span，从span中取出对象给线程缓存，这个过程是需要加锁的，这里使用的是一个桶锁，尽可能提高效率。
2. 中心缓存映射的spanlist中所有span的都没有内存以后，则需要向页缓存申请一个新的span对象，拿到span以后将span管理的内存按大小切好作为自由链表链接到一起。然后从span中取对象给线程缓存。
3. 中心缓存中挂载的span中有一个计数器use_count记录分配了多少个对象出去，分配一个对象给线程缓存，就++use_count！

释放内存：

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

4 页缓存

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

申请内存：

1. 当中心缓存向页缓存申请内存时，页缓存先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。 比如：申请的是4页page，4页page后面没有挂span，则向后面寻找更大的span，假设在10页page位置找到一个span，则将10页pagespan分裂为一个4页page span和一个6页page span。
2. 如果找到_spanList[128]都没有合适的span，则向系统使用mmap、brk或者是VirtualAlloc等方式申请128页page span挂在自由链表中，再重复1中的过程。
3. 需要注意的是中心缓存和页缓存的核心结构都是spanlist的哈希桶，但是他们是有本质区别的:
   • 中心缓存中哈希桶，是按跟线程缓存一样的大小对齐关系映射的，他的spanlist中挂的span中的内存都被按映射关系切好链接成小块内存的自由链表。
   • 页缓存中的spanlist则是按下标桶号映射的，也就是说第i号桶中挂的span都是i页内存。

释放内存：

1. 如果中心缓存释放回一个span，则依次寻找span的前后page id，如果有对应ID的未使用的空闲span，看是否可以合并，如果合并继续向前寻找。这样就可以将切小的内存合并收缩成大的span，减少内存碎片。