為什麼需要記憶體池？
1.效率問題：如果我們直接向系統申請記憶體，當我們需要頻繁的申請釋放記憶體時，就需要頻繁的與系統層産生互動，多次切換使用者态和核心态，而使用者态和核心态之間的切換的消耗是非常大的，是以申請記憶體的消耗就會很大，程式效率也就随之降低了。
2.記憶體碎片問題：如果我們頻繁的申請和釋放小塊的記憶體，系統的記憶體就會是以被碎片化，雖然總的記憶體被占用并不多，但是卻沒有了連續的大塊記憶體，這個時候如果我們需要使用大記憶體的空間時，就無法申請了。
實作一個高并發的記憶體
現在大部分的開發環境都是多核多線程，在申請記憶體的場景下，必然存在激烈的鎖競争問題。要實作一個高并發的記憶體池，必須要考慮以下幾個問題：
- 記憶體碎片問題
- 性能問題
- 多線程場景下，鎖競争問題
高并發記憶體池設計
主要由三部分組成：
- thread cache：
線程緩存
- Central cache：
中心緩存
- Page cache：
頁緩存
**怎麼實作每個線程都擁有自己唯一的線程緩存？**⭐⭐⭐
為了避免加鎖帶來的效率，在Thread Cache中使用
thread local storage
TLS儲存每個線程本地的
ThreadCache
的指針，這樣
Thread Cache
在申請釋放記憶體時是不需要鎖的，因為每一個線程都擁有了自己唯一的全局變量。
第一層：ThreadCache類
class ThreadCache
{
public:
void* Allocate(size_t size);//配置設定記憶體
void Deallocate(void* ptr, size_t size);//釋放記憶體
//從中心緩存中擷取記憶體對象
void* FetchFromCentralCache(size_t index, size_t size);
//當自由連結清單中的對象超過一次配置設定給threadcache的數量，則開始回收
void ListTooLong(FreeList* freelist, size_t byte);
private:
FreeList _freelist[NLISTS];// 建立了一個自由連結清單數組
};
從ThreadCache申請記憶體：
當記憶體申請size<=64時2在ThreadCache中申請，計算size在自由連結清單中的位置，如果自由連結清單中有記憶體對象直接從FreeList[i]中pop一下對象，時間複雜度時O(1)，且沒有鎖競争；當Freelist[i]中沒有對象時則批量從CentralCache中擷取一定數量的對象，插入到自由連結清單并傳回一個對象（剩餘的n-1個對象插入到自由連結清單并傳回一 個對象）
向ThreadCache釋放記憶體：
當釋放記憶體小于64k時将記憶體釋放回Thread Cache， 計算size在自由連結清單中的位置，将對象Push到FreeList[i]； 當連結清單的長度過長， 也就是超過一次最大限制數目時則回收一部分記憶體對象到Central Cache。
第二層：Central Cache（中心緩存
中心緩存要實作為單例模式，保證全局隻有一份執行個體
-
.central cache是記憶體池中的第二層緩存， 這一層緩存主要解決的問題就是記憶體配置設定不均的問題。
在設計thread cache時，我們利用TLS讓每一個線程都獨享了thread cache， 但是這樣雖然解決另外記憶體碎片的問題??? 也導緻了另一個問題，那就是記憶體資源配置設定不均衡的問題。當一個線程大量的開辟記憶體再釋放的時候，這個線程中的thread cache勢必會儲存着大量的空閑記憶體資源，而這些資源是無法被其他線程所使用的，當其他的線程需要使用記憶體資源時，就可能沒有更多的記憶體資源可以使用，這也就導緻了其它線程的饑餓問題。為了解決這個問題，就有了central cache的設計。
- central cache的主要功能：周期性的回收thread cache中的記憶體資源，避免一個或多個線程占用大量記憶體資源，而其它線程記憶體資源不足的問題。讓記憶體資源的配置設定在多個線程中更均衡。
-
Central Cache是線程共享的，就是存在競争的，是以在在這裡取記憶體對象的時候是需要加鎖的，但是鎖的力度可以控制得很小。為了保證全局隻有唯一的Central Cache，這個類被可以設計成了單例模式
單例模式采用餓漢模式，避免高并發下資源的競争
- Central Cache起着承上啟下的作用：對下,它既可以将記憶體對象配置設定給Thread Cache來的每個線程，又可以将線程歸還回來的記憶體進行管理。 對上 它要把自身已經滿了的記憶體塊上交給頁緩存 當自己有需要的時候，得向頁緩存申請
-
.Central Cache本質是由一個哈希映射的Span對象自由雙向連結清單構成。一個span對象大小是恒定的4K大小，一個span是由多個頁組成的(32位下4K 64位下8K ) 但是中心緩存數組每個元素指定了單個span劃分成記憶體塊的大小 (比如第一個8bytes 第二個16bytes等等),故他們能挂載的記憶體塊數不一樣
簡言之：當thread cache中沒有記憶體時，就會批量向Central cache申請一定數量的記憶體對象，Central cache也是一個哈希映射的Spanlist，Spanlist中挂着span，從span中取出對象給thread cache。比如線程申請一個16bytes的記憶體，但是此時thread cache 中16bytes往上的都沒了 ,這個時候向cantral申請，central cache就到16bytes的地方拿下一個span 給thread cache
但是，當向Central Cache中申請發現16bytes往後的span節點全空了時，則将空的span鍊在一起，然後向Page Cache申請若幹以頁為機關的span對象，比如一個3頁的span對象，然後把這個3頁的span對象切成3個一頁的span對象，放在central cache中16bytes位置， 再将這三個一頁的span對象切成需要的記憶體塊大小，這裡就是16bytes，并連結起來，挂到span中 了解實作一個高并發的記憶體池——TLS Memmory Pool -
向central cache中釋放記憶體：
當Thread Cache過長或者線程銷毀，則會将記憶體釋放回Central Cache中，比如Thread cache中16bytes部分連結清單數目已經超出最大限制了，則會把後面再多出來的記憶體塊放到central cache的16bytes部分的他所歸屬的那個span對象上，此時那個span對象的usecount就減一位。當_usecount減到0時則表示所有對象都回到了span，則将Span釋放回Page Cache，Page Cache中會對前後相鄰的空閑頁進行合并。
了解實作一個高并發的記憶體池——TLS Memmory Pool
注意：由span對象劃分出去的記憶體塊和這個span對象是有歸屬關系的，是以由thread cache歸還釋放某個記憶體(比如16bytes)應該歸還到central cache的16bytes部分的他所歸屬的那個span對象上
那麼， 怎麼才能将Thread Cache中的記憶體對象還給它原來的span呢？
答：可以在Page Cache中維護一個頁号到span的映射。當Page Cache給Central Cache配置設定一個span時，将這個映射更新到unordered_map中去，這樣的話在central cache中的span對象下的記憶體塊都是屬于某個頁的 也就有他的頁号,，同一個span切出來的記憶體塊PageID都和span的PageID相同，這樣就能很好的找出某個記憶體塊屬于哪一個span了。
//設計成單例模式
class CentralCache
{
public:
static CentralCache* Getinstence()
{
return &_inst;
}
//從page cache擷取一個span
Span* GetOneSpan(SpanList& spanlist, size_t byte_size);
//從中心緩存擷取一定數量的對象給threa cache
size_t FetchRangeObj(void*& start, void*& end, size_t n, size_t byte_size);
//将一定數量的對象釋放給span跨度
void ReleaseListToSpans(void* start, size_t size);
private:
SpanList _spanlist[NLISTS];
private:
CentralCache(){}//聲明不實作，防止預設構造，自己建立
CentralCache(CentralCache&) = delete;
static CentralCache _inst;
};
第三層：Page Cache 頁緩存
Page cache是一個以頁為機關的span自由連結清單；為了保證全局隻有唯一的Page cache，這個類可以被設計成了單例模式，本單例模式采用餓漢模式
-
page cache的主要功能就是回收central cache中空閑的span，并且對空閑的span進行合并，合并成更大的span，當需要更大記憶體時，就不需要擔心因為記憶體被切小而無法使用大記憶體的情況了，緩解了記憶體碎片的問題。而當central cache中沒有可用的span對象時，page cache也會将大的記憶體切成需要大小的記憶體對象配置設定給central cache。
page cache中的記憶體是以頁為機關儲存和配置設定的。
- 存儲的是以頁為機關存儲及配置設定的(中心緩存數組每個元素表示連結清單中span的頁數)，中心緩存沒有span時(所有的span連結清單都空了)，從頁緩存配置設定出一定數量的頁，并切割成定長大小的小塊記憶體(在中心緩存中對應的位元組數 )，配置設定給Central Cache。Page Cache會回收Central Cache滿足條件的Span(使用計數為0，即span結點滿足一頁)對象，并且合并相鄰的頁(根據頁ID相鄰)，組成更大的頁，緩解記憶體碎片的問題。
- 當thread cache向Central Cache中申請,發現Central Cache16bytes往後的span結點全空了時，則将空的span鍊在一起，然後向Page Cache申請若幹以頁為機關的span對象，比如一個3頁的span對象：Page Cache先檢查3頁的那個位置有沒有span，如果沒有則向更大頁尋找一個span，如果找到則分裂成兩個。比如：申請的是3page，3page後面沒有挂span，則向後面尋找更大的span，假設在10page位置找到一個span，則将10page span分裂為一個3page span和一個7page span。如果找到128 page都沒有合适的span，則向系統使用mmap、brk或者是VirtualAlloc等方式申請128page span挂在自由連結清單中，再重複2中的過程，然後把這個3頁的span對象切成3個一頁的span對象 放在central cache中的16bytes位置可以有三個結點,再把這三個一頁的span對象切成需要的記憶體塊大小 這裡就是16bytes ，并連結起來，挂到span中
-
向page cache中釋放記憶體
當Thread Cache過長或者線程銷毀，則會将記憶體釋放回Central Cache中的，
比如Thread cache中16bytes部分連結清單數目已經超出最大限制了 則會把後面再多出來的記憶體塊放到central cache的16bytes部分的他所歸屬的那個span對象上.
此時那個span對象的usecount就減一位
當_usecount減到0時則表示所有對象都回到了span，則将Span釋放回Page Cache，Page Cache中會依次尋找span的前後相鄰pageid的span，看是否可以合并，如果合并繼續向前尋找。這樣就可以将切小的記憶體合并收縮成大的span，減少記憶體碎片。
- page cache中最重要的就是合并，在span結構中，有_pageid（頁号）和_pagequantity（頁的數量)兩個成員變量，通過這兩個成員變量，同時再利用unordered_map建立每一個頁号到對應span的映射，就可以通過頁号找到對應span進行合并了。
- 那麼頁号又是如何來的，當我們通過VirtualAlloc（Windows環境下是VirtualAlloc，Linux下使用brk或者mmap）直接向系統申請記憶體時，都是以頁為機關，而在32位機器下，一頁就是4k，是以從0開始每一頁的起始位址都是4k的整數倍，那麼隻需要将申請到的記憶體位址左移12位就可以得到相應的頁号了，而通過頁号也可以計算每一頁的起始位址，隻需要将位址右移12位即可。？？？
class PageCache
{
public:
static PageCache* GetInstence()
{
return &_inst;
}
Span* AllocBigPageObj(size_t size);
void FreeBigPageObj(void* ptr, Span* span);
Span* _NewSpan(size_t n);
Span* NewSpan(size_t n);//擷取的是以頁為機關
//擷取從對象到span的映射
Span* MapObjectToSpan(void* obj);
//釋放空間span回到PageCache，并合并相鄰的span
void ReleaseSpanToPageCache(Span* span);
private:
SpanList _spanlist[NPAGES];
//std::map<PageID, Span*> _idspanmap;
std::unordered_map<PageID, Span*> _idspanmap;
std::mutex _mutex;
private:
PageCache(){}
PageCache(const PageCache&) = delete;
static PageCache _inst;
};