記憶體優化總結:ptmalloc、tcmalloc和jemalloc

轉載于：http://www.cnhalo.net/2016/06/13/memory-optimize/

概述

需求

系統的實體記憶體是有限的，而對記憶體的需求是變化的, 程式的動态性越強，記憶體管理就越重要，選擇合适的記憶體管理算法會帶來明顯的性能提升。

比如nginx， 它在每個連接配接accept後會malloc一塊記憶體，作為整個連接配接生命周期内的記憶體池。 當HTTP請求到達的時候，又會malloc一塊目前請求階段的記憶體池, 是以對malloc的配置設定速度有一定的依賴關系。(而apache的記憶體池是有父子關系的，請求階段的記憶體池會和連接配接階段的使用相同的配置設定器，如果連接配接記憶體池釋放則請求階段的子記憶體池也會自動釋放)。

目标

記憶體管理可以分為三個層次，自底向上分别是：

• 作業系統核心的記憶體管理
• glibc層使用系統調用維護的記憶體管理算法

• 應用程式從glibc動态配置設定記憶體後，根據應用程式本身的程式特性進行優化， 比如使用引用計數std::shared_ptr，apache的記憶體池方式等等。

  當然應用程式也可以直接使用系統調用從核心配置設定記憶體，自己根據程式特性來維護記憶體，但是會大大增加開發成本。

本文主要介紹了glibc malloc的實作，及其替代品

一個優秀的通用記憶體配置設定器應具有以下特性:

• 額外的空間損耗盡量少
• 配置設定速度盡可能快
• 盡量避免記憶體碎片
• 快取區域化友好
• 通用性，相容性，可移植性，易調試

現狀

目前大部分服務端程式使用glibc提供的malloc/free系列函數，而glibc使用的ptmalloc2在性能上遠遠弱後于google的tcmalloc和facebook的jemalloc。 而且後兩者隻需要使用LD_PRELOAD環境變量啟動程式即可，甚至并不需要重新編譯。

glibc ptmalloc2

ptmalloc2即是我們目前使用的glibc malloc版本。

ptmalloc原理

系統調用接口

上圖是 x86_64 下 Linux 程序的預設位址空間, 對 heap 的操作, 作業系統提供了brk()系統調用，設定了Heap的上邊界； 對 mmap 映射區域的操作,操作系 統 供了 mmap()和 munmap()函數。

因為系統調用的代價很高，不可能每次申請記憶體都從核心配置設定空間，尤其是對于小記憶體配置設定。 而且因為mmap的區域容易被munmap釋放，是以一般大記憶體采用mmap()，小記憶體使用brk()。

多線程支援

• Ptmalloc2有一個主配置設定區(main arena)， 有多個非主配置設定區。 非主配置設定區隻能使用mmap向作業系統批發申請HEAP_MAX_SIZE（64位系統為64MB）大小的虛拟記憶體。 當某個線程調用malloc的時候，會先檢視線程私有變量中是否已經存在一個配置設定區，如果存在則嘗試加鎖，如果加鎖失敗則周遊arena連結清單試圖擷取一個沒加鎖的arena， 如果依然擷取不到則建立一個新的非主配置設定區。
• free()的時候也要擷取鎖。配置設定小塊記憶體容易産生碎片，ptmalloc在整理合并的時候也要對arena做加鎖操作。線上程多的時候，鎖的開銷就會增大。

ptmalloc記憶體管理

• 使用者請求配置設定的記憶體在ptmalloc中使用chunk表示， 每個chunk至少需要8個位元組額外的開銷。 使用者free掉的記憶體不會馬上歸還作業系統，ptmalloc會統一管理heap和mmap區域的空閑chunk，避免了頻繁的系統調用。
• ptmalloc 将相似大小的 chunk 用雙向連結清單連結起來, 這樣的一個連結清單被稱為一個 bin。Ptmalloc 一共 維護了 128 個 bin,并使用一個數組來存儲這些 bin(如下圖所示)。

  

  數組中的第一個為 unsorted bin, 數組中從 2 開始編号的前 64 個 bin 稱為 small bins, 同一個small bin中的chunk具有相同的大小。small bins後面的bin被稱作large bins。
