一、內存碎片

內部碎片與外部碎片

內部碎片：指已分配給進程但未被實際利用的內存空間，屬于??已分配內存內部的浪費??。
外部碎片：內存中??零散分布的空閑小空間??，總量足夠但無法合并為大塊以滿足連續內存請求。

內部碎片與外部碎片是矛盾的只能平衡取向：

減少內部碎片：當每次申請內存時，只獲取對應大小內存，可以消除內部碎片，但出現難以重新利用的外部碎片（
除非遇到新程序申請的內存指定100B否則只能等待重新整理內存）

減少外部碎片：分配器對內存大小做統一劃分（2的次方大小），分配時向上取整，對于釋放的內存重新分配可能性大大提高但也會導致內部碎片；

重新規整

外部碎片總量足夠但無法合并為大塊以滿足連續內存請求，所以需要重新規整：

將對難以利用的外部碎片清理；

二、伙伴算法

??適用場景??于操作系統底層頁框管理（Linux 物理內存分配），需要大塊連續內存的硬件交互（如 GPU 緩存、DMA 緩沖區）。
??不適用場景??于用戶態小內存頻繁分配（改用 jemalloc/tcmalloc）

結構：

1. 將物理內存劃分為大小為 2 k （k 從 0 到 n）的塊，例如 4KB、8KB、16KB 等。
2. 每個大小的塊維護一個獨立鏈表（共 n+1 個鏈表），用于管理空閑塊。
3. ??位圖管理??：位圖標記塊狀態。
   

分配過程：

1. ??用戶請求大小為 s 的內存，系統計算最小滿足的 2 k ≥s（如請求 6KB 則分配 8KB）。
2. 若 k 級鏈表有空閑塊，直接分配；否則向更大塊鏈表（如 k+1 級）查找。
3. ??若找到更大塊（如 2 k+1 ），將其??對半分裂??為兩個 2 k 的“伙伴塊”：一個分配，另一個插入 k 級鏈表。

遞歸分裂??：若仍無匹配，繼續向上查找并分裂，直到滿足需求（見圖示）。

釋放與合并??:

1. 釋放內存塊時，檢查其“伙伴塊”（相同大小、物理相鄰、同源分裂）是否空閑。
2. 若伙伴空閑，??合并為更大的 2 k+1 塊??，并遞歸檢查更高階鏈表能否繼續合并。

優勢??

??1. 避免外部碎片??: 通過合并機制，相鄰空閑塊可重組為大塊，減少零散碎片。
2. ??分配效率高??: 鏈表查找與分裂/合并操作復雜度為 O(logN)，適合大塊連續內存分配。
3. 內存連續性保障??: 分配的塊物理連續，滿足 DMA、內核頁表等硬件需求。

缺點??

1. ??內部碎片嚴重?:???請求非 2 k 大小時需向上對齊（如 70KB → 128KB），浪費率可達 50%(例??：請求 66KB 實際分配 128KB，浪費 62KB。)。
2. 合并阻塞問題??: ????小塊阻礙大塊合并??：一個未釋放的小塊會阻止相鄰大塊合并（如 4KB 塊阻礙兩個 64KB 塊合并）。
3. ??管理開銷??: ??頻繁分裂/合并增加 CPU 開銷，尤其小內存場景。

三、Slab

伙伴算法最小只能分配4K，作為應用級別會導致嚴重的內部碎片，Slab核心改進對更小內存的劃分分配；
Slab是Linux內核中用于高效管理??小塊內存對象??的分配器，解決伙伴系統（Buddy System）以頁為單位的粗粒度問題；
伙伴算法最小顆粒度page，Slab8B到2048B，分別針對外部碎片與內部碎片（互補、適合小對象）;

結構

• Cache（緩存池）??：管理同類對象（如task_struct），每個Cache對應固定大小的對象（如64B、128B）。
• ??Slab（內存塊）??：由1個或多個連續物理頁組成，存儲多個相同大小的對象。每個Cache包含三類Slab鏈表：
  – slabs_full：無空閑對象
  – slabs_partial：部分對象已分配
  – slabs_empty：全部對象空閑。
• ??Object（對象）??：Slab內分配的最小單元，大小固定
  

分配過程

