Core Data Structures

3 roadmaps 42 questions

You will learn every native Redis type — strings, hashes, lists, sets, sorted sets, bitmaps, HyperLogLog, geospatial — plus the internal encodings that make them cheap. Interviewers probe this to see whether you pick the right structure and can predict its time and memory cost instead of treating Redis as a plain key-value store.

part ofRedisoverview, primer and where to startread it →

on this pageshow

explore

Strings & Bitmaps6 questions
Hashes6 questions
Lists4 questions
Sets5 questions
Sorted Sets6 questions
HyperLogLog4 questions
Geospatial Indexes5 questions
Internal Encodings6 questions

questions

page 1 of 2

Running OBJECT ENCODING on a small Redis hash returns "listpack", and on a large one it returns "hashtable". What is that command reporting, and why does Redis keep more than one internal representation for the same data type?

juniormust knowfreq 50%

answer

TYPE = logical, OBJECT ENCODING = layout
listpack/intset = compact, O(n), tiny overhead
hashtable/skiplist/quicklist = general, scales
thresholds: entries and element size
conversion is one-way, never back

basics

~20 s

OBJECT ENCODING reports the internal memory layout Redis chose for that value. Small collections use a compact, cache-friendly flat array (listpack/intset) that saves a lot of memory; once they grow past configured thresholds Redis switches to a real hash table or skiplist for O(1)/O(log n) access.

solid answer

~50 s

Every Redis value has a logical type (string, list, hash, set, sorted set) and, underneath it, one of several encodings — the actual in-memory layout. OBJECT ENCODING <key> tells you which one is in use.

The reason for more than one is a memory-versus-CPU trade. A real hash table costs pointers, bucket arrays and per-entry allocation headers — easily 50–100 bytes of overhead per entry. For a hash with five small fields, that overhead dwarfs the data. So Redis stores small collections as a listpack: a single contiguous blob holding the entries back to back, with almost no per-entry overhead and excellent CPU-cache behaviour. Lookup is a linear scan, but scanning ten entries in one cache line beats a pointer chase.

When the collection exceeds configured thresholds — entry count or element size — Redis converts to the general structure (hashtable, skiplist, quicklist) whose asymptotics hold at scale. Typical encodings: strings int/embstr/raw; hashes and sorted sets listpack/hashtable/skiplist; sets intset/listpack/hashtable; lists listpack/quicklist.

Every Redis value has a **logical type** (string, list, hash, set, sorted set) and, underneath it, one of several **encodings** — the actual in-memory layout. `OBJECT ENCODING <key>` tells you which one is in use. The reason for more than one is a memory-versus-CPU trade. A real hash table costs pointers, bucket arrays and per-entry allocation headers — easily 50–100 bytes of overhead per entry. For a hash with five small fields, that overhead dwarfs the data. So Redis stores small collections as a **listpack**: a single contiguous blob holding the entries back to back, with almost no per-entry overhead and excellent CPU-cache behaviour. Lookup is a linear scan, but scanning ten entries in one cache line beats a pointer chase. When the collection exceeds configured thresholds — entry count or element size — Redis converts to the general structure (`hashtable`, `skiplist`, `quicklist`) whose asymptotics hold at scale. Typical encodings: strings `int`/`embstr`/`raw`; hashes and sorted sets `listpack`/`hashtable`/`skiplist`; sets `intset`/`listpack`/`hashtable`; lists `listpack`/`quicklist`.

code

text · 17 lines

text

> CONFIG GET hash-max-listpack-entries
1) "hash-max-listpack-entries"
2) "128"

> HSET user:1 name alice age 30
> OBJECT ENCODING user:1
"listpack"

# push it past 128 fields
> for i in $(seq 1 200); do redis-cli HSET user:1 f$i v$i; done
> OBJECT ENCODING user:1
"hashtable"

# delete back down -- encoding does NOT revert
> HDEL user:1 f1 f2 ... f200
> OBJECT ENCODING user:1
"hashtable"

go deeper

for a junior

Name the compact versus general split, that OBJECT ENCODING reports it, and that thresholds drive the switch.

for a middle

Add the specific encodings per type, the entries-and-value-size threshold pair, and the one-way conversion rule.

for a senior

Connect it to real memory numbers and diagnosis — MEMORY USAGE, per-key overhead, latency from oversized listpacks.

for a principal

Frame encoding as the memory cost model of an in-memory store, and drive key-design standards (grouping small keys into hashes) from it.

Type versus encoding

