Skip to content

DeltaSetAggregator: merge is order-insensitive, store returns buckets out of order, and get_keys() drops all keys on any removal #586

Description

@milindsrivastava1997

Three independent, pre-existing bugs in DeltaSetAggregatorAccumulator (delta_set_aggregator_accumulator.rs), found while investigating PR #582's review thread. All three need fixing together — fixing any subset still leaves multi-toggle, multi-epoch key histories wrong.

1. merge_accumulators (lines 291-319) is order-insensitive and collapses toggle counts. It unions every bucket's added/removed into two HashSets, then treats any key present in both as a "conflict" and strips it from both, regardless of which bucket contributed which side or in what order. This is wrong for any key that toggles more than once across the merged buckets — e.g. base window adds K, window A removes K, window B re-adds K, window C removes K again: chronologically K should end up absent, but the algorithm dedups removed={K} (from A and C) against added={K} (from B), calls it a conflict, and strips both — so K survives as present. Wrong regardless of input order, since the algorithm never looks at order at all.

2. The store returns buckets out of chronological order once epoch rotation has occurred. query_precomputed_output (per_key.rs:550-567) — the path DeltaSetAggregator key queries always use, since create_keys_query_params always queries [0, end_timestamp] — checks the current (newest, still-open) epoch first, then sealed epochs oldest-to-newest. The resulting Vec<TimestampedBucket> order is [newest] [oldest sealed] [next-oldest] ... [newest sealed], not sorted, and nothing downstream (merge_precomputed_outputs/merge_accumulators in simple_engine/mod.rs) re-sorts by timestamp before the sequential merge fold.

3. get_keys() (lines 251-258) returns None for the entire accumulator whenever removed is non-empty, instead of returning added.difference(&removed) (the actual current key set). Since removed is non-empty as soon as any key has ever been removed across the metric's full history, this fires on ordinary label churn, not just corrupted state — every currently-active key is hidden just because some unrelated key was removed at some point. This is independent of bugs #1/#2: even with a fully correct, order-sensitive merge producing exactly correct added/removed sets, get_keys() would still wrongly return None here.

No existing test catches any of these: the only multi-bucket DeltaSetAggregator merge test with real toggling covers a single flip across 2 non-overlapping buckets (passes by accident); the only test that forces epoch rotation only asserts a bucket count, never merge correctness or order; no test exercises get_keys() after any removal.

Affects both instant and range queries — not specific to #580/#582, though #582's new hard-fail-on-missing-keys behavior surfaces bug #3 more visibly (turns routine label churn into a full range-query failure instead of a silent skip).

Activity

  1. changed the title [-]DeltaSetAggregator merge is order-insensitive and count-collapsing; store also returns buckets out of chronological order[/-] [+]DeltaSetAggregator: merge is order-insensitive, store returns buckets out of order, and get_keys() drops all keys on any removal[/+] on Aug 23, 2026
  2. milindsrivastava1997 commented on Aug 25, 2026

    @milindsrivastava1997
    ContributorAuthor

    Note on bug #2 (store returns buckets out of order after epoch rotation): this is not currently reachable for DeltaSetAggregator specifically. insert_for_store_key (per_key.rs, and the same logic in global.rs) unconditionally skips maybe_rotate_epoch() whenever aggregation_type == DeltaSetAggregator, and always has (since PR #175/#279) — it needs to retain full history, so it never seals an epoch. So sealed_epochs stays empty for this type, and the current/sealed concatenation order never matters for it today.

    The bug is still real in query_precomputed_output's general contract though: any other accumulator type that does rotate (e.g. Sum, under CircularBuffer with a small capacity) can be returned out of chronological order today. It just doesn't corrupt anything for those types since their merges are commutative. Confirmed this with a test using Sum forcing 3 epoch seals — the newest (still-open current epoch) bucket comes back first, ahead of 3 older sealed epochs.

    Fixing the store's ordering is still worth doing as part of this issue — it's the correct contract for the method regardless, and it's what stands between today's harmless-for-everyone-else bug and a real corruption the moment DeltaSetAggregator's rotation exemption is ever relaxed, or a future order-sensitive accumulator doesn't get the same exemption.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Labels

bugSomething isn't working

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions