$Redis Deep Dive Part 2: The Building Blocks

This is part two of my Redis internals series. Part 1 explains how Redis handles commands and client connections. This article follows a key through the database keyspace and into the encodings Redis uses for strings and collections.

Version scope: source excerpts and configuration names refer to Redis 7.4. Redis 7.0 replaced ziplist configuration for hashes and sorted sets with listpack configuration, and Redis 7.2 added a listpack encoding for small sets. Redis 8 changed how several former Redis Stack capabilities are distributed.

Database keyspace

Each logical database is represented by redisDb. In Redis 7.4, its keys field points to a kvstore, which manages the dictionaries that hold the keyspace.

typedef struct redisDb {
    kvstore *keys;
    kvstore *expires;
    ebuckets hexpires;
    dict *blocking_keys;
    dict *blocking_keys_unblock_on_nokey;
    dict *ready_keys;
    dict *watched_keys;
    int id;
    long long avg_ttl;
    unsigned long expires_cursor;
    list *defrag_later;
} redisDb;

The complete definition is in the Redis 7.4 server.h source.

A dictionary hashes each key to select a bucket. Different keys can produce the same bucket index, so dictionary entries include a link to the next entry in that bucket. This is separate chaining: a lookup checks the entries in the selected bucket until it finds the matching key.

Redis resizes a dictionary when its load and resize policy require more or fewer buckets. Rebuilding the whole table in one operation would pause command processing, so Redis uses two hash tables during a resize. Incremental rehashing moves a limited number of buckets at a time. Lookups inspect both tables while migration is in progress, and new entries go to the destination table.

Redis performs some rehashing during dictionary operations and can continue it from scheduled maintenance. The work still runs on the main thread, but dividing it into bounded steps avoids one large resize pause. The implementation is available in dict.c.

Value objects

A dictionary entry contains the key and its stored value. Keys are Redis string objects. Most values point to a redisObject, usually called robj in the source:

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
};

The type field records the logical Redis type, such as a string or hash. The encoding field records the representation chosen for that value. The pointer leads to the selected representation.

This separation lets one command API use different encodings. A small hash can remain in a compact listpack; Redis converts it to a dictionary after it crosses configured size limits. The command does not change, but its memory use and operation costs can.

Per-key memory consumption depends on the data and runtime environment. Fixed estimates for object overhead are therefore unreliable. The MEMORY USAGE command and a workload-specific test give a better estimate.

The access path for GET mykey is:

Redis hashes mykey, finds its dictionary entry, checks the object’s type and encoding, and reads the encoded value. During rehashing, the dictionary lookup may inspect both hash tables.

Core encodings

Redis chooses an encoding from the value itself and the configured thresholds.

The defaults can be changed in redis.conf. Raising a compact-encoding threshold may save memory, but conversion and linear scans become more expensive as the compact value grows. The Redis memory optimization guide lists the version-specific settings.

Strings and SDS

Redis strings use the Simple Dynamic String (SDS) library. An SDS header stores the used length and allocation size next to the byte buffer. Redis selects a header width that can represent the string’s size.

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;
    uint8_t alloc;
    unsigned char flags;
    char buf[];
};

The stored length makes STRLEN an O(1) operation and allows the buffer to contain null bytes. SDS values can therefore hold text or binary payloads without relying on a null terminator.

When an append needs more capacity, SDS allocates spare space to reduce repeated reallocations. Growth is proportional below the preallocation limit and then increases in fixed-size increments. This makes repeated appends amortized O(1), although a particular append may allocate and copy memory.

Lists and quicklists

Redis 7.4 stores a list as a quicklist. The quicklist is a doubly linked list whose nodes contain listpacks. A listpack stores several elements in one contiguous allocation, reducing per-element pointer and allocator overhead.

Operations at either end work on the head or tail node. Traversal within a node benefits from contiguous storage, while the node boundaries limit how much data an insertion must move. The list-max-listpack-size setting controls node size, and list-compress-depth controls optional compression away from the list ends.

Sets

Redis 7.4 has three set encodings:

An intset stores integers in sorted order and upgrades its integer width when a new value requires it. Adding a non-integer value or crossing a configured threshold causes Redis to convert the set to another encoding. Conversion happens synchronously, so unusually high thresholds should be tested with representative values.

Hashes

Small hashes use a listpack of field-value pairs. Redis converts the value to a dictionary after the number of fields or the size of a field exceeds the configured limits.

