Redis Internals Explained: Data Structures, Memory Management & Use Cases

1. Introduction and Applications

Redis is a high‑performance, network‑enabled, persistent in‑memory key‑value database written in ANSI C, offering APIs for many languages. Its primary data types are String, List, Hash, Set, and ZSet.

Common internet‑company uses include:

String: cache, rate limiting, counters, distributed locks, session storage

Hash: user profiles, page view counts, composite queries

List: timeline feeds, simple queues

Set: likes, dislikes, tags, friend relationships

ZSet: leaderboards

For example, during a large e‑commerce promotion, inventory can be decremented directly in Redis, logged, and later synchronized to a database by a worker that must handle concurrency and idempotency.

The worker design must consider concurrent processing and duplicate handling.

These scenarios illustrate Redis's efficiency and stability; the following sections reveal how Redis implements them under the hood.

2. Redis Object (redisObject)

When executing SET hello world, Redis creates the following model:

dictEntry : each key‑value pair gets a dictEntry containing pointers to the key and value and a next pointer for handling hash collisions via chaining.

SDS : the key "hello" is stored as a Simple Dynamic String (SDS), described later.

redisObject : the value "world" is stored in a redisObject. All five Redis types are represented by a redisObject whose type field indicates the value type and whose ptr points to the actual data structure.

The design enables different internal encodings, memory reclamation, and shared objects, optimizing each type for its typical usage patterns.

Memory for these objects is allocated by a allocator such as jemalloc, which reduces fragmentation by categorizing allocations into small, large, and huge classes.

The ptr in a redisObject points to the underlying data structure, whose concrete type is determined by the encoding field. For example, the command to view the encoding of "hello" yields the following diagram:

3. String

String objects can be encoded as int, raw, or embstr. embstr allocates a single contiguous block, while raw requires two allocations.

Encoding rules: embstr: strings ≤ 39 bytes int: 8‑byte signed integers raw: strings > 39 bytes

Redis uses Simple Dynamic Strings (SDS) for mutable strings. The SDS header is defined as:

struct sdshdr {
    // length of used space in buf
    int len;
    // free space in buf
    int free;
    // actual data buffer (null‑terminated)
    char buf[];
};

Operations:

get: sdsrange – O(n)

set: sdscpy – O(n)

create: sdsnew – O(1)

len: sdslen – O(1)

SDS stores its length, allowing constant‑time length queries and avoiding buffer overflows. It also supports pre‑allocation and lazy space reclamation to reduce reallocations.

4. List

Lists are implemented as a quicklist, a hybrid of ziplist (compressed list) and a doubly‑linked list. This enables O(1) push/pop at both ends and O(N) indexed access.

typedef struct listNode {
    // previous node
    struct listNode *prev;
    // next node
    struct listNode *next;
    // node value
    void *value;
} listNode;

typedef struct list {
    // head node
    listNode *head;
    // tail node
    listNode *tail;
    // value duplication function
    void *(*dup)(void *ptr);
    // value free function
    void (*free)(void *ptr);
    // value compare function
    int (*match)(void *ptr, void *key);
    // number of nodes
    unsigned long len;
} list;

Complexities:

rpush / lpush / push – O(1)

pop – O(1)

index – O(N)

llen – O(N)

The linked‑list part provides O(1) access to head/tail and node count, while the ziplist part compresses small elements to save memory. When the list grows, Redis switches to quicklist, which stores several ziplist segments linked together.

Quicklist’s default compression depth is 0 (no compression). The first and last ziplist are left uncompressed for fast push/pop; deeper ziplists may be LZF‑compressed.

5. Hash

Hashes are stored either as a ziplist (for small hashes) or a hashtable. The ziplist is used when the hash has fewer than 512 entries and all field/value strings are under 64 bytes.

The hashtable implementation resembles Java’s pre‑JDK7 HashMap and provides O(1) read/write. Its core structures are:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* -1 when not rehashing */
    int iterators;
} dict;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask; /* always size-1 */
    unsigned long used;
} dictht;

typedef struct dictEntry {
    void *key;
    union {void *val; uint64_t u64; int64_t s64;} v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

Redis maintains two hash tables during incremental rehashing to keep the load factor within an optimal range.

6. Set

Sets are implemented as intset (integer set) when all members are integers and the set is small, otherwise as a hashtable.

typedef struct intset {
    uint32_t encoding;   // 16, 32 or 64‑bit
    uint32_t length;     // number of elements
    int8_t contents[];   // sorted, duplicate‑free array
} intset;

Operations:

sadd – O(1)

smembers – O(N)

srem – O(N)

slen – O(1)

The array upgrades its integer width when a larger value is added, preserving order and eliminating duplicates.

7. ZSet (Sorted Set)

ZSets use either a ziplist (for small sorted sets) or a skiplist (for larger or longer‑string members). The skiplist provides O(log N) search, insertion, and deletion.

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

Operations:

zadd – average O(log N), worst O(N)

zrem – average O(log N), worst O(N)

zrank – average O(log N), worst O(N)

Skiplist nodes maintain multiple forward pointers, enabling fast traversal similar to balanced trees but with a simpler implementation.

Source: https://www.cnblogs.com/weknow619/p/10464139.html