It's the memory latency, stupid

本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

no LLMs were harmed (or for that matter used) in the writing of this blog post

在撰写这篇博客文章时，没有使用任何大语言模型（也没有受到任何伤害）。

When you see your databases CPU at 100%, what is it actually doing? We like to act as though CPUs run code linearly for simplicity’s sake, but in truth CPUs are incredibly complex beasts; they can potentially do many instructions at once, or sometimes none at all (despite our console showing 100%). Because CPUs can do so many things, one CPU at 100% may be doing much less than another at 100%. A CPU is considered “idle” only if no task (Linux task) needs CPU time; this does not mean the CPU itself is being fully saturated. So why would a CPU not be fully utilized, even if it appears to be at 100%?

当你看到数据库的 CPU 使用率达到 100% 时，它到底在做什么？为了简单起见，我们倾向于认为 CPU 是线性执行代码的，但实际上 CPU 是极其复杂的野兽；它们可能同时执行多条指令，有时甚至一条也不执行（尽管控制台显示为 100%）。由于 CPU 可以处理的事情非常多，一个 100% 的 CPU 可能比另一个 100% 的 CPU 做的工作要少得多。只有在没有任务（Linux 任务）需要 CPU 时间时，CPU 才被认为是“空闲”的；这并不意味着 CPU 本身已完全饱和。那么，为什么即使 CPU 显示为 100%，它却可能没有被充分利用呢？

The answer is usually memory.

答案通常是内存。

Memory accesses are orders of magnitude slower than internal CPU operations. To give a good picture of how much so, a modern CPU might be able to process somewhere in the realm of 4-8 instructions per nanosecond. A memory access to RAM can take somewhere in the realm of 50-100ns. To ease your mathing, that means a modern CPU can do around 400-800 instructions for every one memory access from RAM.

内存访问比 CPU 内部操作慢几个数量级。为了形象地说明这一点，现代 CPU 每纳秒大约能处理 4 到 8 条指令。而访问一次内存（RAM）大约需要 50 到 100 纳秒。为了方便计算，这意味着现代 CPU 在等待一次内存访问时，可以执行大约 400 到 800 条指令。

Given this, CPUs are built from the ground up to work their way around this. The most obvious way this is dealt with is CPU caches. CPU caches keep memory closer to the CPU than RAM, literally baked into the CPU chip. The closest cache (the L1 cache) takes around 1ns per memory operation- that’s 50-100x faster than RAM! The “problem” here of course is that the CPU caches are fairly small; the L1 cache for a modern CPU is probably around ~64KB, while the farther caches max out at a few hundred MB for top end processors. A good database tries manipulating data in small “chunks” to take full advantage of caches, and you’ll often hear cache utilization as being one of the top concerns of performance engineering.

鉴于此，CPU 从底层设计上就旨在绕过这个问题。最明显的解决方法是 CPU 缓存。CPU 缓存将内存保持在比 RAM 更靠近 CPU 的位置，实际上是直接集成在 CPU 芯片中的。最近的缓存（L1 缓存）每次内存操作大约需要 1 纳秒——这比 RAM 快 50 到 100 倍！当然，这里的问题在于 CPU 缓存非常小；现代 CPU 的 L1 缓存大约只有 64KB 左右，而高端处理器的远端缓存最大也只有几百 MB。优秀的数据库会尝试以小的“块”来处理数据，以充分利用缓存，你经常会听到缓存利用率是性能工程中最受关注的问题之一。

Let’s look at GROUP BY aggregations to get a better grip on cache utilization. In GROUP BY, we’re looking to take a dataset, group it by a certain column (or more), and perform certain aggregations (for example, count, or sum on another column). The “naive” method might be to open a HashTable keyed by the group key that grows ever larger. For every new row, you would check if that key exists- if it does, go to it’s corresponding aggregation and update the result. Simple, right? The problem is that if you have millions of unique groups, you’re not utilizing your cache at all! Nearly every HashTable access will be a “cold” hit that goes to RAM. This means that although your CPU may /look/ like it’s 100% utilized, in truth it’ll constantly be waiting for cold memory accesses.

让我们看看 GROUP BY 聚合，以更好地理解缓存利用率。在 GROUP BY 中，我们试图获取一个数据集，按某一列（或多列）进行分组，并执行某些聚合（例如，对另一列进行计数或求和）。“朴素”的方法可能是打开一个以分组键为索引的哈希表，并使其不断增长。对于每一行新数据，你都要检查该键是否存在——如果存在，就找到对应的聚合值并更新结果。很简单，对吧？问题在于，如果你有数百万个唯一分组，你根本无法利用缓存！几乎每一次哈希表访问都会成为需要访问 RAM 的“冷”命中。这意味着，尽管你的 CPU 看起来是 100% 利用的，但实际上它一直在等待冷内存访问。

To demonstrate this, we’ll take our state-of-the-art Pivot engine and ravage it! We’ll remove all our complex logic and replace it with simplicity:

为了演示这一点，我们将拿我们最先进的 Pivot 引擎开刀！我们将移除所有复杂的逻辑，取而代之以简单的实现：

We’ll then run a simple query SELECT count(*), UserID FROM hits GROUP BY UserID on the “hits” dataset ClickBench provides (99m rows). This query will give us a count per UserID, meaning we’ll have an entry in our HashMap per UserID- I’ll give a spoiler here that there are ~17m unique UserID.

然后，我们将在 ClickBench 提供的“hits”数据集（9900 万行）上运行一个简单的查询：SELECT count(*), UserID FROM hits GROUP BY UserID。这个查询将给出每个 UserID 的计数，这意味着我们的哈希表中每个 UserID 都会有一个条目——这里先剧透一下，大约有 1700 万个唯一的 UserID。

