Beringei

View Current Viewing Revision #6 from 12/07/2019 6:37 p.m.

Beringei is an embedded in-memory storage engine for time series data developed by Facebook. It was developed by Facebook to handle the growing scale of their system health monitoring data, as they needed a faster solution to storing constant stream of time series data, as well as a fast way to query this data.

History

The original name of the system was called Gorilla. The architecture was described in a VLDB 2015 research paper. The project was then open-sourced in 2017 and then discontinued in 2018. The original solution to handling monitoring data was an HBase-backed TSDB (Time series database), but the primary issues revolved around slow aggregate queries, and slow writes.

Beringei features a time series compression algorithm that on average compresses each time series by 12x, without loss of resolution as some lossy compression algorithms would do, and works with double precision floating point values that are present in monitoring time series data.

The algorithm was derived from the floating point data compression scheme in scientific computation, that leverages XOR's with previous values to generate a delta encoding. Beringei does not do additional compression across the time series outside of this delta encoding. Each data point in the time series, the time stamp and the value, are represented by a pair of 64 bit values. Each timestamp/value is compressed separately, by using XOR's with the previous timestamp/value. The crux of the idea is that once we have stored the initial value, values following can XOR themselves with the previous value, and obtain the number of significant bits in difference, which is then encoded with a header that serializes the difference.

Time Stamp Compression

Beringei uses a "delta of deltas" compression for time stamps, as most time stamp data points are sent at a fixed interval. This allows the database to store the difference in time stamp, rather than the whole time stamp. It uses a simple schema for variable length encoding of time stamps after storing the initial time stamp, and the overall result is that 96% of time stamps can be compressed to a single bit.

Value Compression

Beringei compresses values in addition to time stamps. It uses the aformentioned XOR floating point compression with a variable length encoding scheme to store its values.