StarRocks 技术内幕：向量化编程精髓
作者：康凯森，StarRocks PMC，负责查询方向的研发
本文是对我在 StarRocks 线下 MeetUp 演讲的整理，主要分为三部分：部分简要介绍向量化的基础知识，第二部分讲解数据库如何进行向量化，后是 StarRocks 向量化实践后的一些粗浅思考。
#01
向量化为什么可以提升数据库性能？
—
本文所讨论的数据库都是基于 CPU 架构的，数据库向量化一般指的都是基于 CPU 的向量化，因此数据库性能优化的本质在于：一个基于 CPU 的程序如何进行性能优化。这引出了两个关键问题：
2. 哪些因素会影响 CPU 性能
个问题的答案可以用以下公式总结：CPU Time = Instruction Number * CPI * Clock Cycle Time
Instruction Number 表示指令数。当你写一个 CPU 程序，终执行时都会变成 CPU 指令，指令条数一般取决于程序复杂度。 CPI 是 （Cycle Per Instruction）的缩写，指执行一个指令需要的周期。 Clock Cycle Time 指一个 CPU 周期需要的时间，是和 CPU 硬件特性强关联的。
我们在软件层面可以改变的是前两项：Instruction Number 和 CPI。那么问题来了，具体到一个 CPU 程序，到底哪些因素会影响 Instruction Number 和 CPI 呢？
我们知道 CPU 的指令执行分为如下 5 步：
5. 结果写回寄存器
其中 CPU 的 Frontend 负责前两部分，Backend 负责后面三部分。基于此，Intel 提出了 《Top-down Microarchitecture Analysis Method》的 CPU 微架构性能分析方法，如下图所示：
Top-down Microarchitecture Analysis Method 的具体内容大家可以参考相关的论文，本文不做展开，为了便于大家理解，我们可以将上图简化为下图（不完全准确）：
即影响一个 CPU 程序的性能瓶颈主要有4大点：Retiring、Bad Speculation、Frontend Bound 和 Backend Bound，4个瓶颈点导致的主要原因（不完全准确）依次是：缺乏 SIMD 指令优化，分支预测错误，指令 Cache Miss， 数据 Cache Miss。
再对应到之前的 CPU 时间计算公式，我们就可以得出如下结论：
而数据库向量化对以上 4 点都会有提升，后文会有具体解释，至此，本文从原理上解释了为什么向量化可以提升数据库性能。
#02
向量化基础知识
—
注意，在第二个章节里面，向量化一词可以理解为和 SIMD 等价，仅指狭义上的 CPU SIMD 向量化，与数据库领域广义的向量化含义不同。
SIMD 是 Single Instruction Multiple Data 的缩写，指单个指令可以操作多个数据流，与之相对的是传统的 SISD，单指令单数据流。
如上图所示，对于简单的 A + B = C，假如我们要计算 4 组加法，传统的 SISD 需要执行 8 次 Load 指令 (A 和 B 分别4次)、4 次 Add 指令、4 次 Store 指令。但当我们使用 128 位宽的 SIMD， 我们只需要 2 次 Load 指令、1 次 Add 指令、1 次 Store 指令，这样理论上就可以获得 4 倍的性能提升。而目前的向量化寄存器位宽已经发展到 512 位，理论上 Int 的加法操作就可以加速 16 倍。
如前文所述，SIMD 指令会带来巨大的性能提升，数据库开发人员自然需要理解并掌握如何进行 SIMD 编程。
种是编译器自动向量化，代码不需要做特殊处理和改动，编译自动将默认的标量代码转换成向量化代码。但编译器默认只能处理比较简单的程序，具体支持的 Case 大家可以在网上搜索，资料很多；
第二种是我们给编译器一些 Hint，给编译器更多的信息和上下文，编译器也可以生成 SIMD 指令；
第三种是使用像 OpenMP 或者 Intel Cilk 这种并行编程 API，开发者可以加一些 Pragma 来生成 SIMD 指令；
第四种是使用一些 SIMD Intrinsics 的包装类；
第五种是直接使用 SIMD Intrinsics 编程；
后一种是直接写汇编代码。
在 StarRocks 项目中，我们向量化的原则是尽可能触发编译器的自动向量化，也就是种和第二种，对于不能自动向量化但是性能又很关键的操作，我们会通过 SIMD Intrinsics 的方式手动向量化。
关于如何触发编译器的自动化，如何给编译器加 Hint 触发向量化以及如何通过 SIMD Intrinsics 的方式手动向量化大家可以参考我个人博客《数据库学习资料》向量化部分的资料，本文不再赘述。
《数据库学习资料》：https://blog.bcmeng.com/post/database-learning.html
当一个项目代码比较复杂时，如何确保代码触发向量化是很常见的问题。 我们可以通过两种方式来检查：
种是给编译器加一些编译选项，编译器会输出某些代码是否触发向量化，以及没有向量化的原因。比如 GCC 编译器，我们可以加入 -fopt-info-vec-all 或者 -fopt-info-vec-optimized，-fopt-info-vec-missed，-fopt-info-vec-note 编译选项。效果如下图所示：
—
StarRocks 的向量化引擎从写下行代码到成为一款成熟、稳定、的查询执行器，已经有 2 年多的时间，以我们的经验来看，数据库的向量化并不仅仅是触发 CPU 的 SIMD 向量化，而是一个巨大的、系统化的性能优化工程。
数据库向量化的挑战主要有以下几点：
6. 整体性能提升 5 倍以上：所有的算子和表达式性能都要提升 5 倍以上，意味着全面地、系统地性能优化，所有重要的算子和表达式性能都不能有短板
数据库的向量化在工程上主要体现在算子和表达式的向量化，而算子和表达式的向量化的关键点就一句话：Batch Compute By Column, 如下图所示：
对应 Intel 的 Top-down 分析方法，Batch 优化了 分支预测错误和指令 Cache Miss，By Column 优化了 数据 Cache Miss，并更容易触发 SIMD 指令优化。
Batch 这一点其实比较好做到，难点是对一些重要算子，比如 Join、Aggregate、Sort、Shuffle 等，如何做到按列处理，更难的是在按列处理的同时，如何尽可能触发 SIMD 指令的优化。每个算子的按列处理和 SIMD 指令优化我们会在之后的 《StarRocks 查询源码解析》系列文章中详细解释。
前面提到，数据库向量化是一个巨大的、系统的性能优化工程，两年来，我们实现了数百个大大小小的优化点。我将 StarRocks 向量化两年多的性能优化经验总结为 7 个方面 （注意，由于向量化执行是单线程执行策略，所以下面的性能优化经验不涉及并发相关）：
1. 高性能第三方库：在一些局部或者细节的地方，已经存在大量性能出色的开源库，这时候，我们可能没必要从头实现一些算法或者数据结构，使用高性能第三方库可以加速我们整个项目的进度。在 StarRcoks 中，我们使用了 Parallel Hashmap、Fmt、SIMD Json 和 Hyper Scan 等的第三方库。
2. 数据结构和算法：高效的数据结构和算法可以直接在数量级上减少 CPU 指令数。在 StarRocks 2.0 中，我们引入了低基数全局字典，可以通过全局字典将字符串的相关操作转变成整形的相关操作。如下图所示，StarRcoks 将之前基于两个字符串的 Group By 变成了基于一个整形的 Group By，这样 Scan、Hash 计算、Equal、Memcpy 等操作都会有数倍的性能提升，整个查询终会有 3 倍的性能提升。
3. 自适应优化：很多时候，如果我们拥有更多的上下文或者更多的信息，我们就可以做出更多针对性的优化，但是这些上下文或者信息有时只能在查询执行时才可以获取，所以我们必须在查询执行时根据上下文信息动态调整执行策略，这就是所谓的自适应优化。下图展示了一个根据选择率动态选择 Join Runtime Filter 的例子，有 3 个关键点：
a. 如果一个 Filter 几乎不能过滤数据，我们就不选择；
b. 如果一个 Filter 几乎可以把数据过滤完，我们就只保留一个 Filter;
c. 多只保留 3 个有用的 Filter
4. SIMD 优化：如下图所示，StarRcoks 在算子和表达式中大量使用了 SIMD 指令提升性能。
5. C++ Low Level 优化：即使是相同的数据结构、相同的算法，C++ 的不同实现，性能也可能相差好几倍，比如 Move 变成了 Copy，Vector 是否 Reserve，是否 Inline， 循环相关的各种优化，编译时计算等等。
6. 内存管理优化：当 Batch Size 越大、并发越高，内存申请和释放越频繁，内存管理对性能的影响越大。我们实现了一个 Column Pool，用来复用 Column 的内存，显著优化了整体的查询性能。下图是一个 HLL 聚合函数内存优化的代码示意，通过将 HLL 的内存分配变成按 Block 分配，并实现复用，将 HLL 的聚合性能直接提升了 5 倍。
7. CPU Cache 优化：做性能优化的同学都应该对下图的数据了熟于心，清楚 CPU Cache Miss 对性能的影响是十分巨大的，尤其是我们启用了 SIMD 优化之后，程序的瓶颈就从 CPU Bound 变成了 Memory Bound。同时我们也应该清楚，随便程序的不断优化，程序的性能瓶颈会不断转移。
下面的代码展示了我们利用 Prefetch 优化 Cache Miss 的示例，我们需要知道，Prefetch 应该是后一项优化 CPU Cache 的尝试手段，因为 Prefetch 的时机和距离比较难把握，需要充分测试。
—
相关文章