系统的物理内存是有限的，而对内存的需求是变化的, 程序的动态性越强，内存管理就越重要，选择合适的内存管理算法会带来明显的性能提升。
比如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 收缩内存是从 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对象都是页面对齐分配，多线程的时候应尽量避免频繁分配，否则也会造成自旋锁的竞争和页面对齐造成的浪费。

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，提升缓存命中。

jemalloc是一个能够快速分配/回收内存，减少内存碎片，对多核友好，具有可伸缩性的内存分配器。为更好的支持多核内存分配的需要，jemalloc首次在FreeBSD中引入，用于取代之前的phkmalloc，而后被facebook发扬光大，成为了业界流行的内存分配解决方案之一。

####设计思想

jemalloc在结合其他内存分配器优势的同时也引入一些自己独特的机制，下面这些观点和设计哲学构成了jemalloc：

针对小内存分配场景引入一系列size类，8bytes，16bytes，32bytes等等，分配小内存时从相应size类分配（可以理解成dlmaooc里的分箱），并且遵循低地址优先原则，这样可以极大避免内存碎片。

谨慎选择size类的数目和间隔，兼顾内存内零头和外零头。

元数据占用空间尽量少，除内存碎片以外，jemalloc元数据的空间占用小于内存总用量的2%。

减少活动页面数目，即尽量充分利用空间，将数据紧紧存储在连续几页，既可以利用局部性，又能减少swap。

最小化锁竞争，jemalloc从lkmalloc引入线程独立的arena机制，从google的tcmalloc引入thread cache机制，尽量减少线程之间分配回收内存时的锁争用。

如果做不到通用，说明不够好

####jemalloc核心架构

jemalloc采用多级内存分配，根据内存对象的大小，jemalloc将其分为small object, large object和huge object三类。

Small objects的size以8字节，16字节，32字节等分隔开的，小于页大小。

Large objects的size以分页为单位，等差间隔排列，小于chunk的大小。

Huge objects的大小是chunk大小的整数倍。

small objects和large objects由arena来管理， huge objects由线程间公用的红黑树管理。

WuYu photo
BY WUYU
MAY 03, 2015
PERMALINK
LIKE
####引言

jemalloc是一个能够快速分配/回收内存，减少内存碎片，对多核友好，具有可伸缩性的内存分配器。为更好的支持多核内存分配的需要，jemalloc首次在FreeBSD中引入，用于取代之前的phkmalloc，而后被facebook发扬光大，成为了业界流行的内存分配解决方案之一。

####设计思想

jemalloc在结合其他内存分配器优势的同时也引入一些自己独特的机制，下面这些观点和设计哲学构成了jemalloc：

针对小内存分配场景引入一系列size类，8bytes，16bytes，32bytes等等，分配小内存时从相应size类分配（可以理解成dlmaooc里的分箱），并且遵循低地址优先原则，这样可以极大避免内存碎片。

谨慎选择size类的数目和间隔，兼顾内存内零头和外零头。

元数据占用空间尽量少，除内存碎片以外，jemalloc元数据的空间占用小于内存总用量的2%。

减少活动页面数目，即尽量充分利用空间，将数据紧紧存储在连续几页，既可以利用局部性，又能减少swap。

最小化锁竞争，jemalloc从lkmalloc引入线程独立的arena机制，从google的tcmalloc引入thread cache机制，尽量减少线程之间分配回收内存时的锁争用。

如果做不到通用，说明不够好

####jemalloc核心架构

jemalloc采用多级内存分配，根据内存对象的大小，jemalloc将其分为small object, large object和huge object三类。

Small objects的size以8字节，16字节，32字节等分隔开的，小于页大小。

Large objects的size以分页为单位，等差间隔排列，小于chunk的大小。

Huge objects的大小是chunk大小的整数倍。

small objects和large objects由arena来管理， huge objects由线程间公用的红黑树管理。对于64位操作系统，假设chunk大小为4M，页大小为4K，内存等级分配如下图：

在 jemalloc 中，整块批发内存，之后或拆开零售，或整块出售。整块批发的内存叫做 chunk，chunk 的大小为 4MB（可调）或其倍数，且为 4MB 对齐。由于chunk粒度太大，只有为huge objects分配内存才需要这种粒度，因此chunk进一步拆分为不同粒度的run，分配small/large objects都以run为单位。但是对于small objects来说，这个粒度还是大了点，因此又分成不同大小的bin，分配时找对应的bin，由bin提供小对象需要的内存，但要注意羊毛出在羊身上，bin其实也是通过其管理的run提供内存的，相当于在run上面盖了一层元数据的帽子。另外由于chunk都是等大小，这样可以通过指针操作在常量时间内找到分配small/large objects的元数据, 在对数时间内（红黑树）定位到分配huge objects的元数据。 chunk，run，bin管理的都是自己那部分内存资源，因此还需要一个角色在chunk，run，bin的基础上，以全局观角度去管理系统内存，这就是Arena。为了更好的线程可扩展性，jemalloc采用多个arena管理内存，它的数目一般为物理机CPU核数的4倍。每个线程独立管理自己的内存，负责small和large的内存分配，减少了多个线程间的锁竞争。线程按第一次分配small或者large内存请求的顺序Round-Robin地选择arena。并且从某个arena分配出去的内存块，在释放的时候一定会回到该arena。此外， jemalloc引入线程缓存tcache来解决线程之间的同步问题， 通过对small和large对象的缓存，实现通常情况下内存的快速申请和释放。下图是经典的jemalloc的架构图，主要涉及前面所讲的四个数据结构：arena，bin，chunk，run。

small object

当jemalloc支持tcache时，small object的分配从tcache开始。
tcache不中则从arena申请run并将剩余区域缓存到tcache。
若arena中不能分配则从系统内存中申请chunk，加入arena进行管理并切成run，go to step2。
不支持tcache时， 则直接从arena中申请，go to step2。
#####large object

当jemalloc支持tcache时，如果大对象所需内存小于tcache_maxclass，则从tcache开始分配。
tcache不中则从arena申请，只申请需要的内存块，不做多余cache，arena从可用run红黑树中取出地址最低且满足大小条件一个，按页对齐切一块给申请者，剩余的继续保留在可用run红黑树中，归还时这块区域放到tcache里。
若arena中不能分配则从system memory中申请。
当大对象所需内存大于tcache_maxclass或者jemmalloc不支持tcache时， 直接从arena中申请。
#####huge object

huge object的内存不归arena管理，直接采用mmap从system memory中申请并由一棵与arena独立的红黑树进行管理。

jemalloc的内存分配和释放的具体细节可以参考文章 1 2 3 4，这里不作详细介绍，jemalloc的内存分配就介绍到这，这里做一个简单的总结：

jemalloc引入线程缓存tcache, 分配区arena来减少线程间锁的争用, 保证线程并发扩展性的同时实现了内存的快速申请释放。
采用arena管理不同大小的内存对象在保证内存高效管理的同时减少了内存碎片。
引入红黑树管理空闲run和chunk，相比链表具有了更高的效率。
在run中采用bitmap管理可分配区域来实现元数据和数据分离，且能够更快地定位到空闲区域。
引入了多层cache，基于内存池的思想，虽然增加了内存占用，但实现了内存的快速申请释放，除了tcache，还有bin中的runcur， arena中的spare等。