• 當free一個chunk并放入bin的時候， ptmalloc 還會檢查它前後的 chunk 是否也是空閑的, 如果是的話,ptmalloc會首先把它們合并為一個大的 chunk, 然後将合并後的 chunk 放到 unstored bin 中。 另外ptmalloc 為了提高配置設定的速度,會把一些小的(不大于64B) chunk先放到一個叫做 fast bins 的容器内。
• 在fast bins和bins都不能滿足需求後，ptmalloc會設法在一個叫做top chunk的空間配置設定記憶體。 對于非主配置設定區會預先通過mmap配置設定一大塊記憶體作為top chunk， 當bins和fast bins都不能滿足配置設定需要的時候, ptmalloc會設法在top chunk中分出一塊記憶體給使用者, 如果top chunk本身不夠大, 配置設定程式會重新mmap配置設定一塊記憶體chunk, 并将 top chunk 遷移到新的chunk上，并用單連結清單連結起來。如果free()的chunk恰好 與 top chunk 相鄰,那麼這兩個 chunk 就會合并成新的 top chunk，如果top chunk大小大于某個門檻值才還給作業系統。主配置設定區類似，不過通過sbrk()配置設定和調整top chunk的大小，隻有heap頂部連續記憶體空閑超過門檻值的時候才能回收記憶體。
• 需要配置設定的 chunk 足夠大,而且 fast bins 和 bins 都不能滿足要求,甚至 top chunk 本身也不能滿足配置設定需求時,ptmalloc 會使用 mmap 來直接使用記憶體映射來将頁映射到程序空間。

ptmalloc配置設定流程

ptmalloc的缺陷

• 後配置設定的記憶體先釋放,因為 ptmalloc 收縮記憶體是從 top chunk 開始,如果與 top chunk 相鄰的 chunk 不能釋放, top chunk 以下的 chunk 都無法釋放。
• 多線程鎖開銷大， 需要避免多線程頻繁配置設定釋放。
• 記憶體從thread的areana中配置設定， 記憶體不能從一個arena移動到另一個arena， 就是說如果多線程使用記憶體不均衡，容易導緻記憶體的浪費。 比如說線程1使用了300M記憶體，完成任務後glibc沒有釋放給作業系統，線程2開始建立了一個新的arena， 但是線程1的300M卻不能用了。
• 每個chunk至少8位元組的開銷很大
• 不定期配置設定長生命周期的記憶體容易造成記憶體碎片，不利于回收。 64位系統最好配置設定32M以上記憶體，這是使用mmap的門檻值。

tcmalloc

tcmalloc是Google開源的一個記憶體管理庫， 作為glibc malloc的替代品。目前已經在chrome、safari等知名軟體中運用。

根據官方測試報告，ptmalloc在一台2.8GHz的P4機器上（對于小對象）執行一次malloc及free大約需要300納秒。而TCMalloc的版本同樣的操作大約隻需要50納秒。

小對象配置設定

• tcmalloc為每個線程配置設定了一個線程本地ThreadCache，小記憶體從ThreadCache配置設定，此外還有個中央堆（CentralCache），ThreadCache不夠用的時候，會從CentralCache中擷取空間放到ThreadCache中。
• 小對象（<=32K）從ThreadCache配置設定，大對象從CentralCache配置設定。大對象配置設定的空間都是4k頁面對齊的，多個pages也能切割成多個小對象劃分到ThreadCache中。

  

  小對象有将近170個不同的大小分類(class)，每個class有個該大小記憶體塊的FreeList單連結清單，配置設定的時候先找到best fit的class，然後無鎖的擷取該連結清單首元素傳回。如果連結清單中無空間了，則到CentralCache中劃分幾個頁面并切割成該class的大小，放傳入連結表中。

CentralCache配置設定管理

• 大對象(>32K)先4k對齊後，從CentralCache中配置設定。 CentralCache維護的PageHeap如下圖所示， 數組中第256個元素是所有大于255個頁面都挂到該連結清單中。

  

• 當best fit的頁面連結清單中沒有空閑空間時，則一直往更大的頁面空間則，如果所有256個連結清單周遊後依然沒有成功配置設定。 則使用sbrk, mmap, /dev/mem從系統中配置設定。

• tcmalloc PageHeap管理的連續的頁面被稱為span.

  如果span未配置設定， 則span是PageHeap中的一個連結清單元素

  如果span已經配置設定，它可能是傳回給應用程式的大對象， 或者已經被切割成多小對象，該小對象的size-class會被記錄在span中

• 在32位系統中，使用一個中央數組(central array)映射了頁面和span對應關系， 數組索引号是頁面号，數組元素是頁面所在的span。 在64位系統中，使用一個3-level radix tree記錄了該映射關系。

回收

• 當一個object free的時候，會根據位址對齊計算所在的頁面号，然後通過central array找到對應的span。
• 如果是小對象，span會告訴我們他的size class，然後把該對象插入目前線程的ThreadCache中。如果此時ThreadCache超過一個預算的值（預設2MB），則會使用垃圾回收機制把未使用的object從ThreadCache移動到CentralCache的central free lists中。
• 如果是大對象，span會告訴我們對象鎖在的頁面号範圍。 假設這個範圍是[p,q]， 先查找頁面p-1和q+1所在的span，如果這些臨近的span也是free的，則合并到[p,q]所在的span， 然後把這個span回收到PageHeap中。
• CentralCache的central free lists類似ThreadCache的FreeList，不過它增加了一級結構，先根據size-class關聯到spans的集合， 然後是對應span的object連結清單。如果span的連結清單中所有object已經free， 則span回收到PageHeap中。

