背景

日志/埋点/业务数据库是互联网公司大数据分析处理的的几种主要数据来源，其中日志数据主要用于业务数据分析/监控告警/生产排障等重要场景，日志数据的特点是Schema较弱，包含大量文本数据，如何针对日志等文本数据进行检索分析一直是大数据领域非常热门的方向。目前最主流的方案是基于ELK三件套（ElasticSearch, LogStash, Kibana）, LogStach负责日志采集，ElasticSearch负责日志的存储和查询，Kibana负责数据可视化。ElasticSearch是非常强大的分布式搜索引擎，其基于Lucene的反向索引，提供了非常高效的文本检索能力，可以满足绝大部分的业务需求。但是随着日志数据量的逐渐增加，在实际的场景中，ELK方案也会碰到如下问题：

ElasticSearch的存储成本较高，相比于大数据领域常用的列存数据格式，相同的数据在ES中侧存储成本大概是2-5倍。
ElasticSearch非常适合中低频文本检索，但是在涉及到大规模数据扫描的数据分析场景，Spark/Presto或者ClickHouse等OLAP引擎显然更加合适和高效。
ELK三件套主要针对日志排障/分析场景，如果需要使用大数据平台的组件和工具链对日志数据进行处理，比如ETL加工，Adhoc分析，报表平台等，需要额外落一份数据在HDFS上，增加存储和使用成本。
针对1和2，目前业界有一些公司在尝试使用通过的OLAP引擎存储日志数据，在存储成本，和大规模数据扫描的数据分析场景都有较大收益。在排障常见的文本检索场景，则通过正向索引（用户检索时常带有的app_id，时间范围等）缩小数据扫描范围，通过OLAP引擎非常强大的现场计算能力(向量化Reader扫描数据/向量化算子等)暴力扫描处理，虽然性能和效率无法和ElasticSearch的反向索引相比，但大部分时候也可以控制在用户能接受的范围内。但是这种方案一般都是基于ClickHouse等OLAP引擎，还是无法解决和基于Hadoop的大数据平台的数据和工具链无法完全打通的问题。此外对于需要保留长久历史的日志数据，对于比较老的日志数据可能访问非常低频，ClickHouse存储和计算一体的架构可能会存储先到达瓶颈造成资源的浪费，新的热数据使用ClickHouse存储，老的冷数据使用基于Hadoop的存储计算分离的架构可能是成本更低的方案。通过大数据平台开发的计算引擎（如Spark/Presto/Trino）和开放的数据存储格式（如ORC/Parquet/Icberg/Hudi）是否能够统一支持日志的不同使用场景，特别是排障场景的业务需求，还未看到业界有成熟的实践经验。本文不讨论日志平台在采集，存储，查询等方面的架构选型和设计问题，主要关注在如何基于大数据平台的组件（具体来说是Trino + Iceberg）如何能够高效的支持日志数据在排障场景的查询效率问题。

场景分析

在日志排障的场景中，日志数据的Schema一般包含公共字段(如log_id, app_id, job_id, timestamp等)和log_msg字段（存储文本数据），典型的用户查询条件一般会包含公共字段的筛选和文本字段的检索条件。针对公共字段的筛选如何根据筛选条件在扫描数据时跳过不相干的数据，主要通过表分区及正向索引的能力，但是剩余需要扫描的数据可能依然是一个比较大的量级，可能无法满足排障场景交互式响应的要求，同时计算也会占用大量的CPU/IO资源。针对文本字段的检索条件，正向索引无法帮助进一步缩小数据扫描范围，反向索引是必然的选择。

针对日志排障的场景，我们需要依赖正向及反向索引的能力，简单来说，查询的性能主要取决于两点：读取索引的代价，基于索引实际扫描的数据能够接近逻辑上过滤条件需要读取最少数据条数的程度。

正向索引的使用

针对公共字段的筛选，在Trino + Iceberg on HDFS的架构中，可以使用的Data Skip手段包括：

分表，不同业务或者不同类型的日志可以放到不同的Iceberg表中。
分区，比如使用时间分区和应用分区，查询的过滤条件一般都会包含分区的过滤条件(查询某个时间段，某个应用的日志)，像Trino/Spark等计算引擎都支持下推过滤条件跳过不需要的分区文件。不过分区字段的基数不能过多，否则可能会产生大量小文件，影响写入和查询的效率。
正向索引，对于log_msg文本字段外的常用过滤字段，可以使用MinMax/BloomFilter/BitMap等索引Skip数据文件，关于Iceberg上索引的设计可以参考：通过索引加速湖仓一体分析
数据排序组织，通过对数据进行排序组织，可以让正向索引发挥更大的Skip数据效果，关于如何对Iceberg数据进行排序组织可以参考：通过数据组织加速大规模数据分析

反向索引的设计

Apache Lucene是应用范围最广的基于反向索引的文本检索框架，参考通过索引加速湖仓一体分析我们可以基于Lucene实现一种反向索引，具体的思路如下：

生成文件级别的Lucene索引，以文件中的行号作为Lucene索引中的DocID，并通过Iceberg metadata文件记录维护数据文件和Lucene索引的关系。
在Trino引擎中，优化SQL查询执行计划时，增加Optimization Rule支持将文本检索过滤条件下推。
在Trino Worker节点中的task扫描数据文件时，根据Iceberg数据文件的metadata信息中的Lucene索引信息和下推的文本检索过滤条件判断是否可以Skip当前数据文件。
如果无法通过Lucene索引直接Skip当前数据文件，可以通过Lucene索引得到文件中符合文本检索条件的DocID列表，增强Trino中的ORC或者Parquet Reader，在读取Orc/Parquet文件时，通过DocID列表判断是否可以进一步Skip文件中更小粒度的Stripe/RowGroup。
Apache Pinot就是基于Lucene实现Text Index，并对Text Search相关UDF函数进行了增强。但是对于日志检索的场景，Trino+Iceberg的湖仓方案使用Lucene构建文本索引会存在如下的问题：

Lucene更多是针对本地文件系统设计的反向索引，并不完全适合HDFS这样的分布式文件系统，比如，Lucene将索引信息的不同部分存储在不同的文件中，生成文件级别的Lucene索引会产生大量的小文件，整个Iceberg表的文件数量可能会有量级的膨胀，对于HDFS Namenode产生较大压力。
Lucene索引文件包含的信息比较丰富，比如记录term在Doc中出现的频次，用于打分排序等，导致Lucene索引数据量比较大，有时甚至超过数据文件本身大小。但是在日志排障或者日志分析场景中，更多是需要精确的文本检索，并不需要打分排序等的能力。
Lucene支持的并发写入，索引更新等能力在日志场景中并不需要。
反向索引一个最核心的特点是对文本字段进行分词，然后保存分词后的Term和数据文件之间的关系。如果不考虑Term在数据文件中出现的DocID信息，只保存Term是否在文件中出现，BloomFilter是非常合适的数据结构，我们可以构建一种TokenBloomFilter索引，将数据文件文本字段分词后的Term都插入BloomFilter中，用户检索时，就可以通过下推的Term过滤条件，使用BloomFilter判断该Term是否在文件中出现过，从而跳过扫描不相干的文件。TokenBloomFilter索引的优势是BloomFilter虽然有FPP(False Positive Possibility)的可能，但是不用保存Term，文件大小会非常小。缺点是由于只能判断Term在文件中是否存在，在Term存在时，无法做文件内更细粒度的Data Skip，对于超低词频Term的检索效果不错，但是对于中高词频Term的检索的Data Skiping效果会显著降低。

基于之上的分析，我们还需要一种相比Lucene更加轻量级的文本索引，支持湖仓一体场景的文本检索类需求，具体的设计目标包括：

文本索引大小相比于数据文件应该尽可能地小，减少索引存储的代价，索引越小，构建索引的ROI越高，尤其是在像日志这样数据规模超大的场景。
文本索引的数量应该尽可能的少，对应一个数据文件，最好是一个或少量文本索引文件，以减少因索引对于HDFS NameNode的压力。
文本索引应该能支持根据文本检索过滤条件返回满足条件的DocID列表，用于数据文件内部更小粒度的Data Skip。
根据以上的设计目标，我们实现了一个轻量级文本索引：TokenBitMap索引，它分为两个部分：Term和PostingList信息，Term由数据文件中文本字段经过分词后得到，PostingList信息记录每个Term在数据文件中出现的DocID列表。考虑到PostingList信息一般需要占用的存储空间远大于Term，在使用文本索引匹配过滤条件时，如果Term未出现，可以直接返回，无需读取PostingList信息，所以可以将Term和PostingList信息分开存储，这对于低频词的检索会有很大好处。轻量级文本索引包括字典文件和PostingList信息文件两个独立的文件，使用字典存储文本分词后的Term及其到PostingList信息的映射，PostingList信息存储每个term在数据文件中出现的DocID列表。

