@datadog/sketches-js

What is @datadog/sketches-js?

@datadog/sketches-js is a JavaScript library for working with data sketches, which are probabilistic data structures used for efficiently summarizing and querying large datasets. This package is particularly useful for applications that require real-time analytics and monitoring, such as those in observability and telemetry.

What are @datadog/sketches-js's main functionalities?

DDSketch

DDSketch is a data structure for accurately tracking quantiles in a data stream. The code sample demonstrates how to create a DDSketch, add data points to it, and query the median (50th percentile).

const { DDSketch } = require('@datadog/sketches-js');

const sketch = new DDSketch();
sketch.accept(10);
sketch.accept(20);
sketch.accept(30);
console.log(sketch.getQuantile(0.5));

Merge Sketches

This feature allows you to merge two DDSketch instances. The code sample shows how to create two sketches, add data points to them, and then merge them into one sketch.

const { DDSketch } = require('@datadog/sketches-js');

const sketch1 = new DDSketch();
sketch1.accept(10);

const sketch2 = new DDSketch();
sketch2.accept(20);

sketch1.merge(sketch2);
console.log(sketch1.getQuantile(0.5));

Serialization

Serialization allows you to convert a DDSketch to a format that can be stored or transmitted and then later reconstructed. The code sample demonstrates how to serialize and deserialize a DDSketch.

const { DDSketch } = require('@datadog/sketches-js');

const sketch = new DDSketch();
sketch.accept(10);
const serialized = sketch.serialize();
console.log(serialized);

const deserializedSketch = DDSketch.deserialize(serialized);
console.log(deserializedSketch.getQuantile(0.5));

Other packages similar to @datadog/sketches-js

tdigest

The 'tdigest' package provides a data structure for accurate online accumulation of rank-based statistics such as quantiles and cumulative distribution. It is similar to DDSketch in that it is used for summarizing large datasets, but it uses a different algorithm (t-digest) which may have different performance characteristics and accuracy trade-offs.

approximate

The 'approximate' package offers various probabilistic data structures for approximate counting, membership, and quantile estimation. It includes implementations of HyperLogLog, Count-Min Sketch, and Quantile Sketches. This package provides a broader range of data structures compared to @datadog/sketches-js, which focuses specifically on DDSketch.

README

sketches-js

This repo contains the TypeScript implementation of the distributed quantile sketch algorithm DDSketch. DDSketch is mergeable, meaning that multiple sketches from distributed systems can be combined in a central node.

Installation

git clone https://github.com/DataDog/sketches-js.git
cd sketches-js
yarn install
yarn test

Usage

Initializing

To initialize a sketch with the default parameters:

const DDSketch = require('ddsketch');
const sketch = new DDSketch();

To configure the sketch's parameters:

const sketch = new DDSketch({
  relativeAccuracy: 0.05, // defaults to 0.01
});

Add a value to the sketch

sketch.accept(0);
sketch.accept(3.1415);
sketch.accept(-20);

Retrieve a value at a given quantile from the sketch

sketch.getValueAtQuantile(0)
sketch.getValueAtQuantile(0.5)
sketch.getValueAtQuantile(0.9)
sketch.getValueAtQuantile(0.99)
sketch.getValueAtQuantile(1)

Merge sketches

Independent sketches can be merged together, provided that they were initialized with the same relativeAccuracy:

const sketch1 = new DDSketch();
const sketch2 = new DDSketch();

[1,2,3,4,5].forEach(value => sketch1.accept(value));
[6,7,8,9,10].forEach(value => sketch2.accept(value));

// `sketch2` is merged into `sketch1`, without modifying `sketch2`
sketch1.merge(sketch2);

sketch1.getValueAtQuantile(1) // 10

Algorithm

DDSketch has relative error guarantees: it computes quantiles with a controlled relative error.

For instance, using DDSketch with a relative accuracy guarantee set to 1%, if the expected quantile value is 100, the computed quantile value is guaranteed to be between 99 and 101. If the expected quantile value is 1000, the computed quantile value is guaranteed to be between 990 and 1010.

References

• DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees. Charles Masson, Jee E. Rim and Homin K. Lee. 2019.
• Java implementation: https://github.com/DataDog/sketches-java
• Go implementation: https://github.com/DataDog/sketches-go
• Python implementation: https://github.com/DataDog/sketches-py