FastLanes 统一传输布局

# FastLanes 统一传输布局（Unified Transport Layout）· blog.dave.tf UTL 来自 FastLanes（https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdf），其设计目的是让增量解码（delta decoding）具有高度的数据并行性。不过，论文对布局的讲解方式让我觉得有些费解，所以我打算在这里用我自己的方式来解释。 我假设你已经了解什么是增量编码（delta encoding）（https://en.wikipedia.org/wiki/Delta_encoding），以及 SIMD（https://en.wikipedia.org/wiki/Single_instruction,_multiple_data）计算的基础知识。 基本的增量编码/解码在本质上是顺序问题，因为计算每个值都必须先计算之前的所有值。本文关注的 FastLanes 部分旨在为这个问题增加并行性，这样我们就可以用 SIMD 让增量编码和（尤其是）解码变得非常快。 ## 预备知识：向量寄存器 SIMD 指令集自带一组专用的宽向量寄存器。在现代系统上，它们的尺寸从 128 位（SSE、Arm 的 Neon）到 512 位（AVX-512）不等，并且可以被切分成不同大小的*通道（lanes）*。指令会在所有通道上并行执行相同的操作。下面是一个 64 位向量寄存器（按现代标准来说非常小），它被分解为 8 位、16 位和 32 位通道。 一个 64 位向量寄存器，可以承载 8 个 8 位值的通道、4 个 16 位值的通道，或 2 个 32 位值的通道（https://blog.dave.tf/res/fastlanes-utl/vector-register.png） FastLanes 围绕虚拟的 1024 位 SIMD 寄存器大小来设计算法，这个大小超出了任何主流指令集的处理能力。原因在于，用较窄的寄存器来实现为宽寄存器设计的算法很容易：只需把每个宽操作实现为多个窄操作即可。 反过来，把为窄 SIMD 宽度设计的算法移植到宽寄存器上并让它变快就很难了，因为你很可能会遇到同一寄存器内不同通道之间的数据依赖。这种依赖会彻底扼杀性能，所以你真的要避免陷入这种局面。 因此，我们讨论的 FastLanes 算法都基于 1024 位寄存器，通道分为 16x64b、32x32b、64x16b 或 128x8b。在 1024 位寄存器上高效的算法，在现实世界的机器及其 128/256/512 位寄存器上也会同样高效。 ## 通道并行增量解码 先从一个包含 1024 个 64 位整数的数组开始，我们想对它做增量编码。 一个包含 1024 个值的数组示意图，标记为 0 到 1023（https://blog.dave.tf/res/fastlanes-utl/flat-array.png） 如我上面所说，这本质上是一个顺序算法：保留第一个值，让后续每个值都是与前一个值的差。计算每个值都需要访问前一个值来计算差值，而在 SIMD 中这意味着要跨到相邻通道去取数据。 对于我们的 1024 位 SIMD 寄存器，我们需要 16 条彼此独立的增量流，这样才能同时计算。如果我们愿意存储多个基准值，就可以把 1024 个值拆成 16 块来实现： 一个 1024 元素数组，排列为 16 行，每行 64 个值（https://blog.dave.tf/res/fastlanes-utl/matrix-16x64.png） 内存中的布局还没有改变，这里只是用一点包装把 16 块可视化为行。 现在，想象一次处理这个二维数组的一列。每一列是 16 个 64 位值，恰好就是一个 1024 位寄存器。而且，如果你沿着每一行往下看，行内的值在顺序上仍然适合增量编码。换句话说，如果我们把整个第一列存储为基准值，那么这 16 行就变成了 16 条可以同时计算的独立数据流。这正是我们需要的！ 有一个小问题：每一列的值在内存中仍然是散落各处的。SIMD 的加载/存储指令希望这些值是连续存放的。我们可以很容易地解决这个问题：把这个数组看作一个 16x64 矩阵，然后对它做转置： 上面的 16x64 数组，转置为 64x16。值现在按列递增，而不是按行递增。（https://blog.dave.tf/res/fastlanes-utl/matrix-64x16.png） 现在，我们可以按每块 16 个值来处理这个数组，正好整齐地放进我们的 1024 位 SIMD 寄存器，并让我们一口气并行处理 16 条增量编码流。 ## 宽度无关的布局 上面的转置效果很好，但理想的分块和转置方式取决于元素大小。上面的布局对 64 位值来说是完美的，但如果我们换成 32 位值，我们就又遇到麻烦了：现在一行 16 个值只有 512 位，只有我们的 SIMD 寄存器的一半大小。如果考虑 16 位和 8 位值，情况会更糟！ 你可能会说“谁在乎”，直接对不同数据类型采用不同的转置方式：32 位值用 32 行，16 位值用 64 行，8 位值用 128 行。这样可行，但意味着两列数据类型不同的列，其值的顺序会不同。无论是对查询执行过程中的过滤，还是拼接出连贯的结果来返回，这都将是一场噩梦。 理想情况下，我们希望找到一种单一的输入数组置换方式，使得无论元素大小如何，都能充分利用 1024 位寄存器。而这正是 UTL 置换所做的。 为了理解它的原理和原因，让我们一步步推导。 ## 32 位值 对于 64 位值，我们已经有了一个效果很好的置换：64 行 x 16 列。让我们从它开始，把元素大小降到 32 位，看看能否调整布局，使其同时适用于 64 位和 32 位值。 对于 32 位，每一行需要的值数量是原来的两倍，而且这些值必须沿每一列构成独立的数据流。我们可以很容易地做到这一点：把下面的 32 行切掉，然后粘贴到上面 32 行的旁边： 64x16 布局的底部 32 行被切掉，并移动到顶部 32 行的右侧。（https://blog.dave.tf/res/fastlanes-utl/split-64-to-32.png） 现在我们有了一个 32x32 矩阵，每一列仍然是一条独立的值流。对于 32 位值来说这没问题，我们现在可以一次处理一行 32 个值。但重要的是，我们也可以让这个布局适用于 64 位值，只要愿意稍微乱序地加载块。 32 位值一次处理 32 个，按简单的内存顺序（https://blog.dave.tf/res/fastlanes-utl/process-32-32.png） 对于 64 位值，我们的 SIMD 寄存器一次只能处理 16 个值。我们仍然可以得到 16 条连续值的流，只要先处理每行的左侧，然后回到顶部处理右侧。 64 位值一次处理 16 个，分两遍进行（https://blog.dave.tf/res/fastlanes-utl/process-64-32.png） 我们需要的 16 值块仍然在数组中，但不再处于连续位置。幸运的是，我们加载这些块的顺序是固定的，所以我们可以预先计算一次，然后写出一个快速的展开循环来快速处理。 此时你可能会担心，与线性扫描相比，乱序内存访问会导致一堆缓存未命中和速度下降。但你大可不必担心。所有这些处理都发生在固定长度的 1024 个值上，即使对于 64 位值来说也只有 8KiB。一颗 Intel Haswell CPU（写作本文时已有 13 年历史）每个核心有 32KiB 的 L1 数据缓存。因此实际上，无论访问模式如何，整个数组都可以以恒定延迟访问。 还要记住，对于 32 位值，我们现在需要存储两倍数量的基准值（每列一个）。但由于值变窄了，存储基准值所需要的字节数仍然与 64 位情况相同。 ## 16 位值 好了，现在我们有了一个同时适用于 64 位和 32 位的单一置换。当 16 位值加入进来时，我们的行需要再次加倍变宽。幸运的是，我们刚才用的技巧可以重复：把底部 16 行切掉，粘贴到顶部 16 行的旁边： 分割过程重复进行：32x32 布局的底部 16 行被切掉，并移动到顶部 16 行的右侧。（https://blog.dave.tf/res/fastlanes-utl/split-32-to-16.png） 重复之前的练习：处理 16 位值很容易，我们可以一次完成一整行。同样，我们需要存储的基准值数量再次翻倍，但每个值的大小又减半了，所以存储的总字节数仍然相同。 16 位值一次处理 64 个，按简单的内存顺序（https://blog.dave.tf/res/fastlanes-utl/process-16-16.png） 32 位值可以分两遍处理：先处理每行的前两个块，然后处理后两个块。 32 位值一次处理 32 个，先处理每行最左侧的 32 个值，再处理最右侧的 32 个。（https://blog.dave.tf/res/fastlanes-utl/process-32-16.png） 64 位值的内存访问模式再次变得更加复杂：如果我们将每行的四个 16 值块命名为 `[0, 1, 2, 3]`，那么 64 位编解码器会先跑遍所有行的块 0，然后跳到块 2 去找序列中接下来的值，再回到块 1，最后到块 3。对于这张插图我深表歉意，它开始变得比《Primer》里的时间线还要纠缠不清了。 64 位值一次处理 16 个。每行被划分为四个 16 值的块。先处理所有行的块 0，然后处理所有行的块 2，再处理所有行的块 1，最后处理所有行的块 3。（https://blog.dave.tf/res/fastlanes-utl/process-64-16.png） 但同样重要的是：不管块处理顺序有多乱，它是一个固定序列，我们可以预先算好，然后写出快速的展开 SIMD 代码来执行。 ## 8 位值 你猜到了，再来一遍同样的技巧！我放弃插图了，因为方框实在太小，要敲的值也太多。但希望你此时已经能想象出发生了什么。 我们最终得到 8 行，每行 128 个值。或者，像上面的插图中那样分组，我们得到八个 8x16 的瓦片（tile），这是论文描述的基本处理单元。和之前一样，我将按照重新排列后它们出现的顺序来命名这些瓦片：`[0, 1, 2, 3, 4, 5, 6, 7]`。 再重复一遍这个练习：对于 8 位值，一个 1024 位 SIMD 寄存器可以一次处理整行。我们现在需要存储 128 个基准值。 16 位值分两遍处理：第一遍把 `[0, 1, 2, 3]` 放在一起处理，然后 `[4, 5, 6, 7]` 一起处理。如果你仔细想想这些值是如何被重新排列的，瓦片 4 中的列确实延续了瓦片 0 中开始的值流。`1->5`、`2->6` 和 `3->7` 也是如此。 32 位值分四遍处理，采用前面展示过的同样曲折路径，但这次是两个瓦片一起：先 `[0, 1]`，然后 `[4, 5]`，再 `[2, 3]`，最后 `[6, 7]`。同样，如果你按照访问顺序把每个瓦片的列粘合在一起，所有列都会看到连续值的流。 最后，64 位值分八遍处理，一次一个瓦片，顺序更加蜿蜒曲折：`[0], [4], [2], [6], [1], [5], [3], [7]`。再强调一次，顺着这个令人眼花缭乱的顺序走一遍，所有列都会看到连续值的流。 ## 将数组重排为 UTL 顺序 回顾一下，要将一个数组置为 UTL 顺序，需要以下步骤： - 在概念上把数组排列成一个 16x64 矩阵。 - 将矩阵转置为 64x16，产生列方向上的独立值流。 - 把 64 行分成八组，形成 8x16 的瓦片。 - 使用置换 `[0, 4, 2, 6, 1, 5, 3, 7]` 对瓦片重新排序。 - 对瓦片（而不是瓦片内部的值）进行转置，把 8x1 的瓦片布局变成 1x8。 另一种理解方式是看数组索引如何被映射到转置后的位置。1024 元素数组的索引恰好占用 10 位。 - 排列成 16x64 矩阵时，10 位索引分解为行索引和列索引：`[row:4b][col:6b]`。 - 交换这两部分索引以转置为 64x16：`[t_row:6b][t_col:4b]`。 - 将 6 位行索引分解为 8 个瓦片，每个瓦片 8 行：`[tile:3b][row_in_tile:3b][t_col:4b]`。 - 交换瓦片顺序，我们只需对瓦片索引进行置换：`[p_tile:3b][row_in_tile:3b][t_col:4b]`。 - 转置瓦片，使所有瓦片的行 0 先出现，然后是行 1，依此类推：`[row_in_tile:3b][p_tile:3b][t_col:4b]`。 转换成代码后，你会得到一个函数，它告诉你 `in[i]` 应该被移动到何处：对于数组中的每个 `i`，执行 `out[translate(i)] = in[i]`。 ## 结论 当数据按 UTL 布局排列时，8/16/32/64 位值都可以用最高效的 SIMD 例程进行增量编码和解码。不同数据类型的列，其值都会以相同顺序排列，从而让查询引擎能够处理多列谓词。 论文还证明了，瓦片的这个神奇置换是唯一具有该性质的置换，这很巧妙。 当然，也有缺点： - 这种数据布局对人类来说完全不可读。我敢打赌，当你想调试某些东西时，盯着这种格式看可不是什么愉快的体验。 - 每种值大小都需要单独的 SIMD 例程，因为它们必须按照截然不同的顺序遍历数组。这倒不算世界末日，但你很可能需要对最底层的原语进行代码生成。 - 如果你需要按插入顺序返回结果，就必须在查询执行结束时将所有数据逆置换回来。论文指出，对许多列存储应用来说，插入顺序并不重要，因此这一步可以跳过。 尽管如此，这仍然是一套非常巧妙的想法，而且根据论文中的数据，它可以让你的线性扫描增量编码列的速度达到 L1 缓存吞吐量的水平，这是相当令人印象深刻的。