DDSketch: A Fast and Fully-Mergeable Quantile Sketchwith Relative-Error Guarantees
Charles Masson

Jee E. Rim

Homin K. Lee

Datadog
620 8th Ave.
New York, NY
charles.masson@datadoghq.com

Datadog
620 8th Ave.
New York, NY
jee.rim@datadoghq.com

Datadog
620 8th Ave.
New York, NY
homin@datadoghq.com

ABSTRACT
Summary statistics such as the mean and variance are easily maintained for large, distributed data streams, but order statistics (i.e.,sample quantiles) can only be approximately summarized. Thereis extensive literature on maintaining quantile sketches where theemphasis has been on bounding the rank error of the sketch while
using little memory. Unfortunately, rank error guarantees do notpreclude arbitrarily large relative errors, and this often occurs inpractice when the data is heavily skewed.
Given the distributed nature of contemporary large-scale systems,
another crucial property for quantile sketches is mergeablility, i.e.,several combined sketches must be as accurate as a single sketch of
the same data. We present the first fully-mergeable, relative-error
quantile sketching algorithm with formal guarantees. The sketch isextremely fast and accurate, and is currently being used by Datadog
at a wide-scale.
PVLDB Reference Format:
Charles Masson and Jee E Rim and Homin K. Lee. DDSketch: A fast
and fully-mergeable quantile sketch with relative-error guarantees. PVLDB,
12(12): 2195-2205, 2019.
DOI: https://doi.org/10.14778/3352063.3352135

1.

INTRODUCTION

Computing has increasingly moved to a distributed, containerized, micro-service model. Some organizations run thousands ofhosts, across several data centers, with each host running a dozen
containers each, and these containers might only live for a couple
hours [11, 10]. Effectively being able to administer and operationalize such a large and disparate fleet of machines requires the ability
to monitor, in near real-time, data streams coming from multiple,
possibly transitory, sources [3].
The data streams that are being monitored can include application
logs, IoT sensor readings [28], IP-network traffic information [9],financial data, distributed application traces [30], usage and performance metrics [1], along with a myriad of other measurements andevents. The volume of monitoring data being transmitted to a central processing system (usually backed by a time-series database orThis work is licensed under the Creative Commons AttributionNonCommercial-NoDerivatives 4.0 International License. To view a copyof this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For
any use beyond those covered by this license, obtain permission by emailing
info@vldb.org. Copyright is held by the owner/author(s). Publication rights
licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 12, No. 12
ISSN 2150-8097.
DOI: https://doi.org/10.14778/3352063.3352135

Figure 1: A distributed web application, with each container
sending metrics to the monitoring system.

an event storage system) can be high enough that simply forwarding all this information can strain the capacities (network, memory,CPU) of the monitored resources. Ideally a monitoring system helps
one discover and diagnose issues in distributed systems—not causethem.

Figure 2: The average latency of a web endpoint over time (dotted line) is closer to the 75th percentile than it is to the 50th (thetwo solid lines).
Our running example will be a web application backed by a distributed system, where the ability to answer any particular request
might depend on several underlying services and databases (Figure 1). The metric we monitor for our example will be the latencyof the requests it handles. Every time a worker finishes handlinga request, it will note how long it took. Simple summary statistics
such as the overall mean and variance can be easily maintained. For
instance, the workers can keep counts, sums, and sums of squaresof the latency and send those values to the monitoring system (andreset those values) every second. The monitoring system will thenbe able to aggregate those values and derive metrics—being able to2195

Figure 3: Histograms for p0-p95 and p0-p100 of 2 million web request response times. (Bars for p93-p100 exist but are shorter thanthe minimum pixel height.)

graph the average latency using 1 second intervals, but also rollingup the sums and counts to graph the average latency over muchlarger time periods using much larger intervals perfectly accurately.
Unfortunately, the latencies of web requests are usually extremely
skewed—the median response time might be in the milliseconds
whereas there could be a couple of outlying responses that takeminutes (Figure 3). A simple average, while easy to monitor canbe easily skewed by outlying values as can be seen in Figure 2.
As the average response time is not a particularly useful measure,
we are instead interested in tracking quantiles such as the 50th andthe 99th percentiles (we will also refer to these as the p50 and p99).
The ability to compute quantiles over aggregated metrics has beenrecognized to be an essential feature of any monitoring system [16].
Quantiles are famously impossible to compute exactly without
holding on to all the data [29]. If one wanted to track the median
request latency over time for a web application that is handling millions of requests a second, this would mean sending millions of data
points to the monitoring service which could then calculate the median by sorting the data. If one wanted the median aggregated overlonger time intervals the monitoring service would have to store allthese data points and then calculate the median over the larger setof points.
Given how expensive calculating exact quantiles can be for bothstorage and network bandwidth, most monitoring systems will compress the data into sketches and compute approximate quantiles.
More formally, given a multiset S of size n over R, the q-quantile
item xq ∈ S is the item x whose rank R(x) in the sorted multiset S
is b1 + q(n − 1)c for 0 ≤ q ≤ 1, where the rank R(x) is the number of elements in S smaller than or equal to x.1 Some special quantiles include x1 , the maximum element of S, and the median x0.5 .
1This definition of quantile is also known as the lower quantile. Replacing the floor with a ceiling gives us what’s known as the upper
quantile.

