Beringei 内存时序数据库

2019-04-02 database linux

Facebook 在 2017.02.03 开源了一个高性能内存时序数据存储引擎 Beringei ，用来解决监控数据的存储和查询需求，具有快速读写、高压缩比等特性。

这里简单介绍。

简介

Facebook 监控团队在 VLD2015 大会上发表一篇名为 Gorilla：A Fast, Scalable, In-Memory Time Series Database 的文章，而 Beringei 正是基于这项工作成果的进一步发展。

FB 最开始采用的是 HBase 进行存储，随着系统的不断发展，2013 年初，监控团队发现 Hbase 无法灵活扩展，将导致未来无法处理高并发的读取负载。

例如：同时分析几千个时序数据时需要几十秒的时间，而对于稀疏数据查询执行时间更长，甚至会出现查询超时。

为此，评估了几款时序数据存储的解决方案：OpenTSDB 压缩率不足，还可能导致数据精度下降；Whisper 不支持数据时序抖动，且不是内存数据库，性能不足；InfluxDB 由于支持 Meta 存储，压缩率不足导致内存利用率下降。

为了解决监控的场景，需要满足如下特性：

  • 高并发写，TPS 基本固定，但是写入量很大，例如 1000w/s；
  • 快速响应查询，其中部分是小窗口 (一般最近 1~2 小时) 的数据聚合查询；
  • 优化最近 26 小时的数据读写，85% 的数据查询是在最近 26 小时内；
  • 采用 ClusterFS 持久化数据，貌似应该是 GlusterFS ；
  • 提供容错能力，包括了容灾、宕机恢复等故障场景；
  • 水平扩展。

压缩算法

为了提高数据的读写效率，最简答的方式就是尽可能高效的利用内存来存储时序数据，也就是通过提高数据的压缩效率，尽量将更多的数据保存在内存中。

采用 Delta-of-Delta 编码压缩时间戳，采用 XOR 压缩 64 位的浮点数。

beringei compress

Delta-of-Delta

一般监控数据是通过固定周期进行采集的，也就是意味着其步长 (Delta) 相同，那么如果再计算一次 (Delta) 一般都是 0 。

在采用该算法来压缩时间戳时，具体的算法步骤如下：

  • 头部存储序列的起始时间戳 T0，该值与两小时的窗口对齐，其中第一个时间戳 T1 采用 14bit 存储 t1−t2 的 Delta 值;
  • 对于接下来的时间戳 Tn 会计算其差值的差值。

在保存差值时，会根据差值 D 的大小保存相关数据：

  • 如果 = 0 则存储 Bit 0；
  • 如果 [−63, 64] 存储 10，并在接下来的 7bit 中存储 Delta 值；
  • 如果 [−255, 256] 存储 110 并在接下来的 9bit 中存储 Delta 值；
  • 如果 [−2047, 2048] 存储 1110 并在接下来的 12bit 中存储 Delta 值；
  • 否则存储 1111 在接下来的 32bit 中存储 Delta 值。

如图 1 所示，采用时间压缩算法可以得到：Header 存储时间 T0 2015.03.24T02:00:00；紧接着存储第一个时间点 T1 2015.03.24T02:01:02 与 T0 的时间差为 62 ；第二个时间点 T2 2015.03.24T02:02:02 与 T1 的差值为 60 ，而 60 与 62 的差值为 -2 (也就是所谓的 Delta-of-Delta 值)，则存储标记位 10 及其值 -2；而 T3 2015.03.24T02:03:02 与 T2 差值的差值为 0 ，那么直接将存储标记为 0 。

XOR 压缩

其中值的压缩算法采用 XOR 编码，具体的算法步骤如下：

  • 第一个值不压缩，直接存储值；
  • 如果 XOR 的值为 0 (也就是之前的值一样)，那么存储 bit 0；
  • 如果 XOR 的值非 0，那么计算 XOR 后前置 0 和尾部 0 的值，存储一位 bit 1 ，然后根据情况存储下一位。

