Bitmap, ribbon filter, posting list

When I added indexes to amber, trace_id landed in a bitmap by default. I knew that putting a bitmap on a high-cardinality field is generally a bad idea, but I wanted to know exactly how bad. Spoiler: very bad.

Bitmap on trace_id

Bitmap indexes work well for fields with a small number of unique values. For level with five possible values:

INFO  -> [1, 1, 0, 1, 0, ...]
ERROR -> [0, 0, 1, 0, 1, ...]

Five compact bitmaps, good RLE compression, intersection of two conditions is a single AND. Cheap.

For trace_id the picture is different. It is a unique field - almost one value per record:

a1b2c3d4... -> [1, 0, 0, 0, ...]  // one bit set per 100K
e5f6a7b8... -> [0, 1, 0, 0, ...]
f9c0d1e2... -> [0, 0, 1, 0, ...]
... (99 997 more)

Instead of a few compact bitmaps: hundreds of thousands of nearly-empty ones. The index ballooned, compressed badly, and was expensive to rebuild at segment sealing time.

Ribbon filter

A ribbon filter is a probabilistic structure (~2 bits per key). It answers "does this segment contain value X?" with no false negatives, in a few kilobytes for a segment of 100K records.

For a trace_id query the executor became:

if ribbon, ok := e.logRibbon(seg.FileName); ok {
    if !ribbon.Contains(q.TraceID[:]) {
        return 0, nil // segment definitely does not contain this trace_id
    }
}
// scan the segment

Ribbon says "no" - skip the segment. Ribbon says "maybe yes" - scan. Indexes for 10M records went from hundreds of MB down to 340 KiB. Most segments were skipped on trace_id queries.

What broke

Before ribbon filter, service=api AND trace_id=X worked through bitmap intersection:

allowedIDs = bitmap(service=api) AND bitmap(trace_id=X)  // 1 record

After ribbon filter there is no bitmap(trace_id=X), so intersection is impossible:

allowedIDs = bitmap(service=api) only  // ~20K candidates out of 100K

20K records scanned instead of 1. Pure trace_id=X queries were fine - ribbon + linear scan works. But combined queries with trace_id lost the intersection entirely.

Posting list

A posting list is an inverted index for high-cardinality fields: trace_id -> []record_id.

If a segment has 2000 unique trace IDs with an average of 50 records each: 2000 x 50 x 8 bytes = 800 KB. Much smaller than the bloated bitmap, and it gives exact record IDs.

The lookup for trace_id now has three steps:

ribbon filter  ->  skip 99 of 101 segments
posting list   ->  get the exact record ID list for this trace_id
roaring64.And(bitmap(service=api), posting_list(trace_id=X))  ->  intersection

Combined queries work correctly again. The posting list lives in a .pidx sidecar next to the segment, built at sealing time, loaded lazily through an LRU cache on the first query to the segment.

Implementation detail

The first builder used map[string][]uint64. For 100K unique trace IDs: map overhead (~12 bytes/entry) + string keys (~32 bytes) + slice headers (~32 bytes) ~= 7.6 MB per segment during build. Multiply by the number of parallel sealings - GC says hello.

Switched to a flat sorted slice of pairs instead:

type rawPair struct {
    key [16]byte
    id  uint64
}

Summary

Bitmap and posting list answer the same question - "which records match this value?" - but through opposite tradeoffs. Bitmap uses a bit vector of length N: cheap at low cardinality, expensive at high cardinality. Posting list uses an explicit list: cheap at high cardinality, expensive at low cardinality.

Ribbon filter answers a different question - "could this segment contain this value?" - so it is not a competitor to either. All three coexist in amber and each does the job the other two cannot.