ddsketch

此仓库包含分布式分位数草图算法DDSketch [1] 的Python实现。DDSketch对[0, 1]区间内的任何分位数q都有相对误差保证。也就是说，如果第q分位数的确切值为，那么DDSketch返回一个值，使得<|x-y| / x < e>，其中是相对误差参数。（这里的默认值设置为0.01。）DDSketch还可以完全合并，这意味着分布式系统中的多个草图可以在中央节点中合并。

我们的默认实现DDSketch保证[1]，对于任何可以用尾端是次指数分布描述的数据，其大小不会太大。

我们还提供了实现（LogCollapsingLowestDenseDDSketch 和 LogCollapsingHighestDenseDDSketch），其中 q-分位数将准确到指定的相对误差，适用于不是太小（或太大）的 q。具体来说，只要属于草图保留的 m 个 bin 之一，q-分位数就会准确到指定的相对误差。如果数据是秒数，默认的 m = 2048 可以覆盖 80 微秒到 1 年的时间。

安装

要安装此包，运行 pip install ddsketch，或者克隆仓库并运行 python setup.py install。此包依赖于 numpy 和 protobuf。（如果不适配，则可以移除 protobuf 依赖。）

用法

from ddsketch import DDSketch

sketch = DDSketch()

向草图添加值

import numpy as np

values = np.random.normal(size=500)
for v in values:
  sketch.add(v)

在相对误差范围内找到 values 的分位数。

quantiles = [sketch.get_quantile_value(q) for q in [0.5, 0.75, 0.9, 1]]

将另一个 DDSketch 合并到 sketch 中。

another_sketch = DDSketch()
other_values = np.random.normal(size=500)
for v in other_values:
  another_sketch.add(v)
sketch.merge(another_sketch)

拼接 values 和 other_values 后的值分位数仍然在相对误差范围内。

开发

要在 ddsketch 上工作，必须安装 Python 解释器。建议使用提供的开发容器（需要 docker），其中包含所有必需的 Python 解释器。

docker-compose run dev

或者，如果您在 docker 外开发，则建议使用虚拟环境

pip install virtualenv
virtualenv --python=3 .venv
source .venv/bin/activate

测试

要运行测试，安装 riot

pip install riot

将 Python 版本替换为可用的解释器。

# Run tests with Python 3.9
riot run -p3.9 test

发行说明

新功能、错误修复、弃用和其他重大更改必须包含发行说明。

要为更改生成发行说明

riot run reno new <short-description-of-change-no-spaces>

编辑生成的文件以包含对提交/PR 中所做的更改的说明，并提交更改。

格式化

使用

riot run fmt

类型检查

使用 mypy 进行类型检查

riot run mypy

类型检查

使用 flake8 检查代码

riot run flake8

Protobuf

Protobuf 存储在 go 仓库中：https://github.com/DataDog/sketches-go/blob/master/ddsketch/pb/ddsketch.proto

安装最低要求的 protoc 并生成 Python 代码

docker run -v $PWD:/code -it ubuntu:18.04 /bin/bash
apt update && apt install protobuf-compiler  # default is 3.0.0
protoc --proto_path=ddsketch/pb/ --python_out=ddsketch/pb/ ddsketch/pb/ddsketch.proto

发布

1. 生成发行说明并使用 pandoc 格式化为 Github

    git checkout master && git pull
    riot run -s reno report --no-show-source | pandoc -f rst -t gfm --wrap=none

将输出复制到新的发布：https://github.com/DataDog/sketches-py/releases/new。

2. 输入发布标签（遵循 semver）（例如 v1.1.3、v1.0.3、v1.2.0）。
3. 使用不带 v 的标签作为标题。
4. 将发布保存为草稿，并将链接传递给其他人进行快速审查。
5. 如果一切看起来都很好，请点击发布

参考文献

[1] Charles Masson 和 Jee E Rim 和 Homin K. Lee. DDSketch：具有相对误差保证的快速且完全可合并的分位数草图。PVLDB，12(12)：2195-2205，2019。（论文中引用的代码，包括我们对 Greenwald-Khanna（GK）算法的实现，可以在以下位置找到：https://github.com/DataDog/sketches-py/releases/tag/v0.1）