tcmalloc的改進

• ThreadCache會階段性的回收記憶體到CentralCache裡。 解決了ptmalloc2中arena之間不能遷移的問題。
• Tcmalloc占用更少的額外空間。例如，配置設定N個8位元組對象可能要使用大約8N * 1.01位元組的空間。即，多用百分之一的空間。Ptmalloc2使用最少8位元組描述一個chunk。
• 更快。小對象幾乎無鎖， >32KB的對象從CentralCache中配置設定使用自旋鎖。 并且>32KB對象都是頁面對齊配置設定，多線程的時候應盡量避免頻繁配置設定，否則也會造成自旋鎖的競争和頁面對齊造成的浪費。

性能對比

官方測試

測試環境是2.4GHz dual Xeon，開啟超線程，redhat9，glibc-2.3.2, 每個線程測試100萬個操作。

上圖中可以看到尤其是對于小記憶體的配置設定， tcmalloc有非常明顯性能優勢。

上圖可以看到随着線程數的增加，tcmalloc性能上也有明顯的優勢，并且相對平穩。

github mysql優化

github使用tcmalloc後，mysql性能提升30%

Jemalloc

jemalloc是facebook推出的， 最早的時候是freebsd的libc malloc實作。 目前在firefox、facebook伺服器各種元件中大量使用。

jemalloc原理

• 與tcmalloc類似，每個線程同樣在<32KB的時候無鎖使用線程本地cache。

• Jemalloc在64bits系統上使用下面的size-class分類：

  Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]

  Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]

  Huge: [4 MiB, 8 MiB, 12 MiB, …]

• small/large對象查找metadata需要常量時間， huge對象通過全局紅黑樹在對數時間内查找。
• 虛拟記憶體被邏輯上分割成chunks（預設是4MB，1024個4k頁），應用線程通過round-robin算法在第一次malloc的時候配置設定arena， 每個arena都是互相獨立的，維護自己的chunks， chunk切割pages到small/large對象。free()的記憶體總是傳回到所屬的arena中，而不管是哪個線程調用free()。

上圖可以看到每個arena管理的arena chunk結構， 開始的header主要是維護了一個page map（1024個頁面關聯的對象狀态）， header下方就是它的頁面空間。 Small對象被分到一起， metadata資訊存放在起始位置。 large chunk互相獨立，它的metadata資訊存放在chunk header map中。

• 通過arena配置設定的時候需要對arena bin（每個small size-class一個，細粒度）加鎖，或arena本身加鎖。

  并且線程cache對象也會通過垃圾回收指數退讓算法傳回到arena中。

  

jemalloc的優化

• Jmalloc小對象也根據size-class，但是它使用了低位址優先的政策，來降低記憶體碎片化。
• Jemalloc大概需要2%的額外開銷。（tcmalloc 1%， ptmalloc最少8B）
• Jemalloc和tcmalloc類似的線程本地緩存，避免鎖的競争
• 相對未使用的頁面，優先使用dirty page，提升緩存命中。

性能對比

官方測試

上圖是伺服器吞吐量分别用6個malloc實作的對比資料，可以看到tcmalloc和jemalloc最好(facebook在2011年的測試結果，tcmalloc這裡版本較舊)。

4.3.2 mysql優化

測試環境：2x Intel E5/2.2Ghz with 8 real cores per socket，16 real cores， 開啟hyper-threading， 總共32個vcpu。 16個table，每個5M row。

OLTP_RO測試包含5個select查詢：select_ranges, select_order_ranges, select_distinct_ranges, select_sum_ranges,

可以看到在多核心或者多線程的場景下， jemalloc和tcmalloc帶來的tps增加非常明顯。

參考資料

glibc記憶體管理ptmalloc源代碼分析

Inside jemalloc

tcmalloc淺析

tcmalloc官方文檔

Scalable memory allocation using jemalloc

mysql-performance-impact-of-memory-allocators-part-2

ptmalloc,tcmalloc和jemalloc記憶體配置設定政策研究

Tick Tock, malloc Needs a Clock

總結

在多線程環境使用tcmalloc和jemalloc效果非常明顯。

當線程數量固定，不會頻繁建立退出的時候， 可以使用jemalloc；反之使用tcmalloc可能是更好的選擇。