Skip to content

Count-Min top-k rounds each sample's weight to an integer, so sum top-k on fractional values comes back empty #916

Open

Description

@milindsrivastava1997

Problem

A sum top-k (topk(k, sum by (...) (...))) runs on CountMinSketchWithHeap, and every sample's value is rounded to an integer before it reaches the sketch. Values below 0.5 count as zero and are dropped, and larger fractional values lose precision. On CPU-utilization data (0–1), the top-k answer is empty or arbitrary.

Where the rounding happens (asap_sketchlib rev 5158bf2, src/message_pack_format/portable/countminsketch_topk.rs):

  • sketchlib_cms_heap_update: let many = value.round() as i64; if many <= 0 { return; }
  • Rebuilding from the wire format: matrix cells and heap values are .round() as i64.

ASAPQuery side: CmsWithHeapAccumulatorUpdater::update_keyed (asap-query-engine/src/precompute_engine/accumulator_factory.rs) passes the raw f64 sample value as the weight.

Impact

The random-workload E2E replays had to scale trace values up so top-k survives:

  • Alibaba MSMetrics CPU utilization: ×10⁴ (make_replay.py).
  • Google ClusterData 2011 CPU rate: ×10⁶ (make_google_replay.py); ×10⁴ would still zero about 6% of samples.

Real deployments can't rescale their metrics, so fractional gauges (CPU fraction, ratios, seconds) need the sketch to keep weights unrounded.

Possible fixes

  1. Use an f64-counter Count-Min + heap. asap_sketchlib already has a generic counter type with an f64 heap test (f64_heap_counts_are_the_unrounded_estimate, rev 63e5655); switch the portable wrapper and the wire format to it.
  2. Or keep integer counters with a fixed per-sketch scale (e.g. ×10⁶), applied on update and removed on query. Cheaper, but the scale has to suit the data range.

Acceptance

  • A sum top-k over values in (0, 1) returns the same keys as the exact answer on a small fixture.
  • An engine test with fractional weights that fails before the fix.
  • Count-based top-k (count_events = true) is unchanged.

Activity

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions