问题在于内存延迟，笨蛋

# 问题在于内存延迟，笨蛋 · Pivot 博客 来源：https://pivotlake.io/blog/its-the-memory-latency-stupid 当你看到数据库的 CPU 使用率达到 100% 时，它*究竟*在做什么？为了便于理解，我们习惯于把 CPU 看作是按顺序执行代码的机器，但实际上，CPU 是极其复杂的庞然大物；它们可能同时执行多条指令，有时也可能一条指令都不执行\(尽管控制台显示使用率为 100%\)。由于 CPU 能做的事情很多，一个使用率为 100% 的 CPU，实际完成的工作可能远少于另一个使用率同为 100% 的 CPU。只有在没有任何任务\(Linux 任务\)需要 CPU 时间时，CPU 才会被视为“空闲”；这并不意味着 CPU 本身的处理能力已经被充分利用。那么，为什么 CPU 看起来已经达到 100%，却仍未得到充分利用呢？答案通常是**内存**。内存访问比 CPU 内部操作慢几个数量级。为了让你直观地理解这个差距，现代 CPU 每纳秒大约可以处理 4\-8 条指令，而一次 RAM 内存访问大约需要 50\-100ns。帮你算一下，这意味着每完成*一次* RAM 内存访问，现代 CPU 就能执行大约 400\-800 条指令。CPU CPU 核心 每纳秒 4–8 条指令 L1 缓存 约 1 ns 约 64 KB · 每次访问相当于约 4–8 条指令 L2 缓存 约 3–4 ns 约 1 MB · 每次访问相当于约 15–30 条指令 L3 缓存 约 10–15 ns 最高可达几百 MB · 每次访问相当于约 50–100 条指令 DRAM 约 50–100 ns 数 GB · 每次访问相当于约 400–800 条指令 因此，CPU 从设计之初就在想办法绕开这个问题。最明显的解决办法就是 CPU 缓存。CPU 缓存让内存比 RAM 更靠近 CPU，实际上就直接集成在 CPU 芯片中。距离最近的缓存\(L1 缓存\)每次内存操作大约需要 1ns，比 RAM 快 50\-100 倍！当然，这里的“问题”是 CPU 缓存相当小；现代 CPU 的 L1 缓存大概只有约 64KB，而距离更远的缓存，即使在顶级处理器上，最大也只有几百 MB。优秀的数据库会尝试以较小的“块”为单位处理数据，以充分利用缓存，你也经常会听到，缓存利用率是性能工程最关注的问题之一。让我们看看 GROUP BY 聚合，以便更好地理解缓存利用率。在 GROUP BY 中，我们需要获取一个数据集，按某一列\(或多列\)进行分组，并执行某些聚合操作\(例如计数，或对另一列求和\)。“朴素”的做法可能是创建一个以分组键为键、不断增大的 HashTable。对于每一条新行，检查该键是否存在；如果存在，就找到对应的聚合结果并进行更新。很简单，对吧？问题是，如果你有数百万个不同的分组，缓存就几乎完全派不上用场了！几乎每次 HashTable 访问都会是一次需要访问 RAM 的“冷”访问。这意味着，虽然你的 CPU /看起来/ 已经得到 100% 的利用，但实际上，它会不断等待冷内存访问完成。为了演示这一点，我们要拿先进的 Pivot 引擎来大肆折腾一番！我们会移除所有复杂逻辑，用简单的实现取而代之：`` fn consume( &mut self, batch: RecordBatch, _sender: &mut dyn Sender, ) -> unary::Result<()> { let group_keys = batch.column(self.key_column).as_primitive::(); for &key in group_keys.values() { // 如果分组键不存在，就将其设为 0 // 随后将该分组的值加 1，这样就能得到 count(*) GROUP BY key_column *self.counts.entry(key).or_insert(0) += 1; } } `` 然后，我们会在 ClickBench 提供的“hits”数据集\(9900 万行\)上运行一个简单查询`SELECT count\(\*\), UserID FROM hits GROUP BY UserID`。这个查询会给出每个`UserID`的计数，也就是说，HashMap 中每个`UserID`都会对应一个条目。这里先剧透一下：不同的`UserID`大约有 1700 万个。我们会在好朋友 CherryServers 提供的一台裸金属服务器上进行性能测试\(AMD EPYC 9124 Genoa，16 核，128 GB DDR5\)。遗憾的是，我们不能使用常见的 AWS/GCP 机器，因为我们需要访问一些出于安全原因而未在这些平台上开放的计数器\(例如，我们想知道有多少内存数据从 DRAM 控制器传输到了 CPU\)。我们会限制为单核运行，因为这个朴素的分组算法无法在多个核心上运行。运行方式如下：`` cat > config.yaml <<'EOF' server: bind: 127.0.0.1:5440 workers: 1 datastores: default: kind: pivotlake location: ./data default: true users: pivot: auth: method: trust EOF taskset -c 3 pivot server --config config.yaml & taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c '\timing on' -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)" `` 这花了……足足 3\.9 秒。算快吗？算慢吗？人们常说，世间万物都是相对的。如果我们再次运行该查询\(不重启服务器\)，耗时为 3\.6 秒。我们更关注第二次运行，因为所有数据都已经位于页缓存中，不涉及磁盘访问。你会注意到我们使用了`taskset \-c`。它会将进程固定到指定的 CPU 上，这样我们就能在该 CPU 上运行`perf stat`，查看其内部情况。我们会测量两组指标：因等待内存而停顿\(同时也没有执行其他操作\)的 CPU 槽位占比，以及实际完成微操作引退的 CPU 槽位占比：`` sudo perf stat -C 3 -M backend_bound_memory,retiring -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)" `` 得到如下结果 `` Performance counter stats for 'CPU(s) 3': 8364109137 ex_no_retire.load_not_complete # 50.1 % backend_bound_memory 38233214040 de_no_dispatch_per_slot.backend_stalls 8977647849 ex_no_retire.not_complete 11861387798 ls_not_halted_cyc 11431618219 ex_ret_ops # 16.1 % retiring 11858248045 ls_not_halted_cyc 4.030148989 seconds time elapsed `` 这告诉我们，CPU 有 50\.1% 的时间因为等待内存而无法做任何事情！而 CPU 真正引退\(也就是完成\)操作的时间仅占 16\.1%。另一个值得关注的统计数据是，CPU 的内存加载中有多少来自 DRAM\(而非缓存\)：`` sudo perf stat -C 3 -e ls_dmnd_fills_from_sys.dram_io_near -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)" `` 结果如下：`` Performance counter stats for 'CPU(s) 3': 76190837 ls_dmnd_fills_from_sys.dram_io_near 3.996301634 seconds time elapsed `` 每次加载都是 64 字节\(即能够读取的最小单位：一个缓存行\)，所以乘以 64，就可以得知，在执行这个查询期间，CPU 的加载操作从 DRAM 读取了 4\.5GB 数据\(这还不包括任何预取\)。现在，让我们尝试改进算法，充分利用 CPU 缓存。为此，我们会使用一种名为基数分区的方法。其思路是将合并过程分成两个独立的阶段：**阶段 1：**在这个阶段，我们只需将键分到 4096 个不同的分区中\(就是一个存放 SlabVec 的 Vec；SlabVec 是一种类似 Vec 的数据结构，建立在已调入物理内存的内存之上。Pivot 不使用 Vec 来管理原始内存，因为它会造成很大的性能波动；这个话题就不在本文展开了！\)。具体分到哪个分区，由键的哈希值的最高 12 位决定\(2\*\*12=4096\)。`` fn consume( &mut self, batch: RecordBatch, _sender: &mut dyn Sender, ) -> unary::Result<()> { let keys = batch.column(self.key_column).as_primitive::(); for &key in keys.values() { let hash = self.hasher.hash_one(key); // 由于我们需要最高 12 位，因此将哈希值（u64）右移 52 位 let partition = (hash >> 52) as usize; self.partitions[partition].push(&mut self.allocator, (hash, key)); } Ok(()) } `` UserID 哈希值\(UserID\)70x**002**A91F3...420x**000**7C4E2...130x**FFF**3B05D...70x**002**A91F3...50x**001**D6A88...420x**000**7C4E2...990x**002**E17B4...70x**002**A91F3...→ 分区 =`hash \>\> 52`，即前 3 个十六进制数字 **分区 0**0x000000... – 0x000FFF... 4242 **分区 1**0x001000... – 0x001FFF... 5 **分区 2**0x002000... – 0x002FFF... 77997 **分区 4095**0xFFF000... – 0xFFFFFF... 13 **阶段 2：**所有数据都处理完后，逐个遍历分区，每次创建一个 HashMap，将该分区的数据聚合到其中，然后输出。这一阶段与最初的算法非常相似，只不过我们会使用阶段 1 中得到的哈希值。`` fn into_outputter(self) -> unary::Result> { let mut groups = Vec::new(); for rows in &self.partitions { let mut table: HashTable<(u64, i64, u64)> = HashTable::new(); // (哈希值, 键, 计数) rows.for_each(|(hash, key)| { match table.entry(hash, |group| group.1 == key, |group| group.0) { Entry::Occupied(mut group) => group.get_mut().2 += 1, Entry::Vacant(slot) => { slot.insert((hash, key, 1)); } } }); groups.extend(table.into_iter().map(|(_, key, count)| (key, count))); } Ok(Some(Outputter::new(groups))) } `` 分区，逐个处理 0–1 已完成 2 正在处理 3–4095 等待中 分区 2 HashTable 输出 77997 → UserID 计数 73 991 → \(UserID, 计数\) \(7, 3\) \(99, 1\) 乍一看，这个方案可能显得相当奇怪。我们执行的操作**更多**了，而不是更少！在两种方案中，每一行都需要计算哈希值并送入 HashMap。但在这个方案中，我们还要先把行放进一些看似毫无意义的 Vec 中。这里的关键\(无意双关\)在于理解我们为什么这样做：为了让执行聚合的 HashMap **更小**。通过将分组操作拆分成 4096 份，我们大大提高了工作中的 HashMap 能够放入 CPU 缓存的概率。每次查找 HashMap 时，CPU 都更有可能在缓存中找到相关内存，从而节省大量时间。不过，何必只听我说呢？运行一下吧！`` taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c '\timing on' -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)" `` 然后……砰！3\.3 秒，第二次运行则是 2\.7 秒！确实有了改进。不过，为了更有力地说明这一点，让我们再次运行 perf：`` sudo perf stat -C 3 -M backend_bound_memory,retiring -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)" `` 结果如下：`` Performance counter stats for 'CPU(s) 3': 3790955223 ex_no_retire.load_not_complete # 23.5 % backend_bound_memory 20376118172 de_no_dispatch_per_slot.backend_stalls 5442424751 ex_no_retire.not_complete 10083617764 ls_not_halted_cyc 19350459182 ex_ret_ops # 32.2 % retiring 10023435553 ls_not_halted_cyc 3.575992317 seconds time elapsed `` 现在可以看到，情况已经完全改变：等待内存的时间占 23\.5%\(之前是 50%\)，真正用于引退操作的时间占 32%。你可能会注意到，我们实际完成的工作**更多**了，而不是更少：这次运行执行了 19350459182 次操作\(即`ex\_ret\_ops`计数器\)，而之前数据库执行了 11431618219 次操作。不过，这是值得的，因为正如前面所说，如果能把冷 DRAM 访问转换成 CPU 指令，这几乎总是一笔划算的交易。在这个例子中，因内存而停顿的 CPU 槽位数量从 8364109137 降到了 3790955223。为了补全这幅图景，确认我们确实从 DRAM 读取了更少的数据，再来检查一下有多少内存加载来自 DRAM：`` sudo perf stat -C 3 -e ls_dmnd_fills_from_sys.dram_io_near -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)" `` `` Performance counter stats for 'CPU(s) 3': 25688280 ls_dmnd_fills_from_sys.dram_io_near 3.009547012 seconds time elapsed `` 太棒了！这意味着我们按需从 DRAM 读取了 1\.5GB 数据，而朴素版本需要读取 4\.5GB。当然，这还远未达到 GROUP BY 利用 CPU 缓存的极限。利用 CPU 缓存也不是我们“隐藏”DRAM 延迟的唯一方法；另一个技巧是在需要数据之前，将内存数据预取到缓存中，还有一个技巧是设计算法，尽可能提高内存吞吐量。不过，这些就不在本文展开了！我们会在下一篇博客中介绍这些内容，届时会研究我们/看起来非常奇怪/的 JOIN 探测实现。目前先不做过多解释，给大家看看 Pivot 在单核上执行这个查询的速度：`` Time: 1848.353 ms (00:01.848) `` 以及从 RAM 读取的数据量：`` Performance counter stats for 'CPU(s) 3': 14917958 ls_dmnd_fills_from_sys.dram_io_near 2.182674864 seconds time elapsed `` 换算下来是 954 MB。当然，Pivot 能够在我们的 16 个核心上并行运行\(其中还有许多其他有趣的情况\)，此时的结果是：不错 :\) 如果你想在 Parquet 文件上体验超快的处理速度，不妨试试 Pivot\(开源的乐趣！\)，下次见。