E 往无前 | 日志成本下降 25%+！腾讯云大数据 ES Lucene 压缩编码深度优化大揭秘

导语：Lucene 作为 Elasticsearch 的底层索引引擎，提供了灵活的数据检索能力。但在日志数据领域，Lucene 现有的设计导致数据膨胀较为严重，本文介绍了关于 Lucene 底层文件格式的系统性优化思路。这些优化特性，目前都已经上线运行，存储成本整体下降 25%+。同时，本文还介绍了常见压缩算法的原理，希望为更广泛的应用领域起到一定的借鉴作用。

Elasticsearch 提供了丰富的搜索及聚合查询能力，以及配套数据采集与可视化组件，这是很多用户选择 Elasticsearch 来存储日志数据的主要原因。但在实际应用中，使用 Elasticsearch 来存储日志数据却显得异常"昂贵"，有三方面的原因：一是 Lucene 索引数据导致的数据膨胀，二是大多数集群需要依赖于 SSD 存储介质来提供高性能的读写服务， 三是云上集群的副本冗余(ES 的副本机制与云盘自身提供的多副本机制存在冗余)。

为了降低日志数据的存储成本，需要在架构与内核层面，对 Elasticsearch/Lucene 做出一系列的改动。本文重点讲解的是 Lucene 压缩编码的深度优化，核心目的是为了降低单位 Document 所占用的存储空间。所有的优化特性，目前都已上线运行，部分特性已经在内部客户集群中运行了半年到一年多的时间，存储成本整体下降 25%+。

Elasticsearch 应用现状

在多数集群中，用户希望存储更长的周期，但存储成本高昂。面对成本问题，常规的应对手段，包括：降低副本数；缩短存储周期。这些都是一些对服务"有损"的手段。

成本优化的可行思路

 如何有效降低存储成本，可行的思路包括：

在分布式架构层，我们引入了支持 HDD/SSD 的混合存储方案，存储重心尽可能的依赖于 HDD 类型的共享存储服务，同时还优化了主从分片间的数据复制协议。这部分工作，不属于此文的内容范畴。

本文重点讨论的是存储引擎层的压缩编码优化工作，目的是为了降低单位 Document 的存储成本。在介绍这些优化之前，本文会先介绍一下 Lucene 的相关技术背景。

Lucene 索引文件构成概述

这次分享的内容涉及到 Lucene 底层的文件格式的优化，因此，需要先简单介绍一下 Lucene 索引文件的构成：

ES 的每一个索引的每一个分片中，都是一个独立的 Lucene 索引。每一个索引中，通常由 1 个或多个 Segment 构成，每个 Segment 包含了一系列文件，重点文件类型包含：

1. 行存文件(fdt)

用户写入的原始 Document 关联的 JSON 数据，都被存储于该文件中。

2. 列存文件(dvd)

列存文件常被应用于一些 OLAP 分析引擎中，业界应用广泛的列存文件包含 ORC、Parquet 等。

列存文件中按列组织数据，不同 Document 中的同一列/Field 的数据，相邻存放在一起，这样可以加速基于该列的分析性查询。同时，每一个列的类型是确定的，在存储的时候可以进行针对性的编码优化。

Lucene 中的列存文件采用了自定义的格式。

3. 索引相关文件

索引相关文件中，重点文件包含：

字典数据(tim)：

从用户数据中提取的分词信息，被存储在 tim 文件中。同一列的分词信息，相邻存放在一起，有序，而且按块组织。

倒排索引(doc)：

doc 文件中记录了每一个分词关联了哪些文档列表，就是所谓的"倒排拉链表"。

大集群索引文件构成调研

通过对一些大客户以及大集群场景的调研，我们发现， 行存文件、列存文件以及索引字典文件在存储空间上占了近 80%的比重。这样，我们明确了压缩编码优化的重点工作就是针对这三类文件的优化。

当然，不同的业务集群会存在明显的出入，我们建议使用者要对自己集群中的索引文件构成做基础的调研，既有助于审视 Mapping 的设置是否合理，又能够明确知道哪些类型的文件存储占比最大，这样后续优化的时候才能做到有的放矢。

Lucene 压缩编码能力现状

在社区版本中，Elasticsearch/Lucene 支持两种压缩策略选项：

    BEST_SPEED：底层基于 LZ4 压缩算法。压缩与解压速度快，CPU 占用较低，但压缩效果弱。

    BEST_COMPRESSION：底层基于 Deflate 压缩算法。压缩与解压速度慢，CPU 占用较高，压缩效果好。