Redis exposes five core data types plus a few specialised ones. TYPE mykey returns the logical type — what commands you may run. OBJECT ENCODING mykey returns something different: the concrete memory layout the server picked for that particular value right now. The same HSET/HGET API works identically whichever encoding is underneath; the encoding is an invisible optimisation.

> RPUSH mylist a b c
> OBJECT ENCODING mylist
"listpack"
> TYPE mylist
list

Why a general structure is wasteful for small values

A hash table in C is an array of buckets holding pointers to entries; each entry holds a key pointer, a value pointer and a next pointer. Add the allocator's per-allocation header and the Redis string (SDS) header on both key and value, and a single field/value pair of a few bytes can cost on the order of 50–100 bytes of overhead. For a hash representing a user session with six short fields, that is an order of magnitude more memory than the payload.

This matters more in Redis than in most systems because Redis is an in-memory store: RAM is the cost model, and real deployments hold tens or hundreds of millions of small objects. A representation that halves per-object overhead halves the bill.

The compact encodings

listpack — a single contiguous byte blob containing entries one after another, each prefixed with its own length metadata so the blob can be traversed in either direction. There are no pointers and one allocation for the whole collection. Used for small hashes, small sorted sets, small sets, and small lists. It replaced the older ziplist, which had the same idea but a design that made some updates prone to cascading size recalculation.
intset — for sets whose members are all integers: a sorted array of fixed-width integers (16, 32 or 64 bit, upgraded as needed). Membership is a binary search; memory is essentially just the numbers.
embstr — for short strings (44 bytes or fewer): the object header and the string data are allocated together in one block, so creating and freeing it is one allocation instead of two. Longer strings use raw (two allocations); strings that are valid integers are stored as int, a plain long inside the object.

The cost of a compact encoding is that operations are O(n) in the number of entries, since you scan the blob. That is deliberately fine because n is capped by configuration — and for small n, a linear walk over contiguous memory is faster in wall-clock terms than hashing plus a pointer dereference, because it touches one or two cache lines instead of jumping around the heap.

The general encodings

hashtable — the real dict, used for large hashes and large sets; O(1) average lookup, incremental rehashing when it grows.
skiplist — used for large sorted sets, giving O(log n) range and rank operations. A sorted set in skiplist encoding actually keeps two structures: the skiplist for ordering and a dict for O(1) member → score lookup.
quicklist — used for large lists: a doubly linked list whose nodes are themselves listpacks, so you get cheap push/pop at both ends without one allocation per element.

How and when Redis switches

Conversion is driven by per-type configuration thresholds — element count and the size of any individual element (for example hash-max-listpack-entries and hash-max-listpack-value, defaulting to 128 and 64). When a write pushes a collection past either limit, Redis converts the value in place to the general encoding.

Two properties matter in practice. First, the check is on any element: one 200-byte field converts an otherwise tiny hash. Second, conversion is one-way: delete elements back down below the threshold and the encoding stays hashtable. Redis does not downgrade, because oscillating around the boundary would cost more than it saves. To get the compact encoding back you must recreate the key.

Why you should care

As a developer you rarely choose an encoding directly, but encoding explains two very common observations: why a million tiny keys use far more memory than the sum of their values (top-level keys always carry full object overhead, so grouping them into hashes that stay listpack-encoded is a large win), and why one key that looks small behaves slowly (a listpack that was allowed to grow, or a value stuck in a general encoding). OBJECT ENCODING plus MEMORY USAGE <key> is the first pair of commands to reach for when memory or latency surprises you.

