Encodings flip under you

Scene 03 · Encodings flip under you

Listpack ↔ hashtable, intset ↔ hashtable, embstr ↔ raw — crossing a threshold silently rewrites memory and op-cost.

Previously

One loop, one command at a time. So the cost of a single command — and therefore everyone else's wait — depends on the SHAPE of the value the loop is touching.

Scene 03

Encodings flip under you

Watch

Diagram

One Redis key on the left with a size dial you control — add or remove entries to change how big it is. The center shows the current internal encoding (listpack/intset/embstr when small, hashtable/skiplist when large) and the byte-cost badge updates as you cross the threshold. A small big-O label on the right marks the operation cost that flips with the encoding.

Sources

Watch a hash grow one field at a time. It starts as a single contiguous listpack — one allocation, ideal cache locality. When the entry count crosses the threshold, the layout morphs into a chained hashtable.

Implementation

Hash.hset

every HSET checks the threshold before appending

1def hset(key, field, value):
2    h = lookupOrCreateHash(key)
3    if h.encoding == 'listpack':
4        # both knobs gate the encoding; either trips the flip
5        if (h.entryCount + 1 > hash_max_listpack_entries
6            or len(value) > hash_max_listpack_value):
7            tryConvertEncoding(h)  # listpack -> hashtable
8    if h.encoding == 'listpack':
9        listpackUpsert(h.lp, field, value)
10    else:
11        dictUpsert(h.ht, field, value)
12    h.entryCount += 1

tryConvertEncoding (listpack -> hashtable)

rehash every entry into a dict; the listpack is freed

1def tryConvertEncoding(h):
2    ht = dictCreate()
3    # walk the contiguous listpack cell by cell
4    for field, value in listpackIter(h.lp):
5        dictAdd(ht, field, value)
6    listpackFree(h.lp)
7    h.lp = None
8    h.ht = ht
9    h.encoding = 'hashtable'  # one-way; never reset on HDEL

Hash.hget

O(N) listpack scan vs O(1) hashtable lookup

1def hget(key, field):
2    h = lookupHash(key)
3    if h is None: return None
4    if h.encoding == 'listpack':
5        # contiguous strip, no index — walk every cell
6        for f, v in listpackIter(h.lp):
7            if f == field: return v
8        return None
9    else:
10        # bucket lookup, pointer chase, ~3x memory
11        return dictFetch(h.ht, field)

PreviousOne thread, one command at a time NextPersistence — fork, CoW, and the 1-second window