TrafficServer内存分配器优化

转自：http://blog.csdn.net/chinainvent/article/details/8243089

TS分配器简介

TrafficServer(简称TS)的内存分配器，在代码里的入口函数为ink_freelist_new/ink_freelist_free，与传统的malloc/free对应。另外还有一个初始化函数：ink_freelist_init，用于设定内存池的元素大小、个数。

TS的内存分配器，其实是一个“类级别”的内存池。用户在使用时，需要为不同的类创建各自的分配器实例。通过要求不同的类，使用各自的分配器实例，从而简化了分配器的设计——每个分配器实例的内存池中，元素大小（tyep_size，其实就是用户sizeof(class)的大小）相等，这样就不必考虑不同大小的元素的合并问题。

在每个分配器实例的内部，有一个lockfree的链表L，多线程可以同时访问链表L而无需加锁，这正是TS分配器高效之处。简而言之，TS分配器的工作过程是这样的：

申请内存

1. 偿试从链表L的头部Pop一个空闲块。若链表L的头部被其他线程占用，循环第1步。

2. 若链接表L头部为空：通过malloc申请一个大块(Chunk)，把Chunk切分为chunk_size份，每份大小为type_size的小块。把这些小块Push到L中，回到第1步。

3. 若链接L头部不为空，把头部的块地址，返回给用户，结束。

释放内存

偿试把用户返回的空闲块Push到链接L的头部。若链表L的头部被其他线程占用，循环第1步。否则，Push成功，结束。

TS分配器的优缺点

优点

由于采用lockfree的链表，线程之间冲突降到了最小，而且申请与释放的逻辑非常简单，速度非常快。

缺点

从TS分配器的申请、释放过程，可以发现，该分配器不存在回收策略。当多个线程同时访问到一个空的链表，这些线程就会同时新建一个Chunk，这也许是导致内存过度膨涨的原因之一，虽然概率很小。无论如何，一个不具备回收策略的分配器，随着时间地推移，它的内存会越来越大，完全不受控制，最终将导致程序OOM。

TS的内存使用特征

一句话概括，就是“过山车”式的。经过统计发现，当一个外部的请求过来，TS会不断的申请内存，随着请求的完成，又会不断的释放内存。整个内存的使用曲线，总是由零点到波峰再到零点。下图是从测试环境（通过jtest工具）中，取出的TS内存分配曲线（某个线程下某个InkFreeList内存池的使用情况）：

其于这样一个曲线，我们就无法使用Slow-Start算法(关于这个算法，可参考Google的TCMalloc文档)来进行内存的回收。因为Slow-Start算法的思想是：在内存的使用量快到波谷时启动回收策略。因此，若使用该算法，回收策略总是在每个波谷处被频繁地、无谓地触发。但是，从这条曲线上，我们还是能够找到一些特征——波峰在某个周期内是相对平坦的。那么，我们便可以通过波峰的统计平均值，来确定cache的大小，从而确定启动回收策略的时机。但比较痛苦的时，基于统计平值的方法，无法实现快速回收。设想一下，如果某个type_size的请求突然消失了，那么这种类型的申请、释放动作，就不再被触发，也就没有机会启动回收策略。

但线上系统的用户请求，通常不会出现这种突然停止的情况，所以从逻辑上，统计平均值的方法会有不错的效果，我也期待在线上环境（使用jtest暂时不好模拟这种请求渐变的过程，即使通过减少jtest的客户端或减少jtest的并发数也无济于事，因为它总是以尽可能最大的频率来发起每一个请求，若能控制它请求的速率就好办了，jtest的选项太多，也许是我还不够了解）验证我的想法。目前我只能通过打日志的方式，来确定回收策略确实会被触发，而且在测试过程中我也能偶尔地观察到内存下降的过程。但无论如何，新的分配器在内存超过预设的最大值时，它总是可以及时的启动回收策略的。

优化目标

1.  保持、甚至超越原版的速度

    速度是TrafficServer的生命力所在，没有速度，没有意义

2.  具有内存自动伸缩功能

    只要能伸缩即可，伸缩的速度可通过参数调节

3.  可以控制内存的最大使用量

为了避免OOM，就必须控制内存使用量，避免其无限制膨涨。内存的最大使用量，可通过参数调节。当内存超过最大使用量时，若用户继续来申请内存，该怎么办？这里有两种策略：
     A)直接返回NULL；
     B）依然返回内存给用户，但当释放内存时，立即启动回收机制，目前采用此策略。

