Understanding Redis Data Types and Their Underlying Implementations

Redis is a widely used in‑memory database, and understanding the underlying principles of its various data types helps developers choose the right structure for specific business scenarios and prepares them for common interview questions.

String

Redis strings use a custom Simple Dynamic String (SDS) structure instead of plain C strings to avoid issues with null characters, repeated reallocations, and length traversal. SDS stores len (used length), alloc (total allocated size), flags (type), and buf (actual data). Redis also defines three encodings for strings: int (8‑byte integer), embstr (short strings ≤44 bytes), and raw (long strings).

List

Redis lists evolved from a classic doubly linked list to ziplist , then quicklist , and finally listpack to improve memory efficiency and access speed.

linkedlist

typedef struct list {
    // head pointer
    listNode *head;
    // tail pointer
    listNode *tail;
    // length of the list
    unsigned long len;
} list;

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

The linked list incurs high memory overhead due to pointer storage and non‑contiguous layout, leading to O(N) lookups.

ziplist

struct ziplist
{
    int32 zlbytes;          // total bytes
    int32 zltail_offset;    // offset of last entry
    int16 zllength;         // number of entries
    T[] entries;            // compact entries
    int8 zlend;             // end marker (0xFF)
};

struct entry {
    int var prevlen;   // length of previous entry
    int var encoding;  // type encoding
    optional byte[] content; // actual data
};

Ziplist stores elements contiguously, saving pointer overhead, but still requires O(N) traversal for arbitrary indexes.

quicklist

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;   // total elements
    unsigned long len;     // number of nodes
    // ... omitted ...
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;   // pointer to ziplist
    size_t sz;               // byte size of ziplist
    unsigned int count : 16; // number of elements in ziplist
    unsigned int encoding : 2; // 1=RAW, 2=LZF
    // ... omitted ...
} quicklistNode;

Quicklist combines a linked list of ziplist nodes, allowing O(log N) access to the k‑th element while keeping memory usage low.

listpack

Listpack, introduced in Redis 5.0 and replacing ziplist in 7.0, stores data in a compact contiguous block with fields such as tot-bytes , num-elements , and encoded element data, further reducing memory overhead.

Set

Sets are implemented using either a hash table ( dict ) for general cases or an intset when all elements are small integers (≤512 entries, ≤64‑bit values). The intset structure stores elements in a sorted array, enabling O(log N) lookups.

typedef struct intset {
    uint32_t encoding;   // int16, int32, or int64
    uint32_t length;     // number of elements
    int8_t contents[];   // contiguous sorted integers
} intset;

Map (Hash)

Redis hashes use either a dict (hash table) or a compact ziplist / listpack when both field and value sizes are small. The dict consists of an array of buckets and linked lists for collision handling.

struct dict {
    dictType *type;
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    long rehashidx;
    int16_t pauserehash;
};

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

Sorted Set

Sorted sets store unique members with a floating‑point score, using a combination of a hash table ( dict ) for O(1) score lookup and a skiplist for ordered range queries. The skiplist nodes contain the member, score, backward pointer, and an array of forward pointers with span information.

// Skiplist node
typedef struct zskiplistNode {
    sds ele;               // member string
    double score;          // score for ordering
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer
        unsigned long span;            // span for rank calculation
    } level[];
} zskiplistNode;

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

Summary

The article provides a detailed walkthrough of Redis’s internal data structures, explaining why different implementations exist across versions, how each structure balances memory usage and operation complexity, and the specific code representations that enable Redis to achieve high performance as an in‑memory database.