TokenBitMap字典的设计

字典（Map）是我们在代码开发中最常用的数据结构之一，例如Java中最常用的HashMap，有非常好的KV读写性能。但是对于文本索引的字典来说，使用HashMap作为字典可能不是一个非常合适选择，最主要的原因是无法有效地压缩导致占用内存空间以及序列化后在磁盘上占用空间较大，在基于文本过滤条件使用文本索引字典进行Data Skip的时候，对于文本索引字典可能只会进行一次或少量几次getValue的访问，不会高频访问，且所占用的时间对于整体查询影响很小，所以字典的KV读写性能不是考虑的重点，影响访问文本索引字典性能的关键是从HDFS中读取字典文件以及反序列化花费的时间，其中的关键是字典文件的大小。

我们参考Lucene的实现，采用FST（Finite State Transducer）数据结构存储文本索引字典，FST是一个有限状态机（Finite State Machines)，具有这样的特性：

确定：意味着指定任何一个状态，只可能最多有一个转移可以遍历到。
无环：不能重复遍历同一个状态
transducer：接收特定的序列，终止于final状态，同时会输出一个值。
对于KV字典{mon -> 2, tues -> 3, thurs -> 5, tye ->99}, 构建出来的FST示意如下所示：

从开始节点0开始，通过确定的状态转换，一直遍历到Final节点3，我们可以匹配所有之前插入的key值，如果输入的key值不存在，比如"mad"，从节点1往后的状态转化失败，则说明key在FST中不存在。transducer用于输出value值，比如对于key值"thurs"，transducer最终输出的value为状态转换路径上的值之和，即“3 + 2 + 0 + 0 = 5”。可以看到FST数据结构的特点是它可以重用key的前缀和后缀，这对于文本类型的词来说会有非常好的压缩效率，使得它的内存占用和序列化大小相比于其他字典实现有显著优势。

基于FST实现的文本索引字典，Key为文本字段分词后的Term，Value为对应Term在PostingList文件中的File Offset，我们使用实际的日志数据与HashMap进行了比较，字典内存占用小了约15倍，另外虽然getValue查询时间慢了10倍左右，但是都是毫秒以下，在我们的场景中不会对查询时间有任何影响。

TokenBitMap PostingList文件的设计

PostingList文件保存每个Term对应的DocID列表，即在数据文件中出现过的行号列表。对于PostingList文件，和字典文件类似，在文本检索以及湖仓一体的架构下，从性能和成本的角度，我们更关注的是PostingList文件的大小，所有的实现策略也都是主要围绕如何减少PostingList文件的大小以及内存占用，部分参考和重用了Lucene的设计，也有一些特定的调整。对于DocID列表，由于天然的是由从0开始的正整数组成，我们很自然地会想到使用BitMap这种信息密集存储的数据结构，Java生态也提供了例如RoaringBitMap这种比较高效的BitMap实现库可以直接使用，对于PostingList文件的存储格式，我们更进一步做了2个主要的优化：

PostingList文件的DocID列表信息主要是用于计算引擎在读取数据文件时，可以根据DocID列表进行数据文件内部更细粒度的数据块Data Skip，比如ORC文件内部Stripe和RowGroup的过滤，如果某个Term在文件中出现的十分频繁，则DocID列表会非常大，但是可能没法过滤任何文件内的数据块，那么这种存储代价很大，但是过滤效果很差的DocID列表存储的价值就非常小。可以支持一个配置参数，DocID列表高于该参数阈值的直接忽略，不保存在PostingList文件中。
BitMap在DocID列表较大时可以非常好地压缩数据，但是当DocID列表较小时，相比于BitMap较为复杂数据格式带来的额外代价，int数组可能是代价更小的选择。
针对第二点优化，经过测试，基本上DocID数量在50个以下时，用Int数组存储的代价更小，DocID数量在50个以上时，用RoaringBitMap代价更小。因为DocID代表的是数据文件中的行号，天然的是由从0开始的正整数，一个日志的数据文件经过优化后都是在256M左右（有一个Iceberg表管理服务专门负责异步的数据文件优化，比如小文件合并，数据排序组织等，可以控制预期的文件大小），所以DocID的大小基本都是在百万量级，这意味着DocID列表中的值基本上会在0到百万的区间内。我们基于这个事实，对于Int数组存储的DocID列表，可以通过BitPacking技术进行进一步的压缩。

