由于X-Engine数据页编码格式和查找算法与很多数据库引擎(如InnoDB)是类似的，因此文中提出的方法对使用类似数据页格式的存储引擎都是普适的。
1、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作比较，以判定是否已经达到搜索目标位置。
现有查找算法的问题
分析DataBlock格式及二分查找算法的执行过程，可以发现两个主要问题：
restart数组只存储记录的偏移而不存储key的实际内容，每次二分查找中选中的pivot点指向的offset位置，与restart数组自身所在的内存位置存在较大的偏移（最大接近8KB，即第一次二分时,DataBlock大小的一半)。查找中，CPU访存地址在restart数组和DataBlock中实际记录存储位置之间跳跃。
DataBlock搜索过程所访问到的key的offset，也是在DataBlock的大小（16KB）范围内跳跃。虽然二分搜索每次能将需要搜索的内存空间减少一半，但想要达到前后相邻的两次查找比较，第二次比较利用前一次的CPU cache，则前后两次访问的地址之差要限定在一个CPU cache line大小之内。在这个过程之前，二分搜索过程需要迭代多次，每次必然会发生访存的cache Miss.
按照CPU cache友好的程序设计原则，在访问时序上相近的数据，在内存物理地址上最好相邻，如此可以充分发挥CPU prefetcher的效用，减少CPU cache miss。DataBlock的二分查找算法，无论是restart数组的内存地址和key的内存地址之间，还是前后两次二分搜索访问的key的内存地址之间，都在计算时序上相邻，内存地址不相邻。此格式和查找过程是CPU cache友好性原则的极端反例。
2、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的数据即可供后续的多次运算使用。任何想达到最优计算性能的内存数据结构都需要遵循这个设计思想。
2层B+树索引
针对前面的分析，要提升数据页上的查找效率，需要重排X-Engine DataBlock格式，并达到如下两个效果：
key内容和索引信息在内存物理地址上相邻。
搜索路径上，访问时序上相邻的key，内存物理地址上也相邻。
要解决第一个问题，最直接的方法就是改变key的存储位置，将key的内容提取出来，并保存在DataBlock尾部的restart数组中。这样只需在保存有restart数组和key内容的内存范围内执行二分查找，由于去除了长度较大的value的影响，此搜索区域更小，cpu cache效率更高。
要解决第二个问题，更改二分搜索算法，前后相邻的比较过程中的key保存在一起。一个很容易想到的解决办法是：将二分查找过程中相邻的节点，在内存保存在一个连续地址上，作为第一次筛选的界标，大幅缩小搜索范围（想象一下B树）。
综合上面的分析，B+树可以满足需求，对DataBlock内部的索引和查找过程做出如下简单的修改：
1.去除全局restart数组，提取出restart数组中元素所对应的key内容与restart偏移保存在一起，如此可以避免二分查找时跳跃到DataBlock中间位置进行访问。
2.将原有一维的restart数组，改造为两层的B+树索引结构。非叶子节点为restart数组二分搜索算法中，逻辑比较上前后相邻的key组成。节点内部的key依然从小到大排列。这样可以保证逻辑前后响铃被访问的key，在内存物理地址上也保存在一起。
上图是该2层B+树查找结构的逻辑布局图(物理上他们是顺序存储)。实际存储方式是按层数遍历算法顺序保存每个节点，指向子节点的指针使用相对内存首地址的offset而不是指针，因为考虑到最大16KB的DataBlock大小，offset可以用更少的字节数来表示，代价是多了一步计算过程。
采用两层B+树的原因有两个：
1.如果采用一层，则root节点会非常大，特别是在key比较长时，其搜索效率与原有DataBlock的类似。
2.采用更多层次的B+树也不合适，一方面层次增加，搜索每一层的节点都会导致cache miss. 另一方面X-Engine 16KB的DataBlock大小保存的记录有限, 不需要太深层次的树结构，而且我们的目标CPU平台L1 Data Cache大小在几十KB级别，L2 Cache在MB级别，这允许我们使用较大的节点大小。
索引查找效率分析
除了使用2层B+树索引替换原有的restart数组+key偏移的索引结构, 为了进一步提升效率，在代码实现上做如下设计：
在一个有N个条记录的的DataBlock上，构建的索引B+树的节点中key的数目为N的平方根。这样可以保证在B+树的第一层和第二层每个节点有均等的大小。
在访问每一层B+树节点前, 手动执行调用prefetch指令。将整个节点预取到CPU cache中，由于一个B+树节点必然比CPU的cache line(64B)大，此步会触发数个in flight的读内存请求。
实际运行中最优的节点大小取决于多个因素，key的长度，DataBlock中记录的数目N，运行时的线程并发度以及L1/L2 Cache等对最优节点大小都有影响。
同时如果我们对一个节点的preload速度太快，而CPU在此节点上的搜索时间过长，则preload进cach中的数据可能被其他线程线程所淘汰（在L1/L2/L3的每一层都是如此）。而如果preload太慢，比在CPU在此节点上的搜索速度慢，则可能发生发生cache miss， CPU陷入stall，也对速度不利。
为了简化测试复杂度，我们设置了固定的节点内key数目为N的平方根。
3、测试评估
测试环境及测试方法
服务器配置：
CPU配置:Intel(R) Xeon(R) Platinum 8163 CPU @ 2.50GHz， 24core48threads， 2Socket.
L1-Cache:32KB Data Cache , 32KB Instruction Cache
L2 Cache:1MB, L3 Cache 32MB
RAM:768GB，关闭NUMA
测试机及统计采样方法:
创建32张表，每张表插入100W条记录，然后执行一次全表顺序读，将所有数据预热缓存到内存，并为每个DataBlock构建好Cache-Consicious的页内索引结构。
使用不同的线程数测试ReadOnly OPS(operation per second)，共7组，线程数分别为2,4,8,16,32,64,128。每组测试20S. 测试启动5S后统计CPU各层级cache的的状态以及IPC等指标，采样时间5S。
测试结果及分析
通过X-Engine的KV接口测试点查场景的性能，以检验DataBlock格式重构之后执行查询时的性能以及cache命中率表现，测试仅验证readonly，unique key distribution场景。
最终吞吐及CPU cache miss率：
1.在所有并发下，新的Block排布方式均有有性能优势，在32线程时，点查吞吐最大提升17%。
2.Last Level Cache的miss率，在新的Block排布方式下下降非常明显，在32线程时，LLC miss比率从27%下降到15%。不过，有一个疑问点是性能的提升没有LLC miss的变化显著。
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%左右，所以还有更多的潜力需要挖掘。
4、未来要解决的问题
本文验证了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格式之间安全的转换也是需要探索的工程问题。
5、相关知识：InnoDB数据页格式及查找分析
InnoDB的数据页(Page)与X-Engine的DataBlock内部的查找算法类似。也包含尾部的restart 数组以及Page内部的记录内存堆。差别之处在于：InnoDB为了支持原地更新，其数据Page通常不会填满。记录在Page中并不是总是有序紧凑排列，而是通过记录之间的指针保持前后索引关系。
从记录查找过程看，针对X-Engine DataBlock记录排布方式的优化方法对InnoDB的Page也是适用的。
但是一个比较关键的问题是InnoDB的数据Page是需要原地更新的，维护一个支持快速查找的索引结构会在更新有着较低的效率。根据已有的学术界研究结果，在索引中保存一定数量的空余slot用作后续更新及插入用，是一个可行的方法。
目前，MySQL(X-Engine) RDS已在阿里云上线，如何使用请点这里。
直播预告
3月26日 15:00-16:00
邀您一同见证
云数据库SQL Server 2019版重磅发布
全面提升性价比及数据库能力
即可预约观看直播
