項(xiàng)目簡(jiǎn)介

這個(gè)項(xiàng)目是實(shí)現(xiàn)了一個(gè)高效的并發(fā)內(nèi)存池。它的原型的goggle的一個(gè)開源項(xiàng)目tcmalloc，即thread-cache malloc（線程緩存的malloc），實(shí)現(xiàn)了高效多線程的內(nèi)存管理，可實(shí)現(xiàn)對(duì)系統(tǒng)提供的內(nèi)存分配函數(shù)malloc和free的替代。

內(nèi)存碎片

內(nèi)存碎片分為外碎片和內(nèi)碎片。

外碎片是指，未被分配給進(jìn)程的內(nèi)存塊，由于其太小了，無法滿足進(jìn)程申請(qǐng)的內(nèi)存大小。

內(nèi)碎片是指，內(nèi)存塊已經(jīng)分配給了進(jìn)程，但是由于各種原因（比如結(jié)構(gòu)體的內(nèi)存對(duì)齊），不會(huì)使用內(nèi)存塊的某一部分，一直處于空閑狀態(tài)，直至釋放。

定長(zhǎng)內(nèi)存池設(shè)計(jì)

所謂定長(zhǎng)，就是每次申請(qǐng)出來的內(nèi)存大小都是一樣的。

申請(qǐng)過程：首先在堆上申請(qǐng)一大塊內(nèi)存，按對(duì)象的大小從大塊內(nèi)存中截取對(duì)應(yīng)的內(nèi)存供進(jìn)程使用。

釋放過程：內(nèi)存池中維護(hù)一個(gè)freelist_的鏈表，用來回收釋放掉的內(nèi)存，采用頭插的方式掛在freelist_后邊。在申請(qǐng)內(nèi)存過程中，優(yōu)先查看freelist_后邊是否回收的內(nèi)存塊，優(yōu)先使用freelist_中的內(nèi)存供進(jìn)程申請(qǐng)用。達(dá)到重復(fù)利用的目的。

項(xiàng)目框架

該內(nèi)存池由3部分組成

1. thread cache：線程緩存是每個(gè)線程獨(dú)有的，用于小于256KB的內(nèi)存的分配，線程從這里申請(qǐng)內(nèi) 存不需要加鎖，每個(gè)線程獨(dú)享一個(gè)cache，這也就是這個(gè)并發(fā)線程池高效的地方。

2. central cache：中心緩存是所有線程所共享，thread cache是按需從central cache中獲取的對(duì) 象。central cache合適的時(shí)機(jī)回收thread cache中的對(duì)象，避免一個(gè)線程占用了太多的內(nèi)存，而其他線程的內(nèi)存吃緊，達(dá)到內(nèi)存分配在多個(gè)線程中更均衡的按需調(diào)度的目的。central cache是存在競(jìng)爭(zhēng)的，所以從這里取內(nèi)存對(duì)象是需要加鎖，首先這里用的是桶鎖，其次只有thread cache的沒有內(nèi)存對(duì)象時(shí)才會(huì)找central cache，所以這里競(jìng)爭(zhēng)不會(huì)很激烈。

3. page cache：頁緩存是在central cache緩存上面的一層緩存，存儲(chǔ)的內(nèi)存是以頁為單位存儲(chǔ)及分配的，central cache沒有內(nèi)存對(duì)象時(shí)，從page cache分配出一定數(shù)量的page，并切割成定長(zhǎng)大小的小塊內(nèi)存，分配給central cache。當(dāng)一個(gè)span的幾個(gè)跨度頁的對(duì)象都回收以后，page cache 會(huì)回收central cache滿足條件的span對(duì)象，并且合并相鄰的頁，組成更大的頁，緩解內(nèi)存碎片的問題。

內(nèi)存池實(shí)現(xiàn)邏輯

threadcache

threadcache設(shè)計(jì)稱為一個(gè)hash結(jié)構(gòu)，申請(qǐng)的大小在其區(qū)間按各自的對(duì)齊數(shù)均勻劃分桶。

其中hash的對(duì)其規(guī)則如下：

1B<= bites<128B，對(duì)齊數(shù)8B，其劃分的桶就有128/8=16個(gè)，即8、16 ······ 128

8KB<=bites<64KB，對(duì)齊數(shù)1KB，其劃分的桶就有(64 - 8)/1=56個(gè)，即9、10 ······ 64

