Micro architectural analysis of in memory OLTP Revisited (ZH)
最近读了这篇文章：Micro-architectural analysis of in-memory OLTP: Revisited , SIGMOD‘21
数据库优化，业务侧常见动作包括调参、分库分表、业务改造等；内核开发者会更深的针对芯片或者硬件的能力做面向场景的内核优化，比如CPU有了大的缓存和大位宽的SIMD，就可以做向量化SQL执行器，比如CPU动辄几百核，就需要做各类NUMA-aware的数据结构和线程亲和，比如HDD、SSD、Flash、AEP各种介质都有不同的IO特征和性能，就会实现新的索引、IO策略。
所有这些优化动作都是要建立在系统的性能观测上的，性能数据观测和采集领域可能比优化还更为庞大的多，操作系统的top/htop/sar等资源监控工具、perf等PMU的软硬件事件采集工具、数据库本身的性能视图（SQL Server的DMV、Oracle的AWR、MySQL的performance schema）等等都是最常用会用来采集热点，收集数据，定位瓶颈。
还有一类历史悠久的性能观测的方法论，似乎已经被很多人淡忘了，那就是workload的微架构分析。回答的是从微架构的角度看，资源使用是什么样的，瓶颈在哪里，宏观上是否可以做软件优化，甚至有条件的话，是否可以做芯片优化？最近几年可能比较有名的工作是Google的Profiling a warehouse-scale computer，从微架构的角度去看数据中心场景下的各种负载，发现数据密集业务场景下的dcache miss过高。至于微架构分析中一些关键观测对象，可以从下面这张图中感受一下，图来自计算机体系结构：量化研究方法（第6版)
本篇论文Micro-architectural analysis of in-memory OLTP: Revisited 从名字可以看出来是续作，前一篇是Micro-architectural analysis of in-memory OLTP，使用类似的方法观测同样的数据库和负载，区别在于CPU的型号从至强的E5–2640(Ivy Bridge)升级到了至强E5–2680 v4(Broadwell)。
OLTP的特征
现在最通用的OLTP数据库仍然是disk-based的数据存储，比如MySQL和PG，根据笔者我个人的经验，跑TPCC时候IPC在0.7~0.8之间，也就是每个时钟周期平均只跑0.7~0.8条指令，伴随着比较高的LLC miss(20%+)和frontend-bound/backend-bound占比。论文中援引了过去多年的数据库workload分析，也总结出了类似的结论。
OLTP benchmarks are famous for their suboptimal microarchitectural behavior. There is a large body of work that characterizes OLTP benchmarks at the micro-architectural level. They all conclude that OLTP exhibits high stall time (> 50% of the execution cycles) and a low instructions-per-cycle (IPC) value (< 1 IPC on machines that can retire up to 4 instructions in a cycle). The instruction cache misses that mainly stem from the large instruction footprint of transactions are the main source of the stall time, while the next contributing factor is the longlatency data misses from the last-level cache (LLC).
disk-based的数据库下对于workload观测的一个影响是面向IO特征的数据结构，比如B-tree, B+tree，索引组织表，堆表，LSM tree等等，他们的数据结构在CPU访存的角度看来特征是完全不一样的；另一个是IO的runtime对于系统表征的影响，比如同步IO、异步IO、系统调用等等要求CPU的调度策略会影响缓存的新鲜度。所以研究内存数据库一方面对于workload分析更纯粹，另一方面内存数据库的使用场景也越来越多，成熟的产品也越来越多。因此本文对于内存数据库的特征分析还是很有意义的。
Considering the lighter components, cache-friendly data structures, and cleaner codebase of in-memory systems, one expects them to exhibit better cache locality (especially for the instruction cache) and less memory stall time. Due to the distinctive design features of the in-memory systems from the disk-based ones, however, it is not straightforward to extrapolate how OLTP benchmarks behave at the microarchitectural level when run on an in-memory engine solely by looking at the results of previous studies.
论文分析观测了三个内存数据库和两个磁盘数据库，虽然没有指明道姓，但是从特征描述来看，DBMS M应该指的是Hekaton(哈希索引、Bw tree、JIT)，DBMS N指的是VoltDB（红黑树）。Silo用的是Masstree。磁盘数据库是DBMS D（应该就是SQL Server）和Shore-MT。我在后续描述中会直接称呼它们的原名，如果推断错误，概不负责哈。
微架构观测指标
观测这些微观指标主要回答这几个宏观问题：
- CPU主要花在访存延迟还是指令的retire（执行）？
- 访存延迟来自于指令还是数据？
- 数据库的容量大小对于这些观测指标的影响是什么？
- 事务大小对于这些观测指标的影响是什么？
CPU cycles
一图胜千言，有如下结论：
- 小数据量（1MB到10MB）下，retiring的占比差不多，因为数据大部分可以放在LLC里，CPU只需要干活，不需要太多的访存。
- 大数据量（10G到100G）下，retiring的占比减少，因为需要花更多的时间去处理cache miss做访存。内存数据库和磁盘数据库的retire占比都小于30%，都是data stall-bound的场景。
- 由于Intel的架构升级，IFU的优化大大减少了Icache miss率，所以Shore-MT在Ivy Bridge时代还是Icache-stall-bound，在Broadwell下变成了Dcache-stall-bound。
“State-of-the-art advances in branch prediction algorithms enable accurate fetch requests to run ahead of micro-operation supply to hide instruction TLB and cache misses.”. Hence, instruction fetch unit keeps supplying instructions even though there is an instruction cache miss, which allows overlapping the instruction cache miss latency with useful work.
4. DBMS D (SQL Server)和DBMS M (Hekaton)的Icache-stall占比都太高了，因为legacy codebase太多了（NTDBMS代码仓300G，懂的都懂）。Hekaton有自己的codegen执行器，存储引擎，但是外壳和runtime（比如SQLOS）还是共享的，所以instruction footprint特别大，进而导致Icache容易被换入换出，造成Icache-stall。Hekaton的吞吐性能是SQL Server的三倍左右，所以也可以看到Hekaton的Dcache使用率比SQL Server好上很多。
5. DBMS N(VoltDB)没有legacy的代码，所以也没有多少instruction footprint。跟之前的原因一致，IFU的升级也让VoltDB从Icache-stall变成了Dcache-stall。
6. Silo的retiring占比高，主要因为它只是个存储引擎，少了数据库的外围组件，但在数据量大的时候，也不可免俗的成为Dcache-bound。
7. Silo的branch misprediction占比很高，主要是因为虽然大家都要做树的遍历，但是代码上的简单导致Silo的Icache stall太低，所以同比分支预测失败的占比升高。
8. 大家都有10–15%的decoding-stall，主要是Intel的DSB太小。这里可以理解为前端译码的缓存太小了。
内存数据库 vs 磁盘数据库 break down
在小数据量（1MB）和大数据量（100GB）情况下，磁盘数据库的各模块执行时间类似，buffer manager和锁闩的时间占比是最多的，Dcache stall也主要来自于buffer manager；VoltDB由于没有缓冲区管理，加上分区机制以及deterministic concurrency control（单线程），所以主要的时间和主要的Dcache stall都来自于在事务建立和初始化阶段。另外在100GB的数据量下，VoltDB的索引查找时间显著增加，从占10%增加到44%。结论就是Shore-MT需要架构重构来减少data footprint，VoltDB需要优化索引组织。下图是1MB数据量下的对比图。
事务大小的影响
文章中事务大小指的是每个事务中取访问的行数多少。对于基本上所有的数据库，随着访问行数的增加，Icache-stall的占比就越少，Dcache-stall的占比就越多。这也不难理解，一方面执行器和存储引擎的代码流比较固化对Icache更友好，另一方面访问更多的行数，主要压力都在存储引擎，更容易造成Dcache miss。
测试模型TPC-B vs TPC-C
TPC-B下，内存数据库性能显然由于磁盘数据库。在内存数据库领域内，Silo > VoltDB > Hekaton。这个结论也无悬念。 TPC-C下的微架构行为与TPC-B类似，SQL Server和Hekaton的Icache stall很高（legacy code），其余都是Dcache stall或者资源冲突，由于TPC-C与之前的自作benchmark相比locality更好，所以retiring的占比更高。
其它数据库特征对微架构的影响
文章还分析了其它数据库组件或者特征对微架构的影响，总结一下。
- JIT JIT可以大幅优化Icache stall （减少~50%），因为：1. 减少虚函数开销（vtable）2. inline函数，减少分支预测 3. 利用编译器自身的优化特性。
- 索引类型 B-tree与哈希索引对比，如果负载对数据的随机访问要求比较高，那么B-tree会有更多的Dcache-stall占比（因为lookup较多）。
- 数据类型 只有Hekaton下处理字符串类型的Dcache-stall比长整型占比高（legacy code处理内存操作开销较大）。
- 多线程 SQL Server的Icache stall依旧很高，其余都是Dcache stall。这也比较容易理解，主要还是跟代码的footprint有关。Hekaton的多线程Icache stall比单线程要少很多，这里主要可能是Hekaton下的指令locality更好（毕竟Hekaton有自己的self contained的SQL执行器和较轻的引擎，总代码行数在SQL Server中占比很低）。
高级特性（芯片或者硬件）
超线程
对于多线程的workload，超线程几乎是无脑有收益的，最关键的就是可以在Dcache/ICache stall时候切出去做其它任务，提升整体的ILP。不只是数据库，数据密集的场景基本都是如此。
超频
主频提升的是cycle时间，而访存的时间主要是由core的LSU与DRAM之间的物理延迟决定的，属于offcore，如果算上多NUMA的架构下的跨DIE的开销，更不是CPU cycle能决定的。所以提升主频主要提升的ALU-bound的场景，所以文章观测到OLTP下，大家都没有收益。
硬件预取
效果有限。随机访问场景下，spatial locality不足以提升预取命中率。对于高性能的数据结构，软件实现过程中已经考虑了prefetching。
后记
这篇文章很长，抛开reference有24页，但其实核心就是观测了不同场景下的微架构数据，做了一些归纳和总结。传统上大家更熟悉的这种分析方法就是Intel的Top Down分析方法论，从指令生命周期中的Frontend-Bound/Backend-Bound/Bad-speculation/Retiring四大类层层展开。本文并没有从这里出发，而是盯着data stall和retiring去看，其实本质是一样的。
这类分析方法其实对数据库内核的开发者来说意义相对比较有限，我相信大部分内核开发或者优化人员不会去用这套方法论去做优化，这套方法论也不会明确告诉内核人员哪个模块执行时间长，哪个锁是热点。相对来说，对底层微架构的设计人员来说意义还会更大。随着数据中心场景被云收编，而云厂商又在疯狂加码定制自己的芯片和硬件，通过这套宏观方法论是很有借鉴意义的。比如Apple M1有能力根据自己的场景设计了变态的架构，对数据库和数据中心场景也是很有借鉴意义的，未来Graviton系列或者微软的ARM芯片也一定会根据自己的workload分析设计适合自己的微架构。
