内存数据库

内存结构

整个内存结构更像是一个内存时序存储，主要包括如下 2 大块组成:

1. Metric Meta/Index: 主要存储了 Metric Metadata 和 Tags 的倒排索引
   • Metric Metadata: 存储该 Metric 下面对应有哪些 Field 和 哪些 Tag Keys，同时为每个 Tag Key 生成一个数据库级别的全局唯一的 ID，方便 Tag Index 在底层 KV Store 中的存储
   • Metric Index: 主要是为每个 Metric Tag Key 下面的 Tag Values 做一个倒排索引，Term 是对应的 Tag Value, Posting List 为该 Metric 下对应的 Series ID
   • Hash(Tags) => Series ID: 通过 Tags Hash Code 计算相应的 Series ID 是否已经存在
   • Series Sequence ID: 为 Metric 级别的 Series ID 生成器，为自增类型，这样所以生成的 Series ID 都是有序的 ID , 更容易做索引及存储
2. Metric Store: 主要存储了 Metric 下面的数据，即该 Metric 下面的所有对应 Series 的每个 Field 的数据
   • Field List(Field Store): 根据不同的 Field Type 存储该 Field 的实际数据

整个内存结构中维护了上面 2 个数据结构的 2 个映射关系。

Series ID 的唯一性

部分设计考虑了 OpenTSDB String => Int 的思路，考虑到时序数据的特点， Metric Name + Tags 这部分占用存储大头的数据存储在 Index 中： Filtering/Grouping 等操作将基于这部分数据来进行，实际存储数据时只存储到Series ID。

Metric下的每一条Series线的唯一性通过tags来确定：对于tags(ip=1.1.1.1, host=test.vm, zone=nt)，先根据tagKey作排序，得到host=test.vm,ip=1.1.1.1,zone=nt。如果原始存储tags文本到Series ID的映射关系，会浪费过多的存储空间。权衡效率后，LinDB 通过对tags计算hash来记录Series，关于碰撞机率可参考 生日碰撞

一般化的哈希碰撞机率公式如下：

通过以上公式，计算得64位hash在不同的tags组合数下的碰撞概率见下表。其中d为取值空间，n为数据集规模。 在监控领域下，Metric下tags的组合数极少能达到1M量级，即使在该量级碰撞机率也极低。

写

整个写入流程如下:

1. 首先通过 Hash(Metric Name) 查询是否存在对应的 Metric Index
   • 存在: 使用 Metric Index 中的数据，找到对应的 Field ID 和 Series ID，如果没有对应的 Field ID 和 Series ID 的话先生成对应的 ID，直接返回，异步的对 Tags 来构建一个倒排索引，以做到构建索引和写数据可以并行处理来提升写入性能
   • 不存在: 这种情况为一个新的 Metric, 返回对应的 ID，异步构建 Index
   • Index 使用 Roaring Bitmap 为存储 Series ID Posting List
2. 拿到 Metric ID/Series ID 之后，就可以操作 Metric Store 了，找到对应的 Field Store 写入即可

这里需要注意的地方有，如果直接使用 Map 来存储 Metric Store 里面的 Map 的话内存的开销还是比较大的，因为本身已经都转换成了 Int，所以这里可以使用 Roaring Bitmap + Array 的数据结构来构建一个 Map 结构，在 Roaring Bitmap 中存储所有 Keys 的值，Key 在 Roaring Bitmap 中的位置就是 Array 的 Index，所以读取的效率也可以保证，同时可以与倒排索引里面的 Roaring Bitmap 保持一致。

深入 Roaring Bitmap 之后发现 Roaring Bitmap 内部是以 High Container + Low Container 的方式存储的，所以 Roaring Bitmap + Array 也可以使用这个思想来对进一步优化 Map 结构，即使用 Roaring Bitmap + []Array 的结构，Key 的高位使用 Roaring Bitmap 的 High Container 来存储，Key 的低位用 Low Container 来存储，Key 的高位对应一个 Array，整体就是一个 2 维数组。这样就可以通过 Key 的高位来进行并行查询操作。

Flush

系统会定期检测当前系统中每个 Memory TSDB 是否已经超过了内存大，如果满足下面条件中的任何一种，都需要把内存中的数据 Flush 到磁盘上：

1. 单个 Memory TSDB 的内存占用超过指定大小
2. 该个 Memory TSDB 距离上次 Flush 时间超过了一定的大小
3. 该 LinDB 实例总内存占用超过一定大小之后，Flush 哪些占用内存比较大的 Memory TSDB，以防止该实例 OOM

文件结构请看 Storage SSTable。