64K<=bites<256KB，對(duì)齊數(shù)8K，其互粉的桶就有(256-64)/8=24個(gè)，即72、80 ······ 256

ps：這里的排列時(shí)不同的桶下應(yīng)掛的小內(nèi)存的大小，并不是hash桶的下標(biāo)。其下標(biāo)是按其排列順序由低到高，由0開始的。

關(guān)于內(nèi)碎片浪費(fèi)的計(jì)算：

比如申請(qǐng)的大小為為129B，就會(huì)按16B對(duì)齊，實(shí)際申請(qǐng)128B+16B=144B，就會(huì)多出15B的內(nèi)碎片，內(nèi)存浪費(fèi)率就是15B/144B=0.104。

再比如申請(qǐng)的大小為1025B，就會(huì)按128B對(duì)齊，實(shí)際申請(qǐng)1204+128=1332B，多出127B的內(nèi)碎片，內(nèi)存浪費(fèi)率就是127B/1332B=0.095。

對(duì)上邊內(nèi)存規(guī)則有了一定認(rèn)識(shí)之后，對(duì)下邊threadcache的結(jié)構(gòu)才會(huì)有更深刻的理解。

TLS（Thread Local Storage）線程本地存儲(chǔ)技術(shù)：普通的全局變量在多線程中是貢獻(xiàn)的，一個(gè)線程對(duì)其進(jìn)行了修改，所有線程都能看見這個(gè)修改，而線程私有的全局變量與普通全局變量不同，線程私有的全局變量是線程的私有財(cái)產(chǎn)，每個(gè)線程都有自己的一份副本，某個(gè)線程對(duì)其所做的修改只會(huì)影響到自己的副本，并不會(huì)修改其他線程的副本。

申請(qǐng)內(nèi)存

1、每個(gè)線程通過TLS無鎖獲取自己獨(dú)屬的ThreadCache對(duì)象

2、如果ThreadCache中對(duì)應(yīng)hash桶下邊的freelist_結(jié)構(gòu)不為空，從中取出內(nèi)存供進(jìn)程使用

3、如果ThreadCache中對(duì)應(yīng)hash桶下邊的freelist_結(jié)構(gòu)為空，向CentralCache中申請(qǐng)內(nèi)存。

? ? ? ? ps：向CentralCache中申請(qǐng)內(nèi)存過程中，使用類似TCP擁塞控制中的滿開始算法。以達(dá)到申請(qǐng)內(nèi)存的多少的合理性（即并不是單個(gè)單個(gè)內(nèi)存申請(qǐng)，而是批量申請(qǐng)）。

釋放內(nèi)存

1、將不用的內(nèi)存，通過內(nèi)存大小，計(jì)算出其在ThreadCache中對(duì)應(yīng)桶的位置，將其插入進(jìn)去。

2、當(dāng)ThreadCache中某個(gè)桶中掛的鏈表過長(zhǎng)的時(shí)候，即鏈表長(zhǎng)度大于一次批量申請(qǐng)的內(nèi)存時(shí)，就將ThreadCache中對(duì)應(yīng)桶中的內(nèi)存回收給CentralCache.

centralcache

centralcache設(shè)計(jì)也是一個(gè)hash結(jié)構(gòu)，也是使用和threadcache的對(duì)齊規(guī)則。不同的是centralcache的每個(gè)hash桶掛著的是span對(duì)象，是一個(gè)雙向鏈表。每個(gè)span中又切分了多個(gè)對(duì)應(yīng)其對(duì)齊數(shù)的小內(nèi)存對(duì)象，是一個(gè)單鏈表結(jié)構(gòu)。

其次，從整個(gè)項(xiàng)目框架上看，多個(gè)ThreadCache內(nèi)存不足或者需要釋放內(nèi)存的時(shí)候，都需要涉及到centralcache，因此centralcache最好設(shè)計(jì)稱為單例模式，供多個(gè)threadcache訪問。

申請(qǐng)內(nèi)存

1、ThreadCache向CentralCache申請(qǐng)內(nèi)存，首先獲得從CentrlCache對(duì)應(yīng)位置的hash桶中獲得一個(gè)Span（此時(shí)需要加桶鎖），在該Span中拿出ThreadCache申請(qǐng)的內(nèi)存數(shù)（盡力而為）。

2、如果CentrlCache對(duì)應(yīng)位置沒有Span，則向PageCache中申請(qǐng)內(nèi)存。將向PageCache中剛申請(qǐng)的內(nèi)存進(jìn)行切分成freelist_。

