数据库存储引擎如何利用好CPU缓存 | X-Engine内核
source link: http://mp.weixin.qq.com/s?__biz=MzU0NDcwNjQxNA%3D%3D&%3Bmid=2247483874&%3Bidx=1&%3Bsn=72a15b8d16102826a8005cb74df8c2f5
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文探讨如何优化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作比较，以判定是否已经达到搜索目标位置。
现有查找算法的问题
分析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友好性原则的极端反例。
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的平方根。
测试评估
测试环境及测试方法
服务器配置：
-
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%左右，所以还有更多的潜力需要挖掘。
未来要解决的问题
本文验证了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）
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK