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

《E往无前》系列将着重展现腾讯云大数据ES在持续深入优化客户所关心的「省！快！稳！」诉求，能够在低成本的同时兼顾高可用、高性能、高稳定等特性，可以满足微盟、小红书、微信支付等内外部大客户的核心场景需求。

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. 给出了未来可能的几点优化方向建议。

免费体验活动专区

Elasticsearch 新用户可享 2核4G，0元 体验 30 天！顺畅体验云上集群

推荐阅读

关注腾讯云大数据公众号

邀您探索数据的无限可能

点击“阅读原文”，了解相关产品最新动态

↓↓↓