Inside Redis 6.0: Understanding SDS, Ziplist, Quicklist, and ZSet Data Structures

SDS (Simple Dynamic String)

Redis does not use the native C string type; instead it defines a custom sdshdr structure called SDS to store strings. The structure is packed to avoid padding, allowing the flags field to be accessed via sds[-1]. Different header variants (sdshdr8, sdshdr16, sdshdr32, sdshdr64) are selected based on the actual string length to minimise memory usage.

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;      /* used */
    uint8_t alloc;    /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

Benefits of SDS include O(1) length retrieval, protection against buffer overflow, reduced reallocations through pre‑allocation, binary safety (length‑based termination), and compatibility with many C string functions.

Ziplist (Compressed Linked List)

A ziplist is a specially encoded doubly linked list that stores strings or integers in a contiguous memory block, providing high space efficiency.

Memory layout (illustrated in the original image) consists of:

zlbytes (uint32_t): total bytes used by the ziplist.

zltail (uint32_t): offset of the tail entry from the start.

zllen (uint16_t): number of entries (exact when < 65535, otherwise requires full traversal).

entry : variable‑size elements.

zlend (uint8_t): constant 255 marking the end.

Each entry contains:

prevlen : length of the previous entry (1 byte if < 254, otherwise 5 bytes).

encoding : type (integer or string) and, for strings, the effective length.

Key characteristics: very high space utilisation (≤6 bytes waste per entry), no explicit pointers—navigation relies on offsets, and insert/delete may trigger cascade updates, potentially leading to O(n²) behaviour if entry sizes vary widely.

Quicklist (List Collection)

Redis implements the list type as a quicklist, a doubly linked list where each node holds a separate ziplist. This combines the fast sequential access of a linked list with the memory efficiency of ziplists.

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;   /* total entries in all ziplists */
    unsigned long len;     /* number of quicklist nodes */
    int fill : QL_FILL_BITS;      /* fill factor for nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of uncompressed tail nodes */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;   /* previous node */
    struct quicklistNode *next;   /* next node */
    unsigned char *zl;            /* pointer to the ziplist */
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;      /* number of items in ziplist */
    unsigned int encoding : 2;    /* RAW=1 or LZF=2 */
    unsigned int container : 2;   /* NONE=1 or ZIPLIST=2 */
    unsigned int recompress : 1;  /* was previously compressed */
    unsigned int attempted_compress : 1; /* too small to compress */
    unsigned int extra : 10;      /* reserved for future use */
} quicklistNode;

Typical use cases include implementing a message queue (push/pop via list commands) and paginated reads with LRANGE.

Hash (Dictionary Type)

Redis hashes use two possible encodings: a ziplist for small collections and a hash table for larger ones. The switch occurs when the number of fields exceeds hash-max-ziplist-entries (default 512) or any field/value exceeds hash-max-ziplist-value (default 64 bytes).

typedef struct dictht {
    dictEntry **table;   /* pointer array */
    unsigned long size;  /* array size */
    unsigned long sizemask; /* length mask */
    unsigned long used; /* number of entries */
} dictht;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;               /* value */
    struct dictEntry *next; /* chaining for collisions */
} dictEntry;

Redis performs incremental rehashing: two hash tables ( ht[0] and ht[1]) exist during rehash, and entries are gradually moved during normal operations and a background task.

Set (Unordered Unique Collection)

Sets store unique elements. When all elements are integers and the set size stays below server.set_max_intset_entries (default 512), Redis uses an intset encoding; otherwise it falls back to a hash table ( OBJ_ENCODING_HT).

int setTypeAdd(robj *subject, sds value) {
    if (subject->encoding == OBJ_ENCODING_HT) {
        dict *ht = subject->ptr;
        dictEntry *de = dictAddRaw(ht, value, NULL);
        if (de) {
            dictSetKey(ht, de, sdsdup(value));
            dictSetVal(ht, de, NULL);
            return 1;
        }
    } else if (subject->encoding == OBJ_ENCODING_INTSET) {
        long long llval;
        if (isSdsRepresentableAsLongLong(value, &llval) == C_OK) {
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr, llval, &success);
            if (success) {
                size_t max_entries = server.set_max_intset_entries;
                if (max_entries >= 1<<30) max_entries = 1<<30;
                if (intsetLen(subject->ptr) > max_entries)
                    setTypeConvert(subject, OBJ_ENCODING_HT);
                return 1;
            }
        } else {
            setTypeConvert(subject, OBJ_ENCODING_HT);
            serverAssert(dictAdd(subject->ptr, sdsdup(value), NULL) == DICT_OK);
            return 1;
        }
    } else {
        serverPanic("Unknown set encoding");
    }
    return 0;
}

The underlying intset is an ordered array that enables binary search, offering lower memory consumption than a hash table.

typedef struct intset {
    uint32_t encoding;   /* encoding type */
    uint32_t length;     /* number of elements */
    int8_t contents[];   /* element array */
} intset;

ZSet (Sorted Set)

ZSets combine a hash table for O(1) member lookup with a skiplist for O(log n) range queries based on a floating‑point score. When the number of elements is ≤128 and each element’s serialized length ≤64 bytes, Redis stores the ZSet using a ziplist; otherwise it uses the hash‑plus‑skiplist representation.

typedef struct zset {
    dict *dict;   /* key → score */
    zskiplist *zsl; /* skiplist ordered by score */
} zset;

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

typedef struct zskiplistNode {
    sds ele;               /* element string */
    double score;          /* element score */
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

The core insertion routine zslInsert creates a new node, updates forward/backward pointers, and adjusts span values to maintain skiplist invariants.

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    serverAssert(!isnan(score));
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                 sdscmp(x->level[i].forward->ele, ele) < 0))) {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    x = zslCreateNode(level, score, ele);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}

Typical ZSet applications include ranking hot topics (e.g., trending searches) and time‑bounded order‑cancellation logic in e‑commerce systems.