Beringei 内存时序数据库

2019-04-02 Tuesday     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() 的介绍。



如果喜欢这里的文章,而且又不差钱的话,欢迎打赏个早餐 ^_^


About This Blog

Recent Posts

Categories

Related Links

  • RTEMS
    RTEMS
  • GNU
  • Linux Kernel
  • Arduino

Search


This Site was built by Jin Yang, generated with Jekyll, and hosted on GitHub Pages
©2013-2019 – Jin Yang