Inside Redis: A Deep Dive into Its Core Data Structures

Overview

Redis is an open‑source, in‑memory key‑value store written in ANSI C. It uses several specialized data structures to achieve high performance and efficient memory usage. The following sections describe each structure, its C definition, and its role within Redis.

Simple Dynamic String (SDS)

Redis does not use C’s native null‑terminated strings. Instead it defines an abstract type called Simple Dynamic String (SDS) that stores the length, free space, and the character buffer.

struct sdshdr {
    int len;   // length of the string
    int free;  // unused bytes in buf
    char buf[]; // actual character data
};

Key points:

len records the used length of the string.

free records the remaining capacity for appends.

buf holds the raw bytes.

SDS is also used as a buffer for AOF persistence and client input.

Linked List

Redis uses a doubly‑linked list for list keys when the list is large or contains long strings.

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

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

Features:

O(1) access to head and tail.

No cycles; head.prev and tail.next are NULL.

Length stored in len for O(1) size queries.

Node values are stored as void* for polymorphism.

Dictionary (Hash Table)

Redis implements its own hash table because C lacks a built‑in map type.

typedef struct dictht {
    dictEntry **table;   // array of buckets
    unsigned long size; // number of buckets
    unsigned long sizemask; // size-1, used for indexing
    unsigned long used; // number of entries
} dictht;

typedef struct dictEntry {
    void *key;          // key object
    union {
        void *val;      // generic pointer value
        uint64_t u64;   // 64‑bit integer
        int64_t s64;    // signed 64‑bit integer
    } v;
    struct dictEntry *next; // next entry in the same bucket (chaining)
} dictEntry;

Key aspects:

Uses chaining (linked list) to resolve hash collisions.

Each bucket is an array entry; sizemask enables fast modulo.

Keys are unique; values can be pointers or integers.

Skiplist

Skiplist provides an ordered data structure with logarithmic‑time operations, used for sorted sets and internal cluster metadata.

typedef struct zskiplistNode {
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer
        unsigned int span;            // span length
    } level[];
    struct zskiplistNode *backward; // backward pointer
    double score;                  // sorting score
    robj *obj;                     // stored object
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // head and tail nodes
    unsigned long length;                // number of elements
    int level;                          // max level
} zskiplist;

Characteristics:

Multiple levels of ordered linked lists.

Each level is a subset of the level below, providing O(log N) search, insert, delete.

Header and tail pointers give quick access to extremes.

Integer Set (intset)

Intset is the underlying representation for sets that contain only integers and are relatively small.

typedef struct intset {
    uint32_t encoding; // integer encoding (16/32/64 bits)
    uint32_t length;   // number of elements
    int8_t contents[]; // array of integers (type depends on encoding)
} intset;

Properties:

Encoding determines the size of each stored integer.

Length tracks element count.

Supports only upgrade (to larger encoding) but not downgrade.

Compressed List (ziplist)

Ziplist is a memory‑efficient sequential structure used for small lists and hash tables.

Structure fields (illustrated in the original diagram): zlbytes – total bytes consumed. zltail – offset of the tail entry. zllen – number of entries.

Entries ( entryX) – each stores either a string or an integer. zlend – end marker.

Features:

Optimized for low memory usage.

Used as the backing store for list and hash keys when they are small.

Adding a node may trigger a cascade of reallocations.

Overall, Redis combines these specialized structures to provide fast, memory‑efficient operations for a variety of data types.