<commit_before>---
layout:     post
title:      Time-series storage design (part two)
date:       2015-02-05 10:33:00
summary: Let's talk about compression algorithms. You probably know that DBMS can be row-oriented or column-oriented. Both have some strengths and weaknesses. Row-oriented has higher write throughput and ...
categories: akumuli
---

Time-series storage design (part two)

Let's talk about compression algorithms. You probably know that DBMS can be row-oriented or column-oriented. Both have some strengths and weaknesses. Row-oriented has higher write throughput and not so great compression. Column-oriented DBMS on the other hand has lower write throughput and better compression. This can be achieved because data in each column is uniform. We can compress all the timestamps using one algorithm and all the IDs using another one that's better suited for IDs.

Akumuli is row-oriented in the sense that every chunk is a row. But on the other hand every chunk is column-oriented. This gives us both high write throughput and good compression ratio.

#### Compression algorithms

Akumuli uses several compression algorithms for different column types.
- Timestamps compressed using Delta encoding followed by RLE. This is great because timestamps is always increasing thus can be easily compressed by delta-encoding. Time-series data is often have periodic nature. In this case delta encoding will give us series of equal numbers that can be compressed by RLE very efficiently! Delta-RLE encoded data then encoded by the [LEB128 algorithm](http://en.wikipedia.org/wiki/LEB128). Implementation can be [found here](https://github.com/akumuli/Akumuli/blob/master/libakumuli/src/compression.h).
IDs compressed using LEB128 encoding. In this scheme small IDs (less then 128) - will occupy single byte and larger IDs will occupy two or more bytes.
- Data offsets (used for binary BLOBs) compressed using delta encoding followed by zig-zag, RLE and finally LEB128 encoding. We need zig-zag encoding because offsets can go out of order sometimes and delta-encoding can produce negative numbers. For numeric values this column contains zeroes (most values in the chunk should be numeric) thus can be compressed by the RLE encoder very good.
- The most interesting part is a numeric values! Let's look at it more closely.

#### Numeric data compression algorithm
My compression algorithm is based on [this paper](http://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf). If we have array of floating-point values we can't delta-encode them because precision will be lost. Instead of that we can XOR two adjacent values and get binary diff. In the case of numeric time series we will get some 64bit number with leading zeroes. This number can be encoded using small amount of memory.

Akumuli uses four bits to represent length of the number and sequence of four bit numbers to encode binary diff. Paper describes slightly more complex algorithm that uses forecasting to predict new value. Predicted and actual value used to calculate binary diff. This diff should be smaller then diff between previous and new value. I'm not using this because it's harder to implement and simple algorithm gives very good results.

Floating-point compression algorithm implementation [can be found here](https://github.com/akumuli/Akumuli/blob/master/libakumuli/src/compression.cpp#L45). It uses `__builtin_clzl` compiler intrinsic function to count leading zeroes for better performance.

#### Lies and benchmarks
In my tests this specialized compression algorithms give up to 50% better compression ratio then generic compression algorithm (gzip).<commit_msg>add links to post<commit_after>---
layout:     post
title:      Time-series storage design (part two)
date:       2015-02-05 10:33:00
summary: Let's talk about compression algorithms. You probably know that DBMS can be row-oriented or column-oriented. Both have some strengths and weaknesses. Row-oriented has higher write throughput and ...
categories: akumuli
---

Let's talk about compression algorithms. You probably know that DBMS can be row-oriented or column-oriented. Both have some strengths and weaknesses. Row-oriented has higher write throughput and not so great compression. Column-oriented DBMS on the other hand has lower write throughput and better compression. This can be achieved because data in each column is uniform. We can compress all the timestamps using one algorithm and all the IDs using another one that's better suited for IDs.

Akumuli is row-oriented in the sense that every chunk is a row. But on the other hand every chunk is column-oriented. This gives us both high write throughput and good compression ratio.

#### Compression algorithms

Akumuli uses several compression algorithms for different column types.
- Timestamps compressed using [Delta encoding](http://en.wikipedia.org/wiki/Delta_encoding) followed by [RLE](http://en.wikipedia.org/wiki/Run-length_encoding). This is great because timestamps is always increasing thus can be easily compressed by delta-encoding. Time-series data is often have periodic nature. In this case delta encoding will give us series of equal numbers that can be compressed by RLE very efficiently! Delta-RLE encoded data then encoded by the [LEB128 algorithm](http://en.wikipedia.org/wiki/LEB128). Implementation can be [found here](https://github.com/akumuli/Akumuli/blob/master/libakumuli/src/compression.h).
IDs compressed using LEB128 encoding. In this scheme small IDs (less then 128) - will occupy single byte and larger IDs will occupy two or more bytes.
- Data offsets (used for binary BLOBs) compressed using delta encoding followed by [ZigZag encoding](https://developers.google.com/protocol-buffers/docs/encoding#types), RLE and finally LEB128 encoding. We need ZigZag encoding because offsets can go out of order sometimes and delta-encoding can produce negative numbers. For numeric values this column contains zeroes (most values in the chunk should be numeric) thus can be compressed by the RLE encoder very good.
- The most interesting part is a numeric values! Let's look at it more closely.

#### Numeric data compression algorithm
My compression algorithm is based on [this paper](http://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf). If we have array of floating-point values we can't delta-encode them because precision will be lost. Instead of that we can XOR two adjacent values and get binary diff. In the case of numeric time series we will get some 64bit number with leading zeroes. This number can be encoded using small amount of memory.

Akumuli uses four bits to represent length of the number and sequence of four bit numbers to encode binary diff. Paper describes slightly more complex algorithm that uses forecasting to predict new value. Predicted and actual value used to calculate binary diff. This diff should be smaller then diff between previous and new value. I'm not using this because it's harder to implement and simple algorithm gives very good results.

Floating-point compression algorithm implementation [can be found here](https://github.com/akumuli/Akumuli/blob/master/libakumuli/src/compression.cpp#L45). It uses `__builtin_clzl` compiler intrinsic function to count leading zeroes for better performance.

#### Lies and benchmarks
In my tests this specialized compression algorithms give up to 50% better compression ratio then generic compression algorithm (gzip).
{'fraction_non_alphanumeric': 0.0523419675211381, 'fraction_numerical': 0.009931552811703126, 'mean_word_length': 4.63265306122449, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6252362', 'n_tokens_mistral': 1848, 'n_tokens_neox': 1711, 'n_words': 1020}