There has been a long line of work on sketching data streams sothat the rank accuracy is preserved, i.e., for any value v, the sketch
provides an estimate rank R̃ such that |R̃(v) − R(v)| ≤ n (see[27] and [21] for excellent surveys on much of this work as well as
additional motivation for sketching quantiles).
Unfortunately, for data sets with heavy tails, rank-error guarantees can return values with large relative errors. Consider again thehistogram of 2M request response times in Figure 3. If we have aquantile sketch with a rank accuracy of 0.005, and ask for the 99th
percentile, we are guaranteed to get a value between the 98.5th and99.5th percentile. In this case this is anywhere from 2 to 20 seconds,
which from an end-user’s perspective is the difference between anannoying delay and giving up on the request.
Given the inadequacy of rank accuracy for tracking the higher
order quantiles for distributions with heavy tails, we turn instead torelative accuracy.
Definition 1. x̃q is an α-accurate q-quantile if |x̃q −xq | ≤ αxq
for a given q-quantile item xq ∈ S. We say that a data structure isan α-accurate (q0 , q1 )-sketch if it can output α-accurate q-quantiles
for all q0 ≤ q ≤ q1 .
To further illustrate the difference between rank accuracy and relative accuracy consider Figure 4. The graphs show the actual p50,
p75, p90 and p99 values along with the quantile estimates from asketch with 0.005 rank accuracy and a sketch with 0.01 relative accuracy.

1.1

Our Results

In Section 2 we describe our relative-error sketch, dubbed theDistributed Distribution Sketch (DDSketch), and we discuss different implementation strategies. In Section 3 we prove that thesketch can handle data that is as heavy-tailed as that which comes

2196

4.2

2.05

4.1

p75

p50

2.10

2.00
1.95

3.9

1.90

3.8
5

10

15

20

5

10

15

20

5

10

15

20

220

11.0

200
180

p99

10.5

p90

4.0

10.0

160
140
120

9.5

100
5

10

15

Rel Err Sketch

80

20

Rank Err Sketch

ActualFigure 4: Actual quantiles vs. 0.005-rank-accurate and 0.01-relative-accurate quantiles of a data stream (20 batches of 100,000
values).

from a distribution whose logarithm is subexponential with parameters (σ, b), which includes heavy-tailed distributions such as the
log-normal and Pareto distributions. We show that for the Pareto
distribution, the size of an α-accurate (o(1), 1)-sketch is:O

b log n/δlog((1 + α)/(1 − α))with probability 1 − δ. (Note that our results hold for data coming from any distribution without any independence assumptions aslong as the tail of the empirical data is no larger than that for a Pareto
distribution). In Section 4 we present our experimental results.

1.2

Related Work

Quantile sketching dates back to 1980 when Munro and Paterson[29] demonstrated the first quantile sketching algorithm with formal guarantees. The best known rank-error quantile sketch is thatof Greenwald and Khanna [20] whose deterministic sketch (GK)provides  rank accuracy using O((1/) log(n)) space.
In addition to accuracy and size, a desirable property of a sketch ismergeability [2]. That is, several sketches of different data sets canbe combined into a single sketch that can accurately answer quantile queries over the entire data set. Mergeability has increasingly
become a necessary property as systems become more distributed.
Equi-depth histograms [6] are a good example of non-mergeable
data set synopses as there is no way to accurately combine overlapping buckets. GK is only known to be “one-way” mergeable, that is
the merging operation itself can not be distributed.
There is a line of work using randomness culminating in a rankerror quantile sketch that uses only O((1/) log log(1/δ)) space(where δ is the probability of failure) [25] with full mergeability.
However, all of the above solutions, deterministic or randomized,
have high relative error for the larger quantiles on heavy-tailed data(in practice we have found it to be worse for the randomized algorithms).

The problems of having high relative errors on the larger quantiles has been addressed by a line of work that still uses rank error,
but promises lower rank error on the quantiles further away from themedian by biasing the data it keeps towards the higher (and lower)
quantiles [7], [8], [17]. The latter, dubbed t-digest, is notable as
it is one of the quantile sketch implementations used by Elasticsearch [18]. These sketches have much better accuracy (in rank)
than uniform-rank-error sketches on percentiles like the p99.9, butthey still have high relative error on heavy-tailed data sets. Like GK
they are only one-way mergeable.
The only relative-error sketch in the literature to our knowledge
is the HDR Histogram [31] (and is the other quantile sketch implementation used by Elasticsearch). It has extremely fast insertion
times (only requiring low-level binary operations), as the bucket
sizes are optimized for insertion speed instead of size, and it is fully
mergeable (though very slow). The main downside for HDR Histogram is that it can only handle a bounded (though very large) rangethat might not be suitable for certain data sets. It also has no published guarantees, though much of the analysis we present for DDSketch can be made to apply to a version of HDR Histogram that moreclosely resembles DDSketch with slightly worse guarantees.
A recent quantile sketch, called the Moments sketch [19] takes
an entirely different approach by estimating the moments of the underlying distribution. It has notably fast merging times and is fully
mergeable. The guaranteed accuracy, however, is only for the average rank error ˜, unlike all the sketches above which have guarantees
for the worst-case error (whether rank or relative). The associatedsize bound is O(1/˜). In practice, the sketch also has a bounded
range as the moments quickly grow larger, and they will eventuallycause floating point overflow errors.
We compare the performance of DDSketch to GK, HDR, andMoments in Section 4.
A related line of work exists in constructing histograms (see [6]for a thorough survey). The accuracy of a histogram is measured
using the distance between the actual values and the values of the2197

Table 1: Quantile Sketching Algorithms
guarantee
range
mergeability
DDSketchrelativearbitraryfull
HDR Histogram
relativeboundedfull
GKArrayrank
arbitraryone-way
Moments
avg rank boundedfullbuckets to which the original values are assigned. The task is tofind the histogram with B buckets that minimizes the overall distance. Optimal algorithms [24] use dynamic programming and areusually considered to be too costly, and thus approximation algorithms are often considered. The most popular distance in the literature is the squared L2 distance (such a histogram is called thev-optimal histogram), but relative-error approximation algorithms
exist as well [23], [22] (though these algorithms use Ω(n) space).
Note that while one can try to use these histograms to answer
quantile queries, there are no guarantees on the error of any particular quantile query, as the only error guarantees are global and not
for any individual item. Moreover, the error guarantees are always
relative to an unknown optimal (for the number of buckets) solution,
not an absolute error guarantee. There is also no straightforward
way to merge histograms as the bucket boundaries are based on thedata, which can be wildly different for each histogram.