釋放內(nèi)存

1、回收ThreadCache中的freelist_鏈表過長(zhǎng)的內(nèi)存，首先得找到CentralCache中對(duì)應(yīng)的hash位置

2、其次CentralCache得找到這個(gè)個(gè)回收回來得freelist_鏈表隸屬于CentralCache對(duì)應(yīng)hash位置下的哪一個(gè)span。

這里找到對(duì)應(yīng)的span，使用了一個(gè)哈希結(jié)構(gòu)，unordered_map<PAGE_ID, Span*>，在PageCache向CentralCache中分配內(nèi)存的時(shí)候，就建立好了對(duì)應(yīng)的映射關(guān)系了。

關(guān)于PAGE_ID的計(jì)算是這樣的，(PAGE_ID)ptr >> PAGE_SHIFT，即將內(nèi)存地址右移PAGE_SHIFT位。這樣每一個(gè)內(nèi)存地址都能找到自己的PAGE_ID。再通過映射關(guān)系找到自己所屬的Span。

3、向?qū)?yīng)hash位置下的對(duì)應(yīng)span中依次掛入回收的鏈表，并且useCount對(duì)應(yīng)減少。

4、當(dāng)useCount減至0的時(shí)候，標(biāo)志著該span中的所有小塊內(nèi)存都被回收回來了。就應(yīng)該向PageCache中歸還該span的內(nèi)存了。

pagecache

pagecache的設(shè)計(jì)也是一個(gè)hash結(jié)構(gòu)，采用的是直接定址法法映射。其每個(gè)hash桶下掛著的是以頁為單位的對(duì)應(yīng)其范圍大小的span內(nèi)存對(duì)象，是個(gè)雙向鏈表結(jié)構(gòu)。

這里的PageCache也設(shè)計(jì)稱為單例模式。

申請(qǐng)內(nèi)存

1、首先向滿足CentralCache申請(qǐng)對(duì)應(yīng)的桶中查看時(shí)候有span。有則交付一個(gè)span。

2、滿足CentralCache申請(qǐng)對(duì)應(yīng)的桶中沒有span，就向后續(xù)桶中遍歷查找存在內(nèi)存的桶。

3、后續(xù)桶中的span必定比滿足CentralCache申請(qǐng)對(duì)應(yīng)的桶中的span大，需要在后續(xù)桶中的span切分滿足CentralCache申請(qǐng)對(duì)應(yīng)的桶中的大小，span剩下的內(nèi)存則，按剩余內(nèi)存大小映射插入到對(duì)應(yīng)的hash桶中。

釋放內(nèi)存

1、回收來自CentralCache返還的span，進(jìn)行合并頁，緩解內(nèi)碎片的問題。

2、向前合并，（1）前邊沒有頁號(hào)了（2）前邊的頁號(hào)正在使用（3）合并后的頁數(shù)超過128頁，無法管理。則不合并。

3、向后合并，（1）前邊沒有頁號(hào)了（2）前邊的頁號(hào)正在使用（3）合并后的頁數(shù)超過128頁，無法管理。則不合并。

內(nèi)存池優(yōu)化邏輯

大塊內(nèi)存的申請(qǐng)和釋放

我們這里內(nèi)存池的單個(gè)線程能申請(qǐng)的最大內(nèi)存就是256KB，當(dāng)線程申請(qǐng)的內(nèi)存大于256KB的時(shí)候，便能是為是大塊內(nèi)存。

我們?cè)O(shè)計(jì)PageCache的時(shí)候，一頁的大小定為的8K，當(dāng)申請(qǐng)256KB的時(shí)候，就需要256KB/8KB=32個(gè)span。因此將Page Cache的哈希桶個(gè)數(shù)多弄幾個(gè)，比如32*4=128個(gè)，即一個(gè)128頁的span可以滿足四個(gè)線程去申請(qǐng)256KB大小的內(nèi)存。

當(dāng)申請(qǐng)大塊內(nèi)存的時(shí)候，我們直接去向PageCache中去申請(qǐng)。

在PageCache中，當(dāng)申請(qǐng)超過128頁的大內(nèi)存的時(shí)候，就直接向堆申請(qǐng)。

釋放的過程相反即可。

釋放大塊內(nèi)存的時(shí)候，直接向PageCache中歸還。

在PageCache中，歸還超過128頁的內(nèi)存時(shí)，直接歸還給堆。

替代系統(tǒng)內(nèi)存分配函數(shù)

