C++實現一個高併發的記憶體池(通俗易懂）
一，什麼是記憶體池
1。1 池化技術
池化技術是將程式中需要經常使用的核心資源先申請出 來，放到一個池，由程式源自己管理，這樣可以提高資源的使用效率，它可以避免核心資源申請和釋放帶來的開銷，也可以保證本程式佔有的資源數量。 經常使用的池化技術包括記憶體池、執行緒池和連線池等。
1。2 關於記憶體池
記憶體池（Memory Pool）是一種動態記憶體分配與管理技術。 通常情況下，我們可以直接使用 new、 delete、malloc、free 等API申請分配和釋放記憶體。這樣導致的後果是：當程式長時間執行時，由於所申請記憶體塊的大小不定，頻繁使用時會造成大量的記憶體碎片從而降低程式和作業系統的效能。記憶體池則是在真正 使用記憶體之前，先申請分配一大塊記憶體（記憶體池）留作備用，當程式設計師申請記憶體時，從池中取出一塊記憶體，當程式設計師釋放記憶體時，將釋放的記憶體再放入池內，再次申請池可以 再取出來使用，並儘量與周邊的空閒記憶體塊合併。若記憶體池不夠時，則自動擴大記憶體池，從作業系統中申請更大的記憶體池。
二，記憶體碎片問題
造成堆利用率很低的一個主要原因就是記憶體碎片化。如果有未使用的儲存器，但是這塊儲存器不能用來滿足分配的請求，這時候就會產生記憶體碎片化問題。記憶體碎片化分為內部碎片和外部碎片。
2。1 內碎片
內部碎片是指一個已分配的塊比有效載荷大時發生的。（假設以前分配了10個大小的位元組，現在只用了5個位元組，則剩下的5個位元組就會內碎片）。內部碎片的大小就是已經分配的塊的大小和他們的有效載荷之差的和。因此內部碎片取決於以前請求記憶體的模式和分配器實現（對齊的規則）的模式。
2。2 外碎片
外部碎片就是當空閒的儲存器的總和足夠滿足一個分配請求，但是沒有一個單獨的空閒塊足夠大可以處理這個請求。外部碎片取決於以前的請求記憶體的模式和分配器的實現模式，還取決於將來的記憶體請求模式。所以外部碎片難以量化。
三，為什麼要使用記憶體池
解決內碎片問題
由於向記憶體申請的記憶體塊都是比較大的，所以能夠降低外碎片問題
一次性向記憶體申請一塊大的記憶體慢慢使用，避免了頻繁的向記憶體請求記憶體操作，提高記憶體分配的效率
但是內碎片問題無法避免，只能儘可能的降低
四，三種記憶體池的演變
4。1 最簡單的記憶體分配器
一個連結串列指向空閒記憶體，分配就是遍歷找到一塊大小和它一致或者是比它大一些的，取出一塊來，然後在修改連結串列，將剩餘的空間掛回到連結串列中。釋放就是放回到連結串列裡面。注意做好標記和保護，避免二次釋放，還可以最佳化如何查詢適合大小的記憶體快的搜尋上，減少記憶體碎片，但是可以增加記憶體池的外碎片。
優點 ：實現簡單
缺點：分配時搜尋合適的記憶體塊效率低，釋放回歸記憶體後歸併比較消耗大，實際中不實用。
4。2 定長記憶體分配器
實現一個 FreeList，這個自由連結串列用於分配固定大小的記憶體塊，比如用於分配 32位元組物件的固定記憶體分配器。每個記憶體分配器裡面有兩個連結串列。OpenList 用於儲存未分配的空閒物件，CloseList用於儲存已分配的記憶體物件。所謂的分配就是從 OpenList 中取出一個物件放到 CloseList 裡並且返回給使用者， 釋放又是從 CloseList 移回到 OpenList。 分配時記憶體如果不夠，那麼就需要增長OpenList，向系統申請一個更大一點的記憶體塊，切割成相同大小的物件新增到 OpenList中。這個固定記憶體分配器回收的時候，統一把先前向系統申請的記憶體塊全部還給系統。
優點：簡單。分配和釋放的效率高，解決實際中特定場景下的問題有效。
缺點：功能單一。只能解決定長的記憶體需求，另外佔著記憶體沒有釋放。
關於記憶體池記憶體不夠的情況，應該繼續想系統去申請：
4。3 Hash對映的多種定長記憶體分配器
在定長分配器的基礎上，按照不同物件大小（8，16，32，64，128，256，512，1k…64K），構造十多個固定記憶體分配器，分配記憶體時根據要申請記憶體大小進行對齊然後查H表，決定到底由哪個分配器負責，分配後要在記憶體頭部的 header 處寫上 cookie，表示由該塊記憶體哪一個分配器分配的，這樣釋放時候你才能正確歸還。如果大於64K，則直接用系統的 malloc作為分配，如此以浪費記憶體為代價你得到了一個分配時間近似O（1）的記憶體分配器。這種記憶體池的缺點是假設某個 FreeList 如果高峰期佔用了大量記憶體即使後面不用，也無法支援到其他記憶體不夠的 FreeList，達不到分配均衡的效果。
優點： ：本質是定長記憶體池的改進，分配和釋放的效率高。可以解決一定長度記憶體分配的問題。
缺點 ：存在內碎片的問題，且將一塊大記憶體切小以後，申請大記憶體無法使用，別的FreeList掛了很多空閒的記憶體塊而分配不到，但是其他的FreeList缺不夠分配。在多執行緒併發場景下，可能會導致執行緒安全的問題，可以透過加鎖解決，但是鎖競爭激烈，申請釋放效率會降低。
這種設計和STL庫的耳機空間配置器的設計完全一樣。
五，瞭解malloc底層原理
malloc優點： 使用自由連結串列的陣列，提高分配釋放效率；減少記憶體碎片，可以合併空閒的記憶體（根據腳步）
malloc缺點： 為了維護隱式/顯示連結串列需要維護一些資訊，空間利用率不高；在多執行緒的情況下，會出現執行緒安全的問題，如果以加鎖的方式解決，會大大降低效率。
六，實現高併發的記憶體池
現在大部分的開發環境都是多核多執行緒，在申請記憶體的場景下，必然存在激烈的鎖競爭問題。要實現一個高併發的記憶體池，必須要考慮以下幾個問題：
記憶體碎片問題
效能問題
多執行緒場景下，鎖競爭問題
6。1 高併發記憶體池設計
組成：
thread cache：執行緒快取是每個執行緒獨有的，用於小於64k的記憶體的分配，執行緒從這裡申請記憶體不需要加鎖，每個執行緒獨享一個cache，這也就是這個併發執行緒池高效的地方。
Central cache：中心快取是所有執行緒所共享，thread cache是按需要從Central cache中獲取的物件。 Central cache週期性的回收thread cache中的物件，避免一個執行緒佔用了太多的記憶體，而其他執行緒的記憶體吃緊。達到記憶體分配在多個執行緒中更均衡的按需排程的目的。Central cache是存在競爭的，所以從這裡取記憶體物件是需要加鎖。
Page cache：頁快取是在Central cache快取上面的一層快取，儲存的記憶體是以頁為單位儲存及分配 的，Central cache沒有記憶體物件（Span）時，從Page cache分配出一定數量的page，並切割成定長大小的小塊記憶體，分配給Central cache。Page cache會回收Central cache滿足條件的Span（使用計數為0）物件，並且合併相鄰的頁，組成更大的頁，緩解記憶體碎片的問題。
注：怎麼實現每個執行緒都擁有自己唯一的執行緒快取呢？
為了避免加鎖帶來的效率，在Thread Cache中使用thread local storage儲存每個執行緒本地的ThreadCache的指標，這樣Thread Cache在申請釋放記憶體是不需要鎖的。因為每一個執行緒都擁有了自己唯一的一個全域性變數。
6。2 設計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
］；
// 建立了一個自由連結串列陣列
}；
關於FreeList這個類，我們只要封裝一個普通指標和連結串列的長度即可。
Thread Cache申請記憶體：
只能申請在64k範圍以內的大小的記憶體，如果大於64k，則呼叫VirtualAlloc直接向系統申請記憶體。
當記憶體申請size<=64k時在thread cache中申請記憶體，先計算size在自由連結串列中的位置，如果自由連結串列中有記憶體物件時，直接從FistList［i］中Pop然後返回物件，時間複雜度是O（1），並且沒有鎖競爭，效率極高。 當FreeList［i］中沒有物件時，則批次從Central cache中獲取一定數量的物件，剩餘的n-1個物件插入到自由連結串列並返回一 個物件。
Thread Cache釋放記憶體：
當釋放記憶體小於64k時將記憶體釋放回thread cache，先計算size在自由連結串列中的位置，然後將物件Push到 FreeList［i］
當自由連結串列的長度超過一次向中心快取分配的記憶體塊數目時，回收一部分記憶體物件到Central cache
6。3 自由連結串列大小設計（對齊規則）
// 控制內碎片浪費不要太大
//［1， 128］ 8byte對齊 freelist［0，16）
//［129， 1024］ 16byte對齊 freelist［17， 72）
//［1025， 8 * 1024］ 64byte對齊 freelist［72， 128）
//［8 * 1024 + 1， 64 * 1024］ 512byte對齊 freelist［128， 240）
// 也就是說對於自由連結串列陣列只需要開闢240個空間就可以了
// 大小類
class
ClassSize
{
public
：
// align是對齊數
static
inline
size_t
_RoundUp
（
size_t
size
，
size_t
align
）
{
// 比如size是15 < 128，對齊數align是8，那麼要進行向上取整，
// （（15 + 7） / 8） * 8就可以了
// 這個式子就是將（align - 1）加上去，這樣的話就可以進一個對齊數
// 然後再將加上去的二進位制的低三位設定為0，也就是向上取整了
// 15 + 7 = 22 ： 10110 （16 + 4 + 2）
// 7 ： 111 ~7 ： 000
// 22 & ~7 ： 10000 （16）就達到了向上取整的效果
return
（
size
+
align
-
1
）
&
~
（
align
-
1
）；
}
// 向上取整
static
inline
size_t
RoundUp
（
size_t
size
）
{
assert
（
size
<=
MAXBYTES
）；
if
（
size
<=
128
）
{
return
_RoundUp
（
size
，
8
）；
}
if
（
size
<=
8
*
128
）
{
return
_RoundUp
（
size
，
16
）；
}
if
（
size
<=
8
*
1024
）
{
return
_RoundUp
（
size
，
128
）；
}
if
（
size
<=
64
*
1024
）
{
return
_RoundUp
（
size
，
512
）；
}
else
{
return
-
1
；
}
}
//求出在該區間的第幾個
static
size_t
_Index
（
size_t
bytes
，
size_t
align_shift
）
{
//對於（1 << align_sjift）相當於求出對齊數
//給bytes加上對齊數減一也就是，讓其可以跨越到下一個自由連結串列的陣列的元素中
return
（（
bytes
+
（
1
<<
align_shift
）
-
1
）
>>
align_shift
）
-
1
；
}
//獲取自由連結串列的下標
static
inline
size_t
Index
（
size_t
bytes
）
{
//開闢的位元組數，必須小於可以開闢的最大的位元組數
assert
（
bytes
<
MAXBYTES
）；
//每個對齊區間中，有著多少條自由連結串列
static
int
group_array
［
4
］
=
{
16
，
56
，
56
，
112
}；
if
（
bytes
<=
128
）
{
return
_Index
（
bytes
，
3
）；
}
else
if
（
bytes
<=
1024
）
//（8 * 128）
{
return
_Index
（
bytes
-
128
，
4
）
+
group_array
［
0
］；
}
else
if
（
bytes
<=
4096
）
//（8 * 8 * 128）
{
return
_Index
（
bytes
-
1024
，
7
）
+
group_array
［
1
］
+
group_array
［
0
］；
}
else
if
（
bytes
<=
8
*
128
）
{
return
_Index
（
bytes
-
4096
，
9
）
+
group_array
［
2
］
+
group_array
［
1
］
+
group_array
［
0
］；
}
else
{
return
-
1
；
}
}
}；
6。4 Central Cache設計
Central cache本質是由一個雜湊對映的span物件自由雙向連結串列構成
為了保證全域性只有唯一的Central cache，這個類被可以設計成了單例模式
單例模式採用餓漢模式，避免高併發下資源的競爭
注：什麼是span?一個span是由多個頁組成的一個span物件。一頁大小是4k。
// span結構
// 對於span是為了對於thread cache還回來的記憶體進行管理
// 一個span中包含了記憶體塊
typedef
size_t
PageID
；
struct
Span
{
PageID
_pageid
=
0
；
//起始頁號（一個span包含多個頁）
size_t
_npage
=
0
；
//頁的數量
Span
*
_next
=
nullptr
；
// 維護雙向span連結串列
Span
*
_prev
=
nullptr
；
void
*
_objlist
=
nullptr
；
//物件自由連結串列
size_t
_objsize
=
0
；
//記錄該span上的記憶體塊的大小
size_t
_usecount
=
0
；
//使用計數
}；
關於spanlist，設計為一個雙向連結串列，插入刪除效率較高:
class
SpanList
{
public
：
// 雙向迴圈帶頭結點連結串列
SpanList
（）
{
_head
=
new
Span
；
_head
->
_next
=
_head
；
_head
->
_prev
=
_head
；
}
Span
*
begin
（）
{
return
_head
->
_next
；
}
Span
*
end
（）
{
return
_head
；
}
bool
Empty
（）
{
return
_head
==
_head
->
_next
；
}
void
Insert
（
Span
*
cur
，
Span
*
newspan
）
{
assert
（
cur
）；
Span
*
prev
=
cur
->
_prev
；
//prev newspan cur
prev
->
_next
=
newspan
；
newspan
->
_prev
=
prev
；
newspan
->
_next
=
cur
；
cur
->
_prev
=
newspan
；
}
void
Erase
（
Span
*
cur
）
{
assert
（
cur
！=
nullptr
&&
cur
！=
_head
）；
Span
*
prev
=
cur
->
_prev
；
Span
*
next
=
cur
->
_next
；
prev
->
_next
=
next
；
next
->
_prev
=
prev
；
}
void
PushBack
（
Span
*
cur
）
{
Insert
（
end
（），
cur
）；
}
void
PopBack
（）
{
Span
*
span
=
end
（）；
Erase
（
span
）；
}
void
PushFront
（
Span
*
cur
）
{
Insert
（
begin
（），
cur
）；
}
Span
*
PopFront
（）
{
Span
*
span
=
begin
（）；
Erase
（
span
）；
return
span
；
}
// 給每一個Spanlist桶加鎖
std
：：
mutex
_mtx
；
private
：
Span
*
_head
=
nullptr
；
}；
Central Cache申請記憶體：
當thread cache中沒有記憶體時，就會批次向Central cache申請一定數量的記憶體物件，Central cache也是一個雜湊對映的Spanlist，Spanlist中掛著span，從span中取出物件給thread cache，這個過程是需要加鎖的，可能會存在多個執行緒同時取物件，會導致執行緒安全的問題。
當Central cache中沒有非空的span時，則將空的span鏈在一起，然後向Page cache申請一個span物件， span物件中是一些以頁為單位的記憶體，將這個人span物件切成需要的記憶體大小並連結起來，最後掛到Central Cache中。
Central cache的中的每一個span都有一個use_count，分配一個物件給thread cache，就++use_count，當這個span的使用計數為0，說明這個span所有的記憶體物件都是空閒的，然後將它交給Page Cache合併成更大的頁，減少記憶體碎片。
Central Cache釋放記憶體：
當thread cache過長或者執行緒銷燬，則會將記憶體釋放回Central cache中，沒釋放一個記憶體物件，檢查該記憶體所在的span使用計數是否為空，釋放回來一個時——use_count。
當use_count減到0時則表示所有物件都回到了span，則將span釋放回Page cache，在Page cache中會對前後相鄰的空閒頁進行合併。
注：怎麼才能將Thread Cache中的記憶體物件還給他原來的span呢？
答：可以在Page Cache中維護一個頁號到span的對映，當Span Cache給Central Cache分配一個span時，將這個對映更新到map中去，在Thread Cache還給Central Cache時，可以查這個map找到對應的span。
6。5 PageCache設計
Page cache是一個以頁為單位的span自由連結串列
為了保證全域性只有唯一的Page cache，這個類可以被設計成了單例模式
本單例模式採用餓漢模式
// 採用餓漢模式，在main函式之前單例物件已經被建立
class
PageCache
{
public
：
// 獲取單例模式
static
PageCache
*
GetInstance
（）
{
return
&
_inst
；
}
// 在SpanList中獲取一個span物件，如果沒有或者申請記憶體大於128頁，則直接去系統申請
Span
*
NewSpan
（
size_t
npage
）；
Span
*
_NewSpan
（
size_t
npage
）；
// 獲取從物件到span的對映
Span
*
MapObjectToSpan
（
void
*
obj
）；
// 從CentralCache歸還span到Page，然後PageCache進行合併
void
RelaseToPageCache
（
Span
*
span
）；
private
：
// NPAGES是129，最大頁數為128，也就是下標從1開始到128分別為1頁到128頁
SpanList
_pagelist
［
NPAGES
］；
private
：
PageCache
（）
=
default
；
PageCache
（
const
PageCache
&
）
=
delete
；
PageCache
&
operator
=
（
const
PageCache
&
）
=
delete
；
static
PageCache
_inst
；
// 為了鎖住SpanList，可能會存在多個執行緒同時來PageCache申請span
std
：：
mutex
_mtx
；
std
：：
unordered_map
<
PageID
，
Span
*>
_id_span_map
；
}；
當CentralCache向PageCache申請記憶體時，PageCache先檢查對應位置有沒有span，如果沒有則向更大頁尋找一個span，如果找到則分裂成兩個。比如：申請的是4page，4page後面沒有掛span，則向後面尋找更大的span，假設在10page位置找到一個span，則將10page span分裂為一個4page span和 一個6page span。
如果找到128 page都沒有合適的span，則向系統使用mmap、brk（Linux）或者是VirtualAlloc（windows）等方式申請128page span掛在自由連結串列中，再重複1中的過程。
PageCache釋放記憶體：
如果CentralCache釋放回一個span，則依次尋找span的前後page id的span，看是否可以合併，如果能夠合併繼續向前尋找。這樣就可以將切小的記憶體合併收縮成大的span，減少記憶體碎片。但是合併的最大頁數超過128頁，則不能合併。
如果ThreadCache想直接申請大於64k的記憶體，直接去PageCache去申請，當在PageCache申請時，如果申請的記憶體大於128頁，則直接向系統申請這塊記憶體，如果小於128頁，則去SpanList去查詢。
6。6 向系統申請記憶體
Linux平臺下使用brk或sbrk向系統直接申請堆記憶體
Windows平臺下使用VirtualAlloc向系統申請堆記憶體
static
inline
void
*
SystemAlloc
（
size_t
npage
）
{
#ifdef _WIN32
// 從系統申請記憶體，一次申請128頁的記憶體，這樣的話，提高效率，一次申請夠不需要頻繁申請
void
*
ptr
=
VirtualAlloc
（
NULL
，
（
NPAGES
-
1
）
<<
PAGE_SHIFT
，
MEM_RESERVE
|
MEM_COMMIT
，
PAGE_READWRITE
）；
if
（
ptr
==
nullptr
）
{
throw
std
：：
bad_alloc
（）；
}
return
ptr
；
#else
#endif
//_WIN32
}
static
inline
void
SystemFree
（
void
*
ptr
）
{
#ifdef _WIN32
VirtualFree
（
ptr
，
0
，
MEM_RELEASE
）；
if
（
ptr
==
nullptr
）
{
throw
std
：：
bad_alloc
（）；
}
#else
#endif
//_WIN32
}
七，專案不足及擴充套件
本專案沒有完全脫離malloc和free，需要使用new和delete去建立span來維護從系統申請來的堆記憶體
解決方案：在專案中增加一個定長的ObjectPool的物件池，物件池的記憶體直接使用brk、VirarulAlloc等向系統申請，new Span替換成物件池申請記憶體。這樣就完全脫離的malloc，就可以替換掉malloc
平臺相容問題：linux系統下面，需要將VirtualAlloc替換為brk。
我們每次去申請記憶體的時候，都是使用new和delete，怎麼實現才能每次申請記憶體的時候使用我們自己實現的記憶體分配器呢？
解決方案： Linux系統下可以使用了weak alias，相當於替換別名。Windows下可以使用hook鉤子技術（不太懂）。
