Prometheus/TSDB · 标签匹配与 postings 迭代器

按标签倒排求交,缩小需要读取的时间序列

Prometheus 为标签值维护有序序列引用列表;多个标签条件通过推进 postings 迭代器求交,只把同时满足条件的序列交给后续读取。

v3.0.0检索与计算核验 2026-10-12
相关概念

工程问题#

查询如 {job="api", instance="node-1"} 时,逐条扫描全部时间序列并检查标签,会在高基数库中浪费大量工作。标签筛选需要尽早缩小候选集,同时避免为每个条件及中间交集都复制一份大型结果数组。

实际实现#

PostingsForMatchers 为相等条件取出对应的 postings,把正向条件交给 index.Intersect。交集迭代器维护当前候选引用 cur,让每个输入 Seek 到不小于 cur 的位置;如果某个输入跳到更大的引用,就提高 cur 并从头对齐,直到所有输入同时停在同一引用或某路耗尽。ListPostings 的 Seek 会在未消费区间二分定位,因此稀疏列表可跳过大段不可能匹配的引用。否定及可匹配空值的条件还需要差集与缺失标签语义,不能一概当成交集。

处理流程#

  1. 把每个正向标签条件解析为按序列引用有序的 postings
  2. 建立交集迭代器,推进各输入并选择当前最大引用作为候选
  3. 让每路 Seek 到候选;遇到更大引用就抬高候选并重新对齐
  4. 所有输入指向同一引用时输出一个匹配,任一路耗尽则结束
  5. 按匹配器语义应用必要的差集,随后才进入序列与样本读取

源码片段#

固定版本 · 原文摘录
tsdb/querier.gov3.0.0 · L328–L345
查看原文件
328func postingsForMatcher(ctx context.Context, ix IndexReader, m *labels.Matcher) (index.Postings, error) {329	// This method will not return postings for missing labels.330331	// Fast-path for equal matching.332	if m.Type == labels.MatchEqual {333		return ix.Postings(ctx, m.Name, m.Value)334	}335336	// Fast-path for set matching.337	if m.Type == labels.MatchRegexp {338		setMatches := m.SetMatches()339		if len(setMatches) > 0 {340			return ix.Postings(ctx, m.Name, setMatches...)341		}342	}343344	it := ix.PostingsForLabelMatching(ctx, m.Name, m.Matches)345	return it, it.Err()
postingsForMatcher · 相等条件走倒排入口

相等条件直接使用标签名与值取得 postings;正则集合匹配和一般匹配走另外的路径。

tsdb/querier.gov3.0.0 · L319–L326
查看原文件
319	it := index.Intersect(its...)320321	for _, n := range notIts {322		it = index.Without(it, n)323	}324325	return it, nil326}
PostingsForMatchers · 求交与差集

正向集合先求交,notIts 再逐个相减。完整函数还处理缺失标签和可匹配空字符串的条件,不能将 != 简化为直接查询另一个标签值。

tsdb/index/postings.gov3.0.0 · L535–L549
查看原文件
535func (it *intersectPostings) doNext() bool {536Loop:537	for {538		for _, p := range it.arr {539			if !p.Seek(it.cur) {540				return false541			}542			if p.At() > it.cur {543				it.cur = p.At()544				continue Loop545			}546		}547		return true548	}549}
intersectPostings.doNext · 对齐候选

任一路超过当前引用,就抬高候选并重新检查所有输入;只有每路都停在同一引用时才返回一个交集元素。

tsdb/index/postings.gov3.0.0 · L551–L565
查看原文件
551func (it *intersectPostings) Next() bool {552	for _, p := range it.arr {553		if !p.Next() {554			return false555		}556		if p.At() > it.cur {557			it.cur = p.At()558		}559	}560	return it.doNext()561}562563func (it *intersectPostings) Seek(id storage.SeriesRef) bool {564	it.cur = id565	return it.doNext()
intersectPostings.Next / Seek · 推进输入

Next 先推进各路并选择当前最大引用,再交给 doNext 对齐;外层 Seek 也复用相同对齐机制。

tsdb/index/postings.gov3.0.0 · L757–L775
查看原文件
757func (it *ListPostings) Seek(x storage.SeriesRef) bool {758	// If the current value satisfies, then return.759	if it.cur >= x {760		return true761	}762	if len(it.list) == 0 {763		return false764	}765766	// Do binary search between current position and end.767	i, _ := slices.BinarySearch(it.list, x)768	if i < len(it.list) {769		it.cur = it.list[i]770		it.list = it.list[i+1:]771		return true772	}773	it.list = nil774	return false775}
ListPostings.Seek · 二分定位剩余区间

已达到目标时直接返回;否则在尚未消费的有序切片中二分搜索,再把迭代位置移到命中位置之后。

五段原文连接标签查询入口、交集构建、候选对齐和底层二分 Seek;多种 postings 的具体 Seek 成本可能不同。

收益与取舍#

工程分析

带来的收益

  • 用索引引用完成标签筛选,减少无关序列的解码与样本读取
  • 交集按需输出,不先物化全部中间交集;交集包装层只保留 O(k) 个输入迭代器和一个当前引用
  • Seek 可利用底层有序存储跳跃,稀疏条件不必逐个扫描较长列表的全部引用

付出的代价

  • 性能取决于列表长度、重叠程度、匹配器数量和底层 Seek 实现;不能把整个多路交集概括成一次 O(log N) 二分查找
  • ListPostings 单次有效 Seek 在剩余 r 个引用中为 O(log r),但每次候选上升可能让多路重新检查;底层索引读取和结果遍历成本另计
  • 倒排索引会占用空间并随新序列维护;正则条件、否定条件和空标签匹配可能扩大候选,不保证所有查询都很便宜

可比较的选择

扫描所有序列标签不需要为每个条件组织 postings,但查询代价随全库序列数增长,通常无法利用选择性强的标签。

将一个列表建哈希集合再过滤其他列表可用期望常数时间判断成员,但需要额外集合内存,也无法直接利用现有有序 Seek 跳过大段区间。

版本与适用范围#

固定 Prometheus v3.0.0,重点分析多个正向、非空相等标签条件的交集。输入是有序的序列引用,不是按采样时间排列的样本;这里的二分搜索定位序列 ID,不能误写为时间范围查找。空值与缺失标签、正则、否定条件的完整行为见 PostingsForMatchers。

参考来源#

源码、官方文档与原始论文
01
prometheus · postingsForMatcher · 相等条件走倒排入口

tsdb/querier.go · postingsForMatcher · 相等条件走倒排入口

源码v3.0.0
02
prometheus · PostingsForMatchers · 求交与差集

tsdb/querier.go · PostingsForMatchers · 求交与差集

源码v3.0.0
03
prometheus · intersectPostings.doNext · 对齐候选

tsdb/index/postings.go · intersectPostings.doNext · 对齐候选

源码v3.0.0
04
prometheus · intersectPostings.Next / Seek · 推进输入

tsdb/index/postings.go · intersectPostings.Next / Seek · 推进输入

源码v3.0.0
05
prometheus · ListPostings.Seek · 二分定位剩余区间

tsdb/index/postings.go · ListPostings.Seek · 二分定位剩余区间

源码v3.0.0
06
prometheus · PostingsForMatchers · 空值、否定和缺失标签语义

tsdb/querier.go · PostingsForMatchers · 空值、否定和缺失标签语义

源码v3.0.0
07
prometheus · Intersect · 特殊情况与迭代器构造

tsdb/index/postings.go · Intersect · 特殊情况与迭代器构造

源码v3.0.0
08
prometheus · bigEndianPostings.Seek · 编码列表上的二分

tsdb/index/postings.go · bigEndianPostings.Seek · 编码列表上的二分

源码v3.0.0

相关实现与比较#

4 个相关案例
19 个匹配案例