Every large company watches itself. Servers report their load, queues report their length, and apps report errors, all the time. Each report is a number with a timestamp, and together they form huge streams called time series. When something breaks, an engineer needs to look at the last few hours of these numbers right now.
Facebook's 2015 paper describes Gorilla, an in-memory time series database for exactly this job. It says that as of spring 2015 their monitoring systems produced more than 2 billion unique time series, with about 12 million data points added per second, which is over a trillion points a day. At 16 bytes a point, that is a lot of memory, so Gorilla compresses aggressively. The compression tricks are short and beautiful.
Gorilla keeps the most recent data in memory, because recent points matter most when diagnosing a problem. It shrinks each series with two ideas. Store timestamps as the change in the change, which is usually zero, using one bit. Store values as the XOR with the previous value, which is mostly zeros, so only the middle bits are kept.
A database tuned for what people actually look at
The authors' insight is about how monitoring is used. Engineers care about aggregates and trends, not single points. Recent points are far more valuable than old ones. So Gorilla chooses to stay highly available for reads and writes even when machines fail, at the price of possibly dropping a small amount of data on the write path.
- Write-through cache. Gorilla sits in front of a long term store (HBase) and holds the most recent 26 hours of data.
- Two copies. The data lives in two in-memory replicas that are not in the same place, for disaster recovery.
- Sharding by key. Each time series has a unique string key, so each series maps to one Gorilla host.
Each data point is a 64 bit timestamp and a 64 bit floating point value. The memory saving comes from how those two numbers are written down.
Timestamps: the change in the change
The authors noticed that almost every series arrives at a fixed interval, such as one point every 60 seconds. Sometimes a point is a second early or late, but the window is tight. So instead of storing each timestamp, Gorilla stores the delta of deltas: the difference between this gap and the previous gap.
