你好，我是安然無虞。

page cache的設(shè)計及實現(xiàn)

page cache 本質(zhì)上也是一個哈希桶, 它是按照頁的數(shù)量進行映射的. 當(dāng) central cache 向 page cache 申請內(nèi)存時, page cache 先檢查對應(yīng)位置是否有span, 如果沒有則向更大頁去尋找一個span, 如果找到則分裂成兩個. 比如: 你申請7page的內(nèi)存, 7頁后面沒有掛span, 則向后面尋找更大的span, 假設(shè)在10頁位置找到了span, 則將10頁的span分裂成7頁的span和3頁的span.

如果找到 _spanLists[128] 都沒有合適的span, 則向系統(tǒng)堆申請128頁的span掛到 _spanLists[128] 上.

可能大家會疑惑, 為什么是128, 而不是別的數(shù)字?
這個問題也就等同于為什么 page cache 中最大掛128頁的span? 因為在這個項目里我們規(guī)定線程申請單個對象最大是256KB, 而128頁可以被切成4個256KB的對象, 因此是足夠的.
當(dāng)然了, 具體情況具體分析, 在別的特殊場景下也可以自行設(shè)置.

//page cache 中哈希桶的個數(shù)
static const size_t NPAGES = 129;

為了讓哈希桶的下標(biāo)和頁數(shù)對應(yīng)起來, 我們將哈希桶的個數(shù)設(shè)置成129個, 也就是將0號下標(biāo)舍棄.

---

page cache與central cache的不同:

我們知道 central cache 和 page cache 的核心結(jié)構(gòu)都是 SpanList 的哈希桶, 但是它們的本質(zhì)是有區(qū)別的, central cache 的哈希桶跟 thread cache 一樣, 都是按照大小對齊關(guān)系映射的, 它的 SpanList 中掛的 span 中的內(nèi)存都被按映射關(guān)系切好鏈接成小塊內(nèi)存的自由鏈表, 而 page cache 中的 SpanList 則是按照下標(biāo)桶號映射的, 也就意味著第 i 號桶下面掛的span都是 i 頁內(nèi)存.

還有一點就是 central cache 中的多個桶可能會同時向 page cache 申請內(nèi)存, 所以 page cache 是存在線程安全問題的, 因此在訪問 page cache 時必須要加鎖. 但是在page cache 這里我們不能像 central cache 一樣使用桶鎖, 因為當(dāng) central cache 向 page cache 申請內(nèi)存時, page cache 可能會將其他桶當(dāng)中大頁span切小, 也就是說會訪問到其他桶. 而且, 當(dāng)central cache 將某個span歸還給 page cache 時, page cache 也會嘗試將該span與其他桶當(dāng)中的span進行合并.

總之就是, 在訪問 page cache 時, 我們可能需要訪問 page cache 中的多個桶, 如果 page cache 用桶鎖就會出現(xiàn)大量頻繁的加鎖和解鎖操作, 導(dǎo)致程序的整體效率低下. 因此我們在訪問 page cache 時用一把大鎖將整個 page cache 給鎖住.

而 thread cache 在訪問 central cache 時, 也可能出現(xiàn)多個 thread cache 同時訪問 central cache 的情況, 但是我們的 central cache 使用的是桶鎖, 因為 central cache 的每個哈希桶中的span都被切分成了對應(yīng)大小的內(nèi)存對象并且通過自由鏈表鏈接起來了, thread cache 只需要根據(jù)自己所需對象的大小訪問 central cache 中對應(yīng)的哈希桶即可, 不會訪問其他哈希桶, 因此 central cache 可以用桶鎖.

---

page cache的實現(xiàn)方式

page cache在整個進程中也是只能存在一個的, 因此我們也需要將其設(shè)置為和 central cache 一樣的單例模式.

// page cache本質(zhì)是一個按頁數(shù)映射的哈希桶
class PageCache
{
public:// 提供一個全局訪問點static PageCache* GetInstance(){return &_sInst;}// 獲取一個k頁的spanSpan* NewSpan(size_t k);private:// 構(gòu)造和拷貝構(gòu)造設(shè)置為私有PageCache(){}PageCache(const PageCache&) = delete;static PageCache _sInst;private:SpanList _spanLists[NPAGES];public:std::mutex _pageMtx; // 一把大鎖
};

程序運行起來直接創(chuàng)建出該對象:

PageCache PageCache::_sInst;

---

page cache中獲取span

獲取一個非空的span

我們知道 thread cache 在向 central cache 申請內(nèi)存對象時, central cache 要先從對應(yīng)的哈希桶中獲取一個非空的span, 然后從這個span中取出若干個內(nèi)存對象給 thread cache, 試問如何獲取到這個非空的span呢?

首先遍歷當(dāng)前位置映射的雙向鏈表, 如果該雙向鏈表中有非空的span, 直接返回即可. 說到遍歷, 需要在SpanList的定義當(dāng)中給出Begin成員函數(shù)和End成員函數(shù), 方便我們像使用迭代器一樣遍歷雙向鏈表.

