转载

lua 分配器的一些想法及实践

从周末开始, 我一直在忙一个想法。我希望给 skynet 中的 lua 服务定制一个内存分配器。

倒不是为了提升性能。如果可以单独为每个 lua vm 配置一个内存分配器，自己调用 mmap 映射虚拟内存，就可以为独立的服务制作快照了。这样可以随时 fork 出子进程，只保留关心的 vm 的内存快照。主要可以有三个用途：

可以在快照上做序列化，并把结果返还父进程。通常做序列化有一定的时间代价，如果想定期保存的话，这个代码很可能导致服务暂停。
可以利用快照监控检查泄露。定期做快照相比较，就能找到累积的对象。我曾经做过这样的工具。
可以在镜像上对快照做一些调试工作而不会影响主进程。

为什么为每个虚拟机单独配备分配器是必要的呢？

因为如果对 skynet 整个进程 fork 做出内存快照的话，当所有虚拟机共用一套内存池，很难单独把不感兴趣的内存 unmap 掉。而子进程的内存页是 COW 机制的，一旦子进程工作时间过长，会导致整体内存开销非常大。

因为 lua 本身就可以为虚拟机定制分配器，所以比较容易给出一个实现。事实上我花了半天时间就动手完成了，随后花的更多的精力是从已有项目的线上数据里采集真实的分配器工作流程的 log 用来对新写的分配器做测试。

让已有项目的分配器加上 log ，逐条记录每个 vm 分配器工作时的分配释放操作在临时文件中，再写一个脚本分析这些 log 就可以还原出内存分配器真实的工作流程。大约收集了几百个，从几千条到几千万条不等的 log 后，我就可以做测试了。

测试的过程完全还原线上程序从一开始到退出的每一个内存管理的操作，并在分配后填充入特定的字符串，并在释放的时候逐字节核对并清理。这样的流程跑下来，几乎所有的潜在 bug 都可以发现。（只要测试样本足够多，就至少能保证在现有项目中替换新的分配器不会出问题）

我定制在分配器放在了 github 上。

从时间性能上，其实是很满意的。由于不需要考虑多线程问题，它几乎一定会比 jemalloc 这样的多线程安全的分配器要快的多。我用了一组 300 万条的真实数据对比过（由于数据比较大，没有上传到 github 上):

$ time ./testalloc skynet  real    0m0.139s user    0m0.080s sys     0m0.056s  $ time ./testalloc jemalloc  real    0m0.200s user    0m0.156s sys     0m0.040s  $ time ./testalloc malloc  real    0m0.217s user    0m0.180s sys     0m0.036s

可以看出 jemalloc 和 glibc 的 malloc 差别不是很大，但定制的分配器要快的多。

我的分配策略主要分成三个，对于小于 256 字节的内存块，建立若干条 small object list 缓存复用。

对于 27 到 32K 间的内存块，每次分配 32K 的内存页，切割使用。并在回收的时候用一个链表实现的循环双向队列串起来。按回收的大小来绝对从队列的哪一头插入。分配的时候，在队列上最多移动固定数量的节点，找到最近匹配的合适节点使用。

对于大于 32K 的大内存块，则直接调用 mmap 分配。（实际在 lua vm 使用时，这种大内存块的需求非常稀少）

不过最终我对这份实现不太满意，主要是在某些测试样本中表现出了很大的碎片率。

碎片的产生是由算法产生的，因为分配器的策略是，对于小于 32K 的内存块，只会分割使用，而没有合并。如果长期运行，池中的内存会越来越碎，一旦后续有大内存请求，就会向外申请更多的内存。

我曾经想过定期对中等内存的内存页做合并整理。这个方案以前在为客户端写分配器时用过，感觉实用性不是特别高，所以这次也没有尝试。但我想过把中等内存块采用伙伴算法管理，昨天晚上完成了实现，还有少量 bug 需要调试，尚未提交到 github 。不过我对其最终的效果依旧保有怀疑。

先谈一下伙伴算法具体实现的一些问题：

如果使用伙伴算法，内存分配的单位就一定是某个最小单位长度的 2 整数幂倍。假设最小单位是 256 字节的话，能分配的大小就是 256, 512, 1024 ... 32K 这样。我查阅过采集来的数据，恰巧 lua vm 也经常申请 512, 1024, 2048 长度的内存（table 的数据区的长度）。这就有了第一个矛盾：

通常，我们需要为申请的内存多加几个字节的 cookie 保存一些分配器需要的额外信息。lua vm 在调用分配器时，会给出内存块长度，这样长度信息可以不用记录在内存块中，但对于伙伴算法，我们还需要有一个指针指向伙伴堆的管理器的位置。8 字节的 cookit 看起来是不可省的，这就导致了一种尴尬的境地：lua 通常申请 512 这种整的内存块，而加上 8 字节后，就需要用更大一级的块去满足需求。

固然我们可以把单位块的大小设成 520 这种，但按 lua 申请的翻倍策略，浪费也会越来越大。

也不是完全不能去除 cookie 的额外开销。比如，我们可以将整个 32k 的页的首地址对齐。这只需要在 mmap 时先申请 2 倍的空间 64K 。其中一定包含有一个 32K 对齐的地址，然后把不需要的部分 munmap 掉即可。且当一次对齐成功后，再申请时，通常也是对齐的。

对于 buddy 算法申请到的内存，我们只需要把地址对齐到 32K 上，就能找到当前页的头部。把每个页的第一块用于管理整个页就可以了。

一般的 lua vm 需要的 32K 页不会超过 1000 这个数量级（32 M 总开销），而伙伴算法很容易把整个页填满，活动页数量就更少了。所以在分配的时候查找的开销并不算太大。

第二个尴尬是，lua 有时候会以一些并不整的基数翻倍请求内存。这会使得上面的优化策略无效，依旧会有接近 50% 的内部碎片率。

似乎我们在使用 jemalloc 的时候也观察到过一些类似现象：在长期运行的服务器上，系统报告的内存使用情况和自己统计出来的申请内存数量相差一倍左右。

但是，如果有几千个分配器独立工作，分别使用完全独立的内存池，很可能恶化这种情况。因为 lua vm 在工作时，一旦把一块内存的需求翻倍，很可能短期就不会有后续相同的申请。如果很多 vm 共用同一个内存池，回收内存块的利用率就要高的多。

接下来几天，如果有别的进展，我再写点东西补充。

正文到此结束