介绍 MinLZ 压缩算法

存在不同类型的压缩算法和非常好的实现。在 MinIO，我们已经使用了 Snappy 的增强版本，它一直为我们服务良好。但随着时间的推移，我们发现了一些可能的改进，可以更好地对压缩数据进行编码。因此，我们设定了我们的目标：

• 在保持我们压缩器的现有速度的同时，是否有可能将压缩率提高到足以证明通过简单的升级路径进行升级是合理的。
• 仍然提供性能优于 IO 的压缩/解压缩，因此可以安全地保持开启状态。

这将解释创建 MinLZ 的一些设计注意事项。MinLZ 是由 MinIO 开发的一种压缩算法。主要目标是提供一种格式，该格式可提供一流的压缩，同时即使使用适度的硬件也能提供非常快速的解压缩。

Snappy/LZ4 Heritage

我们必须考虑的一个重要因素是减压速度。我们还必须考虑不实现需要某些 CPU 功能来快速作的功能。由于 CPU 正在向更多内核扩展，因此我们专注于为高并发压缩和解压缩提供良好的选项，同时以类似的单线程性能为目标。由于我们的主要目标是保持速度，因此我们决定坚持使用固定大小的编码，并使用字节对齐作，因为这允许在没有特定 CPU 指令的情况下进行非常快速的解码。此外，我们希望我们的压缩输出可以选择性地使用索引进行搜索，并且始终能够并发地进行（解）压缩。这意味着 MinLZ 还保持压缩块彼此独立。取消这些限制中的任何一个无疑都会增加潜在的压缩率——但我们也会开始与像 Zstandard 这样的优质压缩器重叠，它提供上述所有功能，但通常速度较低。我们对压缩速度的目标是保持相同的速度，但可能会牺牲一些编码速度来换取解压缩速度。我们将 MinLZ 视为下一代 LZ4/Snappy，并在 Go 实现中提供与 Snappy/S2 的完全向后兼容性。

静态编码和测试集

选择静态编码意味着动态适应内容类型的灵活性很小。不同的内容将具有不同的匹配特征。我们发现，大多数用于测试的 “典型” 测试集并不能很好地反映我们遇到的典型内容。对于静态编码，这一点尤其重要，因为一种数据类型的改进很容易在另一种数据类型中产生回归。我们的主要数据类型是序列化数据。这意味着这些数据类型的改进在我们的决策中具有最高的权重。这包括 HTTP 日志、JSON、CSV、XML 等人类可读内容，以及 Protobuf、MsgPack 和数据库转储等二进制类型。已检查混合文件 （文件系统备份）、文件系统图像和自然文本以进行回归，但尚未给予特殊考虑。

区块改进

“块” 是一个作流。通常这些是 “发出文本” 或 复制作。发出 Literals 只是告诉解码器将一定数量的给定字节附加到输出中，然后作为复制作的基础。LZ4 的解压缩速度非常快，因为解码器中的分支非常少。这些分支很容易预测 CPU。我们的总体印象是，Snappy 编码的灵活性是获得更高效结果的更好方法，值得为此付出一点点努力。我们决定继续采用“Snappy”方法，但看看是否有任何可以改进的地方。

复制编码

副本是 LZ77 编码的基础。解码流时，复制作基本上告诉编码器 “返回特定偏移量并复制一定数量的字节到 output”。这是 Snappy 可以的偏移量/长度编码：

我们看到的第一个限制是长度非常有限。S2 添加了一个带有无效 “Tag 1， Offset = 0” 编码的 “repeat”，允许它扩展之前的匹配。这允许将任何长度的匹配编码为 copy+repeat。然而，它浪费了所有的偏移位，因为这必须为 0 才能表示重复。另一件突出的事情是 Snappy 从 16 位跳到 32 位偏移。这里使用的 32 位中的许多位通常由 0 组成，因为块从未真正达到这个大小。最后，在观察统计数据时，我们发现从 Tag 1 偏移量移动一位到 length 会产生更好的压缩效果 - 即使重复成本较低。

查看偏移量，我们首先删除了无效的 “offset=0” 值。不必检查这一点似乎比无条件添加基值更重要。其次，较长的偏移量最小为 64 字节。虽然这确实实现了稍长的偏移量，但这不是主要目标。此基值的目标是避免在解码时检查重叠的副本。如果基值为 64，我们保证始终可以复制 long matches 64 字节，而不会有与输出重叠的风险。这会将一些分支从 decoder 移动到编码器。我们确实尝试了使用更高的基值，但它几乎没有什么好处，而且只是限制了编码器的灵活性。另一个变化是添加了更灵活的长度编码。这意味着与文字编码类似，我们保留一些长度作为特殊值，这将从后面的 1-3 个字节中读取实际长度。这些都有 base 值，这也减少了 decoder 中的进一步分支。