1. 匹配Cache：根據請求大小選擇最接近的Cache（如申請30B實際分配32B）。
2. ??優先復用Partial Slab??：從slabs_partial鏈表中分配空閑對象，避免頻繁新建Slab。
3. ??新建Slab??（必要時）：若無可用Partial Slab，則從slabs_empty分配或調用伙伴系統申請新內存頁

釋放與合并

• ??對象釋放??：對象釋放后標記為空閑，返回Slab的空閑鏈表，??不立即歸還操作系統??。
• ??Slab狀態遷移：??
  ?-- ?Full → Partial??：Slab中任一對象釋放后移入slabs_partial鏈表。
  ??-- Partial → Empty??：所有對象釋放后移入slabs_empty鏈表，??可被整體歸還伙伴系統??。
• ??無對象合并機制??：相鄰空閑對象??不會合并??，與伙伴系統相反，避免合并開銷但可能限制大內存分配

優勢

• ??減少碎片??：固定大小對象分配??避免外部碎片??；內部碎片可控（通過合理設計Cache大小）。
• ??極速分配/釋放??：對象復用免去重復初始化，分配復雜度為O(1)。
• ??緩存友好性??：對象連續存儲提升CPU緩存命中率，著色策略進一步優化硬件緩存利用。
• ??降低系統調用??：預分配內存池減少頻繁調用伙伴系統（如alloc_pages）。

缺點

• 多線程性能：雖然并發安全但阻塞申請；
• 內部碎片多：內存塊大小只能是2次方（如65B分配128B，浪費率49%）；
• Cache大小靜態設定，無法動態調整，易導致部分Slab用盡而其他空閑；

三、ptmalloc（glibc malloc實現）

mysql默認內存分配器

參考文檔：https://sourceware.org/glibc/wiki/MallocInternals

前置概念

• arena是ptmalloc管理內存的基本單位，每個arena負責管理一組堆內存（heap）和關聯的空閑內存塊鏈表（bins）。一個arena可被多個線程共享，但同一時刻僅允許一個線程通過加鎖獨占訪問。
• arena的數量上限為系統中 CPU 數量的 8 倍（除非用戶另有指定，請參閱 mallopt），這意味著重線程應用程序仍將看到一些爭用，但權衡是碎片較少。
• 每個 arena 結構中都有一個互斥鎖，用于控制對該 arena 的訪問。請注意，某些作（例如訪問 fastbin）可以通過原子作完成，并且不需要鎖定 arena。所有其他作都要求線程鎖定 arena。
• 每個線程都有一個線程局部變量，該變量會記住它上次使用的 arena。如果該 arena 正在使用中，當線程需要使用它時，線程將阻塞以等待 arena 變為空閑狀態。如果線程之前從未使用過 arena，則它可能會嘗試重用未使用的 arena，創建新的 arena，或在全局列表中選擇下一個 arena。
• chunk??是內存管理的基本單元，用于表示用戶申請或釋放的內存塊。其設計通過元數據管理內存的分配、釋放與合并，同時減少碎片化。
• 請注意，由于 chunk 在內存中彼此相鄰，因此如果您知道堆中第一個 chunk 的地址（最低地址），則可以使用 size 信息遍歷堆中的所有 chunk，但只能通過增加 address，盡管當您命中堆中的最后一個 chunk 時可能很難檢測到。

流程分析

改分配算法復雜，所以從分配的流程分析結構，以下是核心結構：

1. 如果 tcache 中有合適的（僅完全匹配）chunk，則將其返回給調用者。不會嘗試使用Larger bin 中的可用 chunk

每個線程都有一個線程局部變量，該變量會記住它上次使用的 arena。如果該 arena 正在使用中，當線程需要使用它時，線程將阻塞以等待 arena 變為空閑狀態。如果線程之前從未使用過 arena，則它可能會嘗試重用未使用的 arena，創建新的 arena，或在全局列表中選擇下一個 arena。
每個線程都有一個每線程緩存（稱為 tcache），其中包含一小部分塊，無需鎖定 arena 即可訪問這些chunk。這些 chunk 存儲為單鏈表數組，就像 fastbin 一樣，但鏈接指向有效負載（用戶區域）而不是 chunk 頭。每個 bin 包含大小相同的 chunk，因此數組按 chunk size （間接） 索引。與 fastbin 不同，tcache 限制了每個 bin 中允許的 chunk 數量 （tcache_count）。如果 tcache bin 對于給定的請求大小為空，則不會使用下一個更大大小的塊（可能導致內部碎片），而是使用正常的 malloc 例程，即鎖定線程的 arena 并從那里開始工作。

