作者|中尾亮
译者|王雪莹编辑|张
出品| csdn (ID: csdnnews)
这篇文章翻译自中尾良的个人博客(https://corecursive.com/066-sqlite-with-richard-hipp/)，主要告诉你如何实现一个时序数据库引擎。是作者的经历，是我从零开始写一个轻量级的时序数据库引擎学到的。
虽然这个引擎是用Go语言编写的，但是本文涉及的大部分内容与编程语言无关。
动机
我一直在研究一些处理海量时间序列数据的工具。其中一个是阿里(https://github . com/naka bonne/Ali)，是一个负载测试工具，可以在客户端实时绘制测量值。它请求执行特定的查询，并无休止地写入每个查询的结果，如延迟或任何其他指标。换句话说，有点像在一台主机上创建一个具有简单查询功能的推送监控系统。
在以前的实现中，它只是将数据点追加到堆上的可变长度数组中。这自然会导致一个问题，那就是随着时间的推移，内存使用量会不断增加:
由naka bonne/go sify测量的Ali堆使用情况
为了解决这个问题，我尝试开发一个存储引擎，可以作为围棋库。
时间序列数据的特征
首先要了解时间序列数据，才能整理出需要解决的问题。
时间序列数据是带有时间戳的多个值的集合。一般用于观测时变数据。每个时间序列数据称为一个数据点，通常表示为一个带有时间戳和值的元组。时间序列数据具有以下特征:
1。海量数据
由于时间序列数据的性质，单个数据点的意义不大，只有在收集了大量数据后才会变得有效。在金融行业，数据捕获要求超过1000000次/秒的情况并不少见，因为数据通常是在很短的时间内写入的。
在Ali的用例中，用户指定的请求速率与写性能要求直接相关(虽然文件描述符数量的上限基本上是瓶颈)。
为了处理海量数据，我们需要尽可能集中精力优化数据写入过程，也需要尽可能减少磁盘空之间的消耗。
2。只添加了。
每个数据点都是不变的。此外，批量删除操作通常是在没有指定特定数据点的情况下对旧数据执行的。
3。按时间排序
因为数据是按时间戳排序的，所以可以看作是按时间索引的。使用该属性，您可以在没有任何开销的情况下构建索引。
4。批量访问
在读出数据时，主要是通过指定一个时间段来检索多个时间戳连续的数据点。您可以使用此功能来提高数据读取的局部性。
5。最近优先级
在许多用例中，我们倾向于读取和使用最新的数据点。这可能会影响缓存算法的选择。
6。高基数
时间序列数据往往具有较高的基数。例如，在系统监控环境中尤其如此。在云时代，我们有更多的机会监控主机和网络等动态变化的环境。
从这个意义上说，几乎没有相同的度量标准；为每个指标创建一个文件会导致各种问题，比如索引节点限制。
现有解决方案
一般来说，我们发现对时序数据的操作是写密集型的，在很多情况下，数据是在一个时间范围内顺序读/写的。
Google的LevelDB是众所周知的键值存储引擎，Go语言的一些实现已经发布。LevelDB基于LSM树，只按顺序写尾部，适合只追加时序数据。键排序也使它适用于基于时间戳的时间序列数据。事实上，早期的Prometheus和InfluxDB存储引擎也是基于LevelDB的。
但是，有些东西是浪费的。正如我们将在后面看到的，时间序列数据是单向的，这可以用来将其编码成较小的大小。我们希望利用这一点，因为我们必须处理大量的时间序列数据。
此外，因为所有数据点都是不可变的，并且不需要更新过程，所以所有写操作都可以按顺序执行。尽管如此，我还是有点担心在执行合并SSTables之类的操作时可能会出现写放大。
t存储
鉴于此，我决定自己写一个数据库引擎库，名为tstorage。
它是一个使用本地磁盘的轻量级引擎，用纯Go语言编写。
本文介绍了我是如何实现tstorage的，并解释了创建它所需的知识。
何谓数据库引擎
典型的DBMS处理来自客户端的请求，并控制集群节点之间的通信。它还解析查询，制定执行计划，并根据这些计划从磁盘读取/写入数据。数据库引擎是一个只执行最后读/写部分的组件，它也是下图中存储引擎的一部分。
数据库内部结构，Alex Petrov，2019，第一章，图1-1。管理系统架构
数据库引擎抽象磁盘/内存上的数据结构，为图中所示的执行引擎提供API，并提供事务和恢复功能。
数据模型
基于这些特点，tstorage采用了线性数据模型结构，将数据点按时间划分。每个分区充当一个完全独立的数据库，包含其时间范围内的所有数据点。
│ │读写││v│┌───────────────────┐max:1600010800 ├─────>；内存分区│└───────────────────┘min:1600007201││┌───────────────────┐max:1600007200 ├─────>；内存分区│└───────────────────┘min:1600003601││┌───────────────────┐max:1600003600 └─────>；磁盘分区└———————————————————————————————————┘min:1600000000受LSM树影响稍大，Prometheus的V3存储也采用了非常相似的模型。
只有头和下一个分区在堆上并且是可写的。这被称为内存分区。在内存分区中，数据在写入之前被附加到预写日志的末尾，以防止数据丢失(如果不需要这种持久性，可以将其关闭)。
旧分区被写入磁盘上的单个文件。这称为磁盘分区，并且是只读的。写入磁盘的文件由mmap(2)内核透明地缓存，这将在后面解释。
您可以为分区设置一个时间段，在此之后，新的内存分区将自动添加到堆头，旧的内存分区将刷新到磁盘。
这种模式有很多优点。首先，指定范围外的分区在读取时完全可以忽略。这种尽可能缩小搜索范围的想法是受LevelDB中使用的Bloom filter的启发。此外，因为最新的数据点缓存在堆中，所以大多数数据点都可以快速读取。
此外，由于tstorage被设计为将分区写入文件:
的所有写操作只能在没有任何写放大的情况下追加，因为它只能按顺序写入一个文件。
文件的数量不取决于基数(度量类型的数量)。
如前所述，读取操作通常指定一个时间段并获取相邻的数据点，从而提高了局部性。
下一节描述了每个分区实现中的要点。
内存分区
1。数据点列表
数据点列表被表示为堆上的一个数组(从技术上来说，它有点像Go语言中指向名为Slice的基数组的指针列表)。这是一个包含无限多个要写入的数据点的列表，所以乍一看，链表似乎是最好的选择，因为它可以添加复杂度为O(1)的元素。但是，内存中具有相邻元素的数组将受益于缓存的空局部性。此外，因为时间序列数据总是预先排序，所以诸如二分搜索法的经典搜索算法可以容易地实现。
2。无序的数据点
在实际应用中，由于网络延迟或时钟同步而导致数据点无序的情况并不少见。写的时候要考虑到这一点，分区里的数据点要一直保持有序。
但是，请注意，当数据点作为数组管理时，每次写入都需要应用一个排他锁。我们必须考虑一种很酷的方式来接收它们，这样我们就不必延长锁定时间来适应无序的数据点。
乱序数据点可以分为两种情况:一是在要写入的分区内乱序；在第二种情况下，数据点超出了第一次尝试写入的分区的范围。
如果写入的数据点符合第一种情况，我们将首先在一个单独的数组中无序地缓存数据点。然后，当刷新到磁盘时，数据点与内存分区中的数据点合并并重新排序。
在数据模型部分，我提到了堆上只有header和它的下一个分区，以适应第二种情况:在header中添加一个新的分区后，可能会立即写入跨分区的数据点。这是为了解决第二种情况。通过保持最后两个分区可写，我们可以防止这些数据点被丢弃。
3。预写日志(WAL)
内存分区使用易失性存储，因此突然崩溃或断电可能会导致数据丢失。为了解决这个问题，内存分区首先将操作日志写入预写日志(WAL)。在崩溃的情况下，可以通过从日志的开头写到结尾来恢复。
对于支持磁盘上数据更新操作的数据库引擎，WAL必须执行非常底层的操作:要完全恢复更新所做的处理，需要准确地存储哪些磁盘块中的哪些字节发生了变化，等等。
但是，时序数据只是附加的，tstorage会将所有磁盘分区设置为只读。它只需要附加关于哪些数据点已被写入内存分区的高级信息，这样就可以用一种简单且独立于磁盘的格式来恢复它们。
磁盘分区
理解磁盘分区的最快方法是查看文件系统上的宏布局。
如下所示，每个分区使用一个目录，该目录下有元数据和实际压缩数据。这是普罗米修斯布局的简化版，所以你之前可能见过类似的结构。
$树。/数据。/├-p-160000001-1600003600 │├-data │└-meta.数据JSON ├-P-1600003601-16000007200元数据顺序来描述实现点。
1。存储器映射数据
如上所述，分区中的所有数据点都被写入文件。Tstorage采用以下格式。
94848 - ┐┌│││││││┌┌┌│││││││││││^││^ 8 │││││││││││└└┘┘┘┘┘┘┘┘┘┘┘┘┘┘┘┘9
回忆时间序列数据的特征。数据点是不可变的，大多数情况下，通过指定一个范围来批量获取指标。因此，我们可以通过按度量对数据点进行分组来提高局部性。
这个文件由mmap(2)中的内核透明地缓存。这使得我们可以缓存文件，而无需将它们复制到users 空。这个方法很有效，因为我最初的动机是想解决阿里日积月累吃堆的问题。
Go程序可以按字节访问内存映射文件，就像堆上的一个字节字符串一样。
type disk partition struct {//f映射文件字节支持的数据文件f * OS.file//memory-mapped文件的文件描述符现在，我们如何搜索这个自包含的字节序列？在Go程序中很容易将其复制到堆中并解码成数据结构，但这并不能达到内存映射的目的。无论如何，我们需要一个索引结构来有效地访问编码数据。接下来描述的元数据用于此目的。
2。元数据
元数据的内容如下。一个分区中只有一个元数据，这也是为什么JSON格式虽然有点多余，但编程可以轻松处理的原因。
$猫。/data/p-16000000001-16000003600/meta . JSON { " minTimestamp": 1600000001，" maxTimestamp": 1600003600，" numDataPoints": 7200，" metrics ":{ " metric-1 ":{ " name ":" metric-1 "，" offset": 0，" minTimestamp ":1600000001，" maxTimestamp": 1600003600，" metrics这是存储每个指标的文件偏移量和字节大小的地方。只有这些元数据可以进入堆。利用这些信息，tstorage尝试随机访问内核空之间映射的数据。类似于:
{ "minTimestamp": 1600000001，" maxTimestamp": 1600003600，" numDataPoints": 7200，" metrics ":{ " name ":" metric-1 "，┌───── "offset": 0，│" mintimestamp ":16000000001，│ "maxTimestamp": 1600003600，│" numdatapoints ":3600 │, │" metric-2 ":{ │" name ││" numdatapoints ":3600 │││}││││││││││┌───────────────────┘│v v 0 36014┌───────────────────────────┐│米制-1 │米制-2│││││米制-3││││米制-4│││││││││──────────┘││││││米制-4│││947
代码
如前所述，时间序列数据通常由时间戳和值的元组表示，可以巧妙地编码成非常小的大小。
2015年，脸书发表了一篇题为《大猩猩:一个快速且可扩展的内存时间序列数据库》的论文，他们在论文中介绍了一种利用时间序列数据特征的编码方法。目前很多主流的时间序列数据库都是基于这种编码方式，tstorage也是如此。
时间戳和值以不同的方式编码。首先，tstorage中的UNIX时间戳被表示为一个无符号的64位整数。由于时间戳趋向于单调增加，所以只存储与前一个值之差的编码方法是有效的。因此，使用增量的增量编码。
此外，tstorage中的值表示为带符号的64位浮点类型。该值使用XOR编码，因为它倾向于保持接近该值，尽管不可能单调增加或减少。
我将解释每种编码方法。
1。增量编码
Delta-of-Delta编码是一种使用Delta编码的方法，所以我先解释一下Delta编码。
增量编码只写前一个数和当前数的差。
例如，假设第一个时间戳是160000000。如果后面写1600000060->:160000120->；10000181，增量分别为60，60，61。
| 增量 | 160000000- | 16000006060 | 16000012060 | 16000018161 |
只有这些增量值按顺序写入文件。解码时，可以通过依次应用增量值来恢复原始值。
2。增量增量编码
即使使用增量编码，一些变长编码结果也可以足够小。而时间序列数据的时间戳通常有固定的间隔，增量值本身很可能相互接近。所以用这个增量值的增量值可以省更多。这个增量值的增量值叫做增量的增量。
让我们以前面例子中时间戳的增量为例。
| 增量 | 的增量 | 1600000000- | - | 160000006060 | - | 160000012060 | 0 | 160000018161 | 一个 |
对于第一个时间戳，由于无法计算增量值，我们照原样写160000000。根据论文，Gorilla使用固定长度编码来编码数据，而tstorage使用称为Variants的可变长度编码方法。
对于第二个时间戳，因为无法计算delta-of-delta，所以我们按原样写入增量值60。Gorilla假设每4小时(=16384秒)创建一个时间序列数据块，可获得的最大位数为14位，因此采用14位的固定长度编码。但是tstorage使用了变体进行变长编码(Prometheus也是用变体对前两个时间戳进行编码，我真的不知道大猩猩为什么要用定长)。
如果你有兴趣了解更多关于变体是如何工作的，请查看我的上一篇文章:https://nakabane.dev/posts/binary-encoding-go/#变体是如何工作的。
Delta-of-delta采用变长编码，因此其大小取决于要写入的数的大小。如果delta-of-delta为0，则使用1位写入0。如果delta-of-delta在64 ~ 64范围内，用2位写1和0，然后用7位写delta-of-delta。
所以每个时间戳的大小是:
| 增量 | 的增量 | 长度 | 1600000000- | - | 40位 | 160000006060 | - | 8位 | 16000012060 | 0 | 1位 | 16000018601 | 9位 |
总大小为40+8+1+9=58位。
如果我们用固定长度对原始的四个时间戳进行编码，我们得到64×4 = 256位；你可以看到我们节省了大量的尺寸。
如您所见，如果时间戳以规则的间隔排列，那么delta-of-delta将始终为零，这使得编码非常高效。如果您希望保持尽可能小的大小，您应该尝试以固定的周期写入数据点。
如果你想了解更多，建议你看一下论文的4.1.1压缩时间戳。
3。异或编码
XOR编码是对两个浮点值进行XOR运算并写入它们而不是实际值的方法。
如果我们对接近的值进行XOR运算，前导零和尾随零往往会更多，我们希望忽略要写入的大小。例如，如果我们对2.0和3.0进行异或运算:
2.0 3.0 = 000000000000000000000000000000000000000000000000└领先0s ┘└落后0s ┘可以看到，异或结果分为三部分。
如果有意义的比特与先前值的比特相同
写入0和有意义的位并退出。
写入有意义位的大小(6位)
写出有意义的比特本身。
如果想了解更多，建议看一下论文的4.1.2压缩值。
注意
重要的是要记住，这些编码方法依赖于相邻值之间的关系，因此不能像现在这样随机访问它们。
九。Ali 的性能改进
之前:
之后:
我们可以看到时序存储层的增加解决了堆使用量随时间增加的问题。
储存的缺点
Tstorage很简单，所以还是有些功能不够强大。
例如，如果一个磁盘分区有大量不同的指标，就会出现堆不堪重负的问题。如前所述，数据本身映射到内核空，所以对数据增长非常有利。但是，索引的所有元数据都在堆上。因为每个指标都有元数据，所以每个分区中的元数据量会随着指标数量的增加而增加，堆的使用量也会线性增加。
摘要[/s2/]
我认为时间序列数据是第一次实现存储引擎的好题目，因为要处理的问题很简单，可以用一种直截了当的方式来设计。
本文以抽象的方式介绍了实现的要点，但如果你还有兴趣，希望你可以看看源代码(https://github . com/naka bonne/t storage)。
如果您有任何问题或反馈，或者发现错误，您可以通过任何您喜欢的方式联系我，这简直太棒了。
原文:https://corecursive.com/066-sqlite-with-richard-hipp/
声明:本文由CSDN翻译，转载请注明出处。
参考:
