jemalloc分配機制的介紹及其優(yōu)化實踐

前言

C++ 語言中提供了大量的類庫和編程接口，雖然可以幫助開發(fā)者提升研發(fā)效率，但在特定場景下，其性能表現仍存在優(yōu)化空間。開發(fā)者往往追求極致的代碼性能邏輯，一點點的優(yōu)化改變就可以幫助業(yè)務獲得良好的性能收益。在字節(jié)降本提效的過程中，STE 團隊在算力監(jiān)控系統(tǒng)中發(fā)現 Jemalloc 是業(yè)務的前五大 CPU 熱點基礎庫，具有很高的潛在性能優(yōu)化空間。因此，從 2019 年開始對 Jemalloc 進行深度優(yōu)化，并在字節(jié)內部進行了大范圍的優(yōu)化落地，幫助業(yè)務團隊取得了較好的收益。本文將主要介紹 Jemalloc 的基本原理以及一些簡單易用的優(yōu)化方法，幫助開發(fā)者在 Jemalloc 的實際應用中，獲得更好的性能表現。

內存相關概念簡介

Linux內存分配與分配器

當代 Linux 系統(tǒng)中可以同時運行多種多樣的進程，并且進程之間可以做到內存互相隔離，這得益于 Linux 的進程地址空間管理。

一個進程的地址空間中，包含了靜態(tài)內存、以及動態(tài)內存(常說的堆棧)，棧的動態(tài)分配和釋放由編譯器完成，對于堆上內存，Linux 提供了 brk、sbrk、mmap、munmap 等系統(tǒng)調用來進行內存分配和釋放，但是這些函數的直接使用會帶來不小的理解門檻和使用復雜性，如 brk 需要指定堆的上界地址，容易出現內存錯誤；mmap 直接申請 pagesize 為單位的內存，對于小于此內存的分配會造成極大的內存浪費。因此需要有內存分配器來輔助管理堆的動態(tài)申請和釋放。

通常內存分配器如 ptmalloc提供了 malloc 等函數來進行內存的分配，free 進行內存釋放，這些函數在底層調用了 brk、mmap 等函數申請內存，并以地址的形式返回給用戶，用戶在 malloc、free 匹配的情況下不必擔心在分配和釋放時出現內存錯誤或者內存浪費。

內存碎片

雖然內存分配器在一定程度上保證了內存的利用率，但是不可避免地會出現內存碎片，包括了內存頁內碎片和內存頁間碎片，碎片的產生會導致部分內存不可用，內存碎片的大小也是評估一個內存分配器好壞的重要指標。

常見的內存分配管理算法

堆上內存以鏈式形式存在，最簡單的動態(tài)內存分配算法有：

First fit：尋找找第一個滿足請求 size 的內存塊做分配

Next fit：從當前分配的地址開始，尋找下一個滿足請求 size 的空閑塊

best fist：對空閑塊進行排序，然后找第一個滿足要求的空閑塊

另外還有 Buddy 算法和 Slab 算法，也是 jemalloc 中用到的核心算法：

Buddy allocation

Buddy 算法簡單來說如上圖，一般 2 的 n 次冪大小來管理內存，當申請的內存 size 較小，且當前空閑內存塊均大于 size 的兩倍，那么會將較大的塊分裂，直到分裂出大于size，并小于 size * 2的塊為止；當內存 size 較大時則相反，會將空閑塊不斷合并。

Buddy 算法沒有塊間內存碎片，但是塊內內存碎片較大，可以看到當申請 2KB+1B 的 size 時，需要用 4KB 的內存塊，內存碎片最壞情況可達 50%。

Slab allocation

調用 Linux 系統(tǒng)調用進行內存的分配和釋放會讓程序陷入內核態(tài)，帶來不小的性能開銷，slab 算法應運而生。每個 slab 都是一塊連續(xù)內存，并將其劃分成大小相同的 slots，用 bitmap 來記錄這些 slots 的空閑情況，內存分配時，返回一個 bitmap 中記錄的空閑塊，釋放時，將其記錄忙碌即可，而 slab size 和 slot size 是內存碎片大小的關鍵。

Jemalloc簡介

Jemalloc 是 malloc(3) 的實現，在現代多線程、高并發(fā)的互聯網應用中，有良好的性能表現，并提供了優(yōu)秀的內存分析功能。

Jemalloc 主要有以下幾個特點：

高效地分配和釋放內存，可以有效提升程序的運行速度，并且節(jié)省 CPU 資源

盡量少的內存碎片，一個長穩(wěn)運行地程序如果不控制內存碎片的產生，那么可以預見地這個程序會在某一時刻崩潰，限制了程序的運行生命周期

支持堆的 profiling，可以有效地用來分析內存問題

支持多樣化的參數，可以針對自身地程序特點來定制運行時 Jemalloc 各個模塊大小，以獲得最優(yōu)的性能和資源占用比

下文主要介紹了 Jemalloc 的內存分配算法、數據結構，以及一些針對具體程序的優(yōu)化實踐和建議。

Jemalloc核心算法與數據結構

Jemalloc 整體的算法和數據結構基于高效和低內存碎片的原則進行設計，主要體現在：

隔離了大 Size 和小 Size 的內存分配(區(qū)分默認閾值為 3.5 個 Pagesize)，可以有效地減少內存碎片

在內存重用時默認使用低地址，并將內存控制在盡量少的內存頁上

制定 size class 和 slab class，以便減少內存碎片

嚴格限制 Jemalloc 自身的元數據大小

用一定數量的 arena 來管理內存的單元，每個 arena 管理相當數量的線程，arena 之間獨立，盡量減少多線程時鎖競爭

我們來看下 Jemalloc 是如何來實現這些特性的。

Extent

Jemalloc 的內存管理結合了 buddy 算法和 slab 算法。Jemalloc 引入 extent 的概念，extent 是 arena 管理的內存對象，在 large size 的 allocation 中充當 buddy 算法中的 chunk，small size allocation 中，充當 slab。

每個 extent 的大小是 Pagesize 的整數倍，不同 size 的 extent 會用 buddy 算法來進行拆分和合并，大內存的分配會直接使用一整個的 extent 來存儲。小內存的分配使用的是 slab 算法，slab size 的計算規(guī)則為 size 和 pagesize 的最小公倍數，因此每個extent總是可以存儲整數倍個對應 size。

extent 本身設置 bitmap，來記錄內存占用情況，以及自身的各種屬性，同類型的 extents 用 paring heap 存儲。

此外，arena 將 extent 分為多種類型，有當前正在使用未被填滿的extent，有一段時間未使用的dirty extent，還有長時間未使用的muzzy extent，以及開啟retained功能后的retained extent，extent分類的作用相當于多級緩存，當線程內存分配壓力較小時，空余的extent會被緩存，以備壓力增大時使用，可以避免與操作系統(tǒng)的交互。

Small size align and Slab size

為了減少頁內內存碎片，Jemalloc 對 small size 進行了對齊，對于每一個 size，以二進制的視角來看，將其分為兩個數：group、mod。group 表示 size 的二進制最高位，如果 size 正好為 2 的冪次，則將其分在上一個 group 中；mod 表示最高位的后兩位，有 0、1、2、3 共 4 種可能。這樣構成的 align 后的 size 在同一個 group 中步長（即兩個相鄰 mod 計算得到的 size 之間的差值）相同，group 越大，步長會呈 2 的倍數增長。

如下圖，框中的 4個是同一個 group 中 4 種 mod 在 align 后的 size，其中 160 表示包含了 129B 到 160B 在對齊后的大?。?/p>

計算出 aligned size 后，就需要計算 slab size，每個 slab size 為 pagesize 和 aligned size 的最小公倍數，以防止跨 slab 的 size 或者 slab 無法被填滿的情況出現。以 4K page 為例，128B 的 slab size 即 4K，160B 的 slab size 為 20K。

Tcache and arena

為了減少多線程下鎖的競爭，Jemalloc 參考 lkmalloc 和 tcmalloc，實現了一套由多個 arena 獨立管理內存加 thread cache 的機制，形成 tcache 有空余空間時不需要加鎖分配，沒有空余空間時將鎖控制在線程所屬 arena 管理的幾個線程之間的模式。

tcache 中每一個 size 對應一個 bin，當 tcache 需要填充時，在 arena 中發(fā)生的如下圖：

allocation/dallocation in tcache

tcache 以 thread local storage對象的形式存儲，主要服務于 small size 和一小部分 large size。

當 tcache 中有空閑時，一次 malloc 的過程很簡單：

對 size 做 align 得到 usize

查找 usize 對應的 bin，bin 為 tcache 中針對不同 size 設置的 slots

bin 有空閑地址則直接返回，沒有空閑地址則會向 arena 請求填充

每個 bin 的結構如下圖，avail 指向 bin 的起始地址，ncached 初始為 bin 的最大值 ncached_max (與 slab size 相關，最小為 20 最大為 200)，每次申請內存會返回 ncached 指向的地址并自減1，直到小于限制值。

釋放的時候相反，當 tcache 不為空，即 ncached 不等于 bin 的 ncached_max 時，ncached 自加1，并且將 free 的地址填入 bin 中。

Tcache fill

上面的 allocation 過程是 tcache 中有足夠的空閑塊供分配，當 tcache 中已經沒有空閑塊時，會向其所屬的 arena 申請 fill，此時 arena 中會加鎖去分級 extent 取空閑塊，并把當前使用的 extent 移入full extent。

Tcache flush

當 dallocate 觸發(fā) tcache 中又沒有分配任何內存，即 ncached_max 等于 ncached_max 時，tcache 會觸發(fā) flush，flush 會將 tcache 中一半的內存釋放回原 extent，即將 tache 的可用空間壓縮到原來的一半，這個過程中也會加對應 extent 的鎖以保證同步。

Jemalloc優(yōu)化思路

從上一章節(jié)可以看到，jemalloc 對于內存用的是多級緩存的思路，tcache 的代價最小，無須加鎖可以直接返回；其次是 arena 的 bin->extent，鎖的粒度在對應的 bin 上，會是 bin 對應的 size 在這個 arena 中無法再做 fill 或 flush；然后是 dirty extent、muzzy extent，這部分是 arena 全局加鎖，會鎖住其他線程的 fill 或者 purge，那么在多線程下，我們可以用幾個思路來優(yōu)化鎖的競爭。

arena優(yōu)化

從上一章節(jié)可知，jemalloc 將鎖的范圍都控制在 arena 中，每個 arena 會管理一系列線程，線程在 arena 中是平均分配的，arena 默認數量是 CPU 個數 * 4。因此，當我們在一臺 8 核的機器上運行 256 個線程時，意味著每個arena 需要管理 8 個線程，這些線程在內存任務繁重時會產生嚴重的鎖競爭，從而影響性能。此時可選擇使用 malloc_conf128，增加 arena 數量到 128 個，每個 arena 只需管理 2 個線程，線程之間產生鎖競爭的概率就會大大減小。

此外還可以選擇用 mallocx 隔離線程，讓內存分配任務較重的線程獨占 arena。

Slab size優(yōu)化

Slab size 的大小如上所述，為 usize 大小和 pagesize 的最小公倍數，這一機制可以保證減少內存碎片，但是tcache 的 fill 與 flush 都與 slab size 相關，一個和業(yè)務內存模型匹配的 slab class 才可以得到最好的性能效果。

下面是一張 jemalloc 和 ptmalloc 的對比圖，可以看到在 1024 以下的性能 jemalloc 都優(yōu)于 ptmalloc，但是jemalloc 自身的性能明顯存在波動，幾個波動出現在 128B、256B、512B 以及 1024B 周圍，因為這些 size 本身就是 pagesize 的因子或者公因子較多，所以 slab size 占用的 page 數也相對較少，fill 和 flush 所需要的slab數也越多。