2.

Moreover, γ i−1 < xq ≤ γ i . So if xq ≥ x̃q , then:xq − x̃q
x̃q
x̃q
2γ i
=1−
≤1− i =1− i
=α
xq
xq
γ
γ (γ + 1)
Similarly if xq ≤ x̃q , then:x̃q − xq
x̃q
x̃q
2γ i
=
− 1 < i−1 − 1 = i−1
−1=α
xq
xq
γ
γ (γ + 1)
Combining both cases:|xq − x̃q | ≤ αxq .

To answer quantile queries, the sketch sums up the buckets until
it finds the bucket containing the q-quantile value xq :Algorithm 2: Quantile(q)Input: 0 ≤ q ≤ 1
i0 ← min({j : Bj > 0});count ← Bi0 ;i ← i0 ;while count ≤ q(n − 1) doi ← min({j : Bj > 0 ∧ j > i});count ← count + Bi ;end while
return 2γ i /(γ + 1);

DDSKETCH

We will first describe the most basic version of our algorithm thatwill be able to give α-accurate q-quantiles for any 0 ≤ q ≤ 1. It is
straightforward to insert items into this sketch as well as delete items
and merge sketches. Then we will show how to modify the sketch sothat it gives α-accurate q-quantiles for q0 ≤ q ≤ 1 with boundedsize. Section 2.2 will go over various implementation options forthe sketch.

2.1

Sketch Details

Let γ := (1+α)/(1−α). The sketch works by dividing R>0 into
fixed buckets. We index our buckets by i ∈ Z, and each bucket Bi
counts the number of values x that fall between: γ i−1 < x ≤ γ i .
That is, given a value x we will assign it to the bucket indexed by
dlogγ (x)e:Algorithm 1: Insert(x)Input: x ∈ R>0i ← dlogγ (x)e;Bi ← Bi + 1;
Deletion works similarly. Since the bucket boundaries are independent of the data, any two sketches using the same value for γ canbe merged by simply summing up the buckets that share an index.
A simple lemma shows that every value gets assigned to a bucket
whose boundary values are enough to return a relative-error approximation to its value.
Lemma 2. For a given q-quantile item xq ∈ S and bucket index
i = dlogγ (xq )e, let x̃q = 2γ i /(γ + 1). Then x̃q is an α-accurate
q-quantile.
Proof. Note that by definition of γ:
α=1−

2
2γ
=
−1
γ+1
γ+1

Given Lemma 2, the following Proposition easily follows:
Proposition 3. Given α > 0 and 0 ≤ q ≤ 1, Quantile(q)return an α-accurate q-quantile.
Proof. Let’s refer to the ordered elements of the multiset S asx(1) ≤ · · · ≤ x(n) , so that by definition of the quantile, xq =x(b1+q(n−1)c) . We will also write c(x) the number of elements in
S that are less than or equal to x. Note that for any j, we always
have 
c(x(j) ) ≥ j. Quantile(q) outputs 2γ i /(γ + 1) where i =min( j : c(γ j ) > q(n − 1) ). Given Lemma 2, it is enough toprove that i = dlogγ x(b1+q(n−1)c) e.
Let k be the largest integer so that x(k) ≤ γ i . It is clear thatx(k) is in the bucket of index i, so that i = dlogγ x(k) e. By definition of k, k = c(x(k) ) and, because there is no element of S in
the bucket of index i that is greater than x(k) , we also know thatc(x(k) ) = c(γ i ). Thus, k = c(x(k) ) = c(γ i ) > q(n − 1) and,given that k is an integer, k ≥ b1 + q(n − 1)c follows. Therefore,
i = dlogγ x(k) e ≥ dlogγ x(b1+q(n−1)c) e.
By contradiction, if i > dlogγ x(b1+q(n−1)c) e, then i − 1 ≥dlogγ x(b1+q(n−1)c) e and γ i−1 ≥ x(b1+q(n−1)c) . As a consequence:c(γ i−1 ) ≥ c(x(b1+q(n−1)c) ) ≥ b1 + q(n − 1)c > q(n − 1),which violates the definition of i. Hence,i = dlogγ x(b1+q(n−1)c) e,
and the result follows.
However buckets are stored in memory (e.g., as a dictionary thatmaps indices to bucket counters, or as a list of bucket counters forcontiguous indices), the memory size of the sketch is at least linear
in the number of non-empty buckets. Therefore, a down-side to thebasic version of DDSketch is that for worst-case input, its size can2198

grow as large as n, the number of elements inserted into it. A simple modification will allow us to guarantee logarithmic size bounds
for non-degenerate input, and Section 3 will show that the modification will never affect the ability to answer q-quantile queries forany constant q.
The full version of DDSketch is a simple modification that addresses its unbounded growth by imposing a limit of m = f (n) on
the number of buckets it keeps track of. It does so by collapsing thebuckets for the smallest indices:
Algorithm 3: DDSketch-Insert(x)Input: x ∈ R>0i ← dlogγ (x)e;Bi ← Bi + 1;
if |{j : Bj > 0}| > m theni0 ← min({j : Bj > 0});i1 ← min({j : Bj > 0 ∧ j > i0 });Bi1 ← Bi1 + Bi0 ;Bi0 ← 0;end ifGiven that our sketch has predefined bucket boundaries for a givenγ, merging two sketches is straightforward. We just increase thecounts of the buckets for one sketch by those of the other. This,
however, might increase the size of the sketch beyond the limit ofm = f (n), where n is now the number of elements in the resulting
merged sketch. As with the insertion, we stay within the limit bycollapsing the buckets with smallest indices:We’ll discuss the trade-offs between the accuracy α, the minimum accurate quantile q, the number of items n, and the size of thesketch m in Section 3.

2.2

Implementation Details

