按标签倒排求交,缩小需要读取的时间序列
Prometheus 为标签值维护有序序列引用列表;多个标签条件通过推进 postings 迭代器求交,只把同时满足条件的序列交给后续读取。
工程问题#
查询如 {job="api", instance="node-1"} 时,逐条扫描全部时间序列并检查标签,会在高基数库中浪费大量工作。标签筛选需要尽早缩小候选集,同时避免为每个条件及中间交集都复制一份大型结果数组。
实际实现#
PostingsForMatchers 为相等条件取出对应的 postings,把正向条件交给 index.Intersect。交集迭代器维护当前候选引用 cur,让每个输入 Seek 到不小于 cur 的位置;如果某个输入跳到更大的引用,就提高 cur 并从头对齐,直到所有输入同时停在同一引用或某路耗尽。ListPostings 的 Seek 会在未消费区间二分定位,因此稀疏列表可跳过大段不可能匹配的引用。否定及可匹配空值的条件还需要差集与缺失标签语义,不能一概当成交集。
处理流程#
- 把每个正向标签条件解析为按序列引用有序的 postings
- 建立交集迭代器,推进各输入并选择当前最大引用作为候选
- 让每路 Seek 到候选;遇到更大引用就抬高候选并重新对齐
- 所有输入指向同一引用时输出一个匹配,任一路耗尽则结束
- 按匹配器语义应用必要的差集,随后才进入序列与样本读取
源码片段#
固定版本 · 原文摘录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()相等条件直接使用标签名与值取得 postings;正则集合匹配和一般匹配走另外的路径。
319 it := index.Intersect(its...)320321 for _, n := range notIts {322 it = index.Without(it, n)323 }324325 return it, nil326}正向集合先求交,notIts 再逐个相减。完整函数还处理缺失标签和可匹配空字符串的条件,不能将 != 简化为直接查询另一个标签值。
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}任一路超过当前引用,就抬高候选并重新检查所有输入;只有每路都停在同一引用时才返回一个交集元素。
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()Next 先推进各路并选择当前最大引用,再交给 doNext 对齐;外层 Seek 也复用相同对齐机制。
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}已达到目标时直接返回;否则在尚未消费的有序切片中二分搜索,再把迭代位置移到命中位置之后。
五段原文连接标签查询入口、交集构建、候选对齐和底层二分 Seek;多种 postings 的具体 Seek 成本可能不同。
收益与取舍#
工程分析带来的收益
- 用索引引用完成标签筛选,减少无关序列的解码与样本读取
- 交集按需输出,不先物化全部中间交集;交集包装层只保留 O(k) 个输入迭代器和一个当前引用
- Seek 可利用底层有序存储跳跃,稀疏条件不必逐个扫描较长列表的全部引用
付出的代价
- 性能取决于列表长度、重叠程度、匹配器数量和底层 Seek 实现;不能把整个多路交集概括成一次 O(log N) 二分查找
- ListPostings 单次有效 Seek 在剩余 r 个引用中为 O(log r),但每次候选上升可能让多路重新检查;底层索引读取和结果遍历成本另计
- 倒排索引会占用空间并随新序列维护;正则条件、否定条件和空标签匹配可能扩大候选,不保证所有查询都很便宜
可比较的选择
扫描所有序列标签不需要为每个条件组织 postings,但查询代价随全库序列数增长,通常无法利用选择性强的标签。
将一个列表建哈希集合再过滤其他列表可用期望常数时间判断成员,但需要额外集合内存,也无法直接利用现有有序 Seek 跳过大段区间。
版本与适用范围#
固定 Prometheus v3.0.0,重点分析多个正向、非空相等标签条件的交集。输入是有序的序列引用,不是按采样时间排列的样本;这里的二分搜索定位序列 ID,不能误写为时间范围查找。空值与缺失标签、正则、否定条件的完整行为见 PostingsForMatchers。
参考来源#
源码、官方文档与原始论文tsdb/querier.go · postingsForMatcher · 相等条件走倒排入口
tsdb/index/postings.go · intersectPostings.doNext · 对齐候选
tsdb/index/postings.go · intersectPostings.Next / Seek · 推进输入
tsdb/index/postings.go · ListPostings.Seek · 二分定位剩余区间
tsdb/querier.go · PostingsForMatchers · 空值、否定和缺失标签语义
tsdb/index/postings.go · bigEndianPostings.Seek · 编码列表上的二分
相关实现与比较#
4 个相关案例nginx 的 consistent hash 将上游展开为有序哈希点,再用二分查找定位请求 key 的落点。
先用粗量化器缩小搜索区域,再扫描被选中的倒排列表。
Git 把内存中的 index 条目指针保存在有序、可增长的数组中,按路径和合并 stage 二分查找位置。
CPython 的列表排序识别已有序段,补齐短段,再按 Powersort 策略稳定归并,兼顾局部有序输入与通用排序。