apache / apache/datasketches-cpp
Proposal: Add DDSketch (Relative-Error Quantile Sketch)
- Vorherrschende Sprache
- C++
- Sterne
- 273
- Forks
- 88
- Ø Merge
- 2 T. 2 Std.
- Gemergte PRs (30 T.)
- 8
Beschreibung
## Proposal: Add DDSketch (Relative-Error Quantile Sketch)
**Summary:**
This issue proposes adding an implementation of [DDSketch](https://www.vldb.org/pvldb/vol12/p2195-masson.pdf), a mergeable quantile sketch with relative-error guarantees, to the `datasketches-cpp` library.
Benefits:
- Relative-error guarantees
- Mergeability for distributed processing
- Predictable memory usage
- Used in production (Datadog, OpenTelemetry)
## References
- VLDB 2019: [DDSketch Paper](https://www.vldb.org/pvldb/vol12/p2195-masson.pdf)
- [Datadog's sketches-java repo](https://github.com/DataDog/sketches-java)
## Proposed Design
- New class under `ddsketch.hpp`
- Logarithmic mapping of input values to buckets using configurable relative accuracy
- Compact, bounded memory footprint with optional bucket collapsing
- Mergeable histogram-style structure
- Serialization and deserialization support
- Unit tests and benchmarks included
## Compatibility
- No changes to existing APIs
- Implementation will be self-contained
- Optional: initial release could be marked experimental
## Next Steps
If there is community interest, I’m happy to:
1. Share a detailed design document
2. Begin work on the implementation and submit a PR
3. Iterate based on feedback
Would the maintainers be open to including DDSketch? Are there specific design or compatibility considerations I should address before proceeding?
Beitragsleitfaden
Rechercherichtung
Beginne mit der Lektüre des DDSketch-Papers und der Referenz sketches-java von Datadog. Die vorgeschlagene Implementierung gehört in ddsketch.hpp und sollte Serialisierung, Deserialisierung, Unit-Tests und Benchmarks umfassen. Als abgeschlossen gilt die Arbeit, wenn ein eigenständiges, zusammenführbares DDSketch mit konfigurierbarer relativer Genauigkeit und begrenztem Speicher vorhanden ist, ohne bestehende APIs zu ändern.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Bewertung
- Tech-Stack
- cpp
- Bereich
- data
- Issue-Typ
- Feature
- Schwierigkeit
- 5/5
- Geschätzter Aufwand
- Über eine Woche
- Aktivitätsstatus
- Ruhig
- Klarheit
- Größtenteils klar
- Anfängerfreundlichkeit
- 45/100