Our performance checks will be on a bare metal server from our good friends over at CherryServers (AMD EPYC 9124 Genoa, 16 cores, 128 GB DDR5). We unfortunately can’t use a common AWS/GCP machine because we want access to counters that aren’t exposed there for security reasons (for example, we want to see how much memory is passing from DRAM controller to us). We’ll confine ourselves to a single core, since this naive group by can’t run on many cores.

我们的性能测试将在 CherryServers 的裸机服务器上进行（AMD EPYC 9124 Genoa，16 核，128 GB DDR5）。遗憾的是，我们不能使用普通的 AWS/GCP 机器，因为我们需要访问出于安全原因未公开的计数器（例如，我们想查看有多少内存从 DRAM 控制器传输到我们这里）。我们将仅限于使用单个核心，因为这种朴素的 GROUP BY 无法在多核上运行。

This takes… a whopping 3.9 seconds. Is that good? Is that bad? Everything in this world is relative, or so they say. If we run the query again (without restarting the server), it takes 3.6s. The second run is the one we’re more interested in- there’s no disk involved as everything is already sitting in our page-cache.

这耗时……整整 3.9 秒。这算好还是坏？俗话说，世间万物皆是相对的。如果我们再次运行该查询（不重启服务器），它需要 3.6 秒。我们更关注第二次运行——因为所有数据都已经存在于页面缓存中，所以不涉及磁盘操作。

You’ll notice we did taskset -c. This pins the process to a given CPU; this will allow us to run perf stat on that CPU and see what’s going on internally. We’ll measure two metric groups- percentage of CPU slots stalling because of memory (and not doing anything in the meanwhile), and percentage of CPU slots actually retiring a micro-op:

你会注意到我们使用了 taskset -c。这会将进程绑定到指定的 CPU 上；这使我们能够在该 CPU 上运行 perf stat 并查看内部发生了什么。我们将测量两组指标：因内存原因导致 CPU 插槽停顿（在此期间什么也不做）的百分比，以及 CPU 插槽实际完成微操作的百分比：

This tells us that 50.1% of the time, the CPU couldn’t do anything because it was stalling on memory! And only 16.1% of the time the CPU was actually retiring (aka doing) operations.

这告诉我们，CPU 有 50.1% 的时间因为在等待内存而处于停顿状态，什么也做不了！而只有 16.1% 的时间 CPU 实际上是在完成（即执行）操作。

Another interesting stat to get is how many of our CPU memory loads are coming from DRAM (and not from caches):

另一个有趣的统计数据是，我们的 CPU 内存加载中有多少来自 DRAM（而不是缓存）：

Every load is 64 bytes (the minimum amount you can bring, a cache line), so we can multiply by 64 to see we pulled 4.5GB during this query from DRAM on CPU loads (this is without any prefetching).

每次加载都是 64 字节（这是可以获取的最小单位，即缓存行），因此我们可以乘以 64，得出在此查询期间，CPU 加载从 DRAM 中提取了 4.5GB 的数据（这还不包括任何预取）。

Let’s now try to improve our algorithm to take advantage of the CPU caches. To do this, we’ll use a method called radix partitioning. The idea is to split the merge into two distinct phases:

现在让我们尝试改进算法以利用 CPU 缓存。为此，我们将使用一种称为基数分区（radix partitioning）的方法。其思路是将合并过程分为两个不同的阶段：

Phase 1: In this phase, we’re simply going to separate the keys into 4096 different partitions (simply a Vec of SlabVecs- a SlabVec is a data structure similar to a Vec that is above memory that is already paged in. We don’t use Vecs for raw memory in Pivot because it creates a lot of variance; not something for this blog post!). The partition will be decided by hashing the key and taking it’s top 12 bits (2**12=4096).

第一阶段：在此阶段，我们只需将键分离为 4096 个不同的分区（简单来说就是一个 SlabVec 的 Vec——SlabVec 是一种类似于 Vec 的数据结构，位于已经分页的内存之上。我们在 Pivot 中不使用 Vec 来处理原始内存，因为它会产生很大的差异；这不在本篇博客的讨论范围内！）。分区将通过对键进行哈希并取其高 12 位（2^12=4096）来决定。

Phase 2: When all data has come through, go partition by partition, each time creating a HashMap, aggregating the partition into it, and then outputting it. This phase is very similar to our original algorithm, but we’re going to use the hash from phase 1.

第二阶段：当所有数据处理完毕后，逐个分区进行处理，每次创建一个哈希表，将分区数据聚合到其中，然后输出。此阶段与我们最初的算法非常相似，但我们将使用第一阶段计算出的哈希值。

At first glance, this solution may seem rather odd. We’re doing more operations here, not less! Every row, in both solutions, is hashed and sent into a HashMap. But in this solution, we’re first pushing rows into seemingly meaningless vecs.

乍一看，这个解决方案似乎相当奇怪。我们在这里执行的操作更多了，而不是更少！在两种方案中，每一行数据都被哈希并发送到哈希表中。但在这种方案中，我们首先将行推送到看似毫无意义的向量中。

The key here (no pun intended) is to understand why we’ve done this; it’s to make the aggregating HashMaps smaller. By dividing our group by into 4096 pieces, we’ve made our working HashMaps much likelier

这里的关键（不是双关语）在于理解我们为什么要这样做；这是为了让聚合哈希表变得更小。通过将 GROUP BY 分成 4096 个部分，我们使得工作哈希表更有可能……