加速 ClickHouse 中的 LZ4

这篇博文最初发表于 2019 年。我们重新发布是为了纪念 LZ 系列算法的作者：亚伯拉罕·莱姆佩尔 和 雅各布·齐夫，他们最近去世了。

人们很容易认为每个新功能都是新颖的。每个新版本都将改变市场。然而，我们——作为一个行业——站在巨人的肩膀上。雅各布对信息论（超越压缩算法）的贡献，一直是并且仍然是几代从业者和研究人员的灵感来源。

当您在 ClickHouse 中运行查询时，您可能会注意到分析器经常显示 LZ_decompress_fast 函数位于顶部附近。这是怎么回事？这个问题让我们想知道如何选择最佳的压缩算法。

ClickHouse 以压缩形式存储数据。运行查询时，ClickHouse 尝试尽可能少地执行操作以节省 CPU 资源。在许多情况下，所有可能耗时的计算都已经过良好的优化，并且用户编写了一个经过深思熟虑的查询。然后剩下的就是执行解压缩。

那么为什么 LZ4 解压缩会成为瓶颈呢？LZ4 似乎是一个极其轻量级的算法：数据解压缩速率通常为每个处理器内核 1 到 3 GB/s，具体取决于数据。这比典型的磁盘子系统快得多。此外，我们使用所有可用的 CPU 内核，并且解压缩在所有物理内核之间线性扩展。

但是，有两点需要注意。首先，压缩数据从磁盘读取，但解压缩速度以未压缩数据的数量来表示。如果压缩比足够大，几乎没有数据需要从磁盘读取。但是会有大量解压缩的数据，这自然会影响 CPU 利用率：在 LZ4 的情况下，解压缩数据所需的工作量几乎与解压缩数据本身的体积成正比。

其次，如果数据被缓存，您可能根本不需要从磁盘读取数据。您可以依靠页面缓存或使用您自己的缓存。在面向列的数据库中，缓存效率更高，因为只有经常使用的列保留在缓存中。这就是为什么 LZ4 通常在 CPU 负载方面表现为瓶颈。

这就引出了另外两个问题。首先，如果解压缩减慢了我们的速度，那么是否值得一开始就压缩数据？但在实践中，这种猜测是无关紧要的。ClickHouse 提供了几种压缩选项，主要包括 LZ4 和Zstandard。默认情况下使用 LZ4。切换到 Zstandard 使压缩更强劲，速度更慢。但是没有选项可以完全禁用压缩，因为假设 LZ4 可以提供合理的最小压缩，始终可以使用。（这正是我喜欢 LZ4 的原因。）

但后来，一位神秘的陌生人在ClickHouse 电报支持群中表示，他拥有非常快的磁盘子系统（使用 NVMe SSD），并且解压缩是唯一减慢查询速度的事情，因此能够在不压缩的情况下存储数据会很好。我回答说我们没有这个选项，但添加起来很容易。几天后，我们收到一个实现压缩方法 none 的请求。我请贡献者报告此选项在加速查询方面有多大帮助。结果表明，这个新功能在实践中毫无用处，因为未压缩的数据开始占用过多的磁盘空间，并且无法容纳在这些 NVMe 驱动器中。

出现的第二个问题是，如果存在缓存，为什么不使用它来存储已经解压缩的数据呢？这是一个可行的方案，在许多情况下可以消除解压缩的需要。ClickHouse 也有这样的缓存：解压缩块的缓存。但浪费大量 RAM 在此很可惜。因此，通常只有在使用几乎相同数据的小型顺序查询时才有意义。

因此，我们的结论是，始终优先选择以压缩格式存储数据。始终以压缩格式将数据写入磁盘。同样，通过网络传输数据时也应使用压缩。在我看来，即使在 10 GB 的网络中，在单个数据中心内传输数据时，默认压缩也是合理的，而无需过度订阅，而在数据中心之间传输未压缩的数据则完全不可接受。

为什么选择 LZ4？我们不能选择更轻量级的算法吗？理论上可以，这是一个很好的想法。但让我们看看 LZ4 所属的算法类别。

首先，它是通用的，不适应数据类型。例如，如果您事先知道将拥有一个整数数组，则可以使用 VarInt 算法之一，这将更有效地利用 CPU。其次，LZ4 并不过度依赖数据模型假设。假设您有一个按时间排序的传感器值时间序列和一个浮点数数组。如果您考虑这一点，您可以计算这些数字之间的增量，然后使用通用算法压缩它们，这将导致更高的压缩比。

使用 LZ4 处理任何字节数组或文件都不会有任何问题。当然，它确实有一些专门化（稍后详细介绍），在某些情况下，使用它是毫无意义的。但如果我们称之为通用算法，我们将非常接近真相。我们应该注意，由于其内部设计，LZ4 自动将RLE算法作为特例实现。