重复编码

“重复”是指与最后一个匹配项具有相同偏移量的副本。这可用于扩展最后一个副本，或者更常见的是，在与最后一个输出不同的一个或多个字节后恢复复制。如上所述，S2 中的重复编码有点浪费，因为它旨在适应现有编码。经过一些实验，我们发现长长度文字作非常罕见，因此我们决定从长度编码中 “获取” 一位，并使用它来表示重复。

repeat length 和 literal length encoding 是相同的，因此可以共享此解码。

我们尝试了不同的重复类型。首先是小偏移的重复。这将允许我们对小的插入或删除进行编码。然而，从几次实验来看，这几乎没有影响，由于从其他地方拿走了位，对一些有效载荷进行了小幅改进，而对其他有效载荷进行了回归。我们决定放弃这一点，因为不值得付出复杂性和额外的处理以及检测这些的成本。同样，我们尝试了更长的重复历史记录，类似于 zstandard - 和 “promoted repeats”，其中经常使用的偏移量将被存储。然而，同样，收益是微不足道的——虽然一些有效载荷受益，但额外的复杂性、额外的解码处理和其他有效载荷的大小回归使我们放弃了这一点。

融合文本

看看 LZ4，突出的一点是它对许多小的文字和复制块非常有效。这是因为作的基本编码是这样完成的......

LZ4 编码：

在 Literals 和短副本很少的情况下，这两个作加起来只有一个字节的开销。同样，在做了一些统计分析后，我们发现大多数字面量块都非常短。事实上，大多数都小于 4 字节。如果开销超过一个字节 - 存储标签和长度加上复制标签，这些效率非常低。对于长偏移量，我们发现通过将最大偏移量限制为 2MB 来轻松节省 3 位。限制偏移量会限制可以引用的可能匹配项，但我们发现在大多数有效负载中，长偏移量通常非常罕见。平均而言，能够发出融合的 Literals 弥补了非常长的偏移量的好处。为了用融合的文字有效地表示 short+closer 匹配，我们还添加了一个类似于 copy 的 2 字节偏移量的融合文字模式。这样，我们最终得到了以下融合文字的编码类型：

我们现在可以用 1 个字节的开销来表示短文本 + 中等偏移量，而“长偏移量”可以有 0 到 3 个文本，而无需任何额外的开销。有限的反向引用偏移量只会“影响”实际大于 2MiB 的块，我们发现它对大多数实际内容的影响很小，因此我们认为这是一个值得的权衡。此外，限制偏移量还可以减少引用 CPU 缓存之外的数据的可能性，从而提高解压缩速度。融合 Literals 的长度有限，并且保证它后面始终跟着一个 4 字节的复制，这也意味着复制这些 Literals 可以比单独的块少一些分支来完成。要阅读编码的所有详细信息，请参阅 github 存储库中的 SPEC.md。我们还在 internal/reference 中提供了简化的压缩/解压缩示例。

流改进

流格式与 Snappy/S2 基本保持不变，只是不再使用以前的压缩块。

流标识符

流标识符将更改为新的魔术字符串。此外，流标识符现在包括流上预期的最大数据块大小。这允许以适当的大小分配缓冲区。

EOF 验证

流现在具有 EOF 验证。以前（在 Snappy 中）无法在块边界处检测截断的流。EOF 块（可选）包括流应生成的解压缩字节数。有效的 MinLZ 必须包含一个 EOF 块，但后面可以跟另一个流标识符。

流查找

MinLZ 从 S2 中转移流索引。流索引允许在压缩流中随机查找。索引可以添加到流的末尾，也可以单独保存，具体取决于使用案例。所有索引都是可选的。

用户定义的数据块

用户定义的块已进行一些修改。

• 0x00 -> 0x7F是内部类型，不应用于用户数据。
• 0x80 -> 0xBF现在被定义为“可跳过的用户区块”。当遇到未知 chunk 时，可以安全地跳过它。
• 0xC0 -> 0xFD是“不可跳过的用户区块”。如果遇到具有这些 ID 之一的未知块，则应停止解码。

您仍应使用其他检查来确保 chunk 是预期的类型。

效率和优势

那么这一切有多大的不同呢？以下是一些统计数据和图表，显示了每种数据类型的有效节省，这意味着与现有压缩相比，您将免费获得 10-20% 的磁盘空间。