Siddhant Deval
Siddhant Deval
Siddhant Deval
backend22 min read

Redis Data Structures & Memory Model: What the Server Actually Stores

Every Redis data structure silently switches between two internal encodings at configurable size thresholds — a compact listpack for small datasets and a performant skiplist or hashtable for large ones. Crossing a threshold mid-traffic triggers an invisible in-place promotion that spikes memory and latency with no log entry. This article deconstructs SDS strings, listpack-to-skiplist transitions, intset encoding chains, the jemalloc fragmentation model, and why KEYS * is a production footgun.

Series·Part 1 of 7

Redis Mastery

Next ChapterRedis Persistence: RDB, AOF & Hybrid Mode — Durability Is Not Free

Redis Data Structures & Memory Model: What the Server Actually Stores

Redis is not a cache you bolt onto a slow database — it is a data structure server with a precisely bounded contract: sub-millisecond latency, in-memory semantics, and optional persistence. The canonical failure mode of this contract is always the same: an engineer calls SET, receives OK, and assumes Redis will remember that value indefinitely, under any memory pressure, through any process restart. The articles in this series exist to replace that assumption with mechanical precision. This first article starts at the foundation — the data structure encodings the server actually uses — because you cannot reason about persistence guarantees, eviction policies, or replication semantics without first understanding what Redis is doing with your data at the byte level.

Architectural Note

This is Part 1 of the Redis Mastery series. It is the entry point for the series and has no prerequisites beyond basic Redis CLI familiarity (GET, SET, DEL). For a surface-level overview of Redis data structure commands, see Specialized Data Stores: Redis, Elasticsearch, Cassandra, Neo4j first — this article covers the internals behind those commands.

1. Key Design & the SCAN Footgun

Before touching encoding internals, there is a production footgun so common it belongs at the top of any Redis article: KEYS *.

BASH
# ❌ Broken pattern: KEYS * in production
redis-cli KEYS "session:*"
# On a Redis instance with 10 million keys, this command:
# 1. Scans the entire keyspace in a single O(N) pass
# 2. Blocks the Redis event loop for the entire duration
# 3. Returns every matching key to the client at once (memory spike)
# Result on a 50M-key instance: ~5 seconds of full server freeze
# Every other client request queues up and times out

Redis is single-threaded for command execution. A command that takes 5 seconds consumes the event loop for 5 seconds. KEYS is that command. It is legitimate in development against a small keyspace. It has no legitimate use in production.

BASH
# ✅ Correct: SCAN with a cursor — non-blocking incremental iteration
redis-cli SCAN 0 MATCH "session:*" COUNT 100
# Returns: [next_cursor, [key1, key2, ...]]
# COUNT 100: hint to Redis to scan roughly 100 entries per call (not guaranteed)
# Repeat with the returned cursor until cursor = 0 (full cycle complete)
# Event loop is not blocked between iterations — other commands run normally
Performance / Safety Warning

SCAN provides weak consistency: keys inserted or deleted during an iteration may appear 0 or 2 times. For cache invalidation workflows this is acceptable. For auditing or exact counts, it is not.

1.1 Production Key Naming Convention

The industry-standard naming schema for Redis keys is:

{namespace}:{entity-id}:{attribute}
BASH
# Examples
session:user:42                   # Session object for user 42
rate:ip:203.0.113.1               # Rate limit counter for an IP
lock:payment:txn-uuid-abc         # Distributed lock for a payment
cache:product:9871:price          # Cached price for product 9871
{user:42}:session                 # Hash-tagged key for Cluster co-location (Part 4)

Key naming rules:

  • Colons as separators — universally recognized convention; allows namespace-aware SCAN MATCH.
  • No spaces — spaces break redis-cli argument parsing.
  • Lowercase — Redis keys are case-sensitive; Session:42 and session:42 are different keys.
  • Bounded length — Redis keys can be up to 512MB but every extra byte is overhead in the key table. Keep keys under 100 bytes.

1.2 Pipelining: N Commands for the Price of One RTT

Every individual Redis command incurs a full TCP round-trip: client sends, server processes, server responds. At 1ms RTT per command, executing 1,000 commands sequentially costs 1,000ms. Pipelining batches those commands into a single write to the socket:

TYPESCRIPT
// ❌ Broken pattern: 1,000 sequential commands = 1,000 × RTT ≈ 1 second
for (const userId of userIds) {
  await redis.get(`session:user:${userId}`) // Each awaits a full network round-trip
}

// ✅ Correct: Pipeline — all 1,000 commands sent in one write, one RTT total
const pipeline = redis.pipeline()
for (const userId of userIds) {
  pipeline.get(`session:user:${userId}`)
}
const results = await pipeline.exec()
// results: [[null, 'value1'], [null, 'value2'], ...]
// First element of each pair: error (null if none)
// Second element: the command's return value
Crucial Requirement

Pipelining is a client-side network optimization. It is not a server-side atomicity mechanism. Commands in a pipeline are not guaranteed to execute without interleaving from other clients — they are simply batched into fewer TCP writes. For atomicity, use MULTI/EXEC or Lua scripts (covered in Part 6).

2. String Internals: SDS, Integer Encoding & the 44-Byte Threshold

When you run SET name "Alice", Redis does not store a C-string. It stores a Simple Dynamic String (SDS) — a custom string type designed to eliminate C-string's limitations: O(N) strlen, unsafe appends, and no binary safety.

2.1 SDS Structure

An SDS string carries its metadata inline:

┌──────────────────────────────────────────┐
│ len (uint8/16/32/64)  — current length   │
│ alloc (uint8/16/32/64) — allocated space │
│ flags (1 byte)        — SDS type (sdshdr5│
│                          sdshdr8, etc.)  │
│ buf[]                 — the actual bytes │
└──────────────────────────────────────────┘

Benefits over C-strings:

  • O(1) length retrieval (no strlen scan)
  • Binary-safe (can store \0 bytes — useful for serialized binary payloads)
  • Pre-allocated space to avoid reallocation on append

2.2 The Three String Encodings

Redis selects one of three internal encodings for a string value:

Encoding Condition Memory layout
OBJ_ENCODING_INT Value is an integer that fits in a long Stored as raw integer in the pointer field — no SDS allocation
OBJ_ENCODING_EMBSTR String length ≤ 44 bytes (Redis 4.0+) Single contiguous allocation: robj + SDS header + content
OBJ_ENCODING_RAW String length > 44 bytes Two separate allocations: robj and SDS separately
BASH
redis-cli SET counter 42
redis-cli OBJECT ENCODING counter
# → "int"

redis-cli SET name "Alice"
redis-cli OBJECT ENCODING name
# → "embstr"  (5 bytes ≤ 44)

redis-cli SET bio "Alice is a senior backend engineer at Acme Corp who specializes in distributed systems"
redis-cli OBJECT ENCODING bio
# → "raw"  (85 bytes > 44)
Crucial Requirement

embstr is immutable. Any modification (e.g., APPEND, SETRANGE) to an embstr string first converts it to raw, even if the result would still fit in 44 bytes. After a single APPEND, OBJECT ENCODING returns raw permanently for that key. This is why you should not use APPEND on high-cardinality session data — each mutation allocates a new separate SDS object.

BASH
redis-cli SET greeting "hello"
redis-cli OBJECT ENCODING greeting
# → "embstr"

redis-cli APPEND greeting " world"
redis-cli OBJECT ENCODING greeting
# → "raw"  — promoted on first mutation, stays raw forever
Pro Tip & Optimization

Store integer counters without quotes: SET hits 0 encodes as int (8 bytes on 64-bit). Storing SET hits "0" forces embstr encoding unnecessarily. For counters using INCR/DECR, the server always operates on the integer representation, but the initial encoding matters for memory at scale.

3. Hash Internals: listpack → hashtable

A Redis Hash (HSET/HGET) is the standard primitive for storing object fields. Its internal encoding depends on the number of fields and their sizes.

3.1 Dual Encoding

Condition Internal Encoding Memory behaviour
Fields ≤ hash-max-listpack-entries (default: 128) AND each value ≤ hash-max-listpack-value bytes (default: 64) listpack Contiguous flat array — compact, cache-friendly, O(N) field lookup
Either threshold exceeded hashtable Hash table with chaining — O(1) average field lookup, higher memory overhead
BASH
redis-cli HSET user:42 name "Alice" role "admin" cartSize 3
redis-cli OBJECT ENCODING user:42
# → "listpack"  (3 fields, well under threshold)

# After adding 129 fields...
for i in $(seq 1 129); do redis-cli HSET user:42 "field$i" "val"; done
redis-cli OBJECT ENCODING user:42
# → "hashtable"  (promoted — this is permanent and irreversible for this key)
Performance / Safety Warning

Encoding promotion is one-way and permanent for a key's lifetime. Once a Hash promotes to hashtable, it will not revert to listpack even if you delete fields below the threshold. The only way to revert is to delete and recreate the key. This means a transient burst of fields — even if immediately cleaned up — causes a permanent memory footprint increase for that key.