但是，更重要的问题是，就压缩速度和压缩强度而言，LZ4 是否是此类算法中最优的算法。最优算法称为帕累托边界，这意味着在某种程度上，没有其他算法在某种程度上绝对更好，而在其他方面并不更差（并且在各种各样的数据集上也是如此）。某些算法更快，但会导致压缩比更小，而其他算法具有更强的压缩能力，但压缩或解压缩速度更慢。

说实话，LZ4 并不是真正的帕累托最优解——还有一些选项略微更好。例如，看看开发者“powturbo”的LZTURBO。由于encode.su社区（最大且可能是唯一的数据压缩论坛），其结果的可靠性毋庸置疑。不幸的是，开发者没有发布源代码或二进制文件；它们仅提供给少数人进行测试或以高价获取。此外，还可以看看Lizard（以前称为 LZ5）和Density。在选择特定压缩级别时，它们可能比 LZ4 略微好一些。另一个非常有趣的选项是LZSSE。但在查看它之前，请先看完本文。

让我们大致了解一下 LZ4 的工作原理。这是 LZ77 算法的一种实现。L 和 Z 代表开发者的名字（Lempel 和 Ziv），77 代表 1977 年，即算法发布的年份。它还有许多其他实现：QuickLZ、FastLZ、BriefLZ、LZF、LZO，以及如果使用低压缩级别，还有 gzip 和 zip。

使用 LZ4 压缩的数据块包含一系列两种类型的条目（命令或指令）

1. 字面量：“按原样获取以下 N 个字节，并将它们复制到结果中”。
2. 匹配：“从解压缩结果中获取 N 个字节，从相对于当前位置的偏移量值开始”。

示例。压缩前

Hello world Hello

压缩后

literals 12 "Hello world " match 5 12

如果我们获取一个压缩块并在运行这些命令时遍历它，那么我们将获得原始未压缩数据作为结果。

所以这基本上就是数据解压缩的方式。基本思想很明确：为了执行压缩，算法使用匹配来编码重复的字节序列。

一些特征也很明显。这种面向字节的算法不会分解单个字节；它只会完整地复制它们。这就是它与熵编码的不同之处。例如，zstd 是 LZ77 和熵编码的组合。

请注意，压缩块的大小不应该太大。选择大小是为了避免在解压缩期间浪费大量内存，避免在压缩文件中（由大量压缩块组成）过分降低随机访问速度，有时是为了让块适合 CPU 缓存。例如，您可以选择 64 KB，以便压缩和未压缩数据的缓冲区可以容纳在 L2 缓存中，并且仍然有半部分是空闲的。

如果我们需要压缩更大的文件，我们可以连接压缩块。这对于将其他数据（如校验和）与每个压缩块一起存储也很方便。

匹配的最大偏移量是有限制的。在 LZ4 中，限制是 64 千字节。这个量称为滑动窗口。这意味着匹配可以在紧挨着光标之前的 64 千字节窗口中找到，该窗口随着光标向前移动而滑动。

现在让我们看看如何压缩数据，或者换句话说，如何在文件中找到匹配的序列。您可以始终使用后缀树（如果您确实听说过它，那将很棒）。有一些方法可以保证在压缩后找到最长的匹配项位于前面的字节中。这称为最优解析，它为固定格式的压缩块提供了几乎最佳的压缩率。但是，还有更好的方法，例如查找一个足够好的匹配项，而该匹配项不一定是最长的。找到它的最有效方法是使用哈希表。

为此，我们遍历原始数据块中的光标，并在光标之后获取几个字节（假设为 4 个字节）。我们对其进行哈希处理，并将从块开头（从何处获取 4 个字节）的偏移量放入哈希表中。值 4 称为“最小匹配”——使用此哈希表，我们可以找到至少 4 个字节的匹配项。

如果我们查看哈希表，并且它已经有一个匹配的记录，并且偏移量不超过滑动窗口，那么我们会检查在那些 4 个字节之后有多少个字节匹配。也许还有很多匹配项。也有可能哈希表中存在冲突，并且没有任何匹配项，但这没什么大不了的。您可以简单地用新值替换哈希表中的值。哈希表中的冲突只会导致压缩率降低，因为匹配项会更少。顺便说一句，这种哈希表（具有固定大小并且没有冲突解决）称为“缓存表”。这个名称很有意义，因为在发生冲突时，缓存表会简单地忘记旧条目。

给仔细阅读者的一个挑战。假设数据是以小端格式表示自然数序列一部分的 UInt32 数字数组：0、1、2…。解释一下为什么使用 LZ4 压缩此数据时不会压缩（压缩数据的尺寸与未压缩数据相比没有变小）。

所以我想加速 LZ4 解压缩。让我们看看解压缩循环是什么样子的。以下是伪代码

