Skip to content
Redis Object Encodings Deep Dive: SDS, Listpack, Skiplist Memory-Performance Tradeoffs
Databases 33 min read

Redis Object Encodings Deep Dive: SDS, Listpack, Skiplist Memory-Performance Tradeoffs

This article analyzes Redis's internal object encodings (SDS, listpack, skiplist, hashtable, intset, quicklist), their automatic conversion thresholds, memory overhead calculations, and practical pitfalls like silent encoding upgrades that quadruple memory usage, providing a framework for choosing data structures and diagnosing production issues.

Architecture Pony
Architecture Pony
Architecture Pony

Three Production Accidents Illustrating Encoding Risks

The article opens with three real-world incidents:

Wrong type for leaderboard: Using a List for a 100k-user ranking with LRANGE 0 -1 (O(N)) blocked the single thread for ~10 ms per call, raising P99 from 3 ms to 90 ms. Switching to ZSET ( ZADD O(log N), ZREVRANGE O(log N+M)) eliminated the problem.

Silent encoding conversion: A cart hash using listpack automatically converted to hashtable when fields exceeded 128, quadrupling memory overnight with no errors or logs — only OBJECT ENCODING revealed the change.

Large value blocking the event loop: A 3 MB HTML string cached as a raw string caused 600 MB/s network copy at 200 QPS; a mistaken GETRANGE 0 -1 held the thread for 30 ms, queuing all connections.

Core Concepts: Type vs Encoding vs Conversion

Type (string/list/hash/set/zset) is the external API; encoding is the internal data structure chosen automatically by Redis; conversion happens when element count or size crosses thresholds, silently changing memory and latency characteristics.

Type × Encoding Landscape

string: int / embstr / raw

hash: listpack / hashtable

list: quicklist (nodes are listpacks)

set: intset / listpack / hashtable

zset: listpack / skiplist

SDS: Byte-Level String Engineering

Redis 7 SDS uses variable-length headers: 1 byte for len<32 (sdshdr8), 2 bytes for <256, 4 bytes for <65536, 8 bytes beyond. Flags store header type. A 20-byte string costs 1+20+1=22 bytes vs C string's implicit strlen scan.

String encodings:

int — value fits in long; stored directly in robj pointer, no SDS allocation.

embstr — length ≤44 bytes; robj (16B) + SDS header (3B) + content + null terminator = 64B, exactly one jemalloc bucket. Single allocation, cache-friendly, read-only — any write (APPEND, SETRANGE) converts to raw.

raw — longer strings; two allocations (robj + SDS).

The 44-byte limit comes from: 64B bucket - 16B robj - 3B sdshdr8 - 1B terminator = 44B.

Dict: Two Tables & Progressive Rehash

Dict always maintains two hash tables ht[0] and ht[1]. Normally only ht[0] is used. When load factor (size/used) exceeds 1 (or 5 during BGSAVE/BGREWRITEAOF to limit COW), ht[1] is allocated and each operation migrates one bucket. Reads check both tables; new inserts go only to ht[1]. Expansion uses next power of two (e.g., 100k entries → 131072 buckets). Shrinkage (load factor <0.1) is also progressive. Collisions use chained lists; SipHash key distribution affects performance.

Listpack & Quicklist: Two-Level Compact Design

Listpack (replaced ziplist in 7.0) stores elements contiguously: encoding tag + content + backlen. backlen records only the element's own encoded length, enabling reverse traversal without ziplist's prevlen field that caused cascade updates. For N≤128, sequential scan beats hash due to cache locality.

Quicklist wraps listpack nodes in a doubly-linked list (default node max 8KB, configurable via list-max-listpack-size). Insert: if current node has space, append to its listpack (memcpy); else allocate new node. This hybrid gives O(1) push/pop at ends and compact storage.

Skiplist: Why Not Red-Black Tree?

ZSET large encoding uses skiplist + dict dual structure: skiplist for ordered range queries ( ZRANGEBYSCORE), dict for O(1) member→score lookup ( ZSCORE). Author's three reasons for skiplist:

Simpler implementation, fewer bugs in range queries.

Probabilistic balance — no rotations, shorter write path.

Lock-free friendly (though single-threaded), and span caching enables O(log N) ZRANK.

Each node promotes to next level with 25% probability, max 32 levels. Expected search O(log N). Memory overhead ~1/3 of member length for pointers; not smaller than RB-tree but wins on write speed and range semantics.

Encoding Conversion Thresholds (Must-Know Table)

hash: fields >128 or single value >64B → listpack → hashtable

set: all integers ≤512 → intset; else hashtable