Most systems often have built-in timeouts and a minimum granularity, so the values coming into a sketch usually have an effective
minimum and maximum. Importantly, our sketch does not need toknow what those values are beforehand.
It is straightforward to extend DDSketch to handle all of R by
keeping a second sketch for negative numbers. The indices for thenegative sketch need to be calculated on the absolute values, andcollapses start from the highest indices.
Like most sketch implementations, it is useful to keep separate
track of the minimum and maximum values. Given how buckets aredefined for DDSketch, we also keep a special bucket for zero (andall values within floating-point error of zero when calculating theindex, which involves computing the logarithm of the input value).
The size of the sketch can be set to grow by setting m = c log n,which will match the upper bounds discussed in Section 3, but inpractice m is usually set to be a constant large enough to handle awide range of values. As an example, for α = 0.01, a sketch of size
2048 can handle values from 80 microseconds to 1 year, and cover
all quantiles.
If m is set to a constant, it often makes sense to preallocate thesketch buckets in memory and keep all the buckets between theminimum and maximum buckets (perhaps implemented as a ringbuffer). If the sketch is allowed to grow with n, then the sketch caneither grow with every order of magnitude of n, or one can implement the sketch in a sparse manner so that only buckets with values
greater than 0 are kept (sacrificing speed for space efficiency).

Algorithm 4: DDSketch-Merge(S 0 )Input: DDSketch S 0

3.

foreach i : Bi > 0 ∨ Bi0 > 0 do
Bi ← Bi + Bi0 ;end foreachwhile |{j : Bj > 0}| > m do
i0 ← min({j : Bj > 0});i1 ← min({j : Bj > 0 ∧ j > i0 });Bi1 ← Bi1 + Bi0 ;Bi0 ← 0;end while

For most practical applications, e.g., tracking the latency of web
requests to a particular endpoint, one cares about constant quantiles
such as those around the median such as 0.25, 0.5, 0.75, or thosetowards the edge such as 0.9, 0.95, 0.99, 0.999. Thus by Proposition 4, we will focus on the necessary conditions for x1 ≤ xq γ m−1
or:

We trade off the benefit of a bounded size with not being able
to correctly answer q-quantile queries if xq belongs to a collapsed
bucket. The next lemma shows a sufficient condition for a quantile
q to be α-accurately answered by our algorithm:
Proposition 4. DDSketch can α-accurately answer a given qquantile query if:
x1 ≤ xq γ m−1 .
Proof. For any particular quantile q, xq will be α-accurate aslong as it belongs to one of the m buckets kept by the sketch. Let’srefer to that bucket index as iq , which holds values between γ iq −1
and γ iq . If the maximum bucket (that holds x1 ) has index i1 ≤
iq + m − 1, then the bucket iq has definitely not been collapsed.
Thus, given that x1 ≤ xq γ m−1 , then γ i1 −1 < x1 ≤ xq γ m−1 ≤γ iq γ m−1 , and i1 − 1 < iq + m − 1, which is equivalent to i1 ≤
iq + m − 1 as these indices are integers.

DISTRIBUTION BOUNDS

log(x1 ) − log(xq )+ 1 ≤ m.
log(γ)(1)√
for q = Θ(1), though our results will apply for q = Ω(1/ n).
(For simplicity, we will assume that qn is a whole number in thissection.)For any fixed γ and m, it is easy to come up 
with a data set S for
which the condition does not hold, e.g., S = γ 1 , γ 2 , . . . , γ 2m .
Given that distribution-free results are impossible, for our formal
results, we will instead assume that our data is i.i.d. from a particularfamily of distributions, and then show how large the sketch would
have to be for Equation 1 to hold. We are able to obtain good bounds
for families of distributions as general as those whose logarithms
are subexponential (e.g., Pareto distributions). While our bounds
are obtained by assuming i.i.d., in practice, as long as the tail of theempirical distribution is no fatter than that of a Pareto, we do notneed to assume anything about the data generating process at all.
We will bound the LHS of Equation 1 by showing that with probability greater than 1 − δ1 the sample quantile xq is greater thana quantile just below it. Then we will show that with probability
greater than 1 − δ2 , the sample maximum is less than some bound.
Finally by the union bound we get that the probability that both2199

bounds apply is greater than 1 − δ1 − δ2 . In practice, the probability of failing these bounds is smaller as the sample maximum
and sample quantiles become quickly independent as n grows.

Definition 6. A random variable X ∈ R is said to be subexponential with parameters (σ, b) if
E [exp (λ(X − EX))] ≤ exp σ 2 λ2 /2 ,3.1

for 0 ≤ λ ≤ 1/b.

Sample Quantiles

Let capital X1 , . . . , Xn denote n independent real-valued random variables drawn from a distribution with cdf F : R → [0, 1].
The generalized inverse of F , F −1 (p) is known as the quantile function of F . Let X(1) ≤ X(2) ≤ · · · ≤ X(n) denote the order statistics of X1 , . . . , Xn (i.e., the ordered random variables).
The next Lemma shows that with high probability a lower sample
quantile can’t fall too far below the actual quantile.
Lemma 5. Let X(1) ≤ X(2) ≤ · · · ≤ X(n) be the order statistics for
p i.i.d. random variables Xi distributed according to F . Lett = log(1/δ1 )/2n and t < q ≤ 1/2, then
Pr X(qn) > F −1 (q − t) ≥ 1 − δ1 .
Proof. The proof follows Chvátal’s proof of a special case of
the Hoeffding bound [5]. For any single random variable X drawn
from a distribution with cdf F , Pr[X ≤ F −1 (p)] = p. Then forany particular order statistic and any x ≥ 1:

Pr X(k) ≤ F −1 (p)
!
n
X
n i
p (1 − p)n−i
=
i
i=k
!
!
k−1
n
X
X n i
n i
n−i i−k≤p (1 − p)x+p (1 − p)n−i xi−k
i
i
0
k
!
n
X
n
= x−k
pi (1 − p)n−i xi = x−k (px + (1 − p))n (2)i0where the last equality is by the Binomial Theorem.
Equation 2 is minimized when x = (1 − p)k/p(n − k), andtaking k = qn, our bound becomes:
 qn n(1−q)(1 − p)n(1 − p)p(n − k)p=