while (...)
{
   read(input_pos, literal_length, match_length);

   copy(output_pos, input_pos, literal_length);
   output_pos += literal_length;

   read(input_pos, match_offset);

   copy(output_pos, output_pos - match_offset,
       match_length);
   output_pos += match_length;
}

LZ4 格式的设计使得字面量和匹配项在压缩文件中交替出现。显然，字面量总是先出现（因为在一开始没有地方可以获取匹配项）。因此，它们的长度一起编码。

实际上，它比这稍微复杂一点。从文件中读取一个字节，然后将其分成两个 nibble（半字节），其中包含编码数字 0 到 15。如果相应的数字不是 15，则假定它分别是字面量和匹配项的长度。如果是 15，则长度更长，并在后续字节中进行编码。然后读取下一个字节，并将它的值添加到长度中。如果它等于 255，则对下一个字节执行相同的操作。

请注意，LZ4 格式的最大压缩率不会达到 255。另一个无用的观察结果是，如果您的数据非常冗余，则使用 LZ4 两次将提高压缩率。

当我们读取字面量的长度（然后是匹配长度和匹配偏移量）时，只需复制两个内存块就足以解压缩它。

看起来您可以使用 memcpy 函数，该函数旨在复制内存块。但这并不是最佳方法，也不是真正合适的。

使用 memcpy 不是最佳方法，因为

1. 它通常位于 libc 库中（并且 libc 库通常是动态链接的，因此 memcpy 调用将通过 PLT 间接进行）。
2. 如果大小参数在编译时未知，则编译器不会将其内联。
3. 它会付出很多努力来正确处理不是机器字长或寄存器倍数的内存块的剩余部分。

最后一点是最重要的。假设我们要求 memcpy 函数精确复制 5 个字节。最好立即使用两个 movq 指令复制 8 个字节。

Hello world Hello wo...
^^^^^^^^ - src
            ^^^^^^^^ - dst

但是，我们将复制三个额外的字节，因此我们将写入缓冲区边界之外。memcpy 函数没有权限执行此操作，因为它可能会覆盖我们程序中的某些数据并导致内存覆盖错误。如果我们写入未对齐的地址，这些额外的字节可能会落在未分配的虚拟内存页面上或没有写访问权限的页面上。这将给我们一个段错误（这很好）。

但在我们的例子中，我们几乎总是可以写入额外的字节。只要额外的字节完全位于输入缓冲区内，我们就可以在输入缓冲区中读取额外的字节。在相同条件下，我们可以将额外的字节写入输出缓冲区，因为我们将在下一次迭代中覆盖它们。

此优化已存在于 LZ4 的原始实现中

inline void copy8(UInt8 * dst, const UInt8 * src)
{
   memcpy(dst, src, 8);    /// Note that memcpy isn't actually called here.
}

