我如何增强 Loki 支持 PB 级日志查询

Loki 是 Grafana 的开源日志产品，它基于 index-free 理念设计，这种设计只对日志的元信息（标签）进行轻量级索引，而对日志内容不做任何索引直接存储。这种方案有以下优点：

• 日志写入轻量 ：因为没有对日志内容构建任何索引，日志写入速度非常快，资源使用率非常低，通常可以达到单核 25MB/s 的速度；

• 存储数据量小 ：不需要存储巨大的索引，而其他有倒排索引的系统，索引与日志的大小比例通常能达到 1:1；

成本从写入侧转到查询侧：针对日志写多读少的特点，通过比较少的资源快速写入日志，然后部署庞大的查询集群，利用对象存储的大吞吐能力（可达几十 GB/s），进行暴力下载和搜索；

Loki 的数据是按标签组织存储的，同一组相同标签值的日志存在同一组文件中，输入应用标签就会排除掉其他应用的数据。因此在日志总量大但每个应用日志量比较均衡时，Loki 非常省成本，能达到 ES 的 20%。

但是如果有某个应用日志量达到 TB 级时，Loki 对这种长板应用的查询会变得很吃力 [1]，特别对“大海捞针”式的查询，比如从几十 TB 日志中搜索一条 tid 或 requestId。而传统有倒排索引的系统处理这种查询耗时通常都小于 1s。

社区也有不少人提出类似问题，Loki 团队一直在思考好的解决方案，但我们在 2022 年上线了 Loki 后就开始迫切需要解决这个问题。

为此我们经过了几个阶段的探索，可以简单概括如下：

第一阶段 ：提取 tid 等高基数字段写入 redis 布隆过滤器

第二阶段 ：研发基于 SSD 存储的 bloom 索引 BBF 1.0 ，写入更多常用查询字段

第三阶段 ：设计研发基于 S3 的大规模全文分词 bloom 索引 BBF 2.0

在思考怎么加速 tid 这种高基数字段查询时，最容易想到的思路是减少不必要的数据检索量，但是我们不能用倒排索引，因为这样会回到旧系统的思路上，Loki 的优势也会消失。

要做到比倒排索引更轻量，我很容易想到了布隆过滤器，因此 2022 年下半年我增强了 Loki 的写入和查询链路，使用 redis bloom-filter 来加速查询。核心思路是对每十分钟的时间片创建一个布隆过滤器，将这段时间需要索引的字段值写入。查询时根据关键字过滤时间片来缩小搜索范围。

布隆过滤器是个概率数据结构，它有一定的误判率，当它返回存在时有可能不存在，但返回结果不存在则一定不存在，因此可以用它先过滤掉一部分不包含查询关键字的数据。

写入链路的改造包括几个部分：

1）扩展 Loki 写入数据协议，从日志内容中提取出相关的字段放在 attachment 中写入 Loki；

2）改造 Loki 写入链路，将 attachment 字段按 bloom-filter 分组后批量写入过滤器；

我们按每个应用每 10 分钟创建一个过滤器，过滤器名字格式为：${tenantId}_${app}_202503041910

查询时，根据字段和时间先从布隆过滤器查找，过滤掉不包含对应 value 的时间片，以此减小搜索的时间范围：

比如：如果取子查询的结束时间点按 10 分钟取整得到“202503041910”，用查询条件中的关键字去名为 “${tenant}_${app}_202503041910” 的 bloom-filter 中过滤，如果关键字在该过滤器中不存在，那么这个子查询就不需要执行，如果返回存在，则拉取日志文件数据进行搜索。

1）写入链路在加入 attachment 出现异常时，向 redis 中设置 bloom-filter 分片为脏数据的标识，比如：Dirty_myapp_2769901；

2）查询时如果发现有该标识则降级为全文查找；



在这个版本上线后，我们随后又进行了一个版本迭代，将时间片粒度的过滤器优化为文件 id 粒度。写入时仍然按时间片创建 bloom-filter，然后在写入字段值时在每个值后面拼接上所在日志文件的 id（Loki 中叫 chunkId），即最终写入的 key 是:

key + "_" + chunkId

key + "_" + chunkId查询时也同样拼接 chunkId 去过滤，这样我们的索引过滤的对象从时间片变成了 chunkId，最终过滤后的数据量更小，可能只有几个 chunk 文件。

第一阶段优化后从 20TB 日志中查询 tid 的耗时从原来的几分钟降低到了 3s 内，搜索的数据量降到了几百 MB。

前面实现的 redis 布隆过滤器索引在查询性能上已经能接近全文索引，满足常见查询场景。但带来的问题是 redis 成本很高，如果要给更多字段建索引则会因资源成本问题变得不切实际。

于是我想能不能将布隆过滤器存储在磁盘中？在查找资料的过程中我从一篇论文 [1] 中找到灵感，因此考虑结合该论文和我们的场景设计一种基于 SSD 的布隆过滤器索引，称之为 BBF 1.0。

SSD 相比内存，I/O 速度上差了一到两个数量级。但布隆过滤器写入和查询的 key 都是明确的，不存在前缀后缀读写情况，我们可以将布隆过滤器在存储上设计成多个分片分别存储：

• 写入时 ：通过一个 hash 函数将需写入的 key 映射到其中的一个分片上写入，分片在内存中缓冲，定期刷盘写到 SSD 中；

• 查询时 ：通过 hash 计算定位到 key 所在的具体分片，然后从 SSD 读取对应的这个分片即可；

