DDSketch: a fast and fully-mergeable quantile sketch with relative-error guarantees

DDSketch: a fast and fully-mergeable quantile sketch with relative-error guarantees Masson et al., VLDB'19 Datadog handles a ton of metrics - some customers have endpoints generating over 10M points per second! For response times (latencies) reporting a simple metric such as ‘average’ is next to useless. Instead we want to understand what’s happening at different ... Continue Reading

The data calculator: data structure design and cost synthesis from first principles and learned cost models

The Data Calculator: data structure design and cost synthesis from first principles and learned cost models Idreos et al., SIGMOD'18 This paper preceded the work on data continuums that we looked at last time, and takes a more general look at interactive and semi-automated design of data structures. A data structure here is defined as ... Continue Reading

Design continuums and the path toward self-designing key-value stores that know and learn

Design continuums and the path toward self-designing key-value stores that know and learn Idreos et al., CIDR'19 We’ve seen systems that help to select the best data structure from a pre-defined set of choices (e.g. ‘Darwinian data structure selection’), systems that synthesise data structure implementations given an abstract specification (‘Generalized data structure synthesis’), systems that ... Continue Reading

Moment-based quantile sketches for efficient high cardinality aggregation queries

Moment-based quantile sketches for efficient high cardinality aggregation queries Gan et al., VLDB'18 Today we’re temporarily pausing our tour through some of the OSDI’18 papers in order to look at a great sketch-based data structure for quantile queries over high-cardinality aggregates. That’s a bit of a mouthful so let’s jump straight into an example of ... Continue Reading

Generalized data structure synthesis

Generalized data structure synthesis Loncaric et al., ICSE'18 Many systems have a few key data structures at their heart. Finding correct and efficient implementations for these data structures is not always easy. Today’s paper introduces Cozy (https://cozy.uwplse.org), which can handle this task for you given a high-level specification of the state, queries, and update operations ... Continue Reading