数据库存储引擎如何利用好CPU缓存 | X-Engine内核

本文探讨如何优化X-Engine中DataBlock内部的记录编码格式，以降低在DataBlock中查找单条记录时的CPU cache miss次数，最终目标是提升DataBlock点查询性能。由于X-Engine数据页编码格式和查找算法与很多数据库引擎(如InnoDB)是类似的，因此 文中提出的方法对使用类似数据页格式的存储引擎都是普适的 。

X-Engine数据页格式和页内查找算法

X-Engine是LSM-tree架构的存储引擎。查找一条记录，首先从内存表Memtable中查找，未命中，则从磁盘中查找。磁盘上的数据，通过索引定位到目标DataBlock，并装载进内存查找目标记录。查询完成后DataBlock被放入缓存，等待下次查询。

X-Engine KV接口单点查询，结果全部缓存命中的场景，通过perf分析表明： 在DataBlock中定位seek()及顺序next()操作，消耗了35%的CPU资源，是单一最大的CPU消耗点。

X-Engine数据页格式

X-Engine的DataBlock中记录编码格式如下图所示：

此格式的几个基本特点：

DataBlock默认定长16KB(可配置调整)，且DataBlock支持原地做单条记录的更新操作，即一个DataBlock只能完整的生效或者被废弃。

记录按key从小到大顺序排列，key和value连续存储在一起。在一段连续存储(默认为16条)的记录段上，使用前缀编码。每个前缀编码段的第一条记录称为一个restart点，在每个restart点之后的记录，key只需要存储相对restart点的key的delta部分。

DataBlock末尾是restart offset数组，它的每个元素存储了restart点相对DataBlock起始地址的偏移。由于offset都是4字节，在此数组中可直接二分查找，快速定位到目标restart点在DataBlock中的偏移位置。

DataBlock页内查找算法

在一个存储N条记录的DataBlock中，查找一条key=X的记录。查找算法如下图所示的1~5步执行：

1.在restart数组二分查找，定位到最后一个小于或等于X的记录的offset。

2.从offset开始，依次向后读取每条记录，与X做比较，直到找到大于等于X的第一条记录，并返回偏移位置。

3.该过程涉及对前缀编码的解码。在一个前缀编码段中，除第一条记录外，后续key只保存了相对于第一条记录的delta部分。需要首先拿到前缀编码段的第一条key（如111100，前4位为前缀），再与本key记录的delta（如01，后两位为delta）做拼接，才能获得完整的key（111101）内容。最后用完整key，与X作比较，以判定是否已经达到搜索目标位置。

Cache-Conscious Block Layout

CPU层级Cache

现代CPU的运算频率相较于服务器主内存的访问速度存在较大的差异，为了解决访问主存速度过慢的问题，现代CPU中一般会增加多个层次的cache，CPU cache使用SRAM制造且离CPU计算单元的距离更近，因此有着更快的访问速度。

有了CPU cache之后，CPU处理数据时首先尝试从cache中读取，如果找到就可以立即送入CPU处理，如果未找到，则会从下一层级的cache或者主存中读取，同时把读取的数据放入cache以便下一次使用. 现代CPU的一般使用三层cache(L1/L2/L3)，其中L1又分为指令cache和数据cache，其架构大致如下图所示：

从L1 cach 到 L2 cache 到 L3 cache，容量越来越大，离CPU计算核心越来越远，而速度则越来越慢。

由于数据在不同层级cache以及主寸之间的转移是以cache line(64Bytes)为单位, 而从不同层级cache的速度差异可以看出， 为了达到更快的数据访问速度，我们需要尽量发挥cache的局部性特征，将计算时序上相邻的数据在内存地址上安排在一起 ，目标是实现一次读取到高层次cache的数据即可供后续的多次运算使用。任何想达到最优计算性能的内存数据结构都需要遵循这个设计思想。

测试评估

IPC(instrunction per cycle)及instruction cache miss率对比：

1.在所有的并发下，新的DataBlock排布方式IPC都有提升。

2.新DataBlock排布方式，CPU的 L1 instrunction cache miss数值更高。因为相较于之前的记录排布方式，新格式的逻辑更复杂。同时为了节省空间，使用计算偏移的方式替代直接指针。最终导致l1-icache的miss上升。另一个有趣的现象是，随着并发增加，l1-icache的miss次数是下降的，考虑到并发执行的线程可以复用instruction cache, 这个结果是符合逻辑的。

而一个反常的结果是，所有并发场景，新的DataBlock排布方式CPU  L1 Data Cache的miss率反而是上升的，如下图所示：

猜测原因是新的2层B+数索引结构下，处理每一层节点都有显式的prefetch操作，由于l1-data-cache比较小，此时不同线程访问的data在l1-data-cache中会产生挤占效应，在代码中disable显式的prefetch操作验证了这个结论。

对比LLC的miss率和l1-data-cache的miss率，我们可以判定进一步提升性能的关键在提升l1-data-cache的命中率，即需要寻找到一个时间平衡点，让prefetch到l1-data-cache的数据在被挤占出cache之前刚好处理完。

以上是一个验证性测试(key长度8Byte,value长度8Byte)，从Perf的结果看，使用新的Block排布方式，点查场景DataBlock内查找的CPU消耗只是从35下降到30%左右，所以还有更多的潜力需要挖掘。

未来要解决的问题

本文验证了X-Engine中DataBlock内部索引格式一个优化实现，其有着更好的CPU cache友好性，由于只进行几个简单的对比测试，因此还有一些未明确的问题需要进一步的分析：

1.验证不同key-value长度场景下，此优化对性能的提升效果。

2.从perf结果看，LLC的命中率大幅增加，但是离CPU最近的L1-Data-Cache的cache miss有上升，L1 Data Cache的cache miss上升可能是导致性能提升幅度不大的原因，需要进一步的测试对比。

3.对于2层B+树的索引节点，需要寻找到一个最优的节点大小，此大小与key-value长度，并发数线程数，L1 Cache/L2 Cache/L3 Cache大小等因素相关。理论上可以对关系建立数学模型。

4.短key-value场景，新的编码格式，内存增加幅度可能较大(需要进一步量化)，此时一个方法是可以动态将部分热点DataBlock改造成cache友好但内存使用稍多的索引结构。而这里挑选哪些DataBlock需要精准的热点识别算法(我们可以利用LRU，在DataBlock LRU链表头部的数据页会更热),如何在两种DataBlock格式之间安全的转换也是需要探索的工程问题。

相关知识：InnoDB数据页格式及查找分析

InnoDB的数据页(Page)与X-Engine的DataBlock内部的查找算法类似。也包含尾部的restart 数组以及Page内部的记录内存堆。差别之处在于：InnoDB为了支持原地更新，其数据Page通常不会填满。记录在Page中并不是总是有序紧凑排列，而是通过记录之间的指针保持前后索引关系。

从记录查找过程看，针对X-Engine  DataBlock记录排布方式的优化方法对InnoDB的Page也是适用的。

但是一个比较关键的问题是InnoDB的数据Page是需要原地更新的，维护一个支持快速查找的索引结构会在更新有着较低的效率。根据已有的学术界研究结果，在索引中保存一定数量的空余slot用作后续更新及插入用，是一个可行的方法。

目前，MySQL(X-Engine) RDS已在阿里云上线，如何使用请点击 阅读全文 。 阿里巴巴实习生招聘即将开启，技术咨询及招聘询问，请联系旺德（微信w262730936）