5. Internals and Architecture
Earlier chapters treated Redis as a black box that runs commands quickly. This chapter opens the box: how a single thread serves thousands of clients, how each data type is stored in memory and why its encoding changes as it grows, and what Redis does when memory runs out or keys expire. These internals explain most of Redis's performance traps, such as one slow command that freezes every client, a hash that suddenly uses three times more memory, or keys that "should have expired" but still occupy RAM. They are also the basis for the persistence, replication and tuning chapters that follow.
<a id="51-execution-model"></a>
5.1 Execution Model
This subchapter explains how Redis runs commands: the single-threaded event loop, the I/O multiplexing that lets one thread watch thousands of sockets, the optional I/O threads, the difference between commands that block a client and commands that block the server, and why the time complexity of each command matters more in Redis than in most databases.
Single-Threaded Event Loop
Most databases handle concurrency with many threads: one per connection or a pool of workers, coordinated by locks. Locks have costs: contention, context switches, deadlocks, and code that is hard to reason about. Redis keeps all data in memory and most commands take about a microsecond, so the CPU rarely limits it. The usual limits are the network and memory. Given that, Redis's author chose a simpler design: one main thread executes every command, one at a time.
Think of a bank with a single, extremely fast teller. Customers (clients) form one queue and are served one request at a time. The teller never has to coordinate with colleagues, so there are no mix-ups, and each request is so short that the queue moves very quickly. The weakness is equally clear: one customer with a two-hour request blocks everybody behind them.
What the loop does
The main thread runs an event loop (Redis's own small library, ae). Each iteration looks like this:
┌───────────────────────────────────────────────────────────┐
│ main thread │
│ │
┌───────▶│ 1. beforeSleep() flush pending replies, fast expire │
│ │ cycle, append to AOF buffer, ... │
│ │ 2. poll the OS "which sockets are ready?" (epoll) │
│ │ waits until an event or the next timer │
│ │ 3. file events accept new connections │
│ │ read requests, parse, EXECUTE commands │
│ │ queue replies in client buffers │
│ │ 4. time events serverCron(), hz times per second │
│ │ (expiry, rehashing, stats, timeouts) │
└────────┤ │
└───────────────────────────────────────────────────────────┘
Commands from different clients are therefore never executed at the same time. A command runs from start to finish before the next one begins.
Not literally one thread
"Single-threaded" refers to command execution. A Redis process has other threads and processes for work that would otherwise stall the loop:
| Helper | What it does |
|---|---|
bio_close_file thread | Closes files in the background (closing a large deleted file can take a long time) |
bio_aof thread | Runs fsync for the append-only file (chapter 6.2) |
bio_lazy_free thread | Frees memory for UNLINK, FLUSHALL ASYNC and the lazyfree-* options |
io_thd_N threads | Optional I/O threads that read and write sockets (see "Threaded I/O") |
| Forked child process | Writes RDB snapshots and rewrites the AOF (chapter 6) |
jemalloc_bg_thd | Allocator housekeeping threads |
None of these touch the dataset while commands run, so the main thread still needs no locks on data.
serverCron and hz
Periodic work runs in serverCron, which fires hz times per second (default 10, maximum 500). It expires keys actively, advances incremental rehashing, closes timed-out clients, updates statistics and triggers persistence. With dynamic-hz yes (the default), Redis raises the effective frequency when many clients are connected.
Consequences
- Atomicity for free. Every single command is atomic.
INCRnever loses an update, andMULTI/EXECand Lua scripts are isolated simply because nothing else runs at the same time (chapter 4). - Throughput comes from short commands. Hundreds of thousands of simple operations per second on one core are normal.
- One slow command delays everybody. A 2-second command adds 2 seconds of latency to every client, including health checks and replicas.
- One core per instance for command execution. To use more cores for commands, you run several instances or Redis Cluster (chapter 7).
Example: watching one command block everyone
# Terminal 1: a Lua script that spins for a couple of seconds (never do this in production)
redis-cli EVAL "local x = 0 for i = 1, 200000000 do x = x + i end return 'done'" 0
# Terminal 2, started while terminal 1 is running: PING is answered only when the script ends
redis-cli --latency -i 1
# min: 2212, max: 2212, avg: 2212.20 (1 samples) <- a single PING waited about 2.2 seconds
Example: listing the threads of a running server (Linux)
pid=$(pidof redis-server)
for t in /proc/$pid/task/*; do cat "$t/comm"; done
# redis-server <- the main thread: runs every command
# bio_close_file
# bio_aof
# bio_lazy_free
# jemalloc_bg_thd
Key Takeaways
- One main thread executes all commands sequentially, so single commands are atomic and the data needs no locks.
- Background threads and forked children handle file closing,
fsync, lazy freeing and persistence, but never run commands. serverCronrunshztimes per second for housekeeping such as active expiry and rehashing.- The design is fast because commands are short. A long command blocks every client for its full duration.
Practice
- (Beginner) Start a local Redis server, list its threads with the
/procloop above, and match each thread name to the table.- (Intermediate) Run
redis-cli --latencyin one terminal. In another, run the spinning Lua script with increasing loop counts (5e7,1e8,2e8). Plot the max latency against the script duration and explain the relation.- (Interview) "Redis is single-threaded. How can it handle 100,000+ operations per second, and why doesn't it need locks?" Hint: compare the time to execute an in-memory
GETwith the time spent on the network, and think about what a lock protects against.
I/O Multiplexing
A single thread must serve thousands of connections. If it called a blocking read() on one socket, it would sleep until that client sent something while every other client waited. Creating one thread per connection avoids this but brings back the costs Redis wants to avoid: memory for each thread's stack, context switches, and locks.
The solution is I/O multiplexing: all sockets are set to non-blocking mode, and the thread asks the operating system one question per loop iteration: "which of these sockets are ready to read or write?" The OS answers with a short list, and the thread handles only those sockets. Picture a waiter responsible for fifty tables. They do not stand at one table waiting for the guests to decide; they watch the room and go only to tables where someone raises a hand.
client sockets kernel Redis main thread
─────────────── ──────── ────────────────────
fd 7 (idle) ┐
fd 8 (sent "GET a") ├──▶ epoll instance ──epoll_wait──▶ ready: [fd 8, fd 12]
fd 9 (idle) │ (watches all read fd 8 → GET a
... │ registered fds) read fd 12 → INCR c
fd 12 (sent "INCR c") ┘ queue replies, loop
Backends
The ae library uses the most efficient mechanism the platform offers, chosen at compile time:
| Backend | Platform | Cost per poll |
|---|---|---|
epoll | Linux | O(number of ready sockets) |
kqueue | macOS, FreeBSD | O(number of ready sockets) |
evport | Solaris / illumos | O(number of ready sockets) |
select | Fallback | O(number of watched sockets), limited to 1024 descriptors |
redis-cli INFO server | grep multiplexing_api
# multiplexing_api:epoll
Reading and writing
- Readable events: the listening socket becomes readable when a new client connects (accept handler); a client socket becomes readable when a request arrives (read handler). The read handler reads whatever bytes are available into the client's query buffer, parses complete commands and executes them. A partial command simply waits in the buffer for the next readable event.
- Writable events: replies are appended to the client's output buffer. Just before going back to
epoll_wait, Redis tries to write pending replies directly. Only if the kernel's socket buffer is full (a slow or distant client) does it register a writable event and finish the write later.
This is why pipelining is so effective (chapter 4.3): one readable event can bring in hundreds of commands, and one write can send all their replies.
Example: the same pattern in Python
The selectors module wraps epoll/kqueue. This toy server speaks enough of the Redis inline protocol to answer redis-cli with PING, SET and GET, using one thread for any number of clients:
import selectors
import socket
sel = selectors.DefaultSelector() # epoll on Linux, kqueue on macOS
data: dict[str, str] = {}
buffers: dict[socket.socket, bytes] = {}
def accept(server: socket.socket) -> None:
conn, _ = server.accept()
conn.setblocking(False) # never let one client stall the loop
buffers[conn] = b""
sel.register(conn, selectors.EVENT_READ, handle)
def execute(parts: list[str]) -> bytes:
cmd = parts[0].upper()
if cmd == "PING":
return b"+PONG\r\n"
if cmd == "SET" and len(parts) == 3:
data[parts[1]] = parts[2]
return b"+OK\r\n"
if cmd == "GET" and len(parts) == 2:
v = data.get(parts[1])
return b"$-1\r\n" if v is None else f"${len(v)}\r\n{v}\r\n".encode()
return b"-ERR unknown command\r\n"
def parse_resp_array(buf: bytes) -> tuple[list[str] | None, bytes]:
"""Parse one RESP array of bulk strings, as sent by redis-cli. Returns (parts, rest)."""
if not buf.startswith(b"*") or b"\r\n" not in buf:
return None, buf
header, rest = buf.split(b"\r\n", 1)
parts = []
for _ in range(int(header[1:])):
if b"\r\n" not in rest:
return None, buf # incomplete: wait for more bytes
length_line, rest = rest.split(b"\r\n", 1)
n = int(length_line[1:])
if len(rest) < n + 2:
return None, buf
parts.append(rest[:n].decode())
rest = rest[n + 2:]
return parts, rest
def handle(conn: socket.socket) -> None:
chunk = conn.recv(4096) # socket is ready: this does not block
if not chunk: # client closed the connection
sel.unregister(conn)
conn.close()
del buffers[conn]
return
buffers[conn] += chunk
replies = b""
while True: # a pipeline may contain many commands
parts, buffers[conn] = parse_resp_array(buffers[conn])
if parts is None:
break
replies += execute(parts)
conn.sendall(replies) # simplification: Redis buffers and retries
server = socket.socket()
server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
server.bind(("127.0.0.1", 7777))
server.listen()
server.setblocking(False)
sel.register(server, selectors.EVENT_READ, accept)
while True: # the event loop
for key, _ in sel.select(): # blocks until at least one socket is ready
key.data(key.fileobj) # dispatch to accept() or handle()
redis-cli -p 7777 SET greeting hello # OK
redis-cli -p 7777 GET greeting # "hello"
Key Takeaways
- Redis uses non-blocking sockets and asks the kernel which ones are ready, so one thread can serve tens of thousands of connections.
epoll(Linux) andkqueue(BSD/macOS) cost time proportional to ready sockets, not to all connected sockets.- Partial requests wait in a per-client query buffer; replies wait in a per-client output buffer.
- Replies are written directly before the next poll. Writable events are used only when a client cannot keep up.
Practice
- (Beginner) Check which multiplexing backend your Redis uses with
INFO server. If you have both Linux and macOS available, compare the results.- (Intermediate) Run the toy server above and send inline commands with
printf 'PING\r\nPING\r\n' | nc 127.0.0.1 7777. Explain why nothing comes back, then extend the parser to also accept inline commands (lines that do not start with*) and verify that both pipelinedPINGs are answered with onerecv().- (Interview) "Why does Redis use an event loop with
epollinstead of one thread per client connection?" Hint: consider 10,000 mostly idle connections: what does each design cost in memory and context switches, and what would each command need to touch shared data safely?
Threaded I/O
At very high throughput, profiling the main thread shows something surprising: much of its time is not spent executing commands but on read() and write() system calls and on parsing the protocol. Command execution of a GET takes well under a microsecond; moving its bytes through the kernel costs several times more. On a machine with spare cores, that I/O work can be done in parallel without giving up the single-threaded execution model.
Threaded I/O does exactly that: extra threads read and parse requests and write replies, while command execution stays on the main thread. Back to the bank: the teller still processes every request alone, but assistants now take forms from customers, check they are filled in, and hand results back. The teller works faster because they never touch the paperwork.
How it works in Redis 8
Redis 6.0 introduced I/O threads in which the main thread fanned out reads and writes to helpers and waited for them on every loop iteration. Redis 8.0 replaced this with a new implementation in which each client connection is assigned to an I/O thread. That thread runs its own event loop for its clients: it reads the socket, parses complete commands, and hands the client to the main thread, which executes the commands and gives the client back for the reply to be written.
io_thd_1 ── clients A, D, G ──┐ read + parse ┌── write replies ── io_thd_1
io_thd_2 ── clients B, E, H ──┼──────────────────▶ main ──────────────────┼── io_thd_2
io_thd_3 ── clients C, F, I ──┘ parsed commands │ executes ALL └── io_thd_3
│ commands, one at
│ a time, as before
Configuration
# redis.conf
# Total threads doing I/O, INCLUDING the main thread. 1 = disabled (default).
# 4 here means the main thread plus 3 I/O threads (io_thd_1 .. io_thd_3).
io-threads 4
io-threadscannot be changed at runtime; set it in the config file or on the command line.- In Redis 6.x and 7.x, reads were threaded only with
io-threads-do-reads yes. Redis 8 always threads both directions, and that option no longer exists. - Guidance: leave it at 1 unless the main thread is CPU-bound (near 100% of one core) and the machine has idle cores. A typical starting point is half the available cores, keeping a core free for the main thread, the OS and persistence forks. Gains are largest with many concurrent connections and small commands.
Inspecting threads
redis-server --io-threads 4 --daemonize yes
redis-cli INFO threads
# io_thread_0:clients=0,reads=0,writes=0 <- the main thread
# io_thread_1:clients=1,reads=1,writes=0
# io_thread_2:clients=0,reads=0,writes=0
# io_thread_3:clients=0,reads=0,writes=0
redis-cli CLIENT LIST | grep -o 'io-thread=[0-9]*'
# io-thread=1 <- which thread owns this connection
Measuring the effect
# 200 connections, 1M requests, no pipelining; run the benchmark from another machine
# (or pin it to other cores) so it does not compete with the server for CPU
redis-benchmark -h redis.internal -t set,get -n 1000000 -c 200 --threads 4 -q
Run the benchmark with io-threads 1 and then with io-threads 4, and compare requests per second and p99 latency. For heavy commands (large HGETALL, Lua scripts, SORT), expect little difference, because execution time dominates.
Key Takeaways
- I/O threads parallelize socket reads, protocol parsing and reply writes. Commands still run one at a time on the main thread, so atomicity is unchanged.
- In Redis 8 each client is owned by one I/O thread;
INFO threadsandCLIENT LIST(io-thread=) show the distribution. io-threadscounts the main thread, is set at startup only, and is worth enabling only when the main thread is saturated by I/O on a multi-core machine.- I/O threads do not speed up expensive commands; only splitting data across instances or shards does.
Practice
- (Beginner) Start Redis with
--io-threads 4, connect threeredis-clisessions, and useINFO threadsandCLIENT LISTto see how the connections are distributed.- (Intermediate) Benchmark
GET/SETwith 50 and with 500 connections, each time withio-threads 1andio-threads 4. Report requests per second and p99 latency, and explain in which configuration threading helps most.- (Interview) "We enabled
io-threads 8, but our Lua-heavy workload didn't get faster. Why?" Hint: identify which part of a request's life is parallelized and which is not, and where a Lua script spends its time.
Blocking vs Non-Blocking Commands
"Blocking" means two very different things in Redis, and confusing them causes real incidents:
- A command that blocks the calling client: the client waits, but the server keeps serving everyone else. This is a feature.
- A command that blocks the server: it takes so long to execute that the event loop stops for every client. This is a hazard.
Commands that block only the client
These commands wait until data is available or a timeout expires:
| Command | Waits for |
|---|---|
BLPOP, BRPOP, BLMOVE, BLMPOP | An element in a list (chapter 2.3) |
BZPOPMIN, BZPOPMAX, BZMPOP | A member in a sorted set |
XREAD BLOCK, XREADGROUP BLOCK | New stream entries (chapter 3.4) |
WAIT, WAITAOF | Replicas or AOF fsyncs to acknowledge writes (chapters 6, 7) |
When such a command finds nothing, Redis does not loop or sleep. It records the client in a table of "clients blocked on key X", stops reading from that client, and moves on. When a later command (for example LPUSH) adds data to key X, Redis marks the key as ready and, after that command finishes, serves the waiting clients in the order they blocked. A timed-out client receives a null reply.
client W: BLPOP jobs 0 ──▶ jobs is empty ──▶ W parked in blocking_keys["jobs"]
client P: LPUSH jobs j1 ──▶ executes, marks "jobs" ready
──▶ after LPUSH: pop j1, reply to W, unpark W
other clients ──▶ served normally the whole time
Two rules follow from the execution model: inside MULTI/EXEC and inside Lua scripts, blocking commands never block. They behave like their non-blocking forms and return null immediately if there is no data, because a transaction or script cannot pause while holding the whole server.
redis-cli BLPOP jobs 30 & # waits up to 30 s; the server stays responsive
redis-cli INFO clients | grep blocked_clients
# blocked_clients:1
redis-cli CLIENT LIST | grep -o 'flags=b'
# flags=b <- "b" = blocked
redis-cli LPUSH jobs job-1 # the background BLPOP returns: 1) "jobs" 2) "job-1"
CLIENT UNBLOCK <id> [TIMEOUT | ERROR] releases a blocked client from another connection, which is useful when shutting down workers.
Commands that block the server
Any command whose work grows with the size of the data can stall the loop when the data is large:
| Risky operation | Why it is slow | Non-blocking alternative |
|---|---|---|
KEYS pattern | Scans every key | SCAN with MATCH (chapter 2.1) |
DEL of a key with millions of elements | Frees every element | UNLINK (frees in bio_lazy_free) |
FLUSHALL, FLUSHDB | Frees the whole dataset | FLUSHALL ASYNC / lazyfree-lazy-user-flush yes |
SMEMBERS, HGETALL, LRANGE 0 -1 on huge keys | Builds a huge reply | SSCAN, HSCAN, paged LRANGE |
SAVE | Writes the RDB file on the main thread | BGSAVE (forked child) |
| Long Lua scripts or functions | Run atomically to completion | Keep scripts bounded (chapter 4.4) |
The lazyfree-* options make implicit deletions asynchronous too. In Redis 8 they all default to no:
lazyfree-lazy-eviction yes # keys evicted by maxmemory
lazyfree-lazy-expire yes # expired keys
lazyfree-lazy-server-del yes # implicit deletes, e.g. SET or RENAME overwriting a big key
lazyfree-lazy-user-del yes # make plain DEL behave like UNLINK
lazyfree-lazy-user-flush yes # FLUSHALL / FLUSHDB without ASYNC behave as ASYNC
Example: DEL vs UNLINK on a 2-million-member set
import time
import redis
r = redis.Redis(decode_responses=True)
def build(key: str, n: int = 2_000_000) -> None:
r.delete(key)
pipe = r.pipeline(transaction=False)
for start in range(0, n, 10_000):
pipe.sadd(key, *range(start, start + 10_000)) # 200 batches of 10k members
pipe.execute()
for cmd in ("DEL", "UNLINK"):
build("big:set")
t0 = time.perf_counter()
r.execute_command(cmd, "big:set")
print(f"{cmd:6} took {(time.perf_counter() - t0) * 1000:.1f} ms")
# Sample run (Redis 8.10, local container):
# DEL took 354.7 ms <- every other client waited ~355 ms
# UNLINK took 0.8 ms <- the key disappears now; memory is freed in the background
UNLINK removes the key from the keyspace immediately (so it is invisible to all clients) and hands the actual freeing to a background thread. Small values are still freed inline, because handing them off would cost more than freeing them.
Key Takeaways
- Client-blocking commands (
BLPOP,XREAD BLOCK,WAIT, ...) park the client without consuming server time; they are the right tool for queues and waiting. - Blocking commands inside
MULTI/EXECor Lua return immediately instead of waiting. - Server-blocking work comes from O(N) operations on large data: prefer
SCANvariants,UNLINK,FLUSHALL ASYNCandBGSAVE. INFO clients(blocked_clients) andCLIENT LIST(flags=b) show parked clients;CLIENT UNBLOCKreleases them.
Practice
- (Beginner) In one terminal run
BLPOP tasks 0. In a second, checkblocked_clients, runPINGto show the server is still responsive, thenRPUSH tasks t1and observe the first terminal.- (Intermediate) Reproduce the
DELvsUNLINKmeasurement with a 1M-field hash and a 1M-member sorted set. WhileDELruns, measure the latency seen by a second client withredis-cli --latency.- (Interview) "A colleague says: 'Never use
BLPOPwith a timeout of 0, it freezes Redis until something is pushed.' Are they right?" Hint: distinguish who waits from who works, and consider what the server does with a parked client.
Command Time Complexity
In a multi-threaded database, a slow query mostly hurts the client that issued it. In Redis, because one thread executes everything, a command's running time is added to the latency of every client queued behind it. That makes the algorithmic cost of each command an operational concern, not only an academic one. Every command page in the Redis documentation states its complexity in Big-O notation, and COMMAND DOCS returns it from the server:
redis-cli COMMAND DOCS LRANGE
# ...
# complexity
# O(S+N) where S is the distance of start offset from HEAD for small lists, from nearest
# end (HEAD or TAIL) for large lists; and N is the number of elements in the specified range.
Reading the notation
- N is usually the number of elements in the key (or keys in the database).
- M is usually the number of elements returned or processed by the command.
- A constant factor hides inside: O(1) commands take around a microsecond; an O(N) command over 1 million elements takes milliseconds to hundreds of milliseconds.
Complexity of common commands
| Command | Complexity | Safe on huge keys? |
|---|---|---|
GET, SET, INCR, HGET, HSET, SADD, SISMEMBER, LPUSH, LPOP | O(1) per element | Yes |
ZSCORE | O(1) | Yes |
ZADD, ZREM, ZRANK | O(log N) | Yes |
ZRANGE by rank or score | O(log N + M) | Yes, if M is small |
LRANGE start stop | O(S + M) | Yes near the ends, slow in the middle |
LINDEX, LSET, LINSERT, LREM | O(N) | Avoid as a random-access pattern on long lists |
HGETALL, SMEMBERS, HKEYS, HVALS | O(N) | No |
SINTER, SUNION, SDIFF | O(total elements involved) | No |
DEL of a collection (also when it expires) | O(N) elements freed | No (use UNLINK or lazy freeing) |
SORT | O(N + M log M) | No |
KEYS | O(N) over the whole database | Never in production |
SCAN, SSCAN, HSCAN, ZSCAN | O(1) per call, O(N) for a full iteration | Yes, done in small steps |
A latency budget
A useful mental model: "how long does this command hold the thread, and how often is it called?" One HGETALL on a 10-field hash is harmless; the same command on a 2-million-field hash takes hundreds of milliseconds and, called once per second, blocks every client for a large fraction of each second. The fix is usually a change of data model (smaller keys) or of access pattern (paging with HSCAN, fetching only needed fields with HMGET).
Finding slow commands: SLOWLOG
The slow log records commands whose execution time (not network time) exceeds a threshold:
redis-cli CONFIG SET slowlog-log-slower-than 10000 # microseconds; 10 ms is the default
redis-cli CONFIG SET slowlog-max-len 128 # entries kept in memory (default 128)
redis-cli SLOWLOG GET 2
# 1) 1) (integer) 14 <- entry id
# 2) (integer) 1762770000 <- Unix timestamp
# 3) (integer) 354712 <- execution time in microseconds (355 ms)
# 4) 1) "DEL" <- command and arguments
# 2) "big:set"
# 5) "10.0.0.12:53122" <- client address
# 6) "" <- client name
redis-cli SLOWLOG RESET
Related tools: the latency monitor (CONFIG SET latency-monitor-threshold 100, then LATENCY LATEST and LATENCY DOCTOR) records spikes from any source, including forks and expiry cycles; redis-cli --bigkeys finds the keys most likely to make O(N) commands slow (chapter 12.1).
Example: the same hash, four ways
import time
import redis
r = redis.Redis(decode_responses=True)
r.delete("bighash")
pipe = r.pipeline(transaction=False)
for start in range(0, 1_000_000, 10_000): # 1M fields, loaded in 100 batches
pipe.hset("bighash", mapping={f"f{i}": i for i in range(start, start + 10_000)})
pipe.execute()
def timed(label, fn):
t0 = time.perf_counter()
fn()
print(f"{label:28} {(time.perf_counter() - t0) * 1000:8.2f} ms")
timed("HGET (1 field)", lambda: r.hget("bighash", "f123")) # O(1)
timed("HMGET (10 fields)", lambda: r.hmget("bighash", [f"f{i}" for i in range(10)])) # O(10)
timed("HSCAN (one call, COUNT 100)", lambda: r.hscan("bighash", 0, count=100)) # ~O(100)
timed("HGETALL (1M fields)", lambda: r.hgetall("bighash")) # O(N)
r.unlink("bighash")
# Sample run (Redis 8.10, local container):
# HGET (1 field) 0.87 ms <- mostly round-trip time
# HMGET (10 fields) 0.62 ms
# HSCAN (one call, COUNT 100) 0.81 ms
# HGETALL (1M fields) 4183.39 ms <- SLOWLOG shows 158 ms of server time:
# every client waited those 158 ms; the
# rest is transferring and decoding ~20 MB
Key Takeaways
- With a single execution thread, the cost of a command is paid by every client waiting behind it.
- O(1) and O(log N) commands are safe at any size; O(N) commands are safe only while N is small.
- Check complexity in the docs or with
COMMAND DOCS; find offenders withSLOWLOG, the latency monitor and--bigkeys. - Fix slow patterns with smaller keys,
SCAN-family paging, partial reads (HMGET, boundedZRANGE) andUNLINK.
Practice
- (Beginner) Set
slowlog-log-slower-thanto 0 (log everything), run a few commands, read them withSLOWLOG GET, then restore the default of 10000.- (Intermediate) Build a 1M-member set and a 1M-member sorted set. Time
SMEMBERS,SSCANwithCOUNT 1000(one call),ZRANGE 0 9andZRANGE 500000 500009. Explain each result with the complexity table.- (Interview) "Every few minutes all our Redis clients see a 200 ms latency spike at the same moment, but CPU usage is low on average. How would you find the cause?" Hint: think about what a single O(N) command does to everyone else, and which built-in tools record execution time per command and latency events per source.
<a id="52-internal-encodings"></a>
5.2 Internal Encodings
This subchapter looks at how Redis stores each data type in memory: the string representation (SDS), the compact listpack used for small collections, the quicklist behind large lists, intsets, the skip list inside sorted sets, incremental rehashing of hash tables, and how to inspect all of this with OBJECT ENCODING.
Every value in Redis is wrapped in a small header, the redisObject, that records the logical type (what commands see: string, list, hash...) and the physical encoding (how the bytes are laid out). One type can have several encodings. Redis picks a compact encoding while a value is small and switches to a faster, larger one as it grows. This is why the same HSET can cost 20 bytes per field in one key and 50 in another.
redisObject (16 bytes on 64-bit builds)
┌──────────┬──────────────┬────────────┬───────┬─────────────────────┬──────────────┐
│ type │ encoding │ refcount │ flags │ lru / lfu │ ptr ─────────┼──▶ actual data
│ (4 bits) │ (4 bits) │ (23 bits) │ │ (24 bits) │ (8 bytes) │ (SDS, listpack,
└──────────┴──────────────┴────────────┴───────┴─────────────────────┴──────────────┘ quicklist, ...)
"hash" "listpack" access info used
by eviction (5.3)
Since Redis 8.2, the object that represents a key-value pair in the keyspace also embeds the key name (and, if set, the expiration time) in the same allocation, saving a separate allocation per key.
Simple Dynamic Strings
C, the language Redis is written in, represents strings as bytes ending with a zero byte (\0). That representation has three problems for a database: finding the length means scanning the whole string (O(N)), a string cannot contain a zero byte (so it is not safe for binary data such as images or serialized objects), and appending requires a fresh allocation and copy every time.
Redis uses its own string type, SDS (Simple Dynamic String), for keys, string values and many internal buffers. An SDS stores a small header in front of the bytes:
header buf (what the sds pointer points to)
┌────────────┬────────────┬───────┐ ┌───┬───┬───┬───┬───┬────┬───────────────┐
│ len = 5 │ alloc = 10 │ flags │ │ h │ e │ l │ l │ o │ \0 │ 5 spare bytes │
└────────────┴────────────┴───────┘ └───┴───┴───┴───┴───┴────┴───────────────┘
O(1) length capacity header binary-safe: len, not \0, marks the end
type
- O(1) length:
STRLENreadsleninstead of scanning. - Binary safe: the end is defined by
len, so values may contain any byte, including\0. - Still C-compatible: the pointer refers to
buf, and a\0is kept after the data, so standard C functions can read SDS strings. - Variable header size: five header types (
sdshdr5,sdshdr8,sdshdr16,sdshdr32,sdshdr64) use 1 to 17 bytes, so short strings do not pay for 64-bit length fields. - Preallocation: when a string grows, Redis allocates extra space. Below 1 MB the new capacity is double the needed length; above 1 MB it adds 1 MB. Repeated
APPENDtherefore causes few reallocations. Shrinking a string does not immediately give the spare space back.
String encodings
A string value uses one of three encodings:
| Encoding | Used when | Layout |
|---|---|---|
int | The value is the canonical text of a 64-bit signed integer ("42", "-7", not "007" or "1e3") | The number is stored in the object itself; no SDS |
embstr | Short strings | Object header and SDS in one allocation; read-only |
raw | Longer strings, or any string after an in-place modification | Object header and SDS in two allocations |
The embstr limit used to be a fixed 44 bytes: the object (16 bytes), the smallest SDS header (3 bytes), 44 bytes of data and the trailing \0 fill exactly one 64-byte allocator slot. Since Redis 8.2, the key is stored in the same allocation as the value object, so the limit depends on the key length: in tests on Redis 8.10, a 1-character key allows 40 bytes, a 10-character key 31 bytes, and a 30-character key 11 bytes.
redis-cli SET n 12345
redis-cli OBJECT ENCODING n # "int"
redis-cli SET code 007
redis-cli OBJECT ENCODING code # "embstr" (leading zero: not canonical)
redis-cli SET s hello
redis-cli OBJECT ENCODING s # "embstr"
redis-cli APPEND s " world"
redis-cli OBJECT ENCODING s # "raw" (embstr is read-only; modifying converts it)
redis-cli SET big 12345678901234567890
redis-cli OBJECT ENCODING big # "embstr" (outside the 64-bit range)
Key Takeaways
- SDS gives O(1) length, binary safety and cheap appends, while staying readable by C functions.
- String values are
int,embstrorraw; small integers and short strings are the cheapest. embstris read-only:APPEND,SETRANGEand similar commands turn it intoraw.- The
embstrthreshold is 44 bytes up to Redis 8.0; from 8.2 the key shares the allocation, so longer keys lower the threshold.
Practice
- (Beginner) Predict, then check with
OBJECT ENCODING, the encoding of these values:"100","-0","3.14","9223372036854775807","9223372036854775808", a 20-byte string, a 200-byte string.- (Intermediate) On your Redis version, find the largest value that is still
embstrfor keys of 1, 10 and 30 characters with a small loop in Python or Bash. Explain the result in terms of a 64-byte allocation.- (Interview) "Why doesn't Redis just use null-terminated C strings?" Hint: consider
STRLENon a 100 MB value, storing a PNG image, and a loop ofAPPENDcalls.
Listpack Encoding
A "real" data structure, such as a hash table, has a high fixed cost per element: an entry struct, pointers (8 bytes each), and the allocator's own bookkeeping for each small allocation. For a hash with 5 fields, those overheads are larger than the data. Small collections are also so short that O(N) scanning is faster in practice than computing hashes and following pointers, because the bytes are contiguous and stay in the CPU cache.
A listpack is a single block of memory in which elements are packed one after the other, with no pointers. It is like writing a short shopping list on one sheet of paper instead of filing each item in its own folder: finding an item means reading the sheet, but for a short list that is quicker than opening folders.
listpack
┌─────────────┬────────────┬─────────────────────┬─────────────────────┬─────┬──────┐
│ total bytes │ num elems │ entry 1 │ entry 2 │ ... │ 0xFF │
│ (4 bytes) │ (2 bytes) │ enc+data │ backlen │ enc+data │ backlen │ │ end │
└─────────────┴────────────┴─────────────────────┴─────────────────────┴─────┴──────┘
│ └── length of this entry, so the list can
│ also be walked backwards from the end
└── small integers fit in 1 byte; short strings need
1 byte of header plus the bytes themselves
Listpacks are used by small lists, hashes, sets and sorted sets (and by stream nodes). Hashes store field and value as two consecutive entries; sorted sets store member and score as two entries kept in score order.
Listpack replaced the older ziplist in Redis 7.0. A ziplist entry stored the length of the previous entry, so growing one entry could force its neighbour to grow, and so on down the list (a "cascade update"). Each listpack entry stores only its own length, which removes that problem. The old configuration names (hash-max-ziplist-entries, ...) are still accepted as aliases.
When a collection leaves listpack
A key is converted to its large encoding as soon as it exceeds either limit:
| Type | Entries limit (default) | Element size limit (default) | Large encoding |
|---|---|---|---|
| Hash | hash-max-listpack-entries 512 | hash-max-listpack-value 64 bytes | hashtable |
| Sorted set | zset-max-listpack-entries 128 | zset-max-listpack-value 64 bytes | skiplist |
| Set (non-integer members) | set-max-listpack-entries 128 | set-max-listpack-value 64 bytes | hashtable |
| List | list-max-listpack-size -2 (8 KB, see "Quicklist") | quicklist |
For hashes, sets and sorted sets, the conversion is one-way: deleting elements later does not convert the key back. Rewriting the key (for example with DUMP/RESTORE, or after a restart that reloads it from an RDB file) re-encodes it compactly if it fits. Hashes with per-field TTLs (HEXPIRE, chapter 2.4) use a variant called listpackex.
Example: measuring the difference
import redis
r = redis.Redis(decode_responses=True)
fields = {f"field:{i}": f"value:{i}" for i in range(100)}
r.delete("compact", "table")
r.hset("compact", mapping=fields) # 100 fields < 512: listpack
r.config_set("hash-max-listpack-entries", 0) # force the large encoding
r.hset("table", mapping=fields)
r.config_set("hash-max-listpack-entries", 512) # restore the default
for key in ("compact", "table"):
print(key, r.object("encoding", key), r.memory_usage(key), "bytes")
# Sample output (Redis 8.10):
# compact listpack 2017 bytes
# table hashtable 4888 bytes <- about 2.4x more for the same data
The same test with 100 members in a sorted set gave 720 bytes as a listpack and 7,973 bytes as a skiplist, a factor of 11.
Tuning trade-off
Raising the limits saves memory but makes every operation on those keys O(N) over a bigger block, and each insertion may reallocate and move the whole block. Values of a few hundred to about a thousand entries are usually reasonable; tens of thousands are not.
Key Takeaways
- A listpack is a contiguous, pointer-free block; it is several times smaller than a hash table or skip list for the same small collection.
- Operations on a listpack are O(N), which is fast only because N is bounded by the
*-max-listpack-*settings. - Exceeding either the entry count or the element size limit converts the key; for hashes, sets and sorted sets the conversion does not reverse on its own.
- Listpack replaced ziplist in Redis 7.0 to remove cascading updates; the old
*-ziplist-*names remain as aliases.
Practice
- (Beginner) Create a hash with 3 short fields and check
OBJECT ENCODING. Add one field whose value is 65 bytes long and check again.- (Intermediate) Store 10,000 user profiles of 6 short fields each as 10,000 hashes, then repeat with
hash-max-listpack-entries 0. Compareused_memoryfromINFO memoryand compute the bytes per profile in each case.- (Interview) "To save memory, a teammate proposes
hash-max-listpack-entries 100000. What could go wrong?" Hint: think about the cost ofHSETandHGETon a 2 MB contiguous block, and what happens to latency for all clients.
Quicklist
Lists have two common shapes: tiny lists (a few recent items) and very long lists (a queue with millions of jobs). A single listpack is ideal for the first, but inserting at the head of a 50 MB listpack means moving 50 MB of memory. A classic doubly linked list handles long lists well, but spends two pointers plus an allocation on every element, which can be more than the element itself.
A quicklist combines both: a doubly linked list whose nodes are listpacks. Pushing or popping at either end touches only the first or last node, and the pointer overhead is paid once per node (thousands of elements) rather than once per element. It is like a train: the cars (nodes) are linked, and each car is packed full of passengers (elements).
quicklist
head tail
│ │
▼ ▼
┌─────────────┐ ⇄ ┌─────────────┐ ⇄ ┌─────────────┐ ⇄ ┌─────────────┐
│ listpack │ │ listpack │ │ listpack │ │ listpack │
│ ≤ 8 KB │ │ LZF- │ │ LZF- │ │ ≤ 8 KB │
│ e1 e2 e3 … │ │ compressed │ │ compressed │ │ … e98 e99 │
└─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘
uncompressed inner nodes compressed when uncompressed
(depth 1) list-compress-depth = 1 (depth 1)
Configuration
list-max-listpack-size sets the size of each node:
| Value | Meaning |
|---|---|
-1 | 4 KB per node |
-2 | 8 KB per node (default) |
-3, -4, -5 | 16 KB, 32 KB, 64 KB per node |
| Positive N | At most N elements per node, whatever their size |
list-compress-depth compresses inner nodes with LZF. The value is the number of nodes at each end left uncompressed, because pushes and pops happen there. 0 (default) disables compression; 1 keeps head and tail plain and compresses everything else. Compression saves memory for long lists of compressible data at the cost of CPU when middle elements are accessed.
Small lists are plain listpacks
Since Redis 7.2, a list that fits in a single node is stored as a plain listpack with no quicklist wrapper. It becomes a quicklist when it outgrows one node, and turns back into a listpack when it shrinks to half of the node limit (the margin prevents flapping between the two forms).
redis-cli RPUSH small a b c
redis-cli OBJECT ENCODING small # "listpack"
# 200 elements of 100 bytes each, about 20 KB: more than one 8 KB node
redis-cli RPUSH long $(for i in $(seq 200); do printf 'x%.0s' $(seq 100); echo -n ' '; done)
redis-cli OBJECT ENCODING long # "quicklist"
redis-cli LTRIM long 0 9 # keep 10 elements, about 1 KB
redis-cli OBJECT ENCODING long # "listpack" (lists do convert back)
Complexity in practice
LPUSH, RPUSH, LPOP and RPOP are O(1). Index-based access (LINDEX, LSET, LRANGE with a large offset) is O(N) in theory, but the quicklist skips whole nodes using their element counts, so it walks nodes rather than elements, starting from the nearer end. That keeps moderate lists fast, but it remains a poor fit for random access on very large lists; use a sorted set or hash when you need it.
Key Takeaways
- A quicklist is a doubly linked list of listpack nodes: O(1) at both ends, with pointer overhead paid per node, not per element.
list-max-listpack-size(default-2, 8 KB) controls node size;list-compress-depthoptionally LZF-compresses inner nodes.- Since Redis 7.2, lists that fit in one node are plain listpacks, and they convert back when they shrink to half the limit.
- Index access walks nodes from the nearer end; lists are best used through their ends.
Practice
- (Beginner) Push elements to a list one at a time and find the size at which
OBJECT ENCODINGchanges fromlistpacktoquicklistfor 10-byte elements and for 1,000-byte elements.- (Intermediate) Load a list of 1M JSON strings (about 200 bytes each, with repetitive content). Compare
MEMORY USAGEwithlist-compress-depth 0and1, rebuilding the list after each change. Then timeLINDEX key 500000in both cases.- (Interview) "Why doesn't Redis implement lists as a plain doubly linked list of elements, or as one big array?" Hint: estimate the per-element overhead of the first, and the cost of
LPUSHon the second for a list of 10 million elements.
Intset
Sets of integers are very common: IDs of users who liked a post, IDs of products in a category, numeric tags. Storing each ID as a string in a hash table wastes memory, and a listpack still stores each element with its own header. An intset stores such sets as a sorted array of integers, all of the same width.
intset
┌───────────────┬──────────┬────────┬────────┬────────┬────────┐
│ encoding │ length │ 3 │ 17 │ 250 │ 9000 │ sorted, fixed width
│ INT16 (2 B) │ 4 │ 2 bytes│ 2 bytes│ 2 bytes│ 2 bytes│
└───────────────┴──────────┴────────┴────────┴────────┴────────┘
SADD ids 100000 (does not fit in 16 bits) ──▶ upgrade: every element rewritten
┌───────────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ INT32 (4 B) │ 5 │ 3 │ 17 │ 250 │ 9000 │ 100000 │
└───────────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
- Lookup (
SISMEMBER) is a binary search: O(log N). - Insertion keeps the array sorted, so it may shift elements: O(N), cheap for N ≤ 512.
- Upgrade: the width is the smallest of 16, 32 or 64 bits that fits every element. Adding a larger number rewrites the whole array with the wider type. Removing it later does not downgrade the width.
- Because the array is sorted,
SMEMBERSon an intset returns members in ascending order. Do not rely on this: the order changes as soon as the set is converted.
Conversions
| Situation | Result |
|---|---|
All members are integers and count ≤ set-max-intset-entries (512) | intset |
| A non-integer member is added, and the set is small enough for a listpack (≤ 128 members, ≤ 64 bytes each) | listpack (Redis 7.2+) |
| More than 512 integer members, or a non-integer added to a set larger than the listpack limits | hashtable |
redis-cli SADD ids 1 2 3
redis-cli OBJECT ENCODING ids # "intset"
redis-cli SADD ids x
redis-cli OBJECT ENCODING ids # "listpack" (non-integer, still small)
redis-cli SADD more $(seq 1 513)
redis-cli OBJECT ENCODING more # "hashtable" (more than 512 integers)
In a test on Redis 8.10, a set of the integers 1 to 100 used 231 bytes as an intset and 3,097 bytes as a hash table.
Key Takeaways
- An intset is a sorted array of same-width integers: compact, with O(log N) lookups and O(N) inserts.
- Adding a wider integer upgrades the whole array to 32 or 64 bits; there is no downgrade.
- A non-integer member or more than
set-max-intset-entries(512) members converts the set tolistpackorhashtable. - Keep ID sets numeric (no prefixes such as
"user:42") when you want them to stay intsets.
Practice
- (Beginner) Create a set with members
1 2 3, check its encoding, add70000, and useMEMORY USAGEbefore and after to observe the width upgrade.- (Intermediate) Store 400 user IDs once as
"1001","1002", ... and once as"user:1001","user:1002", .... Compare encodings andMEMORY USAGE. What does this suggest about naming members?- (Interview) "Why is an intset insert O(N), and why is that acceptable?" Hint: consider how a sorted array makes room for a new element, and the maximum N for this encoding.
Skiplists in Sorted Sets
A large sorted set must support three kinds of query efficiently: "what is the score of member X?" (ZSCORE), "give me the members ranked 100 to 110 or with scores between 50 and 80" (ZRANGE), and "what is X's rank?" (ZRANK). No single classic structure does all three well. A hash table answers the first in O(1) but knows nothing about order. A sorted array answers range queries but makes inserts O(N). Balanced trees work but are complex to implement, especially with rank queries.
Redis's large sorted-set encoding (skiplist) therefore uses two structures that reference the same members:
- a hash table mapping member to score, for O(1)
ZSCOREand existence checks; - a skip list ordered by (score, member), for ranges and ranks in O(log N).
How a skip list works
A skip list is a sorted linked list with "express lanes". Every node is on level 1. Some nodes also appear on level 2, fewer on level 3, and so on. To search, you start on the highest level and move right while the next node is still smaller than the target, then drop one level and repeat. It is like a subway system with local and express lines: you ride the express as far as possible, then switch to the local for the last few stops.
Searching for score 70:
level 4 HEAD ─────────────────────────────────────────────▶ 50 ─────────────────────────▶ NULL
level 3 HEAD ──────────────────▶ 20 ──────────────────────▶ 50 ─────────────────────────▶ NULL
level 2 HEAD ────────▶ 10 ─────▶ 20 ─────────▶ 40 ────────▶ 50 ────────▶ 70 ────────────▶ NULL
level 1 HEAD ─▶ 5 ──▶ 10 ─▶ 15 ▶ 20 ─▶ 30 ──▶ 40 ─▶ 45 ──▶ 50 ─▶ 60 ──▶ 70 ─▶ 80 ─────▶ NULL
Path: L4 HEAD→50, next is NULL: drop to L3 → next NULL: drop to L2 → 70 found.
When a node is inserted, its height is chosen randomly: each extra level is added with probability 1/4 (Redis's ZSKIPLIST_P = 0.25), up to 32 levels. On average a node has 1.33 forward pointers, and searches take O(log N) steps. Redis adds two refinements:
- each forward pointer stores a span, the number of level-1 nodes it skips. Summing spans along the search path gives a member's rank, which makes
ZRANKandZRANGEby index O(log N); - each node has a backward pointer on level 1, so
ZREVRANGEcan walk from the tail.
A minimal skip list in Python
import random
P, MAX_LEVEL = 0.25, 32
class Node:
def __init__(self, score: float, member: str, level: int):
self.score, self.member = score, member
self.forward: list["Node | None"] = [None] * level # one pointer per level
class SkipList:
def __init__(self):
self.head = Node(float("-inf"), "", MAX_LEVEL)
self.level = 1
@staticmethod
def random_level() -> int:
level = 1
while random.random() < P and level < MAX_LEVEL: # 1/4 chance per extra level
level += 1
return level
def insert(self, score: float, member: str) -> None:
update = [self.head] * MAX_LEVEL # last node visited on each level
x = self.head
for i in range(self.level - 1, -1, -1): # top level down
while x.forward[i] and (x.forward[i].score, x.forward[i].member) < (score, member):
x = x.forward[i]
update[i] = x
lvl = self.random_level()
self.level = max(self.level, lvl)
node = Node(score, member, lvl)
for i in range(lvl): # splice into each of its levels
node.forward[i] = update[i].forward[i]
update[i].forward[i] = node
def range_by_score(self, lo: float, hi: float) -> list[tuple[str, float]]:
x = self.head
for i in range(self.level - 1, -1, -1): # O(log N) descent to lo
while x.forward[i] and x.forward[i].score < lo:
x = x.forward[i]
x, out = x.forward[0], []
while x and x.score <= hi: # then walk level 1: O(M)
out.append((x.member, x.score))
x = x.forward[0]
return out
sl = SkipList()
for i in range(100_000):
sl.insert(random.random() * 1000, f"m{i}")
print(sl.range_by_score(500.0, 500.05)) # a handful of members, found in ~log N steps
When the skip list is used
Small sorted sets use a listpack (members and scores in score order). The conversion to skiplist happens above zset-max-listpack-entries (128) members or when a member exceeds zset-max-listpack-value (64 bytes), and is not reversed when the set shrinks.
| Operation | Complexity (skiplist encoding) |
|---|---|
ZSCORE, ZMSCORE per member | O(1) via the hash table |
ZADD, ZREM, ZINCRBY | O(log N) |
ZRANK, ZREVRANK | O(log N) via spans |
ZRANGE by rank, score or lex | O(log N + M) |
ZCARD | O(1) |
Key Takeaways
- Large sorted sets combine a hash table (member to score) and a skip list (ordered by score, then member).
- A skip list is a layered linked list with random node heights (p = 1/4, max 32 levels) that gives O(log N) search, insert and delete.
- Spans make rank queries O(log N); a backward pointer supports reverse iteration.
- Small sorted sets (≤ 128 members of ≤ 64 bytes) are listpacks; conversion to
skiplistis one-way.
Practice
- (Beginner) Add 128 members to a sorted set and check
OBJECT ENCODING; add one more and check again. CompareMEMORY USAGEbefore and after.- (Intermediate) Extend the Python skip list with spans so that it can return the rank of a member in O(log N). Verify it against a sorted Python list for 10,000 random inserts.
- (Interview) "Why does Redis use a skip list rather than a balanced tree such as a red-black tree for sorted sets?" Hint: compare implementation complexity, how range scans proceed once the start is found, how easily rank can be added, and how the probability p trades memory for speed.
Hash Table Rehashing
Redis's main keyspace is a hash table (Redis calls it a dict), and so are large hashes, sets and the member index of large sorted sets. A hash table is fast only while it has enough buckets for its elements; when it fills up, chains grow and lookups slow down. It must then be resized, which means moving every element to a new, larger table, because an element's bucket depends on the table size. For a keyspace with 50 million keys, doing this in one go would stop the server for seconds.
Redis avoids that pause with incremental rehashing: it keeps the old and the new table side by side and moves elements a few buckets at a time. Think of moving house over several weeks rather than in one day: every time you visit, you carry one box. Until the move is finished, you check both homes when looking for something, but new purchases go straight to the new home.
Rehashing in progress (rehashidx = 3: buckets 0..2 already moved)
ht[0] (old, 8 buckets) ht[1] (new, 16 buckets)
┌───┐ ┌───┐
│ 0 │ (empty, moved) │ 0 │──▶ k8
│ 1 │ (empty, moved) │ 1 │──▶ k1
│ 2 │ (empty, moved) │ 2 │
│ 3 │──▶ k3 ──▶ k11 ◀── next │ 3 │
│ 4 │──▶ k4 │ ...
│ ... │ 9 │──▶ k9
│ 7 │──▶ k7 │ ...
└───┘ └───┘
GET k4 : look in ht[0], then ht[1]
SET new: insert into ht[1] only
any op : also move one bucket (and up to 10 empty buckets) from ht[0] to ht[1]
cron : with activerehashing yes, spend up to 1 ms per serverCron call moving buckets
The rules
- Initial size is 4 buckets; sizes are always powers of two.
- Expansion starts when the number of elements reaches the number of buckets (load factor 1). The new table is the next power of two that fits.
- Shrinking starts when the table is less than 1/8 full (12.5%).
- Each operation on a rehashing table (lookup, insert, delete) migrates one bucket. Idle tables are migrated by
serverCron, which spends up to 1 ms per call on it whenactiverehashing yes(the default). - During a fork (RDB snapshot or AOF rewrite, chapter 6), resizing is postponed, because moving elements touches memory pages and multiplies copy-on-write. It happens anyway only if the table becomes 4 times overloaded (or 32 times too large when shrinking).
- Memory limit: allocating the new bucket array can be large: going from 2^26 to 2^27 buckets allocates 2^27 × 8 bytes = 1 GiB at once. Recent versions skip an expansion that would push memory over
maxmemorywhile the load factor is still moderate (below about 1.6); past that point the table expands anyway.
SCAN remains correct during rehashing because its cursor iterates over bucket indexes in reversed-bit order, which visits each bucket of both table sizes in a compatible sequence. Every element present for the whole scan is returned at least once.
Simulating it
class IncrementalDict:
"""Toy dict with chained buckets and incremental rehashing (no shrinking)."""
def __init__(self):
self.tables = [[[] for _ in range(4)], None] # ht[0], ht[1]
self.used = 0
self.rehashidx = -1 # -1 = not rehashing
def _bucket(self, table, key):
return table[hash(key) & (len(table) - 1)] # size is a power of two
def _step(self):
"""Move one non-empty bucket from ht[0] to ht[1]."""
if self.rehashidx == -1:
return
old, new = self.tables
while self.rehashidx < len(old) and not old[self.rehashidx]:
self.rehashidx += 1 # skip empty buckets
if self.rehashidx < len(old):
for k, v in old[self.rehashidx]:
self._bucket(new, k).append((k, v))
old[self.rehashidx] = []
self.rehashidx += 1
if self.rehashidx >= len(old): # done: new table becomes ht[0]
self.tables, self.rehashidx = [new, None], -1
def set(self, key, value):
self._step()
if self.rehashidx == -1 and self.used >= len(self.tables[0]):
self.tables[1] = [[] for _ in range(len(self.tables[0]) * 2)]
self.rehashidx = 0 # start a new rehash
for t in self.tables: # update in place if present
if t is None:
continue
bucket = self._bucket(t, key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
target = self.tables[1] if self.rehashidx != -1 else self.tables[0]
self._bucket(target, key).append((key, value)) # new keys go to the new table
self.used += 1
def get(self, key):
self._step()
for t in self.tables: # check both tables
if t is not None:
for k, v in self._bucket(t, key):
if k == key:
return v
return None
d = IncrementalDict()
for i in range(1000):
d.set(f"k{i}", i)
assert all(d.get(f"k{i}") == i for i in range(1000))
print("buckets:", len(d.tables[0]), "rehashing:", d.rehashidx != -1)
Observing it
redis-cli MEMORY STATS | grep -A1 hashtable
# overhead.hashtable.main <- bucket arrays of the keyspace
# overhead.db.hashtable.rehashing <- memory of tables currently being rehashed
redis-cli INFO memory | grep mem_overhead_db_hashtable_rehashing
A sudden jump in used_memory when a keyspace crosses a power of two (for example from 33.5M to 67.1M keys in one table) is the new bucket array being allocated.
Key Takeaways
- Redis hash tables grow and shrink by powers of two, at load factor 1 (expand) and below 1/8 (shrink).
- Rehashing is incremental: two tables coexist, each operation moves one bucket, and
serverCronmoves more in 1 ms slices. - Lookups check both tables; inserts go to the new one;
SCANstays correct thanks to its reverse-binary cursor. - Resizing is postponed during forks to limit copy-on-write, and the new bucket array can be a large, sudden allocation.
Practice
- (Beginner) Run the Python simulation and print
rehashidxafter eachsetfor the first 40 inserts. Mark where each rehash starts and ends.- (Intermediate) Add shrinking to the simulation: when
usedfalls below 1/8 of the bucket count after a delete, rehash into a table of the next power of two that fits. Test with 1,000 inserts followed by 990 deletes.- (Interview) "Why does Redis rehash incrementally instead of resizing all at once, and what does it cost?" Hint: consider latency for 50 million keys, the extra memory of two tables, and the work added to lookups during the transition.
OBJECT ENCODING
TYPE tells you the logical type of a key; OBJECT ENCODING tells you how it is actually stored. Checking encodings is the first step whenever memory usage looks wrong or a "small" key behaves slowly, and it is how you confirm that a memory optimization (smaller hashes, numeric set members) really works.
Possible encodings by type
TYPE | Encodings | Notes |
|---|---|---|
string | int, embstr, raw | Bitmaps and HyperLogLogs are strings and show raw |
list | listpack, quicklist | Lists can convert back to listpack when they shrink |
set | intset, listpack, hashtable | |
hash | listpack, listpackex, hashtable | listpackex: small hash with field TTLs |
zset | listpack, skiplist | Geospatial indexes are sorted sets |
stream | stream | A radix tree of listpacks (chapter 3.4) |
Module types (ReJSON-RL, vectorset, ...) | raw | The module manages its own layout |
The OBJECT command
| Subcommand | Returns | Notes |
|---|---|---|
OBJECT ENCODING key | Encoding name | |
OBJECT IDLETIME key | Seconds since last access | Error if an LFU policy is active |
OBJECT FREQ key | Logarithmic access counter (5.3) | Error unless an LFU policy is active |
OBJECT REFCOUNT key | Reference count of the value | Mostly of historical interest |
OBJECT HELP | Usage |
OBJECT IDLETIME does not itself count as an access, so you can inspect keys without changing their eviction ranking. The DEBUG OBJECT command shows more detail (such as the serialized length), but DEBUG is disabled by default since Redis 7.0 (enable-debug-command no).
Example: an encoding audit
from collections import Counter
import redis
r = redis.Redis(decode_responses=True)
def describe(keys: list[str]) -> list[tuple[str, str]]:
pipe = r.pipeline(transaction=False) # 2 commands per key, 1 round trip
for k in keys:
pipe.type(k)
pipe.object("encoding", k)
replies = pipe.execute()
return list(zip(replies[0::2], replies[1::2])) # [(type, encoding), ...]
def audit(match: str = "*", limit: int = 100_000) -> Counter:
"""Count (type, encoding) pairs over up to `limit` keys, without blocking the server."""
counts, batch = Counter(), []
for i, key in enumerate(r.scan_iter(match=match, count=1000)): # SCAN, never KEYS
if i >= limit:
break
batch.append(key)
if len(batch) == 500:
counts.update(describe(batch))
batch = []
if batch:
counts.update(describe(batch))
return counts
for (typ, enc), count in audit("user:*").most_common():
print(f"{typ:8} {enc:10} {count}")
# hash listpack 9812
# hash hashtable 188 <- which users have oversized profiles, and why?
Key Takeaways
OBJECT ENCODINGshows the physical representation behind the logicalTYPE.- Compact encodings (
int,embstr,listpack,intset) mean the key is small and cheap;hashtable,skiplistandquicklistmean it has outgrown them. OBJECT IDLETIME(LRU policies) andOBJECT FREQ(LFU policies) expose eviction metadata without touching the key.- Audit encodings with
SCANplus pipelinedOBJECT ENCODING, never withKEYS.
Practice
- (Beginner) Create one key of each type (string, list, set, hash, sorted set, stream, geospatial index, HyperLogLog) and record
TYPEandOBJECT ENCODINGfor each.- (Intermediate) Run the audit script on a test dataset where 2% of hashes have one value longer than 64 bytes. Extend it to report which field caused each
hashtableencoding.- (Interview) "Memory usage grew 40% after a release, but the number of keys did not change. How would you investigate?" Hint: think about which encoding thresholds a code change could cross, and how to compare encodings and per-key memory between a sample of old and new keys.
<a id="53-memory-management"></a>
5.3 Memory Management
This subchapter covers what happens as Redis's memory fills up: how to cap memory with maxmemory, which eviction policy decides what to remove, how the approximated LRU and LFU algorithms work, how expired keys are actually reclaimed, why the operating system may report more memory than Redis uses (fragmentation), and the commands for measuring memory per key and per instance.
maxmemory Configuration
Redis keeps the whole dataset in RAM. If it grows past the physical memory of the machine, one of two bad things happens: the OS starts swapping Redis pages to disk, and latency jumps from microseconds to milliseconds or worse; or the Linux out-of-memory killer terminates the process, losing everything that was not persisted. A cache that may grow without bound needs a ceiling and a rule for what to do at the ceiling.
maxmemory is that ceiling. When the memory Redis has allocated for data exceeds it, Redis applies the configured eviction policy before running each command that may need memory: it either removes keys or refuses the command.
# redis.conf
maxmemory 4gb # units: b, kb, mb, gb (1gb = 1024^3 bytes)
maxmemory-policy allkeys-lru # what to do at the limit (see "Eviction Policies")
redis-cli CONFIG SET maxmemory 4gb # can be changed at runtime
redis-cli CONFIG GET maxmemory
redis-cli INFO memory | grep -E '^(used_memory|maxmemory)(_human)?:'
# used_memory:1874360
# used_memory_human:1.79M
# maxmemory:4294967296
# maxmemory_human:4.00G
What counts toward the limit
- Redis compares
used_memory, the bytes obtained from its allocator, withmaxmemory. That is not the same as the process's resident memory (RSS), which also includes fragmentation (see "Memory Fragmentation and Active Defrag"). - Output buffers of replicas and the AOF buffers are subtracted before the comparison, so that replication traffic cannot trigger eviction of data.
- Client buffers (query and output buffers of normal clients) do count.
maxmemory-clients(Redis 7.0+, default 0 = unlimited) caps their total and disconnects the most expensive clients instead of evicting data. maxmemory 0(the default) means no limit on 64-bit builds.- Replicas ignore
maxmemoryby default (replica-ignore-maxmemory yes): they delete keys only when the master tells them to, which keeps them identical to the master. Give replicas at least as much memory as the master.
What happens with noeviction
noeviction is the default policy. At the limit, commands that may add data (SET, LPUSH, HSET, ...) fail with an OOM error; reads and deletions keep working.
import redis
r = redis.Redis(decode_responses=True)
r.config_set("maxmemory", "4mb")
r.config_set("maxmemory-policy", "noeviction")
try:
for i in range(1_000_000):
r.set(f"k:{i}", "x" * 100)
except redis.exceptions.OutOfMemoryError as e: # subclass of ResponseError
print(f"rejected at key {i}: {e}")
# sample run: rejected at key 6552: command not allowed when used memory > 'maxmemory'.
finally:
r.config_set("maxmemory", "0") # remove the limit again (test only)
Sizing
maxmemory should be well below the machine's RAM, because Redis needs memory beyond its dataset:
| Consumer | Why it needs headroom |
|---|---|
| Fork for RDB / AOF rewrite (chapter 6) | Copy-on-write duplicates pages modified during the save; with heavy writes, up to the size of the dataset |
| Fragmentation | RSS is typically 10-50% above used_memory |
| Replication backlog and replica buffers | Excluded from the limit but still real memory |
| Client buffers, Lua, OS page cache | Grow with load |
A common starting point is 60-75% of RAM when persistence uses fork, and higher (around 80-90%) for a pure cache without persistence. Monitor used_memory_rss and adjust.
Key Takeaways
maxmemorycaps the memory Redis uses for data;0means unlimited, which is risky for caches.- The limit is checked against allocator memory (
used_memory), not RSS, and excludes replica output and AOF buffers. - With the default
noevictionpolicy, writes fail withOOMerrors at the limit while reads continue. - Leave headroom for fork copy-on-write, fragmentation and buffers; replicas need at least as much memory as the master.
Practice
- (Beginner) On a test instance, set
maxmemory 5mb, keep the default policy, and write keys in a loop until you get theOOMerror. Confirm thatGETandDELstill work.- (Intermediate) A server has 16 GB of RAM, uses RDB snapshots, and its write rate modifies about 30% of the dataset during a snapshot. Propose a
maxmemoryvalue and justify each part of the headroom.- (Interview) "Redis is configured with
maxmemory 10gb, yet the Linux OOM killer terminated it on a 12 GB machine. How can that happen?" Hint: list the memory thatmaxmemorydoes not cover, and think about what happens during aBGSAVE.
Eviction Policies (LRU, LFU, TTL, Random)
When Redis is used as a cache, hitting maxmemory is normal and an error is the wrong response: the right response is to drop the entries least likely to be needed again. Which entries those are depends on the workload, so Redis offers several policies, set with maxmemory-policy. Each policy answers two questions: which keys are candidates (all keys, or only keys with a TTL) and how to rank them.
| Policy | Candidates | Evicts first | Typical use |
|---|---|---|---|
noeviction (default) | None | Nothing; writes return OOM | Primary data store, queues, data that must not vanish |
allkeys-lru | All keys | Least recently used | General-purpose cache; the safest default for caches |
allkeys-lfu | All keys | Least frequently used | Caches with stable popular keys (catalogs, configs) |
allkeys-random | All keys | Random | Uniform access patterns; lowest CPU cost |
allkeys-lrm (8.6+) | All keys | Least recently modified | Data whose value comes from being kept up to date |
volatile-lru | Keys with a TTL | Least recently used | Cache and persistent data sharing one instance |
volatile-lfu | Keys with a TTL | Least frequently used | Same, with frequency ranking |
volatile-random | Keys with a TTL | Random | Same, cheapest |
volatile-ttl | Keys with a TTL | Shortest remaining TTL | When TTLs encode priority ("expires soonest, least valuable") |
volatile-lrm (8.6+) | Keys with a TTL | Least recently modified | As allkeys-lrm, protecting keys without TTL |
How to choose
Must every key survive (queues, sessions, source of truth)?
└─ yes ──▶ noeviction, size memory properly and alert on usage
└─ no ──▶ Do some keys have no TTL and must survive?
└─ yes ──▶ volatile-lru / volatile-lfu (and put TTLs on everything evictable)
└─ no ──▶ Is popularity stable over time?
└─ yes ──▶ allkeys-lfu
└─ no / unsure ──▶ allkeys-lru
Notes on specific policies:
volatile-*with no TTL keys left behaves likenoeviction: writes start failing. Check that evictable keys really have TTLs.- LRM (least recently modified) policies, added in Redis 8.6, update a key's recency only on writes. Reads, including scans by analytics jobs, do not keep a key alive. They suit data such as cached aggregates or feature values that a background job refreshes: entries the job stopped refreshing are evicted first, even if they are still read often.
volatile-ttluses the remaining TTL as a priority signal. It works only if your application sets TTLs deliberately with that meaning.
The eviction process
Before executing a command, Redis checks whether memory is over the limit. If so, it evicts keys, using the policy, until it is under the limit again, and only then runs the command. Large evictions are bounded by maxmemory-eviction-tenacity (default 10, range 0-100): when the time budget is used up, the command proceeds and eviction continues in the background on later event loop iterations. With lazyfree-lazy-eviction yes, the memory of evicted keys is freed in a background thread, which keeps eviction of large keys from stalling the loop.
redis-cli CONFIG SET maxmemory 3mb
redis-cli CONFIG SET maxmemory-policy allkeys-lru
# write 20,000 keys of 100 bytes: all writes succeed, older keys are evicted
redis-cli INFO stats | grep -E 'evicted_keys|total_eviction_exceeded_time'
# evicted_keys:10505 <- sample run on Redis 8.10; 9,331 keys remain
# total_eviction_exceeded_time:0 <- ms spent above the limit (eviction kept up)
Watch evicted_keys over time: a cache that evicts steadily is working as designed, while sudden eviction in a database that should hold everything is an incident.
Key Takeaways
maxmemory-policychooses the candidates (allkeys-*orvolatile-*) and the ranking (LRU, LFU, LRM, TTL, random), ornoeviction.allkeys-lruis the usual cache default;allkeys-lfuworks better when the popular set is stable.volatile-*policies only evict keys with TTLs and act likenoevictionwhen none are left.- LRM policies (Redis 8.6+) rank by last write, ignoring reads.
- Eviction runs before commands and continues in the background when it exceeds its time budget; monitor
evicted_keys.
Practice
- (Beginner) With
maxmemory 3mbandallkeys-random, write 20,000 keys and recordevicted_keysandDBSIZE. Repeat withnoevictionand compare.- (Intermediate) Fill a capped instance with 10,000 "hot" keys that you read repeatedly and 50,000 "cold" keys written once. Under
allkeys-lruand thenallkeys-lfu, write 20,000 new keys and measure how many hot keys survive in each case.- (Interview) "One Redis instance stores both user sessions, which must not be lost, and a page cache. Which eviction policy would you choose, and what must the application guarantee for it to work?" Hint: consider which keys have TTLs, what
volatile-*does when no candidate exists, and whether separate instances would be simpler.
Approximated LRU and LFU
Exact LRU is simple in theory: keep all keys in a linked list ordered by last access, move a key to the front on each access, and evict from the back. For Redis this is expensive. Each key would need two extra pointers (16 bytes, more than many small values), and every read would have to update a shared list. Exact LFU is worse, because it needs a priority queue ordered by frequency.
Redis chooses approximation: it stores a little access metadata in each object and, at eviction time, compares a random sample of keys. A good analogy is a librarian who must remove books from a full shelf. Instead of keeping a perfect log of every loan, each book has a stamp with its last loan date. The librarian pulls five books at random, discards the one with the oldest stamp, and keeps a short list of "good candidates" seen during earlier rounds.
LRU: a 24-bit clock
Each object has a 24-bit field (see the redisObject diagram in 5.2). Under LRU policies it stores the time of last access from a global clock with one-second resolution (the clock wraps after about 194 days, which Redis handles). OBJECT IDLETIME key shows the derived idle time.
The eviction pool
Each eviction round:
1. sample maxmemory-samples keys (default 5) from the keyspace (or the expires table)
2. compute a score for each (idle time, inverse frequency, or TTL)
3. insert them into the eviction pool, a 16-entry array sorted by score,
keeping only the best candidates seen so far
4. evict the best candidate in the pool that still exists
pool: [ idle 9s | idle 40s | idle 300s | ... | idle 7200s ] ──▶ evict "idle 7200s"
worst candidate ───────────────────────── best candidate
Because the pool persists across rounds, the algorithm accumulates good candidates over time and approximates true LRU closely. maxmemory-samples trades CPU for accuracy: 5 is a good default, 10 is very close to exact LRU, 3 is faster but less precise.
LFU: a logarithmic counter with decay
Under LFU policies the same 24 bits are split in two:
16 bits 8 bits
┌─────────────────────────────────────┬──────────────────────┐
│ last decrement time (minutes) │ log counter (0..255) │
└─────────────────────────────────────┴──────────────────────┘
Eight bits can only count to 255, so the counter is logarithmic: each access increments it with a probability that falls as the counter grows. New keys start at 5, so they are not evicted before they have a chance to be accessed. The probability is:
p = 1 / ((counter - 5) * lfu-log-factor + 1) (p = 1 while counter <= 5)
The counter also decays: when a key is examined, it is decremented by one for every lfu-decay-time minutes (default 1) since the last decrement. Without decay, a key that was popular last month would stay protected forever.
Approximate counter values after N accesses, simulated with this formula (decay ignored):
lfu-log-factor | 100 hits | 1,000 hits | 100K hits | 1M hits | 10M hits |
|---|---|---|---|---|---|
| 0 | 105 | 255 | 255 | 255 | 255 |
| 1 | 19 | 50 | 255 | 255 | 255 |
| 10 (default) | 9 | 19 | 145 | 255 | 255 |
| 100 | 7 | 10 | 48 | 152 | 255 |
A higher factor distinguishes better among very popular keys; a lower one distinguishes better among rarely used keys.
import redis
r = redis.Redis(decode_responses=True)
r.config_set("maxmemory-policy", "allkeys-lfu") # OBJECT FREQ requires an LFU policy
r.set("hot", 1)
r.set("cold", 1)
for _ in range(50):
r.get("hot")
print("hot:", r.object("freq", "hot")) # 7 to 9 in test runs: starts at 5, increments are probabilistic
print("cold:", r.object("freq", "cold")) # 5
r.config_set("maxmemory-policy", "noeviction")
redis-cli --hotkeys uses OBJECT FREQ to list the most frequently accessed keys, so it also requires an LFU policy.
Key Takeaways
- Redis approximates LRU and LFU by sampling
maxmemory-sampleskeys and keeping a 16-entry pool of the best eviction candidates. - LRU stores a 24-bit last-access time per object; LFU stores a 16-bit decay timestamp and an 8-bit logarithmic counter in the same space.
- LFU counters start at 5, grow with probability
1/((c-5)*lfu-log-factor+1)and decay everylfu-decay-timeminutes. OBJECT IDLETIMEworks only under non-LFU policies, andOBJECT FREQand--hotkeysonly under LFU policies.
Practice
- (Beginner) Switch to
allkeys-lfu, create a key, read it 10, 100 and 1,000 times, and recordOBJECT FREQafter each step. Compare with the table.- (Intermediate) Write a simulation of the LFU counter in Python, including decay: access a key 10,000 times in the first minute, then never again, and plot the counter over 30 minutes for
lfu-decay-timevalues 1 and 10.- (Interview) "Why doesn't Redis implement exact LRU with a linked list, like most textbook caches?" Hint: estimate the memory cost per key for 100 million small keys, and consider what every
GETwould have to modify.
Expiration Algorithm (Lazy and Active)
Setting a TTL is easy (EXPIRE, SET ... EX, chapter 2.1), but removing a key at the exact moment it expires is not. An instance may hold tens of millions of keys with TTLs. A timer per key would cost memory and CPU, and scanning all keys every second would block the loop. Redis instead combines two cheap strategies: check a key when someone touches it, and clean up the rest in small random batches.
Every key with a TTL has an entry in a separate per-database expires table that maps the key to its absolute expiration time in milliseconds.
Lazy (passive) expiration
Every command that looks up a key first checks the expires table. If the key's time has passed, Redis deletes it and behaves as if it never existed. A client can therefore never read an expired value, no matter how long ago it expired.
Lazy expiration alone is not enough: a key that is never read again would stay in memory forever.
Active expiration
Redis also runs an active expire cycle, like a cleaner who checks a few random rooms each round and works longer when they find many dirty ones:
Slow cycle: runs from serverCron, hz times per second (default 10)
for each database:
repeat:
take 20 keys with a TTL (walking the expires table bucket by bucket)
delete the ones that have expired
while more than 10% of the sampled keys were expired
and the cycle has used less than 25% of CPU time
Fast cycle: runs before the event loop sleeps, for at most 1 ms (1000 µs),
only if the previous cycle hit its time limit or the estimated share
of expired keys is still above 10%
The design is adaptive. If few keys are expired, a cycle costs almost nothing. If many are, Redis keeps working until the share of expired keys falls to about 10%, within its CPU limit. The consequence is that, at any moment, up to about 10% of the keys with a TTL may be expired but not yet deleted: they cannot be read, but they still use memory and are still counted by DBSIZE.
active-expire-effort (1-10, default 1) makes the cycle more aggressive: each step above 1 samples more keys per loop (+5), lengthens the fast cycle, raises the CPU budget (+2 percentage points) and lowers the tolerated share of expired keys (-1 percentage point, down to 1% at effort 10). Use it when memory held by expired keys matters more than a little extra CPU.
Related behaviour
- Replicas do not expire keys on their own. The master sends an explicit
DEL(orUNLINK) when a key expires, which keeps replicas consistent. Reads on a replica still return nothing for a logically expired key. - Hash fields with TTLs (
HEXPIRE, Redis 7.4+) are expired by the same lazy and active mechanisms; they are reported asexpired_subkeys. lazyfree-lazy-expire yesfrees expired values in a background thread.- The expiration check uses the current time, except that during a script or
MULTI/EXECthe time is frozen at the start, so a key cannot expire halfway through an atomic block.
Monitoring
redis-cli INFO keyspace
# db0:keys=1203344,expires=1200001,avg_ttl=41233,subexpiry=0
redis-cli INFO stats | grep -E 'expired_|expire_cycle'
# expired_keys:5912033 <- total keys expired (lazily and actively)
# expired_keys_active:5807120 <- of which by the active cycle
# expired_stale_perc:8.71 <- estimated % of TTL keys already expired
# expired_time_cap_reached_count:12 <- times the slow cycle hit its CPU limit
# expire_cycle_cpu_milliseconds:73120 <- total CPU spent in active expiry
Example: watching keys disappear
import time
import redis
r = redis.Redis(decode_responses=True)
r.flushdb() # test instance only
pipe = r.pipeline(transaction=False)
for i in range(100_000):
pipe.set(f"session:{i}", "x", px=1000) # all expire after 1 second
pipe.execute()
for _ in range(6):
stats = r.info("stats")
print(f"dbsize={r.dbsize():>6} expired={stats['expired_keys']:>6} "
f"stale%={stats['expired_stale_perc']}")
time.sleep(0.5)
# Sample run (Redis 8.10). Nobody reads these keys, so every deletion comes
# from the active cycle:
# dbsize=100000 expired= 0 stale%=0.0
# dbsize= 79036 expired= 19986 stale%=10.42 <- TTLs have passed; cleanup starts
# dbsize= 2040 expired= 96950 stale%=43.46 <- high stale share: cycle works harder
# dbsize= 0 expired=100000 stale%=37.86
# dbsize= 0 expired=100000 stale%=21.53 <- the estimate decays over later cycles
# dbsize= 0 expired=100000 stale%=12.25
Key Takeaways
- TTLs live in a per-database expires table holding absolute millisecond timestamps.
- Lazy expiration deletes a key when it is accessed, so expired values are never returned.
- Active expiration samples 20 TTL keys per database, repeats while more than 10% are expired, and uses at most about 25% of CPU; a 1 ms fast cycle helps between slow cycles.
- Expired-but-not-yet-deleted keys still use memory (
expired_stale_perc);active-expire-effortmakes cleanup more aggressive. - Replicas wait for the master's deletions instead of expiring keys on their own.
Practice
- (Beginner) Set a key with
EX 5, watchTTLcount down, and confirm thatGETreturns nil andEXISTSreturns 0 after it expires.- (Intermediate) Create 1 million keys with random TTLs between 1 and 60 seconds and nobody reading them. Log
DBSIZE,expired_stale_percandused_memoryevery second for two minutes, first withactive-expire-effort 1, then with10. Compare the curves.- (Interview) "After a traffic spike that created 20 million short-lived keys, memory stayed high for minutes even though the keys had expired. Why, and how would you reduce it?" Hint: think about what fraction of expired keys the active cycle tolerates, its CPU limit, and the settings that change both.
Memory Fragmentation and Active Defrag
Redis allocates and frees millions of small blocks of memory. The allocator (jemalloc in standard builds) groups blocks of similar size into pages. When many keys are deleted or shrink, pages become partly empty: the free space is scattered in small holes that are hard to reuse for different sizes, and a page can only be returned to the OS when it is completely empty. Like a parking lot after a busy day, there may be plenty of free spaces in total, yet the lot cannot be closed because a few cars remain in every row.
The result is that the process's resident memory (RSS), which the OS and container limits see, stays well above the memory Redis actually uses for data.
Measuring fragmentation
redis-cli INFO memory | grep -E 'used_memory:|used_memory_rss:|frag|allocator_'
# used_memory:6442450944 <- bytes in use by Redis (allocator view)
# used_memory_rss:9663676416 <- resident memory seen by the OS
# mem_fragmentation_ratio:1.50 <- rss / used_memory
# mem_fragmentation_bytes:3221225472
# allocator_frag_ratio:1.42 <- fragmentation inside the allocator's pages
# allocator_frag_bytes:2717908992
mem_fragmentation_ratio | Meaning |
|---|---|
| Below 1.0 | RSS smaller than used memory: part of Redis has been swapped out. Serious latency problem |
| 1.0 to about 1.5 | Normal |
Above 1.5, with many GB in mem_fragmentation_bytes | Significant fragmentation; consider active defrag |
| Very high on an almost empty instance | Meaningless: fixed process overhead dominates (an empty instance can show 16 or more) |
allocator_frag_ratio isolates the fragmentation that active defrag can fix; the overall ratio also includes non-data memory such as the process's code and thread stacks.
Active defragmentation
With jemalloc, Redis can move live data into fuller pages, letting the allocator release empty ones. It scans the keyspace incrementally on the main thread and reallocates values that sit in sparsely used pages.
# redis.conf (active defrag is off by default)
activedefrag yes
active-defrag-ignore-bytes 100mb # do nothing below 100 MB of fragmentation
active-defrag-threshold-lower 10 # start when fragmentation exceeds 10%
active-defrag-threshold-upper 100 # work at maximum effort above 100%
active-defrag-cycle-min 1 # minimum CPU effort (% of main thread time)
active-defrag-cycle-max 25 # maximum CPU effort
active-defrag-max-scan-fields 1000 # large collections are processed in steps
redis-cli CONFIG SET activedefrag yes # can also be enabled at runtime
redis-cli INFO memory | grep active_defrag_running
# active_defrag_running:7 <- current CPU effort in %; 0 = idle
redis-cli INFO stats | grep -E 'active_defrag_(hits|misses|key_hits|key_misses)'
Active defrag costs CPU on the main thread, which slightly increases latency while it runs; the thresholds above keep it within limits. Alternatives are MEMORY PURGE (asks jemalloc to release dirty pages it is holding, a quick and cheap first step), or restarting the instance or failing over to a replica, which rebuilds memory from scratch.
Key Takeaways
- Fragmentation is free memory the allocator cannot return to the OS; it makes RSS exceed
used_memory. mem_fragmentation_ratio(RSS / used memory) is normally 1.0-1.5; below 1.0 means swapping, and on tiny instances it is meaningless.allocator_frag_ratioandallocator_frag_bytesshow what active defrag can recover.activedefrag yesrelocates live data incrementally within CPU limits;MEMORY PURGE, a restart or a failover are alternatives.
Practice
- (Beginner) Read
INFO memoryon an empty instance and explain whymem_fragmentation_ratiois so high.- (Intermediate) Load 2 million keys with random value sizes between 10 and 2,000 bytes, then delete every second key. Record
used_memory,used_memory_rssandallocator_frag_ratio. Enableactivedefragand record the same values every 10 seconds until defrag stops.- (Interview) "Kubernetes keeps killing our Redis pod for exceeding its 8 GB memory limit, but
used_memoryis only 5 GB. What is going on and what would you do?" Hint: compare what the container runtime measures with what Redis counts, and list the fixes from configuration to architecture.
MEMORY USAGE and MEMORY DOCTOR
"Redis uses 12 GB" is the start of an investigation, not an answer. You need to know which keys and which kinds of overhead use the memory. The MEMORY command family answers these questions from inside the server.
MEMORY USAGE
MEMORY USAGE key [SAMPLES count] returns the bytes a key and its value use, including the object header, the key name and allocator overhead. For collections, Redis measures count elements (default 5) and extrapolates; SAMPLES 0 measures every element, exact but O(N).
redis-cli HSET user:1 name Ada email ada@example.com age 36
redis-cli MEMORY USAGE user:1 # (integer) 74 (small listpack hash)
redis-cli MEMORY USAGE big:zset SAMPLES 0 # exact, but walks every member
MEMORY STATS
MEMORY STATS breaks down the instance's memory:
redis-cli MEMORY STATS
# Excerpt from a Redis 8.10 test instance holding 9,166 small string keys,
# shown as name: value pairs:
# peak.allocated: 70620952 <- highest used_memory since start
# total.allocated: 3145672 <- current used_memory
# startup.allocated: 1382064 <- memory used right after startup
# replication.backlog: 0
# clients.normal: 0 <- buffers of normal clients
# db.0: overhead.hashtable.main 424712 <- keyspace bucket arrays and entries
# overhead.hashtable.expires 232
# overhead.total: 1897864 <- everything that is not data
# keys.count: 9166
# keys.bytes-per-key: 136 <- average cost per key, overhead included
# dataset.bytes: 1247808 <- memory for the data itself
# dataset.percentage: 70.75
# allocator-fragmentation.ratio: 1.16
# fragmentation: 10.85 <- RSS / used memory (tiny instance: not meaningful)
MEMORY DOCTOR
MEMORY DOCTOR analyses these numbers and returns advice in plain language: high fragmentation, a large peak compared to current usage, big client output buffers, a large replication backlog, and so on. On a nearly empty instance it says so instead of diagnosing:
redis-cli MEMORY DOCTOR
# "Hi Sam, this instance is empty or is using very little memory, my issues detector
# can't be used in these conditions. ..."
Other subcommands: MEMORY MALLOC-STATS (raw allocator statistics) and MEMORY PURGE (release dirty allocator pages, see the previous topic).
Finding the biggest keys
redis-cli can scan the keyspace with SCAN and report the largest keys, without blocking the server:
redis-cli --bigkeys # largest key per type, by element count (or length for strings)
redis-cli --memkeys # largest key per type, by MEMORY USAGE bytes
redis-cli --memkeys -i 0.01 # sleep 10 ms every 100 SCAN calls on a busy production server
redis-cli --keystats # both views at once, plus size percentiles
For a full ranking, combine SCAN with pipelined MEMORY USAGE:
import heapq
import redis
r = redis.Redis(decode_responses=True)
def top_keys_by_memory(n: int = 20, match: str = "*") -> list[tuple[int, str]]:
"""Return the n largest keys as (bytes, key), scanning without blocking Redis."""
heap: list[tuple[int, str]] = [] # min-heap of the n largest seen
batch: list[str] = []
def flush() -> None:
pipe = r.pipeline(transaction=False)
for k in batch:
pipe.memory_usage(k) # default SAMPLES 5: cheap estimate
for k, size in zip(batch, pipe.execute()):
if size is None: # key deleted since SCAN returned it
continue
if len(heap) < n:
heapq.heappush(heap, (size, k))
elif size > heap[0][0]:
heapq.heapreplace(heap, (size, k))
batch.clear()
for key in r.scan_iter(match=match, count=1000):
batch.append(key)
if len(batch) == 500:
flush()
if batch:
flush()
return sorted(heap, reverse=True)
for size, key in top_keys_by_memory(10):
print(f"{size:>12,} {key}")
Key Takeaways
MEMORY USAGEreports the bytes of one key; for collections it samples 5 elements by default, andSAMPLES 0makes it exact but O(N).MEMORY STATSsplits instance memory into dataset, keyspace overhead, client buffers, replication and fragmentation.MEMORY DOCTORturns those numbers into plain-language advice, and needs a non-trivial dataset to say anything useful.redis-cli --bigkeysand--memkeys, orSCANplus pipelinedMEMORY USAGE, find the largest keys without blocking the server.
Practice
- (Beginner) Create a string, a 10-field hash and a 1,000-member sorted set. Compare
MEMORY USAGEwith the size of the raw data you stored and explain the difference.- (Intermediate) Run the
top_keys_by_memoryscript on a test dataset, then compare its results withredis-cli --memkeys. For a 100,000-member hash with very uneven value sizes, compareMEMORY USAGEwithSAMPLES 5andSAMPLES 0.- (Interview) "
used_memorydoubled overnight. Walk me through how you would find out where the memory went." Hint: start broad withINFO memoryandMEMORY STATS(data vs overhead vs buffers), then narrow down to key patterns and individual keys, and consider encoding changes (5.2) as well as new data.
<a id="6-persistence-and-durability"></a>