dirty decay & muzzy decay

盡管我們希望將所有的 malloc、free 內存都可以放在 tcache 中或者 bin 中，這樣可以最大化執(zhí)行效率，但是實際的程序中這很難做到，因為每個線程都需要增加內存，會造成不小的內存壓力，而且內存的申請釋放往往會有波峰，dirty extents 和 muzzy extents 就可以來應對這些內存申請的波峰，而避免需要轉入內核態(tài)來重新申請內存頁。

dirty_decay_ms 和 muzzy_decay_ms 是 jemalloc 中用來控制長時間空閑內存衰變的時間參數，適當地擴大 dirty decay 的時間可以有效地解決性能劣化的尖刺。

Tcache ncached_max

tcache 中每一個 bin 的 slots 數量由 ncached_max 決定，當 tcache 中 ncached_max 耗盡時會觸發(fā) arena 的 fill tcache 而產生鎖，而 ncached_max 的大小默認為 2 * slab size，最小為 20，最大為 200，適當地擴大 ncached_max 值可以在一些線程上形成更優(yōu)的 allocation/deallocation 循環(huán)（5.3版本已支持用malloc_conf進行更改）。

優(yōu)化方法：調優(yōu)三板斧

結合以上優(yōu)化思路，通過以下步驟對應用進行調優(yōu)：

Dump stats

在 long exist 的程序中可調用 jemalloc 的 malloc_stats_print 函數，dump 出應用當前內存分配信息：

// reference: https://jemalloc.net/jemalloc.3.html
void malloc_stats_print(void (*write_cb)(void *, const char *), // 回調函數，可以寫入文件
                        void *cbopaque, // 回調函數參數
                        const char *opts); // stats的一些選項，如"J"是導出json格式

或通過設置 malloc_conf，在程序運行結束后自動 dump stats：

export MALLOC_CONF=stats_print:true

stats 分析

用 Json 格式 dump stats 后，可以得到如下圖所示結構的 json 文件：

各字段含義可參考：
https://jemalloc.net/jemalloc.3.html

按上一章節(jié)思路，可主要關注以下幾點： （1）arena 數量與 threads 數量比例

arena 數：jemalloc->arenas->narenas

threads 數：jemalloc->stats.arenas->merged->nthreads

分析：

threads : arenas 比例代表了單個 arena 中管理的線程數，將 malloc、free 較多，并且有可能產生競爭的線程盡量獨占 arena。

（2）各個 extent 中 mutex 開銷

jemalloc->stats.arenas->merged->mutexes

分析：

該節(jié)點中的 mutex 操作次數、等鎖時間可以反映出該類型 extent 的鎖競爭程度，若 extent_retained 鎖競爭嚴重，可適當調大 muzzy_decay_ms；同理，當 extents_muzzy 鎖競爭嚴重，可適當調大 diry_decay_ms；extents_dirty 鎖競爭嚴重，可適當調大 ncached_max，讓malloc 盡量可以在 tcache 中完成

（3）arena 中各個 bin 的 malloc、free 次數

jemalloc->stats.arenas->merged->bins

分析：

bin 中的 nfills 可以反映該 slab 填充的次數，針對 regions 本身較少，nfill 次數又多的 size，如 521B、1024B、2048B、4096B 等，可適當調大 slab size 來減小開銷

添加MALLOC_CONF參數或修改代碼

MALLOC_CONF 是 jemalloc 中用來動態(tài)設置參數的途徑，無須重新編譯二進制，可以通過 MALLOC_CONF 環(huán)境變量或者 /etc/malloc_conf 軟鏈接形式設置，參數之間用 ',' 分割。除需要使用線程獨占的 arena 外，以上其他優(yōu)化均可通過 MALLOC_CONF 配置來完成。

（1）arena優(yōu)化方法

narenas 設置：

export MALLOC_CONF=narenas:xxx  # xxx最大為1024

或