Grouping related fields in one hash can reduce per-key overhead. The Redis memory guide reports that compact aggregate encodings can use up to ten times less memory, with five times described as a typical saving. Those figures depend on the data and configuration, so MEMORY USAGE should be measured for the intended schema.

Redis 7.4 added field-expiration commands such as HEXPIRE. Earlier Redis 7 releases did not support independent expiry for hash fields. Applications that must run across several Redis 7 minor versions need to account for that difference.

Sorted sets

A small sorted set can use a listpack. Larger sorted sets maintain a dictionary and a skip list together:

Both structures are updated when a member or score changes. For ZINCRBY, Redis finds the member, removes its old skip-list position, inserts the new position, and updates the score mapping. The command is O(log N).

The skip list stores forward links at several levels, allowing a search to skip groups of nodes. Span counts support rank operations such as ZRANK, which is O(log N). Range commands add work proportional to the number of returned elements.

Streams

A Redis stream uses a radix tree, called rax in the source, to index macro nodes containing listpacks. Stream IDs share timestamp prefixes, which suits a prefix tree. XADD appends field-value entries, and commands such as XRANGE navigate by ID.

The representation supports ordered event records and consumer groups. Trimming can remove old entries, so a stream should not be treated as permanent history unless retention and persistence are configured for that requirement.

Bitmaps and bitfields

Bitmaps are operations on Redis strings rather than a separate stored type. A bit offset addresses one bit in the string, so a 512 MiB string can address 2^32 bit positions. GETBIT and SETBIT are O(1); BITCOUNT and bitwise operations scan data proportional to the string length.

This representation works well when identifiers map to a reasonably dense range. A very large maximum identifier with only a few populated values can allocate far more space than a set would require.

BITFIELD packs signed or unsigned integers into the same string and applies several operations atomically. Redis supports signed widths through 64 bits and unsigned widths through 63 bits. Overflow behavior can wrap, saturate at the type boundary, or return no result without modifying the field.

Geospatial indexes

Redis stores geospatial members in a sorted set. Each score contains a 52-bit integer derived from longitude and latitude. GEOHASH returns an 11-character standard geohash without losing precision relative to that internal representation.

The stored coordinates are quantized, so a value returned by GEOPOS may differ slightly from the input. Nearby locations often share a geohash prefix, but nearby points can also fall on opposite sides of a prefix boundary. Commands such as GEOSEARCH handle radius and bounding-box queries without requiring callers to compare prefixes themselves.

HyperLogLog

HyperLogLog estimates cardinality with a standard error of 0.81%. Redis stores the structure in a string and uses at most 12 KiB in its dense representation.

The sparse representation records a small number of non-zero registers compactly. Redis converts to the dense representation when the sparse form would exceed its configured size. Cardinality alone does not define a fixed conversion point, so an estimate such as “ten thousand elements” is not a reliable threshold.

Redis 8 distribution changes

In Redis 7.4, capabilities beyond the core data structures were delivered as Redis Stack modules or compatible components. Redis 8 integrated those capabilities into the Redis Open Source distribution and added the vector set data type.

The distinction matters when choosing commands and deployment packages. A Redis 7.4 server does not gain JSON or Bloom filter commands merely because a client library exposes them; the matching modules must be installed. Redis 8 documentation treats these capabilities as part of the unified distribution.

Choosing a type

Compact encodings optimize small values for memory. General encodings favor predictable lookup or update costs as a collection grows. The thresholds are operational choices rather than universal recommendations.

Inspecting encodings locally

The following shell session creates values on Redis 7.4 and asks the server which encoding it selected:

redis-cli DEL small large visitors locations active:users

redis-cli HSET small field1 value1 field2 value2
redis-cli OBJECT ENCODING small

for i in {1..600}; do
  redis-cli HSET large "field$i" "value$i" >/dev/null
done
redis-cli OBJECT ENCODING large

redis-cli PFADD visitors user1 user2 user3
redis-cli PFCOUNT visitors

redis-cli GEOADD locations -122.419 37.775 SF -118.244 34.052 LA
redis-cli GEOSEARCH locations FROMLONLAT -122.419 37.775 BYRADIUS 50 km

redis-cli SETBIT active:users 100 1
redis-cli SETBIT active:users 500 1
redis-cli BITCOUNT active:users

Configuration changes can alter these results. Record the Redis version and the relevant listpack or intset settings when comparing memory use.

Further reading

• Redis 7.4 source
• Redis data types
• Redis memory optimization
• Redis Streams
• Redis HyperLogLog
• Redis geospatial indexes