// 雙向鏈表結(jié)構(gòu)
class SpanList
{
public:SpanList(){_head = new Span;_head->_prev = _head;_head->_next = _head;}// 第一個spanSpan* Begin(){return _head->_next;}// 最后一個span的下一個位置Span* End(){return _head;}private:Span* _head = nullptr;
};

如果當(dāng)前位置映射的SpanList中沒有非空的span, 那么只能向 page cache 中申請大塊內(nèi)存了.

但是需要從 page cache 中獲取多大的內(nèi)存呢? 這個由具體對象的大小決定, 我們可以先根據(jù)對象的大小計算出 thread cache 一次向 central cache 獲取對象數(shù)量的上限值, 然后將這個上限值乘以單個對象的大小, 計算出具體需要多少字節(jié), 最后再將這個算出來的字節(jié)數(shù)轉(zhuǎn)換為頁數(shù), 如果轉(zhuǎn)換后不夠一頁, 那么我們就申請一頁, 否則轉(zhuǎn)換出來是幾頁就申請幾頁. 也就是說, central cache 向 page cache 申請內(nèi)存時, 要求申請到的內(nèi)存盡量能夠滿足 thread cache 向 central cache 申請時的上限.

// 管理對齊和映射的關(guān)系
class SizeClass
{
public:// 一次向page cache要多少頁static size_t NumMovePage(size_t size){size_t num = NumMoveSize(size); // thread  cache一次向central cache獲取對象的上限值size_t npage = num * size; //num個size大小的對象所需的字節(jié)數(shù)npage >>= PAGE_SHIFT; // 將字節(jié)數(shù)轉(zhuǎn)化成頁數(shù)if (npage == 0)npage = 1; // 最少給一頁return npage;}
};

其中 PAGE_SHIFT 表示頁大小轉(zhuǎn)換偏移, 這里我們按每頁8K的大小為例, 那么PAGE_SHIFT 的大小就是13.

// 頁大小轉(zhuǎn)換偏移，即一頁定義為2^13Byte，也就是8KB
static const size_t PAGE_SHIFT = 13;

當(dāng) central cache 申請到了這個若干頁的span之后, 還需要將其切成一個個所需要的內(nèi)存對象鏈接起來, 然后掛到span的自由鏈表當(dāng)中.

那怎么對這個大塊span進行切分呢? 首先根據(jù)大塊內(nèi)存起始頁的頁號計算出大塊內(nèi)存的起始地址, 再根據(jù)大塊內(nèi)存的頁數(shù)計算出大塊內(nèi)存的大小, 然后利用起始地址和大塊內(nèi)存的大小計算出大塊內(nèi)存的結(jié)束地址.

有了大塊內(nèi)存的起始地址和結(jié)束地址, 那么對其進行切分就簡單多了, 但是有一點需要注意的是為什么我們這里選用的是尾插, 而不是頭插呢?

因為將切好的對象尾插到自由鏈表, 這些對象看起來是按照鏈?zhǔn)浇Y(jié)構(gòu)鏈接起來的, 而實際它們在物理上是連續(xù)的, 這時當(dāng)我們把這些連續(xù)內(nèi)存分配給某個線程使用時, 可以提高該線程的CPU緩存利用率, 這樣一來CPU高速緩存命中率會更高.

補充: CPU高速緩存命中率知識點

一般程序編譯連接后, 生成可執(zhí)行程序, CPU執(zhí)行這個程序時需要去訪問內(nèi)存, 但是CPU太快了, 比內(nèi)存快得多, 于是CPU總是在等內(nèi)存.

所以CPU不會直接去訪問內(nèi)存, 因為它嫌內(nèi)存的速度太慢了, 所以CPU會把數(shù)據(jù)加載到三級緩存或者寄存器中, 一般小數(shù)據(jù)加載到寄存器中, 大數(shù)據(jù)加載到緩存中.

那什么叫做命中呢? CPU會看數(shù)據(jù)是否在緩存, 在就叫命中, 可以直接訪問, 不在就叫不命中, 此時需要先把數(shù)據(jù)從內(nèi)存加載到緩存中, 之后再訪問.

所以針對CPU高速緩存命中率這個知識點, 我們可以用之前學(xué)習(xí)的順序表和鏈表來舉例子:
首先我們知道順序表在物理空間上是連續(xù)的, 而鏈表在物理空間上是不連續(xù)的.

當(dāng)我們訪問順序表第一個元素時, 會看其是否在緩存中, 不在, 不命中, 然后就把后面的一段加載到緩存中去(具體加載多少, 看硬件), 然后再訪問后面的元素就都命中了.

如果是鏈表, 雖然也會將后面的一段數(shù)據(jù)加載到緩存中, 但是鏈表在物理上是不連續(xù), 隨機存儲的, 所以命中率會低一些.

---

有了上面的基礎(chǔ), 請看具體代碼實現(xiàn):

