压缩篇:delta-of-delta编码

4,266 阅读4分钟

前言

本文主要讨论时序数据库中常见的一种时间戳或者数值压缩方法:delta-of-delta 算法,可以极大地降低数据存储的成本和提高数据写入、查询的性能。

delta-of-delta 压缩时间戳是 Facebook Gorilla 论文中所提到的,论文地址:www.vldb.org/pvldb/vol8/… Prometheus TSDB 项目也是借鉴了 Facebook Gorilla 论文中的思路,可以实现很高的时序数据压缩率。

delta 时间戳压缩

时间戳一般采用 long 类型进行存储,需要占用 8byte 存储空间。最直接的优化就是存储时间戳的差值,这里需要起始时间戳和 delta 的最大范围阈值。有两种常用的实现思路:

  • 存储相邻两个时间戳差值 Delta(n) = T(n) - T(n-1)
Unix时间戳 Delta
1571889600000 0
1571889600010 10
1571889600025 15
1571889600030 5
1571889600040 10
  • 存储与起始时间戳的差值 Delta(n) = T(n) - T(0)
Unix时间戳 Delta
1571889600000 0
1571889600010 10
1571889600025 25
1571889600030 30
1571889600040 40

假设起始时间戳为 1571889600000,delta 的最大范围阈值为 3600s,每个 delta 的数值需要 13bit 可以存储。因此以上时间戳数据共占用空间为 64 + 13 * 4 = 116bit。

思路 2 的优势是不需要对块内数据依次遍历,但是相比思路 1 可能需要更为频繁地更换起始时间,根据实际需求选择合适的压缩方案。

delta-of-delta 时间戳压缩

Facebook Gorilla 有详细阐述 delta-of-delta 编码的计算方式,以下为论文的摘录。

image

针对不同时间跨度的数据,Facebook Gorilla 给出了一种较为通用的处理方案。

D 标识位 占用总bits
0 0 1
[-63,64] 10 2 + 7 = 9
[-255,256] 110 3 + 9 = 12
[-2047,2048] 1110 4 + 12 = 16
> 2048 1111 4 + 32 = 36

依然通过一组时间戳数据来直观感受下 delta-of-delta 编码的压缩效果:

Unix时间戳 delta delta-of-delta 压缩后总bits
1571889600000 0 0 --
1571889600010 10 10 9
1571889600010 0 -10 9
1571889600011 1 1 9
1571889600012 1 0 1
1571889600013 1 0 1
1571889600015 2 1 9
1571889600017 2 0 1

依然假设起始时间戳为 1571889600000,delta 的最大范围阈值为 3600s,占用存储空间对比如下:

  • delta 算法: 64 + 13 * 7 = 155bit 。
  • delta-of-delta 算法: 64 + 9 * 4 + 1 * 3 = 103bit 。

可以看出 delta-of-delta 算法相比 delta 算法进一步获得了更高的压缩率。在实际应用场景中,海量时序数据的时间戳都是密集且连续的,绝大部分都满足 delta-of-delta=0 的条件,这样可以大幅度降低时间戳的存储空间。

总结

  • delta-of-delta 算法常用于监控数据中时间戳的压缩,可以大幅度降低存储成本和提高写入、查询性能。
  • 针对跨度较大的数据,系统需要有一定的容错能力。
  • delta-of-delta 算法也存在一定的缺陷,因为是不定长的压缩算法,所以导致解压后必须从数据块的首地址依次计算。

附录

转载请注明出处,欢迎关注我的公众号:亚普的技术轮子

亚普的技术轮子