ln -s "narenas:xxx" /etc/malloc_conf

設置線程獨占的 arena：

unsigned thread_set_je_exclusive_arena() {
  unsigned arena_old, arena_new;
  size_t sz = sizeof(unsigned);


  /* Bind to a manual arena. */
  if (mallctl("arenas.create", &arena_new, &sz, NULL, 0)) {
    std::cout << "Jemalloc arena create error
";
    return 0;
  }
  if (mallctl("thread.arena", &arena_old, &sz, &arena_new, sizeof(arena_new))) {
    std::cout << "Thread bind to jemalloc arena error
";
    return 0;
  }
  return arena_new;
}

（2）各類大小優(yōu)化方法

dirty extents：

export MALLOC_CONF=dirty_decay_ms:xxx  # -1為不釋放dirty extents，易發(fā)生OOM

muzzy extents：

export MALLOC_CONF=muzzy_decay_ms:xxx  # -1為不釋放muzzy extents，易發(fā)生OOM

tcache ncached_max 調整，ncached_max 與 slab size 相關，計算方式為

(slab_size / region_size) << lg_tcache_nslots_mul (默認值1)

最大限值為 tcache_nslots_small_max(默認200)，最小限值為 tcache_nslots_small_min(默認20)。

如調整 32B 的 ncached_max，當前系統(tǒng) page size 為 4K，計算默認的 ncached_max 的方法：

(slab_size / region_size) << lg_tcache_nslots_mul = (4096 / 32) << 1 = 256

超過了 tcache_nslots_small_max，所以 32B 的 ncache_max 默認即為 200。

調整 ncached_max 默認值相關參數：

export 
MALLOC_CONF=tcache_nslots_small_min:xxx,tcache_nslots_small_max:xxx,lg_tcache_nslots_mul:xxx

Slab size 設置方法：

export MALLOC_CONF="slab_sizes17|100-200:1|128-128:2" # -左右表示size范圍，:后設置page數，|分割各個不同的size范圍

字節(jié)業(yè)務優(yōu)化案例

Jemalloc 的 stats dump 已經集成到監(jiān)控系統(tǒng)中，經過分析發(fā)現，字節(jié)內部的應用普遍線程數量較多，在 arena 中的鎖競爭比較激烈，并且 allocte/deallocte 集中在某些線程中，因此可以通過讓核心線程獨占 arena 來完成優(yōu)化。以其中一個業(yè)務在平臺上的 stats 數據為例：

可以看到進程總線程數為 1776 個，arenas 數量為 256 個，平均每個 arena 中的內存需要有 7-8 個線程共享，再查看 mutexs 的 stats ：

可以看到在 extents 中產生鎖的開銷并不小，首先選擇擴大 arenas 的數量，從 256 擴大到 1024 個，發(fā)現 CPU 相對下降了 4.5%，但是相對的內存上漲了 10%，在分析代碼后，發(fā)現 allocate/deallocate 較多的線程總數量只有80+，針對這些線程通過 mallctl 單獨創(chuàng)建了 arena，并綁定 tcache，并調小其他線程的 muzzy_decay_ms，最終為該業(yè)務節(jié)省了 4% 的 CPU 收益，內存基本持平。

總結

最好的基礎庫總是通用的，最適合的基礎庫總是最個性化的。對于 jemalloc 在業(yè)務上的優(yōu)化與實踐，STE團隊進行不斷探索，采集內存信息并進行平臺化展示，以便業(yè)務及時發(fā)現自身程序在 jemalloc 上的性能瓶頸，并做出針對性地調優(yōu)，目前已在 10+ 業(yè)務上進行參數優(yōu)化，平均幫助各業(yè)務團隊節(jié)省了 3% 的 CPU（jemalloc 在部分業(yè)務中平均占用 10% ~ 15% 的CPU）。未來 STE 團隊將繼續(xù)深入 jemalloc 性能優(yōu)化，探索定制化的業(yè)務內存分配和管理方案，以獲得更好的優(yōu)化成果。

審核編輯：劉清