從“豐巢”快遞柜看Jemalloc 的內存管理
引子
在某些工作負載中，隨著時間的推移，內存的使用會逐漸增長，直到 OOM。后面發現是內存碎片問題，而將系統默認的內存分配器（glibc malloc[1]）換成 jemalloc[2] ，能有效控制內存的增長上界。
為了解其背后原理，便找來 jemalloc 最初的論文：A Scalable Concurrent malloc(3) Implementation for FreeBSD[3] 來一探究竟。當然，相比 2006 年論文發表時，當前的 jemalloc 可能已經發生了很大改變，因此本文只對當時論文內容負責。更多 jemalloc 機制，大家可以去其 github 倉庫[4]查看文檔和源碼。
背景
在探討論文的主要思路之前，我們先簡單回顧下內存分配器（memory allocator）的作用和邊界。簡言之：
- 對下，向操作系統申請大塊內存（使用 sbrk、mmap 等系統調用）
- 對上，處理應用層的各種尺寸的內存申請請求（malloc(size)），并在應用層“表示”不用（free）后進行釋放
往小了說，分配器的功能非常簡單：分配和釋放（malloc 和 free）。想象中，實現也應該很簡單，只需利用一個表來記錄所有已使用內存和未分配內存（ a bit of bookkeeping），然后：
- malloc 請求來了，先去空閑表中找，不夠的話就問操作系統要
- free 請求來了，還回空閑表中，如果空的多了，就還給操作系統
但為了實現內存的高效分配和回收、控制內存的利用率，其間的學問就大了去了，CPU 緩存、 RAM 特性和虛擬內存都會對其造成影響。其中最核心的點，就是如何進行內存組織排布，以便在用戶高并發、多尺寸、不定時的申請和釋放后，仍然能保證較低的調用延遲和較高的使用率。當然，對于本論文來說，還要加上一條：越多的核數能夠支持越高的并發，謂之可擴展（scale）。
需要說明的是，不要將本文的內存分配器和各種具有自動 GC 功能的編程語言運行時（比如 Java 的 JVM、Golang 的 Runtime）所混淆。后者是在 malloc/free 的基礎上，往上繼續封裝了一層，通過對象間的引用關系來追蹤每個對象的生命周期，以自動地回收空間。
可以這么理解，C++/C 等編程語言要用戶自己通過 malloc/free 來管理內存；而使用 Java/Golang/Python，用戶無腦新建對象就可以了，什么時候回收是語言“運行時”的工作。而我們本文只討論前者。
但從另外角度來看，存儲引擎中也實現了類似的功能。因為存儲引擎本質上也是要面對用戶 put/delete 的的請求，來進行存儲的的分配和釋放。只不過這里的存儲，就不局限于內存（存儲引擎多是 disk-based）。但其主要思想非常相似，比如使用空閑列表（free list）對可分配內存進行追蹤。
主要思想
從論文標題可以看出，jemalloc 在提出時，主要為了解決在多核時代下內存分配器性能隨核數而 scale 問題，但其實論文花了相當多的篇幅來闡釋如何進行內存排布來解決碎片問題。下面，我們就圍繞這兩個方向來大致窺探下其原理。
多核并發
在多核時代進行內存分配時，主要面對的問題有：
- 搶鎖競爭
- 緩存震蕩
為了保證全局數據結構的一致性的問題，就必須引入某種手段（比如鎖）來進行協調。但如果多線程搶鎖過于頻繁，就會造成嚴重的性能下降。為了降低對鎖的競爭，自然的想法就是，對主要的全局數據結構粒度拆分（比如 Java 的 ConcurrentHashMap 就是將哈希桶分成了多個段進行上鎖）。
分配器中最重要的數據結構就是空閑列表，我們可以將空閑列表拆分成多個，每個空閑列表使用單獨的鎖。這樣可以緩解多線程的競爭問題，但卻解決不了多核架構的另外一個問題——緩存震蕩（cache sloshing）。
在多核架構中，如果兩個線程沒有正確的共享緩存。比如線程 A 和線程 B 共享了一個緩存行（Cache Line），且兩線程分別會反復修改緩存行的不同部分。如果 A 和 B 調度到了不同的 CPU 上，就會造成 Cache Line 所有權的反復競爭。
cache sloshing
為了解決此問題，jemalloc 會將所管理的內存分為幾個（通常是 CPU 核數的四倍）區域（ 稱為 Arena，“競技場”）。在不同線程的 client 到來時，會均勻地（round robin）綁定到某個 Arena，之后該 client 所有內存的申請和釋放都發生在該 Arena。論文還提及了 Larson and Krishnan (1998) 之前使用 hash 的方法進行綁定，但由于哈希過程是偽隨機的（pseudo-random），因此很難保證線程到 Arena 的均勻。
下面我們來討論如何在每個 Arena 內排布內存來應對用戶對象的申請和釋放。
內存排布
在開始討論前，我們首先引入一個衡量內存利用率的指標——內存碎片（fragments），分為內部碎片和外部碎片。為了理解這個概念，我們可以思考下平日中“豐巢寄存柜”的工作原理，借此意象來比對理解分配器如何進行內存排布的。
“豐巢”一般是問物業要一塊地方，來建立一個快遞柜（對應一個 Arena），就近服務小區居民。對于每個快遞柜，會進一步將其劃分成一個個格子，但如何劃分就是講究之處。
由于快遞通常大小不一，如果將快遞柜等分，會有什么問題？
- 對于小快遞，每個格子會浪費很多空間（內部碎片）
- 對于大快遞，所有格子都放不下（明明總空間夠，但卻放不下，此時整個格子就是外部碎片）
為了解決這個問題，我們日常中所見的快遞柜多會分成大大小小尺寸不等的格子。但仍然可能有快遞員，選一個大格子卻放一個小快遞。對于真實世界來說，這無解，因為所有格子是在快遞柜出廠時就分好的，也即“靜態分配”的；但在計算機世界，我們對內存的劃分都是“邏輯上的”，因此可以做到“動態分配”。
如果有人往大格子中放了一個小對象，可以將剩下的空間切出來形成一個新格子，給后面的對象用。且，在后面該小對象被取走后，可以將兩個格子重新合并成一個大格子，以應對更大的對象。
這就是“伙伴分配算法”的基本思想，當然，這并非 jemalloc 原創。但 jemalloc 在“二分伙伴算法”基礎上，通過統計用戶負載，進一步精細化管理內存，從而控制了碎片的無節制增長。
比如 jemalloc 發現，大部分的對象不超過 512 B，因此引入了“量子間距”（quantum-spaced）。對這個尺寸附近及以下的格子并不使用伙伴算法，而是在一個頁內進行靜態分配，讓其全是同樣大小的格子——這樣有什么好處呢？由于每個格子大小固定，就可以使用 bitmap 來充當空閑列表，從而加快了空閑列表的查找。
memory layout
這種精細化管理雖然會帶來比較多的外部碎片（很多格子用不了），但卻能更多地減少內部碎片（大部分格子能用滿），得可償失。
評估
由于實踐中不同應用程序內存負載的千變萬化，如何衡量分配器好壞本身就是一個非常復雜的問題。很可能一個分配器設計出來后，在某些用戶負載中表現良好、但在另外負載中卻表現極差，此時我們很難說其是一個好的分配器。好的分配器應該是多數方面表現均衡、某些方面表現突出——因為面對如此復雜的現實世界，不可能所有方面都好，總會有取舍。
因此作者花了很大功夫來設計了一套分配器性能評價工具，來證明 jemalloc 的優勢，但這部分就不是本文重點了，感興趣的同學可以去查論文原文。
小結
我們首先鋪墊了內存分配器的一些背景，說明了分配器是什么（malloc/free），不是什么（auto gc），和什么相似（存儲引擎 put/get）；然后分析了論文中實現 jemalloc 的主要目標——多核擴展；繼而討論了其主要實現思路——為了避免競爭和緩存震蕩問題，引入均勻的內存分區；為了減少碎片問題，基于伙伴算法對分區內存精細化管理，并以“豐巢快遞柜”比對來幫助理解。
最后提了一嘴如何評估分配器的好壞。需要強調的是，本文旨在幫你建立直覺，有想要展開查證之處，強烈推薦大家去讀論文原文。
參考資料
[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