bin : 一組大小、屬性相同的chunk
fastbin :
small chunk存儲在特定于大小的 bin 中。添加到fast bin 的 chunks 不會與相鄰的 chunks 合并 - 邏輯是最小的，以保持快速訪問。fastbin 中的 chunk 可以根據需要移動到其他 bin。fastbin 的chunk存儲在單鏈列表數組中，因為它們的大小都相同，并且列表中間的塊永遠不需要訪問，同時基于CAS樂觀鎖（而非arena中的互斥鎖）了；

2. 如果請求足夠大(閾值可配置)，則使用 mmap（） 直接從作系統請求內存（此類映射有數量限制）。

核心結構中能看到chunk一般屬于某個堆（heap）管理，但是這種場景下創建的chunk是獨立堆內的；

3. fastbin 中有合適的chunk那就優先使用。如果有額外的 chunk 可用，這里可能預填充 tcache

每個 arena 結構中都有一個互斥鎖，用于控制對該 arena 的訪問。但如訪問 fastbin ，可以通過原子操作完成，并且不需要鎖定 arena（所有其他作都要求線程鎖定 arena。對這個互斥鎖的爭用是創建多個 arena 的原因 - 分配給不同 arena 的線程不需要彼此等待。如果爭用需要，線程將自動切換到未使用（解鎖）的 arenas）。

small塊存儲在特定于大小的 bin 中。添加到快速fastbin 的 chunks 不會與相鄰的 chunks 合并 - 邏輯是最小的，以保持快速訪問（因此得名）。fastbin 中的 chunk 可以根據需要移動到其他 bin。fastbin Fastbin 塊存儲在單鏈列表數組中，因為它們的大小都相同，所以鏈表中間的trunk永遠不需要訪問。

4. 如果smallbin 中有合適的 chunk那就用 ，這里也可能預填充 tcache。

空閑的數據塊會根據大小和使用歷史被存儲在不同的列表中，以便庫能夠快速找到合適的數據塊來滿足分配請求：

Fastbin

Small chunk數據被存儲在按大小劃分的特定fast bin中。添加到fastbin中的數據塊不會與相鄰的數據塊合并——這種邏輯非常簡單，目的是為了保持訪問速度（這就是其名稱的由來）。

Unsorted

當內存塊被釋放時，它們最初會存儲在一個單獨的容器中。之后會在“malloc”過程中對其進行排序，以便讓它們有機會被fastbin重新使用。這意味著排序邏輯只需存在于一個地方——其他地方的程序只需將已釋放的內存塊放入這個容器中，之后它們就會被進行排序。而“Unsorted”容器只是常規容器中的第一個。

這里與jemalloc不同的是，ptmalloc中下次分配內存的時候才會對釋放的數據重新整理，但jemalloc用后臺線程實時整理；

Small

正常的存儲單元被分為“Small”單元和“Large”單元。在“Small”單元中，每個塊的大小相同；而在“Large”單元中，chunk的大小則存在一定的范圍。當一個塊被添加到這些單元中時，首先會將其與相鄰的chunk合并，從而將它們合并成更大的chunk。因此，這些chunk永遠不會與其它這樣的chunk相鄰（盡管它們可能與fastbin或unsorted的chunk相鄰，當然也可能與正在使用的chunk相鄰）。Small和Large是雙向鏈接的，這樣就可以從中間移除這些chunk（例如當它們與新釋放的chunk合并時）。

Large

如果一個塊的存儲空間可以容納多種大小的數據，則該塊被視為“較大”的。對于較小的存儲空間塊，您可以選取第一個塊并直接使用它。而對于較大的存儲空間塊，則需要找到“最佳”的塊，并可能將其拆分為兩個塊（一個為所需大小，另一個用于剩余部分）。