// 從SpanList或者page cache獲取一個非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{// 判斷當(dāng)前的SpanList是否有非空的spanSpan* it = list.Begin();while (it != list.End()){if (it->_freeList != nullptr){return it;}else{it = it->_next;}}// 解除桶鎖, 方便thread cache釋放內(nèi)存回來list._mtx.unlock();// 走到這說明需要從page cache獲取一個非空的spanPageCache::GetInstance()->_pageMtx.lock();Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(size));PageCache::GetInstance()->_pageMtx.unlock();// 計算大塊內(nèi)存所在的地址和大小char* start = (char*)(span->_pageId << PAGE_SHIFT); // 大塊內(nèi)存的起始地址size_t bytes = span->_n << PAGE_SHIFT; // 大塊內(nèi)存的大小 - 字節(jié)數(shù)char* end = start + bytes; // 大塊內(nèi)存的結(jié)束地址// 將獲取到的span切成小塊內(nèi)存鏈接起來// 先切一塊下來做頭, 方便尾插span->_freeList = start;void* tail = span->_freeList;start += size;while (start < end){NextObj(tail) = start;tail = start;start += size;}list._mtx.lock(); // 加在前面// 將切好的span插入central cache的SpanList中list.PushFront(span);return span;
}

對于上面的代碼我們還需要注意的是加鎖解鎖問題, 了解代碼后就會知道, 當(dāng) central cache 向 page cache 申請內(nèi)存時, central cache 對應(yīng)的哈希桶是處于加鎖狀態(tài)的, 那在訪問 page cache 之前我們應(yīng)不應(yīng)該把 central cache 對應(yīng)的桶鎖解掉呢?

這里建議在訪問 page cache 前, 先把 central cache 對應(yīng)的桶鎖解掉, 雖然此時 central cache 的這個桶當(dāng)中是沒有內(nèi)存供其他 thread cache 申請的, 但 thread cache 除了在 central cache中申請內(nèi)存外, 還會釋放內(nèi)存回到 central cache 中, 如果在訪問 page cache 前將 central cache 對應(yīng)的桶鎖解掉, 那么此時如果有 thread cache 想要歸還內(nèi)存給 central cache 的這個桶時就不會被阻塞.

還需要注意的是在調(diào)用 NewSpan 函數(shù)之前, 還需要將 page cache 的大鎖加上, 當(dāng)申請到k頁的span后, 我們需要將 page cache 的大鎖解掉, 但此時我們不需要立刻獲取到 central cache 中對應(yīng)的桶鎖. 因為 central cache 拿到k頁的span后還會對其進行切分操作, 因此我們可以在span切好后需要將其掛到 central cache 對應(yīng)的桶上之前, 獲取對應(yīng)的桶鎖.

---

獲取一個k頁的span

當(dāng)我們調(diào)用 GetOneSpan 函數(shù)從 central cache 的某個哈希桶獲取一個非空的span時, 如果遍歷哈希桶中的雙向鏈表后發(fā)現(xiàn)其中沒有span, 或該雙向鏈表中的span都為空, 那么此時 central cache 就需要向 page cache 申請若干頁的span.

因為 page cache 是直接按照頁數(shù)進行映射的, 因此我們要從 page cache 中獲取一個k頁的span, 就應(yīng)該直接去找 page cache 的第k號桶, 如果第k號桶中有span, 那我們直接頭刪一個span返回給 central cache 就行了, 如果沒有, 繼續(xù)向下遍歷直至最后一個桶, 在這期間, 如果第n號桶掛有n頁的span非空, 將其分裂成一個k頁的span和一個n-k頁的span.

但是如果遍歷到了最后一個桶, 依然沒有發(fā)現(xiàn)非空的span, 此時需要向系統(tǒng)堆申請一個大頁的span, 我們這里申請的是128頁的span, 直接使用我們封裝的 SystemAlloc 函數(shù)即可.

// 獲取一個k頁的span
Span* PageCache::NewSpan(size_t k)
{assert(k > 0 && k < NPAGES);// 判斷k號桶是否有非空的spanif (!_spanLists[k].Empty()){_spanLists[k].PopFront();}// 遍歷k+1到最后一個桶for (size_t i = k + 1; i < NPAGES; i++){if (!_spanLists[i].Empty()){Span* kSpan = new Span;Span* nSpan = _spanLists[i].PopFront();// 將nSpan頭部的k頁切下來kSpan->_pageId = nSpan->_pageId;kSpan->_n = k;nSpan->_pageId += k;nSpan->_n -= k;// 將nSpan剩下的掛到其映射的位置_spanLists[nSpan->_n].PushFront(nSpan);return kSpan;}}// 走到這說明需要向系統(tǒng)堆申請128頁的spanSpan* bigSpan = new Span;void* ptr = SystemAlloc(NPAGES - 1);bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;bigSpan->_n = NPAGES - 1;_spanLists[bigSpan->_n].PushFront(bigSpan);// 盡量避免代碼重復(fù), 遞歸調(diào)用自己return NewSpan(k);
}