Skip to content
notes.vinhnq.com

Search

Database & ORMMid24 min read

Redis internals: why it is fast, how it stores data and how it removes expired keys

Review 19 cards
On this page

Redis series: 1. Redis internals: why it is fast · 2. Persistence, replication, Sentinel and Cluster · 3. Choosing data structures for real problems

“Redis is single-threaded, so how can it be fast?” comes up in almost every backend interview, and “because it runs in RAM” only gets you half the points. This post covers the other half: the event loop, how keys are stored, how expired keys are cleaned up, and why one KEYS * can freeze the whole system. This is part 1; part 2 covers durability and scaling (RDB, AOF, replication, Sentinel, Cluster), part 3 covers choosing data structures, and cache failures (avalanche, hot keys, big keys, eviction) have their own post.

All numbers in this post were measured on Redis 7.4 running in Docker with the default configuration.

1. What Redis is, and how it differs from Memcached

Key idea: Redis is an in-memory key-value store whose values have types, with commands that run right on the server. Memcached stores only byte strings, is multi-threaded, and has no persistence or built-in replication.

Value types include string, list, hash, set, sorted set, stream, bitmap, HyperLogLog and geo. To add one element to a list you send RPUSH instead of pulling the whole list into the app. On top of that you get transactions (MULTI/EXEC), Lua scripts and functions, pub/sub, persistence, replication, clustering, and eviction policies (dropping keys) for when memory runs out.

Redis Memcached
Command execution model One thread runs commands (optional extra I/O threads since 6) Multi-threaded
Data types Many types, operated on by the server Byte strings only
Persistence RDB, AOF None
Replication, failover Yes (replicas, Sentinel, Cluster) Not built in
Spreading data over nodes Redis Cluster (the server knows about slots) The client hashes keys itself (consistent hashing)
Value size limit 512 MB per string 1 MB per item by default
Extra features Lua, transactions, pub/sub, streams Almost none
Two things the slides get wrong: “Memcached has no cluster” and “Redis gets slow past 16 GB”

2. Why Redis is fast

Key idea: data in RAM, one command thread so no locks, one event loop watching tens of thousands of sockets, and optimised data structures. The cost: every command is queued serially, so one slow command slows everyone.

2.1. The bottleneck is not the CPU

A GET on an in-memory hash table costs a few hundred nanoseconds of CPU. A network round-trip inside one data center costs 100–500 microseconds. So most of the time goes to the network and socket read/write syscalls, not to running the command.

When Redis hits its ceiling, it is usually because of:

  • Memory: the data no longer fits in RAM, so keys get evicted or writes fail with OOM.
  • Network bandwidth: large values times the read rate saturate the network card (big keys).
  • One slow command blocking everyone: an O(N) command on a large collection, a long Lua script.

The CPU only becomes the bottleneck with very many connections sending small commands. Even then the CPU-hungry part is socket I/O, exactly what io-threads in version 6 were introduced to offload.

2.2. Four reasons

  1. Data lives in RAM: no disk seek on the read path. Persistence (if enabled) runs in a child process or as appends.
  2. One thread runs commands: no locks, no context switches (the CPU swapping between threads), no race conditions inside the server. Every command is atomic, so INCR is safe without anything extra.
  3. I/O multiplexing: one thread watches many sockets at once with epoll (Linux) or kqueue (macOS/BSD) and only handles those with data ready.
  4. Optimised data structures: small collections are stored compactly (listpack, intset), large ones use hash tables and skiplists. See section 3.

2.3. What the event loop looks like

An event loop is an endless loop: ask the kernel “which sockets are ready”, then handle each one. Like a waiter who only goes to tables with a raised hand instead of standing at each table in turn.

flowchart LR
  C1[Client 1] --> E[epoll_wait]
  C2[Client 2] --> E
  C3[Client N] --> E
  E --> R[Read and parse commands]
  R --> X[Execute command on the keyspace]
  X --> W[Write reply to buffer]
  W --> S[Send reply to socket]
  S --> T[Timers: active expire, cron]
  T --> E

Each iteration ends with the periodic serverCron, run at a frequency of hz (10 times per second by default): active expiry, hash table resizing, statistics. Because only one thread runs commands, a command that takes 200 ms means every other client waits 200 ms.

