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.
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.
2. Timestamps values in the series. They are regularly increasing.
Differentiate once.
3. Difference values between adjacent timestamps
Differentiate again.
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:
- Take the difference-of-difference in each timestamp.
- 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.
- Take the XOR difference of each adjacent value.
- Compress the leading and trailing zeros of this column.
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!