## Type versus encoding Redis exposes five core data types plus a few specialised ones. `TYPE mykey` returns the logical type — what commands you may run. `OBJECT ENCODING mykey` returns something different: the concrete memory layout the server picked for that particular value right now. The same `HSET`/`HGET` API works identically whichever encoding is underneath; the encoding is an invisible optimisation. ``` > RPUSH mylist a b c > OBJECT ENCODING mylist "listpack" > TYPE mylist list ``` ## Why a general structure is wasteful for small values A hash table in C is an array of buckets holding pointers to entries; each entry holds a key pointer, a value pointer and a next pointer. Add the allocator's per-allocation header and the Redis string (SDS) header on both key and value, and a single field/value pair of a few bytes can cost on the order of 50–100 bytes of *overhead*. For a hash representing a user session with six short fields, that is an order of magnitude more memory than the payload. This matters more in Redis than in most systems because Redis is an in-memory store: RAM *is* the cost model, and real deployments hold tens or hundreds of millions of small objects. A representation that halves per-object overhead halves the bill. ## The compact encodings - **listpack** — a single contiguous byte blob containing entries one after another, each prefixed with its own length metadata so the blob can be traversed in either direction. There are no pointers and one allocation for the whole collection. Used for small hashes, small sorted sets, small sets, and small lists. It replaced the older **ziplist**, which had the same idea but a design that made some updates prone to cascading size recalculation. - **intset** — for sets whose members are *all* integers: a sorted array of fixed-width integers (16, 32 or 64 bit, upgraded as needed). Membership is a binary search; memory is essentially just the numbers. - **embstr** — for short strings (44 bytes or fewer): the object header and the string data are allocated together in one block, so creating and freeing it is one allocation instead of two. Longer strings use `raw` (two allocations); strings that are valid integers are stored as `int`, a plain long inside the object. The cost of a compact encoding is that operations are **O(n) in the number of entries**, since you scan the blob. That is deliberately fine because n is capped by configuration — and for small n, a linear walk over contiguous memory is faster in wall-clock terms than hashing plus a pointer dereference, because it touches one or two cache lines instead of jumping around the heap. ## The general encodings - **hashtable** — the real dict, used for large hashes and large sets; O(1) average lookup, incremental rehashing when it grows. - **skiplist** — used for large sorted sets, giving O(log n) range and rank operations. A sorted set in `skiplist` encoding actually keeps *two* structures: the skiplist for ordering and a dict for O(1) member → score lookup. - **quicklist** — used for large lists: a doubly linked list whose nodes are themselves listpacks, so you get cheap push/pop at both ends without one allocation per element. ## How and when Redis switches Conversion is driven by per-type configuration thresholds — element count and the size of any individual element (for example `hash-max-listpack-entries` and `hash-max-listpack-value`, defaulting to 128 and 64). When a write pushes a collection past either limit, Redis converts the value in place to the general encoding. Two properties matter in practice. First, the check is on *any* element: one 200-byte field converts an otherwise tiny hash. Second, **conversion is one-way**: delete elements back down below the threshold and the encoding stays `hashtable`. Redis does not downgrade, because oscillating around the boundary would cost more than it saves. To get the compact encoding back you must recreate the key. ## Why you should care As a developer you rarely choose an encoding directly, but encoding explains two very common observations: why a million tiny keys use far more memory than the sum of their values (top-level keys always carry full object overhead, so grouping them into hashes that stay listpack-encoded is a large win), and why one key that looks small behaves slowly (a listpack that was allowed to grow, or a value stuck in a general encoding). `OBJECT ENCODING` plus `MEMORY USAGE <key>` is the first pair of commands to reach for when memory or latency surprises you.

If a listpack lookup is O(n), why is it not slower than a hash table for small collections?
Because n is bounded by configuration, typically 128 entries, and the listpack is one contiguous allocation. Scanning it touches a couple of cache lines sequentially, which modern CPUs prefetch well, whereas a hash table costs a hash computation plus a pointer dereference into a randomly located entry — likely a cache miss. Asymptotics only win once n is large enough for the constant factors to stop dominating.
A hash was converted to hashtable and then shrunk back to three fields. What encoding does it have, and how would you reclaim the memory?
It stays hashtable — Redis never converts back, because a value oscillating across the threshold would pay repeated conversion cost. The only way to regain the compact encoding is to recreate the key: read the remaining fields and write them to a fresh key, for example with a rename after rebuilding, or simply delete and re-populate from the source of truth.

A shopping list of five items fits on one sticky note you read top to bottom; a warehouse inventory needs an indexed catalogue. Redis keeps the sticky note until the list outgrows it, then builds the catalogue — and never goes back to the sticky note.

saying these in an interview costs you the question

Confusing TYPE with OBJECT ENCODING, or thinking the encoding changes the available commands
Believing Redis converts back to the compact encoding when a collection shrinks
Assuming O(n) listpack access is always slower than a hash table
Thinking encodings are a legacy detail with no memory impact
Saying the encoding is chosen once at key creation and never changes

§explore

▾sections8 · 42 questions

▾roadmaps that cover this3

§questions

Running OBJECT ENCODING on a small Redis hash returns "listpack", and on a large one it returns "hashtable". What is that command reporting, and why does Redis keep more than one internal representation for the same data type?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Type versus encoding

Why a general structure is wasteful for small values

The compact encodings

The general encodings

How and when Redis switches

Why you should care

▾common follow-ups2 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions8 questions

▾related topics3 topics

How would you store a user profile in a Redis hash, and which commands read a single attribute, several attributes, and the whole object? What happens to the key when you delete its last field?

basics

Describe the Redis List type: which commands you use to add and remove elements, how you read a range out of it, and how the cost of those operations differs between the ends of the list and the middle.

basics

