我如何增强 Loki 支持 PB 级日志查询
本文介绍了我在面对 Loki 查询大规模日志上的挑战，研发迭代 BBF 索引的思考过程及实践落地经验
背景
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
第一阶段：基于 redis 的布隆过滤器索引
在思考怎么加速 tid 这种高基数字段查询时，最容易想到的思路是减少不必要的数据检索量，但是我们不能用倒排索引，因为这样会回到旧系统的思路上，Loki 的优势也会消失。
要做到比倒排索引更轻量，我很容易想到了布隆过滤器，因此 2022 年下半年我增强了 Loki 的写入和查询链路，使用 redis bloom-filter 来加速查询。核心思路是对每十分钟的时间片创建一个布隆过滤器，将这段时间需要索引的字段值写入。查询时根据关键字过滤时间片来缩小搜索范围。
布隆过滤器是个概率数据结构，它有一定的误判率，当它返回存在时有可能不存在，但返回结果不存在则一定不存在，因此可以用它先过滤掉一部分不包含查询关键字的数据。
1. 写入链路
写入链路的改造包括几个部分：
1）扩展 Loki 写入数据协议，从日志内容中提取出相关的字段放在 attachment 中写入 Loki；
2）改造 Loki 写入链路，将 attachment 字段按 bloom-filter 分组后批量写入过滤器；
我们按每个应用每 10 分钟创建一个过滤器，过滤器名字格式为：${tenantId}_${app}_202503041910
2. 查询链路
查询时，根据字段和时间先从布隆过滤器查找，过滤掉不包含对应 value 的时间片，以此减小搜索的时间范围：
比如：如果取子查询的结束时间点按 10 分钟取整得到“202503041910”，用查询条件中的关键字去名为 “${tenant}_${app}_202503041910” 的 bloom-filter 中过滤，如果关键字在该过滤器中不存在，那么这个子查询就不需要执行，如果返回存在，则拉取日志文件数据进行搜索。
3. 容错设计
1）写入链路在加入 attachment 出现异常时，向 redis 中设置 bloom-filter 分片为脏数据的标识，比如：Dirty_myapp_2769901；
2）查询时如果发现有该标识则降级为全文查找；
在这个版本上线后，我们随后又进行了一个版本迭代，将时间片粒度的过滤器优化为文件 id 粒度。写入时仍然按时间片创建 bloom-filter，然后在写入字段值时在每个值后面拼接上所在日志文件的 id（Loki 中叫 chunkId），即最终写入的 key 是:
查询时也同样拼接 chunkId 去过滤，这样我们的索引过滤的对象从时间片变成了 chunkId，最终过滤后的数据量更小，可能只有几个 chunk 文件。
4. 成果
第一阶段优化后从 20TB 日志中查询 tid 的耗时从原来的几分钟降低到了 3s 内，搜索的数据量降到了几百 MB。
第二阶段：基于 SSD 的布隆过滤器索引
前面实现的 redis 布隆过滤器索引在查询性能上已经能接近全文索引，满足常见查询场景。但带来的问题是 redis 成本很高，如果要给更多字段建索引则会因资源成本问题变得不切实际。
于是我想能不能将布隆过滤器存储在磁盘中？在查找资料的过程中我从一篇论文[1]中找到灵感，因此考虑结合该论文和我们的场景设计一种基于 SSD 的布隆过滤器索引，称之为 BBF 1.0。
1. 核心原理
SSD 相比内存，I/O 速度上差了一到两个数量级。但布隆过滤器写入和查询的 key 都是明确的，不存在前缀后缀读写情况，我们可以将布隆过滤器在存储上设计成多个分片分别存储：
写入时：通过一个 hash 函数将需写入的 key 映射到其中的一个分片上写入，分片在内存中缓冲，定期刷盘写到 SSD 中；
查询时：通过 hash 计算定位到 key 所在的具体分片，然后从 SSD 读取对应的这个分片即可；
这种分片机制可以有效减少查询时从 SSD 读取的数据量，同时采取批量写入和读取数据短暂缓存的方法，使用户最终对延时增加无感知。
写入流程
当日志块刷存储时，批量写入其中的所有索引字段值到对应的布隆过滤器中；
写入布隆过滤器时先根据字段值 hash 定位到过滤器的某个分片，然后写入该分片中；
查询流程
查询时先根据关键字的 hash 值定位到分片，只从 SSD 加载该分片到内存；
判断时将关键字和每个 chunkId 进行拼接后去过滤器分片中过滤，以确定这个 chunk 是否可能包含关键字，如果不包含那么这个 chunk 文件就不需要查询；
2. 存储结构
结构：每个过滤器由一个 meta 和多个“子过滤器”组成；
存储：meta 在内存缓存，用来记录 shard 数量等元信息，子过滤器存在 SSD 文件中，里面就是布隆过滤器的位数组；
写入：写入时过滤器的第一个 hash 函数用来将 field value 映射到某一个“子过滤器”上；
查询：先 field value 处于哪个“子过滤器”上，然后从 SSD 中加载这个“子过滤器”进行过滤即可；
过滤器扩容
如果布隆过滤器写入过多的 key 时会导致它的误判率上升，因此当写入值数量计数超过预设值时需要扩容，扩容通过创建新的子过滤器并添加后缀实现。
比如：如果 filter name 为 “202308090110_fake_tid_myapp”，key hash 计算 shard 分片值为 1，当写入字符串数量超过预设容量时，新创建同样大小的 filter，创建后该 key 对应的子过滤器文件列表如下：
文件目录结构
默认情况下以 filter name 作为存储文件名，以 "default" 作为目录名；当用户传入了 prefix 时，用 prefix 作为目录名。目录树如下所示：
3. 数据写入与落盘
数据写入时先在内存中构建布隆过滤器，一段时间后写入 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 时间跨度内被多次追加写入；
4. 性能分析
以某个数据中心查询 tid 为例，每天的枚举数量大约 44 亿，在容错率设置为 0.001 时过滤器大小约为 7.5GB[3]，假设 shard 取 100，Buffer 后每个 SSD I/O 处理 10 个查询请求，这时需要读取的 SSD 文件大小为：
SSD 读取速度按 250MB/s 计算，一次查询需要： 30ms。当然我们可以增大分片数量来进一步减少每次加载的数据量。
另外还有集群管理和容错设计就不详细展开，做法大同小异。
5. 成果
BBF 1.0 索引落地后，我们用同等成本支持了比原来大 50 倍的索引容量，用户体验到的查询延迟和 redis 相比无差别。
第三阶段：基于 S3 的布隆过滤器索引
前面设计的 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 中，势必会有大量的跨区流量，一些云服务厂商会对跨区流量收取高昂的费用；
另外为了满足集群高性能与可扩展的要求，我们还有两个问题要考虑：
分词计算任务协调：多个节点按什么规则划分对日志内容的分词计算任务；
索引的分片管理协调：节点间如何分工协作管理所有分片，根本问题是如何决定谁负责哪些分片的写入缓冲；
社区方案
巧合的是这个时候 Loki 团队也在基于布隆过滤器开发他们的索引，我们先来看看 Loki 团队的方案：
如上图所示，Loki 增加了 Bloom compactor 节点，多个 compactor 节点按 stream 分段协调任务分配，每个节点负责一段 stream 中日志的索引，索引构建中会生成一系列的 Blocks 存储在 SSD 上。
stream 是多个标签的唯一组合，Loki 按 stream 组织日志写入，比如共有 3 个标签，他们的值有 100 种组合就会有 100 个 stream
可以看出，社区版本只对数据处理任务进行了并行处理，数据存储上是简单的累积，并没有在减少查询加载数据量方面做优化，因此查询时需要挂载非常多 SSD 盘来提高吞吐能力，数据达到一定程度就会因为成本问题无法扩展。
社区的不足
社区这个方案在试用一段时间后发现规模难以扩展，于是将原来的全文 Ngram 分词方式改成了抽取部分高基数字段放到 structured metadata 中然后进行分词索引，细心的读者有没有发现，社区修改后的方案和我们阶段二的非常像。
这种方案的不足细分起来可以罗列如下：
资源消耗高：Loki 文档描述索引构建过程大约每核每秒能处理 4MB 数据，对一个每秒 1GB 的集群，最少需要 256 核，考虑高峰期会更高；
索引延时大：根据 Streams 来循环构建的缺点是 Streams 量可能非常大，新日志索引构建的延迟等于一轮 Streams 处理完成的时间；
查询性能差：因为没有做数据存储结构的优化，每次查询可能要加载所有 bloom 数据，因此只能做部分字段级别的索引；
我们的方案
2024 年上半年我在测试社区方案的基础上对它进行了存储结构改造，将生成的 Block 进行了类似我们阶段二的 Hash 分片式存储以优化查询速度，经过半年改造后实测查询速度是没问题的，但是在合理成本的资源条件下索引写入速度很慢，每轮延时达到 1 小时以上。于是放弃社区方案回到自己的设计上来。
架构
Ingester 在将日志块文件刷存储时，同时将 chunkId 发送到 BBF Computer 节点，这部分会有跨区流量，但是因为只发送文件 id，跨区流量比较小；
BBF Computer 节点：BBF Computer 节点主要负责分词计算任务，接收到 chunkId 后，从 S3 重新拉取日志文件进行分词计算，然后将分词后的 key 发送到对应的 BBF Index 节点，发送规则是先根据 key hash 映射到某个分片，然后根据分片 hash 映射到某个 BBF Index 节点；
BBF Index 节点：BBF Index 节点负责 bloom 索引分片的缓冲和存储，每个节点负责哪些分片是通过 Consul 集群发现后 hash 计算得到的；
集群管理
集群管理主要要解决 BBF Index 集群的扩容缩容问题，因为 bloom 索引分片是在 BBF Index 内存中缓冲的，如果集群扩容， hash 结果发生改变后可能出现一个分片现在在两个节点上都有的情况。
集群缩容后，虽然数据会写入 S3 存储，但是因为节点数量发生变化导致映射关系变化，其他节点对分片的管理还是会出现紊乱。
Sticky Ring
解决办法是在创建 BBF 所有分片后，记录当前时间 bucket 的节点列表，写到 Consul 中。集群扩容后，新节点只对下一个时间 bucket 新创建的 BBF 生效。
集群缩容时，先执行下线接口，此时下线的节点不会接受新分片的创建，但是仍然会完成当前负责分片的写入，直到超出最大时间窗口不会再有该 bucket 的数据写入方可下线服务。
内存控制与稳定性
我们的索引在时间维度上是按时间 bucket 拆分的，比如：每 10 分钟一个 BBF。理想情况下正在写入的索引应该聚集在最近一到两个 bucket 上，但是实际情况可能会出现写入堆积，或者 Ingester 刷盘数据出现下面的乱序情况：
这可能导致内存中 bucket 数量增长得很大，特别在写入出现堆积后重新恢复时，可能不得不成倍扩容索引节点资源才能追上正常写入。
分布式 window 机制
要控制 BBF bucket 长度很容易想到用 window 机制，但在实现了本地 window 后，线上试运行发现出现了不同节点 window 元素不一样的情况，导致写入速度严重下降。
因此将方案升级为基于 Consul 的分布式 window，consul 中存储的 key 结构如下：
扩展 window 时，每个 BBF Index 节点都会在 /window 下面创建包含节点主机名的 bucket key。
缩小 window 时，当某个节点缩小 window 时，只删除该节点对应的 bucket key，当 bucket 下所有节点都删除掉时才认为该 bucket 在所有节点都已写入完成，此时才会删除该 bucket。如下图所示：
在 bucket 长度失控与多节点 window 不一致问题都得到解决后，又发现在写入堆积后一些较早的分片一直抢占不到 window 空间，出现了饥饿现象。于是我又在 window 基础上增加了候选队列，候选队列每次变更时进行排序，当 window 有空闲空间时，将候选队列中最小的 bucket 元素取出加入 window，解决排队等待饥饿问题。
整流
虽然有了完善的 window 和 candidate 机制，但是当写入 bucket 出现严重乱序时，因为每个 bucket 在内存中是有最小 buffer 时间的，因此当 window 满了以后只能等待旧的 BBF 刷盘。为了提高堆积时的写入速度避免卡在等待 window 空间上，我额外对写入的 chunkId 进行了整流。
具体做法是批量读取一批 chunkId，然后按 bucket 分组排序，再按 bucket 顺序逐个批次写入，这样显著提高了堆积时可能受 window 容量影响的写入速度。
小结
这个方案的设计中：
让 Ingester 只发送 chunkId 给 Bloom Computer 节点减少了跨区流量；
通过 Computer 节点重新拉取 chunk 进行计算解决了 Ingester 内存问题（S3 Get 很便宜）；
将计算型的 BBF Computer 和内存型的 BBF Index 节点分离的设计使查询尽量少的受到写入的影响；
同时解决了“分词计算任务”与“索引写入任务”的分配协调，并延续了阶段二中通过存储设计的优化来减少查询数据量方案的优点；
引入 sticky ring 解决集群管理问题；
引入分布式 window 机制优化索引写入的内存控制；
使用整流策略提高索引堆积后恢复时的写入速度；
成果
这个方案上线后，实现了用社区版本 1/5 的资源支持了全文分词 bloom 索引，索引容量比阶段二提升了 30 倍。写入延时从社区版的大约 1 小时降低到秒级。查询需要加载的数据量是社区的几千分之一，耗时与方案二基本一致:
400 核查询器 + 32GB 索引节点：从 20TB 数据中查询不同频率的数据 P95 耗时约 3 秒，查询 7 天共 140TB 数据 P95 耗时约 12 秒；
200 核查询器 + 32GB 索引节点：查询低频关键字耗时与 400 核相当，查询高频与中频关键字时耗时大约增长一倍。表面后续通过优化高频关键字索引判断过程可进一步优化性能；
总结展望
经过 3 年三个大版本的迭代，我们实现了全文分词的轻量级 Bloom 索引，解决了 Loki 在大规模日志量下的查询性能问题。我们的方案与社区方案在部分思路上不谋而合，但在设计上又走出了不同的路径。
从上面结果可以看出瓶颈其实在索引节点中，适当增加资源可以进一步提升查询性能。性能部分还可以做的优化可能包括：
向量化计算提高索引节点判断速度;
高频词自动降级优化;
支持可配置的多粒度 Bloom 索引，比如：时间片和 chunkId;
[1] Loki Cloud 为了满足云服务大客户的查询性能要求，就运维了一个高达 50TB 的 Memcached 缓存集群，https://grafana.com/blog/2023/08/23/how-we-scaled-grafana-cloud-logs-memcached-cluster-to-50tb-and-improved-reliability/
[2] 《Buffered Bloom Filters on Solid State Storage》，https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=da6a07944d97723d6c154d76609b5c20a3636f9a
[3] Bloom filter calculator, https://hur.st/bloomfilter/
原文同时发表于：https://mp.weixin.qq.com/s/P90vZR0oDutcP2nFykF_5w
版权声明: 本文为 InfoQ 作者【阿南】的原创文章。
原文链接:【http://xie.infoq.cn/article/990f140fba479bf1fc1800883】。文章转载请联系作者。
还未添加个人签名 2019-04-08 加入
关注可观测系统、大规模分布式系统、存储、中间件。 mail：honganan@qq.com WX：honganan_
评论