在 Lucene 8.7 版本之前，这两种压缩策略，仅仅应用于行存文件。在很长的一段时间里，列存文件、索引字典文件里都仅仅采用了简单的编码优化，并未应用这些效果更好的压缩算法。从 Lucene 8.7 版本开始，社区已经开始陆陆续续做了一些优化，例如，将 LZ4 压缩局部应用于列存文件的 Binary DocValue 类型中，以及索引字典文件中。

关于基础压缩算法的拓展

我们在 LZ4/Deflate 压缩算法的基础上，新引入了 Zstandard 压缩算法。通过实际测试发现，Zstandard 压缩算法兼顾了 LZ4 算法的"快"以及 Deflate 算法的"效果好"。接下来，我们从几种压缩算法的实现原理上，来探讨一下 Zstandard 压缩算法"既快效果又好"的底层逻辑。

压缩算法的工作原理，包含两个关键步骤：

1. "宏观层面"寻找重复的字符串

重复的字符串，可以使用一种更简短高效的表达方式来节省空间。关于字符串找重，业界常见压缩算法基本上都是基于 LZ77 算法实现的。

2. "微观层面"使用尽可能少的位来表达每一个字符

这里最常用的算法如 Huffman 编码。Huffman 编码的核心思想：越高频的字符，使用越少的位数来表达。这样起到了数据压缩的效果。

LZ77 算法

上图中的红线，代表着当前压缩到的数据位置。从当前位置开始，每输入一个字符，就会回看之前已经压缩过的数据部分，看是否有已经出现过的字符串。可以回看多少数据，也就是上图中的滑动窗口大小，会显著的影响压缩速度以及压缩效果。一旦找到了一段匹配的字符串以后，就可以使用两个数字来替换表达该字符串：

Distance: 在什么位置找到了重复字符串

Length: 重复字符串的长度是多少

至于未重复的字符串，被称之为 Literal。

不同的压缩算法，关于回看滑动窗口的大小，最小匹配字符串长度，以及{Literal, Distance, Length}这三类数据的编码机制上，都存在明显的区别。

LZ4 算法

LZ4 压缩算法在 LZ77 算法基础上，做了巧妙的改动。LZ4 中要求重复匹配的字符串最小长度为 4，而且使用一个 Hash 表来存储已经出现过的数据的位置信息。当压缩到某一个字符位置时，从该位置连续读取 4 个 Bytes，这样得到一个 Int 值，通过该 Int 值可以快速查看是否存在于 Hash 表中，这样可以加速找重的速度。如果在 Hash 表中存在，则代表着已经至少匹配到了 4 个 Bytes，然后继续检查后面是否有更多的匹配字符。

LZ4 压缩算法关于{Literal, Distance, Length}信息，几乎未做任何编码转换。这是 LZ4 算法快但效果不好的原因。

Deflate 压缩算法

Deflate 中采用了更大的滑动窗口(32KB)，而且定义最小的字符串匹配长度为 3。

Deflate 算法技巧性极高，核心设计概括如下：

1. {Literal, Distance, Length}采用了 Huffman 编码。Literal + Length 数据采用一个 Huffman-Tree, Distance 单独使用一个 Huffman-Tree。

2. Huffman-Tree 编码基于 Literal、Length、Distance 的数据特点做了分区编码优化，依据： 越小的 Length、Distance 值，出现越高频。

3. Huffman 编码的结果在存储的时候也做了优化：只要分配 Codeword 的方案是确定的，只需要按序记录每一个字符对应的 Codeword Length 即可，不需要记录原始 Codeword 信息。而且按序记录的 Codeword Length 信息，可以进一步采用 RLE 编码来节省存储空间。

该算法关于 Huffman 编码的应用可谓是登峰造极，因此，Deflate 算法压缩可以取得很好的效果，但因为大量的"编码再编码"的转换，导致该算法并不够快，而且平均 CPU 占用率较之 LZ4 高出 10~20 个百分点。

Zstandard 压缩算法

ZStandard 压缩算法基于 LZ77 的改进思路，与 LZ4 类似。核心依然是关于{Literal, Distance, Length}信息的编码采用了不同的实现思路：

1. 每一个压缩块中包含 Literals Section 与 Sequences Section。

2. 一个 Sequence 由{LiteralLength, Offset, Match_Length} 构成。

3. Literals 采用 Huffman 编码。

4. {LiteralLength, Offset, Match_Length}采用 FSE 编码。

Zstandard 压缩算法的核心：FSE 编码