3.2 The Threshold Tuning Trade-off

INI
# redis.conf defaults (Redis 7.0+)
hash-max-listpack-entries 128
hash-max-listpack-value   64

Raising hash-max-listpack-entries keeps more Hashes in compact listpack format — saves memory, but increases per-key read CPU cost (O(N) scan vs O(1) hashtable lookup). The right threshold depends on your read pattern:

Workload Recommended threshold Rationale
Write-heavy, rarely read all fields Higher (256–512) Memory savings outweigh O(N) scan cost
Read-heavy, full hash scans common Lower (64) Promote to O(1) hashtable sooner
Fixed small objects (sessions, configs) Default (128) Optimal for typical web backend payloads

4. Sorted Set Internals: listpack → skiplist + hashtable

The Sorted Set (ZADD/ZRANGE/ZRANK) is Redis's most mechanically interesting data structure. It maintains elements in score order while supporting O(1) member score lookup.

4.1 Dual Encoding

Condition Internal Encoding Characteristics
Elements ≤ zset-max-listpack-entries (default: 128) AND each member ≤ zset-max-listpack-value bytes (default: 64) listpack Contiguous (member, score) pairs. O(N) range scans — acceptable for small sets.
Either threshold exceeded skiplist + hashtable Two simultaneous structures sharing the same SDS member objects.
BASH
redis-cli ZADD leaderboard 1500 "alice" 1200 "bob" 900 "carol"
redis-cli OBJECT ENCODING leaderboard
# → "listpack"  (3 members)

# After 129 members...
redis-cli OBJECT ENCODING leaderboard
# → "skiplist"

4.2 The skiplist + hashtable Dual Structure

When a Sorted Set promotes, Redis creates two simultaneous internal structures that reference the same underlying SDS string objects (no string duplication):

skiplist:  Sorted by score → O(log N) ZADD, ZRANGE, ZRANK
hashtable: Maps member → score → O(1) ZSCORE, ZCOUNT membership check

Why a skiplist instead of a balanced BST (AVL, Red-Black)?

Redis chose the skiplist for three reasons:

  1. Range scans: A skiplist's base layer is a linked list — range queries (ZRANGE score1 score2) traverse it linearly, which has better CPU cache locality than an in-order BST traversal.
  2. Simpler implementation: No rotations, no rebalancing. Probabilistic level assignment via coin flip.
  3. The span field: Each skiplist node stores a span value at every level — the number of nodes skipped at that level. This lets ZRANK compute rank in O(log N) by summing spans, not by counting nodes one by one.
skiplist level 3:  [head] ──────────────────────────────────────► [carol:900]  span=3
skiplist level 2:  [head] ──────────────────► [bob:1200]  span=2  [carol:900]  span=1
skiplist level 1:  [head] ► [alice:1500] sp=1 [bob:1200]  span=1  [carol:900]  span=1

ZRANK leaderboard carol:
→ traverse level 3: span=3, rank accumulator = 3
→ result: rank 3 (0-indexed: rank 2) — O(log N), not O(N)
Mental Model Check

The skiplist span field transforms a search structure into a ranking structure. Without span, ZRANK would require traversing every node from the head to count position. With span, it accumulates the rank by summing spans at each level during the O(log N) search. This is why ZRANK and ZREVRANK are O(log N), not O(N).

4.3 Configuration

INI
# redis.conf (Redis 7.0+)
zset-max-listpack-entries 128
zset-max-listpack-value   64

5. List Internals: listpack → quicklist

A Redis List (LPUSH/RPOP/LRANGE) is used for work queues, activity feeds, and ordered collections.

5.1 The quicklist

In Redis 7.2+, Lists use the quicklist encoding for all sizes above the listpack threshold. A quicklist is a doubly-linked list of listpack nodes — it provides O(1) head/tail push-pop while keeping individual nodes compact.

quicklist:
  ┌──────────────────────────────────────────────────────────┐
  │  [listpack node]  ↔  [listpack node]  ↔  [listpack node] │
  │  max 128 entries     max 128 entries     max 128 entries  │
  └──────────────────────────────────────────────────────────┘
                         doubly-linked
Condition Encoding
≤ list-max-listpack-size entries (default: 128) AND each ≤ 64 bytes listpack
Exceeds either quicklist (linked list of listpack nodes)
BASH
redis-cli RPUSH queue "job-1" "job-2" "job-3"
redis-cli OBJECT ENCODING queue
# → "listpack"