我們的內(nèi)存池是能替代系統(tǒng)提供的內(nèi)存分配函數(shù)（malloc、free）的，因此我們不能在里邊繼續(xù)使用系統(tǒng)提供的內(nèi)存分配函數(shù)。定長(zhǎng)內(nèi)存池便能達(dá)到使用內(nèi)存分配的效果。

使用基數(shù)樹優(yōu)化

基數(shù)樹，或稱壓縮前綴樹，是一種更節(jié)省空間的Trie（前綴樹）。對(duì)于基數(shù)樹的每個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)是確定的子樹的話，就和父節(jié)點(diǎn)合并。基數(shù)樹可用來構(gòu)建關(guān)聯(lián)數(shù)組。

為什么要使用基數(shù)樹優(yōu)化呢？

在PageCache向CentralCache分配內(nèi)存的時(shí)候，我們需要建立PageId和Span的映射關(guān)系，我們使用的是STL中unordered_map，其底層是使用的哈希表。關(guān)于哈希表有如下缺點(diǎn)不符我們內(nèi)存池的使用：

1、哈希表的底層必定使用了系統(tǒng)內(nèi)存分配相關(guān)函數(shù)

2、哈希表的底層使用數(shù)組實(shí)現(xiàn)的，數(shù)組大小不好確定，還涉及到擴(kuò)容的問題（擴(kuò)容就分為原地?cái)U(kuò)容和一定擴(kuò)容）。

接下來就開始介紹基數(shù)樹了！

單層基數(shù)樹

單層基數(shù)樹就如同hash的直接定址法一樣，其中的模板參數(shù)表示的是存儲(chǔ)頁號(hào)的位數(shù)。在32位環(huán)境下是32-PAGE_SHIFT，64位環(huán)境下是64-PAGE_SHIFT。我們的PAGE_SHIFT是2^13，也就是說BITES在32位環(huán)境下的值就是2^19位。占用的內(nèi)存就是2^19*4=2^21=2M。

比如頁號(hào)為多少，就在對(duì)應(yīng)的void**的數(shù)組中找對(duì)應(yīng)的位置，其位置存儲(chǔ)的就是它Span的信息。

雙層基數(shù)樹

上邊的雙層基數(shù)樹的模板參數(shù)含義和單層基數(shù)樹一樣，都代表存儲(chǔ)頁號(hào)需要多少位。

這里的雙層基數(shù)樹的前5位用于標(biāo)識(shí)頁號(hào)，能通過第一層對(duì)應(yīng)位置中的內(nèi)容找到第二層的數(shù)據(jù)，第二層的數(shù)組標(biāo)識(shí)著Span的屬性。32位環(huán)境下，二層基數(shù)樹需要的大小是2^19*4=2^21=2M。

項(xiàng)目反思

項(xiàng)目不足

可能存在內(nèi)存泄漏。在ThreadCache的回收邏輯里，當(dāng)哈希桶下掛的freelist_過長(zhǎng)的時(shí)候，才將freelist_向CentralCache中返還。當(dāng)freelist_掛的內(nèi)存不長(zhǎng)的時(shí)候呢？比如說就只掛了一個(gè)小的內(nèi)存對(duì)象，并不滿足過長(zhǎng)的條件，就不會(huì)向CentralCache里返還，就造成了內(nèi)存泄漏的問題。

項(xiàng)目?jī)?yōu)勢(shì)

1、ThreadCache使用了TLS技術(shù)，每個(gè)線程無鎖獲得自己獨(dú)屬的ThreadCache對(duì)象。

2、ThreadCache內(nèi)存不足時(shí)向CentralCache申請(qǐng)時(shí)，并不是需要多少申請(qǐng)多少，而是批量申請(qǐng)，也就是說在向CentralCache申請(qǐng)依次后，Thread Cache就有了一批內(nèi)存對(duì)象供本線程使用。即減少了ThreadCache向CentralCache申請(qǐng)的頻次，而CentralCache的訪問時(shí)會(huì)加鎖的，這也將使CentralCache中的桶鎖不會(huì)很激烈。

3、使用基數(shù)樹優(yōu)化，既可以代替底層使用new和delete，有可以利用基數(shù)樹可以根據(jù)一個(gè)長(zhǎng)整型（比如一個(gè)長(zhǎng)ID）快速查找到其對(duì)應(yīng)的對(duì)象指針，比hash映射來的簡(jiǎn)單和節(jié)省空間。