What is a Redis Set, and which commands do you use to add a member, remove one, test membership and get the element count?

basics

What is a Redis Sorted Set, how is the ordering of its elements defined, and which commands do you use to add an element, read its score, read its rank and read a range?

basics

The Redis SET command accepts NX, XX, EX/PX, KEEPTTL and GET options. What does each of them do, and why is `SET key value NX EX 30` preferred over calling SETNX and then EXPIRE?

basics

Which Redis configuration settings decide whether a hash or sorted set keeps its compact internal layout, and what exactly happens at the boundary?

basics

When storing an object in Redis, what do you gain and lose by modelling it as a hash with one field per attribute versus serialising the whole object to JSON and storing it in a single string key?

basics

A Redis Set holds several million members. What does SMEMBERS cost the server and the client, and how would you satisfy the common requests against that set — its size, whether specific values are in it, a random sample, the size of its overlap with another set — without ever materialising it?

basics

Design a game leaderboard on Redis Sorted Sets: how do you record a score change, fetch the top ten, and show one player their own position and the players around them?

basics

Why is Redis's INCR the correct way to implement a counter shared by many clients, and what happens if the key is missing, holds non-numeric text, or is incremented past the 64-bit range?

basics

Implement a sliding-window rate limiter using a Redis Sorted Set — which commands run, in what order, and what are the failure modes you have to design around?

basics

A ride-hailing backend needs to find every driver within 5 km of a pickup point using Redis. Which Redis commands would you use to store the driver positions and to run that proximity query, and what does the query return?

basics

When a Redis sorted set grows past its compact threshold, OBJECT ENCODING reports "skiplist". What two structures does that encoding actually maintain, and why does it need both?

basics

Redis geospatial commands are often described as a thin layer over another core Redis type. Which type actually backs GEOADD, how is a longitude/latitude pair encoded into it, and what practical consequences does that have for how you operate the key?

basics

You are keeping per-endpoint request counters grouped under one Redis key. How does HINCRBY behave when the key or the field does not exist yet, when the stored value is not a number, and how does it compare with reading the field and writing it back from the application?

basics

You want to show a random sample of fields from a large Redis hash without pulling the whole thing. How does the Redis command HRANDFIELD serve that, how does its reply shape change with the WITHVALUES option under RESP2 versus RESP3, and how does it compare with HSCAN for the same job?

basics

You keep one Redis HyperLogLog per day of unique visitors. How do you produce a weekly and a monthly unique-visitor number, and what does the PFMERGE command guarantee about the accuracy of the result?

basics

Redis exposes a HyperLogLog type through the PFADD and PFCOUNT commands. What problem does it solve, and what do you give up compared with putting the same items into a Redis Set and calling SCARD?

basics

Redis offers blocking list commands such as BLPOP and BLMOVE. Explain what blocking means here, what happens to the server and to other clients while one client is blocked, and how these commands behave inside a MULTI/EXEC transaction.

basics

You want a Redis key holding only the 100 most recent events for each user, without it growing forever. Show how LPUSH together with LTRIM implements that, and explain what the trim actually costs and why the two commands should be issued together.

basics

Redis offers SINTER, SUNION and SDIFF plus SINTERSTORE, SUNIONSTORE and SDIFFSTORE. How do these behave, what do they cost, and when would you reach for the STORE variants?

basics

Redis has both SPOP and SRANDMEMBER for getting random elements out of a Set. How do they differ, and how does supplying a count — including a negative one — change what you get back?

basics

Explain the ZADD flags NX, XX, GT, LT, CH and INCR in Redis, and give a situation where each one changes the outcome.

basics

Redis has no dedicated bitmap type — SETBIT, GETBIT and BITCOUNT operate on ordinary strings. How does that work, how much memory does a daily-active-user flag for 50 million user ids cost, and what is the trap when the bit offsets are sparse?

basics

Redis strings can be modified in place with APPEND, SETRANGE and read partially with GETRANGE. How do these commands behave — including what SETRANGE does when you write past the end of the value — and what are the limits of treating a Redis string as a growable buffer?

basics

A Redis instance holds 50 million tiny key-value pairs and uses far more memory than the sum of the values suggests. How would you investigate, and what restructuring would let the encoding layer cut that footprint?

basics

A Redis list of a million elements reports the "quicklist" encoding while a three-element list reports "listpack". Explain how a quicklist is built and what list-max-listpack-size and list-compress-depth control.

basics

Redis 7.4 added the HEXPIRE command family. What problem does expiring individual hash fields solve, how do you use those commands, and how did teams handle the same requirement before they existed?

basics

explore

questions

answer

go deeper

context