FSE 编码由 Zstandard 作者 Yann Collet 实现，基于 Jarek Duda 的 ANS 算法。FSE 算法包含很多位操作技巧，与原始 ANS 论文中介绍的算法有一些出入。但我们可以通过 ANS 算法来粗略理解 FSE 编码的核心思想。

在介绍 ANS 算法之前，我们先来介绍压缩算法领域的另外一个经典算法 Arithmetic Coding：

Arithmetic Coding 设置了一个数字区间 0~1，并且按照每一个字符的出现概率在该区间上为其分配一个子区间：

例如： 假设 A 的出现概率为 0.25， B 的出现概率为 0.1， C 的出现概率为 0.2，…

每一个字符的子区间分配如下图所示(示例与图截取自 Colt McAnlis & Aleks Haecky 《Understanding Compression》)：

当输入 3 个字符"AAA"的时候，编码过程如下图所示：

编码过程涉及到对整个区间的 3 次迭代切割过程，最终，"AAA"编码后得到一个区间值：[0, 0.015625) 

可见，Arithmetic Coding 依赖于浮点数精度来体现编码结果。Arithmetic Coding 的压缩效果非常优秀，但因为涉及到大量的浮点数运算，对 CPU 计算并不友好。

接下来，我们通过一个例子来理解 ANS 算法的设计思想(示例与部分图片截取自 Colt McAnlis & Aleks Haecky 所著的《Understanding Compression》一书)：

假设，某段数据中仅包含 A, B, C 三个字符，且出现的概率分别为：P([A, B, C]) = [0.45, 0.35, 0.2]。

ANS 算法依据这三个字符的出现概率信息，生成一个宽度为 31 的 Tranform Table。将 A, B, C 字符按照特定算法打散填充到 Tranform Table 中，每一个字符在该 Transform Table 中的出现频次与字符在原始数据中的出现概率有关。得到如下表格：

以字符 A 为例：字符 A 离散分布于表格中，共出现了 14 次，在表格中的出现概率约为 0.45(14/31~=0.45)。同 Arithmetic Coding 算法类似，Transform Table 表格也与文本中的字符出现概率有关，但关于概率的表达方式却有明显不同。

将上述表格换一种呈现形式，得到下图：

站在字符 A 的角度来看，它将整个 Transform Table 划分成了 14 个区间，任何一个状态值，一定会落在这 14 个区间的其中一个区间中：

输入字符 A 时，假设此时的状态为 State-X，如果 State-X 大于 14，通过不断的右移位操作，一定可以得到一个小于等于 14 的值 State-Y。

这样，State-X 被表达成了两个部分：State-Y 和右移位过程中溢出的 Bits。State-Y 可以理解为分区号，而 State-Y 与 A 列的交叉值，得到一个新的 State-Z。分区号本身包含在 Transform Table 中， 不需要在输出信息中表达。这正是 ANS 数据压缩原理的奥秘所在。

下面介绍了先后输入两个字符"AB"之后的 ANS 编码与状态转换过程：

1. 输入字符"A"，初始状态为 31。将 31 右移位，直到得到一个小于等于 14 的值(因字符 A 总共出现了 14 次)，得到 7。

第 7 行与 A 列的交集得到新的状态值 16。

2. 输入字符"B"，输入状态为 16，而字符 B 总共在 Transform Table 中出现了 10 次，因此，将 16 右移位以后得到一个小于等于 10 的值，得到 8。

第 8 行与 B 列的交叉得到新的状态值 22。

......

关于 Zstandard 压缩算法的简要总结：

1. 底层基于 FSE 编码，FSE 是 ANS 算法的工程实现。

2. ANS 算法使用"分区号+溢出位"来表达每一个状态值，因分区号信息本身维护在 Tranform Table 中，在编码过程中并不需要输出分区信息，这是 Zstandard 压缩算法"效果好"的原因。

3. 因编码过程大量依赖位移运算来完成状态的切换。这是 Zstandard 压缩算法"快"的原因。

将 Zstandard 压缩算法应用于行存文件压缩

行存文件内部是以 Chunk 形式组织的，Chunk Size 通常为数十 KB 级别。

在 Lucene 8.7 版本之前， 采用 LZ4 压缩算法时设置的 Chunk Size 为 16KB，而 Deflate 压缩算法设置的 Chunk Size 为 60KB。

我们先将 Zstandard 压缩应用到了行存文件中，而且尝试了不同的 Chunk Size 后的效果，如下图所示：

可以看出来，Zstandard 压缩算法在压缩率上与 Deflate 相当，而压缩速度甚至略优于 LZ4。相较于 LZ4，压缩效果有 30%+提升。