# After 129 entries
redis-cli OBJECT ENCODING queue
# → "quicklist"

6. Set Internals: intset → listpack → hashtable

Sets (SADD/SMEMBERS/SISMEMBER) have a three-stage encoding chain unique among Redis data structures:

Stage Condition Encoding Memory
1 All members are integers AND count ≤ set-max-intset-entries (default: 512) intset Sorted array of integers. O(log N) lookup via binary search. Extremely compact.
2 Non-integer member added OR count > intset limit AND count ≤ set-max-listpack-entries (default: 128) listpack Contiguous flat array.
3 Either listpack limit exceeded hashtable Standard hash table. O(1) lookup.
BASH
redis-cli SADD online-users 101 202 303 404
redis-cli OBJECT ENCODING online-users
# → "intset"  (all integers, under 512)

redis-cli SADD online-users "alice"   # ← non-integer member added
redis-cli OBJECT ENCODING online-users
# → "listpack"  (demoted from intset, not yet to hashtable)

# After adding 129+ members
redis-cli OBJECT ENCODING online-users
# → "hashtable"
Performance / Safety Warning

The intset → listpack demotion is silent and permanent. Adding a single non-integer member to an intset converts it to listpack immediately, even if you then remove that member. An intset Set of 500 user IDs consumes roughly 4KB. The equivalent hashtable Set consumes ~48KB — a 12× memory difference. If your Set values are always integers (user IDs, product IDs, numeric flags), never add a string member.

BASH
# ❌ Broken: Using string representations of numeric IDs
redis-cli SADD active-sessions "1001" "1002" "1003"
redis-cli OBJECT ENCODING active-sessions
# → "listpack"  — quoted strings are not integers

# ✅ Correct: Use raw integers to get intset encoding
redis-cli SADD active-sessions 1001 1002 1003
redis-cli OBJECT ENCODING active-sessions
# → "intset"  — 7× memory reduction

7. Memory Model: used_memory, Fragmentation & Diagnostic Commands

7.1 used_memory vs used_memory_rss

BASH
redis-cli INFO memory | grep -E "used_memory:|used_memory_rss:|mem_fragmentation"
# used_memory:           104857600   ← 100MB: what Redis thinks it's using
# used_memory_rss:       188743680   ← 180MB: what the OS reports as physical RSS
# mem_fragmentation_ratio: 1.80      ← 80% excess physical memory vs logical
Metric What it means
used_memory Logical memory: sum of all key/value allocations tracked by Redis
used_memory_rss Physical RSS: what the Linux kernel reports as Resident Set Size
mem_fragmentation_ratio rss / used_memory — gap caused by the jemalloc allocator

jemalloc allocates memory in fixed-size size classes (8, 16, 32, 48, 64, 80, 96, 128 bytes, ...). A 33-byte value is allocated in a 48-byte size class — 15 bytes wasted. Over millions of keys of varying sizes, this internal fragmentation grows. Additionally, when keys are deleted, freed arenas are not immediately returned to the OS — they remain as rss while used_memory drops.

Fragmentation ratio Interpretation
< 1.0 OS swapped Redis memory to disk — severe latency cliff, immediate action required
1.0 – 1.5 Healthy — normal jemalloc arena overhead
1.5 – 2.0 Elevated — consider active defragmentation
> 2.0 High fragmentation — risk of OOM kill without actual data growth
Pro Tip & Optimization

For deep coverage of eviction policies, active defragmentation (activedefrag yes), and the approximate sampled LRU algorithm, see High-Concurrency Cache Hazards §4. This article covers the diagnostic side; that article covers the remediation.

7.2 Diagnostic Commands

BASH
# Check a key's internal encoding
redis-cli OBJECT ENCODING session:user:42
# → "ziplist" (pre-7.0) or "listpack" (7.0+) or "hashtable"

# Check logical memory used by a single key (includes overhead)
redis-cli MEMORY USAGE session:user:42
# → 312  (bytes, including key name + value + metadata overhead)

# Check access frequency (requires allkeys-lfu or volatile-lfu maxmemory-policy)
redis-cli OBJECT FREQ session:user:42
# → 5  (approximate LFU counter — logarithmic scale, not a raw count)

# Full memory breakdown
redis-cli MEMORY DOCTOR
# → Outputs diagnostic advice: fragmentation warnings, peak memory info

8. Key Expiry Mechanics: Why Keys Outlive Their TTL

When you set SET key value EX 60, Redis does not start a timer per key. Expiry is handled by two co-existing mechanisms:

8.1 Lazy Expiry (On Access)

When a client requests an expired key, Redis checks the expiry timestamp at access time and deletes the key before returning nil. This is O(1) per access — no background work.

Client: GET session:user:42
Redis:  1. Lookup key in dictionary → found
        2. Check expiry: now > expiry_ts? → YES (expired 3 minutes ago)
        3. Delete key
        4. Return nil to client

Consequence: keys that are never accessed after expiry are not removed by lazy expiry alone. They consume memory indefinitely.

8.2 Active Expiry (Background Sampling)

To reclaim memory from unaccessed expired keys, Redis runs an active expiry cycle 10 times per second (configurable via hz). The algorithm is probabilistic:

Every 100ms (at hz=10):
  1. Sample 20 random keys from the set of keys with TTLs
  2. Delete all expired keys found in the sample
  3. If > 25% of sampled keys were expired: repeat immediately
  4. Stop when < 25% of sample is expired OR time limit reached (25% of the cycle budget)
Crucial Requirement

Keys can outlive their TTL under write-heavy load. If the active expiry cycle consistently finds > 25% expired keys (meaning expiry is outpacing the cycle), it loops — but is still bounded by the cycle time budget. In extreme cases, expired keys can persist for seconds or minutes beyond their TTL before the cycle catches up. This is not a bug; it is a deliberate trade-off to prevent the expiry cycle from consuming excessive CPU.

BASH
# Monitor active expiry behaviour
redis-cli INFO stats | grep expired_keys
# expired_keys: 1482930  ← cumulative count of keys expired (lazy + active)

# Check current hz setting
redis-cli CONFIG GET hz
# → hz 10 (default — 10 cycles per second)

# Increase hz for faster active expiry on TTL-heavy workloads (costs CPU)
redis-cli CONFIG SET hz 20

Summary

Concept Rule
KEYS * footgun Blocks the event loop for full O(N) scan — use SCAN cursor MATCH pattern COUNT N in all production code.
Key naming Use {namespace}:{entity-id}:{attribute} schema; colons as separators; lowercase; under 100 bytes.
Pipelining Batches N commands into 1 RTT — a client-side network optimization, not server-side atomicity.
String encodings int for integers; embstr for ≤ 44-byte strings (immutable); raw for larger strings.
Hash/ZSet/List encoding listpack (compact, O(N) lookup) → hashtable or skiplist+hashtable (O(1)/O(log N)) at configurable thresholds. Promotion is one-way per key.
Set encoding chain intset (integers only, 7× denser) → listpack → hashtable. A single non-integer member permanently demotes from intset.
OBJECT ENCODING First diagnostic command for any memory investigation — reveals the actual internal layout of a key.
Fragmentation ratio used_memory_rss / used_memory — healthy at 1.0–1.5; > 2.0 risks OOM kill without actual data growth.
Active expiry Probabilistic — keys can outlive their TTL by seconds under write-heavy load; this is by design.

What's Next

In Part 2: Redis Persistence — RDB, AOF & Hybrid Mode, we confront the most dangerous Redis misconception: that SET followed by OK means the data survives a crash. We deconstruct BGSAVE fork-and-copy mechanics, the appendfsync durability spectrum, the no-appendfsync-on-rewrite footgun that silently widens your data-loss window to minutes, and why Hybrid mode is the 2025 production default.

Research & Synthesis Note

This article was developed with AI-assisted deep search, specification cross-referencing, and technical research synthesis.

#Redis#Memory Management#Data Structures#Performance#Backend Engineering
Siddhant Deval

Written by Siddhant Deval

Senior Full-Stack Engineer building high-scale architectures, browser performance engineering systems, and SaaS platforms.

LinkedIn·GitHub·Twitter
Series·Part 1 of 7

Redis Mastery

Curriculum Roadmap
01Redis Data Structures & Memory Model: What the Server Actually Stores
Reading
02Redis Persistence: RDB, AOF & Hybrid Mode — Durability Is Not Free
03Redis Replication & High Availability: Sentinel, Failover & Split-Brain
04Redis Cluster: The Operational Reality Beyond Hash Slots
05Redis Pub/Sub vs. Streams: Choosing the Right Messaging Primitive
06Lua Scripting, MULTI/EXEC & True Atomicity in Redis
07Production Redis: Observability, Security, Connection Management & the Valkey Decision
Next ChapterRedis Persistence: RDB, AOF & Hybrid Mode — Durability Is Not Free
Previous Article
Isolation & Concurrency Control: The Anomaly You Are Allowing Right Now
Next Article
The Normalized Cache: Your Client's Replica of the Server Graph