Prometheus TSDB 源码解析:bstream 位流与 delta-of-delta 时间戳编码的实现原理

本文以 Prometheus 仓库中的 bstream.md 文档为核心,深入讲解 TSDB 样本压缩的底层位流(bitstream)机制:包括 bstream/bstreamReader 的读写实现、delta-of-delta(dod)时间戳编码中“前缀 + 有效位”的变长编码方案,以及负数在 uint64 容器下如何被正确解码。读完本文,你将能够对照 tsdb/chunkenc/bstream.go、tsdb/chunkenc/varbit.go 与 tsdb/chunkenc/xor.go 读懂 Prometheus 磁盘上时间序列样本的比特级布局。

bstream 在 TSDB 中的定位

TSDB 中的每个数据块(chunk)并不直接存储裸的“时间戳 + 浮点值”,而是使用 XOR 编码对二者分别做差分/异或压缩。整个压缩体系都构建在一个比特级的读写层之上,即 tsdb/chunkenc/bstream.go 中的两个类型:

• bstream:写入端。它把比特流追加到一个 []byte 缓冲中,count 字段记录当前最后一个字节中还可写入的最低侧比特数。文档说明该代码主要基于 Damian Gryski 的 go-tsz 实现改写而来(文件头部的版权注释保留了原始出处);
• bstreamReader:读取端。它内部维护一个最多 8 字节的 uint64 位缓冲,支持逐位或整段地按大端序读回比特。

文档 bstream.md 自己也声明了定位与局限:“This doc describes details of the bstream (bitstream) and how we use it for encoding and decoding. This doc is incomplete”,并建议读者结合 Gorilla TSDB 的 VLDB 白皮书及 go-tsz 原始实现来理解背景。下文的讲解正是在该文档骨架上,用仓库源码把每个论点落到实处。

上层使用方包括:

• XOR 浮点块:tsdb/chunkenc/xor.go 中的 XORChunk/xorAppender/xorIterator;
• 变长整型编码:tsdb/chunkenc/varbit.go 中的 putVarbitInt/readVarbitInt(用于直方图等样本的时间戳增量);
• XOR2 新编码:tsdb/chunkenc/xor2.go 中的 XOR2Chunk,以及 bstream 上专门为其增加的 writeBitsFast、readXOR2Control、readVarint 等热路径优化函数。

Delta-of-delta 编码:为什么需要支持正、零、负

对于时间戳,第一个样本直接以 varint 写入,第二个样本写入“与第一个的时间差(tDelta)”,从第三个样本开始,写入的是时间差的差,即 dod(delta-of-delta)。在采集间隔稳定的最常见情况下,dod 恒为 0,只需 1 个比特;但 dod 可能为正、零或负(例如采集间隔抖动),因此编码方案必须对称地覆盖正负区间。文档原文:“We need to be able to encode and decode dod's for timestamps, which can be positive, zero, or negative.”

文档给出了 int64 的二进制补码(2's complement)示意,帮助理解“有效位”与“符号前缀”的关系:

0111...111 = maxint64
    ...
0000...111 = 7
0000...110 = 6
0000...101 = 5
0000...100 = 4
0000...011 = 3
0000...010 = 2
0000...001 = 1
0000...000 = 0
1111...111 = -1
1111...110 = -2
1111...101 = -3
1111...100 = -4
1111...011 = -5
1111...010 = -6
1111...001 = -7
1111...000 = -8
    ...
1000...001 = minint64+1
1000...000 = minint64

规律是:每个数都由一个符号前缀(正数为 0、负数为 1)加上一串尾部的有效位构成,且绝对值越小,有效位越少。

编码方案:前缀 + “比有效位多 1 位”的数据段

文档给出的编码结构由两部分组成:

1. 前缀(prefix):声明后续跟随多少比特。前缀采用一个按“有效位数量递增”排列的预定义选项列表;
2. 数据段:比“有效位数量”多 1 位的比特。多出的这 1 位并不是严格意义的符号位,而是因为底层操作的是无符号整数(uint64)容器,需要额外 1 位来区分正负区间。

bitRange 函数负责判断某个整数能否用给定位数表示。其源码定义在 xor.go:

// bitRange returns whether the given integer can be represented by nbits.
// See docs/bstream.md.
func bitRange(x int64, nbits uint8) bool {
	return -((1<<(nbits-1))-1) <= x && x <= 1<<(nbits-1)
}

注意函数注释直接指向 docs/bstream.md,说明这段实现就是文档所述方案的落点。按文档的推导:对 nbits 个比特,可以区分并编码任意 2^nbits 个数,边界可以自由选择(如 -4~3、-3~4、0~7 甚至 -2~5,均含端点)。由于需要同等地支持正负数,边界被选为对称生长:以 nbits = 3 为例,选择区间为 -3 ~ 4,而不是 -4 ~ 3。对照 bitRange(x, 3) 的实现,即 -((1<<2)-1) <= x && x <= (1<<2),恰好是 -3 <= x <= 4,与文档完全一致。

解码时的关键:负数如何从 uint64 容器中还原

文档强调了 bstream 的一个特性:位流库本身不解释整数的具体类型,读出来的只是 uint64——它只是 64 个比特的容器。在我们选定的区间内,按无符号整数看,区间的上半部分代表负数。

沿用 nbits = 3 的例子:比特串 001、010、011、100 被读回为无符号数 1、2、3、4,转成 int64 后含义相同;而 101、110、111 读回为无符号数 5、6、7,实际却代表 -3、-2、-1。还原规则是:

• cutoff 值 = 第 nbit 位所能表示的数(3 比特的例子中第 3 位 = 4);
• 需要减去的值 = 第 nbit+1 位所能表示的数(例子中第 4 位 = 8);
• 因此只要无符号值超过 4(即 5、6、7),就减去 8,得到 -3、-2、-1。

这条规则在仓库源码中出现为同一个“回绕减一整个区间长度”的写法。XOR 迭代器解码 dod 时,见 xor.go:

if sz != 0 {
    bits, err := it.br.readBitsFast(sz)
    ...
    // Account for negative numbers, which come back as high unsigned numbers.
    // See docs/bstream.md.
    if bits > (1 << (sz - 1)) {
        bits -= 1 << sz
    }
    dod = int64(bits)
}

这里 1 << (sz-1) 即 cutoff 值,1 << sz 即需减去的“多出的那 1 位”对应的权重,与文档描述的 3 比特例子(4 与 8)同构。变长整型解码器 varbit.go 的 readVarbitInt 采用完全相同的写法:

if sz != 0 {
    bits, err := b.readBitsFast(sz)
    ...
    if bits > (1 << (sz - 1)) {
        // Or something.
        bits -= (1 << sz)
    }
    val = int64(bits)
}

文档结尾还留了一个值得玩味的观察:如果把边界整体下移一位(nbits = 3 时变为 -4 ~ 3),最高位就会恰好指示符号(隐含所需前缀);但当前方案同样工作正常。这一节体现了设计者在“理论优雅”与“实现现状”之间的诚实记录。

写入端:bstream 的三个核心写函数

bstream 的写入模型见 bstream.go:

// bstream is a stream of bits.
type bstream struct {
	stream []byte // The data stream.
	count  uint8  // How many right-most bits are available for writing in the current byte (the last byte of the stream).
}

• writeBit:当 count == 0 时追加一个新字节并把 count 置 8,然后在最后字节上按 1 << (count-1) 置位,count 递减。这是最细粒度的写入;
• writeByte:整字节写入。若当前字节尚有 count 个空位,先用新字节的左移部分补满最后字节,再把剩余部分作为新字节追加,从而保持比特级对齐不丢;
• writeBits(u, nbits):把 u 的最低 nbits 位按从左到右的顺序写入。实现先 u <<= 64 - nbits 把目标段顶到高位,然后尽量按整字节循环调用 writeByte,不足 8 位的尾巴逐位调用 writeBit。

仓库还在同一文件中提供了 writeBitsFast(bstream.go):它把“补满末字节 + 整字节直写 + 尾部残位”合并成一段内联逻辑,避免逐字节的函数调用开销,并带有 TODO 说明:“Once XOR2 stabilizes, replace writeBits with the writeBitsFast implementation”。对应的 putVarbitIntFast(varbit.go)则进一步把“前缀 + 数据段”打包成单次 writeBitsFast 调用,例如 3 比特档直接写 (0b10<<3)|(uval&0x7) 共 5 位。

读取端:bstreamReader 的 8 字节缓冲与快慢路径

读取端 bstreamReader 的设计目标是减少函数调用与内存访问,核心字段(bstream.go):

• buffer uint64:当前缓冲,从流中填充,最多含 8 字节;
• valid uint8:缓冲中还可读取的比特数(从左往右数);
• last byte:流的最后一个字节的副本,用于规避并发写竞争——注释明确说明,流末尾的字节可能正被另一个 goroutine 追加更新,因此读取器初始化时先拷贝一份,慢速路径触底时使用该副本。

读写方法成对出现“Fast/慢速”双通道,这是一个在 Prometheus 压缩层中反复出现的模式:

• readBitFast/readBitsFast:假设缓冲内已有足够比特,纯位运算取回数据,若不足则返回 io.EOF;
• readBit/readBits:Fast 失败时的兜底,会调用 loadNextBuffer 重新装填缓冲,readBits 还能跨越缓冲边界拼接两段比特。

调用方(如 xorIterator、readVarbitInt)统一遵循“先 Fast,失败再回退慢速”的写法。loadNextBuffer(bstream.go)则把最常见的“缓冲内还有超过 8 字节可读”情况优化为一次 binary.BigEndian.Uint64 拷贝;只有尾部不足 8 字节时才走逐字节拼装,并对最后一个字节使用 last 副本。

实战落点:varbit 的比特桶与 XOR 块的时间戳编码

putVarbitInt 是文档所述“前缀选项列表”最完整的实现,它按 dod 在直方图桶中实际观测到的分布划分比特桶(varbit.go):

前缀	前缀位数	数据段位数	覆盖范围	总比特数
0	1	0	val == 0	1
0b10	2	3	-3 ~ 4	5
0b110	3	6	-31 ~ 32	9
0b1110	4	9	-255 ~ 256	13
0b11110	5	12	-2047 ~ 2048	17
0b111110	6	18	-131071 ~ 131072	24
0b1111110	7	25	-16777215 ~ 16777216	32
0b11111110	8	56	-36028797018963967 ~ 36028797018963968	64
0b11111111	8	64	全 int64 兜底	72

每一档的数据段都恰好遵循 bitRange 的对称边界(如 6 比特档为 -31 ~ 32,即 -((1<<5)-1) ~ (1<<5)),前缀逐位加长,保证解码器可以按比特流逐位比对前缀后确定数据段宽度——readVarbitInt 正是先读出一个最长 8 位的 d 再对照 switch d 分支。

XOR 浮点块的时间戳编码也直接使用 bitRange 划分 dod 区间,见 xor.go 中 xorAppender.Append 的注释:“Gorilla has a max resolution of seconds, Prometheus milliseconds. Thus we use higher value range steps with larger bit size.” 即因为 Prometheus 时间戳是毫秒级,Gorilla 原方案中 14/17/20 比特的 dod 分桶需要整体上移。编码侧为 dod 选择 0、0b10(14 比特)、0b110(17 比特)、0b1110(20 比特)、0b1111(64 比特兜底)五档;解码侧(xorIterator.Next)则对最典型的 dod==0 情况提供了直接探测缓冲首比特的快路径,并顺带探测“值也未变化”的超级快路径,两次单比特判断即可跳过整个样本的解码。

从源码结构看,bstream 层还在向 XOR2 方向演进:文件内的 TODO、readXOR2Control(把六个编码情形压缩到 1~5 个控制比特)、readVarint/readUvarint(绕开 binary.ReadVarint 的接口分派以避免接收者逃逸到堆上)等注释,都说明该文档所述机制目前仍是 XOR、XOR2、直方图(st、histogram_meta)等全部变长编码共用的比特级地基。

测试佐证

tsdb/chunkenc/bstream_test.go 为这一层提供了直接的行为验证:

• TestBstream_Reset 验证 Reset 会丢弃旧流并把 count 归零;
• TestBstreamReader 是一个完整的回环测试:先写 1/0 两个单比特,再以 1~64 的每一种宽度 writeBits/readBits 各值,最后以 29 位宽度写入 1 到 10000 的序列并逐一读回比对,覆盖所有位宽边界;
• BenchmarkWriteBits 与 BenchmarkWriteBitsFast 在 1、8、17、32、52、64 位宽下对比新旧写入实现,与前述 writeBitsFast 的 TODO 计划相互印证。

小结

bstream.md 虽然篇幅不长且自述“incomplete”,但它精确刻画了 Prometheus TSDB 压缩体系的三个关键约定:补码视角下的“符号前缀 + 有效位”、bitRange 对称边界(如 3 比特档 -3 ~ 4),以及“读出 uint64 后按 cutoff 判断、超界则减去区间全长”的负数还原规则。这三个约定在 xor.go 的 bitRange、xor.go 与 varbit.go 的解码回绕逻辑、以及 bstream.go 的读写原语中都能逐一对上。理解这一层,是继续深入 XOR/XOR2/直方图编码乃至 TSDB 块格式(tsdb/docs/format/chunks.md)的前提。