值得一提的是，从 Lucene 8.7 版本开始，社区也针对 LZ4 与 Deflate 压缩算法做了优化，引入了 Preset Dictionary 特性，如下图所示：

Preset Dictionary 特性引入了 Chunk-Group 概念，在一个 Chunk-Group 内部，第一个 Chunk 作为字典 Chunk， 后面的 Chunk 基于第一个 Chunk 的字典数据进行压缩，解压的时候，也仅需要读取字典 Chunk 与对应的 Chunk 即可，无须解压 Chunk-Group 中的所有 Chunk。

这里简单解释一下该特性的优化思想。

Chunk 级别压缩存在两点局限性：

1. Chunk 的开始位置，无法得到好的压缩效果。因为在回看的时候缺乏可参考的字典数据。

2. Chunk 内部找重，只见树木不见森林，无法看到更大范围的重复数据。

因此，容易想到的一种简单的改善压缩效果的思路：增大 Chunk Size，这样可以在一个更大的数据区间内共享字典数据。但增大 Chunk Size 会导致随机访问时延变大。

Preset Dictionary 引入的 Chunk-Group 级别的压缩，可以说是一个很好的折中实现方案：既可以在 Chunk-Group 级别内共享字典数据，又可以有效避免随机访问时延明显增大。在我们的测试场景中，发现 Preset Dictionary 会有 10%以上的压缩效果提升，实际改善效果与业务数据特点相关。

Zstandard 压缩算法尚不支持 Chunk-Group 能力，但我们为 Zstandard 压缩提供了多种 Chunk Size 选项，在部分场景中，使用较大的 Chunk Size，也能取得较好的改善效果(大多数场景下，使用默认的 Chunk Size 选项即可满足需求)。另外，Zstandard 提供了预训练字典能力，预先训练好的字典数据可以在全局范围内共享，这比 Preset Dictionary 特性共享字典的区间范围更大，取得的压缩改善效果更佳。

对倒排索引字典文件的优化

索引字典文件中存储的分词数据，也是按块组织的，而且已事先做了排序，如下图所示：

在 Lucene 8.7 版本之前，索引字典文件仅仅支持简单的前缀编码优化，压缩效果还有较大的改进空间。社区从 Lucene 8.7 版本开始，引入了 LZ4 压缩与 LOWERCASE_ASCII 编码。腾讯 Elasticsearch 在此基础上也扩展了关于 Zstandard 压缩算法的支持：

从实际应用效果来看，Terms Dictionary(tim)文件占用空间下降 40%+。

关于列存文件的几点优化

列存数据(DocValue)对于聚合分析类查询起到了很好的加速作用，这部分先简单介绍一下原有的列存文件组织结构，然后介绍了关于 SortedSet 以及 Numeric 两类 DocValue 的优化。

列存文件组织结构

在列存文件中，不同的 DocValue 类型，拥有不同的内部结构定义，上图给出了 SortedSet 与 SortedNumeric 两种 DocValue 的内部结构定义。

SortedSet DocValue 优化

通过对大集群的应用调研，发现大量使用了 keyword 类型。keyword 类型默认开启了 DocValue，底层对应着 SortedSet DocValue 类型。

我们先来看一下 SortedSet DocValue 的内部结构：

SortedSet DocValue 结构中重点需要理解的就是 Ord Value 与 Terms Dictionary 部分：

Terms Dictionary：该列所有 Value 的集合。

    Ord Value:  为每一个 Value 分配的一个数字编码。这样可以加速一些聚合分析类查询。

通过调研，我们发现应用中存在大量高基类型(High Cardinality)的 keyword 列，通过解析 SortedSet DocValue 内部的构成，Terms Dictionary 部分占据了极高的比重。而 Terms Dictionary 数据在存储的时候，仅仅做了简单的前缀编码。

我们为 SortedSet DocValue 的 Terms Dictionary 提供了 Chunk 级别的压缩能力：

从实际应用效果来看，SortedSet DocValue 的存储空间下降 40%+：

该特性已经贡献给了 Apache Lucene 社区(LUCENE-9663)，并且成为 Lucene 8.9 版本的 Highlight 特性：

Numeric DocValue 优化

在时序数据场景中，存在大量的浮点数类型。Lucene 的 Numeric DocValue 仅支持 Long 类型，因此，Elasticsearch 将浮点数转换成了 Long 类型。

Numeric DocValue 在存储 Long 类型时，采用了定长编码的思路：依据数据集合的分布区间来决定采用多少位来表达每一个数值。

