导读
在java的世界里好像已经不再需要关注内存申请、内存回收这些直接内存操作了。更多的时候java程序员是在讨论垃圾回收器(内存分代、回收算法)等内存自动回收技术。操作系统中各种相关名词“内存池”、“内存碎片”、“malloc”、“free”似乎早已远去。
本文借助于内存池的java实现—Netty内存池，对相关理论和实现进行了阐述以使我们重新复习一下内存分配和回收的相关知识。
背景
计算机世界中存在着各种各样的“池子”，如线程池、连接池、内存池。在java世界中可能接触的最多的是线程池/连接池，内存池好像比较陌生，更多的时候对内存池的印象只停留在上学时期操作系统课程中的内存管理相关内容。因此本文要讲的主要内容为内存池的一个java实现—Netty内存池。为了能较明白的理解Netty内存池的设计和实现，本文从以下几个方面对内存池进行了分析。
1，为什么需要内存池；
2，内存池的实现思路和理论支持；
3，Netty内存池的总体介绍；
4，Netty内存池关键组件分析。
为什么需要内存池
在做一件事情前如果不了解它存在的意义那么必将陷入“只见树木不见森林”的误区。因此弄清楚内存池存在的意义会是很有必要的。这里先不直接去说明为什么需要内存池，可以举例思考下面几个场景。
直观上感觉java中内存的分配和回收完全是由jvm所控制的，jvm对内存管理高效并且方便(不需要要求程序员时刻想着内存释放)。的确，jvm内存分配确实是高效的，但是是否所有的场景下jvm的自动的分配和回收都是高效的呢?是否还有着更好的实现方案?对于有着更高要求的情况也是这样的吗?对上面几个问题分别简单思考一下（当然这并不是要读者联想到如C++语言的手动内存分配和回收，仅仅是针对java中的一些典型情况）。
1）是否所有的场景下jvm的自动的分配和回收都是高效的呢?
对于需要使用缓冲区Buffer的io操作来讲，情况却稍有不同。这主要体现在两个方面：频繁的内存Buffer的创建销毁这必然会对jvm的GC造成一定的压力，进而影响服务的性能，因为既然是io密集型的业务为什么不cache一份呢；如果对内存使用有着更高的要求，如使用堆外直接内存的分配和回收，虽然堆外内存的使用效率会比较高，但是其内存申请的操作会比堆内存的申请更加耗时，因此频繁的申请和释放将是一件更加耗时的操作。
2）是否还有着更好的实现方案?
受限于当下的软件和硬件的处理速度或许一时想不到更好的方案对 这些特殊的场景进行优化，这时我们可以借助于一些计算机领域的传统理论“内存池”。进而就是java语言实现的内存池-Netty内存池。针对上面的情况可以看一下一个比较权威的官方测试结果-Twitter使 用Netty内存池和不使用内存池的性能对比(ps为什么算是比较权威官方的测试呢?因为Netty的创始人加入了twitter，并且Netty在其公司内部被广泛使用)。
图1:内存分配池化和非池化对比
（出自twitter技术博客netty-4-at-twitter-reduced-gc-overhead）
从上图中可以清楚的看到随着内存需求的逐渐增大，无论是堆内存还是堆外直接内存耗费时间的差距越来越大。池化技术确实展现了不错的性能。
怎么实现一个内存池
上一部分对内存池存在的必要性进行说明，此部分主要说明下如何实现一个内存池。先不去参考其他任何成熟的线程池方案，可以先用我们朴素的想法去思考一下这个问题。这里举一个常规思路的例子并说说在此例子中可能会遇到的问题。
1）预先去申请一块内存（比如java中去new一个byte数组）然后缓存起来一直不释放;
2）外部有对内存池的内存申请请求时，这时候需要去byte数组中选取一块可用的内存返回给使用方。
上面简单的两步似乎就完美的解决了内存池的问题。但再深入思考一下就会发现在分配的过程中就会面临几个典型的问题:
1）采用什么样的数据结构和算法组织管理内存的使用和未使用情况?
2）在多线程并发申请的情况下如何尽量保证和单线程一样的效率?
3）随着不断的分配内存，回收内存这些操作会不会造成内存空间的不连续性也就是内存碎片，如何避免这些问题?
4）进一步还有更高级一点的问题，有没有机制来保证不发生内存泄露的情况(这里指本应该释放回内存池的内存因为某种错误一直 占据着没有释放)。
通过上面几个问题，进而可以得出评价内存池好坏指标的两个重要的因素:
1）快速的申请和释放内存;
2）尽可能的提高内存的利用率，减少内存碎片。
自己思考半天可能未必会是一个较优的方案，这时候需要来看看一个优秀的内存池实现-jemalloc，这个也是Netty内存池实现的理论依据和参考。了解完jemalloc后再看Netty源代码中那些晦涩的术语和莫名其妙的算法才有事半功倍的作用，否则只会是事倍功半。
简单的介绍一下jemalloc，jemalloc由Jason Evans(当时FreeBSD的一个厉害的开发人员)在2005年为提高低性能的malloc而开发的jemalloc，此后Jason Evans加入Facebook并在2009年针对 Facebook的使用情况做了一系列的适配和优化后应用到了Facebook内部的很多项目中，同时jemalloc也因为Facebook变的很出名。
（http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc. pdf）为Jason Evans在2006年发表的论文原文。
jemalloc同样也是站在了malloc的肩膀之上，但是jemalloc发展出最突出的两个特点:多Arena和threadlocal-cache。多Arena是将整个内存池的总体内存容量划分成几个小块来管理，这个块就是Arena。多个Arena可以分散多线程的请求，减少Arena上的内存竞争。threadlocal-cache为线程级别缓存，每个线程有自己的内存缓存，这样可以完全避免多线程的锁竞争，同时也减少了内存池内存分配的总体流程，减少了内存分配的时间复杂度。
Netty中的内存池
在网络IO中会涉及到大量的读写操作，从而也会涉及到大量的内存申请和回收操作。Netty虽然由java语言开发但其“重回原点”开发了一个内存池用于内存的分配和回收来进一步提高性能。本文内容基于Netty4.1.43.Final版本(5.x版本官方承认效果不佳不再支持，如fork-join线程池的优化失败)。
1.Netty 内存池总体概览
在了解一件事的时候往往会先了解一下helloworld，这次也不例外，下面为Netty内存池的使用例子。
publicstaticvoidmain(String[] args){// 默认为堆内存，Netty内存池可以为堆内存，也可以为堆外内存ByteBufAllocator alloc =newPooledByteBufAllocator();// 申请3M的的堆外内存ByteBuf byteBuf = alloc.directBuffer(3145728);// 内存释放 byteBuf.release();// 申请12字节的堆内存ByteBuf heapBuf = alloc.buffer(12); heapBuf.release(); }
为了避免让读者陷入N多不知所云的术语和无尽的源代码细节中，因此先根据jemalloc来总体上介绍一下Netty内存池。首先需要介绍Netty内存池中的几个关键组件，之所以会有这些组件就是是因为仿照参考了jemalloc，而jemalloc又在实践中取得了不错的表现。
图2:Netty 内存池总体结构
PoolArena：内存池分配的总体入口，内存池的分配动作都在这个类中对外提供。根据jemalloc设计思路Netty也采用多个PoolArena以应对多线程的情况(Arena的数量为了和Netty中EventLoop的数量保持一致，都是采用cup核心数量 * 2)。这样多个线程对内存池有分配请求时可以使多个线程均匀的分配在多个PoolArena以减少竞争。
PoolThreadLocalCache：为了提高在多线程环境下的性能，Netty设计了一个线程变量，该线程变量缓存一定的分配空间，使得分配回收不用走全部的分配流程，避免了线程竞争。有点类似于java中ThreadLocal的概念，是不是也和JVM中的TLAB有一种似曾相识的感觉。
PoolChunkList：将具有相同内存使用率区间的Chunk集中在一起形成的一个Chunk列表。目的在于高效的分配和管理。
PoolChunk：一个连续内存空间的管理者。具体有堆内Chunk和堆外Chunk，其默认大小为16MB。
Page：Chunk中的最小内存单位。Chunk将自身申请的连续内存空间分割成相等大小的许多Page。通过对Page的分配来完成内存分配功能。其默认大小为8k。
PoolSubpage：分为Tiny和Small类型的内存，用来表示不同大小的内存块。Tiny内存大小范围是16Byte到512Byte，以16Byte为一个台阶，因此可以用于分配Tiny内存的有512/16=32种。Small内存大小分别为512Byte、1k、2k、4k四种类型的内存块大小。
上面还是不可避免的介绍了几个组件概念，如果读者第一次读到的话肯定也会比较懵。在详细介绍上面几个组件前，先来看一下内存池的总体分配流程：
1）内存分配器(ByteBufAllocator)确定是堆外直接内存还是堆内存，根据请求的内存块大小转换为线程池支持的内存块大小(如500字节转化为512字节、3M转化为4M);
2）先去线程级缓存(PoolThreadLocalCache)中查看自己对应线程的缓存中是否有已经分配好的内存块，如有的话就直接返回。PoolThreadLocalCache思想基本和ThreadLocal一样，可以避免多线程的锁竞争;
3）根据申请的内存块大小选择不同的分配策略申请内存，如
<512byte的请求会根据实际请求的内存大小去tinySubpagePools数组中选择合适的Tiny链表进行分配;
<8KB的请求会根据实际请求的内存大小去smallSubpagePools数组总选择合适的Small链表进行分配;
<=16MB的请求会去 PoolChunkList组团中根据规则选取PoolChunkList中的PoolChunk进行内存分配。
看完上面的关键组件介绍和总体内存分配流程，或许你已经对Netty内存池有了一个总体上的印象。各个组件的一些细节会在后面的章节中进行详细的阐述。但是图2中提到的“PoolChunkList 组团”这里必须解释一下，先来看jemalloc 论文中的一个截图。
图 3:jemalloc论文中PoolChunkList组团示意图
（出自论文A Scalable Concurrent malloc(3) Implementation for FreeBSD）
在PoolChunkList组团中各个PoolChunkList如图2中那样通过双向链表结合在一起，各个PoolChunkList的PoolChunk会根据内存使用率情况在各个PoolChunkList中移动，如图3中按照chunk的使用率进行了分类，并且根据论文中的建议内存在PoolChunkList组团中的分配顺序Q50,Q25,Q0,Q75。Netty中基本也是按照这个顺序只是在Q0和Q75之间增加了QINIT。之所以会存在“组团”其目的是为了提高内存的分配效率，并能够及时回收掉不使用的内存来控制总内存池子的大小。如Q50保存的是内存利用率50%至100%的Chunk，首先在Q50中分配是一个综合考虑分配效率和池子内存利用率的折中方案。再比如Q75因为内存利用率太高，首先分配的必然会导致分配成功率降低从而整体上降低内存分配效率。
2.PoolChunk和伙伴算法
为了让读者有一个直观的感受，首先看一下PoolChunk中管理内存池的数据结构和算法。
图4:PoolChunk管理page数据结构
图5:层数索引结构图
如图4，PoolChunk内部管理着一个大块的连续内存区域，将这个内存区域切分成同样大小的块，每一个称之为一个Page。从内存池中申请大于等于8K内存块将会转变为从PoolChunk中申请一定数量Page。为了方便内存空间的管理，PoolChunk内部采用完全二叉树的方式对Page进行管理。通过PoolChunk，可以对大于等于PageSize(Page的大小默认8k)的内存申请进行分配和管理。图5中表示的是一个辅助满二叉树查询层数的索引信息，在Netty中对应于depthMap索引是为了便于快速根据page定位到层数。为了理解PoolChunk内存分配算法需要记住PoolChunk的以下几点:
1）一个PoolChunk默认会申请16M大小的内存空间；
2）page代表chunk中能被分配的最小单元，page的大小为8k，因此 PoolChunk中共有2048个page;
3）PoolChunk中的2048个page的开辟数组(实际数组下标从1开始)按照满二叉树数组的存储方式，把此数组看成一个逻辑上的二叉树，此二叉树共有最高层数11。
在了解了PoolChunk内部内存管理的数据结构后，下面对PoolChunk分配流程/算法进行介绍。为了便于理解下面的流程以分配3M的内存流程为例子进行表述。
1）由于3M大于2M小于4M，那么把3M的内存请求转换为4M进行；
2）此时为PoolChunk的初始分配，由图可知二叉树的第二层和4M空间相符合，这时取这层的最左节点page4节点作为内存空间，并将高度值设置为12(树的最大高度值+1)表示此节点以及此节点下的所有子节点都已经分配完了；
3）page4节点的父亲节点(page2节点)，将高度值更新为两个子节点的较小值，直到高度值更新到根节点。父节点的高度值会相对原来的高度值变大，这代表该节点下的至少一个子节点或者孙子节点已经被分配出去了。
上面的步骤基本描述了page内存块的分配过程，但是有一点还需要补充说明一下，步骤3提到二叉树节点被分配出去后更新了父节点并一直到根节点，并没有去更新子节点。如上个例子中page4节点已经被分配，但是page4下面的子节点/孙子节点的高度值并没有更新，那么是如何保证这些子节点不会被再次分配到的呢? 这个Netty针对满二叉树做了一系列巧妙的位运算得以解决这个问题。源代码注释如下:
上面写的内容都是关于PoolChunk是如何分配内存的。但为什么要这样设计呢?比如两个主要的问题:
1）为什么要组织为二叉树的形式?
2）为什么要组织为满二叉树?
在回答上面两个问题前先了解一下PoolChunk的理论依据-伙伴内存分配算法。该算法的主要思路是每次把一个大内存块对半切分，然后再对半切分，一直切到最小的单位如PoolChunk的page（满二叉树可以方便的利用一块大的连续内存。分配的时候找到合适内存块大小即可;回收的时候，如果跟它的伙伴 (即PoolChunk二叉树的兄弟节点)也是未被使用的，就合并成一个大的块。数据结构组织为二叉树的形式，那么分配和释放的时间复杂度都是O(logN)同时N不会很大。该算法的优点是可以有效减少内存外部碎片;缺点是page为最小的内存分配单位，那么如果分配请求不能被pageSize整除的情况下必然会产生内存浪费。如上面的例子中申请的是3M的内存空间，但是必须要给其分配一个4M的节点，这就造成了有1M的内存空间虽然被分配出去了，但是却无法真正利用，这也就是内部碎片。
知识小助手，内部碎片和外部碎片。
外部碎片指的是还没有被分配出去(不属于任何进程)，但由于太小无法分配给申请内存空间的进程的内存空闲区域。这些存储块的总和可以满足当前申请 的长度要求，但是由于它们的地址不连续或其他原因，使得无法分配出去。内部碎片是指已经被分配出去却不能被利用的内存空间，如上面Netty中PoolChunk的page例子。直到这个内存空间被释放后才有可能在下次分配中重新被真正利用。
3.PoolSubpage和Slab分配算法
通过上一个部分对PoolChunk的介绍得知，PoolChunk可以高效的对内存进行分配，同时PoolChunk的存在有效的避免了外部碎片的产生。但是PoolChunk是否就完美了呢?显然不是的。我们可以轻易的发现PoolChunk的两个问题。
1) PoolChunk中最小分配单位Page的大小为8K字节。但是如果小于PageSize的申请也要消耗掉一个Page的话就有些浪费了。
2) PoolChunk虽然有效减少了外部碎片的产生，但是如果我们分配更小(小于8k)需求的情况下势必有会造成内存空洞或者内存内部碎片的产生。
针对上面的两个问题，这时候有人或许会提出：把page的单元大小做的小一点不就行了吗？比如page大小设置为4k，2k，1k甚至更小。那么这么做是否可行呢?只能说这个解决方案在思路上有一定的道理(事实上几种不同的伙伴系统的实现最小分配单位确实各不相同，不过应该也没有低于1k的)。
之所以最小单位不能设置的太小，说说我的理解：
1）page太小必然耗费更多的内存去管理大量的小块内存;
2）虽然伙伴分配和释放内存时间复杂度是logN，但是随着层数的增多以及不同大小内存的混合分配必然造成二叉树操作的冗余；
3)经过一段时间的分配和回收之后内存碎片的问题也更容易严重；
4）从统计实践的角度去看这个问题也不太合理，即一个系统中不同大小内存的应用和使用方式肯定有着自己的规律，因此实践中会更适合“因材施教”。
Netty内存池中PoolSubpage负责小内存的管理分配，PoolSubpage的实现思路基本借鉴了SLAB内存分配算法，SLAB是一种针对小内存块申请回收的算法。SLAB往往也和伙伴分配机制配合使用，SLAB会在伙伴系统中申请一个最小内存单元块，然后把块进一步划分为多个不同大小的内存块以满足不同大小内存分配的需求。针对小内存块的申请释放可以只在SLAB中以一种更简单的方式运行。参考SLAB内存分配器的特点，Netty中PoolSubpage仿照SLAB思路设计了数据结构。下面介绍PoolSubpage的结构（总体上分为smallSubPagePool和tinysubPagePool）以及几个重要特点。
图6: Small级别smallSubPagePool
图7: Tiny级别tinysubPagePool
PoolSubpage其实是从PoolChunk中分配出来的一个page因此其大小也为8K。PoolSubpage也分为两种类型：小于512字节的块类型称之为Tiny，大于等于512字节的块类型称之为Small。
SmallSubPagePools（Small类型的PoolSubpage链表）如图6所示，总共有四种不同的内存大小块，512字节、1024字节、2048字节、4096字节4个元素，每个元素对应一个相同大小内存块的PoolSubpage链表。
TinySubPagePools（Tiny类型的PoolSubpage链表）如图7所示最小空间为16字节且16个字节为一个阶梯，区间为[16,512)的一个数组，所以共有32种不同的内存大小块，因此也就会有32个元素，每个元素对应一个相同大小内存块的PoolSubpage链表。
那么是如何有效管理PoolSubpage中的内存块的呢？
简单的说，Netty的实现方案是用bitMap管理PoolSubpage内存块是否已经分配。如果bitMap对应的位的值为1，那么说明已经分配，如果为0说明还没有分配。这里需要特别说明的是这里的bitMap为Netty利用long类型数组实现方式。结合PoolSubpage内存块的分配流程和bitMap说明如下：
如申请16字节的内存块：
1）判断16字节的内存块为Tiny类型，那么去tinysubPagePool中中查找大小为16字节的PoolSubpage
2）如果为首次分配那么初始化PoolSubpage（内存块大小为16字节）
3）初始化一个8个元素的long数组new long[8]（总量为8k的PoolSubpage里面的小块大小为16字节，因此总共需要管理的小块数量为512个，512/64=8，64为long占用bit数量，因此需要8个元素）
4）在小块内存的分配过程中会按照bitMap中的顺序依次分配，如下
第1次分配取long数组（bitMap）的第1个元素，并把long数字的最低位置为1；
第2次分配取long数组（bitMap）的第1个元素，并把long数字的次低位置为1；
.......
第65次分配取long数组（bitMap）的第2个元素，并把long数字的最低位置为1。
4.多线程和PoolThreadCache
在文章的前段提到Jemalloc内存分配器设计的一个主要目标是为了改善之前内存分配器在多线程环境下不尽如人意的性能表现。因此Jemalloc除了利用多个Arena来减少线程竞争的方式外，还有重要的一点是充分利用了线程级别缓存。针对线程级别缓存Netty设计了一个线程缓存类PoolThreadCache通过线程变量的方式存储。
当程序申请空间也首先尝试从缓存中申请，内存使用完毕后内存空间也会添加到线程缓存PoolThreadCache中。这里的线程级别缓存其实现思想非常类似于java中的ThreadLocal并且Netty还设计了FastThreadLocal来进一步提升性能。PoolThreadCache的设计思路沿用Arena内存空间分块设计思想。但是在存储空间和内存管理数据结构上做了调整。
线程级缓存（PoolThreadLocalCache）和PoolThreadCache逻辑设计结构如下图:
图8:poolThreadCache结构图
线程级缓存（PoolThreadLocalCache）中存储了数据结构PoolThreadCache。在PoolThreadCache创建有三种不同的MemoryRegionCache数组。分别为tiny数组、small数组、normal数组，这三者的含义和Arena定义的定义的三种数组的含义一致，代表着一个线程下缓存的不同大小的内存块。这里需要说明的是为了控制线程栈内占用太多的内存，在PoolThreadCache中现在了存放内存块的大小，如normal级别的内存块只允许cache最大32K的块单位。
当要从线程缓存中申请空间时，根据申请大小从MemoryRegionCache数组中找到合适的MemoryRegionCache。如果能找到，则从队列中获取节点得到内存信息。当要释放内存空间时，优先将内存空间加入到缓存中，也是先找到合适的MemoryRegionCache。如果能找到则尝试将内存信息放入队列中，如果队列已满，则走正常的释放流程。之所以采用队列存储内存池信息一方面为了方便控制cache内存的大小；另外也是为了方便快速的读取缓存信息。
还有一点值得说明是FastThreadLocal。FastThreadLocal是为了进一步提高JDK当中ThreadLocal的性能而开发的工具类，其利用内存对齐、优化存取等一系列手段提升性能。当然FastThreadLocal并不是本文的重点这里不做详细展开。这里要想表达的是FastThreadLocal对提高Netty线程级缓存发挥了更极致的作用，因此它的设计和实现值得好好研究一下。
总结
对于java程序员来说内存的手动分配和回收并不常用，但随着java中越来越多的高性能IO工具如缓存管理工具的广泛应用。熟悉系统中的内存分配和回收原理会更加有利于掌握底层运行的原理，加深系统的认知。
本文通过用内存分配相关理论和Netty内存池的实现联系在一起的方式对内存分配理论和实践进行介绍。虽然针对Netty内存池源代码方面的分析并不多，但是熟悉本文中的各种相关知识后再去阅读源码定会容易很多，同时也有助于我们设计出越来越优秀的系统。
作者简介：
崔海东：用户价值增长部-部落后端技术
参考文献：
http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf
https://blog.twitter.com/2013/netty-4-at-twitter-reduced-gc-overhead
http://jemalloc.net/
Glibc内存管理-Ptmalloc2源代码分析
Netty源代码
推荐阅读：
