Listpack is a memory-efficient format to store a list of strings. It's a single, contiguous block of memory, which is great for cache performance.
- Header (6 bytes): The first 4 bytes store the total size of the listpack, and the next 2 bytes store the number of elements.
- Entries: Each entry consists of an encoding-type, the element-data, and a backlen.
-
Encoding: Listpack uses variable-length encoding for both integers and strings to save space. The specific type is chosen based on the value or byte length of the data:
- Integers: Stored as
7-bit, 13-bit, 16-bit, 24-bit, 32-bit, or 64-bit values.
- Strings: Length is stored using
6-bit, 12-bit, or 32-bit encodings based on the string's byte length.
- Backlen: This is the magic for traversing backward! It stores the length of the *previous* entry, allowing efficient navigation from tail to head. It's also variable-length encoded.
- EOF (1 byte): A final `0xFF` byte marks the end of the listpack.