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.
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 spanNo 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/ZSCOREO(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 -cOutput: 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.chashTypeConvertand
t_zset.czslInsert; 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.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
