监控系统的时序流有两个朴素直觉:采样间隔几乎恒定,相邻浮点值几乎相同。通用压缩(gzip/zstd)把每条记录当独立字节处理,既看不出"间隔没变",也看不出"数值只动了几位"。Gorilla 把这两个直觉做成了两套位级编码器,把 16 字节的时间戳+浮点对压到常常不足 2 字节。这是 Facebook 2015 年论文里那套至今仍在 Prometheus TSDB、InfluxDB、VictoriaMetrics 中延续的设计。

本篇从零拆解这套编码:时间戳走 Delta-of-Delta 的四档控制位,浮点值走 XOR 位模式 + 前后导零窗口复用。文末给出一份本地实跑通过(6 组测试、含 NaN/±0/随机 double)的 Python 教学实现,以及它与字典编码、FSST、数据跳过这三篇姊妹文构成的知识链。

一、时序数据为什么需要专属压缩

一条监控样本通常是 (timestamp:int64, value:float64),16 字节。假设一个采集器每秒采一次、跑一年,单序列就是 5 亿字节。但这类数据有三个结构性冗余,通用压缩都吃不到:

  • 时间间隔高度规律:绝大多数相邻采样的 delta = t[n]-t[n-1] 完全相等(都是 1000ms),偶有抖动也只是小幅偏移。
  • 数值变化极小:CPU 使用率从 41.23 变到 41.24,两个 double 的 IEEE-754 位模式只有最低几位不同,高位一片相同。
  • 随机访问要求:监控查询常只读某时间窗,压缩块必须能快速定位和局部解压,不能像 gzip 那样做跨流的大字典。

通用压缩以字节为最小单位,无法表达"这个 64 位整数只变了 2"。Gorilla 的核心是把冗余定义在位(bit)这一层,而不是字节层。

二、整体设计:时间流与值流分离

Gorilla 不把时间戳和值交错存储,而是分成两条独立比特流,各自采用最贴合自身冗余的编码:

流冗余来源编码方法典型位宽
时间戳流间隔规律Delta-of-Delta + 分档变长1 / 9 / 15 / 35 bit
浮点值流位模式相近XOR + 前后导零窗口复用1 / 13 / 20+ bit

首条记录是"锚点":时间戳原样存 64 位,浮点值原样存 64 位。从第二条起,两条流都只记录"相对上一条的变化",而且变化越小、占用比特越少。这正是一个针对单调有序流的增量编码(delta encoding)家族。

三、时间戳编码:Delta-of-Delta 与四档控制位

直接存 delta 还不够省。规律采样下 delta 恒为 1000,一阶差分已经是个常数;再做一次差分 dod = delta[n] - delta[n-1](Delta-of-Delta,二阶差分),规律采样时 dod = 0,只需 1 个比特。Gorilla 用控制位前缀标注 dod 落在哪一档:

控制位dod 范围载荷总位数场景
0= 0无1间隔完全没变(绝大多数)
10[-63, 64]7 bit (dod+63)9轻微抖动
110[-256, 255]12 bit (dod+256)15中等间隔变化
111其余 int3232 bit 补码35丢点、大间隔兜底

这里有个极易踩坑的 off-by-one:7 bit 要容纳 [-63, 64] 共 128 个值,偏移必须是 +63(-63→0,64→127);若写成 +64,dod=64 会得到 128 溢出 7 bit,解码时静默出错。12 bit 档同理用 +256 偏移覆盖 [-256, 255]。32 bit 档存的是补码,解码需判断符号位并还原负数。

下面是时间戳流的编码核心(教学版,省略了位写入器细节):

def enc_ts(ts):
    w = BitWriter()
    if not ts:
        return w.to_bytes()
    w.write(ts[0], 64)                 # 首值原样存(锚点)
    prev, prev_delta = ts[0], 0
    for t in ts[1:]:
        delta = t - prev
        dod = delta - prev_delta       # 二阶差分
        if dod == 0:
            w.write(0b0, 1)            # '0'
        elif -63 <= dod <= 64:
            w.write(0b10, 2)
            w.write(dod + 63, 7)       # 7bit 偏移 63
        elif -256 <= dod <= 255:
            w.write(0b110, 3)
            w.write(dod + 256, 12)     # 12bit 偏移 256
        else:
            w.write(0b111, 3)
            w.write(dod & 0xFFFFFFFF, 32)  # 补码兜底
        prev, prev_delta = t, delta
    return w.to_bytes()

解码是严格的逆过程:delta = prev_delta + dod,t = prev + delta,每步同步更新 prev 与 prev_delta。位流中不含长度信息,实际系统按块记录样本数;教学实现把 count 作为参数传入解码器。

四、浮点值编码:XOR 位模式与有效位提取

浮点值的冗余来自 IEEE-754 的位布局。把 double 按位 reinterpret 成 uint64,当前值与上一值做 XOR:

  • XOR 结果全 0:值完全没变,只写 1 个控制位 0。
  • XOR 非 0:先写控制位 1,再找出这段差异位串——前导零个数 lz(高位连续 0)和尾随零个数 tz(低位连续 0)。夹在中间的 mb = 64 - lz - tz 位叫有效位(meaningful bits),只需存这一段。

例如 41.23 与 41.24 的 double 位模式,高位符号位和指数位完全相同,有效位可能只落在最低 20 位以内。存 20 位 + 少量元信息,远胜存完整 64 位。

def enc_vals(vals):
    w = BitWriter()
    prev_u = f2u(vals[0])
    w.write(prev_u, 64)                # 首值原样存
    prev_lz = prev_tz = None
    for v in vals[1:]:
        x = f2u(v) ^ prev_u            # 位模式异或
        if x == 0:
            w.write(0, 1)              # 值未变:仅 1 bit
        else:
            w.write(1, 1)
            lz = 64 - x.bit_length()
            tz = (x & -x).bit_length() - 1  # 最低置位之后的零个数
            mb = 64 - lz - tz
            if prev_lz is not None and lz >= prev_lz and tz >= prev_tz:
                w.write(0, 1)          # 命中上一窗口:复用 lz/tz
                w.write(x >> prev_tz, 64 - prev_lz - prev_tz)
            else:
                w.write(1, 1)          # 新窗口:显式写元信息
                w.write(lz, 6)         # 6bit 覆盖 double 的 0..63
                w.write(mb - 1, 6)     # mb-1 适配 6bit
                w.write(x >> tz, mb)
                prev_lz, prev_tz = lz, tz
        prev_u = f2u(v)
    return w.to_bytes()

五、窗口复用:第二层控制位

如果每次非 0 变化都写 6 位 lz + 6 位 mb,开销仍偏高。Gorilla 观察到:相邻样本的变化区间往往稳定在同一位置(比如温度总是在小数部分第 8~15 位抖动)。于是加了第二层控制位:

  • 若本次的 lz >= 上一窗口lz 且 tz >= 上一窗口tz,说明有效位完全落在上次的窗口内,写 0 + 复用窗口截取的有效位即可,省掉 12 位元信息。
  • 否则写 1 + 新的 lz(6bit) + mb-1(6bit) + 有效位,并更新窗口。

解码端对称:读到复用标志就从 prev_lz/prev_tz 恢复窗口,按 u = prev_u XOR (有效位 << tz) 还原。这里用 6 bit 存 lz(而非论文针对 32 位 float 的 5 bit)是为了完整覆盖 double 的 0..63 前导零范围——这是把论文方法移植到 64 位时的必要调整。

六、完整实现与自测

把两条流装进一个 BitWriter/BitReader 框架,配合一组覆盖规律的测试,就是完整实现。位写入器逐位追加、按字节对齐补零,位读取器则反向展开:

class BitWriter:
    def __init__(self):
        self.bits = []
    def write(self, val, n):           # 高位优先写 n 位
        for i in range(n - 1, -1, -1):
            self.bits.append((val >> i) & 1)
    def to_bytes(self):                # 尾部补零对齐到字节
        out = bytearray()
        for i in range(0, len(self.bits), 8):
            chunk = self.bits[i:i + 8]
            b = 0
            for bit in chunk:
                b = (b << 1) | bit
            out.append(b << (8 - len(chunk)))
        return bytes(out)

def f2u(f):  # double 按位 reinterpret 为 uint64
    return struct.unpack('<Q', struct.pack('<d', f))[0]
