移除排序限制
作者：Owen Diehl - owen-d ( Grafana Labs)
日期：28/01/2021
问题
Loki 对摄入数据强制执行排序约束；也就是说，按流分区传入的数据必须具有单调递增的时间戳。这继承了我们父项目 Cortex 的历史惯性，但给日志摄入带来了一些意想不到的后果。与指标抓取相比，Loki 在一些合理用例中，排序约束带来了问题，包括
- 从云函数摄入日志时，无需为避免乱序错误而被迫添加 invocation_id 等高基数标签。
- 摄入来自其他未考虑 Loki 排序约束的代理/机制的日志。例如，fluent{d,bit} 变体可能会独立于其他批次进行批处理和重试写入，从而导致通过乱序错误而发生不可预测的日志丢失。
其中许多示例说明了 *排序* 与 *基数* 之间的冲突。除了支持一些以前困难/不可能的用例外，移除排序约束还能让我们避免这两个概念之间的潜在冲突，并有助于鼓励以减少有用标签形式的良好实践。
要求
- 启用乱序写入
- 保持查询接口对等
额外的好处
- 优化有序写入
替代方案
- 实现与顺序无关的块 + 按压缩率增加内存使用：由于 TCO（总拥有成本）原因，被认为不可接受。
- 实现与顺序无关的块 + 横向扩展（减少每个 ingester 的流）：由于 TCO 和增加的 ring 压力，被认为不可接受。
- 实现与顺序无关的块 + 更频繁地刷新块：由于负面地增加了索引和读取时需要合并的块数量，被认为不可接受。
设计
背景
我建议允许流的 head block 接受乱序写入，然后在将它们刷新到存储之前，将切出的块类似于归并排序进行重新排序。当前，写入以单调递增的时间戳顺序被接受到 *headBlock* 中，该 *headBlock* 会偶尔被“切出”并压缩成不可变的 *block*。接着，这些 *block* 被组合成一个 *chunk* 并持久化到存储。
Figure 1
Data while being buffered in Ingester | Chunk in storage
|
Blocks Head | ---------------------------------------------------------------------
| | ts0 ts1 ts2 ts3 ts4 ts5 ts6 ts7 ts8 ts9 |
-------------- ---------------- | | --------- --------- --------- --------- --------- |
| blocks |-- | head block | | | |block 0| |block 1| |block 2| |block 4| |block 5| |
|(compressed)| | |(uncompressed)| | | | | | | | | | | | | |
| | | ------> | | | | --------- --------- --------- --------- --------- |
| | | | | | | |
-------------- | ---------------- | ---------------------------------------------------------------------
| | |
-------------- |历史上，由于 Loki 的排序约束，这些块保持单调递增的时间戳（缩写为 `ts`）顺序，其中
Figure 2
start end
ts0 ts1 ts2 ts3
-------------- --------------
| | | |
| | --------> | |
| | | |
| | | |
-------------- --------------这使我们能够进行两项优化
- 我们可以将更多数据存储在内存中，因为每个块在从 head block 切出后都被压缩了。
- 我们可以查询块的元数据，例如 `ts0` 和 `ts1`，并在时间戳超出请求边界的情况下跳过查询它。
乱序 Head Blocks
head block 的内部结构将被树结构取代，从而实现对数级别的插入/查找和 `n log(n)` 的扫描。从 head block *切出*一个块将遍历这棵树，创建一个与当前使用的块相同的排序块。然而，由于我们将接受任意顺序的写入，块间将不再有任何保证的顺序。与图 2 不同，块可能包含重叠数据
Figure 3
start end
ts1 ts3 ts0 ts2
-------------- --------------
| | | |
| | --------> | |
| | | |
| | | |
-------------- --------------因此，*所有*块的元数据都必须根据查询进行检查。在此示例中，查询边界 `[ts1,ts2]` 需要解压缩并扫描这两个块中的 `[ts1, ts2]` 范围，但查询 `[ts3, ts4]` 只需解压缩并扫描*一个*块。
Figure 4
chunk1
-------------------
chunk2
---------------------
query range requiring both
----------
query range requiring chunk2 only
-----------
ts0 ts1 ts2 ts3 ts4 (not in any block)
------------------------------
| | | |
| | | |
| | | |
| | | |
------------------------------相较于当前方法，性能损失包括
- 追加日志行现在在对数时间内执行，而不是分摊（由于数组大小调整）的常数时间。
- 块可能包含重叠数据（尽管每个块内部仍然保证有序）。
- Head block 扫描现在是 `O(n log(n))`，而不是 `O(n)`
刷新和 Chunk 创建
Loki 定期将多个块组合成一个 chunk 并将其“刷新”到存储。为了确保对已刷新 chunk 的读取尽可能保持高性能，我们将把可能重叠的块集合重新排序成一个保持块间单调递增顺序的块集合。从 Loki 其他组件（从存储中获取 chunk 的查询器/rules）的角度来看，没有任何变化。
注意
如果流的数据是有序摄入的，这实际上是一个空操作，从而很好地优化了有序写入（这既是当前 Loki 的要求，也是默认行为）。因此，这对有序数据性能影响很小，同时使 Loki 能够摄入无序数据。
Chunk 持续时间
当 `--validation.reject-old-samples` 启用时，Loki 接受范围内传入的时间戳
[now() - `--validation.reject-old-samples.max-age`, now() + `--validation.create-grace-period`]对于我们的大多数集群，这意味着可接受的数据范围长达一周。相比之下，我们的最大 chunk 生命周期是 `2h`。允许乱序写入将意味着 ingesters 愿意接收长达 168 小时的数据，或多达 84 个不同的 chunk 长度。这带来了一个问题：恶意用户可以同时向许多（本例中为 84 个）不同的 chunk 写入数据，从而用未充分利用的 chunk 淹没 Loki，导致索引膨胀。
为了缓解这个问题，有几种方案（不相互排斥）
- 降低有效接受范围
- 创建一个*活跃的*有效性窗口，例如 `[most_recent_sample-max_chunk_age, now() + creation_grace_period]`。
第一种方案简单易行，已经可用，并且可能在某种程度上是合理的。第二种方案易于实现，是确保 Loki 能够摄入无序日志但保持滑动有效性窗口的有效方法。我预计这将涵盖几乎所有合理的用例，并有效缓解恶意行为。
Chunk 同步
我们还根据 `sync_period` 切割 chunk。摄入的第一个超过此边界的时间戳将触发切割。此过程有助于提高 chunk 的确定性，从而提高我们在对象存储中的重复数据删除率，因为 chunk 是内容寻址的。随着我们移除排序约束，在某些情况下同步方法可能效果不佳，例如在并发写入同一流并跨越此边界时。
注意
重要的是要提到，在当前排序约束下，这种情况今天也可能发生，但通过移除排序约束，我们将增加发生的可能性。
Figure 5
Concurrent Writes over threshold
^ ^
| |
| |
-----------------|-----------------
|
v
Sync Marker为了缓解这个问题并保留 chunk 重复数据删除的好处，我们需要使 chunk 同步在并发写入期间更不易受到非确定性影响。为此，我们可以将同步触发器从 `Append` 代码路径移动到异步的 `FlushLoop`。注意，chunk *何时*被切割的语义不会改变：也就是说，当第一个时间戳跨越同步边界时。然而，在刷新路径上为同步而 *切割* chunk 减少了 *不同* chunk 被切割的可能性。为了切割具有不同哈希的多个 chunk，追加操作需要在 flush loop 检查流的同时跨越此边界，这种情况应该非常不可能发生。
未来机会
本文的初步设计部分到此结束。下面，我将描述一些我们将来可能解决的变更，如果它们被证实有必要的话。
方差预算
为每个流设置“滑动有效性”窗口的预期方法简单有效，可防止滥用和恶意行为者在传入时间戳的整个可接受范围内进行写入。然而，未来我们可能希望采用更复杂的方法，引入每个租户的“方差”预算，这可能源自流限制。例如，此 ingester 限制可以使用增量（在线）标准差/方差算法，例如 Welford 算法，这将允许写入比Chunk 持续时间部分中的方案 (2) 更大的范围。
LSM 树
所提出的方法大部分类似于LSM 树（日志结构合并树），尽管是在内存中而不是使用磁盘。这是一个奇怪的选择——LSM 树旨在有效利用磁盘，那么为什么不走这条路呢？目前我们不希望在可避免的情况下向 Loki 添加额外的磁盘依赖，但下面我将概述 LSM 树方法是什么样的。最终，使用磁盘将能够在 ingester 刷新前缓冲更多数据，
使我们能够
- 刷新更高效利用的 chunk（在某些情况下）
- 为传入日志保持更宽的有效性窗口
以…为代价
- 易受磁盘相关复杂性和问题的影响
MemTable (head block)
在 LSM 树中，写入首先被接受到一个称为 memtable（通常是平衡树，例如红黑树）的内存结构中，直到 memtable 达到预配置的大小。在 Loki 中，这对应于流的 head block，它是未压缩的。
SSTables (blocks)
在 LSM 树中，一旦 Memtable (head block) 达到预定义的大小，它就会作为不可变的排序结构刷新到磁盘，称为 SSTable (sorted strings table)。在 Loki 中，我们可以使用预先存在的 MemChunk 格式（它有序、紧凑且包含块索引），或直接使用预先存在的 block 格式。这些存储在磁盘上以减轻内存压力，并在需要时加载进行查询。
块索引
LSM 树中的传入读取除了当前活跃的 memtable (head block) 外，可能还需要访问 SSTable 条目。为了改进这一点，我们可以在内存中缓存 SSTable (block || MemChunk) 中的元数据，包括块偏移量、开始和结束时间戳，以减少查找、寻道和从磁盘加载不必要的数据。
合并 (刷新)
LSM 树中的合并操作组合并重新排序多个 SSTable (blocks || MemChunks)。这主要在内存方法中的刷新部分有所涵盖，但对于我们的用例来说，合并等同于刷新。也就是说，使用类似于归并排序的算法，将磁盘上的多个 SSTable 合并在一起，并以我们有序的 chunk 格式将它们刷新到存储。
