Internal Encodings

## Type versus encoding Redis exposes five core data types plus a few specialised ones. `TYPE mykey` returns the logical type — what commands you may run. `OBJECT ENCODING mykey` returns something different: the concrete memory layout the server picked for that particular value right now. The same `HSET`/`HGET` API works identically whichever encoding is underneath; the encoding is an invisible optimisation. ``` > RPUSH mylist a b c > OBJECT ENCODING mylist "listpack" > TYPE mylist list ``` ## Why a general structure is wasteful for small values A hash table in C is an array of buckets holding pointers to entries; each entry holds a key pointer, a value pointer and a next pointer. Add the allocator's per-allocation header and the Redis string (SDS) header on both key and value, and a single field/value pair of a few bytes can cost on the order of 50–100 bytes of *overhead*. For a hash representing a user session with six short fields, that is an order of magnitude more memory than the payload. This matters more in Redis than in most systems because Redis is an in-memory store: RAM *is* the cost model, and real deployments hold tens or hundreds of millions of small objects. A representation that halves per-object overhead halves the bill. ## The compact encodings - **listpack** — a single contiguous byte blob containing entries one after another, each prefixed with its own length metadata so the blob can be traversed in either direction. There are no pointers and one allocation for the whole collection. Used for small hashes, small sorted sets, small sets, and small lists. It replaced the older **ziplist**, which had the same idea but a design that made some updates prone to cascading size recalculation. - **intset** — for sets whose members are *all* integers: a sorted array of fixed-width integers (16, 32 or 64 bit, upgraded as needed). Membership is a binary search; memory is essentially just the numbers. - **embstr** — for short strings (44 bytes or fewer): the object header and the string data are allocated together in one block, so creating and freeing it is one allocation instead of two. Longer strings use `raw` (two allocations); strings that are valid integers are stored as `int`, a plain long inside the object. The cost of a compact encoding is that operations are **O(n) in the number of entries**, since you scan the blob. That is deliberately fine because n is capped by configuration — and for small n, a linear walk over contiguous memory is faster in wall-clock terms than hashing plus a pointer dereference, because it touches one or two cache lines instead of jumping around the heap. ## The general encodings - **hashtable** — the real dict, used for large hashes and large sets; O(1) average lookup, incremental rehashing when it grows. - **skiplist** — used for large sorted sets, giving O(log n) range and rank operations. A sorted set in `skiplist` encoding actually keeps *two* structures: the skiplist for ordering and a dict for O(1) member → score lookup. - **quicklist** — used for large lists: a doubly linked list whose nodes are themselves listpacks, so you get cheap push/pop at both ends without one allocation per element. ## How and when Redis switches Conversion is driven by per-type configuration thresholds — element count and the size of any individual element (for example `hash-max-listpack-entries` and `hash-max-listpack-value`, defaulting to 128 and 64). When a write pushes a collection past either limit, Redis converts the value in place to the general encoding. Two properties matter in practice. First, the check is on *any* element: one 200-byte field converts an otherwise tiny hash. Second, **conversion is one-way**: delete elements back down below the threshold and the encoding stays `hashtable`. Redis does not downgrade, because oscillating around the boundary would cost more than it saves. To get the compact encoding back you must recreate the key. ## Why you should care As a developer you rarely choose an encoding directly, but encoding explains two very common observations: why a million tiny keys use far more memory than the sum of their values (top-level keys always carry full object overhead, so grouping them into hashes that stay listpack-encoded is a large win), and why one key that looks small behaves slowly (a listpack that was allowed to grow, or a value stuck in a general encoding). `OBJECT ENCODING` plus `MEMORY USAGE <key>` is the first pair of commands to reach for when memory or latency surprises you.