不同于Java中int默认的4字节存储，BitPacking算法采用变长字节存储int数据，每个字节的第一个比特位用作标志位，不存储实际数据信息，该标志位用0代表当前字节属于当前int，1代表当前字节开始下一个int，剩余的7个比特位存储数据信息，如下所示：

可以看到BitPacking算法对于越小的正整数压缩效果越好，基于这个特点，我们还可以先对int数组进行Delta Encode，比如对于int数组[73, 300, 302, 332, 343, 372]，Delta编码后变为[73, 227, 2, 30, 11, 29]，int数组里的数值都会减小，更有利于BitPacking算法的压缩，采用int数组还是RoaringBitMap存储的阈值可以调整到100左右。在实际数据的测试中，我们发现int数组存储的DocID列表可以使用BitPacking压缩至原本的1/2到3/4左右，由于实际场景中大部分Term都是中低词频，这对于减少PostingList文件的大小有非常大的帮助。

分词器的选择和定制

分词器的选择也会对文本检索的效果和性能产生非常重要的影响，这主要体现在：一，分词后的Term应该尽量覆盖用户检索的关键词，否则，用户使用该关键词检索时无法利用文本索引加速查询。二，用户不会用来检索的关键词，应该尽量在分词时过滤掉，因为越多的Term数量，也就意味着越大的字典文件和PostingList文件。所以分词器的选择和定制关键在于深入理解业务场景，通过合理的定制化尽量在构建文本索引的分词阶段过滤掉用户不会用来检索的Term关键词。

Lucene提供了丰富的Analyzer/Tokenizer实现，可用于不同分词场景，同时Analyzer及相关类也提供了丰富的扩展接口，用于定制化实现 ，我们基于Lucene，结合日志场景的数据特点，也进行了一些定制化的实现，主要包括：

STOP_WORDS的扩展，一些在日志中特别高频出现，但是并不具备过滤价值的词，可以通过配置在STOP_WORDS中在分词阶段直接丢弃。
一些定制的TokenFilter，比如超长的二进制字符串，不太可能被用于文本检索，但是FST字典存储代价会很大。还有超高频出现一些timestamp数据，每条数据的timestamp可能都不一样，基数非常大，FST字典和PostingList存储代价都会很大，但是timestamp会保存在单独字段中，可使用正向索引进行过滤，log_msg中的timestamp实际对于用户检索数据几乎没有用处。
不同于字典和PostingList文件的设计和优化主要是单纯的技术问题，分词器对于文本检索的成本和性能也有非常大的影响，但是其选择和优化依赖于对于业务使用场景的深入洞察和定制化，需要平台和业务用户深入沟通合作才能通过定制化达到更好的效果。

Text Match函数支持

日志平台可以支持Term/Fuzzy/Regex/Phrase Query等各种针对文本检索的DSL语法，然后翻译成对应的SQL语句。在Trino层面，主要是支持几种基本类型的String匹配表达式的下推使用，包括=/like/regex_like/starts_with/has_token等，以及他们通过AND/OR组装的复杂表达式，其中has_token是新增的UDF，用户可以使用该UDF以关键词作为输入参数直接检索，关键词会被当作切词后的Term直接使用索引匹配查找。虽然PostingList中DocID列表的存储可能会采用int数组或者BitMap，但是索引匹配过滤条件后统一返回BitMap，使用复杂过滤表达式时，也是把表达式中的AND/OR关系转化为BitMap的交并操作，最大可能地精确匹配命中的DocID列表。

