Facebook Gorilla 时序数据压缩原理

/ 算法TSDB / 没有评论 / 950浏览
202031512839-golrilla-facebook

Facebook Gorilla 时序数据压缩原理

Gorilla源自Facebook对于内部基础设施的近乎”变态”的监控需求,我们先来看看这些数据:

对于监控数据,本身还具有如下几个典型特点:

Timestamp压缩(Delta-Of-Delta)

在大多数情形下,可以将一个Time Series中的连续的Data Points的Timestamp列表视作一个等差数列,这是Delta-Of-Delta编码算法的最适用场景。编码原理如下:

按照D的值所处的区间范围,分别有5种不同情形的处理:

  1. 如果D为0,那么,存储一个bit ‘0’
  2. 如果D位于区间[-63, 64],存储2个bits ’10’,后面跟着用7个bits表示的D值
  3. 如果D位于区间[-255, 256],存储3个bits ‘110’,后面跟着9个bits表示的D值
  4. 如果D位于区间[-2047, 2048],存储4个bits ‘1110’,后面跟着12个bits表示的D值
  5. 如果D位于其它区间则存储4个bits ‘1111’,后面跟着32个bits表示的D值

关于这些Range的选取,是出于个别Data Points可能会缺失的考虑。例如:

假设正常的Interval为每60秒产生一个Data Point,如果缺失一个Data Point,那么,相邻的两个Data Points之间的Delta值为:60, 60, 121 and 59,此时,Delta Of Delta值将变为: 0, 61, -62。

这恰好落在区间[-63, 64]之间。

如果缺失4个Data Point,那么,Delta Of Delta值将落在区间[-255, 256]之间。

下图针对Gorilla中的440,000条真实的Data Points采样数据,对Timestamp数据应用了Delta-Of-Delta编码之后的效果:

2020315114519-DeltaOfDelta-Mini

96.39%的Timestamps只需要占用一个Bit的空间,这样看来,压缩的效果非常明显。

Point Value压缩(XOR)

Gorilla中限制Point Value的类型为双精度浮点数,在未启用任何压缩编码的前提下,每个Point Value理应占用64个Bits。

同样,Facebook在认真调研了ODS中的数据特点以后也有了这样一个关键发现在大多数Time Series中,相邻的Data Points的Value变化比较轻微。这一点比较好理解,假设某一个Time Series关联某个仪器温度指标的监控,那么,温度的变化应该是渐进式的而非跳跃式的。XOR编码就是用来描述相邻两条Point Value的变化部分,下图直观描述了Point Value “24.0”与”12.0″的变化部分:

202031511477-XOR-EFFECT

XOR编码详细原理如下:

  1. 第一个 Value存储时不做任何压缩。
  2. 后面产生的每一个Value与前一个Value计算XOR值:
    • 如果XOR值为0,即两个Value相同,那么存为’0’,只占用一个bit。
    • 如果XOR为非0,首先计算XOR中位于前端的和后端的0的个数,即Leading Zeros与Trailing Zeros。
    • 第一个bit值存为’1’。
    • 如果Leading Zeros与Trailing Zeros与前一个XOR值相同,则第2个bit值存为’0’,而后,紧跟着去掉Leading Zeros与Trailing Zeros以后的有效XOR值部分。
    • 如果Leading Zeros与Trailing Zeros与前一个XOR值不同,则第2个bit值存为’1’,而后,紧跟着5个bits用来描述Leading Zeros的值,再用6个bits来描述有效XOR值的长度,最后再存储有效XOR值部分(这种情形下,至少产生了13个bits的冗余信息)

如下是针对Gorilla中1,600,000个Point Value采样数据采用了XOR压缩编码后的效果:

2020315115236-XOR-Mini

从结果来看:

另外,XOR压缩编码机制,对于Integer类型的Point Value效果尤为显著。

合理的Block大小

压缩算法通常都是基于Block进行的,Block越大,效果越明显。对于时序数据的压缩,则需要选择一个合理的时间窗大小的数据进行压缩。Facebook测试了不同的时间窗大小的压缩效果:

2020315115512-Compression-Timewindow

可以看出来,随着时间窗的逐步变大,压缩效果的确越显著。但超过2个小时(120 minutes)的时间窗大小以后,随着时间窗口的逐步变大,压缩效果的改善并不明显。时间窗口为2小时的每个Data Point平均只占用1.37 bytes

参考