2.4. What “single-threaded” means precisely

The slides say “since 6.0 Redis is no longer single-threaded”. The idea is right, but in an interview be precise:

  • Command execution is still single-threaded, even in Redis 7. This is what makes each command atomic.
  • io-threads (6.0) is optional and off by default (io-threads 1). When enabled, extra threads read/parse requests and write replies, while commands still run on the main thread.
  • Persistence uses child processes, not threads: BGSAVE and AOF rewrites call fork(). Details in part 2.

To use many cores for running commands, run several instances on one machine (one shard each) or use Redis Cluster.

Background bio threads, io-threads in detail, and the Redis/Valkey license story

The full slide claim is “the main thread runs commands, other threads handle persistence and network I/O”. The “persistence” part needs the correction above. A few more details:

  • Background threads (bio) existed long before version 6: closing files, fsync for the AOF, freeing the memory of keys deleted with UNLINK (lazyfree).
  • io-threads help when there are very many connections and syscalls eat all of the main thread’s CPU. Redis 8 reworked the mechanism to make better use of multiple cores.

3. How Redis stores data

Key idea: the keyspace is a hash table (key → value) plus an expires dict for keys with a TTL. Every value has a type and an encoding (how it is stored underneath); small collections are stored compactly, and as they grow Redis converts them to faster but more memory-hungry structures.

3.1. The keyspace is a hash table

Each Redis database (16 by default, numbered 0–15; Cluster only uses 0) has:

  • a main dict: key → value,
  • an expires dict: key → expiry time (ms), holding only keys with a TTL.
flowchart LR
  DB[redisDb] --> D[dict: key -> redisObject]
  DB --> EX[expires: key -> unix ms]
  D --> O1[redisObject type=hash encoding=listpack]
  D --> O2[redisObject type=string encoding=int]
  EX --> T1[1735689600000]

Looking up a key is O(1) on average. The value is a redisObject carrying a type (string, list, hash…) and an encoding. One type can have several encodings.

The hash table rehashes incrementally: when it grows, Redis keeps two tables side by side and every command moves a few buckets to the new one. So there is never a resize that stops the server, like when a giant Java HashMap resizes.

3.2. Encodings: compact when small, converted when large

A listpack is one contiguous byte array with elements packed back to back and no pointers. Finding a field is an O(N) scan, but for small N sitting snugly in the CPU cache it beats a hash table and uses far less memory. Like a short list on a single sheet of paper: skimming it is faster than looking things up in an index.

I measured a hash with 512 fields (still a listpack) and one with 513 fields (already a hashtable), with the same short contents:

512 fields, listpack  -> MEMORY USAGE = 5,168 bytes
513 fields, hashtable -> MEMORY USAGE = 28,816 bytes

Adding one field makes memory grow 5.6 times. That is why a classic trick still works: instead of 10 million keys user:{id}:status, group them into small hashes user:status:{id / 1000} with at most 512 fields each. Every top-level key pays for a dict entry, a redisObject and the key string, so grouping saves a lot.

Encoding table with Redis 7.4 default thresholds, and the old ziplist

The table shows what OBJECT ENCODING returns on Redis 7.4. The thresholds come from CONFIG GET on the Docker image without a config file; a redis.conf or a managed service may set different values, so check your own instance.

Type When small When large Default threshold (7.4)
String int (integer), embstr (≤ 44 bytes) raw 44 bytes
List listpack quicklist (a linked list of listpacks) list-max-listpack-size -2 (8 KB per node)
Hash listpack hashtable 512 fields, values ≤ 64 bytes
Set intset (all integers), listpack hashtable 512 integers / 128 members
Sorted set listpack skiplist + dict 128 members, values ≤ 64 bytes

Before 7.0 Redis used ziplist. It had a “cascade update” problem: changing one element could force a chain of updates to the elements after it. listpack replaced it.

3.3. SDS: Redis’s string type

Redis does not use \0-terminated C strings but SDS (Simple Dynamic String): a header holding the used length and allocated capacity, followed by the bytes. That makes strings binary safe (any byte, including 0) with an O(1) length.

3.4. The skiplist behind sorted sets

A large sorted set uses two structures at once: a dict (member → score) so ZSCORE is O(1), and a skiplist ordered by score so ZRANGE and ZRANK are O(log N).

