Build a Prometheus-style time-series database (12 scenes)
Scene 08

Inverted index — labels to series

For each (label, value) pair the database keeps a sorted list of series IDs — a postings list — and a multi-label query is the intersection of those lists, with cost bounded by the SMALLEST list.

Previously

Stage 2 is a search engine in disguise — postings lists and intersections, just like Lucene.

Scene 08

Inverted index: labels to series

  1. Watch
  2. Try it
  3. Predict
  4. Capture
POSTINGS · label = value → series idsINTERSECTION LANEmethod=GET12468n=5method=POST357n=3status=200134678n=6status=50025n=2path=/api12345n=5path=/health678n=3drv25L2357MERGE WALKO(2) · 0 cmpRESULT · 1 series5Query {method=POST, status=500} → select two postings lists. status=500 is smaller (2 IDs) — it drives the walk.
What to watch for

How does the database go from {method=POST, status=500} to series IDs without scanning every series? It keeps a tiny sorted list of series IDs for every (label, value) pair — a postings list. The query becomes an intersection of two such lists. Watch status=500 (the smaller list) drive the walk; each of its 2 IDs is probed against POST.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

Index.addSeries
every label of every series fans out into one postings list
def addSeries(seriesId, labels):
    for (k, v) in labels:
        # postings: (label, value) -> sorted [seriesId, ...]
        postings[(k, v)].sortedInsert(seriesId)
    # special list for the no-selector query {}
    postings[allPostingsKey].sortedInsert(seriesId)
Index.resolveSeries
selectors -> postings lists, smallest first
def resolveSeries(selectors):
    if len(selectors) == 0:
        return postings[allPostingsKey]
    lists = [postings[(k, v)] for (k, v) in selectors]
    # planner's only heuristic: drive the walk by the
    # smallest list — the corpus size never appears.
    lists.sort(key = len)
    if len(lists) == 1:
        return lists[0]
    return intersect(lists)
Index.intersect
walk the smallest list, probe the others
def intersect(lists):
    driver = lists[0]      # smallest after sort
    others = lists[1:]
    out = []
    for candidate in driver:
        # gallop / binary search — never a linear scan
        if all(other.contains(candidate)
               for other in others):
            out.append(candidate)
    return out             # cost = O(|driver|)

Where this sits in Build a Prometheus-style time-series database

Scene 08 of 12. For each (label, value) pair the database stores a sorted list of series IDs (a postings list). A multi-label query is the intersection.

Up next. Each label-value adds one postings list; each unique combination adds one series ID. That sounds cheap — until someone adds the wrong label.

All 12 scenes in Build a Prometheus-style time-series database · Every curriculum

Built with Arqly
Every scene in Build a Prometheus-style time-series database builds on the one before it.All 12 Build a Prometheus-style time-series database scenes