cockroachdb/cockroach — pull request #242 by mrtracy (2014-12-21 15:02:04+00:00)
Title: InternalTimeSeries improvements

This commit introduces significant improvements to the underlying storage for
time series data.

The existing `TimeSeriesData` has been renamed to `InternalTimeSeriesData`,
indicating that it is used for internal storage of time series; the name
"TimeSeriesData" is reserved for a forthcoming externally-facing protobuffer.
This message has also been simplified; it now contains only a start timestamp
and a "sample duration" expressed in milliseconds, along with the repeated
samples.

`TimeSeriesDataPoint` is now `InternalTimeSeriesSample`, and stores
significantly more data than before. Each sample represents the aggregated data
from measuring a statistic over an interval of time; the duration of this
interval is the "sample duration" of the InternalTimeSeriesData the sample is a
part of. Each sample stores the sum of all measurements, the count of all
measurements, and the max and min of any individual measurement taken. Data can
be stored as either integer or floating points. This new design greatly
enhances our ability to create data rollups. It will also mitigate idempotency
concerns to a degree, as even the smallest interval can have multiple
measurements.

Finally, the merge logic for time series has been significantly altered; it will
now automatically sort and aggregate merged samples. No matter what order
samples are merged into an InternalTimeSeriesData key, when read they will be in
sorted order with duplicates (determined by offset) accumulated into a single
sample.

In order to make this efficient, the merge logic for TimeSeries now behaves
differently for partial merges; partial merges simply "concatenate" consecutive
merged samples, with sorting and aggregation only performed at the FullMerge
phase. Without this, merging individual samples would result in effectively
O(n^2) behavior.