Scene 03

Encodings flip under you

Each Redis type has multiple internal encodings chosen by size, and crossing a threshold silently rewrites memory layout and operation 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
Try it
Predict
Capture

What to watch for

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

Highlighted lines are the ones running in the diagram right now.

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)

Sources

Where this sits in Build Redis

Scene 03 of 10, in the The loop act — One thread, one command — and the encoding under it.. Listpack ↔ hashtable, intset ↔ hashtable, embstr ↔ raw — crossing a threshold silently rewrites memory and op-cost.

Up next. Persistence — those carefully encoded bytes only live in RAM. Persistence is how Redis turns RAM into something that can survive a crash.

All 10 scenes in Build Redis · Every curriculum

Designs that use this

Built with Arqly

Every scene in Build Redis builds on the one before it.All 10 Build Redis scenes