(1 − p)kn−kq(1 − q)(3)
Note that for x ≥ 1, p ≤ q ≤ 1/2, and that the bound is trivial
when p = q. However, if we take p = q − t, we get:





q
1−q
(3) = exp −qn log− (1 − q) n log
q−t
1−q+t
 

Z q 
q
1−q
= exp −n
−
dx
x
1−x
q−t


Z q
q−x
= exp −ndx
q−t x(1 − x)


Z q

≤ exp −4n(q − x)dx = exp −2nt2 = δ1


k 

n

q−t

p
for t = log(1/δ1 )/2n, and where the last inequality uses the factthat x(1 − x) ≤ 1/4 for all x ∈ R.

3.2

Sample Maximums

We will first bound the sample maximum for subexponential distributions, which include the Gaussian, logistic, chi-squared, exponential, and many others.

Using Chernoff-type techniques, one can obtain concentration inequalities for subexponential variables [4].
Theorem 7. Let X be a subexponential random variable withparameters (σ, b). Then,
Pr [X − EX ≥ t] ≤ exp −t2 /2σ 2
for 0 ≤ t ≤ σ 2 /b, andPr [X − EX ≥ t] ≤ exp (−t/2b)
2

for t > σ /b.
Now we can lower-bound the sample maximum by the complement of the event that none of the sample is greater than t.
Corollary 8. Let X(1) ≤ X(2) ≤ · · · ≤ X(n) be the order
statistics for i.i.d. subexponential random variables Xi with parameters (σ, b), and t = 2b log(n/δ2 ). Then the sample maximum isless than t with probability at least 1 − δ2 .
Proof. By Theorem 7,nPr X(n) − EX > t < 1 − 1 − e−t/2bnδ2=1− 1−< δ2 ,nwhere the final inequality is by Bernoulli’s inequality.

3.3

Sketch Size Bounds

For subexponential distributions, we can bound Equation 1 bycombining Lemma 5 and Corollary 8:
Theorem 9. Let X(1) ≤ X(2) ≤ · · · ≤ X(n) be the order
statistics for i.i.d. random variables Xi distributed according to a
subexponential distribution F with parameters (σ, b). Then withprobability at least 1 − δ1 − δ2 , DDSketch is an α-accurate (q, 1)sketch with size at most (log X(n) − log X(qn) )/ log(γ) + 1, which
is bounded from above by:log (2b log (n/δ2 ) + EX) − log F −1 (q − t)+1log(γ)
pfor γ = (1 + α)/(1 − α), t = log(1/δ1 )/2n, and t < q ≤ 1/2.
Exponential. For concreteness, let’s take δ1 = δ2 = e−10 and
α = 0.01 (i.e., γ ≈ 1.02), and let’s consider the exponential distribution with cdf F (t; λ) = 1 − exp(−λt) for t ≥ 0, and 0 otherwise. The exponential distribution is subexponential with parameters (2/λ, 2/λ).
If n > 320, then p > 3/8, and the sample median is at leastF −1 (p) > −λ−1 log(1−3/8) > 0.47/λ. The sample maximum2
is at most 4λ−1 (log(n) + 10 + 1/4), and 1/ log(γ) < 51 so we
can bound the size from Theorem 9 by: 51(log(4 log n + 41) −log(0.47)) + 1.
This means that even with a sketch of size 273 one can 0.01accurately maintain the upper half order statistics of over a million
2

The factor of 4 can be removed from the bound for the sample
maximum if we analyze the exponential distribution directly insteadof using the generic bounds for subexponential distributions.

2200

1e-03pareto

1e-09

1e-04

1e-10

1e-05

1e-11

1e-06

1e-12

1e-07

1e-13

1e-08

1e-14

1e-09

1e-15

span

1e-10
1e-16
0e+00 1e+05 2e+05 3e+05 4e+05 5e+05 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
1e11

1.6
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

power

0

2

4

6

8

10

12

Figure 5: Histograms of the pareto, span and mpcat-obs data sets. The y-axes of the pareto and span data sets are plotted on log scales
due to their heavy-tailed nature.

samples with probability greater than 0.99991. This grows doubleexponentially, so a sketch of size 1000 can 0.01-accurately maintainthe upper half order statistics of over exp(exp(17)) values with thatsame probability.
Pareto. The double logarithm in our size bound from Theorem 9
allows us to handle distributions with much fatter tails as well. The
Pareto distribution distribution has cdf F (t; a, b) = 1 − (b/t)a .
If X is a random variable drawn from this distribution, then Y =log(X/b) ∼ Exp(a). Thus, we can reuse the arguments above to
get that with probability at least 1 − δ1 − δ2 :log(X(n) ) < 4a−1 log(n/δ2 ) + a−1 + log(b)andlog(X(n/2) ) > −a−1 log(1/2 +plog(1/δ1 )/2n) + log(b).

As before, let’s take δ1 = δ2 = e−10 , α = 0.01, and assume
that n > 320. With probability greater than 1 − e−10 − e−10 ≈0.99991:
log(X(n) ) − log(X(n/2) )+ 1 < 51a−1 (4 log n + 11) + 1
log(γ)
Given that Pareto distributions have exponentially fatter tails than
exponential distributions, the sketch size upper bounds increase accordingly. Taking a = 1, this means that we require a sketch ofsize 3380 to 0.01-accurately maintain the upper half order statistics
of over a million samples with probability greater than 0.99991. A
sketch of size 10000, can 0.01-accurately maintain the upper halforder statistics of over exp(46) values with that same probability.
Other Distributions. We focused on subexponential tails and thePareto distribution in this section as we believe it to best represent
the worst case for practical use-cases of quantile sketching. For
lighter tails such as subgaussians and thus for lognormal distributions, we can of course get much tighter bounds.

4.

representation of floating-point values, which provides a costless
way to evaluate the logarithm to the base 2. In between a linear or
quadratic interpolation can be used so that the logarithm to any basecan be approximated. Those mappings define buckets whose sizes
are not optimal under the constraint of ensuring relative accuracy
guarantee as some of them are smaller than necessary. Their fasterevaluation than the memory-optimal logarithmic mapping comes atthe cost of requiring more buckets to cover a given range of values,
and therefore a memory footprint overhead in DDSketch. We referto this version of the code as DDSketch (fast) in our experiments.
We compare DDSketch against the Java implementation [31] of
HDR Histogram, our Java implementation of the GKArray versionof the GK sketch [12], as well as the Java implementation of theMoments sketch [15] (all three discussed in Section 1.2). HDR
Histogram is a relative-error sketch for non-negative values. Its accuracy is expressed as the number of significant decimal digits dof the values. GKArray guarantees that the rank error of the estimated quantiles will be smaller than  after adding values. The
Moments sketch has guarantees on the average rank error boundedby the number of moments k that are estimated.
We consider three data sets, and compare the size in memoryof the sketches, the speed of adding values and merging sketches,
and the accuracy of the estimated quantiles. The measurements are
performed with the Java implementations of all four sketches.
The sketch parameters are chosen so that the targeted relative accuracy for DDSketch and HDR Histogram is 1%. For GKArray, we
use a rank accuracy that gives roughly similar memory footprints
as DDSketch. For the Moments sketch, we use the maximum recommended numbers of moments, as per the Java implementation
documentation, and we also use the arcsinh transform (called compression in the code), which makes the sketch more accurate for
distributions with heavy tails. Those parameters are summarized inTable 2.
Table 2: Experiment Parameters
α = 0.01
DDSketchm = 2048
HDR Histogram
d=2
GKArray = 0.01
k = 20Moments sketch
compression enabled

EVALUATION

We provide implementations of DDSketch in Java [12], Go [13]and Python [14]. Our Java implementation provides multiple versions of DDSketch: buckets can be stored in a contiguous way (forfast addition) or in a sparse way (for smaller memory footprint).
The number of buckets can grow indefinitely or be bounded with afixed maximum of m buckets, collapsing the buckets of lowest or
highest indices. The mapping of the values to their bucket indicescan be logarithmic, as defined above, but we also provide alternative mappings that are faster to evaluate while still ensuring relative
accuracy guarantees. Those mappings make the most of the binary

4.1

Data Sets

We use three data sets for our experiments, whose distributions
are shown in Figure 5. The pareto data set contains synthetic data
generated from a Pareto distribution with a = b = 1. The span data

2201

Sketch Size (kB)

40
35
30
25
20
15
10
5
0

pareto

10 3

10 4

10 5

10 6

N Values

DDSketch

10 7

10 8

40
35
30
25
20
15
10
5
0

span

power

10
8
6
4
2

10 3

10 4

10 5

10 7

10 6

N Values

DDSketch (fast)

GKArray

10 8

0

10 3

10 4

10 5

10 6

N Values

HDRHistogram

MomentSketch

Figure 6: Sketch size in memory in kB.

1200

meaning that the lower quantile estimates may not meet the relative
accuracy guarantee. In our experiments this maximum was neverreached, and we have not found this to be an issue. Figure 7 plots
the number of DDSketch bins for the pareto data set. The number of bins is around 900 for n = 1010 , less than half the limit of2048. It is also worth noting that the actual sketch size required for
the Pareto distribution is much smaller than the upper bounds wecalculated in Section 3.3.

N Bins

1000
800
600
400
0

Time per Add operation (ns)200
10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10

N Values

Figure 7: Number of bins in DDSketch for the pareto data set.

set is a set of span durations of the distributed traces of requests that
Datadog received over a few hours. The durations are integers inunits of nanoseconds, and it includes a wide range of values (from100 to 1.9 × 1012 ). The power dataset is the global active power
measurements from the UCI Individual Household Electric Power
Consumption dataset [26].

4.2

200
180
160
60
40
20
0

10 3

10 4

10 5

10 6

N Values

DDSketch
DDSketch (fast)

Sketch Size In Memory

How much space a sketch takes up in memory will be an important consideration in many applications. For each of the foursketches, the parameters chosen will determine the accuracy of thesketch as well as its size. An increase in accuracy generally requiresa larger sketch. Figure 6 plots the sketch size in memory as n increases.
We see that DDSketch (fast) can be up to twice the size of DDSketch, and that HDR Histogram is significantly larger. Both GKArray and the Moments sketch are much smaller, and the Moments
sketch in particular is completely independent of the size of the input.
If one runs DDSketch with a limit placed on the number of bins
the sketch can contain, when the maximum number of bins is reached,
DDSketch starts to combine the smallest bins together as needed,

220

HDRHistogram

10 7

10 8

GKArray
MomentSketch

Figure 8: Average time required to add a value to a sketch.

4.3

Add and Merge Speeds

In this section, we compare the performance of the sketches interms of the time required to add values to a sketch and to merge
sketches together. Figure 8 shows the average time required to add nvalues to an empty sketch divided by n. It takes less than 5 seconds
to add a hundred million values to an empty DDSketch on a 3.1GHz
MacBook Pro.

2202

Merge Time (microseconds)

80

which has a guarantee on average, and even GK for the higher quantiles.

70
60

5.

50
40
30
20
10
0

10 3

10 4

10 5

10 6

N Values

DDSketch
DDSketch (fast)
HDRHistogram

10 7

10 8

GKArray
MomentSketch

Figure 9: Average time required to merge two sketches as afunction of number of values in the merged sketch.

GKArray is the slowest for insertions by far, being around six
times slower than the Moments sketch. Adding to an HDR Histogram is faster than adding to the standard version of DDSketch
as HDR Histogram has a simpler index calculation than DDSketch
which has to calculate logarithms. DDSketch (fast) is the fastest interms of insertion speed, though this was obtained by an increase in
the sketch size as we saw in Section 6.
Figure 9 plots the average time required to merge two sketchesof roughly the same size, as a function of the number of values in
the merged sketch. Merging two DDSketches is very fast—it takes
around 10 microseconds or less to merge two sketches containing
up to fifty million values each—depending on the data set and size,
it can be more than an order of magnitude faster than GKArray or
HDR Histogram. The Moment sketch has the fastest merge speedsof all the algorithms, as each sketch only holds on to k = 20 values.

4.4

CONCLUSION

Datadog’s use-case for distributed quantile sketching comes from
our agent-based monitoring where we need to accurately aggregate
data coming from disparate sources in our high-throughput, lowlatency, distributed data processing engine. To get a sense of thescale, some of our customers have endpoints that handle over 10M
points per second, and DDSketch provides accurate latency quantiles for these endpoints.
After our initial evaluation of existing quantile sketching algorithms, we settled on the Greenwald-Khanna algorithm as it could
handle arbitrary values, and provided the best compromise between
accuracy, size, insertion speed, and merge time. (The implementation we provide comes from our work in optimizing the algorithm.)
Unfortunately, the relative-accuracy errors for higher quantiles
generated by the rank-error sketch proved to be unacceptable, which
led us to develop DDSketch. Unlike HDR Histogram, which is designed to handle a bounded range and has poor merge speeds, DDSketch is a flexible relativer error sketch that can handle arbitrarily
large ranges, and has fast merge speeds. Compared to GK, the relative accuracy of DDSketch is comparable for dense data sets, while
for heavy-tailed data sets the improvement in accuracy can be measured in orders of magnitude. The rank error is also comparable to
if not better than that of GK. Additionally, it is much faster in bothinsertion and merge.

6.

ACKNOWLEDGMENT

This research has made use of data provided by the International
Astronomical Union’s Minor Planet Center.

7.

REFERENCES[1] L. Abraham, J. Allen, O. Barykin, V. Borkar, B. Chopra,
C. Gerea, D. Merl, J. Metzler, D. Reiss, S. Subramanian, J. L.
Wiener, and O. Zed. Scuba: Diving into data at facebook.
PVLDB, 6(11):1057–1067, 2013.
[2] P. K. Agarwal, G. Cormode, Z. Huang, J. Phillips, Z. Wei,
and K. Yi. Mergeable summaries. In Proceedings of the 31st
ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems, PODS ’12, pages 23–34, New York, NY,
USA, 2012. ACM.
[3] B. Beyer, C. Jones, J. Petoff, and N. R. Murphy. Site
Reliability Engineering: How Google Runs Production
Systems. ” O’Reilly Media, Inc.”, 2016.
[4] V. V. Buldygin and U. V. Kozachenko. MetricCharacterization of Random Variables and Random
Processes. American Mathematical Society, Rhode Island,
USA, 2000.
[5] V. Chvátal. The tail of the hypergeometric distribution.
Discrete Mathematics, 25:285–287, 1979.
[6] G. Cormode, M. Garofalakis, P. J. Haas, and C. Jermaine.
Synopses for massive data: Samples, histograms, wavelets,
sketches. Foundations and Trends R in Databases,
4(1-3):1–294, 2011.
[7] G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava.
Effective computation of biased quantiles over data streams.
In 21st International Conference on Data Engineering,
ICDE’05, pages 20–31, New York, NY, USA, 2005. IEEE
Computer Society Press.

Sketch Accuracy

DDSketch guarantees a relative error in its quantile estimates of at
most α, while GKArray guarantees a rank error of less than . HDR
Histogram has an implied relative-error guarantee of 10−d where dis the number of significant digits. Therefore we compare both theaverage relative and rank errors in Figures 10 and 11, for the p50,
p95, and p99 estimates. Note that for GKArray, for n ≤ 1/, all thevalues are retained so that both the relative error and rank error will
be zero.
Figure 10 shows that for all three data sets DDSketch has a consistent relative error less than α for all values of n. For the heavytailed pareto and span data sets, the relative error sketches (DDSketch and HDR Histogram) have much smaller relative error thaneither GKArray or Moments. The discrepancy is especially striking
for the higher quantiles, as the values returned can be several ordersof magnitude off the actual value. The Moments sketch has particular difficulty with the span data set as it has trouble dealing withsuch a large range of values.
In terms of rank error, the guarantee of GKArray can be clearlyseen in Figure 11. No such guarantee is provided for DDSketch and
HDR Histogram, yet they perform better than the Moments sketch

2203

Relative Error in p50
Relative Error in p95
Relative Error in p99

pareto

10 1
10 0
10 -1
10 -2
10 -3
10 1

10 3

10 4

10 5

10 6

10 7

10

10

10 6
10 5
10 4
10 3
10 2
10 1
10 0
10 -1
10 -2
-3
8 10

10

10 3
10 2
10 1
10 0
10 -1
10 -2
-3
8 10

10 0
10 -1
10 -2
10 -3
10 8
10 7
10 6
10 5
10 4
10 3
10 2
10 1
10 0
10 -1
10 -2
10 -3

10 3

10 3

10 4

10 4

10 5

10 5

10 6

10 6

N Values

10 7

10 7

DDSketch

10 98
10 7
10 6
10 5
10 4
10 3
10 2
10 1
10 0
10
10 -1
10 -2
-3
8 10

10 4

span

power

10 1
10 0
10 -1
10 -2

10 3

10 4

10 5

10 6

10 7

10 8

10 -3
10 1

10 3

10 4

10 5

10 6

10 3

10 4

10 5

10 6

10 3

10 4

10 5

10 6

10 0
10 -1
10 -2
10 3

10 4

10 5

10 6

10 7

10 8

10 -3
10 1
10 0
10 -1
10 -2

10 3

10 4

10 5

10 6

N Values

GKArray

10 7

10 8

HDRHistogram

10 -3

N Values

MomentSketch

