Understanding Redis Internal Data Structures: SDS, Linked List, and Dictionary Implementation

Redis is a high‑performance in‑memory middleware that appears in almost every project, serving roles such as cache, distributed lock, and message queue. Its ability to improve system performance and support high concurrency makes it indispensable.

The article examines the low‑level data structures behind Redis objects, starting with the object‑encoding constants table that maps encoding IDs to their underlying representations (e.g., OBJ_ENCODING_RAW → simple dynamic string, OBJ_ENCODING_INT → long integer, etc.).

Encoding Constant

Value

Underlying Data Structure

OBJ_ENCODING_RAW

0

Simple Dynamic String (SDS)

OBJ_ENCODING_INT

1

Long integer

OBJ_ENCODING_HT

2

Dictionary

OBJ_ENCODING_ZIPMAP

3

Compressed map

OBJ_ENCODING_LINKEDLIST

4

Doubly linked list

OBJ_ENCODING_ZIPLIST

5

Compressed list

OBJ_ENCODING_INTSET

6

Integer set

OBJ_ENCODING_SKIPLIST

7

Skiplist and dictionary

OBJ_ENCODING_EMBSTR

8

Embedded string (simple dynamic string)

OBJ_ENCODING_QUICKLIST

9

Quicklist

OBJ_ENCODING_STREAM

10

Stream

SDS (Simple Dynamic String)

Redis implements its own string type called SDS to overcome the limitations of C strings. The SDS header for Redis 2.8 is defined as:

struct sdshdr {
    int len;   // number of bytes used in buf (string length)
    int free;  // number of unused bytes in buf
    char buf[]; // actual byte array, null‑terminated but the null byte is not counted in len
};

Key advantages over traditional C strings:

Length is stored in len , giving O(1) strlen operations.

Appending checks and expands space automatically, preventing buffer overflows.

Pre‑allocation and lazy free reduce the number of memory reallocations.

Binary‑safe: the string can contain any byte value because the length, not the terminating null, determines the end.

Compatibility: SDS still follows the null‑terminated convention, allowing reuse of many C string functions.

Starting with Redis 3.2, SDS was further optimized with several packed structures to save memory for short strings:

struct __attribute__((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 LSB = type, 5 MSB = length */
    char buf[];
};

struct __attribute__((__packed__)) sdshdr8 {
    uint8_t len;   /* used */
    uint8_t alloc;  /* total allocated space (excluding header and null) */
    unsigned char flags; /* 3 LSB = type, 5 unused bits */
    char buf[];
};

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

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

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

These variants store the length in the smallest possible integer type and pack the header tightly, saving space for short strings.

Linked List Implementation

Redis implements its own doubly linked list because C lacks a built‑in list type. The structures are:

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

typedef struct listNode {
    struct listNode *prev; // previous node
    struct listNode *next; // next node
    void *value;           // stored value (void* for polymorphism)
} listNode;

Key properties:

O(1) access to head and tail.

O(1) retrieval of a node’s predecessor or successor.

Length is stored, allowing O(1) size queries.

Values are stored as void* , enabling any data type via custom dup , free , and match callbacks.

Redis uses this list for its list data type (later replaced by quicklist for large lists) and for internal structures such as the publish/subscribe channel list, slow‑log, and client output buffers.

Dictionary (Hash Table) Implementation

The dictionary provides a key‑value mapping similar to Java’s HashMap . Core structures:

typedef struct dict {
    dictType *type;          // type‑specific functions
    void *privdata;          // private data for type functions
    dictht ht[2];            // two hash tables for incremental rehashing
    long rehashidx;          // -1 if not rehashing, otherwise current bucket
    unsigned long iterators; // number of active iterators
} dict;

typedef struct dictType {
    uint64_t (*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;

typedef struct dictht {
    dictEntry **table;   // array of pointers to entries
    unsigned long size; // size of the table (always a power of two)
    unsigned long sizemask; // size-1, used for indexing
    unsigned long used; // number of occupied slots
} dictht;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // next entry in the same bucket (chaining)
} dictEntry;

Hash algorithm: Redis uses MurmurHash. The index for a key is computed as hash & ht[x].sizemask . Collisions are resolved with chaining (head‑insertion).

Rehashing is incremental: when the load factor exceeds thresholds (e.g., ≥1 under normal conditions, ≥5 when a background child process is active) or falls below 0.1, Redis allocates a second table ht[1] and gradually moves buckets from ht[0] to ht[1] during normal operations, ensuring the server remains responsive.

Use cases: The dictionary backs Redis hash objects, the internal key‑space, and many APIs that expose key‑value semantics.

Overall, the article provides a detailed walkthrough of Redis’s core data structures—SDS, linked list, and dictionary—explaining their C implementations, performance characteristics, and the evolution of these structures across Redis versions.