t-digest module for Redis
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
include
src
test
.gitignore
LICENSE
Makefile
README.md
circle.yml

README.md

redis-tdigest

Build Status

This is a Redis module for the t-digest data structure which can be used for accurate online accumulation of rank-based statistics such as quantiles and cumulative distribution at a point. The implementation is based on the Merging Digest implementation by the author.

Building & Loading

Before going ahead, make sure that the Redis server you're using has support for Redis modules.

First, you'll have to build the Redis t-digest module from source.

make

This should generate a shared library called tdigest.so in the root folder. You can now load it into Redis by using the following redis.conf configuration directive:

loadmodule /path/to/tdigest.so

Alternatively, you can load it on an already running Redis server by issuing the following commands:

MODULE LOAD /path/to/tdigest.so

API

TDIGEST.NEW key [compression]

Initializes a key to an empty t-digest structure with the compression provided or with the default compression of 400.

Reply: "OK"

TDIGEST.ADD key value count [value count ...]

Adds a value with the specified count. If key is missing, an empty t-digest structure is initialized with a default compression of 400. Returns the sum of counts for all values added.

Reply: long long

TDIGEST.MERGE destkey sourcekey [sourcekey ...]

Merges one or more sourcekey into destkey. If destkey is missing, an empty t-digest structure is initialized with a default compression of 400.

Reply: "OK"

TDIGEST.CDF key value [value ...]

Returns the cumulative distribution for all provided values. value must be a double. The cumulative distribution returned for all values is between 0..1.

Reply: double array or nil if key missing

TDIGEST.QUANTILE key quantile [quantile ...]

Returns the estimate values at all provided quantiles. quantile must be a double between 0..1.

Reply: double array or nil if key missing

TDIGEST.DEBUG key

Prints debug information about the t-digest.

Reply: bulk strings array

The reply is of the form:

1) TDIGEST (<compression>, <num_centroids>, <memory size>)
2)   CENTROID (<mean>, <weight>)
3)   CENTROID (<mean>, <weight>)
4)   CENTROID (<mean>, <weight>)
5)   ...

Centroids are printed in sorted order with respect to their mean.

Testing

The integration tests require a running Redis server so you must have redis-server on your PATH or pass its location in an environment variable called REDIS_SERVER. Tests are written in Python and use the pytest unit testing library.

make test

Contributing

Bug reports, feature and pull requests are welcome! Please add tests for any non-trivial changes you submit.