| 1 | # Gorilla compression and decompression |
| 2 | |
| 3 | This provides an alternative way of representing values stored in database |
| 4 | pages. Instead of allocating and using a page of fixed size, ie. 4096 bytes, |
| 5 | the Gorilla implementation adds support for dynamically sized pages that |
| 6 | contain a variable number of Gorilla buffers. |
| 7 | |
| 8 | Each buffer takes 512 bytes and compresses incoming data using the Gorilla |
| 9 | compression: |
| 10 | |
| 11 | - The very first value is stored as it is. |
| 12 | - For each new value, Gorilla compression doesn't store the value itself. Instead, |
| 13 | it computes the difference (XOR) between the new value and the previous value. |
| 14 | - If the XOR result is zero (meaning the new value is identical to the previous |
| 15 | value), we store just a single bit set to `1`. |
| 16 | - If the XOR result is not zero (meaning the new value differs from the previous): |
| 17 | - We store a `0` bit to indicate the change. |
| 18 | - We compute the leading-zero count (LZC) of the XOR result, and compare it |
| 19 | with the previous LZC. If the two LZCs are equal we store a `1` bit. |
| 20 | - If the LZCs are different we use 5 bits to store the new LZC, and we store |
| 21 | the rest of the value (ie. without its LZC) in the buffer. |
| 22 | |
| 23 | A Gorilla page can have multiple Gorilla buffers. If the values of a metric |
| 24 | are highly compressible, just one Gorilla buffer is able to store all the values |
| 25 | that otherwise would require a regular 4096 byte page, ie. we can use just 512 |
| 26 | bytes instead. In the worst case scenario (for metrics whose values are not |
| 27 | compressible at all), a Gorilla page might end up having `9` Gorilla buffers, |
| 28 | consuming 4608 bytes. In practice, this is pretty rare and does not negate |
| 29 | the effect of compression for the metrics. |
| 30 | |
| 31 | When a gorilla page is full, ie. it contains 1024 slots/values, we serialize |
| 32 | the linked-list of gorilla buffers directly to disk. During deserialization, |
| 33 | eg. when performing a DBEngine query, the Gorilla page is loaded from the disk and |
| 34 | its linked-list entries are patched to point to the new memory allocated for |
| 35 | serving the query results. |
| 36 | |
| 37 | Overall, on a real-agent the Gorilla compression scheme reduces memory |
| 38 | consumption approximately by ~30%, which can be several GiB of RAM for parents |
| 39 | having hundreds, or even thousands of children streaming to them. |