优化方法详解

优化思路

    1.  TS的原版分配器，已被证明有非常好的性能，它的性能是通过lockfree的链表，来实现线程之间对同一个内存池的共享。因此，我们应该继承这个高性能的方案，让新版的分配器，在大部分的时间里，都通过lockfree的链表来申请、释放内存。

    2.  TS的原版分配器，还是存在线程之间对同一个链表L的争抢，如果我们为每个线程单独分配一个链表，这种竞争就可以减小（仅在生产者－消费者模式下，才存在线程之间的竞争），那么我们就有机会实现一个速度更快的分配器。

    3.  为了实现内存自动伸缩的功能，需要在申请和释放操作中，增加内存回收的逻辑。内存回收的逻辑，应该在大部分情况下，都不会触发。因此，我们必须增加一些计数器，用于统计内存的平均空闲率，当平均空闲率超过某个阈值，则在申请、释放的操作中，启动回收逻辑。

    4.  当启动回收逻辑后，采用无锁的设计，至关重要。这将决定在回收过程中，是否会阻塞其它线程。否则某个线程一旦进入回收逻辑，将使系统的整体性能产生抖动。如果我们为每个线程分配独立的内存池，在回收逻辑中，只操作自己内存池的数据，就可以实现无锁化的编程。

    5.  如果我们采用线程独立的内存池，当某些线程空闲后，它的内存池中的空闲块，应该能被其他忙碌的线程复用，以减少浪费。

数据结构

新版内存分配器的数据结构如下所示，主要由四个结构体组成：InkFreeList，InkThreadCache，InkAtomicList，InkChunkInfo，下面将讲解这些结构体的用意。

在TS原版中，所有线程中相同的类，共享同一个内存池（对应数据结构：InkFreeList）。为了给每个线程创建独立的内存池，需要为每个线程创建一个数据结构，我把其命名为：InkThreadCache。每个InkFreeList对应N个线程池，N为使用到该InkFreeList的线程数。
在每个ThreadCache中，根据用户的内存需求，会从操作系统中分配若干大块（Chunk），每个Chunk再切分为chunk_size份小块。为了方便后续的回收，需要为每个Chunk创建一个对应的数据结构来记录这个大块的使用情况，我把这个数据结构命名为：InkChunkInfo。每个InkThreadCache对应一到多个InkChunkInfo。
每个Thread有自己的LockFree list，在大部分情况下，它应该总是可以从这个list上取到内存块。当这个list为空，它再到它的邻近的线程池的LockFree list上取，更多细节我会在下文的“申请内存”，“释放内存”，“回收内存”的描述中介绍。

申请内存

    1.  通过查表法（O(1)时间复杂度），找到自己的线程池InkThreadCache。

    2.  检查线程池的空闲统计平均值、内存总量（后面会介绍统计方法），决定是否启动回收策略，如果需要回收跳到“回收逻辑”的第2步。

    3.  从本线程的内存池中找到LockFree List，即上图中的outer_free_list指针，偿试通过该指针Pop一个空闲块。若成功，返回给用户，结束。理想大小的线程池，在大部分时间里，在这一步应该顺利地完成申请。

    4.  如果outer_free_list为空，通过InkThreadCache->next指针，找到自己相邻的线程池，并偿试从该线程池的outer_free_list中Pop一个空闲块。若成功，返回给用户，结束。这一步的意义在于，防止出现空闲的线程池。

    5.  偿试从线程池的free_chunk_list中找到空闲的InkChunkInfo（Chunk中至少有一个小块空闲，即视为空闲）。若有空闲的Chunk，则通过从该块的inner_free_list中获取一个空闲块，返回给用户，结束。

    6.  若没找到空闲的Chunk，新建一个对应的InkChunkInfo，把线程ID、线程池的地址保存在InkChunkInfo中，再从操作系统mmap一个Chunk、并把Chunk切分为chunk_size份空闲块，每个空闲块的大小为：(type_size + sizeof(void *)，在这些空闲块的末尾埋一个void*指针，用于存储InkChunkInfo的地址信息，把这些空闲块添加到InkChunkInfo的inner_free_list中，回到第5步。

释放内存

    1.   通过释放的地址ptr，反算出对应的InkChunkInfo地址：InkChunkInfo *pChunk = (InkChunkInfo *)((char *)ptr + type_sze - sizeof(void *))。在InkChunkInfo中保存有生产者（指创建本Chunk的线程）的线程ID(tid)、线程池的地址pThreadCache，从而得到该线程池的outer_free_list（即生产者线程的outer_free_list）。

    2.   如果tid与当前的线程ID不一样，说明本线程属于消费者线程，把释放块Push到第1步计算出的outer_free_list中。结束。

    3.   如果tid与当前线程ID一样，说明申请与释放，都在同一个线程。检查线程池的空闲统计平均值、内存总量，若需要启动回收策略，则跳到“回收逻辑”第1步

    4.   若不需要回收，则把释放块Push到第1步计算出的outer_free_list中。结束。

回收逻辑

    1.   把释放块添加到其所对应的InkChunkInfo的inner_free_list中，如果inner_free_list已满（说明本Chunk的所有小块都是空闲的），把整个Chunk块munmap回操作系统。

    2.   试图从本线程的outer_free_list中Pop出chunk_size个空闲块，把每个空闲块添加到其对应的InkChunkInfo的inner_free_list中，如果inner_free_list已满，把整个Chunk块munmap回操作系统

    3.   回收结束，返回。

统计内存总量

内存总量，即所有Chunk所占的内存之和。它的统计非常简单，在mmap/munmap Chunk时，通过原子操作增加/减少一个全局变量(total_mem_in_byte)即可。

统计空闲平均值

空闲平均值，只有在图2的波峰处统计才有意义。最理想的方法是，当程序处在图2中的各个波峰时，查看outer_free_list的空闲值，然后把这些空闲值加起来，求一个平均值。
有两个问题
    1. 如何知道程序处在峰值？
    2.如果我们要记录历史的前N个峰值，就需要N个位置来保存这些信息。
第1个问题，很好解决，我们为每个内存池，增加一个状态变量：status。申请时，把status变量修改为0，释放时把status修改1。在每次释放前，如果status为0，就表明现在处于波峰处。
第2个问题，我使用另一种方法绕过它。假设我们现在，已经得到了一个空闲平均值：nr_average，又计算出了当前的空闲值nr_free，通过下面的公式可近似的求出新的平均值：
    nr_average = P * nr_free + (1 - P) * nr_average

其中P(0 < P < 1)是一个经验值参数，P值越大收敛越快，P值越小收敛越慢，在程序中P是一个可通过配置文件设置的变量：reclaim_factor。

可配置参数介绍

max_mem_in_mb，最大内存总量(单位是MB)

当total_mem_in_byte > max_mem_in_mb * 1024 * 1024，总是启动回收策略。

reclaim_factor，收敛因子

用于计算空闲平均值nr_average，当nr_average > chunk_size时，并且 nr_overage > max_overage时，启动回收策略。
max_overage，超额数
测试中发现，某些突然的峰值，会剧烈地改变空闲平均值，使程序启动不必要的回收策略。因此引入了max_overage这个配置变量，当nr_arerage连续大于chunk_size的次数达到max_overage后，才启动回收策略。

性能对比

QPS性能

 压测命令

 jtest -S ts.cn -s $PORT -P localhost -c 1000 -z 0.96 -D 1 -Z 100000

 为了不受网卡的影响，jtest与trafficserver跑在同一台机器上。
对比说明    

从测试结果来看，分配器的内存池一旦预热完成，新、老版本性能非常接近，这符合我们的优化目标。甚至，在多个线程同时密集地访问到某个内存池时——这个情况不太好模拟——新版的内存池性能会更好，因为新版的内存池总是先从自己的outer_free_list取内存，冲突率更小。

内存控制效果及CPU使用率

使用率

在相同的QPS下，CPU使用率也大致一样，几乎没有太大差异。当然，如果新版Allocator进入回收策略（在请求速率不变的情况下或者没有超过最大内存使用量的情况下，是不会进入的），CPU使用率是升高一些。
内存控制效果

从图中可以看到，新版Allocator由于为每个线程设置独立的内存池，因此它在刚启动并进入平稳状态后，它的内存基数会比原版的Allocator大，只要这个值在可控制的范围内，我想不会是什么问题。

而内存的控制效果，我暂时没有找到好的方法在这里展示，因为这是一个变化过程。我可以通过设置一个小的max_mem_in_mb值，来控制内存的上涨；而内存的自动回缩，我前文已经阐述过，目前的测试手段不太好证明其效果（值得庆幸的是，我刚才已经找到了回缩的证据，前面已经给出截图:D）。