这种分片机制可以有效减少查询时从 SSD 读取的数据量，同时采取批量写入和读取数据短暂缓存的方法，使用户最终对延时增加无感知。

• 当日志块刷存储时，批量写入其中的所有索引字段值到对应的布隆过滤器中；

• 写入布隆过滤器时先根据字段值 hash 定位到过滤器的某个分片，然后写入该分片中；

• 查询时先根据关键字的 hash 值定位到分片，只从 SSD 加载该分片到内存；

• 判断时将关键字和每个 chunkId 进行拼接后去过滤器分片中过滤，以确定这个 chunk 是否可能包含关键字，如果不包含那么这个 chunk 文件就不需要查询；

• 结构 ：每个过滤器由一个 meta 和多个“子过滤器”组成；

• 存储 ：meta 在内存缓存，用来记录 shard 数量等元信息，子过滤器存在 SSD 文件中，里面就是布隆过滤器的位数组；

• 写入 ：写入时过滤器的第一个 hash 函数用来将 field value 映射到某一个“子过滤器”上；

• 查询 ：先 field value 处于哪个“子过滤器”上，然后从 SSD 中加载这个“子过滤器”进行过滤即可；

如果布隆过滤器写入过多的 key 时会导致它的误判率上升，因此当写入值数量计数超过预设值时需要扩容，扩容通过创建新的子过滤器并添加后缀实现。

比如：如果 filter name 为 “202308090110_fake_tid_myapp”，key hash 计算 shard 分片值为 1，当写入字符串数量超过预设容量时，新创建同样大小的 filter，创建后该 key 对应的子过滤器文件列表如下：

202308090110_fake_tid_myapp_s1202308090110_fake_tid_myapp_s1_1

默认情况下以 filter name 作为存储文件名，以 "default" 作为目录名；当用户传入了 prefix 时，用 prefix 作为目录名。目录树如下所示：

// prefix 使用每 10 分钟的时间 bucket（202308111210）时./202308111210  202308111210_fake_tid_myapp_meta.json  202308111210_fake_tid_myapp_s0  202308111210_fake_tid_myapp_s0_1  202308111210_fake_tid_myapp_s1  202308111210_fake_tid_myapp_s1_1  ...  202308111210_fake_tid_myapp_s3000  202308111210_fake_tid_myapp_s3000_1

数据写入时先在内存中构建布隆过滤器，一段时间后写入 SSD，随后在有新数据需要继续写入时先在内存缓存数据，然后定期更新写入，相关动作的时间关系如下图所示：

• t0-t1 ：这里的 BBF 是按每 10 分钟的粒度创建的，即 t0-t1 这段时间所有数据写入同一个 BBF 索引（BBF 索引中有很多分片）；

• t2 ：在每个 BBF 所属的 10 分钟窗口期过后的一段时间（flush_delay），将 BBF flush 至 SSD 上；

• t3 ：如果在 BBF 刷盘后又有新数据请求写入，则将新数据在内存中缓冲一段时间（append_period）后重新加载 BBF 进行批量追加写入，防止反复加载和刷盘；

• max_chunk_age ：这是日志在 Loki Ingester 中缓存的最大时长，超过这个时间的日志块将会立即刷盘，因此 BBF 索引在最差的情况下会在 max_chunk_age 时间跨度内被多次追加写入；

以某个数据中心查询 tid 为例，每天的枚举数量大约 44 亿，在容错率设置为 0.001 时过滤器大小约为 7.5GB[3]，假设 shard 取 100，Buffer 后每个 SSD I/O 处理 10 个查询请求，这时需要读取的 SSD 文件大小为：

7.5GB / 100 / 10 = 7.5MB

SSD 读取速度按 250MB/s 计算，一次查询需要：30ms。当然我们可以增大分片数量来进一步减少每次加载的数据量。

另外还有集群管理和容错设计就不详细展开，做法大同小异。

BBF 1.0 索引落地后，我们用同等成本支持了比原来大 50 倍的索引容量，用户体验到的查询延迟和 redis 相比无差别。

前面设计的 BBF 1.0 虽然支持了更多字段写入，但如果要扩展到全文分词 bloom 索引这种更大规模场景仍然存在问题：

• SSD 带宽限制 ：全文分词场景下 bloom 索引大小大约是原始日志的 3%，即 20TB 日志对应 600GB 的布隆过滤器。假设分片数取 3000，一个查询分词后有 10 个 key，那么一次查询需要从 SSD 加载的数据量是 600GB / 3000  10 ≈ 18GB，带宽 250MB 的 SSD 读取耗时为 18 * 1024/250 = 72 秒。

• Ingster 内存问题 ：1.0 版本在日志写入 Loki 时就把抽取出的相关字段暂存在 Ingester 组件内存中，直到日志块刷存储时才写入索引（因为直到刷存储时才能确定日志块的 chunkId），在全文分词场景中，要把所有分词后的 key 在内存中缓存显然太昂贵；

• 跨可用区流量问题 ：因为我们的写入链路是多可用区隔离部署的，如果要将一个日志块中内容的所有分词写入不同 BBF 节点负责的不同 shard 中，势必会有大量的跨区流量，一些云服务厂商会对跨区流量收取高昂的费用；

另外为了满足集群高性能与可扩展的要求，我们还有两个问题要考虑：

• 分词计算任务协调 ：多个节点按什么规则划分对日志内容的分词计算任务；

• 索引的分片管理协调 ：节点间如何分工协作管理所有分片，根本问题是如何决定谁负责哪些分片的写入缓冲；