[Bug]: Badger index keys concatenate fields without a delimiter, so different tag/operation values can collide

[aarushitandon0]

What happened?

As a Jaeger operator, I want queries to return only traces that exactly match the requested service, operation, and tags, so that search results are correct and do not include unrelated traces.

Badger's secondary index keys are constructed by concatenating fields without any delimiter or length prefix. Different combinations of service names, operation names, tag keys, and tag values can therefore produce identical index keys. When this happens, queries silently return trace IDs that belong to a different service, operation, or tag combination. No error is returned, and nothing is logged.

For example, service="checkout" with tag id="123" and service="checkout" with tag id1="23" both encode to checkoutid123. The same applies to the operation index: service="A", operation="Bc" and service="AB", operation="c" both encode to ABc.

The keys are built at writer.go:74 (operation index) and writer.go:85,89,94 (tag index), and the reader rebuilds the same concatenation to seek at reader.go:277 (operation) and reader.go:267 (tag).

ADR-005 (docs/adr/005-badger-storage-record-layouts.md:106) states the reader guards against this ambiguity by checking the full key prefix up to the timestamp matches exactly. That check exists at reader.go:547 (bytes.Equal on the key prefix), but it cannot catch this case: collided fields produce byte-identical prefixes rather than a mismatch, so bytes.Equal returns true and the entry passes. The ADR's own example, "foo"+"bar" vs "foobar"+"", concatenates identically and would also pass.

For the tag index, the ADR makes no correctness claim, describing it only as a latent source of subtle bugs, which matches the code: no equivalent check exists there.

Steps to reproduce

1. Write a span with service="checkout" and tag id="123".
2. Write a second span with service="checkout" and tag id1="23".
   Both encode to the index key bytes "checkoutid123".
3. Query FindTraceIDs for tag id=123. Both traces are returned.

The same applies to the operation index: service="A", operation="Bc" and service="AB", operation="c" both encode to "ABc".

Reproduced by two tests I've added to internal/storage/v1/badger/spanstore/read_write_test.go, both failing on main: TestFindTraceIDs_TagIndexKeyCollision and TestFindTraceIDs_OperationIndexKeyCollision. The rest of the Badger suite passes.

Expected behavior

Queries should return only traces matching the exact requested service, operation, and tag key/value combination. Different field combinations that happen to concatenate to the same bytes must not match.

In the example above, querying for tag id=123 should return only the trace carrying that tag, not the one tagged id1=23.

Relevant log output

=== RUN   TestFindTraceIDs_TagIndexKeyCollision
    read_write_test.go:334:
        Error: []model.TraceID{{Low:0x2, High:0x1}, {Low:0x1, High:0x1}} should not contain model.TraceID{Low:0x2, High:0x1}
        Messages: query for tag id=123 incorrectly matched tag id1=23 due to
                  delimiter-less tag index key concatenation
    read_write_test.go:336:
        Error: "[...0002 ...0001]" should have 1 item(s), but has 2
        Messages: expected exactly 1 trace id (trace1) to match
--- FAIL: TestFindTraceIDs_TagIndexKeyCollision (0.01s)

=== RUN   TestFindTraceIDs_OperationIndexKeyCollision
    read_write_test.go:385:
        Error: []model.TraceID{{Low:0x2, High:0x1}, {Low:0x1, High:0x1}} should not contain model.TraceID{Low:0x2, High:0x1}
        Messages: query for service=A,operation=Bc incorrectly matched
                  service=AB,operation=c due to delimiter-less operation
                  index key concatenation
    read_write_test.go:387:
        Error: "[...0002 ...0001]" should have 1 item(s), but has 2
        Messages: expected exactly 1 trace id (trace1) to match
--- FAIL: TestFindTraceIDs_OperationIndexKeyCollis

Screenshot

No response

Additional context

Possible fix

Encode field boundaries in the index key, either by length-prefixing each field or by inserting a separator byte. Length-prefixing seems more robust, since no byte value is genuinely forbidden in a service name, tag key, or tag value. This touches six call sites: four in writer.go and two in reader.go, ideally through a shared helper so the writer and reader cannot drift apart.

On-disk format change

This changes the index key format. I checked both internal/storage/v1/badger and internal/storage/v2/badger for a versioning or migration scheme and found none: no format version byte and no migration path.

In practice, the impact looks limited. Per ADR-005, Ephemeral defaults to true (temp directory, removed on process exit), and TTL.Spans otherwise defaults to 72 hours, so old-format index entries age out within one TTL window. Stale index entries also fail closed rather than returning incorrect data. Flagging it in case maintainers would prefer it handled differently.

I'd be happy to work on this if the approach sounds right.

Jaeger backend version

main, unreleased, post-v2.20.0 (commit 33d2964)

SDK

No response

Pipeline

No response

Stogage backend

Badger (v1 native span store)

Operating system

Linux (Ubuntu on WSL2)

Deployment model

No response

Deployment configs

[waterWang]

I've submitted a PR (#9223) that fixes the Badger index key collision issue.

The fix adds a makeIndexKeyValue helper function that joins service name, operation name, tag key, and tag value fields with a delimiter byte (�), preventing the field concatenation ambiguity described in the issue. The reader's seek logic has been updated to use the same delimiter.

Changes:

• writer.go: Use makeIndexKeyValue for operation name and tag index keys
• reader.go: Use makeIndexKeyValue for tag and operation name seek keys
• rw_internal_test.go: Updated existing test, added collision prevention test