Elasticsearch 将浮点数转换成 Long 类型的方法，依据了 IEEE-754 标准。这种转换存在一种显著的问题，如下表所示：  

数值上相近的两个浮点数 31.245 与 31.875，基于 IEEE-754 标准转换以后得到的二进制位，可能存在较大的差异。

Lucene 采用了 64 位的 Long 值来表达每一个浮点数，当列的基值较大时，转换出来的 Long 值区间极为发散。这导致 Lucene 底层在做定长编码时，只能使用 64-Bits 来表达每一个 Long 值：

关于浮点数的优化，业界应用较为广泛的便是 Facebook Gorilla 论文中提及的 XOR 算法：

该算法假定同一时间线中的相邻值变化不大，因此可以通过 XOR 算法寻找出变化的二进制位。

通过实际测试，我们发现 XOR 算法的效果并不佳，主要原因：Elasticsearch 并不支持时间序列的数据组织方式，或者说，数据可能是杂乱无序的。

在对一些大集群做详细调研的时候，我们通过解析 Numeric DocValue 的内部构成，发现在很多场景中，0 值占据了较高的比重。基于定长编码的思路，0 值也需要使用固定的位数来表达(通常会占用 64 位)。

从业务侧来看，某一个指标大部分时间段的值都为 0 值，这是正常现象。从另外一个角度来看，0 值是一个非常重要的默认值。

一个简单的思路就是在写入的时候，直接将 0 值抛弃，但 0 值与 NULL 值往往代表着不同的业务含义，例如，NULL 值可能意味着这次没有采集到指标，但并不代表指标值为 0。因此，在底层考虑对 0 值存储优化的时候，既要业务无感知，又不能带给业务侧任何歧义。

Numeric DocValue 包含 Dense 模式与 Sparse 模式：

    Dense 模式：Segment 中每一个 Document 都拥有该 Field 的值

    Sparse 模式：Segment 中只有部分 Document 拥有该 Field 的值

因此，在优化的时候，需要考虑对这两条路径的支持。这里仅以 Sparse 模式为例来简单介绍方案优化思路：

优化之前，Numeric DocValue 中使用了一个 Bitmap 来描述哪些 Document 拥有该 Field 的值。优化之后，使用了两个 Bitmap 来表达 0 值相关的 Documents 以及非 0 值相关的 Documents，这样，Values 部分仅仅存储非 0 值即可：

在读取的时候，如果一个 Doc ID 出现在 0 值相关的 Bitmap 中，则在返回列值的时候会自动填充 0 值，如果出现在非 0 值的 Bitmap 中，则依据该 Doc ID 在非 0 值 Bitmap 中的位置来对应读取 Values 中的值。读取场景需要考虑关于随机读取与顺序读取的支持。

如果某一个特殊场景中存在一个高频出现的其它值，也可以基于该方案思路进行优化。

该方案的优化效果与 0 值占比有密切关联。下图选取了一个 0 值占比超过 96%的场景，Numeric DocValue 存储空间下降 90%+：

为各种压缩新特性提供细粒度配置开关

压缩可以使得存储空间下降，但会带来额外的性能开销。因此，我们允许每一个压缩特性都可以通过配置开关来控制，这样，业务应用方可以按照子的负载/数据访问特点以及成本控制需求，来灵活选用不同的压缩策略：

后续优化方向建议

1. 深入理解日志数据特点的字典编码压缩策略

在通用压缩算法上，已经很难取得明显的突破。Elasticsearch 中存放的日志数据，都以 JSON 结构来表达，如果能在更大的范围内共享字典数据的话，将会是一个很好的优化方向。

2. 智能压缩策略

我们已经提供了针对各类文件格式的优化特性，但在实际应用中，需要结合用户的数据特点以及负载特点，智能化的给出最佳的压缩策略。

3. 关于 pos 文件的优化

个别用户场景中，存在 pos 文件过大的问题，社区方案存在较大的优化空间，感兴趣的同学可以在这个方向上探索一下。

本文内容总结

关于本文内容的简要总结：

1. 从索引文件构成调研，明确了重点优化方向（行存文件/列存文件/索引字典文件）。

2. 介绍了社区 Lucene 的压缩编码支持能力现状。

3. 引入了 Zstandard 作为 Lucene 的基础压缩算法。并且从压缩算法原理的角度出发，解释了 Zstandard"既快又好"的原因。

4. 针对行存、列存、索引字典文件的详细优化思路。

5. 针对不同的业务特点，提供了细粒度的配置参数。

6. 给出了未来可能的几点优化方向建议。