Unveiling Redis’s Hidden Data Structures: From SDS to Dictionaries

Redis Object Encodings

Redis uses a set of internal object encodings identified by constants such as OBJ_ENCODING_RAW (0) for simple dynamic strings, OBJ_ENCODING_INT (1) for integers, OBJ_ENCODING_HT (2) for hash tables, and others like OBJ_ENCODING_ZIPMAP, OBJ_ENCODING_LINKEDLIST, OBJ_ENCODING_ZIPLIST, OBJ_ENCODING_INTSET, OBJ_ENCODING_SKIPLIST, OBJ_ENCODING_EMBSTR, OBJ_ENCODING_QUICKLIST, and OBJ_ENCODING_STREAM. These encodings map high‑level Redis data types (STRING, LIST, SET, ZSET, HASH) to low‑level memory representations.

Simple Dynamic String (SDS)

Redis implements its own string type called SDS (Simple Dynamic String) instead of raw C strings. In Redis 2.8 the structure is:

struct sdshdr {
    int len;   // used length of buf
    int free;  // unused space in buf
    char buf[]; // actual byte array, null‑terminated
};

The len field stores the string length, enabling O(1) length retrieval. The free field records pre‑allocated but unused space, allowing efficient appends without frequent reallocations. The buf holds the characters and follows the C‑string convention of a terminating null byte, which is not counted in len.

SDS Advantages over C Strings

Constant‑time length queries (O(1) vs O(n)).

Safe concatenation: SDS automatically expands the buffer when needed, preventing buffer overflows.

Reduced memory reallocations: the free field enables pre‑allocation and lazy release, cutting the number of system calls.

Binary safety: SDS uses len to determine the end, so embedded null bytes are allowed.

Compatibility: SDS retains the null‑terminated layout, allowing reuse of many C string library functions.

Version‑Specific Optimizations

Starting with Redis 3.2, SDS was refined into several size‑specific structures to save memory:

struct __attribute__((__packed__)) sdshdr5 { unsigned char flags; char buf[]; };
struct __attribute__((__packed__)) sdshdr8 { uint8_t len; uint8_t alloc; unsigned char flags; 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[]; };

Fields:

len : used bytes.

alloc : total allocated bytes (previous free = alloc - len).

flags : type identifier; low 3 bits store the encoding type, high 5 bits are reserved (or store length in sdshdr5).

buf : byte array, null‑terminated.

Linked List Implementation

Redis provides its own doubly‑linked list to support structures like the AOF buffer and client input buffers. The core definitions are:

typedef struct list {
    listNode *head; // first node
    listNode *tail; // last node
    void *(*dup)(void *ptr); // duplicate node value
    void (*free)(void *ptr); // free node value
    int (*match)(void *ptr, void *key); // compare node value
    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*)
} listNode;

Key properties:

Bidirectional, non‑circular list with O(1) access to head, tail, and length.

Node values are stored as void*, enabling polymorphic storage of any data type.

Custom functions ( dup, free, match) allow type‑specific handling.

Dictionary (Hash Table) Implementation

Redis implements its own hash table‑based dictionary to map keys to values. Core structures:

typedef struct dict {
    dictType *type;      // type‑specific functions
    void *privdata;      // optional private data
    dictht ht[2];        // two hash tables for rehashing
    long rehashidx;      // -1 if not rehashing
    unsigned long iterators; // active iterators count
} 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;  // table size (always power of 2)
    unsigned long sizemask; // size-1, for fast modulo
    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; // linked list for collisions
} dictEntry;

The dictionary uses MurmurHash as its hash function. Index calculation follows:

hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask;

Collisions are resolved with chaining (head‑insertion). Rehashing occurs when the load factor (used/size) crosses thresholds:

Expand if load factor ≥ 1 (or ≥ 5 when a child process like BGSAVE/BGREWRITEAOF is active).

Shrink if load factor < 0.1.

During rehashing, Redis performs incremental migration: each regular operation moves a bucket from ht[0] to ht[1], avoiding long pauses. New insertions go directly into ht[1] while rehashing is in progress.

Practical Usage in Redis

SDS backs the AOF buffer and client input buffers. Linked lists were used for list objects before version 3.2 (replaced by quicklists). Dictionaries implement hash objects, the core key‑value store, and support many internal APIs.