包 tsi1
tsi1 包提供了一种内存映射索引实现，支持高基数序列。
概述
tsi1 中的顶级对象是 Index。它是系统其他部分的主要访问入口。Index 由 LogFile 和 IndexFile 对象组成。
日志文件是小型的预写式日志文件，它们会按照接收顺序立即记录新的序列。文件中的数据会在内存中建立索引，以便能够快速访问。当系统重启时，这个日志文件会被重放，内存中的表示也会被重建。
索引文件也包含序列信息，不过，它们经过了高度索引，因此可以快速执行读取操作。索引文件是通过一个称为压缩的过程构建的，在这个过程中，一个日志文件或多个索引文件会被合并在一起。
操作
该索引可以执行许多与序列、测量和标签数据相关的任务。所有数据都是通过向索引中添加序列来插入的。在添加序列时，测量名称、标签键和标签值都会被分别提取并建立索引。
一旦添加了一个序列，就可以通过几种方式将其删除。首先，可以删除单个序列。其次，可以在批量操作中通过删除整个测量来删除该序列。
查询引擎需要能够以多种方式查找序列，例如按测量名称、按标签值或使用正则表达式。索引提供了一个 API，用于遍历序列的子集并执行集合操作，如并集和交集。
日志文件布局
序列最初插入的预写式文件只是按顺序追加所有新操作。它仅由一系列日志条目组成。一个条目包含一个标志，用于指定操作类型、测量名称、标签集和一个校验和。
┏━━━━━━━━━日志条目━━━━━━━━━┓
┃ ┌──────────────────────┐ ┃
┃ │ 标志 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 测量名称 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 键/值对 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 键/值对 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 键/值对 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 校验和 │ ┃
┃ └──────────────────────┘ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
当重放日志文件时，如果校验和不正确或条目不完整（由于部分写入失败），则会截断日志。
索引文件布局
索引文件由 3 种主要的块类型组成：一个序列块、一个或多个标签块以及一个测量块。在索引文件的末尾是一个尾部，用于记录这些块的偏移量等元数据。
序列块布局
序列块按排序顺序存储原始序列键。它还提供哈希索引，以便能够快速查找序列。为了在写入时限制内存大小，会定期插入哈希索引。一旦所有序列和哈希索引都已写入，就会写入一个索引条目列表，以便可以通过二分查找来查找哈希索引。
该块的末尾包含两个 HyperLogLog++ 草图，用于跟踪已创建和已删除序列的估计数量。草图之后是一个尾部，其中包含有关该块的元数据。
┏━━━━━━━序列块━━━━━━━━┓
┃ ┌──────────────────────┐ ┃
┃ │ 序列键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 序列键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 序列键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ │ ┃
┃ │ 哈希索引 │ ┃
┃ │ │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 序列键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 序列键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 序列键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ │ ┃
┃ │ 哈希索引 │ ┃
┃ │ │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 索引条目 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ HLL 草图 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 尾部 │ ┃
┃ └──────────────────────┘ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
标签块布局
在序列块之后是一个或多个标签块。索引文件中的每个测量都有一个这样的块。该块的结构是每个键的排序值列表，然后是排序的键列表。这些列表中的每一个都有自己的哈希索引，用于快速直接查找。
┏━━━━━━━━标签块━━━━━━━━━┓
┃ ┌──────────────────────┐ ┃
┃ │ 值 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 值 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 值 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ │ ┃
┃ │ 哈希索引 │ ┃
┃ │ │ ┃
┃ └──────────────────────┘ ┃
┃ ┌──────────────────────┐ ┃
┃ │ 值 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 值 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ │ ┃
┃ │ 哈希索引 │ ┃
┃ │ │ ┃
┃ └──────────────────────┘ ┃
┃ ┌──────────────────────┐ ┃
┃ │ 键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 键 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ │ ┃
┃ │ 哈希索引 │ ┃
┃ │ │ ┃
┃ └──────────────────────┘ ┃
┃ ┌──────────────────────┐ ┃
┃ │ 尾部 │ ┃
┃ └──────────────────────┘ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
每个值条目都包含一个使用该值的序列键的排序偏移量列表。可以围绕单个标签键值构建序列迭代器，或者可以使用并集或交集等集合运算符合并多个迭代器。
测量块
测量块存储一个排序的测量列表、它们关联的序列偏移量以及它们标签块的偏移量。这使得可以快速遍历一个测量的所有序列，并且可以快速直接查找测量及其标签。
这个块还包含用于新测量和已删除测量的 HyperLogLog++ 草图。
┏━━━━测量块━━━━━┓
┃ ┌──────────────────────┐ ┃
┃ │ 测量名称 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 测量名称 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 测量名称 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ │ ┃
┃ │ 哈希索引 │ ┃
┃ │ │ ┃
┃ ├──────────────────────┤ ┃
┃ │ HLL 草图 │ ┃
┃ ├──────────────────────┤ ┃
┃ │ 尾部 │ ┃
┃ └──────────────────────┘ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
清单文件
索引只是日志文件和索引文件的有序集合。这些文件可以合并在一起或重写，但它们的顺序必须始终保持不变。这是因为序列、测量和标签可以被标记为已删除（即逻辑删除），并且需要按时间顺序跟踪此操作。
每当活动文件集发生更改时，都会写入一个清单文件来跟踪该集合。清单指定文件的顺序，并且在启动时，索引目录中所有不在清单中的文件都会从索引目录中删除。
压缩索引文件
压缩是将文件合并为单个文件的过程。TSI 中有两个压缩阶段。
首先，一旦日志文件超过大小阈值，它们就会被压缩成一个索引文件。这个阈值相对较小，因为日志文件必须在堆中维护其索引，而 TSI 尽量避免这种情况。小的日志文件也可以非常快速地转换为索引文件，因此会积极进行此操作。
其次，一旦连续的一组索引文件超过某个因子（例如 10 倍），它们就会全部合并为一个索引文件，并且旧文件会被丢弃。由于所有块都是按排序顺序写入的，因此新的索引文件可以流式处理，从而最大限度地减少内存使用。
并发
索引文件是不可变的，因此它们不需要细粒度的锁，但是，压缩操作需要我们跟踪哪些文件正在使用，以免它们被过早丢弃。这是通过对文件集使用引用计数来实现的。
文件集只是一个有序的索引文件列表。当从索引中获取当前文件集时，会增加一个计数器以跟踪其使用情况。一旦用户完成对文件集的使用，就会释放它并且计数器会减少。在这个计数器归零之前，文件不能从文件系统中删除。
除了引用计数之外，在读取或写入索引文件时没有其他锁定机制。但是，每当访问日志文件时都需要加锁。这也是尽量减小日志文件大小的另一个原因。