5. 如果請求是 “Large” 的，會花點時間將 fastbin 中的所有內容移動到Unsorted的 bin 中，并隨時合并它們。

到這部分能發現ptmalloc主要是以單線程下去執行所有任務，這種模式實現復雜度較低也適用于單線程系統中，相對的多核系統性能得不到利用

6. 開始從Unsorted的列表中取出chunk，并將它們移動到Small/Large bin，并隨著你的搜索進度而合并（請注意，這是代碼中唯一將chunk放入Small/Large bin 的地方）。這時候有發現大小合適的數據chunk就直接使用并結束本次Unsorted bin的整理。

7. 如果請求是 “large”，則搜索相應的 large bin 和連續的large bin，直到找到足夠大的 chunk。

8. 如果我們在 fastbin 中仍有 chunk （這可能發生在 “small” 請求中），請合并這些 chunk 并重復前面的兩個步驟。

9. 拆分 “top” 塊的一部分，可能事先放大 “top”。

• ??位置與結構??：
  top 塊位于當前分配區（arena）堆內存的??最高地址處??，是唯一連續且未分割的空閑內存塊。它不屬于任何 bin（如 fastbin、smallbin 等），而是獨立管理。
• ??動態伸縮性??：
  當其他 bins 無法滿足內存分配請求時，top 塊會被切割：
  ??切割機制??：從 top 塊中切出用戶所需大小的 chunk，剩余部分仍作為新的 top 塊保留。
  ??擴容機制??：若剩余空間不足，ptmalloc 會通過 brk()（主分配區）或 mmap()（非主分配區）向操作系統申請新內存，并追加到 top 塊中。

優勢

• 兼容性好，Glibc 默認集成；
  mysql默認用它

• 單線程性能優秀
  內存分配系統沒有最優只有更適用于的應用場景；

缺點

• 多線程鎖競爭嚴重；

多線程之間會出現共享緩存行

• 碎片累積不可逆；

??ptmalloc碎片不可逆的根源在于其設計邏輯??：
🔸 ??brk機制?? 要求堆頂連續空閑才能收縮；
🔸 ??非相鄰空閑塊?? 無法合并成大塊；
🔸 ??延遲回收策略?? 緩存碎片化內存；
🔸 ??多arena隔離?? 阻礙全局碎片整理

• 分配效率不高

large多閾值時512B，這意味著>512后搜索可用chunk的時間是O(log(n)),且分配時還需要協助內存管理；

四、jemalloc

使用Jemalloc的知名項目：Firefox、Redis、Rust、Netty

參考文檔：https://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf

特點

緩存行偽共享

代多處理器系統在每個緩存行上保持內存的一致視圖。如果兩個線程同時在不同的處理器上運行，并且操作位于同一緩存行中的不同對象，那么處理器必須仲裁(鎖)緩存行的所有權（見圖1）。這種錯誤的緩存行共享會導致嚴重的性能下降。解決這一問題的一種方法是通過填充分配來增加空間(填充整個緩存行避免剩余空間被使用)，可能導致嚴重的內部碎片化。jemalloc 則依靠多個分配區（顆粒度更小的內存塊大小劃分）域來減輕這一問題，并將避免在性能關鍵代碼中出現虛假緩存行共享，或者在其中一個線程分配對象并將其傳遞給多個其他線程的代碼中的這一問題，留給了應用程序編寫者自行處理，即自行填充分配空間。

圖1：兩個由不同線程使用的分配共享物理內存緩存中的同一行（假緩存共享）。如果線程并發修改這兩個分
配，處理器必須爭奪緩存行的所有權。

緩存行（Cache Line）是CPU緩存的最小讀寫單位，其大小取決于具體的CPU架構，但在現代主流處理器中??一般為64字節??（Bytes）。

線程&Arena

對比ptmalloc它一個線程只會對應一個Arena，但Arena也可以被多個線程使用；

內存塊大小劃分

于ptmalloc相比，內存大小劃分的更加詳細，特別是Quantum-spaced類型–非二冪對齊（但可以被分配單位整除）：Quantum-spaced大小類顯著減少了平均內部碎片。雖然更多的size可能會導致外部碎片增加，但在實際應用中，減少的內部碎片通常能抵消外部碎片的增加；

