DDSketch: representative-formula accuracy bug, release-mode merge-check gap, positive-only value handling (vs DataDog reference; companion to sketchlib-go#72)

[zzylol]

What

Comparing src/sketches/ddsketch.rs against the reference implementation
(DataDog/sketches-go's ddsketch/ddsketch.go +
ddsketch/mapping/logarithmic_mapping.go) turns up one correctness bug and
several missing pieces, on top of the unbounded-bucket-growth issue already
tracked as sketchlib-go#72 (which this file shares, per that issue's own
scope note).

1. Bucket representative formula doesn't meet the advertised α-accuracy bound (correctness bug).

bin_representative(k) = gamma.powf(k as f64 + 0.5) (ddsketch.rs:352-354) —
the log-midpoint of the bucket. DataDog's representative is
LowerBound(index) * (1 + relativeAccuracy), i.e. gamma^k * (1+α)
(logarithmic_mapping.go Value()), chosen specifically so the relative
error is exactly α at both bucket edges. The midpoint formula instead
gives edge error sqrt(gamma) - 1, which is strictly larger than α (by
~α²/2). The file's own round-trip test (ddsketch.rs:806-811) already had to
loosen its tolerance to gamma.sqrt() - 1.0 to pass — that's the test
tacitly admitting the doc comment's claim ("guaranteeing a relative
accuracy of alpha for every quantile query", ddsketch.rs:3-5) isn't met.
Fix is mechanical: gamma.powf(k as f64) * (1.0 + self.alpha).

2. merge() only checks mapping compatibility via debug_assert!, compiled out in release builds.

ddsketch.rs:320-322 use debug_assert! for both alpha and gamma equality
before merging bucket vectors. In a release build this check doesn't exist
at all — merging two sketches built with different α silently reinterprets
one sketch's bucket indices under the other's mapping, corrupting the
result with no error. DataDog's MergeWith does a real runtime
IndexMapping.Equals check unconditionally and returns an error
(ddsketch.go:302-310). sketchlib-go's Go Merge already does this
correctly (a real if check, not a debug-only assert) — this file should
match it.

3. Positive-only: negative and zero values are silently dropped, not tracked.

add() (ddsketch.rs:213-232) returns early unless v.is_finite() && v > 0.0
— no error, no count, the sample just vanishes. DataDog tracks a dedicated
zeroCount plus a full mirrored negativeValueStore so those values are
counted. Any metric with legitimate zero or negative samples (deltas,
signed measurements) silently undercounts here.

4. No MinIndexableValue/MaxIndexableValue bound, no typed too-high/too-low/NaN errors.

add() has no bound on how far from the current window an extreme (but
finite, positive) value's index can land — it just feeds straight into the
unbounded-growth path (sketchlib-go#72's companion problem in this repo:
Buckets::ensure, ddsketch.rs:68-94, has the identical unbounded-grow
shape as the Go file that issue describes). DataDog derives
minIndexableValue/maxIndexableValue from the mapping so extreme values
are rejected with a typed error instead of silently producing an
arbitrarily distant bucket index.

5. Dense-only store, dense-only wire format.

No sparse/map-backed store option (only the single growing Vector1D), and
serialize_to_bytes messagepacks the raw dense count array as-is, including
zero runs across whatever span got touched. DataDog's Encode writes
varint-encoded (index-delta, count) pairs for populated bins only,
independent of internal store choice — wire size tracks cardinality, not
bucket span.

6. (minor) add_one's hot path uses raw unsafe pointer writes (ddsketch.rs:104-107) to
skip a bounds check it just performed itself. Not unsound as currently
written, but a self-inflicted safety hole with no compiler backstop if the
surrounding logic is ever refactored — the Go file has no equivalent risk.

Why this matters

(1) and (2) are real correctness bugs, not scope gaps — (2) especially,
since debug_assert! gives a false sense of safety that evaporates in
release builds. (3)-(5) mean this sketch silently produces worse accuracy
and worse memory/wire behavior than the documented DDSketch guarantee, in
ways a caller has no way to detect (everything fails silently rather than
returning an error).

Scope note

Item 4 overlaps with sketchlib-go#72 (unbounded bucket growth) — same root
cause (Buckets::ensure has no cap), tracked here as the Rust counterpart
per that issue's explicit "also applies to asap_sketchlib" note. Items 1,
2, 3, 5, 6 are independent of #72 and specific to this file (item 2 is
Rust-specific; the Go Merge already does the right thing).

Suggested direction (not yet decided)

• Fix the representative formula (mechanical, no design decision needed).
• Replace the debug_assert! mapping check in merge() with a real
  runtime check that returns a Result/error on mismatch.
• Decide whether negative/zero support is in scope for this project's use
  cases; if so, add a zero_count + mirrored negative store analogous to
  DataDog's, matching whatever direction is chosen for sketchlib-go#72's Go
  counterpart so both stay consistent.

[zzylol]

Partially addressed by asap_sketchlib #72 (fix/ddsketch-datadog-parity): item 1 (representative formula → gamma^k*(1+alpha)), item 2 (merge() debug_assert! → real release-surviving Result runtime check), and the input side of item 4 (min/max_indexable_value() + add() dropping untrackable extremes, which also guards the #72-shared unbounded-growth path at the input) are fixed there. Round-trip test tolerance tightened from sqrt(gamma)-1 back to alpha.

Deliberately left for a follow-up (coupled to the in-flight GOS per-cell delta stack + Rust backend decoder): negative/zero value tracking (item 3), the collapsing-store cap itself, DataDog's sparse/varint wire format (item 5), and the add_one unsafe hot-path cleanup (item 6). Go counterpart: sketchlib-go#79.

[zzylol]

Split the negative/zero value tracking design question (item 3) into its own issue: #73.

[zzylol]

The collapsing-store cap (item 4's memory-safety piece, shared root cause with sketchlib-go#72) is implemented in #74 (fix/ddsketch-collapsing-store, stacked on #72): a new opt-in DDSketch::with_max_bins(alpha, max_bins) constructor caps the bucket store, collapsing the LOWEST bins (DataDog's CollapsingLowestDenseStore semantics) once growth would exceed the cap. max_bins is #[serde(skip)] so it never leaks onto the wire — a decoded sketch is always unbounded. Defaults to uncapped, plain DDSketch::new unaffected. Go counterpart: sketchlib-go#81.