All posts

Meta's time series compression algorithm reduces memory requirements by 12x

The engineering team at Meta used a practical difference-of-differences algorithm, to reduce their time series memory footprint from 16 bytes to less than 2 bytes.

Gaurav Sen/5 min read

Here are two compression algorithms that Meta uses to efficiently store time series data.

What is a time series?

For the uninitiated, time series data is a set of key-value pairs, where the key is a timestamp and the value is a number.

Like website visits per day.

Time series graph
  1. A typical time series, with timestamps in the x-axis of and values in y-axis

Looking at this time series, you can tell how well the website is performing. Time series data is particularly useful for operations and business use cases.

With enough data, you may describe user behavior, like users preferring to come on weekends.

With more data, you could predict behavior, like the number of users who will come on a weekend.

With even more data, you could prescribe behavior, like giving discounts on weekends, which would result in increased sales.

How does Meta store time-series data?

Meta uses a system called GorillaDB to store its time series data. This is an in-memory database.

An in-memory database is fast. Meta uses this characteristic to quickly detect and report critical bugs.

But main memory is expensive, and Meta has petabytes of data.

Storing data in its raw format is infeasible. Meta engineers use compression algorithms to make GorillaDB's memory footprint feasible.

The algorithm

To compress the data inside a time series, Facebook uses two separate algorithms.

1. Compression of timestamps

Timestamps are the x-values in the above graph. Note that they are equally spaced since the values of a time series are regularly emitted by clients.

Let's plot these points on a graph.

Timestamp values
2. Timestamps values in the series. They are regularly increasing.

Differentiate once.

Timestamp differences
3. Difference values between adjacent timestamps

Differentiate again.

Timestamp second order difference
  1. Second-order differences of timestamp values are mostly zero (the acceleration of timestamp values is zero).

See? Nearly all points are zero. That's because timestamps have regular intervals. Unless we have a clock skew or a system fault, data will flow into the system in regular intervals.

So our algorithm to compress timestamps runs as follows:

  1. Take the difference-of-difference in each timestamp.
  2. Apply Nonzero run length encoding on the column.

That's it. Meta used this simple algorithm to compress 90% of all timestamps into a single bit (zero)!

2. Compression of values

Let's look at the values table. You will notice that values tend to increase or decrease gradually.

This means that the difference between any two adjacent values is likely to be small. Meta uses this characteristic to build the following algorithm.

  1. Take the XOR difference of each adjacent value.
  2. Compress the leading and trailing zeros of this column.
XOR difference between adjacent values
  1. XOR difference between adjacent values has the same number of leading zeros.

Why does this work? As we said, the increase in value per timestamp is usually small. This means the entire time series has an equal number of leading zeros.

Meta notes that 52% of all time-series values are compressed to zero!

The effect

Meta's compression algorithm reduces their memory requirements by 12x.

This astounding result helps them keep recent time-series data in memory, resulting in fast error detection and low response times.

To know more about system design, check out our course at InterviewReady.

Cheers!

References

  1. What is a time series database.
  2. Requirements of a time series database.
  3. Time series data schema.
  4. Compression algorithms.