内核干货 | 数据库存储引擎如何利用好CPU缓存?

由于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中记录编码格式如下图所示:
内核干货 | 数据库存储引擎如何利用好CPU缓存?

此格式的几个基本特点:

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步执行:

内核干货 | 数据库存储引擎如何利用好CPU缓存?

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,其架构大致如下图所示:

内核干货 | 数据库存储引擎如何利用好CPU缓存?

从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,在内存物理地址上也保存在一起。

内核干货 | 数据库存储引擎如何利用好CPU缓存?

上图是该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的变化显著。

内核干货 | 数据库存储引擎如何利用好CPU缓存?

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, 这个结果是符合逻辑的。

内核干货 | 数据库存储引擎如何利用好CPU缓存?

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

内核干货 | 数据库存储引擎如何利用好CPU缓存?

猜测原因是新的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中并不是总是有序紧凑排列,而是通过记录之间的指针保持前后索引关系。

内核干货 | 数据库存储引擎如何利用好CPU缓存?

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

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

目前,MySQL(X-Engine) RDS已在阿里云上线,如何使用请点这里

相关阅读:前沿干货 | X-Engine:RDS MySQL的新存储引擎


直播预告

3月26日 15:00-16:00

邀您一同见证

云数据库SQL Server 2019版重磅发布

全面提升性价比及数据库能力

点这里

即可预约观看直播

上一篇:iOS,Objective-C,相册功能的实现。


下一篇:Shell脚本的书写规范与优秀的开发习惯