高并发内存池 - page cache 整体设计

高并发内存池 - page cache 整体设计项目 gitee 链接 高并发内存池项目项目 github 链接 高并发内存池项目这一层来到Page Cache我们将对其的整体设计进行解析。首先还是以SpanList为基本结构但与Central Cache有几处不同。它不再保持和Thread Cache的映射关系而是根据Span中存储的页数进行划分将有着相同页数大小的Span划分到了一个SpanList。将结构明晰后我们梳理一下申请内存的逻辑当Central Cache向Page Cache申请内存时Page Cache先检查对应位置有没有Span如果没有则向更⼤⻚寻找⼀个Span如果找到则分裂成两个。⽐如申请的是 4 ⻚ page4 ⻚ page 后⾯没有挂Span则向后⾯寻找更⼤的Span假设在 10 ⻚ page 位置找到⼀个Span则将 10 ⻚page Span分裂为⼀个 4 ⻚page span和⼀个 6 ⻚page span。如果找到_spanList[128]都没有合适的Span则向系统使⽤ mmap、brk 或者是 VirtualAlloc 等⽅式申请 128 ⻚page Span挂在⾃由链表中再重复 1 中的过程。需要注意的是Central Cache和Page Cache的核⼼结构都是Spanlist的哈希桶但是他们是有本质区别的Central cache中哈希桶是按跟Thread Cache⼀样的⼤⼩对⻬关系映射的他的Spanlist中挂的Span中的内存都被按映射关系切好链接成⼩块内存的⾃由链表。⽽Page Cache中的Spanlist则是按下标桶号映射的也就是说第 i 号桶中挂的 span 都是 i ⻚内存。释放内存如果Central Cache释放回⼀个Span则依次寻找Span的前后Page id的没有在使⽤的空闲Span看是否可以合并如果合并继续向前寻找。这样就可以将切⼩的内存合并收缩成⼤的Span减少内存碎⽚。在讲解完申请内存和释放内存的逻辑后有几个设计中的要点需要重点讲解锁设计在哪里在剖析完申请内存后会发现是有多个线程向Page cache申请内存的可能的但好像都只是在各自的桶内申请所以只需要设计桶锁就够了么答案显然是否定的。问题就在Page Cache如果桶中没有Span后会尝试分割更大的Span然后将分割完后的Span放入对应的桶中这说明申请内存时并非是桶与桶独立的而是会产生交集这样就可能产生死锁情况假设线程 A 申请 1 页但Page Cache的SpanList[1]为空。它只能去更大的桶找比如SpanList[8]里有一个 8 页的Span。分割流程从SpanList[8]取出这个 8 页Span切分成 1 页 7 页把 1 页返回给上层把剩余的 7 页 挂回SpanList[7]如果此时只锁SpanList[8]的桶锁步骤 1 可以安全取出锁住了但步骤 4 需要把 7 页挂到SpanList[7]这需要另一把锁SpanList[7]._bucketMtx此时就会面临两个致命问题死锁风险如果线程 B 同时申请 7 页发现SpanList[7]为空去SpanList[8]找——两把锁的获取顺序相反经典死锁。竞态条件即使你用固定顺序加锁避免死锁切分过程中的状态对其他线程是可见的。看这个时间线时间线程 A申请 1 页线程 B申请 7 页T1拿到SpanList[8]桶锁取出 8 页 SpanT2释放SpanList[8]桶锁已经取出来了T3开始切分此时 8 页 Span 已不在任何桶里T4检查SpanList[7]为空T5检查SpanList[8]也为空因为被 A 取走了T6线程 B 认为系统没有 7 页内存去向系统申请brk/mmapT7线程 A 切分完把 7 页挂到SpanList[7]结果线程 B 白白向 OS 申请了一块新内存而实际上线程 A 马上就会释放一个 7 页Span到SpanList[7]。这导致内存碎片增加、系统调用开销翻倍、Page Cache失去了缓存合并的意义。所以不推荐使用桶锁的底层原因是什么呢桶锁的粒度太小无法把跨桶的切分-迁移包装成一个原子事务。如果可以包装成一个原子事务就不会出现上述的致命问题所以对于Page Cache要设计一把大锁。Page Cache可以采用什么模式设计这里其实算是一个知识点的深入和拓展借着Page Cache抛砖引玉出来。对于一个进程Page Cache只有一个不会产生多个所以可以思考到使用单例模式来实现单例模式有两种实现方法饿汉模式懒汉模式最终我们选择饿汉模式因为选择懒汉模式会产生几个较大的问题。1. 指令重排问题对于new PageCache一行代码编译器会将其拆分成三步分配内存_sInstnewPageCache();在内存上构造对象PageCache*objnew(raw)PageCache();// 调用构造函数把地址赋值给指针_sInstobj;这三个步骤在 C 的抽象机器里是有先后顺序的但编译器和 CPU 为了优化性能可能把步骤 3 重排到步骤 2 之前。编译器认为“new PageCache()的返回值最终就是要给_sInst的而构造函数里如果没有用到_sInst那先把地址写进去再执行构造似乎也没问题”于是可能生成这样的机器码1. call operator new ; 分配内存地址暂存寄存器 eax 2. mov [_sInst], eax ; ⚠️ 先把地址写入 _sInst步骤3提前了 3. call PageCache::ctor ; 调用构造函数步骤2被延后了即使编译器没重排现代 CPUx86、ARM为了提高流水线效率也会乱序执行Out-of-Order Execution。只要两个指令没有数据依赖CPU 可能先执行mov [_sInst], eax再执行构造函数。2. 时序推演问题假设有两个线程 A 和 B 同时调用GetInstance()GetInstance() 函数的功能是获取单例模式中对象的地址。staticPageCache*GetInstance(){if(_sInstnullptr){// 第一次检查无锁std::lock_guardstd::mutexlock(_mtx);if(_sInstnullptr){// 第二次检查有锁_sInstnewPageCache();// 危险区}}return_sInst;}时间线程 A线程 BT1第一次检查_sInst nullptr✅T2获取锁_mtxT3第二次检查_sInst nullptr✅T4执行new分配内存T5⚠️指令重排把地址写入_sInst构造还没完成T6第一次检查_sInst ! nullptr❌T7直接返回_sInstT8线程 B 拿到指针调用成员函数…T9崩溃对象还没构造完vtable 未初始化、成员变量是垃圾值T10调用构造函数完成正是因为new PageCache()不是原子操作编译器可能重排指令导致其他线程拿到构造了一半的指针先赋值地址再执行构造函数。当然由于 C11 新特性的引入这个问题已经能用新的方法来解决但这个问题还是要在此提出作者觉得这个问题还是很好的有助于能力的提升。关于Page Cache的整体框架分析就到此结束了下面直接展示现阶段可以实现的代码部分其余部分后续篇章会进行讲解。Page Cache.h#pragmaonce#includeComm.hclassPageCache{public:staticPageCache*GetInstance(){return_sInst;}Span*NewSpan(size_t k);//要的 Span 长度为几页private:std::mutex _pageMtx;//桶锁在 PageCache 中是行不通的需要整体上锁SpanList _spanLists[NPAGES];PageCache(){}PageCache(constPageCache)delete;staticPageCache _sInst;};Page Cache.cpp#includePageCache.hstaticPageCache _sInst;静态成员变量的初始化要放在 .cpp 文件中放入头文件中会被重复包含引发链接报错。本篇文章到此结束让我们下篇文章再见