高频交易系统的内存管理机制介绍与性能调优

概述

本文首先测试了当前交易系统与同类型分配器的性能并进行对比，介绍了当前交易系统内存的管理机制，分析了当前交易系统内存机制性能瓶颈所在，提出了优化方案并落地实践，优化后当前交易系统内存管理性能得到大幅提升，获得预期的调优效果。

与其它内存分配器的性能比较

内存分配器的核心的性能是内存分配与释放的速度。这里将当前交易系统内存分配器与同它内存分配器进行性能测试与对比。
参与比较测试的分配器介绍如下：

当前交易系统内存分配器：基于内存池
malloc-free：无内存池，每次和操作系统申请内存
STL_SGI版本分配器：摘自候捷《C++内存管理》课程代码，基于内存池
GUNC pool_alloc ： GNUC基础内存池的分配器
STL allocator：标准库内存分配器，无内存池

方法： 300万次的内存分配，然后再将分配的内存释放掉，计算总耗时。

当每次分配大小为128字节，O0优化时：

分配器种类	分配内存耗时 ms	释放内存耗时 ms
当前交易系统内存分配器	640	1250
malloc/free	220	140
STL_SGI pool allocator	120	110
GNUC pool allocate	650	320
STL allocator	640	260

当每次分配大小为128字节，O3优化时：

分配器种类	分配内存耗时 ms	释放内存耗时 ms
当前交易系统内存分配器	160	180
malloc/free	210	140
STL_SGI pool allocator	100	100
GNUC pool allocate	610	290
STL allocator	630	300

测试结果显示：

当前交易系统分配器对于优化级别非常敏感，03优化时分配性能提高3倍，释放性能提高6倍
O3优化后的当前交易系统内存分配性能居中。
SGI版本STL内存池分配器在所有情况下都是最好的
malloc-free性能并不差

当前交易系统内存数据库简介

当前交易系统内存数据库的总体构造如下图所示

本文将内存分配器归到内存数据库范围，一是因为目前内存分配器主要只给内存数据库提供内存支持；二是因为内存数据库的遍历功能由内存分配器提供。
内存分配器与内存数据库的细节构造如下图所示

内存分配器分为两级：

一级分配器较为简单，主要功能是向操作系统申请大片内存，申请后不再释放，一级分配器为所有表共用。
二级分配器对内存池进行结构化，通过索引与链表对内存单元进行管理（索引与内存也占用内存池空间），提供内存申请、释放与遍历功能，支撑上层内存数库。内存表的表记录、二叉索引，哈希索引都有各自独立的二级内存分配器。
本文分析与优化的部分是第二级内存分配器，文中所述的内存分配器也是指第二级内存分配器。

内存表由表记录、二叉树与哈希链表构成。

表记录本身有自己的二级内存分配器，内存单元大小就是表记录大小，大小视业务需求而定，例如资金表记录与持仓表记录是不一样的。
二叉树或哈希链表记录也有自己的二级内存分配器，记录的是表记录的内存首地址（指针）即一个节点占用8字节；二叉树的比较函数与哈希链表的哈希函数都是先根据地址找到表记录，再根据字段内容来实现的。

内存池数据结构与分配原理

内存分配的过程简单说来分以下3个步骤：
（1）分配前：用链表将内存单元“串”起来
（2）分配时：从链头“摘”一个出去，索引记录一下“已占用”
（3）归还时：放到链头上，索引记录一下“已空闲”。如果图所示。

内存池整个包含四个部分：头链表，占位索引，内存单元与内存块，地址数组
内存池的结构如下图所示：

链表头：最关键的信息就是下一个空闲内存单元的首地址，上层申请内存时，直接从这里分配，速度快。
占位索引：记录内存单元是否被占用，一个单元用一个bit记录。有了这个索引就知道某个内存单元有没有被占用，在此基础上实现遍历。
内存单元（block）与内存块(chunk)：被分配前空闲时，记录的是下一个内存单元的首地址；被分配后所记录的就是实际内容（分配前所记录的下个内存单元地址信息被上层数据覆盖）。

地址数组：记录的是每一个内存块的首地址，用标准库的vector实现。为什么需要这个东西，是因为归还内存时直接给了个地址，有了这个数组就可以很快找到所属内存块，进而找到索引。

初始化内存分配器时，需要事先确定内存单元大小（UnitSize）和每次申请单元个数N。第一次创建和内存单元用尽时，会向一级分配器申请一片内存，大小为UnitSize * N（简称为chunk，即内存块）的加上相关索引。

性能瓶颈分析