zset: elements >128 or single value >64B → listpack → skiplist

list: controlled by list-max-listpack-size (default 8KB per node)

string: integer → int; ≤44B → embstr; else raw; embstr write → raw

Two tunable params: hash-max-listpack-entries / hash-max-listpack-value. Not recommended to change — 128/64 balanced from real workloads; larger listpack increases write amplification (full block memcpy). Conversion is one-way only — never reverts; recovery requires DEL + rewrite.

HSET Encoding Decision Walkthrough

For HSET cart:1001 sku:88 count:

Key missing → create hash object with default listpack encoding.

Append to listpack tail (memcpy, O(N) but N small).

Before each write, check conversion conditions: fields >128? value >64B?

If triggered, hashTypeConvert expands entire listpack into dict, migrating field by field.

Subsequent ops use hashtable: SipHash → bucket → chained list.

Never reverts to listpack.

AOF logs original HSET; replay re-decides encoding based on data at replay time.

Four Key Understandings

Encoding decision happens on write path (two integer compares, negligible cost).

Conversion is a one-shot bulk migration — large key conversion causes observable pause.

AOF/RDB store semantics, not encoding; replay may produce different encoding under new version/thresholds.

Read path has zero decision logic — once stable, performance is predictable.

Core Source Code Snippets

4.1 robj — 16-Byte Object Header

typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:24; int refcount; void *ptr; } robj;

Bitfields: type (5 types), encoding (enum), LRU (24-bit clock for eviction), refcount (shared integers 0-9999). All commands read type/encoding first, then dispatch via function table — C-style polymorphism.

4.2 hashTypeLookupWriteOrCreate — Encoding Fork

