A minimize Time Series Database, written from scratch as a learning project. 从零开始实现一个 TSDB
A minimize Time Series Database, written from scratch as a learning project. 从零开始实现一个 TSDB
A minimize Time Series Database, written from scratch as a learning project.
时序数据库（TSDB: Time Series Database）大多数时候都是为了满足监控场景的需求，这里先介绍两个概念：
series1: {"__name__": "netspeed", "host": "localhost", "iface": "eth0"}
series2: {"__name__": "netspeed", "host": "localhost", "iface": "eth1"}
Prometheus, InfluxDB, M3, TimescaleDB 都是时下流行的 TSDB。时序数据的压缩算法很大程度上决定了 TSDB 的性能，以上几个项目的实现都参考了 Facebook 2015 年发表的论文《Gorilla: A fast, scalable, in-memory time series database》 中提到的差值算法，该算法平均可以将 16 字节的数据点压缩成 1.37 字节，下文会介绍。
Who's mando?
Din Djarin, also known as "the Mandalorian" or simply "Mando," was a human male Mandalorian who worked as a famous bounty hunter during the New Republic Era.
What's mandodb?
作为一名监控系统开发人员，自然要对时序数据库有所了解。mandodb 是我在研究过程中实现的一个最小化的 TSDB，从概念上来讲它还算不上是一个完整的 TSDB，因为它：
mandodb 主要受到了两个项目的启发。本项目仅限于学习用途，未经生产环境测试验证！
prometheus 的核心开发者 Fabian Reinartz 写了一篇文章 《Writing a Time Series Database from Scratch》 来介绍 prometheus TSDB 的演变过程，非常值得一读，强烈推荐。
数据模型定义
// Point 表示一个数据点 (ts, value) 二元组
type Point struct {
Ts int64 // in seconds
Value float64
}
// Label 代表一个标签组合
type Label struct {
Name string
Value string
}
// Row 一行时序数据 包括数据点和标签组合
type Row struct {
Metric string
Labels LabelSet
Point Point
}
// LabelSet 表示 Label 组合
type LabelSet []Label
// LabelMatcher Label 匹配器 支持正则
type LabelMatcher struct {
Name string
Value string
IsRegx bool
}
// LabelMatcherSet 表示 LabelMatcher 组合
type LabelMatcherSet []LabelMatcher
API
// InsertRows 写数据
InsertRows(rows []*Row) error
// QueryRange 查询时序数据点
QueryRange(metric string, lms LabelMatcherSet, start, end int64) ([]MetricRet, error)
// QuerySeries 查询时序序列组合
QuerySeries(lms LabelMatcherSet, start, end int64) ([]map[string]string, error)
// QueryLabelValues 查询标签值
QueryLabelValues(label string, start, end int64) []string
配置项在初始化 TSDB 的时候设置。
…
…
下面是我对这段时间学习内容的整理，尝试完整介绍如何从零开始实现一个小型的 TSDB。
我本身并没有数据库开发的背景，某些描述可能并不那么准确，所以欢迎 实名 diss 指正。
Gorilla 论文 4.1 小节介绍了压缩算法，先整体看一下压缩方案，T/V 是紧挨存储的，'0'/'10'/'11' 表示控制位。
Figure: Gorilla 压缩算法
Timestamp DOD 压缩：
在时序的场景中，每个时序点都有一个对应的 Timestamp，一条时序序列中相邻数据点的间隔是有规律可循的。一般来讲，监控数据的采集都是会以固定的时间间隔进行的，所以就可以用差值来记录时间间隔，更进一步，我们可以用差值的差值来记录以此来减少存储空间。
t1: 1627401800; t2: 1627401810; t3: 1627401820; t4: 1627401830
--------------------------------------------------------------
// 差值：delta
t1: 1627401800; (t2-t1)d1: 10; (t3-t2)d2: 10; (t4-t3)d3: 10;
--------------------------------------------------------------
// 差值的差值：delta of delta
t1: 1627401800; dod1: 0; dod2: 0; dod3: 0;
实际环境中当然不可能每个间隔都这么均匀，由于网络延迟等其他原因，差值会有波动。
Value XOR 压缩：
Figure: IEEE 浮点数以及 XOR 计算结果
当两个数据点数值值比较接近的话，通过异或操作计算出来的结果是比较相似的，利用这点就可以通过记录前置零和后置零个数以及数值部分来达到压缩空间的目的。
下面通过算法实现来介绍，代码来自项目 dgryski/go-tsz。代码完全按照论文中给出的步骤来实现。
…
论文给出了不同 case 的 buckets 占比分布。
Figure: Timestamp buckets distribution
Figure: Value buckets distribution
Timestamp buckets 中，前后两个时间戳差值相同的比例高达 96.39%，而在 Value buckets 中只用一个控制位的占比也达到了 59.06%，可见其压缩比之高。
论文还给出了一个重要结论，数据压缩比随着时间的增长而增长，并在 120 个点的时候开始收敛到一个最佳值。
Figure: 压缩率曲线
Gorilla 差值算法也应用于我的另外一个项目 chenjiandongx/tszlist，一种时序数据线程安全链表。
时序数据具有「垂直写，水平查」的特性，即同一时刻有多条时间线的数据不断被追加。但查询的时候往往是查某条时间线持续一段时间内的数据点。
…
时序数据跟时间是强相关的（不然还叫时序数据？），即大多数查询其实只会查询最近时刻的数据，这里的「最近」是个相对概念。所以没必要维护一条时间线的完整生命周期，特别是在 Kubernetes 这种云原生场景，Pod 随时有可能会被扩缩容，也就意味着一条时间线的生命周期可能会很短。如果我们一直记录着所有的时间线的索引信息，那么随着时间的推移，数据库里的时间线的数量会呈现一个线性增长的趋势 ，会极大地影响查询效率。
这里引入一个概念「序列分流」，这个概念描述的是一组时间序列变得不活跃，即不再接收数据点，取而代之的是有一组新的活跃的序列出现的场景。
series
^
│ . . . . . .
│ . . . . . .
│ . . . . . .
│ . . . . . . .
│ . . . . . . .
│ . . . . . . .
│ . . . . . .
│ . . . . . .
│ . . . . .
│ . . . . .
│ . . . . .
v
我们将多条时间线的数据按一定的时间跨度切割成多个小块，每个小块本质就是一个独立小型的数据库，这种做法另外一个优势是清除过期操作的时候非常方便，只要将整个块给删了就行 （梭哈是一种智慧）。内存中保留最近两个小时的热数据（Memory Segment），其余数据持久化到磁盘(Disk Segment)。
Figure: 序列分块
DiskSegment 使用的是 AVL Tree 实现的列表，可在插入时排序。为什么不用更加高大上的红黑树？因为不好实现...
当 Memory Segment 达到归档条件的时候，会创建一个新的内存块并异步将刚归档的块写入到磁盘，同时会使用 mmap 将磁盘文件句柄映射到内存中。代码实现如下。
…
Figure: Memory Segment 两部分数据
写入的时候支持数据时间回拨，也就是支持有限的乱序数据写入，实现方案是在内存中对还没归档的每条时间线维护一个链表（同样使用 AVL Tree 实现），当数据点的时间戳不是递增的时候存储到链表中，查询的时候会将两部分数据合并查询，持久化的时候也会将两者合并写入。
mmap 是一种将磁盘文件映射到进程的虚拟地址空间来实现对文件读取和修改操作的技术。
从 Linux 角度来看，操作系统的内存空间被分为「内核空间」和「用户空间」两大部分，其中内核空间和用户空间的空间大小、操作权限以及核心功能都不相同。这里的内核空间是指操作系统本身使用的内存空间，而用户空间则是提供给各个进程使用的内存空间。由于用户进程不具有访问内核资源的权限，例如访问硬件资源，因此当一个用户进程需要使用内核资源的时候，就需要通过 系统调用 来完成。
虚拟内存细节可以阅读 《虚拟内存精粹》 这篇文章。
Figure: 常规文件操作和 mmap 操作的区别
常规文件操作
读文件： 用户进程首先执行 read(2) 系统调用，会进行系统上下文环境切换，从用户态切换到内核态，之后由 DMA 将文件数据从磁盘读取到内核缓冲区，再将内核空间缓冲区的数据复制到用户空间的缓冲区中，最后 read(2) 系统调用返回，进程从内核态切换到用户态，整个过程结束。
写文件： 用户进程发起 write(2) 系统调用，从用户态切换到内核态，将数据从用户空间缓冲区复制到内核空间缓冲区，接着 write(2) 系统调用返回，同时进程从内核态切换到用户态，数据从内核缓冲区写入到磁盘，整个过程结束。
mmap 操作
mmap 内存映射的实现过程，总的来说可以分为三个阶段：
** 小结**
常规文件操作为了提高读写效率和保护磁盘，使用了页缓存机制。这样造成读文件时需要先将文件页从磁盘拷贝到页缓存中，由于页缓存处在内核空间，不能被用户进程直接寻址，所以还需要将页缓存中数据页再次拷贝到内存对应的用户空间中。这样，通过了两次数据拷贝过程，才能完成进程对文件内容的获取任务。写操作也是一样，待写入的 buffer 在内核空间不能直接访问，必须要先拷贝至内核空间对应的主存，再写回磁盘中（延迟写回），也是需要两次数据拷贝。
而使用 mmap 操作文件，创建新的虚拟内存区域和建立文件磁盘地址和虚拟内存区域映射这两步，没有任何文件拷贝操作。而之后访问数据时发现内存中并无数据而发起的缺页异常过程，可以通过已经建立好的映射关系，只使用一次数据拷贝，就从磁盘中将数据传入内存的用户空间中，供进程使用。
总而言之，常规文件操作需要从磁盘到页缓存再到用户主存的两次数据拷贝。而 mmap 操控文件只需要从磁盘到用户主存的一次数据拷贝过程。mmap 的关键点是实现了「用户空间」和「内核空间」的数据直接交互而省去了不同空间数据复制的开销。
TSDB 的查询，是通过 Label 组合来锁定到具体的时间线进而确定分块偏移检索出数据。
在传统的关系型数据库，索引设计可能是这样的。
| Sid（主键） | Label1 | Label2 | Label3 | Label4 | ... | LabelN |
|---|---|---|---|---|---|---|
| sid1 | × | × | × | ... | × | |
| sid2 | × | × | × | ... | × | |
| sid3 | × | × | × | ... | × | |
| sid4 | × | × | × | ... | × |
时序数据是 NoSchema 的，没办法提前建表和定义数据模型 ，因为我们要支持用户上报任意 Label 组合的数据，这样的话就没办法进行动态的扩展了。或许你会灵光一现 ✨，既然这样，那把 Labels 放一个字段拼接起来不就可以无限扩展啦，比如下面这个样子。
| Sid（主键） | Labels |
|---|---|
| sid1 | label1, label2, label3, ... |
| sid2 | label2, label3, label5, ... |
| sid3 | label4, label6, label9, ... |
| sid4 | label2, label3, label7, ... |
哟嚯，乍一看没毛病，靓仔窃喜。
不对，有问题 ，要定位到其中的某条时间线，那我是不是得全表扫描一趟。而且这种设计还有另外一个弊病，就是会导致内存激增，Label 的 Name 和 Value 都可能是特别长的字符串。
那怎么办呢（ 靓仔沉默...），刹那间我的脑中闪过一个帅气的身影，没错，就是你，花泽类「只要倒立眼泪就不会流出来」。
我悟了！要学会逆向思维 ，把 Label 当做主键，Sid 当做其字段不就好了。这其实有点类似于 ElasticSearch 中的倒排索引，主键为 Keyword，字段为 DocumentID。索引设计如下。
| Label（主键） | Sids |
|---|---|
| label1: {vm="node1"} | sid1, sid2, sid3, ... |
| label2: {vm="node2"} | sid2, sid3, sid5, ... |
| label3: {iface="eth0"} | sid3, sid5, sid9, ... |
| label4: {iface="eth1"} | sid2, sid3, sid7, ... |
Label 作为主键时会建立索引（Hashkey），查找的效率可视为 O(1)，再根据锁定的 Label 来最终确定想要的 Sid。举个例子，我们想要查找 {vm="node1", iface="eth0"} 的时间线的话就可以快速定位到 Sids（忽略其他 ... sid）。
sid1; sid2; sid3
sid2; sid3; sid5
两者求一个交集，就可以得到最终要查询的 Sid 为 sid2 和 sid3。 Nice!
假设我们的查询只支持相等匹配的话，格局明显就小了 。查询条件是 {vm=~"node*", iface="eth0"} 肿么办？对 label1、label2、label3 和 label4 一起求一个并集吗？显然不是，因为这样算的话那结果就是 sid3。
厘清关系就不难看出，只要对相同的 Label Name 做并集然后再对不同的 Label Name 求交集就可以了。这样算的正确结果就是 sid3 和 sid5。实现的时候用到了 Roaring Bitmap，一种优化的位图算法。
Memory Segment 索引匹配
…
然而，确定相同的 LabelName 也是一个问题，因为 Label 本身就代表着 Name:Value，难不成我还要遍历所有 label 才能确定嘛，这不就又成了全表扫描？？？
没有什么问题是一个索引解决不了的，如果有，那就再增加一个索引。 --- 鲁迅。
只要我们保存 Label 的 Name 对应的 Value 列表的映射关系即可高效解决这个问题。
| LabelName | LabelValue |
|---|---|
| vm | node1, node2, ... |
| iface | eth0, eth1, ... |
还是上面的 {vm=~"node1|node2", iface="eth0"} 查询，第一步通过正则匹配确定匹配到 node1, node2，第二步匹配到 eth0，再将 LabelName 和 LabelValue 一拼装，Label 就出来了，✌️ 完事！
桥豆麻袋！还有一个精彩的正则匹配优化算法没介绍。
fastRegexMatcher 是一种优化的正则匹配器，算法来自 Prometheus。
…
SnappyBytesCompressor
func main() {
store := mandodb.OpenTSDB(mandodb.WithMetaBytesCompressorType(mandodb.SnappyBytesCompressor))
defer store.Close()
// ...
}
// 压缩效果 28M -> 26M
❯ ll seg-1627763918-1627771178
Permissions Size User Date Modified Name
.rwxr-xr-x 26M chenjiandongx 1 Aug 14:39 data
.rwxr-xr-x 110 chenjiandongx 1 Aug 14:39 meta.json
多多少少还是有点效果的 ...
压缩是有成本的，压缩体积的同时会增大 CPU 开销（mbp 可以煎鸡蛋了），减缓写入速率。
敲黑板，接下来就要来好好讲讲 data 文件到底写了什么东西。 data 存储布局如下。
Figure: Segment Stroage
TOC 描述了 Data Block 和 Meta Block（Series Block + Labels Block）的体积，用于后面对 data 进行解析读取。Data Block 存储了每条时间线具体的数据点，时间线之间数据紧挨存储。DataContent 就是使用 Gorilla 差值算法压缩的 block。
Figure: Data Block
Labels Block 记录了具体的 Label 值以及对应 Label 与哪些 Series 相关联。
Figure: Labels Block
Series Block 记录了每条时间线的元数据，字段解释如下。
Figure: Series Block
了解完设计，再看看 Meta Block 编码和解编码的代码实现，binaryMetaSerializer 实现了 MetaSerializer 接口。
type MetaSerializer interface {
Marshal(Metadata) ([]byte, error)
Unmarshal([]byte, *Metadata) error
}
编码 Metadata
…
解码 Metadata
…
至此，对 mandodb 的索引和存储整体设计是不是就了然于胸。** 文档较长，建议 Star 收藏，毕竟来都来了...**
Q: Is mandodb cool?
A: Not sure.
Q: Is mando awesome?
A: Definitely YES!
Q: Write performance?
A: ~40w/s
Q: PRs or Issues?
A: are welcome.
Q: What's the hardest part of this project？
A: Writing this document.
Q：Anything else?
A: *** Life is magic. Coding is art. Bilibili!***
MIT ©chenjiandongx
No open issues yet, or sync has not completed.