其中下一位的存储方式如下：

  • 控制位 0 。如果 XOR 后的有效位落在之前有效位内 (至少与之前相同的前导零和后缀零) 则只存储有意义的 XOR 值；
  • 控制位 1 。通过 5bit 存储前导零长度，6bit 存储有效 XOR 值长度，最后存储有效 XOR 值。

PS. 所谓的有效值，就是执行 XOR 运算后，位的值为 1 的范围。

如图 1 所示，采用值压缩算法，其中 T1 时刻的值为 12 直接存储；T2 时刻的值 12 与 T1 时刻值的 XOR 值为 0 ，则直接存储标记位 ‘0’ (注意，此时没有所谓的有效值)；T3 时刻的值 24.0 与 T2 时刻的值做 XOR 运算后，有效位是 1 ，前导零数为 11 (通过 5bit 保存)，接着 6bit 保存 XOR 后的有效值长度，然后是有效值。

其它

浮点数表示方法

任何数据在内存中都是以二进制的形式存储，包括浮点数，目前所有的 C/C++ 编译器都是采用 IEEE 所制定的标准浮点格式，即二进制科学表示法。

在二进制科学表示法中，S=M*2^N 主要由三部分构成：符号位、阶码 N、尾数 M。对于 float 类型数据，其二进制有 32 位，其中符号位 1 位，阶码 8 位，尾数 23 位；对于 double 型数据，其二进制为 64 位，符号位 1 位，阶码 11 位，尾数 52 位。

其中使用方式如下：

  • 符号位，0 表示正，1 表示负；
  • 阶码，这里采用移码表示，详见如下解释；
  • 尾数，有效数字位，即部分二进制位(小数点后面的二进制位)，因为规定 M 的整数部分恒为 1，所以这个 1 就不再进行存储。

对于阶码来说，以 float 型为例，其规定偏置量为 127，因为阶码有正有负，对于 8 位二进制来说，其表示范围为 -128~127，若阶码的真实值为 2，则加上 127 后为 129，其阶码表示形式为 10000010 。

示例

将 125.5 转换为浮点

这里转换为 float 类型的浮点数。

其中 125 二进制表示形式为 1111101，而小数部分表示为二进制为 1 ，那么 125.5 二进制表示为 1111101.1。由于规定尾数的整数部分恒为 1，则表示为 1.1111011*2^6，那么阶码为 6 ，加上 127 为 133，则表示为 10000101，而对于尾数将整数部分 1 去掉，为 1111011，在其后面补 0 使其位数达到 23 位，则为 11110110000000000000000 。

这样其二进制表示形式为 0 10000101 11110110000000000000000，因为 Intel CPU 采用的小端字节序，那么实际在内存中存放的数据为：

00000000 0x00  低地址
00000000 0x00
11111011 0xfb
01000010 0x42  高地址
将二进制转换为浮点数

仍然以 float 类型为例，其中二进制的序列为 0 10000101 11110110000000000000000 。

符号位为 0 表示正数，而阶码为 133-127=6，尾数为 11110110000000000000000 ，则其真实尾数为 1.1111011。

所以其大小为 1.1111011*2^6，将小数点右移 6 位，得到 1111101.1，而 1111101 的十进制为 125，0.1 的十进制为 1*2^(-1)=0.5，所以其大小为 125.5 。

测试程序

可以通过如下程序进行测试。

#include <stdio.h>

int main(void)
{
    unsigned char *ptr;
    float a = 125.5;

    ptr = (unsigned char *)&a;
    printf("%02X%02X%02X%02X\n", *(ptr + 3), *(ptr + 2), *(ptr + 1), *(ptr + 0));

    return 0;
}

参考

实现详细可以参考 Github Beringei 中关于 TimeSeriesStream::appendValue() 的介绍。