当前交易系统内存分配直接从链表头拿地址，理论上速度很快。对代码裁剪与实践发现，去掉遍历功能后，申请与释放内存确实非常快，符合理论预期。
但是加上遍历后性能功能后急剧恶化，因为当前交易系统分配完内存后，还要将对应索引位置为“已使用”，这步消耗大量时间。其中涉及的主要计算是寻找索引，即根据内存地址找到内存块号以及内存单元偏移，再将相应位置1，期间会调用标准库算法lower_bound进行二分法查找等操作。
用perf工具也能印证GetBlockID最为耗时，GetBlockID就是为SetBlockUsedState设置占位用的。

GetBlockID具体计算过程过下图所示

首先根据地址确定所属块号：确定数组下标
再通过块号与块内偏移得到全局唯一的单元号
最后将“占位”索引置1

在释放内存时，情况类似，除了将内存地址放到链头外，还要将对应索引位置为“空闲”，期间同样要计算索引位置，导致性能恶化。

性能优化方案

既然计算索引位置太耗时，就要避免这个计算，但又要实现遍历，自然的想法是事先将计算好的值存起来。
于是问题的核心转化为“何时”将“何值”事先存于“何处”？

“何值”问题：如何能拿到全局的单元号（block ID），就可以很方便地找到索引位置，计算过程为除以最大单元数可以得到块号，取余数可以得到块内偏移，于是存索引位置就可转化为在于单元号。
“何时”问题：单元号如果通过内存地址来推导，确实很慢，优化空间不大。但这个信息在第一次建立索引时是“现成”的，可以在第一次建立索引“串”链时，把这个单元号存下来。
“何处”问题：内存空闲时，内存单元头地址已经存储指向下一单元的指针，分配后被覆盖，并不占用实际空间。第一轮优化时，我们同样可以将单元号存储于相邻指针旁边，分配后被实际内容覆盖，但问题是这个信息一旦被覆盖，将来释放内存时就又需要进行耗时的运算了。于是第二轮优化时，我们索性将这个值单独存放，即分配后地址的前8个字节存全局单元号，8字节以后才是上层看到的内存地址。

如果图所示

因为8个字节可以表很大的数，实际用不到这么多，于是借用最高位来表示占用信息，原先的索引信息就可以去掉，把集中的索引块分散于每个单元上。

下面两张图显示了优化前后的内存池结构：
优化前：

优化后

该优化方案避开了耗时的计算，缺点是每个单元块会增加8字节表示id，但是由于去掉了索引块，部分抵消了内存占用增加的劣势。

性能优化实践
- 将上述方案实践于代码后，与同类分配器再次进行性能比较，如下图所示。

当分配大小为128字节，O0优化时：

分配器种类	分配内存耗时 ms	释放内存耗时 ms
当前交易系统内存分配器	130（优化前为640）	90（优化前为1250）
malloc/free	210	120
STL_SGI pool allocator	140	100
GNUC pool allocate	630	300
STL allocator	650	310

当分配大小为128字节，O3优化时：

分配器种类	分配内存耗时 ms	释放内存耗时 ms
当前交易系统内存分配器	100（优化前为160）	40（优化前为180）
malloc/free	220	140
STL_SGI pool allocator	120	100
GNUC pool allocate	610	180
STL allocator	630	240

测试结果显示，修改后对优化级别不再敏感；两种情况下当前交易系统的分配与释放性能均为最优。

将修改代码移植到当前交易系统中间件，使用中间件单元测试代码进行修改前后比较，同样显示性能大幅提高。

测试方法为进行4096K次操作，统计耗时。当分配大小为136字节，O3优化时，测试比对结果如下表所示：

中间件性能	优化前ms	优化后ms
分配	223	135
释放	24	5.9
遍历	1716	727
直取	173	6.5

测试截图：

总结与思考

本次优化主要抓住内存分配器耗时的主要环节，通过空间换时间的办法提升分配器的性能，获得了良好效果。在优化过程中以下几点值得思考：

当前交易系统内存分配器的功能是提供内存支持，但其自身又使用了vector，vector是由标准库内存分配器支持的，从这个角度来看，当前交易系统分配器并不独立，依赖于外部分配器支持。
当前交易系统内存分配器中的vector在空间用尽时会进行二倍扩张，期间耗时会增加，这个过程是在上层内存申请时发生的，且初期扩长频繁，会导致事务处理的延时抖动。
本次优化大幅提升了内存释放与遍历的性能，而实际场景中持仓资金等核心表记录很少涉及表记录的删除与遍历。如果明确表不需要遍历，可以在构造表分配器时传入参数，不维护索引相关信息，进一步提高内存分配时的速度。