引子

在某些工作負(fù)載中，隨著時(shí)間的推移，內(nèi)存的使用會(huì)逐漸增長(zhǎng)，直到 OOM。后面發(fā)現(xiàn)是內(nèi)存碎片問題，而將系統(tǒng)默認(rèn)的內(nèi)存分配器（glibc malloc[1]）換成 jemalloc[2] ，能有效控制內(nèi)存的增長(zhǎng)上界。

為了解其背后原理，便找來 jemalloc 最初的論文：A Scalable Concurrent malloc(3) Implementation for FreeBSD[3] 來一探究竟。當(dāng)然，相比 2006 年論文發(fā)表時(shí)，當(dāng)前的 jemalloc 可能已經(jīng)發(fā)生了很大改變，因此本文只對(duì)當(dāng)時(shí)論文內(nèi)容負(fù)責(zé)。更多 jemalloc 機(jī)制，大家可以去其 github 倉(cāng)庫(kù)[4]查看文檔和源碼。

背景

在探討論文的主要思路之前，我們先簡(jiǎn)單回顧下內(nèi)存分配器（memory allocator）的作用和邊界。簡(jiǎn)言之：

1. 對(duì)下，向操作系統(tǒng)申請(qǐng)大塊內(nèi)存（使用 sbrk、mmap 等系統(tǒng)調(diào)用）
2. 對(duì)上，處理應(yīng)用層的各種尺寸的內(nèi)存申請(qǐng)請(qǐng)求（malloc(size)），并在應(yīng)用層“表示”不用（free）后進(jìn)行釋放

往小了說，分配器的功能非常簡(jiǎn)單：分配和釋放（malloc 和 free）。想象中，實(shí)現(xiàn)也應(yīng)該很簡(jiǎn)單，只需利用一個(gè)表來記錄所有已使用內(nèi)存和未分配內(nèi)存（ a bit of bookkeeping），然后：

1. malloc 請(qǐng)求來了，先去空閑表中找，不夠的話就問操作系統(tǒng)要
2. free 請(qǐng)求來了，還回空閑表中，如果空的多了，就還給操作系統(tǒng)

但為了實(shí)現(xiàn)內(nèi)存的高效分配和回收、控制內(nèi)存的利用率，其間的學(xué)問就大了去了，CPU 緩存、 RAM 特性和虛擬內(nèi)存都會(huì)對(duì)其造成影響。其中最核心的點(diǎn)，就是如何進(jìn)行內(nèi)存組織排布，以便在用戶高并發(fā)、多尺寸、不定時(shí)的申請(qǐng)和釋放后，仍然能保證較低的調(diào)用延遲和較高的使用率。當(dāng)然，對(duì)于本論文來說，還要加上一條：越多的核數(shù)能夠支持越高的并發(fā)，謂之可擴(kuò)展（scale）。

需要說明的是，不要將本文的內(nèi)存分配器和各種具有自動(dòng) GC 功能的編程語(yǔ)言運(yùn)行時(shí)（比如 Java 的 JVM、Golang 的 Runtime）所混淆。后者是在 malloc/free 的基礎(chǔ)上，往上繼續(xù)封裝了一層，通過對(duì)象間的引用關(guān)系來追蹤每個(gè)對(duì)象的生命周期，以自動(dòng)地回收空間。

可以這么理解，C++/C 等編程語(yǔ)言要用戶自己通過 malloc/free 來管理內(nèi)存；而使用 Java/Golang/Python，用戶無腦新建對(duì)象就可以了，什么時(shí)候回收是語(yǔ)言“運(yùn)行時(shí)”的工作。而我們本文只討論前者。

但從另外角度來看，存儲(chǔ)引擎中也實(shí)現(xiàn)了類似的功能。因?yàn)榇鎯?chǔ)引擎本質(zhì)上也是要面對(duì)用戶 put/delete 的的請(qǐng)求，來進(jìn)行存儲(chǔ)的的分配和釋放。只不過這里的存儲(chǔ)，就不局限于內(nèi)存（存儲(chǔ)引擎多是 disk-based）。但其主要思想非常相似，比如使用空閑列表（free list）對(duì)可分配內(nèi)存進(jìn)行追蹤。

主要思想

從論文標(biāo)題可以看出，jemalloc 在提出時(shí)，主要為了解決在多核時(shí)代下內(nèi)存分配器性能隨核數(shù)而 scale 問題，但其實(shí)論文花了相當(dāng)多的篇幅來闡釋如何進(jìn)行內(nèi)存排布來解決碎片問題。下面，我們就圍繞這兩個(gè)方向來大致窺探下其原理。

多核并發(fā)

在多核時(shí)代進(jìn)行內(nèi)存分配時(shí)，主要面對(duì)的問題有：

1. 搶鎖競(jìng)爭(zhēng)
2. 緩存震蕩

為了保證全局?jǐn)?shù)據(jù)結(jié)構(gòu)的一致性的問題，就必須引入某種手段（比如鎖）來進(jìn)行協(xié)調(diào)。但如果多線程搶鎖過于頻繁，就會(huì)造成嚴(yán)重的性能下降。為了降低對(duì)鎖的競(jìng)爭(zhēng)，自然的想法就是，對(duì)主要的全局?jǐn)?shù)據(jù)結(jié)構(gòu)粒度拆分（比如 Java 的 ConcurrentHashMap 就是將哈希桶分成了多個(gè)段進(jìn)行上鎖）。

分配器中最重要的數(shù)據(jù)結(jié)構(gòu)就是空閑列表，我們可以將空閑列表拆分成多個(gè)，每個(gè)空閑列表使用單獨(dú)的鎖。這樣可以緩解多線程的競(jìng)爭(zhēng)問題，但卻解決不了多核架構(gòu)的另外一個(gè)問題——緩存震蕩（cache sloshing）。

在多核架構(gòu)中，如果兩個(gè)線程沒有正確的共享緩存。比如線程 A 和線程 B 共享了一個(gè)緩存行（Cache Line），且兩線程分別會(huì)反復(fù)修改緩存行的不同部分。如果 A 和 B 調(diào)度到了不同的 CPU 上，就會(huì)造成 Cache Line 所有權(quán)的反復(fù)競(jìng)爭(zhēng)。

cache sloshing

為了解決此問題，jemalloc 會(huì)將所管理的內(nèi)存分為幾個(gè)（通常是 CPU 核數(shù)的四倍）區(qū)域（ 稱為 Arena，“競(jìng)技場(chǎng)”）。在不同線程的 client 到來時(shí)，會(huì)均勻地（round robin）綁定到某個(gè) Arena，之后該 client 所有內(nèi)存的申請(qǐng)和釋放都發(fā)生在該 Arena。論文還提及了 Larson and Krishnan (1998) 之前使用 hash 的方法進(jìn)行綁定，但由于哈希過程是偽隨機(jī)的（pseudo-random），因此很難保證線程到 Arena 的均勻。

下面我們來討論如何在每個(gè) Arena 內(nèi)排布內(nèi)存來應(yīng)對(duì)用戶對(duì)象的申請(qǐng)和釋放。

內(nèi)存排布

在開始討論前，我們首先引入一個(gè)衡量?jī)?nèi)存利用率的指標(biāo)——內(nèi)存碎片（fragments），分為內(nèi)部碎片和外部碎片。為了理解這個(gè)概念，我們可以思考下平日中“豐巢寄存柜”的工作原理，借此意象來比對(duì)理解分配器如何進(jìn)行內(nèi)存排布的。

“豐巢”一般是問物業(yè)要一塊地方，來建立一個(gè)快遞柜（對(duì)應(yīng)一個(gè) Arena），就近服務(wù)小區(qū)居民。對(duì)于每個(gè)快遞柜，會(huì)進(jìn)一步將其劃分成一個(gè)個(gè)格子，但如何劃分就是講究之處。

由于快遞通常大小不一，如果將快遞柜等分，會(huì)有什么問題？

1. 對(duì)于小快遞，每個(gè)格子會(huì)浪費(fèi)很多空間（內(nèi)部碎片）
2. 對(duì)于大快遞，所有格子都放不下（明明總空間夠，但卻放不下，此時(shí)整個(gè)格子就是外部碎片）

為了解決這個(gè)問題，我們?nèi)粘Ｖ兴姷目爝f柜多會(huì)分成大大小小尺寸不等的格子。但仍然可能有快遞員，選一個(gè)大格子卻放一個(gè)小快遞。對(duì)于真實(shí)世界來說，這無解，因?yàn)樗懈褡邮窃诳爝f柜出廠時(shí)就分好的，也即“靜態(tài)分配”的；但在計(jì)算機(jī)世界，我們對(duì)內(nèi)存的劃分都是“邏輯上的”，因此可以做到“動(dòng)態(tài)分配”。

如果有人往大格子中放了一個(gè)小對(duì)象，可以將剩下的空間切出來形成一個(gè)新格子，給后面的對(duì)象用。且，在后面該小對(duì)象被取走后，可以將兩個(gè)格子重新合并成一個(gè)大格子，以應(yīng)對(duì)更大的對(duì)象。

這就是“伙伴分配算法”的基本思想，當(dāng)然，這并非 jemalloc 原創(chuàng)。但 jemalloc 在“二分伙伴算法”基礎(chǔ)上，通過統(tǒng)計(jì)用戶負(fù)載，進(jìn)一步精細(xì)化管理內(nèi)存，從而控制了碎片的無節(jié)制增長(zhǎng)。

比如 jemalloc 發(fā)現(xiàn)，大部分的對(duì)象不超過 512 B，因此引入了“量子間距”（quantum-spaced）。對(duì)這個(gè)尺寸附近及以下的格子并不使用伙伴算法，而是在一個(gè)頁(yè)內(nèi)進(jìn)行靜態(tài)分配，讓其全是同樣大小的格子——這樣有什么好處呢？由于每個(gè)格子大小固定，就可以使用 bitmap 來充當(dāng)空閑列表，從而加快了空閑列表的查找。

memory layout

這種精細(xì)化管理雖然會(huì)帶來比較多的外部碎片（很多格子用不了），但卻能更多地減少內(nèi)部碎片（大部分格子能用滿），得可償失。

評(píng)估

由于實(shí)踐中不同應(yīng)用程序內(nèi)存負(fù)載的千變?nèi)f化，如何衡量分配器好壞本身就是一個(gè)非常復(fù)雜的問題。很可能一個(gè)分配器設(shè)計(jì)出來后，在某些用戶負(fù)載中表現(xiàn)良好、但在另外負(fù)載中卻表現(xiàn)極差，此時(shí)我們很難說其是一個(gè)好的分配器。好的分配器應(yīng)該是多數(shù)方面表現(xiàn)均衡、某些方面表現(xiàn)突出——因?yàn)槊鎸?duì)如此復(fù)雜的現(xiàn)實(shí)世界，不可能所有方面都好，總會(huì)有取舍。

因此作者花了很大功夫來設(shè)計(jì)了一套分配器性能評(píng)價(jià)工具，來證明 jemalloc 的優(yōu)勢(shì)，但這部分就不是本文重點(diǎn)了，感興趣的同學(xué)可以去查論文原文。

小結(jié)

我們首先鋪墊了內(nèi)存分配器的一些背景，說明了分配器是什么（malloc/free），不是什么（auto gc），和什么相似（存儲(chǔ)引擎 put/get）；然后分析了論文中實(shí)現(xiàn) jemalloc 的主要目標(biāo)——多核擴(kuò)展；繼而討論了其主要實(shí)現(xiàn)思路——為了避免競(jìng)爭(zhēng)和緩存震蕩問題，引入均勻的內(nèi)存分區(qū)；為了減少碎片問題，基于伙伴算法對(duì)分區(qū)內(nèi)存精細(xì)化管理，并以“豐巢快遞柜”比對(duì)來幫助理解。

最后提了一嘴如何評(píng)估分配器的好壞。需要強(qiáng)調(diào)的是，本文旨在幫你建立直覺，有想要展開查證之處，強(qiáng)烈推薦大家去讀論文原文。

參考資料

[1]glibc malloc: https://github.com/lattera/glibc/blob/master/malloc/malloc.c

[2]jemalloc: https://jemalloc.net/

[3]A Scalable Concurrent malloc(3) Implementation for FreeBSD: https://www.bsdcan.org/2006/papers/jemalloc.pdf

[4]jemalloc github 倉(cāng)庫(kù): https://github.com/jemalloc/jemalloc