apache / apache/datasketches-cpp

Proposal: Add DDSketch (Relative-Error Quantile Sketch)

未关闭
#457 8 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
C++
星标
273
派生
88
平均合并
2 天 2 小时
30 天内合并 PR
8

描述

## 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?

贡献指南

打开贡献指南

调研方向

首先阅读 DDSketch 论文和 Datadog 的 sketches-java 参考实现。建议的实现应放在 ddsketch.hpp 中,并包含序列化、反序列化、单元测试和基准测试。完成的标准是得到一个自包含、可合并的 DDSketch,具有可配置的相对精度和有界内存,同时不更改现有 API。

由索引模型根据 Issue 内容生成。

评估

技术栈
cpp
领域
data
Issue 类型
功能
难度
5/5
预计耗时
一周以上
活跃度
冷清
描述清晰度
基本清楚
新手友好度
45/100

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。