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

哈希查找算法本身的计算开销：包括计算hash值和在hashtable中的某个slot进行链表的顺序查找，链表的顺序查找具有CPU cache不友好的问题。
维护LRU信息的计算开销：命中后需要调整entry在双向链表中的位置，还可能需要维护old pool和high priority pool的指针。
锁竞争的开销：Cache除了用于查找之外，还需要Insert和Evict ，因此查找和维护LRU信息时需要对分片加锁，当并发度很高、访问流量很大时，锁的竞争非常激烈。

PointSwizzling优化BufferPool的间接引用导致的CPU资源开销有一个方法，叫做PointSwizzling ，即使用直接指针代替使用PageID+HashMap查找的方法，针对X-Engine中Cache中哈希查找计算开销大的问题，我们引入直连指针进行数据访问， Cache仅用于数据管理，具体方案如下：

目标索引页/数据页/ExtentMeta在第一次装载进内存之后，我们增加一个直连指针指向目标对象(PointSwizzling), 这样可在下一次访问使用直连指针，而不必通过一次HashMap的计算。
目标内存对象并发访问和回收：多线程访问时，可能出现一个线程正在使用一个内存对象，而另一个线程触发了Cache淘汰，需要淘汰这个内存对象并回收这个内存对象的空间。这个问题有两种解决方案：基于Epoch的内存回收或者基于引用计数的内存回收，我们对两种方案都进行了测试，结论是基于Epoch的方式优于基于引用计数的方式（基于Epoch的具体实现见附录) 。原因是引用计数虽然是一个原子变量，但是多核环境下计数器的高频更新和读取依然存在因cache一致性导致的cache失效问题，导致性能不佳。
通过PointSwzzling ， X-Engine在内存部分的数据访问形态就和全内存数据库一样具有非常高的CPU使用效率。而当存在数据汰换时，可以继续使用BufferPool保持内存数据的命中率。 PointSwizzling引入之后， X-Engine在KV接口上全内存命中场景的点查性能提升了近60% 。
多核CPU上的Cache访问数据页编码以及PointSwizzling都是着眼于单线程运行过程中的优化方法，其中数据页的新编码提升了CPU 的Cache命中率，而SIMD和PointSwizzling都是提升了CPU指令的执行效率，即提升了程序的IPC 。
分析X-Engine的整体执行框架，我们发现另一个导致CPU Cache利用率低问题：
多线程并发问题X-Engine作为RDS MySQL以及PolarDB MySQL中的一个存储引擎，其执行框架与MySQL类似，使用One-thread-per-client或者采用线程池模式。特点就是任何线程均可以访问所有表中的数据，在现今动辄32/64/128core的服务器上，执行线程的高度并发导致如下一些问题：

CPU cache的低效率。例如在128core的服务器上，我们并发访问1000张表，则同一内存数据会同时在多个CPU core的L1/L2 cache中被加载，导致cache利用率较低。同时如果存在更新，在多核上的cache一致性也会带来较大的开销。线程在不同的core上调度发生context switch ，同样会造成CPU cache频繁大量的失效。
线程同步的开销较大。内存数据都是共享的，访问和修改（例如上面提到的Cache查找、插入和淘汰）需要锁的保护，锁竞争的开销很大。对于使用原子操作进行的线程同步，原子变量在多个CPU core的L1/L2中同步状态需要进行数据传输和跨核通信，开销也很大。

针对此类问题，业界先驱如H-Store,VoltDB给出了一条可供参考的优化方法
多核Shared-nothing架构我们对X-Engine的执行框架做如下改造：
限制读数据的执行线程数为可用CPU core数目，并进行绑core处理，特定线程只能在特定的core上执行，避免频繁的线程调度。