Figure 10: Relative errors of p50, p95, and p99 estimates.

[8] G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava.
Space- and time-efficient deterministic algorithms for biased
quantiles over data streams. In Proceedings of the 25th ACM
SIGMOD-SIGACT-SIGART Symposium on Principles of
Database Systems, PODS ’06, pages 263–272, New York,NY, USA, 2006. ACM.
[9] C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk.
Gigascope: a stream database for network applications. In
Proceedings of the 2003 ACM SIGMOD International
Conference on Management of Data, pages 647–651. ACM,
2003.
[10] Datadog. 8 emerging trends in container orchestration.
https://www.datadoghq.com/container-orchestration,
2018. Accessed: 2018-12-12.
[11] Datadog. 8 surprising facts about real docker adoption.
https://www.datadoghq.com/docker-adoption/,2018. Accessed: 2018-12-12.
[12] Datadog.
https://github.com/DataDog/sketches-java, 2019.
[13] Datadog. https://github.com/DataDog/sketches-go,2019.
[14] Datadog. https://github.com/DataDog/sketches-py,
2019.
[15] S. DAWN. Moments sketch. https://github.com/stanford-futuredata/momentsketch,2018. Accessed: 2019-05-29.

[16] J. Dean and L. A. Barroso. The tail at scale. Communicationsof the ACM, 56(2):74–80, 2013.
[17] T. Dunning and O. Ertl. Computing extremely accuratequantiles using t-digests. arXiv preprint arXiv:1902.04023,
2019.
[18] Elasticsearch. Elasticsearch reference: Percentiles
aggregation. https://www.elastic.co/guide/en/
elasticsearch/reference/current/
search-aggregations-metrics-percentile-aggregation.
html, 2015. Accessed: 2018-09-14.
[19] E. Gan, J. Ding, K. S. Tai, V. Sharan, and P. Bailis.
Moment-based quantile sketches for efficient high cardinality
aggregation queries. PVLDB, 11(11):1647–1660, 2018.
[20] M. B. Greenwald and S. Khanna. Space-efficient online
computation of quantile summaries. In Proceedings of the2001 ACM SIGMOD International Conference on
Management of Data, SIGMOD ’01, pages 58–66, New
York, NY, USA, 2001. ACM.
[21] M. B. Greenwald and S. Khanna. Quantiles and equidepth
histograms over streams. In M. Garofalakis, J. Gehrke, and
R. Rastogi, editors, Data Stream Management, pages 45–86.
Springer, New York, NY, USA, 2016.
[22] S. Guha, N. Koudas, and K. Shim. Approximation andstreaming algorithms for histogram construction problems.
ACM Transactions on Database Systems (TODS),
31(1):396–438, 2006.

2204

Rank Error in p50
Rank Error in p95

span

10 0
10 -1

10 -1

10 -2

10 -2

10 -2

10 -3

10 -3

10 -3

10 -4

10 -4

10 -4

10 3

10 4

10 5

10 6

10 7

10 8

10 -5

10 3

10 4

10 5

10 6

10 7

10 8

10 -5

10 0

10 0

10 0

10 -1

10 -1

10 -1

10 -2

10 -2

10 -2

10 -3

10 -3

10 -3

10 -4

10 -4

10 -4

10 -5

10 3

10 4

10 5

10 6

10 7

10 8

10 -5

10 3

10 4

10 5

10 6

10 7

10 8

10 -5

10 0

10 0

10 0

10 -1

10 -1

10 -1

10 -2

10 -2

10 -2

10 -3

10 -3

10 -3

10 -4

10 -4

10 -4

10 -5

10 3

10 4

10 5

10 6

N Values

10 7

DDSketch

10 8

10 -5

10 3

10 4

10 5

10 6

N Values

GKArray

power

10 0

10 -1

10 -5

Rank Error in p99

pareto

10 0

10 7

10 8

10 -5

10 3

10 4

10 5

10 6

10 3

10 4

10 5

10 6

10 3

10 4

10 5

10 6

HDRHistogram

N Values

MomentSketch

Figure 11: Rank errors of p50, p95, and p99 estimates.

[23] S. Guha, K. Shim, and J. Woo. Rehist: Relative error
histogram construction algorithms. In Proceedings of the
30th International Conference on Very Large Data Bases,
VLDB ’04, pages 300–311. VLDB Endowment, 2004.
[24] H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala,K. C. Sevcik, and T. Suel. Optimal histograms with quality
guarantees. In Proceedings of the 24rd International
Conference on Very Large Data Bases, VLDB ’98, pages
275–286, 1998.
[25] Z. Karnin, K. Lang, and E. Liberty. Optimal quantile
approximation in streams. In Proceedings of the 57th IEEE
Symposium on Foundations of Computer Science (FOCS),FOCS ’16, pages 71–78, New York, NY, USA, 2016. IEEE
Computer Society Press.
[26] M. Lichman. Uci machine learning repository. https://archive.ics.uci.edu/ml/datasets/individual+
household+electric+power+consumption, 2013.

[27] G. Luo, L. Wang, K. Yi, and G. Cormode. Quantiles overdata streams: experimental comparisons, new analyses, andfurther improvements. PVLDB, 25(4):449–472, 2016.
[28] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong.
The design of an acquisitional query processor for sensor
networks. In Proceedings of the 2003 ACM SIGMODInternational Conference on Management of Data, pages
491–502. ACM, 2003.
[29] J. I. Munro and M. S. Paterson. Selection and sorting withlimited storage. Theoretical Computer Science,
12(3):315–323, 1980.
[30] R. R. Sambasivan, R. Fonseca, I. Shafer, and G. R. Ganger.
So, you want to trace your distributed system? key design
insights from years of practical experience. Technical Report
CMU-PDL-14-102, Carnegie Mellon University, 2014.
[31] G. Tene. Hdrhistogram: A high dynamic range (hdr)
histogram. http://hdrhistogram.org/, 2012. Accessed:
2018-09-15.

2205