前言
上期介绍了线程缓存层 thread cache ，本期我们进行 中心缓存层 即 central cache 的介绍与实现，以及完善 thread cache 没有内存时向 central cache 获取的那个接口！
目录
前言
一、central cache 的整体设计
二、central cache 的结构设计
三、central cache 的核心实现
一、central cache 的整体设计
当线程申请某一大小的内存时，如果其 thread cache 对应的哈希桶中的自由链表不为空，则直接取出一个返回即可。如果为空那么 thread cache 的就需要去 central cache 申请了
central cache 与 thread cache 的结构是一样的，也是一个哈希桶结构，映射规则也是一样的，这样做的好处就是当thread cache 没有内存时，就可以直接根据所需的内存大小通过和thread cache 一样的映射规则找到 central cache 对应桶去获取内存了
thread cache 与 central cache 的区别
thread cache 与 central cache 的区别主要有两个：
第一：他两哈希位置存放的内容不一样
thread cache 的每个哈希桶中挂的是一个个的切好的内存对象，也就是每个哈希位置都是一个个的定长内存的自由链表。而central cache 的每个哈希桶中挂的是一个个的 Span 对象，在每个哈希桶中的 Span 对象是根据带头双向循环链表组织的，也就也是说 central cache 的每一个哈希位置都是一个个的 节点为 Span 的带头双向循环链表
Span 对象是管理以页为单位的大块内存，它里面有一个自由链表，管理的是将大块内存根据哈希桶的位置切成固定大小的内存块对象！
第二： thread cache 的每一个哈希位置是无锁的，而 central cache 是需要加锁的
thread cache 是每一个线程私有的(TLS)，因此每一个线程在他的thread cache 获取内存时是不需要加锁的，但是每个thread cache 没有内存时都会去向 central cache 获取，此时central cache 是存在线程安全的，所以必须得加锁。这里采用的是桶锁，即每一个哈希桶一个锁。设置为桶锁的目的是：为了减少锁竞争的问题。只有当两个 thread cache 同时访问同一个central cache 的桶时，才会出现竞争锁的问题，如果两个或以上的 thread cache 访问不同位置的桶，不会出现锁竞争的问题，这样就比整体加锁的性能好很多
二、central cache 的结构设计
页号的类型设计
每个程序运行起来之后都会变成一个进程，有自己独立的进程地址空间，在32位平台下，进程的地址空间大小是 2^32；而在64位平台下，进程地址空间的大小就是2^64。
一般一个页的大小是 4K / 8K，这里我们以 8K 为例。32位的地址空间就可以被分成 2^32 / 2^13 = 2^19 个页，64 位的地址空间就可以被分成 2^32 / 2^13 = 2^51 个页。其实页号和地址本质是一样的，都是一个编号，地址是一个字节为单位，页号是 N 个字节为单位。
由于在64位下有 2^51 个页， 所以页号的范围是：[0, 2^51) 这已经不能使用 size_t 存下的了，这里我们考虑使用条件编译的方式进行控制：
// 控制页号的类型
#ifdef _WIN64typedef unsigned long long PAGE_ID;
#elif _WIN32typedef size_t PAGE_ID;
#else// linux...
#endif // _WIN64需要注意的是：在 32位下，有 _WIN32 的定义，没有 _WIN64 的定义。在64 位下，既有_WIN64的定义，又有_WIN32的定义。所以我们应该在条件编译时，优先判断是否有 _WIN64 的定义然后在判断 _WIN32 是否定义。
Span 的结构设计
central cache 中的每个哈希桶中都挂的是一个个的 Span 对象，Span 管理的时以页为单位的大块内存，其结构如下：
// 管理以页为单位的大块内存
struct Span
{PAGE_ID _id = 0; // 大块内存的起始页号size_t _n = 0; // 当前 Span 管理大块内存的数量，即页数Span* _next = nullptr; //双链表结构Span* _prev = nullptr;size_t _useCount = 0; //切好的小内存分给 thread cache 的数量void* _freelist = nullptr; //管理切好小块内存的自由链表
};对于 Span 管理的以页为单位的大块内存，我们需要知道这亏内存具体是在哪一个位置，便于后续 page cache 层进行前后页的合并，因此需要一个记录当前页的起始位置的页号 PAGE_ID。
至于一个 Span 中有多少页，这是不确定的。例如： 8字节的那个桶，可能一页就够了，而 256K 的则需要很多页，所以Span 中有一个成员 _n 记录当前的 Span 有多少页。
因为central cache 会将大块的内存按照映射规则，切成固定大小的小内存对象，因此也需要一个自由链表来管理。
Span 中的 _useConut 表示的是 将切好用自由链表管理的定长的内存对象，分配给 thread cache 的数量。 分配给thread cache则_useCount++, 还回来 _useConut--；当 _useConut 为 0 表示都换回来了，此时可以将这个 Span 的大块内存还给下一层 page cache。
Central Cache 中的每个位置都是一个带头双向循环链表，原因是当 _ useConut = 0 需要将该Span 给Page Cache 时，比单链表方便。
封装Span结构的双链表
根据上面的介绍，central cache 中的每个哈希桶的位置都是一个带头双向循环链表，我们先来封装一下该双链表。
// 双链表结构
class SpanList
{
public:SpanList(){_head = new Span;_head->_next = _head;_head->_prev = _head;}void Insert(Span* pos, Span* newSpan){assert(pos);assert(newSpan);Span* prev = pos->_prev;prev->_next = newSpan;newSpan->_prev = prev;newSpan->_next = pos;pos->_prev = newSpan;}void Erase(Span* pos){assert(pos);assert(pos != _head);Span* prev = pos->_prev;Span* next = pos->_next;// 这里不是真的删除，只是将该 span 从双链表中删除，还给 page cache ,不需要 deleteprev->_next = next;next->_prev = prev;}private:Span* _head;
public:std::mutex _mtx; // 桶锁
};注意：这里的删除并不是传统的那种删除，这里的删除是将 span 对象从 双链表中移除，将内存还给 page cache 层，所以并不需要 delete
central cache 结构
central cache 的映射规则和thread cache 的映射规则一样，因此 central cache 的哈希桶的个数也是 208 个，但每个哈希桶位置挂的是一个带头双向循环链表
class CentralCache
{
public:// ...
private:SpanList _spanlists[N_FREE_LIST];// 映射规则和thread cache 一样所以也是 208 个桶
};central cache和thread cache的映射规则一样，有一个好处就是，当thread cache的某个桶没有内存了，就可以直接根据映射规则去central cache对应的哈希桶进行申请就行了。
三、central cache 的核心实现
central cache 的单例设计
每个线程都有一个自己私有的 thread cache，我们是采用TLS来实现每个线程访问自己的 thread cache的。而 central cache 和 page cache 在整个进程中只有一个，对于这种只是个创建一个对象的类，我们一般设计为 单例模式。
单例模式可以保证该类的对象在全局只存在一个，并且在提供一个全局访问的单例句柄，在全局内该单例句柄是共享的。单例模式的实现又分为：饿汉模式 和 懒汉模式。这里采用最简单的恶汉模式。
另外， central cache 中目前有两个方法，一个是在当前桶中获取一个非空的 span 对象；另一个是从中心缓存中给一定数量的对象给 thread cache ，因为获取到的那些都是从自由链表中截取下来的 多个 所以我们采用 输出型参数的方式接收；
// 单例模式
class CentralCache
{
public:// 提供一个获取单例对象的全局的句柄static CentralCache* GetInstance(){return &_sInst;}// 获取一个非空的spanSpan* GetOneSpan(SpanList& list, size_t byte_size);// 从中心缓存获取一定数量的对象给thread cachesize_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size);private:// 价格构造私有化、拷贝构造/赋值拷贝禁用CentralCache(){}CentralCache(const CentralCache&) = delete;// C++11CentralCache& operator=(CentralCache&) = delete;
private:SpanList _spanlists[N_FREE_LIST];// 映射规则和thread cache 一样所以也是 208 个桶static CentralCache _sInst;//恶汉模式，类里申明,类外面(cpp)定义
};#include "CentralCache.h"// static 定义的成员，在类外面实现
CentralCache CentralCache:: _sInst;为了保证 CentralCache 有唯一的一个全局的对象（实现单例），我们需要将CentralCache的构造、拷贝构造、赋值拷贝全部给私有化/禁用掉。
慢开始调节算法
当 thread cache 向 central cache 申请内存时，central cache 一次性应该给 thread cache 多少呢？如果一次给的太少，短时间内可能会出现频繁申请的现象，如果一次给的太多，有可能导致 thread cache 用不了那么多，而导致内存的浪费。
鉴于此，我们这里采用慢开始调节算法。当thread cache 向 central cache 申请内存时，如果申请的对象较小，那么可以多给一些；如果申请的对象较大，那么可以少给一点。
所以我们在SizeClass中下面这个函数，就可以根据所需的内存大小计算出具体应该给出对象的个数，并且将个数控制在 2 - 512 之间。即就算 thread cache 申请的对象再小，我们也不可能给很多个，而是给 最多512个；就算 thread cache 申请的对象再大，我们一次性给出两个对象。
// thread cache 一次从 central cache 获取到的内存对象的个数
static size_t NumMoveSize(size_t size)
{assert(size > 0);// size 越大，上限越小// size 越小，上限越大int num = MAX_BYTES / size;if (num < 2)num = 2;if (num > 512)num = 512;return num;
}尽管上面这两控制已经避免了一些内存浪费了，但还有优化的空间。当申请小内存对象时，一次性给512个还是有点浪费的，大多数情况下是用不了 512 个的，基于此我们在 FreeList 中增加一个_maxSize 的成员属性来控制，该变量的初始值为 1 ；即thread cache 中的每个自由链表都有一个自己的 _maxSize
class FreeList
{
public:// ...size_t& MaxSize(){return _maxSize;}private:void* _freelist = nullptr;size_t _maxSize = 1;// 初始值给成1，表示第一次申请一个内存对象
};因此，当 thread cache 获取对象时，我们会比较 _maxSize 和 计算应该获取到的数量 两者取最小作为向 central cache 申请内存的个数，此外如果本次采用的时 _maxSize 我们会对 _maxSize 的值加一，一次它的返回值是引用。
thread cache第一次向central cache申请某大小的对象时，申请到的都是一个，但下一次thread cache再向central cache申请同样大小的对象时，因为该自由链表中的_maxSize增加了，最终就会申请到 两个 直到该自由链表中_maxSize的值，增长到超过 计算出的值 后就不会继续增长了，此后申请到的对象个数就是计算出的个数。（这有点像网络中拥塞控制的机制）
thread cache 从 central cache 获取内存对象
每次thread cache向central cache申请对象时，先是根据 慢开始调节算法 计算出本次应该申请的对象的个数，然后在向 central cache 进行申请。
如果 thread cache 获取到的对象是一个，则直接返回即可；如果是多个，则将第一个返回，将剩下的挂到thread cache 对应的 哈希桶中。
// 从中心缓存获取对象
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size) // index 表示 哈希桶的下标，size 表示申请的内存大小
{// 慢开始调节算法// 最开始向 central cache 申请的个数不多，避免太多了用不完浪费// 如果对同一个size 的对象又不断的需求，batchNum 就会不断地增长，直到上线size_t batchNum = std::min(_freelists[index].MaxSize(), SizeClass::NumMoveSize(size));if (batchNum == _freelists[index].MaxSize()){_freelists[index].MaxSize()++;}void* start = nullptr;void* end = nullptr;// 根据慢反馈调节算法去central cache 获取 batchNum 个对象size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);assert(actualNum >= 1);// 至少有一个if (actualNum == 1){// 只有一个直接返回assert(start == end);return start;}else{// 大于一个将第一个返回，将剩余的插入到对应哈希桶的位置_freeLists[index].PushRange(NextObj(start), end);return start;}
}以一段范围的自由链表的插入
当我们从 central cache 申请了多个内存对象时，将一个返回，其余的挂到对应哈希桶中，但是前面的FreeList中没有提供插入一段范围的，所以这里写一个！
实现思路很简单，就是头插。将end 的头部存上以前 _freelist ，让_freelist指向 start即可！
class FreeList
{
public://插入一段范围的对象到自由链表void PushRange(void* start, void* end){assert(start);assert(end);//头插NextObj(end) = _freelist;_freelist = start;}// ...private:void* _freelist = nullptr;size_t _maxSize = 1;// 初始值给成1，表示第一次申请一个内存对象
};central cache 获取一定数量的 对象给 thread cache
这里我们要从central cache获取n个指定大小的对象，这些对象肯定都是从central cache对应哈希桶的某个span中取出来的，因此取出来的这n个对象是链接在一起的，我们只需要得到这段链表的头和尾即可，这里可以采用输出型参数进行获取。
//从central cache获取一定数量的对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t n, size_t size)
{size_t index = SizeClass::Index(size);// 根据size 确定在几号桶中获取// 加锁_spanlists[index]._mtx.lock();// 在对应的哈希桶中获取一个 非空的 SpanSpan* span = GetOneSpan(_spanlists[index], size);assert(span); //span不为空assert(span->_freelist); //span当中的自由链表也不为空// 从 span 中获取 n 个对象，如果不够，有多少拿多少start = span->_freelist;end = span->_freelist;size_t actualNum = 1;// 因为 start 和 end 都是一开始指向 _freelist 的，即默认至少一个size_t i = 0;while (i < n - 1 && NextObj(end))// 避免不够n的时候奔溃{end = NextObj(end);i++;actualNum++;}// 将原先的span->_freelist指向end 的后一个span->_freelist = NextObj(end);NextObj(end) = nullptr;// 将申请的 那一段的最后一个的下一个置为空span->_useCount += actualNum;// 更新分配给 thread cache 的个数// 解锁_spanlists[index]._mtx.unlock();return actualNum;
}因为 central cache 是所有线程共享的，因此我们在 central cache 申请内存时，首先需要先给对应的哈希桶加上锁，在获取完成之后再将其解锁。
在向central cache获取对象时，先是在central cache对应的哈希桶中获取到一个非空的span，然后从这个span的自由链表中取出n个对象即可，但可能这个非空的span的自由链表当中对象的个数不足n个，这时该自由链表当中有多少个对象就给多少就行了。
也就是说，thread cache实际从central cache获得的对象的个数可能与我们传入的n值是不一样的，因此我们需要统计本次申请过程中，实际thread cache获取到的对象个数，然后根据该值及时更新这个span中的小对象被分配给thread cache的计数。
需要注意的是，虽然我们实际申请到对象的个数可能比n要小，但这并不会产生任何影响。因为thread cache的本意就是向central cache申请一个对象，我们之所以要一次多申请一些对象，是因为这样一来下次线程再申请相同大小的对象时就可以直接在thread cache里面获取了，而不用再向central cache申请对象。
OK，中心缓存层就到这里，我们下一期介绍 page cache层。