inline void wildCopy8(UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
{
   do
   {
       copy8(dst, src);
       dst += 8;
       src += 8;
   } while (dst < dst_end);
}

为了利用此优化，我们只需要确保我们远离缓冲区边界足够远即可。这不会造成任何损失，因为我们已经在检查缓冲区溢出。并且可以在主循环之后处理最后的几个字节，“剩余”数据。

但是，仍然有一些细微差别。复制在循环中发生两次：使用字面量和匹配项。但是，当使用 LZ4_decompress_fast 函数（而不是 LZ4_decompress_safe）时，仅在我们需要复制字面量时才执行检查。在复制匹配项时不执行检查，但LZ4 格式规范有一些条件允许您避免它

• 最后 5 个字节始终是字面量。
• 最后一个匹配项必须在块结束前至少 12 个字节开始。
• 因此，少于 13 个字节的块无法压缩。

专门选择输入数据可能会导致内存损坏。如果您使用 LZ4_decompress_fast 函数，则需要防止不良数据。至少，您应该计算压缩数据的校验和。如果您需要防止黑客攻击，请使用 LZ4_decompress_safe 函数。其他选项：将加密哈希函数作为校验和（尽管这可能会降低性能）；为缓冲区分配更多内存；使用单独的 mmap 调用为缓冲区分配内存并创建保护页面。

当我看到复制 8 个字节数据的代码时，我立即想知道为什么正好是 8 个字节。您可以使用 SSE 寄存器复制 16 个字节

inline void copy16(UInt8 * dst, const UInt8 * src)
{
#if __SSE2__
    _mm_storeu_si128(reinterpret_cast<__m128i *>(dst),
        _mm_loadu_si128(reinterpret_cast<const __m128i *>(src)));
#else
    memcpy(dst, src, 16);
#endif
}

inline void wildCopy16(UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
{
    do
    {
        copy16(dst, src);
        dst += 16;
        src += 16;
    } while (dst < dst_end);
}

对于 AVX 复制 32 个字节和 AVX-512 复制 64 个字节，同样适用。此外，您可以展开循环多次。如果您曾经看过 memcpy 的实现方式，这正是使用的方法。（顺便说一句，编译器在这种情况下不会展开或矢量化循环，因为这将需要插入庞大的检查。）

为什么 LZ4 的原始实现没有这样做？首先，尚不清楚这是否更好或更差。产生的增益取决于要复制的块的大小，因此如果它们都很短，则会白白增加工作量。其次，它破坏了 LZ4 格式中有助于避免内部循环中不必要分支的规定。

但是，我们将暂时记住此选项。

让我们回到是否始终可以以这种方式复制数据的问题。假设我们需要复制一个匹配项，也就是说，从输出缓冲区中获取位于光标后面某个偏移量处的一段内存，并将其复制到光标位置。

想象一个简单的例子，您需要以 12 的偏移量复制 5 个字节

Hello world ...........
^^^^^ - src
            ^^^^^ - dst

Hello world Hello wo...
^^^^^ - src
            ^^^^^ - dst

但是，有一个更复杂的情况，我们需要复制的内存块比偏移量长。换句话说，它包含一些尚未写入输出缓冲区的数据。

以 3 的偏移量复制 10 个字节

abc.............
^^^^^^^^^^ - src
   ^^^^^^^^^^ - dst

abcabcabcabca...


^^^^^^^^^^ - src
   ^^^^^^^^^^ - dst

在压缩过程中，我们拥有所有数据，并且很可能找到这样的匹配。memcpy 函数不适合复制它，因为它不支持内存块范围重叠的情况。memmove 函数也不起作用，因为数据应该从中获取的内存块尚未完全初始化。我们需要像逐字节复制一样进行复制。

op[0] = match[0];
op[1] = match[1];
op[2] = match[2];
op[3] = match[3];
...

以下是它的工作原理

abca............
^ - 源地址
   ^ - 目标地址

abcab...........
 ^ - 源地址
    ^ - 目标地址

abcabc..........
  ^ - 源地址
     ^ - 目标地址

abcabca.........
   ^ - 源地址
     ^ - 目标地址

abcabcab........
    ^ - 源地址
       ^ - 目标地址

换句话说，我们必须创建一个重复序列。LZ4 的原始实现使用了一些令人惊讶的奇怪代码来做到这一点

const unsigned dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};
const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};

const int dec64 = dec64table[offset];
op[0] = match[0];
op[1] = match[1];
op[2] = match[2];
op[3] = match[3];
match += dec32table[offset];
memcpy(op+4, match, 4);
match -= dec64;

它逐个复制前 4 个字节，跳过某个魔法数字，完全复制接下来的 4 个字节，并使用另一个魔法数字将光标移动到匹配位置。代码的作者（Yan Collet）不知何故忘记留下关于这意味着什么的注释。此外，变量名令人困惑。它们都命名为 dec...table，但一个是加法，另一个是减法。此外，其中一个是无符号的，另一个是 int。但是，作者最近改进了代码中的这个地方。

以下是它的实际工作原理。我们一次一个字节地复制前 4 个字节

abcabca.........
^^^^ - 源地址
   ^^^^ - 目标地址

现在我们可以一次复制 4 个字节

abcabcabcab.....
 ^^^^ - 源地址
       ^^^^ - 目标地址

我们可以照常继续，一次复制 8 个字节

abcabcabcabcabcabca.....
  ^^^^^^^^ - 源地址
           ^^^^^^^^ - 目标地址

正如我们从经验中了解到的，有时理解代码的最佳方法是重写它。以下是我们想出的方法

