小镇的夕阳|深度 | X-Engine的In-Memory读性能优化( 二 ) 作者：顾绅/北楼背景虽然同为LSM-tree

Block编码及SIMD数据页编码及其问题与Rockdb/InnoDB数据页格式类似， X-Engine索引页和数据页具有相同的格式。每个Block顺序存储KV pairs ，并对key进行分段前缀压缩（每个段称为restart interval）， KV pairs之后有一个restart array ，存储每个restart interval在Block中的offset 。搜索时首先会在restart array中进行二分查找，定位到可能包含target key的最小的restart interval（下图1、2、3、4），再从这个restart interval开始顺序比较（下图5），如下图所示：
查找过程本质上就是指针数组中的二分查找， restart array中存储的restart interval的offset可以理解为指向restart interval的指针， perf分析显示，该过程存在如下两点问题：
1.内存访问在前面的KVs和restart array之间跳跃。 restart array中仅存储restart interval的offset ，在查找时需要根据offset访问BlockContent的相应位置获得key ，这样跳跃的内存访问没有规律（每次restart array和实际key的距离随机）且间隔多个cache line ，无法充分利用CPU cache ，带来一定的访存开销。
2.前后两次比较无法利用CPU cache 。除了最后一次比较之外，每次比较的index key和前一次比较的index key间隔都可能超过一个cache line ，因此无法利用前一次的CPU cache ，导致访存开销很大。
Cache友好的Block编码针对指针数组中二分查找CPU cache不友好的问题，尝试将频繁访问的数据页转换成CPU cache友好的两层B+树结构，将访问时序上前后相邻的记录在物理空间上聚簇在一起，其逻辑存储形式如下：
物理存储形式如下：
构建时按物理存储形式顺序构建每个node ，查找时使用类似B+树的查找方式。 CPU cache友好的两层B+树从三个角度提升CPU cache利用效率：

使内存组织的空间局部性和访问顺序的时间局部性一致。使用B+树作为索引结构，直接在B+树中存储kv的内容，并在节点内采用顺序查找。 B+树中访问顺序相邻的节点存储在同一个node中， kv内容直接存储在node中避免了访存地址跳跃的问题，顺序查找进一步保证了时间局部性和空间局部性的一致，并且访问顺序和prefetch的顺序一致，尽可能地保证了prefetch在恰当的时机进行。计算开销方面， B+树查找算法的时间复杂度和二分查找相同，因为node内key的数量较少，顺序查找和二分查找计算开销接近。
提升cache size与数据量的比值：压缩存储元信息。例如使用2Byte存储offset而不是存储leaf node的指针。
选择合适的B+树层数：B+树层数为2 ， fanout为N开根号。每层节点至少会产生一次cache miss ，过多的层数会带来更多的cache miss ，而1层的B+树node过大，计算开销和CPU cache效率实际上和restart array差不多，当层数为2时， CPU cache对in-flight的load请求和prefetch的支持可以让每层node访问仅产生1-2次cache miss ，是CPU cache效率最佳的选择。

这种编码格式对range查询也能完好的支持，对range查询的第一次seek操作，能起到和点查类似的加速效果，而对于后续的scan迭代，也无负面影响。此部分优化更详细的新可以参见公众号前一篇文章：数据库存储引擎如何利用好CPU缓存