A skiplist is a linked list with several levels of “express lanes”: the bottom level holds every element in order, and each level above holds a random subset of the one below. A search starts at the top level, jumps as far as it can, then drops down.

level 2:  1 ----------------- 9 ----------------- 31
level 1:  1 ------ 4 ------- 9 ------ 18 ------- 31
level 0:  1 - 2 -- 4 -- 6 -- 9 - 13 - 18 - 25 -- 31
SDS and skiplist internals, and skiplists versus balanced trees

SDS in detail:

  • Binary safe: it can hold a 0 byte, so a string can contain images, protobuf, compressed data.
  • O(1) length (STRLEN) instead of counting up to \0.
  • No buffer overflow on append: APPEND checks the capacity and allocates more before writing. It over-allocates (doubling while small, adding 1 MB once large) so repeated appends don’t realloc every time.
  • embstr is an optimisation for short strings: the redisObject and the SDS live in one contiguous allocation (one cache line) instead of two.

Skiplist in detail: Redis promotes a node to the next level with probability 1/4, up to 32 levels. Why not a balanced tree? A skiplist is simpler to implement and debug, a range query is just walking forward on level 0, and every link stores a “span” so rank can be computed in O(log N).

4. How expired keys are removed

Key idea: Redis does not delete a key the moment it expires. It deletes it lazily when a command touches it, and actively with a sampling cycle that runs 10 times per second, so keys nobody reads don’t occupy RAM forever.

4.1. Checking for expiry

SET k v EX 60 writes k into the main dict and k → now + 60000 into expires. When a command touches k, Redis looks it up in expires:

  • absent: the key has no TTL, read it normally;
  • present and past due: delete it and respond as if it didn’t exist (nil);
  • present, not yet due: read it normally.

If Redis relied only on reads, “dead” keys that nobody reads would occupy RAM forever. So it combines two approaches.

4.2. Lazy (passive) and active expiration

  • Lazy: delete when someone touches the key. Cheap, but it never removes a key nobody reads.
  • Active: on every cron cycle, activeExpireCycle takes a batch of keys with a TTL (20 by default) and deletes the expired ones. If more than 25% of the batch had expired it repeats, otherwise it waits for the next cycle.

The consequence: in steady state, the share of expired keys still sitting in RAM hovers around 25%. To clean harder, raise active-expire-effort (1–10, default 1), at the cost of CPU.

activeExpireCycle in detail, the 20,000-key experiment, and two slide mistakes

The steps of the active cycle:

  1. Take a batch of keys with a TTL (20 keys by default) from expires.
  2. Delete the expired keys in that batch.
  3. If more than 25% of the sampled keys had expired (still a lot of garbage), repeat step 1; otherwise stop until the next cycle.
  4. It has a time limit (about 25% of CPU time per cycle) so it doesn’t block client commands. Besides this “slow” cycle there is a “fast” cycle of at most 1 ms that runs before each return to the event loop.

Experiment: write 20,000 keys with a 1-second TTL and never read any of them back. After 3 seconds DBSIZE dropped from 20,004 to 4, and INFO stats reported expired_keys:20000 and expire_cycle_cpu_milliseconds:11. Nobody read them and they were still cleaned up, thanks to the active cycle.

4.3. Expiry on replicas and on restart

  • Replicas don’t expire keys themselves. When the master removes a key it generates a DEL and writes it to the replication stream and the AOF; the replica waits for that. Since 3.2, reading an expired key on a replica returns nil even though it isn’t deleted yet, so clients don’t see stale data; but memory is only freed once the DEL arrives.
  • A TTL is an absolute point in time (unix ms): the master skips already-expired keys when loading an RDB, and changing the system clock makes keys expire earlier or later accordingly.

5. When memory is full

Key idea: at maxmemory, Redis follows maxmemory-policy. The default noeviction rejects writes (OOM command not allowed) while reads still work; the other policies drop keys by random, TTL, LRU or LFU.

  • Each family has an allkeys-* variant (every key) and a volatile-* variant (only keys with a TTL). The TTL family drops keys closest to expiry first.
  • Redis’s LRU (drop the least recently used key) is approximate: it samples maxmemory-samples keys (5 by default) and evicts the oldest, without a global linked list.
  • LFU (drop the least frequently used key) uses an 8-bit logarithmic counter that decays over time.