inline void copyOverlap8(UInt8 * op, const UInt8 *& match, const size_t offset)
{
    /// 4 % n.
    /// Or if 4 % n is zero, we use n.
    /// It gives an equivalent result, but is more CPU friendly for unknown reasons.
    static constexpr int shift1[] = { 0, 1, 2, 1, 4, 4, 4, 4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[] = { 0, 0, 0, 1, 0, -1, -2, -3 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
}

不出所料，这根本不会改变性能。我只是非常想尝试优化一次复制 16 个字节。

但是，这使“特殊情况”变得复杂，并导致它被更频繁地调用（offset < 16 条件至少执行的次数与 offset < 8 一样多）。使用 16 字节复制来复制重叠范围看起来像这样（仅显示开头）

inline void copyOverlap16(UInt8 * op, const UInt8 *& match, const size_t offset)
{
    /// 4 % n.
    static constexpr int shift1[]
        = { 0,  1,  2,  1,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[]
        = { 0,  0,  0,  1,  0, -1, -2, -3, -4,  4,  4,  4,  4,  4,  4,  4 };

    /// 16 % n - 8 % n
    static constexpr int shift3[]
        = { 0,  0,  0, -1,  0, -2,  2,  1,  8, -1, -2, -3, -4, -5, -6, -7 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
    memcpy(op + 8, match, 8);
    match += shift3[offset];
}

此函数可以更有效地实现吗？我们希望为如此复杂的代码找到一个神奇的 SIMD 指令，因为我们只想写入 16 个字节，这些字节完全由一些输入数据（从 1 到 15）组成。然后只需要按正确的顺序重复它们。

有一个这样的指令称为 pshufb（打包混洗字节），它是 SSSE3（三个 S）的一部分。它接受两个 16 字节寄存器。其中一个寄存器包含源数据。另一个寄存器包含“选择器”：每个字节包含一个从 0 到 15 的数字，具体取决于要从源寄存器的哪个字节获取结果。如果选择器的字节值大于 127，则结果的相应字节将填充为零。

这是一个例子

xmm0: abc.............
xmm1: 0120120120120120

pshufb %xmm1, %xmm0

xmm0: abcabcabcabcabca

结果的每个字节都填充了选定的源数据字节——这正是我们需要的！以下是结果代码的样子

inline void copyOverlap16Shuffle(UInt8 * op, const UInt8 *& match, const size_t offset)
{
#ifdef __SSSE3__

    static constexpr UInt8 __attribute__((__aligned__(16))) masks[] =
    {
        0,  1,  2,  1,  4,  1,  4,  2,  8,  7,  6,  5,  4,  3,  2,  1, /* offset = 0, not used as mask, but for shift amount instead */
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* offset = 1 */
        0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,
        0,  1,  2,  0,  1,  2,  0,  1,  2,  0,  1,  2,  0,  1,  2,  0,
        0,  1,  2,  3,  0,  1,  2,  3,  0,  1,  2,  3,  0,  1,  2,  3,
        0,  1,  2,  3,  4,  0,  1,  2,  3,  4,  0,  1,  2,  3,  4,  0,
        0,  1,  2,  3,  4,  5,  0,  1,  2,  3,  4,  5,  0,  1,  2,  3,
        0,  1,  2,  3,  4,  5,  6,  0,  1,  2,  3,  4,  5,  6,  0,  1,
        0,  1,  2,  3,  4,  5,  6,  7,  0,  1,  2,  3,  4,  5,  6,  7,
        0,  1,  2,  3,  4,  5,  6,  7,  8,  0,  1,  2,  3,  4,  5,  6,
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  0,  1,  2,  3,  4,  5,
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,  0,  1,  2,  3,  4,
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  0,  1,  2,  3,
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12,  0,  1,  2,
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13,  0,  1,
        0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,  0,
    };

    _mm_storeu_si128(reinterpret_cast<__m128i *>(op),
        _mm_shuffle_epi8(
            _mm_loadu_si128(reinterpret_cast<const __m128i *>(match)),
            _mm_load_si128(reinterpret_cast<const __m128i *>(masks) + offset)));

    match += masks[offset];

#else
    copyOverlap16(op, match, offset);
#endif
}

这里 _mm_shuffle_epi8 是一个 内联函数，它编译成 pshufb CPU 指令。

我们可以使用更新的指令一次对更多字节执行此操作吗？毕竟，SSSE3 是一款非常老的指令集，自 2006 年以来一直存在。AVX2 有一个指令可以一次对 32 个字节执行此操作，但针对各个 16 字节通道分别执行。这称为向量置换字节，而不是打包混洗字节——单词不同，但含义相同。AVX-512 VBMI 还有另一个指令可以一次处理 64 个字节，但支持它的处理器只是最近才出现。ARM NEON 有类似的指令，称为 vtbl（向量表查找），但它们只允许写入 8 个字节。

此外，还有一个使用 64 位 MMX 寄存器的 pshufb 指令版本，用于形成 8 个字节。它非常适合替换代码的原始版本。但是，我决定改为使用 16 字节选项（出于严重的原因）。

在 Highload++ 西伯利亚会议上，一位与会者在我的演讲结束后走到我面前，提到对于 8 字节的情况，您可以只使用乘以一个特别选择的常数（您还需要一个偏移量）——我之前从未想到过这一点！

假设我想使用复制 16 个字节的变体。如何避免必须对缓冲区溢出进行额外检查？

我决定不进行此检查。函数上的注释会说明开发人员应该为指定的字节数多分配一块内存，以便我们可以在那里读取和写入不必要的垃圾。函数的接口将更难使用，但存在另一个问题。

实际上，可能会产生负面后果。假设我们需要解压缩的数据是由每个 65,536 字节的块形成的。然后用户为我们提供了一块 65,536 字节的内存用于解压缩数据。但是，使用新的函数接口，用户将需要分配一个例如 65,551 字节的内存块。然后，分配器可能会被迫实际分配 96 甚至 128 千字节，具体取决于它的实现。如果分配器非常糟糕，它可能会突然停止在“堆”中缓存内存，并每次为内存分配（或使用 madvice 释放内存）使用 mmap 和 munmap。由于页面错误，此过程将非常缓慢。因此，这种小小的优化最终可能会导致所有内容都变慢。

因此，我创建了一个使用三种优化的代码版本

1. 复制 16 个字节而不是 8 个。
2. 对于 offset < 16 案例使用混洗指令。
3. 删除了一个额外的 if。

我开始在不同的数据集上测试此代码，并得到了意想不到的结果。

Example 1:
Xeon E2650v2, Browser data, AppVersion column.
Reference: 1.67 GB/sec.
16 bytes, shuffle: 2.94 GB/sec (76% faster).

Example 2:
Xeon E2650v2, Direct data, ShowsSumPosition column.
Reference: 2.30 GB/sec.
16 bytes, shuffle: 1.91 GB/sec (20% slower).

当我看到一切都加速了这么大的百分比时，我一开始真的很高兴。然后我发现其他文件的速度并没有更快。对于其中一些文件，它甚至有点慢。我得出结论，结果取决于压缩率。文件压缩得越厉害，切换到 16 字节的优势就越大。这感觉很自然：压缩率越大，要复制的片段的平均长度就越长。

为了进行调查，我使用了 C++ 模板为四种情况创建代码变体：使用 8 字节或 16 字节块，以及是否使用混洗指令。

template <size_t copy_amount, bool use_shuffle>
void NO_INLINE decompressImpl(
    const char * const source,
    char * const dest,
    size_t dest_size)

完全不同的代码变体在不同的文件上表现更好，但在台式机上测试时，使用混洗的版本总是获胜。在台式机上进行测试很不方便，因为您必须这样做

sudo echo 'performance' | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
kill -STOP $(pidof firefox) $(pidof chromium)

然后我转到一个旧的“开发”服务器（带有 Xeon E5645 处理器），获取更多数据集，并得到了几乎相反的结果，这让我完全困惑了。事实证明，除了压缩率之外，最佳算法的选择还取决于处理器型号。处理器决定何时最好使用混洗指令，以及何时开始使用 16 字节复制的阈值。

顺便说一句，在我们的服务器上进行测试时，这样做是有意义的

sudo kill -STOP $(pidof python) $(pidof perl) $(pgrep -u skynet) $(pidof cqudp-client)

否则，结果将不稳定。还要注意热量限制和功率限制。

因此，我们有四种算法变体，我们需要为条件选择最佳变体。我们可以创建一个具有代表性的数据和硬件集，然后执行严肃的负载测试，并选择平均情况下最佳的方法。但我们没有具有代表性的数据集。为了进行测试，我使用了 网络分析数据 和 美国航班 的样本。但这还不够，因为 ClickHouse 被全球数百家公司使用。通过过度优化一个数据集，我们可能会导致其他数据的性能下降，甚至没有意识到这一点。如果结果取决于处理器型号，我们将不得不显式地在代码中编写条件并在每个型号上进行测试（或者查阅关于定时指令的参考手册，您觉得如何？）。无论哪种情况，这都太耗时了。

因此，我决定使用另一种方法，这对于在我们数据分析学院学习的同事来说是显而易见的："多臂老虎机"。关键是算法的变体是随机选择的，然后我们使用统计数据逐步选择表现更好的变体。

需要解压缩许多数据块，因此我们需要独立的函数调用来解压缩数据。我们可以为每个块选择四种算法之一，并测量其执行时间。与处理数据块相比，这样的操作通常不花费任何成本，并且在 ClickHouse 中，一个未压缩的数据块至少为 64 KB。（阅读这篇关于测量时间的 文章）。

为了更好地理解“多臂老虎机”算法的工作原理，让我们看看名称的由来。这与赌场中的老虎机类似，老虎机有几个杠杆，玩家可以拉动杠杆以获得一些随机金额的钱。玩家可以以任何顺序多次拉动杠杆。每个杠杆都有一个固定的概率对应于给出的金额，但玩家不知道它是如何工作的，只能从玩游戏的经验中学习。一旦他们弄清楚了，他们就可以最大化他们的赢利。

最大化奖励的一种方法是在每个步骤中根据先前步骤的游戏统计数据评估每个杠杆的概率分布。然后，我们根据收到的分布在心理上为每个杠杆“赢得”一个随机奖励。最后，我们拉动在我们的心理游戏中获得最佳结果的杠杆。这种方法称为汤普森采样。

但我们正在选择一个解压缩算法。结果是以每字节皮秒为单位的执行时间：越少越好。我们将把执行时间视为一个随机变量，并使用数理统计对其分布进行评估。贝叶斯方法通常用于此类任务，但将复杂的公式插入 C++ 代码将很麻烦。我们可以使用参数方法，并说一个随机变量属于一个参数随机变量族，然后评估其参数。

我们如何选择随机变量的族？举个例子，我们可以假设代码执行时间服从正态分布。但这绝对是错误的。首先，执行时间不可能是负数，而正态分布在数轴上的所有位置都取值。其次，我假设执行时间在右侧会有一个较重的“尾部”。

然而，有一些因素可能使得仅出于汤普森采样目的估计正态分布是一个好主意（尽管目标变量的分布不一定服从正态分布）。这样做的原因是，计算数学期望和方差非常容易，并且在经过足够多的迭代次数后，正态分布会变得相当窄，类似于我们使用其他方法获得的分布。如果我们不太关心初始步骤的收敛速度，这些细节可以忽略。

这看起来可能有点愚蠢。经验告诉我们，查询执行、网站页面加载等的平均时间是“垃圾”，不值得计算。最好计算中位数，它是一个稳健统计量。但这有点困难，正如我稍后将展示的，这种方法在实践中证明了其有效性。

起初，我实现了数学期望和方差的计算，但后来我决定这太好了，我需要简化代码以使其“更差”。

/// For better convergence, we don't use proper estimate of stddev.
/// We want to eventually separate the two algorithms even in cases
///  when there is no statistical significant difference between them.
double sigma() const
{
    return mean() / sqrt(adjustedCount());
}

double sample(pcg64 & rng) const
{
    ...
    return std::normal_distribution<>(mean(), sigma())(rng);
}

我编写了它，使得前几次迭代不被考虑在内，以消除内存延迟的影响。

结果是一个测试程序，它可以为输入数据选择最佳算法，并提供使用 LZ4 参考实现或特定算法版本的可选模式。

所以有六个选项

• 参考（基线）：原始 LZ4，没有我们的修改。
• 变体 0：一次复制 8 个字节，不进行乱序。
• 变体 1：一次复制 8 个字节，并进行乱序。
• 变体 2：一次复制 16 个字节，不进行乱序。
• 变体 3：一次复制 16 个字节，并进行乱序。
• “bandit”选项，它选择四个优化变体中最好的一个。

如果结果强烈依赖于 CPU 模型，那么找出它究竟是如何受到影响的将是一件很有趣的事情。在某些 CPU 上可能会有非常大的差异。

我准备了一组来自 ClickHouse 中不同表的包含真实数据的数据集，总共有 256 个不同的文件，每个文件包含 100 MB 的未压缩数据（数字 256 是偶然的）。然后我查看了我可以在哪里运行基准测试的服务器的 CPU。我发现了以下 CPU 的服务器

• Intel® Xeon® CPU E5-2650 v2 @ 2.60GHz
• Intel® Xeon® CPU E5-2660 v4 @ 2.00GHz
• Intel® Xeon® CPU E5-2660 0 @ 2.20GHz
• Intel® Xeon® CPU E5645 @ 2.40GHz
• Intel Xeon E312xx (Sandy Bridge)
• AMD Opteron(TM) Processor 6274
• AMD Opteron(tm) Processor 6380
• Intel® Xeon® CPU E5-2683 v4 @ 2.10GHz
• Intel® Xeon® CPU E5530 @ 2.40GHz
• Intel® Xeon® CPU E5440 @ 2.83GHz
• Intel® Xeon® CPU E5-2667 v2 @ 3.30GHz

接下来是最有趣的部分——以下处理器也已可用

• AMD EPYC 7351 16 核处理器，当时是 AMD 的新款服务器处理器。
• Cavium ThunderX2，它是 AArch64，而不是 x86。对于这些，我的 SIMD 优化需要稍微修改一下。服务器有 224 个逻辑核心和 56 个物理核心。

总共有 13 台服务器，每台服务器在 256 个文件上以 6 种变体（参考、0、1、2、3、自适应）运行测试。测试运行十次，在选项之间随机切换顺序。它输出 199,680 个结果，我们可以进行比较。

例如，我们可以将不同的 CPU 相互比较。但我们不应该从这些结果中草率得出结论，因为我们只在单个核心上测试 LZ4 解压缩算法（这是一个非常狭窄的案例，所以我们只得到一个微基准测试）。例如，Cavium 的每个核心的性能最低。但我自己也在上面测试了 ClickHouse，由于核心数量更多，它在重查询方面胜过了 Xeon E5-2650 v2，即使它缺少 ClickHouse 特别针对 x86 所做的大量优化。

┌─cpu───────────────────┬──ref─┬─adapt─┬──max─┬─best─┬─adapt_boost─┬─max_boost─┬─adapt_over_max─┐
│ E5-2667 v2 @ 3.30GHz  │ 2.81 │  3.19 │ 3.15 │    3 │        1.14 │      1.12 │           1.01 │
│ E5-2650 v2 @ 2.60GHz  │ 2.5  │  2.84 │ 2.81 │    3 │        1.14 │      1.12 │           1.01 │
│ E5-2683 v4 @ 2.10GHz  │ 2.26 │  2.63 │ 2.59 │    3 │        1.16 │      1.15 │           1.02 │
│ E5-2660 v4 @ 2.00GHz  │ 2.15 │  2.49 │ 2.46 │    3 │        1.16 │      1.14 │           1.01 │
│ AMD EPYC 7351         │ 2.03 │  2.44 │ 2.35 │    3 │        1.20 │      1.16 │           1.04 │
│ E5-2660 0 @ 2.20GHz   │ 2.13 │  2.39 │ 2.37 │    3 │        1.12 │      1.11 │           1.01 │
│ E312xx (Sandy Bridge) │ 1.97 │  2.2  │ 2.18 │    3 │        1.12 │      1.11 │           1.01 │
│ E5530 @ 2.40GHz       │ 1.65 │  1.93 │ 1.94 │    3 │        1.17 │      1.18 │           0.99 │
│ E5645 @ 2.40GHz       │ 1.65 │  1.92 │ 1.94 │    3 │        1.16 │      1.18 │           0.99 │
│ AMD Opteron 6380      │ 1.47 │  1.58 │ 1.56 │    1 │        1.07 │      1.06 │           1.01 │
│ AMD Opteron 6274      │ 1.15 │  1.35 │ 1.35 │    1 │        1.17 │      1.17 │              1 │
│ E5440 @ 2.83GHz       │ 1.35 │  1.33 │ 1.42 │    1 │        0.99 │      1.05 │           0.94 │
│ Cavium ThunderX2      │ 0.84 │  0.87 │ 0.87 │    0 │        1.04 │      1.04 │              1 │
└───────────────────────┴──────┴───────┴──────┴──────┴─────────────┴───────────┴────────────────┘

• ref、adapt、max - 以千兆字节每秒为单位的速度（所有数据集上所有启动时间的算术平均值的倒数）。
• best - 优化变体中最佳算法的编号，从 0 到 3。
• adapt_boost - 自适应算法相对于基线的相对优势。
• max_boost - 非自适应变体中最好的一个相对于基线的相对优势。
• adapt_over_max - 自适应算法相对于最佳非自适应算法的相对优势。

结果表明，我们能够在现代 x86 处理器上将解压缩速度提高 12-20%。即使在 ARM 上，我们也看到了 4% 的改进，尽管我们没有针对此架构进行太多优化。同样清楚的是，对于不同数据集的平均值，在所有处理器上，“bandit”算法都优于预先选择的最佳变体（除了非常旧的英特尔 CPU）。

在实践中，这项工作的实用性是值得怀疑的。是的，LZ4 解压缩平均加速了 12-20%，在某些数据集上，性能提高了一倍多。但总的来说，这对查询执行时间没有太大影响。很难找到查询速度提高超过几个百分点的实际查询。

当时，我们决定在几个用于执行长查询的集群上使用 ZStandard 级别 1 而不是 LZ4；因为在冷数据上节省 IO 和磁盘空间更为重要。如果您有类似的工作负载，请记住这一点。

我们观察到，在高度可压缩的数据中优化解压缩效果最好，例如主要包含重复字符串值的列。但是，我们已经为此场景开发了一个单独的解决方案，它允许我们显着加快对这类数据的查询速度。

另一个需要记住的点是，解压缩速度的优化通常受压缩数据格式的限制。LZ4 使用了一种非常好的格式，但 Lizard、Density 和 LZSSE 有其他可以更快工作的格式。也许与其尝试加速 LZ4，不如将 LZSSE 集成到 ClickHouse 中。

这些优化不太可能在主流 LZ4 库中实现：为了使用它们，库接口必须进行修改。实际上，这在改进算法时经常发生——优化不适合旧的抽象，并且必须进行修改。但是，原始实现中的变量名称已经得到更正。例如，inc 和 dec 表格已更正。此外，原始实现通过复制 32 个字节而不是 16 个字节将解压缩速度提高了相同的 12-15%，如上所述。我们自己尝试了 32 字节选项，结果不是很好，但仍然更快。

如果您查看文章开头的概要，您可能会注意到我们可以从页面缓存到用户空间删除一个额外的复制操作（或者使用 mmap，或者使用 O_DIRECT 和用户空间页面缓存，但这两个选项都存在问题）。我们还可以稍微改进校验和计算（目前使用 CityHash128 而不使用 CRC32-C，但我们可以使用 HighwayHash、FARSH 或 XXH3）。这两个操作的加速对于压缩较弱的数据很有用，因为它们是在压缩数据上执行的。

无论如何，这些更改已合并到 master 中，并且由此研究产生的想法已应用于其他任务。