def u2f(u):
    return struct.unpack('<d', struct.pack('<Q', u))[0]

本地实跑的自测输出(6 组测试全部通过,含 NaN、±inf、±0、随机 double 的位级无损验证):

T1 时间戳往返 OK:201 点 1608B -> 177B,压缩率 0.110
T2 浮点往返 OK:103 点 824B -> 334B,压缩率 0.405
T3 相同值 1bit 编码 OK:100 个相同 double -> 21B (理论 ceil(163/8)=21B)
T4 前后导零窗口复用往返 OK
T5 空/单点/NaN/inf/±0 边界 OK(位级无损)
T6 随机 double 往返 OK:100 点无损
ALL TESTS PASSED

七、实测压缩率与边界行为

把时间戳流和值流合起来看,规律采样的压缩收益极其可观:

数据原始(double)Gorilla 编码压缩率
201 点规律时间戳1608 B177 B0.110(省 89%)
103 点缓慢变化浮点824 B334 B0.405(省 60%)
100 点完全相同的 double800 B21 B0.026(省 97%)

压缩率与数据的"可预测性"强相关:值越稳定、间隔越规律,收益越大。两个边界值得注意:

  • 随机数据会膨胀:完全随机的 double 之间 XOR 位串分散,lz/tz 都小,有效位接近 64,加上元信息反而比原始 8 字节略大。所以 Gorilla 只适合数值连续、缓变的时序流,不适合高熵数据。
  • NaN / ±0 的位级无损:XOR 操作在 uint64 位模式上进行,不做数值比较,因此 NaN 的 payload、+0.0 与 -0.0 的符号位都原样保留——这是用位模式而非数值相等判断的优势。

八、工程落地与常见陷阱

Gorilla 原始论文用 32 位 float + 5 bit lz,移植到现代 double 时序库时有几处必须调整:

  • lz 位宽:double 前导零可达 63,5 bit 不够,需扩到 6 bit;mb-1 也用 6 bit 覆盖 1..64。
  • 32 bit 补码符号还原:dod 兜底档存的是补码,解码要判断最高位并减 2^32,否则大负数间隔会解成错误正数。
  • 块边界重置锚点:每条流每块(如 2 小时或固定样本数)存一个完整首值锚点,块内增量编码。这既限制了错误传播,也支持按块随机访问与并行解压——Prometheus TSDB 的 chunk、VictoriaMetrics 的块编码都沿用这一思路。
  • 与 XOR Filter 区分:本站另有一篇《Xor Filter 与 Ribbon Filter》,虽都含"XOR",但那是近似成员查询的概率结构,与此处"用 XOR 求差分以压缩浮点"完全无关,勿混淆。

九、知识链:与字典编码、FSST、数据跳过的关系

本站"列式压缩"系列已从三个层次切入,本篇补上时序浮点这一支:

  • 字典编码(整值级):把重复字符串映射成字典 ID,适合低基数。
  • FSST(字节子串级):学习字节符号表,把字符串拆成短symbol,攻高基数字符串。
  • 数据跳过(块级剪枝):Zone Map / Bloom 在查询前跳过整块,属压缩之外的剪枝侧。
  • Gorilla(位级 + 时序):利用采样的时间规律与数值连续,逐位编码——与前三者的冗余维度都不同。

四者合起来,覆盖了"整值 → 字节 → 位 → 查询剪枝"的列式优化全景。下一篇可继续补 Frame-of-Reference + bit-packing(整数列的中心化+位打包),把整数压缩这一环也补齐。

结语

Gorilla 的优雅之处在于它不做通用压缩,而是把时序数据的两条物理直觉——"间隔几乎不变"和"数值只动几位"——直接翻译成两套位级编码器。Delta-of-Delta 把时间维压到接近 1 bit/点,XOR + 前后导零窗口把浮点维压到十几 bit/点。理解它,就理解了现代时序数据库为什么能在单位磁盘上塞进几十亿个采样点。真正需要留意的,是论文 32 位假设迁移到 double 时的位宽调整、补码符号还原,以及"随机数据反而膨胀"这条适用边界。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论
立即
投稿

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部