引子

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

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

背景

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

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

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

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

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

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

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

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

主要思想

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

多核并發(fā)

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

1. 搶鎖競爭
2. 緩存震蕩

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

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

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

cache sloshing

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

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

內(nèi)存排布

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

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

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

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

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

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

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

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

memory layout

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

評估

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

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

小結

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

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

參考資料

[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 倉庫: https://github.com/jemalloc/jemalloc