The full table, a comparison with Caffeine’s W-TinyLFU, and the volatile-* trap with keys that have no TTL are in the cache failures post, section 7.

Exercises

Exercise 1: estimate memory for 10 million status flags

Task: store online/offline status for 10 million users (user_id values are contiguous integers). Option A: 10 million keys online:{id} with the value 1. Option B: group them into hashes online:{id / 500} with id % 500 as the field. Option C: one bitmap, SETBIT online {id} 1. Compare memory and operations.

Solution to Exercise 1: comparing the three layouts
  • A: each top-level key costs roughly 50–70 bytes (dict entry, redisObject, an SDS for the key, the int value using a shared object), around 500–700 MB in total. Simple, with a TTL per key.
  • B: 20,000 hashes, each with 500 short fields, still listpacks (below the 512 threshold), with only a few bytes per field. Around 50–80 MB in total, almost 10 times less. You lose per-user TTLs (unless you use HEXPIRE from 7.4), and the hashes must not cross the threshold.
  • C: 10 million bits = 1.25 MB. The smallest by far, countable with BITCOUNT, but it stores exactly 1 bit, has no TTL, and user_id must be dense (with sparse, large ids the bitmap grows to the largest id).

How to verify: load 100,000 entries with each option, compare INFO memory (used_memory) before and after, and scale up. Don’t trust estimates without measuring, because the overhead depends on the version and the allocator (jemalloc).

Exercise 2: diagnose Redis latency that spikes every hour

Task: Redis p99 is normally 1 ms, but right at the top of every hour it jumps to 80 ms for a few seconds. List hypotheses and how to check them.

Solution to Exercise 2: four hypotheses and how to check them
  1. Many keys expiring at once (a job that fills the cache at the top of the hour with a round 1-hour TTL). Check INFO stats → expired_keys jumping at exactly that time; fix with TTL jitter and lazyfree-lazy-expire yes.
  2. Scheduled RDB snapshots (save 3600 1): fork() of a process with tens of GB takes tens of ms and blocks the main thread. Check INFO persistence → latest_fork_usec; fix with smaller instances, disabling THP (transparent huge pages), or snapshotting only on a replica.
  3. A cron job running O(N) commands (a report using KEYS, a large SMEMBERS). Check SLOWLOG GET 20; fix with SCAN.
  4. AOF rewrite also calls fork(), and an fsync stuck on a busy disk makes the main thread wait. Check aof_rewrite_in_progress and the log line “Asynchronous AOF fsync is taking too long”.

Enable LATENCY MONITOR (CONFIG SET latency-monitor-threshold 10) and then run LATENCY DOCTOR to let Redis summarise the causes itself.

Remember

  • Explain why Redis’s bottleneck is the network and memory, not the CPU.
  • Say precisely what is single-threaded (command execution) and what isn’t (io-threads, bio threads, fork()).
  • Know why one O(N) command slows every client, and what to use instead of KEYS *.
  • Explain the listpack encoding and why crossing the threshold makes memory jump.
  • Describe the two ways expired keys are removed, and know when to choose allkeys-* or noeviction.

Interview questions

Junior

What is Redis and what is it typically used for?

An in-memory key-value store whose values have types (string, list, hash, set, sorted set, stream…) with commands that run on the server.

It is used as a cache, for session storage, counters and rate limiting, leaderboards, lightweight queues and distributed locks. It has persistence and replication, but it usually isn’t the primary store for critical data.

Why is Redis fast even though it is single-threaded?

Because the bottleneck is the network and memory, not the CPU: the data is in RAM, so each command costs only a few hundred nanoseconds of CPU.

  • One thread means no locks and no context switches, and every command is naturally atomic.
  • I/O multiplexing (epoll) lets one thread serve tens of thousands of connections.
  • The data structures are optimised: listpack for small collections, skiplists, a hash table that rehashes incrementally.
How do key TTLs work? Is an expired key deleted immediately?

Not immediately: Redis records the expiry time in the expires dict, then deletes keys lazily on read or actively with a sampling cycle.