对于Phrase Query，实际上TokenBitMap索引并没有提供完全的支持，因为Phrase Query除Term外，还需要匹配多个Term之间在文本中出现的位置顺序，而TokenBitMap索引并不保存行内位置数据，实际上目前只是将此转化为多个Term用AND串联的has_token查询，这么做可能会比用户预期返回更多的数据。考虑到将 Term在每行文本字段中的位置顺序信息需要额外较大的存储空间，而Phrase Query中每个Term都出现但是顺序不满足要求，这种情况实际出现的概率不高，且用户可以通过增加更多的过滤条件减少这种可能，所以TokenBitMap索引未支持位置顺序的匹配。

性能测试

Lucene vs TokenBitMap
我们使用一个实际业务的日志文件分别创建Lucene索引和TokenBitMap索引进行了比较，它们的大小分别如下，其中TokenBitMap索引字典文件6M，PostingList文件14.8M，相比于Lucene索引，TokenBitMap索引只有 1/6的大小。

数据文件 Lucene索引 TokenBitMap索引
96M 122M 20.8M

E2E测试

我们基于某个业务实际一天的日志数据进行了性能测试，数据量共330GB，构建了TokenBloomFilter索引和TokenBitMap索引，其中TokenBloomFilter索引大小为2.1GB，TokenBitMap索引大小为76.6GB，分别针对低频/中频/高频的单个Term检索进行了测试，测试的结果如下：

Test1: 低词频场景（词频=25）

索引使用状况 查询执行时间 CPU时间 读取split数量 读取Row数量 读取数据量
No Index 38.38 2.53h 4488 76.3亿 163G
BloomFilter Index 8.56 6.21m 241 4.08亿 8.65G
BitMap Index 3.43 55.6s 3 3万 13.6M
在低词频场景下，可以看到在默认0.05FPP的配置下，使用TokenBloomFilter索引跳过了94.6%的split，只实际读取了5.4%的数据。使用TokenBitMap索引由于不存在FPP的情况，且支持数据文件内部细粒度的数据过滤，只需要实际读取4个split中的3万行数据，查询响应时间有10倍以上的提升，CPU时间和读取数据量两个指标分别代表查询对于CPU和磁盘IO这两个关键机器资源的消耗，相比于查询时间的减少，它们其实有更大程度的提升。

Test2: 中词频场景（词频=2813）

索引使用状况 查询执行时间 CPU时间 读取split数量 读取Row数量 读取数据量
No Index 38.50 2.53h 4488 76.3亿 163G
BloomFilter Index 7.71 16.94m 519 8.9亿 18.9G
BitMap Index 3.89 1.9m 315 340万 1.56G
在中词频的场景中，TokenBloomFilter索引和TokenBitMap索引虽然读取split数量更加接近了，但是因为TokenBitMap索引支持返回DocID列表，可以进行数据文件内部细粒度的数据过滤，读取Row数量还是减少了200多倍，CPU消耗也减少了10倍左右。

Test3: 高词频场景（词频=127204438）

索引使用状况 查询执行时间 CPU时间 读取split数量 读取Row数量 读取数据量
No Index 37.86 2.61h 4488 76.3亿 163G
BloomFilter Index 38.27 2.76h 4488 76.3亿 163G
BitMap Index 39.79 2.53h 4488 76.3亿 163G
在高词频的场景下，TokenBloomFilter索引和TokenBitMap索引都没有任何实际的Data Skip效果，读取的数据量都是一样的，但是总体的查询响应时间和CPU时间与没有使用索引基本一致，说明对于TokenBloomFilter索引和TokenBitMap索引额外的访问消耗，对于整体查询响应影响不大，基本没有性能回退的情况。

总结

本文主要讨论了在湖仓一体的架构下，针对于日志文本检索场景，如何有针对性的设计实现轻量级的文本索引，用于支持低成本高效的日志文本检索需求。在业务实践中 ，我们主要采用这套方案支持历史日志数据的检索和分析场景，目标是在可接受的查询响应体验的基础上，尽量降低日志存储和计算的成本，过程中最主要的经验是文本索引的大小是同时影响性能和成本的关键，这也是整篇文章的核心关注点，希望能够对探索这个方向的同学能有所裨益。

参考
https://en.wikipedia.org/wiki/Finite-state_transducer
https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/
https://docs.pinot.apache.org/b