Facebook Gorilla


Facebook Gorilla

Gorilla是Facebook公司内部的时序数据库产品。Facebook在世纪的使用过程中发现现有的产品不能满足对Facebook超大数据量的处理要求,开发了Gorilla这一样一个产品,通过应用多种压缩方法、将数据放在内存之中,Gorilla获得了73x的延时提升、14x的吞吐量提升。

介绍&背景

2013年Facebook就开始使用一套基于HBase的时序数据库,但是随着Facebook的发展,这套系统以及不能满足未来的负载,90%的查询已经长达几秒。一个对几千个时间序列的查询要消耗几十秒的时间来执行,而在稀疏的更大数据集上查询通常会超时。HBase被设置为写入优化,现在在其中已经保存了2PB的数据,查询的效率不高,又不太好完全更换系统。所以,Gorilla讲注意力转移到给现有的系统在一个in-memory的cache。这里数据的特点就是新数据一般是热点数据,所以选择奖近段时间内的数据cache,就能很好地提高性能。 Memcache是Facebook大规模使用的一个缓存系统,但是将memcache应用在这里,追加新数据到已经存在的时间序列中要消耗一个read/write周期,给memcache造成很大的压力,所以需要一种更好的解决方案。注:这里没怎么看懂,原文是:

  We also considered a separate Memcache [20] based write-through cache but rejected it as appending new data to an existing time series would require a read/write cycle, causing extremely high traffic to the memcache server. We needed a more efficient solution. 

对于Gorilla,主要有以下的要求:

    1. 2billion的unique的时间序列id,以string表示;
    2. 每秒700million的data points(timestamp加上value)写入;
    3. 保存数据26小时;
    4. 超过40k的QPS;
    5. 读成功在1ms以下;
    6. 支持15s的时间粒度;
    7. 两个用于灾难恢复的不一致的内存副本;
    8. 单服务器故障时也能保证读取;
    9. 可以快速扫描所有的内存数据;
    10. 可以支持每年至少增长2x;

现有的OpenTSDB、InfluxDB、Whisper都不能满足这些要求;

架构

数据保存方式

Gorilla中数据的基本单元时一个Timestamp+value的组合,其中,Timstamp时一个654bit的整数,value是一个double类型的浮点数,一个这样基本单元的stream称为data stream。这个的一连串的数据被压缩保存,称为一个block,block存为一个header加上后面被压缩的数据。

时间戳压缩

根据Gorilla论文的描述,16bytes的数据被压缩到1.37bytes,压缩了约12倍。其中,对于64bit的时间戳使用的压缩方法是delta-of-delta的方式,基本的原理如下:Gorilla不会保存整个世界戳,因为时间戳大部分的bit位都是相同。举个例子:如果一个时间戳后面时间的差值分别为60,60,59和61,delta-of-delta通过减去前一个时间戳来计算,这样我们得到了0,-1,2。具体算法描述如下:

  1. Block的header保存了时间戳t-1(t负1), 它对齐到两个窗口,t0时间戳保存一个14bit的对于t-1的增量。
  2. 对于序列之后的时间戳:
    • 计算the delta of delta:D = (tn −tn−1)−(tn−1 −tn−2);
    • 如果D为0,则存储单个“0”bit;
    • 如果D在[-63,64]之间,则存储’10’后跟值(7位);
    • 如果D在[-255,256]之间,则存储’110’后面跟着值(9位);
    • 如果D在[-2047,2048]之间,则存储’1110’后跟值(12位);
    • 否则使用32位存储’1111’,后跟D。

在实际的使用中发现96%可以背压缩位单个bit(很显然呀,这么大的QPS,必然很多相邻的时间戳是一样的)。

数据压缩

除了数据压缩,对于value也使用了压缩,基于相邻的数据变化不大的特点,主要使用的方法是基于XOR的方法。方法如下描述:1. 第一个值是无压缩存储的,2. 如果XOR与前一个值为零(相同值),则存储单个“0”bit,3. 当XOR不为零时,计算XOR中开头和结尾0的数量:(Control bit ‘0’) 如果有意义的位的块落在先前有意义的位的块内,即至少与前一个值一样多的前导0和多个尾随0,就使用该信息作为 块位置,并且只存储有意义的异或值; (Control bit ‘1’) 否则,用5bit前导零数的长度,然后将有意义的异或值的长度存储在接下来的6bit中,最后存储XOR后值的有意义的bit。

实际的数据中,大约51%的值被压缩到一个位,因为当前值和以前的值很多是相同的。大约30%的值用控制位’10’压缩,平均压缩大小为26.6位。剩余的19%被压缩为控制位’11’,平均大小为36.9位,这是由于编码前导零位和有意义位的长度需要额外的13位开销。

内存中的数据结构

Gorilla实现的主要数据结构是一个Timeseries Map(TSmap)。TSmap由时间序列的C++标准库vector<unique_ptr>,和从时间序列名称到的案例保存map组成。该矢量允许通过所有数据进行有效的分页扫描。 使用C++ unqiue_ptr可以在几微秒内复制向量,从而避免影响输入数据流的冗长的关键部分。在删除时间序列时,只标记为‘dead’,但是不会真的删除保存的数据。通过SpnLock的高效实用和分片,以及map有效使用,高效的实现了这个结构。

磁盘上的结构

Gorilla的一个设计目标就是在单机的故障的下能不影响使用,所以,Gorilla将数据保存在有3个副本的GlusterFS中。 将数据保存在HDFS或其他分布式文件系统也很简单。Gorilla还考虑了单个主机数据库,如MySQL和RocksDB,但是最终没有使用,因为Gorilla不需要数据库查询语言。 一个Gorilla Host拥有多个分片数据,每个分片维护一个目录。每个目录包含四种类型的文件:key列表,追加日志,完整的块文件和检查点文件。 key列表只是时间序列字符串键到整数ID的简单映射。该整数ID是内存中vector的索引。新keys将附加到当前的密钥列表中,并且Gorilla会定期扫描每个分片的所有keys,以重新写入该文件。数据被流式传输到Gorilla,它们被存储在日志文件中。使用4.1节中描述的格式压缩时间戳和值。但是,每个分片只有一个追加日志,因此分片中的值会跨越时间序列交错,这个增加了存储的开销。Gorilla不会提供ACID保证,因此日志文件不是预写日志。在flush之前,数据通常包含一到两秒钟的数据,最多可达64kB,所以崩溃可能导致少量数据的丢失。 每两小时,Gorilla将压缩的数据写到磁盘,因为经过了压缩,所以这个比日志文件小得多。这个块文件有两个部分:一组连续64kB的数据块,和一个<time serics ID, data block pointer>的列表。 当一个块文件完成后,Gorilla会更新检查点文件并删除相应的日志。 检查点文件用于标记何时将完整的块文件写入到磁盘。如果在进程崩溃时块文件未成功刷新到磁盘,则当新进程启动时,这个检查点将不存在,因此新进程知道它不能信任该块文件,而应该从日志文件中读取。

错误处理

// TODO

参考

  1. Gorilla: A Fast, Scalable, In-Memory Time Series Database, VLDB ‘15.
  2. https://github.com/facebookincubator/beringei