Lazy: a command touches the key, finds it past its expiry and deletes it. Active: a cycle running 10 times per second samples keys with a TTL, deletes the expired ones, and repeats if more than 25% of the sample had expired. Readers never see an expired key, but its memory may not be freed right away.

Mid

Is Redis 6 and later still single-threaded?

Command execution is still single-threaded; only socket I/O, background jobs and persistence run elsewhere.

Background threads for closing files, fsync and freeing memory (lazyfree) existed before version 6. Version 6 added optional io-threads (off by default) to read/parse requests and write replies in parallel. Persistence uses child processes via fork(), not threads. To use multiple cores for running commands, run several instances or use Cluster.

What is the encoding of a Redis hash, and why does it matter?

A small hash (by default ≤ 512 fields in 7.4, each value ≤ 64 bytes) is a listpack; past the threshold it becomes a hashtable and uses 5–6 times more memory.

A listpack is a contiguous byte array, scanned linearly but very compact. I measured 5 KB → 28 KB when adding the 513th field, and the hash never converts back. Knowing this lets you group small keys into hashes to save memory and avoid putting long values into hashes.

Why is KEYS * banned in production? What do you use instead?

Because KEYS walks the whole keyspace in O(N) on the single command thread and can block Redis for seconds. Use SCAN instead.

SCAN with MATCH and COUNT iterates with a cursor, a little at a time; you accept that you may see duplicates or miss keys that change during the scan. Even better is a design that never needs to find keys by pattern (keep an index in a set).

What happens when Redis runs out of memory?

It depends on maxmemory-policy; the default noeviction rejects writes with an OOM error while reads keep working.

With allkeys-lru/lfu, Redis evicts keys using approximate (sampled) LRU/LFU; with volatile-*, it only evicts keys that have a TTL. A cache should use allkeys-*; an instance holding data that must not be lost (locks, queues) should use noeviction and be kept separate.

Senior

Design Redis usage to keep p99 latency consistently low. What do you pay attention to?

Never let anything block the command thread: no O(N) commands, no big keys, no mass expiry, and fast fork().

  • Use SCAN, cap collection sizes, enforce with ACLs; use UNLINK/lazyfree for large keys.
  • Spread TTLs; keep instances moderately sized so fork() is fast, disable THP, leave RAM for copy-on-write; AOF everysec on a dedicated disk.
  • Pipelining/MGET instead of many round-trips; short client timeouts and a sensible pool.
  • Monitor SLOWLOG, LATENCY DOCTOR, latest_fork_usec, expired_keys, evicted_keys and mem_fragmentation_ratio.
Why do sorted sets use a skiplist instead of a balanced tree?

Because a skiplist is simpler with equivalent complexity (expected O(log N)), natural range scans and easy rank computation.

Insert/delete only change local pointers, a range scan just walks forward on the bottom level, and a “span” on each link gives you rank in O(log N). The sorted set also keeps a dict so ZSCORE is O(1). Small sets (≤ 128 members) use a listpack to stay compact.

Can a replica read a key that has already expired? When is the memory on the replica freed?

No: since Redis 3.2 a replica returns nil for an expired key. But the memory is only freed when the master sends a DEL.

The replica doesn’t delete it on its own; it waits for the master to generate a DEL (when the master expires the key lazily or actively) through the replication stream. So replica memory can be slightly higher than the master’s, and if the clocks between machines drift a lot, results can differ.

Useful phrases for interviews

  • “Redis is in-memory, so the bottleneck is usually the network or memory, not the CPU.”
  • “Commands run on a single thread, which is exactly why every command is atomic without any locking.”
  • “With epoll, one event loop only touches the sockets that are actually ready.”
  • “io-threads only parallelise socket reads and writes; command execution stays on the main thread.”
  • “One slow O(N) command shows up as tail latency for every client, so I’d use SCAN instead of KEYS.”
  • “A small hash uses the listpack encoding and converts to a real hash table once it crosses the threshold, and it never converts back.”
  • “Expired keys are removed lazily on access and actively by a sampling cycle that runs ten times per second.”
  • “I’d add jitter to TTLs so a million keys don’t expire in the same second.”
  • “For a pure cache I’d pick allkeys-lru or allkeys-lfu; for data that must not be lost, noeviction plus alerting.”
  • “Leave headroom below maxmemory for copy-on-write when the server forks for a snapshot.”

Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.