根據分配的大小進行獨立管理狀態。每個管理狀態都存儲了一個區域位圖，具有以下優點：

• 可以快速掃描位圖以查找第一個空閑區域(因為大小相同)，從而允許緊密地提供內存(而非夾雜更多管理元數據–抽離出去了)。
• 分配器數據和應用程序數據是分開的。這減少了應用程序損壞分配器數據的可能性。此外，由于分配
  器數據不與應用程序數據混合，因此可能增加應用程序數據的局部性。
• Tiny區域可以很容易地得到支持（如果是ptmalloc那種，可能頭尾的元素比數據本身還大）。

對比ptmalloc采用了大量的鏈表（chunk之間是連續的內存快，其中包含大量的元素（不緊密）構建成雙向鏈表管理）， ??jemalloc不需要用連續的chunk組成鏈表管理，更快的管理速度更適合異步管理（因為不會搶占內存行的鎖） ??

減少外部碎片

若采用嵌入式設計（如ptmalloc），??每個空閑塊需存儲“前驅/后繼指針”?? 以維護空閑鏈表：

• ?? ??問題??：分配極小塊（如8B）時，指針可能需占用8-16B，導致小內存分配失敗或被迫浪費空間。
• ?? ??碎片化風險??：嵌入式指針使實際可分配空間小于請求值，加劇內部碎片。

jemalloc 中通過 ??multi-page runs（多頁 run）設計??降低 run header 空間占用導致的外部碎片問題，其核心思路是通過擴大 run 的規模來攤薄元數據開銷，從而將大尺寸 size class 的外部碎片率控制在較低水平（如論文所述的約 3%）。以下是具體分析：

Run 是 jemalloc 中管理 small 內存的基本單元（通常為 4KB 頁的整數倍），內部劃分為固定大小的 ??region??（如 8B、16B 等）。每個 run 通過位圖（bitmap）記錄 region 的分配狀態，并通過 nfree 字段跟蹤空閑 region 數量。

• ??擴大 run 規模??：
  對于非最小 size class（尤其是接近 small class 上限的尺寸，如 2KB），jemalloc 將 run 設計為??多頁連續內存??（例如 4 頁、16KB）。此舉顯著降低了元數據在總空間中的占比。
• ??量化效果??：
  以管理 2KB region 的 run 為例：
  ??單頁 run（4KB）??：header 占用約 128B，剩余空間可分配 1 個 2KB region，??碎片率 ≈ 50%??（剩余 2KB 無法利用）。
  ??四頁 run（16KB）??：header 同樣占用 ~128B，可分配 8 個 2KB region，??碎片率降至 ≈ 3%??（128B/16KB）。

設計選擇	適用場景	碎片影響	性能影響
單頁 run	極小 size class（≤128B）	高外部碎片（元數據占比大）	分配速度快，但碎片代價高
多頁 run	中大 size class（>128B）	碎片率低至 ~3%	減少 run 切換頻率，提升連續性

管理runs

由于每次運行管理的區域數量有限，因此必須為每個size設置多個運行。任何時候，每個size類最多只有一個“當前"run"。當前run保持當前狀態，直到它完全填滿或完全清空。然而，如果沒有 ??滯后機制 ??，單次的malloc/free操作可能會導致一個運行的創建或銷毀。為了避免這種情況，運行根據其滿度分類，QINIT類別的運行永遠不會被銷毀。為了使一個運行被銷毀，它必須首先提升到更高的滿度類別:

滿載類別還提供一種從非滿載運行中選擇新當前運行的機制。優先順序為：Q50、Q25、Q0，然后是Q
75。Q75是最后的選擇，因為這樣的run盡可能滿載；

后臺線程

jemalloc 后臺線程本質是 ??“內存管家”??，通過異步執行回收、合并、負載均衡等任務，實現四大優化：

• ??降低碎片??：合并空閑內存，碎片率 ≤3%；
• ??減少鎖競爭??：動態均衡 Arena 負載；
• ??平滑 CPU 開銷??：延遲操作避免尖峰；
• ??控制內存增長??：按需回收物理頁；

<減少外部碎片>小節的設計是利好后臺線程設計，避免后臺線程與用戶線程搶占內存行的鎖

ptmalloc沒有后臺線程