一、内存碎片

内部碎片与外部碎片

内部碎片：指已分配给进程但未被实际利用的内存空间，属于​​已分配内存内部的浪费​​。
外部碎片：内存中​​零散分布的空闲小空间​​，总量足够但无法合并为大块以满足连续内存请求。

内部碎片与外部碎片是矛盾的只能平衡取向：

减少内部碎片：当每次申请内存时，只获取对应大小内存，可以消除内部碎片，但出现难以重新利用的外部碎片（
除非遇到新程序申请的内存指定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没有后台线程