Malloc技術原理解析以及在轉轉搜索業(yè)務上的實踐
1 導讀
內存管理在三個不同的層面上發(fā)揮作用：用戶程序層、C運行時庫層以及內核層。其中，內存分配器allocator是C運行時庫中的一個關鍵組件，其主要任務是響應用戶程序的內存分配請求。分配器負責向操作系統內核請求適當大小的內存塊，并將這些內存塊分配給用戶程序。
為了提高內存分配的效率，分配器通常會預先分配一塊稍大于用戶請求的內存空間，并使用特定的算法來管理這塊內存，以滿足用戶的內存需求。不同之處在于，用戶釋放的內存并不會立即返回給操作系統，而是由分配器來管理這些空閑內存空間，以備將來用戶的內存分配請求。簡而言之，分配器的任務不僅僅是管理已分配的內存塊，還包括有效地管理可用的空閑內存塊。當需要響應用戶的內存分配請求時，分配器會首先在已有的空閑內存中查找合適大小的內存塊，只有在空閑內存不足時才會申請新的內存。系統的物理內存是有限的，而對內存的需求是變化的, 程序的動態(tài)性越強，內存管理就越重要，選擇合適的內存分配庫會帶來明顯的性能提升。
在轉轉的服務中，許多服務存在較高的堆外內存使用問題，例如轉轉搜索業(yè)務的排序服務，堆外內存的使用超出了預期，這已經導致了許多物理機內存的不足。初步分析表明，這些內存占用較高的轉轉服務內部使用TensorFlow進行推斷，Linux默認使用的glibc的malloc實現在內存池資源回收方面存在缺陷，導致已分配的內存無法有效地返還給操作系統，根據此現狀，需要對現有的可選malloc進行原理分析和合理選擇，優(yōu)化服務的內存占用表現，緩解服務器內存不足的現狀。常見的內存分配庫包括ptmalloc（作為glibc標準庫的一部分）、tcmalloc（由Google開發(fā)）、jemalloc（由Facebook開發(fā)），由于篇幅較長，下文將對ptmalloc和tcmalloc的基本原理和相關參數進行介紹，并只介紹jemalloc的參數部分。
2 內存管理與系統調用
在介紹ptmalloc、tcmalloc等內存分配庫之前，讓我們先了解一下內存布局：
圖片
上圖描述了x86_64架構下的Linux進程默認地址空間，棧從頂向下擴展，堆從底向上擴展，而mmap映射區(qū)域也是從頂向下擴展。mmap映射區(qū)域與堆相對擴展，直到耗盡虛擬地址空間，操作系統提供了brk()系統調用，用于設置堆的上邊界。其次，針對mmap映射區(qū)域的操作，可以使用mmap()和munmap()函數。由于系統調用的開銷較高，因此不太適合在每次需要內存分配時都從內核申請空間，特別是對于小內存分配來說更是如此。另外，mmap的映射區(qū)域可能會因為munmap()的釋放而容易被回收。因此，一般的做法是對于大內存分配，使用mmap()來申請內存，而對于小內存分配，則采用brk()方式。這其中也包含了linux內存管理的基本思想：內存延遲分配。即只有在真正訪問一個地址的時候才建立這個地址的物理映射。linux內核在用戶申請內存的時候，只是給它分配了一個虛擬地址，并沒有分配實際的物理地址，只有當用戶使用這塊內存的時候，內核才會分配具體的物理地址給用戶使用。
2.1 brk() 和 sbrk()
#include <unistd\.h>
int brk(void *addr);brk()是一個系統調用，其實現定義在mmap.c中。它的主要作用是調整堆頂的位置，使堆內存可以從低地址向高地址增長。在分配內存時，brk()會將堆段的最高地址指針mm->brk向高地址擴展，然后調用do_brk_flags來分配新的虛擬內存區(qū)域（Virtual Memory Area，VMA），并將這個VMA插入到內核的鏈表和紅黑樹中。
需要注意的是，雖然使用brk()分配了一段新的虛擬內存區(qū)域，但這并不會立即分配物理內存。實際的物理內存分配通常是在訪問新分配的虛擬內存區(qū)域時，如果發(fā)生了缺頁異常（Page Fault），操作系統才會開始分配并映射相應的物理內存頁面，內存收縮時，調用__do_munmap對heap進行收縮。
圖片
- Brk()的參數設置為新的brk上界地址，成功返回1，失敗返回0；
- Sbrk()的參數為申請內存的大小，返回heap新的上界brk的地址。
2.2 mmap()
圖片
mmap()系統調用用于在進程的虛擬地址空間中創(chuàng)建新的內存映射。內存分配器通常使用這個系統調用來創(chuàng)建私有匿名映射，以分配內存。內核會按照頁面大小的倍數（通常為4096字節(jié)）來分配內存，函數原型如下：
#include <unistd\.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);一旦建立了這種映射關系，進程就可以通過指針的方式來讀寫這段內存，而系統會自動將臟頁（被修改的頁）回寫到相應的磁盤文件上。這意味著進程可以通過直接訪問內存來完成對文件的操作，而無需再調用read、write等系統調用函數。
除了減少read、write等系統調用外，mmap()還可以減少內存拷貝的次數。例如，在使用read調用時，典型的流程是操作系統首先將磁盤文件內容讀入頁緩存，然后再將數據從頁緩存復制到read傳遞的緩沖區(qū)中。然而，使用mmap()后，操作系統只需將磁盤數據讀入頁緩存，然后進程可以直接通過指針方式操作mmap映射的內存，從而減少了從內核態(tài)到用戶態(tài)的數據拷貝。
3 ptmalloc
目前大部分服務端程序使用GNU Libc的內存分配器ptmalloc，起源于Doug Lea的malloc，進而由Wolfram Gloger改進得到可以支持多線程。ptmalloc的設計是在性能和內存放大之間做了權衡，為了降低鎖沖突，設置了多arena機制，卻間接增加了內存碎片，從而導致物理內存的消耗增加。下面將對服務器常用的centos7上使用的ptmalloc2的技術細節(jié)進行介紹和分析。
3.1 整體架構
主分配區(qū)（main_area）和非主分配區(qū)（no_main_area）：當多個線程同時使用malloc分配內存時，內存分配器會采取一些策略來解決線程之間的鎖競爭問題。分配器將內存分配區(qū)分為兩種：主分配區(qū)和非主分配區(qū)。這兩種分配區(qū)被組織成一個環(huán)形鏈表，以便進行有效管理。每個分配區(qū)都使用互斥鎖來確保線程對其的訪問是互斥的。每個進程只有一個主分配區(qū)，但可以有多個非主分配區(qū)。ptmalloc根據系統對分配區(qū)的競爭情況動態(tài)調整分配區(qū)的大小，一旦增加了分配區(qū)的數量，就不會再減少。主分配區(qū)可以使用brk和mmap來分配內存，而非主分配區(qū)只能使用mmap來映射內存塊。在分配小內存時，可能會導致內存碎片問題，因此ptmalloc在整理內存時需要對分配區(qū)進行加鎖操作。當線程需要使用malloc分配內存時，它首先檢查自己的私有變量中是否已經有一個分配區(qū)。如果有，它會嘗試對其進行加鎖操作，如果成功，就使用該分配區(qū)分配內存。如果失敗，它會遍歷循環(huán)鏈表，尋找一個未加鎖的分配區(qū)。如果整個鏈表中都沒有未加鎖的分配區(qū)，那么malloc將創(chuàng)建一個新的分配區(qū)，將其加入全局循環(huán)鏈表并加鎖，然后使用該分配區(qū)進行內存分配。
在釋放內存時，線程會先獲取待釋放內存塊所在分配區(qū)的鎖。如果其他線程正在使用該分配區(qū)，線程必須等待其他線程釋放該分配區(qū)的互斥鎖，然后才能進行釋放內存的操作。這些策略有助于確保內存分配的線程安全性和高效性。
圖片
ptmalloc使用chunk結構體來描述內存塊，其中包含了大小、前后chunk指針、前一個chunk是否在使用中以及前一個chunk的大小等成員信息。這些成員在內存塊的管理和合并操作中起著關鍵作用。
其中，p字段主要用于內存塊的合并操作，具體表示如下：
- 當p=0時，表示前一個chunk為空閑，此時prev_size字段有效；
- 當p=1時，表示前一個chunk正在使用，此時prev_size字段無效。
值得注意的是，ptmalloc分配的第一個塊總是將p設為1，以防止程序引用到不存在的區(qū)域。此外，還有M和A字段，其中M=1表示該內存塊來自mmap映射區(qū)域，而M=0表示來自heap區(qū)域；A=0表示主分配區(qū)分配，A=1表示非主分配區(qū)分配。
圖片
在內存中，空閑的chunk具有如下結構：
- fp和bp分別指向前一個和后一個空閑鏈表上的chunk；
- fp_nextsize和bp_nextsize分別指向前一個空閑chunk和后一個空閑chunk的大小，用于在空閑鏈表上快速查找合適大小的chunk。
這些指針的值都存儲在原始用戶區(qū)域中，這樣就不需要為每個chunk準備單獨的內存存儲指針。
圖片
ptmalloc還維護了多個bin，用于存儲相似大小的chunk，這些bin以雙向鏈表的形式鏈接在一起。總共有128個bin，根據chunk的大小可以分為四種類型：
- Fast bin（小于64B）
- Unsorted bin
- Small bin
- Large bin
這些bin被保存在數組fastbinsY（fast bin）和bins（其他bin）中。當用戶調用malloc時，系統可以快速查找適合用戶需求大小的內存塊是否在這些bin中，并通過雙向鏈表查找合適的chunk內存塊提供給用戶使用。
Fast bins記錄著大小以8字節(jié)遞增的Fast bin鏈表，主要用于存儲較小的內存塊（小于默認的max_fast大小64B），這些chunk一般不會被合并，因此分配速度很快。
Unsorted bin的隊列使用bins數組的第一個bin，相當于small bins和large bins的一個緩沖區(qū)，存放最近釋放的大小大于max_fast 的chunk、合并后的chunk以及切割剩余的chunk等。這個bin沒有尺寸上限，可以快速找到最近釋放的chunk。如果找不到合適大小的chunk，ptmalloc會清空unsorted bin，將其中的chunks按照大小分類放入其他適當的bin中。
Small bin保存大小小于512字節(jié)的chunk，從2開始編號，一共有63個，相鄰的small bin之間相差8字節(jié)。同一個small bin中的chunk具有相同的大小。在釋放一個chunk時，會檢查其前后的chunk是否為空閑，如果是，則將它們合并成一個新的chunk，然后將新chunk添加到unsorted bin的前端。
Large bin保存大小大于等于512字節(jié)的chunk，位于small bin之后。每個bin包含了一個給定范圍內的chunk，這些chunk按大小遞減排序。在分配chunk時，會尋找大小最合適的chunk，并進行切割，剩余部分放入unsorted bin。釋放操作類似于small bin，如果條件滿足，將會進行合并。
除了以上類型的chunk，還有mmaped chunk和top chunk：
mmaped chunk用于分配非常大的內存塊（大于默認的分配閾值，通常為128K）。在釋放mmaped chunk上的內存時，會直接返回給操作系統。
top chunk相當于分配區(qū)的頂部空閑內存，當bins上無法滿足內存分配要求且小于mmap分配閾值時，就會使用top chunk來分配。如果top chunk的大小比用戶請求的大小大，會將其切割為兩部分：User chunk（用戶請求大?。┖蚏emainder chunk（剩余大?。?。其中Remainder chunk成為新的top chunk。當top chunk大小小于用戶所請求的大小時，top chunk就通過sbrk（主分配區(qū)）或mmap（非主分配區(qū)）系統調用來擴容。
last remainder是一種特殊的chunk，類似于top chunk和mmaped chunk，它不會出現在任何bins中。當需要分配一個small chunk，但在small bins中找不到合適的chunk，如果last remainder chunk的大小大于所需的small chunk大小，last remainder chunk被分裂成兩個chunk，其中一個chunk返回給用戶，另一個chunk變成新的last remainder chuk。
3.2 內存分配
ptmalloc的內存申請過程其實是：獲取arena并加鎖–> fast bin –> unsorted bin –> small bin –> large bin –> top chunk –> 擴展堆的過程，詳細流程如下：
- 獲取分配區(qū)（arena）的鎖，以確保多線程環(huán)境下的內存分配操作不會發(fā)生沖突；
- 計算出需要分配的chunk的實際大??；
- 首先檢查chunk的大小是否小于max_fast（默認64字節(jié)），如果是，則嘗試從fast bins中獲取適合的chunk，如果找到則分配結束。否則，繼續(xù)下一步；
- 如果chunk的大小小于512字節(jié)，嘗試從small bins中獲取合適的chunk，如果找到則分配結束。否則，繼續(xù)下一步；
- 如果以上步驟都未成功，會首先遍歷fast bins中的chunk，將相鄰的chunk合并，并鏈接到unsorted bin中，然后遍歷unsorted bins。如果unsorted bins中只有一個chunk且大小大于待分配的chunk，則將其切分，并將剩余的部分繼續(xù)放入unsorted bins；如果unsorted bins中有大小適合的chunk，則分配結束。否則，繼續(xù)下一步；
- 如果以上步驟都未成功，在large bins中查找合適的chunk，進行切割，并將剩余部分放回unsorted bin。如果fast bins和bins都沒有找到合適的chunk，那么就需要操作top chunk來進行分配了。如果top chunk的大小比用戶所請求的大小還大，則將top chunk切分為兩部分：User chunk（用戶請求大?。┖蚏emainder chunk（剩余大小），并將剩余塊作為新的top chunk。如果top chunk的大小小于用戶所請求的大小，根據分配區(qū)的類型（主分配區(qū)或非主分配區(qū)），通過sbrk（主分配區(qū)）或mmap（非主分配區(qū)）系統調用來擴展top chunk的大?。?/li>
- 如果以上步驟都未成功，根據需要的chunk大小，選擇調用sbrk（主分配區(qū)）或mmap（非主分配區(qū)）系統調用來分配內存塊；
- 使用mmap系統調用為程序的內存空間映射一塊大小為chunk_size、對齊到4KB的內存空間，并將內存指針返回給用戶；
- 判斷是否為第一次調用malloc，如果是主分配區(qū)，則需要進行初始化工作，分配一塊初始大小為（chunk_size + 128KB）、對齊到4KB的空間作為初始的heap。如果已經初始化過了，主分配區(qū)則調用sbrk（主分配區(qū)）來增加heap的大小，非主分配區(qū)則在top chunk中切割出一個chunk以滿足分配需求。
3.3 回收過程
內存回收流程概述如下：
- 首先，獲取分配區(qū)的鎖，以確保線程安全性；
- 如果要釋放的是空指針，則無需執(zhí)行任何操作，直接返回；
- 檢查當前的內存塊（chunk）是否是通過mmap映射的內存區(qū)域。如果是的話，直接通過munmap()函數將該chunk釋放。我們可以通過已使用chunk的數據結構中的"M"標志來判斷是否是mmap映射的內存；
- 判斷chunk是否與頂部內存塊（top chunk）相鄰。如果相鄰，將它們合并在一起（相鄰意味著與分配區(qū)中的空閑chunk相鄰）。然后，繼續(xù)下一步驟；
- 如果chunk的大小大于max_fast（64字節(jié)），將其放入未排序的bin中，并檢查是否需要合并。如果需要合并且與top chunk相鄰，進入下一步驟；
- 如果內存塊的大小小于max_fast（64字節(jié)），直接放入快速bin中，而不改變chunk的狀態(tài)。然后，檢查是否需要合并，如果需要合并，繼續(xù)下一步驟；
- 在快速bin中，如果當前chunk的下一個chunk也是空閑的，將它們合并，并將合并后的chunk放回未排序的bin中。如果合并后的chunk大小大于64字節(jié)，將觸發(fā)快速bin的合并操作，將與相鄰的空閑chunk合并后，放回未排序的bin中。如果合并后的chunk與top chunk相鄰，將它們合并到top chunk中；
- 最后，檢查top chunk的大小是否大于mmap的收縮閾值（默認為128KB）。如果是，嘗試將部分top chunk歸還給操作系統，然后結束內存釋放操作。
3.4 部分參數解析
MALLOC_ARENA_MAX(線程內存池的最大數量)：通過將MALLOC_ARENA_MAX設置為較小的值，可以減少arena的數量，從而降低內存碎片的可能性。然而，這可能會導致高并發(fā)環(huán)境中的鎖爭用問題，從而對性能產生負面影響。因此，需要在性能和內存利用之間找到一個平衡點。
此外，ptmalloc2默認會根據內存需求的動態(tài)情況來調整mmap分配的閾值，以便更有效地利用內存緩沖池設置,但是設置M_TRIM_THRESHOLD，M_MMAP_THRESHOLD，M_TOP_PAD 和 M_MMAP_MAX 中的任意一個就可以固定分配閾值為128K，這樣超過128K的內存分配請求都不會進入ptmalloc的buffer池而是直接走mmap分配和munmap回收（性能上會有損耗）。
3.5 特性分析
- ptmalloc2使用了多arena 來分配內存，雖然增加了內存碎片，但卻提升了內存分配效率；
- 后分配的內存先釋放，因為 ptmalloc 收縮內存是從 top chunk 開始,如果與 top chunk 相鄰的 chunk 不能釋放, top chunk 以下的 chunk 都無法釋放；
- 多線程鎖開銷大，需要避免多線程頻繁分配釋放；
- 內存從thread的areana中分配， 內存不能從一個arena移動到另一個arena， 就是說如果多線程使用內存不均衡，容易導致內存的浪費。比如說線程1使用了300M內存，完成任務后glibc沒有釋放給操作系統，線程2開始創(chuàng)建了一個新的arena， 但是線程1的300M卻不能用了；
- 每個chunk至少8字節(jié)的開銷很大；
- 不定期分配長生命周期的內存容易造成內存碎片，不利于回收。64位系統最好分配32M以上內存，這是使用mmap的閾值。
4 tcmalloc
TCMalloc 全稱 Thread-Caching Malloc，即線程緩存的 malloc，是 Google 開發(fā)的內存分配器，在不少項目中都有使用，目前已經在chrome、safari等知名軟件中運用。
4.1 整體架構
tcmalloc的架構大體分為三個部分：
- Front-end用來為應用提供快速分配以及釋放內存的需求?？梢愿鶕档呐渲谜{整為Per-cpu mode 和 per-thread mode兩種模式，后面會細講；
- Middle-end 由 CentralFreeList 和 TransferCache 兩部分組成，負責重新填充Front-end的Cache，并將空閑內存返回給 back-end；
- back-end 負責管理從操作系統獲取的內存，支持大內存和小內存的pageheap 管理。
下面將對內存組織形式和三個核心組成部分進行詳細講解，并說明在內存的分配和釋放過程中各個部分的機制。
4.1.1 Pagemap 和 Spans
tcmalloc 管理的堆內存會在編譯期間確定一個page-size，并將這么多內存映射為對應size的一個個page。一系列正在被使用的pages 可以被一個span 對象描述，一個span 對象可以管理一個大的內存對象，也可以按照size-class 管理多個小對象。
pagemap 則是用來查找一個內存對象屬于哪一個span的，或者申請一個指定size-class 的內存對象，pagemap 根據32位還是64位是一個 2層或者3層的 radix-tree。下圖展示了一個兩層的 page-map 如何管理 span的，其中 span A 管理了2個page，span B 管理了三個page。
圖片
Span 這個數據結構在middle-end中用來管理回收的內存對象，在back-end 用來管理 對應大小的pages，負責給central-list 提供對應大小的span。
4.1.2 Front-end
Front-end 提供了Cache，能夠緩存一部分內存用來分配給應用 ，也能夠持有應用釋放的內存。其同一時刻只能由一個線程訪問，所以本身不需要任何的鎖，這也是多線程下內存分配釋放高效的原因。如果Front-end 持有的內存大小足夠，其能夠滿足應用線程任何內存需求。如果持有的內存為空了，那它會從 middle-end 組件請求一批內存頁進行填充。如果用戶請求的內存大小超過了front-end 本身能緩存的大小（大內存需求），或者middle-end 緩存的內存頁也被用盡了，那這個時候會直接讓從back-end分配內存給用戶。
針對小內存對象的分配，Front-end的cache 會按照其大小將其映射到 60-80個size-classes（size-class是front-end 分配內存的粒度）中的一個，實際的內存分配會按照該大小對應的size-class 的大小進行分配。比如12B 的對象會best-fit到16B 的size-class中。設置這么多的size-class 是為了盡可能得降低內存的浪費，比如原本的內存分配粒度都是2的n次冪，那對于23字節(jié)的內存需求就需要分配一個32字節(jié)的內存區(qū)域，而在tcmalloc的size-class的配置中只需要分配24字節(jié)即可。
對于大內存需求的對象來說，內存大小的需求超過256K，則會直接從back-end 分配。因此，這一部分的內存需求不會緩存再 front-end 以及 middle-end 中，由back-end的page-heap 進行管理。對于大內存對象的實際內存分配會按照tcmalloc page size 進行對齊。
如果要釋放一個對象，編譯期間如果能夠知道這個對象的大小，編譯器會直接告訴分配器這個對象的大小。大多數的時候，編譯期間并不清楚對象的大小，會從pagemap中查找這個對象。如果這個對象是一個小內存對象，釋放的時候會告訴front-end cache進行管理，如果是一個超過kMaxSize 的對象，則會直接釋放給back-end 的 pageheap。
4.1.3 Middle-end
Middle-end 的主要作用為 font-end 提供內存申請需求，并將空閑內存返回給 back-end。Middle-end 對于每一個size-class，都會有有一個各自的 transfer cache 和 central free list。這一些caches 會有自己的互斥鎖，所以對于這一些cache的訪問， 因為鎖粒度較低，則不會有過多的沖突，保證了訪問的性能。
當 front-end 請求內存或者釋放內存的時候，會先到達transfer cache。Transfer cache 會持有 一個數組指針進行內存的釋放或者將新的內存對象填充進來并返回給font-end。Transfer cache會將一個cpu/thread 釋放的內存分配給另一個cpu/thread 對內存的需求，這個類似于內存池的內存對象流動在兩個不同的cpu/threads 之間可以非常迅速。
central free list通過 span 數據結構來管理內存，一個span可以管理一個或者多個tcmalloc page。Font-end如果從central free list請求一個或者多個內存對象的時候，central free list會從span中提取對應大小的對象，如果此時span 沒有足夠的pages返回，則會從back-end 請求更多的span。
當內存對象返回給central free list，則這一些對象會通過 pagemap 被映射到對應的span中進行管理，如果所有的對象都返回給span，這個span就可以被釋放給back-end。
4.1.4 Back-end
tcmalloc的back-end 主要有三個工作線程，分別負責管理未使用的大塊內存區(qū)域，負責從 os 中獲取內存，來滿足其他組件的內存需求以及負責將其他組件不需要返回的內存，還給os。還有兩個后端組件：Legacy page heap和Huge page heap，分別負責管理tcmalloc 的pages和管理大頁內存的 pageheap。Huge page heap可以用來提升應用程序大頁內存的申請需求，提升頁表緩存的命中率。
圖片
legacy pageheap是一個數組的freelist，統一管理可用內存頁。數組的每一個節(jié)點是一個free list，也就是單鏈表。一般這個數組的大小 k < 256，對于第k 個數組元素來說，它的鏈表中的每一個節(jié)點都管理了 k 個pages。
如果想要申請 k 個pages，則直接查找這個數組的第k 個元素，從free list中取一個節(jié)點即可。如果這個free list是空的，那就查找下一個數組元素的free list,直到找到一個非空的free list。如果還是失敗，則直接mmap 獲取內存。
當一段連續(xù)的pages 被返回給了pageheap，則會根據當前pages 是否能夠形成一個連續(xù)的pages區(qū)域，然后串聯這一些pages 并根據page數量 添加到對應的free list中。
針對大頁場景，Huge page heap能夠有效持有 hugepage 大小的內存塊，需要的時候能夠快速分配，不需要的時候也能在合理的內存占用情況下釋放給操作系統。
tcmalloc的back-end 擁有三個不同的cache 來管理大頁內存的分配：
- filler cache：能夠持有hugepage ，并提供一些大頁內存的申請需求。類似于legacy pageheap，通過一些free lists 管理pages 那樣管理huge page，主要用于處理小于hugepage 大小的內存申請；
- region cache：用于大于hugepage 大小的內存申請，這個cache 允許分配多個連續(xù)的hugepage；
- hugepage cache：和region cache的功能有點重復，也是用于分配大于hugepage 的內存申請。
4.2 Per-thread mode
per-thread的cache模式是TCMalloc 名字 Thread-Cacheing malloc的由來。小內存的申請和釋放會根據thread-cache的需求在middle-end 之間遷移。
每一個 thread-cache 內部不同size-class 對象會各自構造一個單鏈表（如果有 n 個size-classes，也就會有對應 n 個單鏈表），類似如下圖：
圖片
分配某一個對應size-class 對象的時候，對應 size-class 鏈表對象會被從單鏈表移除（free-list），表示這個指針對應地址的內存可以被用戶使用。釋放對象的時候，則會將這個對象地址追加到thread-cache 管理的 size-class 的鏈表。在這個過程中，如果thread-cache 管理的內存不夠，或者超限，則會從 middle-end 獲取更多的內存對象或者將多余的內存對象釋放給 middle-end。
對于per-thread caches來說，可以通過參數設置最大的可用內存大小。每一個線程有自己的最小的thread-cache大小 512K，如果當前線程內存申請需求較大，內存容量也會通過middle-end 將其他線程的可用內存遷移到當前線程。通過 middle-end 來協調當前的thread-cache 內存，通過ThreadCache::Scavenge()進行。如果當前線程退出，則會將自己的thread-cache 的內存返回給 middle-end。
Per-thread 模式下，cache 內部的最大存儲對象容量 達到當前最大閾值時就會從middle-end 獲取更多的對象，從而增大這個限制。降低最大限制的前提是發(fā)現了較多的未被使用的對象，則會將這一些對象根據需求還給middle-end。
4.3 Per-CPU mode
然而這種場景會隨著用戶線程的大量增加，出現了一些內存問題：每個線程只能有極小的thread-cache，需要消耗較多的CPU資源來聚合每個線程的內存資源。新的per-CPU 模式應運而生，這種模式下每一個邏輯CPU 會有自己的的thread-cache 用來為運行在這個cpu的現場分配內存。
Per-cpu mode和per-thread mode是tcmalloc的font-end 主體部分的兩種模式。因為per-thread mode受到系統進程的線程數的影響，在大量線程的情況下會讓每個thread-cache 只能夠處理一小部分的內存申請釋放需求，還會消耗大量的cpu 來 由middle-end 進行不同thread-cache 之間的內存遷移。
所以 tcmalloc 提供了優(yōu)化版本的 per-cpu mode，即每一個邏輯核維護一個 cpu-cache，用來處理運行在當前核的線程的內存申請/釋放需求，大體形態(tài)如下：
圖片
Per-cpu mode下會申請一個大內存塊（也可以稱為slab），這個slab 會被多個cpu共享，其中每一個cpu會持有slab 的一部分內存，并在其上存儲一系列元數據管理對應線程的內存對象。
上圖中的cpu1會管理 on slab 的綠色部分內存區(qū)域，在這一部分區(qū)域中會先存儲一些元數據和指針來管理不同大小的 size-classes 的內存對象。其中元數據中包含一個header指針和每一個size-class 的索引block。
每一個size-class 的header 指針數據結構會有指向某一種實際存儲內存對象的指針數組，即是一個數組，每一個元素是一個指針，總共是三個指針，分別指向這一種size-class 內存對象區(qū)域的起始地址塊，當前地址塊（后續(xù)分配這個size-class 大小對象的時候會從current 開始分配），最大地址。
每一個cpu 能夠緩存的內存大小是通過SetMaxPerCpuCacheSize 配置的，也就是設置當前font-end 能夠緩存的內存總大小取決去當前系統的cpu核心數，擁有更好核心數的機器使用tcmalloc 能夠緩存更多的內存。當每一個cpu cache 的內存被分配耗盡，想要從 middle-end 獲取內存來緩存更多的對象時，也需要考慮對size-class進行擴容。如果這個size-class 的內存分配需求還在持續(xù)增加，則這個size-class的容量會持續(xù)增加，直到達到這個size-class 容量的hard-code。
Per-cpu 模式下，增加cache 容量的前提是當前cache 是否在頻繁的從 middle-end 獲取內存 以及 釋放內存交替，則需增加容量限制，有更多的空間來緩存這一些內存對象。降低容量限制的前提是發(fā)現有一些空閑容量長時間沒有被使用。
4.4 部分參數解析
部分主流的tcmalloc配置參數有:
- TCMALLOC_MAX_TOTAL_THREAD_CACHE_BYTES: 限制每個線程本地緩存的最大總大??；
- TCMALLOC_LARGE_ALLOC_REPORT_THRESHOLD: 內存最大分配閾值；
- TCMALLOC_SAMPLE_PARAMETER : 采樣時間間隔；
- TCMALLOC_RELEASE_RATE：用于控制tcmalloc內部的內存回收速率。
4.5 特性分析
- 高性能：TCMalloc在內存分配和釋放過程中，大多數情況下都能夠避免產生過多的競爭。這是因為它維護了線程本地緩存（thread-cache），以滿足當前線程的內存分配需求。這意味著在許多情況下，應用程序的內存申請不會涉及到鎖的競爭，尤其是在多核處理器的環(huán)境下，TCMalloc表現出色，并具有良好的可擴展性；
- 智能內存資源管理：TCMalloc能夠靈活地管理內存資源，當用戶不再需要內存時，TCMalloc會智能地選擇是重新利用這些內存還是將其歸還給操作系統，以便更有效地利用系統資源；
- 降低內存開銷：通過以頁面（page）為單位進行內存分配，TCMalloc降低了每個請求的內存開銷。這種優(yōu)化在處理小對象時特別有效，有效地減少了內存浪費；
- 低開銷的內部信息統計：TCMalloc具有低開銷的內存使用信息統計功能，可以以細粒度的方式跟蹤應用程序的內存占用情況。這有助于用戶更詳細地了解TCMalloc內部的內存使用情況，從而更好地進行性能調優(yōu)和資源管理。
5 實踐
5.1 背景
當前轉轉的服務中，很多都存在堆外內存較高的現象。以轉轉搜索排序服務為例，目前線上服務jvm堆內存上限為18G，服務內無堆外的特征緩存等數據，堆外內存的大小超出預期，很多物理機的內存已經開始告急，初步判斷原因為相關的服務中用到了tensorflow進行推斷，linux默認使用的glibc的malloc實現在內存池資源回收上存在缺陷，導致申請過的內存無法還給操作系統，上文的梳理和特性分析體現出主流的兩種非原生malloc：tcmalloc和jemalloc都可能會改善這一狀況，因此下面對三種不同的malloc進行實踐分析。
5.2 準備工作
1.安裝jemalloc和tcmalloc：
- tcmalloc：需要提前安裝libunwind和gperftools（自帶tcmalloc）并配置環(huán)境變量生效，下文中的實驗采用的是gperftools2.10和centos7；
- jemalloc：下載最新版本的jemalloc，編譯安裝并配置環(huán)境變量即可，下文中的實驗采用的是jemalloc5版本。
2.在服務啟動時，終端設置export LD_PRELOAD={對應malloc.so文件的路徑}和export MALLOC_CONF={指定的malloc參數}后，重新終端啟動服務即可生效。其中jemalloc經過多次嘗試，選擇了利用MALLOC_CONF配置參數：background_thread:true，metadata_thp:auto，dirty_decay_ms:30000，muzzy_decay_ms:30000來獲得最佳的表現（其含義見下表），而tcmalloc和ptmalloc經過測試，默認的參數表現最佳，3個malloc的最佳參數的測試過程同樣是采用壓測+線上對比來進行的，較為繁瑣所以不再贅述。
參數 | 含義 |
narenas | 默認為ncpus的四倍，用于設置線程獨占的 arena數量。 |
dirty_decay_ms與muzzy_decay_ms | 控制內存頁的過期時間。jemalloc使用一種延遲回收策略，根據指定的時間段將內存頁從"dirty"狀態(tài)（已經寫入）轉換為"muzzy"狀態(tài)（未寫入），然后再回收 |
background_thread | 啟用后臺線程。jemalloc支持后臺線程來定期處理內存釋放操作，這可以降低內存碎片并提高性能。啟用此參數后，jemalloc將自動創(chuàng)建和管理后臺線程。 |
tcache | 禁用tcache（thread-local cache）。tcache是jemalloc的一項特性，用于線程本地的內存分配緩存。通過禁用它，您可以在一定程度上減少jemalloc的線程局部性，適用于高并發(fā)場景或者特定需求下。 |
percpu_arena | 啟用每個CPU核心的獨立內存池。這可以提高多核系統中的內存分配性能，減少了多核之間的鎖競爭。 |
5.3 壓測表現
在隔離環(huán)境進行服務壓測，分別對存在較高內存占用的轉轉搜索排序服務更換3種malloc進行10分鐘的多線程壓測，分析耗時和內存占用表現。下圖從左至右分別是原生malloc tcmalloc jemalloc 壓測過程中的內存表現：
圖片
下圖從左至右分別是原生malloc tcmalloc jemalloc 壓測過程中的耗時表現：
圖片
根據實踐結果可以得出分別使用三種malloc在此服務上進行等條件壓測，壓測過后常駐內存增加了2.51g，而tcmalloc和jemalloc都只增加了0.5g左右，回顧ptmalloc2的內存分配和回收機制，有多種原因單一或者同時導致了這一現狀：
- 由于原生的ptmalloc2自身的內存釋放機制的不足，如果多線程使用內存不均衡，容易導致內存的浪費。比如說線程1使用了300M內存，完成任務后glibc沒有釋放給操作系統，線程2開始創(chuàng)建了一個新的arena，但是線程1的300M卻不能使用；
- 與此同時，每個chunk至少需要8字節(jié)的開銷；
- top chunk的釋放機制收縮內存是從 top chunk 開始，如果與 top chunk 相鄰的 chunk 不能釋放, top chunk 以下的 chunk 都無法釋放。
與此同時，在服務初始化完成后，tcmalloc也擁有更好的內存占用表現，可能的原因有：
- 由于tcmalloc相比jemalloc還需要少一些額外的內存開銷；
- ThreadCache會階段性的回收內存到CentralCache里來進行分發(fā)，在初始化階段線程較少時占用的內存會更低。
而在耗時分析中，tcmalloc小幅優(yōu)于ptmalloc和jemalloc但是差距不大，而tcmalloc表現最優(yōu)可能和線程局部緩存在并發(fā)的環(huán)境下，因為每個線程可以獨立地管理自己的內存分配，所以減少了線程之間的競爭，jemalloc在耗時方面表現不佳可能的原因是沒有找到更合適的參數，還需要進一步的分析和實踐。
5.4 線上表現
在線上環(huán)境進行對照實驗，分別對兩臺內存和cpu占用率一致的物理機上的轉轉搜索排序服務同時進行重啟，綠色的是更換tcmalloc的，而黃色的是原生的ptmalloc2，下圖可以觀察到服務啟動后接入真實流量后內存的變化：
圖片
采用原生malloc的物理機上的服務，在初始化完成就占用了較多的內存，同時隨著處理請求的過程，內存發(fā)生了較大的增長，而采用tcmalloc的物理機上的服務，則在初始化完成時就有更好的內存占用表現，在后續(xù)的處理請求的過程內存占用的增量較低，且出現了明顯的內存釋放過程。
5.5 實踐結果
在上述的實踐后，將tcmalloc部署至至搜索推薦的所有服務，平均每臺機器得到了10g以上的內存減少量，經過上文壓測和線上的實踐得出,選擇合理的malloc及其參數對服務的耗時和內存占用表現有著很高的影響，耗時情況也保持整體持平。
6 總結
本文主要是結合各類資料梳理了三種linux下常用的malloc:ptmalloc，tcmalloc的整體架構，以及對jemalloc的參數講解，概念簡介，內存分配和回收過程，并給出常用的參數的解析說明以及特性分析，限于篇幅，只對jemalloc進行了參數講解，并分享了上述malloc在轉轉的搜索排序主服務上的實踐經驗，最終降低了大量的服務器內存占用，獲得了不錯的收益，這表明了我們應該根據服務的場景，不只考慮于jvm的參數調整，還應該選擇適當的malloc并調整參數來達到性能和內存占用的平衡，不斷在技術上精進自己，追求卓越。
7 參考文獻
- https://zhuanlan.zhihu.com/p/613696274 Linux mmap內存映射；
- https://zhuanlan.zhihu.com/p/649511901 Linux內存分配之brk與mmap；
- https://zhuanlan.zhihu.com/p/645312749 Linux內存管理（三）--內存分配之malloc；
- https://zhuanlan.zhihu.com/p/448293503 malloc的底層實現（ptmalloc）；
- https://zhuanlan.zhihu.com/p/537042335 ptmalloc2 源碼剖析2 -- 設計哲學;
- https://google.github.io/tcmalloc/design.html；
- https://zhuanlan.zhihu.com/p/653320304 內存分配器：TCMalloc 基本設計原理詳解；
- https://developer.aliyun.com/article/6045 tcmalloc淺析；
- https://zhuanlan.zhihu.com/p/642471269 內存管理特性分析（十五）:內存分配器之jemalloc技術原理分析。
關于作者
劉子涵，轉轉搜索推薦基礎建設研發(fā)工程師