robj *o = lookupKeyWrite(c->db, c->argv[1]); if (o == NULL) { o = createHashObject(); // encoding = OBJ_ENCODING_LISTPACK } else { if (hashTypeConvert(o) == C_ERR) ... }

New objects always start with most compact encoding — "start compact, expand on overflow" is universal strategy.

4.3 hashTypeConvert — One-Shot Migration

int hashTypeConvert(robj *o) { if (o->encoding == OBJ_ENCODING_LISTPACK) { hashTypeConvertListpack(o, OBJ_ENCODING_HT); // iterate fields, dictAdd, no rollback } return C_OK; }

Entire listpack expanded in one command; no progressive rehash here.

4.4 zslInsert — Skiplist Insert in ~17 Lines

for (i = level-1; i >= 0; i--) { while (x->level[i].forward && (score compare)) x = x->level[i].forward; rank[i] = rank; } level = zslRandomLevel(); // dice roll if (level > sl->level) { // add new level forward pointers } // insert pointers, update span

No rotations, no recoloring. span stores nodes skipped per level; ZRANK accumulates span during descent.

4.5 quicklistInsertAfter — Two-Level Write Path

if (quicklistNodeSize < fill) { listpackInsert(entry); // insert inside node } else { quicklistCreateNode(); __quicklistInsertNode(ql, node); }

All complexity condensed: pack while space exists (compact), else new node (O(1) link). Explains why LPUSH fast, LINSERT slow (must locate position first).

Advanced: Quantifying Memory & Latency

5.1 Memory Accounting: listpack vs hashtable

100 fields × 20 bytes each:

listpack: ~3 KB — contiguous, 2-3 byte per-element header, zero pointers/buckets.

hashtable: ~11 KB — 256 buckets × 8B pointers, each field a dictEntry (24B) + two SDS headers + allocator alignment waste.

3-4× difference; smaller fields widen gap. Threshold 128 exists because O(N) scan at N≤128 is faster than hash constant overhead.

Allocator factor: jemalloc fixed buckets (64/128/256B...). listpack single allocation; hashtable many small allocations each paying alignment tax (~2 KB extra for 100 fields). Estimate real memory as theoretical ×1.3; use MEMORY USAGE for truth.

5.2 One-Way Conversion: Recovery Strategies

Fix for accident #2: split large hash, not tune thresholds. Decision tree:

Fields long-term >128 → design for hashtable (accept memory, use HSCAN).

Fields fluctuate near 128 → split by business dimension (e.g., SKU category) to keep each in listpack.

Few fields but large values → store values as separate strings, hash holds references.

Per-key design beats global params because thresholds affect all keys.

5.3 Command Complexity Cheat Sheet (for Code Review)

ZADD/ZSCORE

O(log N) / O(1) ZRANGE BYSCORE O(log N+M) LRANGE O(S+N) (S=offset) LINSERT O(N) (locate first) SMEMBERS O(N) (full return) SRANDMEMBER O(N) / O(1) HGETALL O(N) (fields) KEYS / SORT / DEBUG — production banned

Rule: any command with 0 -1 on potentially large collections must be reviewed. Replace SMEMBERS with SSCAN, HGETALL with HSCAN, full LRANGE with pagination.

5.4 Observation Toolkit: Three OBJECT Axes

Encoding distribution: sample 100 keys per type at peak, run OBJECT ENCODING; abnormal hashtable ratio signals accident #2.

Access pattern: OBJECT FREQ (hot keys worth optimizing), OBJECT IDLETIME (candidates for cleanup).

Memory budget: MEMORY USAGE key average × estimated key count ≈ budget; 2× gap indicates fragmentation, conversion, or expired keys not reclaimed.

5.5 30-Second Encoding Health Script

redis-cli --scan --pattern 'cart:*' | head -100 | while read key; do redis-cli object encoding "$key" done | sort | uniq -c

Output: count of listpack vs hashtable. Hashtable % = direct accident #2 risk metric. Schedule per business prefix; trend (2% → 15%) reveals data shape changes before monitoring alerts.

5.6 Eight Common Pitfalls

embstr high-frequency writes: each write converts to raw + realloc; counters must use int + INCR.

Single field >64B converts whole hash: large values belong in separate strings.

One string in SET destroys intset: entire set converts to hashtable.

list-max-listpack-size too large: 32KB node saves memory but write amplification spikes.

Unbounded list as queue: LPUSH growth + slow LPOP → linear memory; use LTRIM or Stream.

Large ZSET members: skiplist + dict store member twice; store IDs, fetch details elsewhere.

Blindly splitting hash fields: near 128 fields, split may trigger conversion; verify with MEMORY USAGE.

Using KEYS for sizing: blocks server; use INFO keyspace or SCAN cursor iteration.

Learning Path & Interview Framework

Four-Stage Roadmap

Beginner (3 days): manually trigger conversions (127 vs 129 fields), compare OBJECT ENCODING and MEMORY USAGE.

Intermediate (1 week): validate 44-byte magic with allocator stats; produce production encoding health report.

Deep (2 weeks): read

t_hash.c
hashTypeConvert

and

t_zset.c
zslInsert

; implement mini skiplist (30 lines) to verify level dice & span accumulation.

Ongoing: structure audit — every list/hash/set/zset: type choice, field scale, full-read commands; remediate per complexity cheat sheet.

Five-Part Answer Framework for Structure Questions

Type/encoding separation.

Compact encodings (listpack/intset/embstr) for small data.

Threshold upgrade to scalable structures (hashtable/skiplist).

One-way conversion.

Command complexity dictated by encoding; KEYS/full-read are red lines.

20 Interview Q&A (Condensed)

Key answers include: SDS O(1) strlen, binary safety, prealloc; embstr 44B = 64B bucket - 16B robj - 3B header - 1B terminator; progressive rehash reads both tables, writes to ht[1], migrates one bucket per op; listpack beats hashtable for N≤128 due to cache locality; listpack eliminates ziplist cascade updates via backlen; list = quicklist (linked list of listpack nodes); skiplist chosen for simplicity, no rotations, range queries via bottom list; dict in ZSET provides O(1) point lookup; conversion thresholds (128/64B) one-way; OBJECT three axes for production; intset for all-int sets ≤512; refcount shares 0-9999 integers; single large hash vs many small hashes memory math; LRANGE 0 -1 cost = skip + copy + network; skiplist level 25% promotion, max 32, probabilistic O(log N); SipHash prevents collision DoS; shrinkage returns memory to allocator pool not OS; KEYS blocks, SCAN cursor safe but may duplicate; tuning thresholds trades write amplification for memory; leaderboard→ZSET, cart→hash (watch 128), counter→int+INCR.

One-Page Cheat Sheet

type is facade, encoding is internals<br>small uses listpack, large swaps to hashtable<br>skiplist rolls dice, range query O(log N)<br>embstr forty-four, one write turns raw<br>conversion one-way door, reclaim via rewrite<br>thresholds 128 / 64B, cross and memory doubles

Summary

This article exhaustively covers Redis's data structure encodings — SDS variable headers & 44-byte magic, dict dual-table progressive rehash, listpack backlen & cascade-update fix, quicklist two-level compromise, skiplist dice-roll & dual-index with dict — all unified by the theme of precise memory-vs-speed tradeoffs governed by hard thresholds executed on the write path. Three decision rules: choose type by access pattern, watch 128/64 thresholds, ban full-collection reads via complexity table.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

Memory OptimizationRedisEncodingperformance tuningData StructuresSDSSkiplistListpack
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.