How Does a Key-Value Database Work?

Redis employs a hash table to store all key-value pairs. The primary advantage of a hash table is O(1) time complexity for quickly locating entries. Redis's hash buckets hold pointers (dictEntry *) to key-value data. The key-value data structure does not store values directly but uses void *key and void *value pointers.

SDS (Simple Dynamic String)

Redis implements its own string type called SDS (Simple Dynamic String). It is defined as:

struct sdshdr {
    int len;      // Length of the string
    int free;     // Available free space
    char* buf;    // Character array, null-terminated
}

Benefits of SDS include:

• O(1) retrieval of string length.
• Binary safety, allowing storage of data containing '\0'.
• Dynamic expansion to prevent buffer overflow.

Linked List

The List object in Redis uses a doubly linked list as one of its underlying implementations.

Node structure:

typedef struct listNode {
    struct listNode *prev; // Previous node
    struct listNode *next; // Next node
} listNode;

List structure:

typedef struct list {
    listNode *head;               // Head node
    listNode *tail;               // Tail node
    void *(*dup)(void *ptr);      // Node copy function
    void (*free)(void *ptr);      // Node value free function
    int (*match)(void *ptr, void *key); // Node value comparison function
    unsigned long len;            // Number of nodes
} list;

Compressed List

The compressed list is designed as a memory-efficient structure that occupies a contiguous block of memory. It leverages CPU cache and encodes data differently based on length to save space. It is used for List, Hash, and Sorted Set objects when they contain few elements or small values.

Structure:

A compressed list is a sequential data structure built from a contiguous memory block, similar to an array but with variable-size elements. The header has three fields:

• zlbytes: Total bytes occupied by the compressed list.
• zltail: Offset from the start address to the tail node.
• zllen: Number of nodes in the list.
• zlend: End marker, fixed value 0xFF (255).

Each node (entry) contains:

• prevlen: Length of the previous node, enabling reverse traversal.
• encoding: Type and length of the current node's data (string or integer).
• data: The actual stored data.

Memory is saved by using variable space for prevlen and encoding based on data size:

• If the previous node's length is less than 254 bytes, prevlen uses 1 byte.
• If the previous node's length is 254 bytes or more, prevlen uses 5 bytes (first byte 0xFE, next 4 store the length).
• The size of encoding depends on whether the data is a string or integer and its length.

Cascade Update

When adding or modifying an element in a compressed list, if space is insufficient, reallocation occurs. Inserting a large element may change subsequent nodes' prevlen sizes, triggering a cascade that forces reallocation of multiple nodes, degrading performence. For example, if consecutive nodes are 250-253 bytes and a new node of 254+ bytes is inserted, each subsequent node's prevlen expands, causing a chain reaction. Thus, compressed lists are only suitable for scenarios with few nodes.

Hash Table

Hash tables enable O(1) lookup by computing an index from a key through a hash function. They are implemented as an array for quick access, but collisions increase with data volume. Redis uses chaining to handle collisions, linking entries with the same hash in a list.

Structure:

typedef struct dictht {
    dictEntry **table;     // Hash array
    unsigned long size;    // Table size
    unsigned long sizemask; // Mask for index calculation
    unsigned long used;    // Number of nodes
} dictht;

Hash table node:

typedef struct dictEntry {
    void *key;      // Key
    union {
        void *value;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;            // Value
    struct dictEntry *next; // Next node in chain
} dictEntry;

Rehashing

Redis uses a dict structure with two hash tables (ht[2]):

typedef struct dict {
    dictht ht[2];
    ...
} dict;

During normal operation, data is written to ht[0]. When rehashing is triggered:

1. Allocate space for ht[1], typically twice the size of ht[0].
2. Migrate data from ht[0] to ht[1].
3. Free ht[0], set ht[1] as the new ht[0], and create a new empty ht[1] for future rehashing.

Progressive rehashing avoids lengthy interruptions by spreading the migration over multiple operations:

• During rehashing, each lookup, insert, update, or delete also migrates one bucket's entries from ht[0] to ht[1].
• Lookups check ht[0] first, then ht[1] if not found.
• New keys are added only to ht[1].
• Updates and deletes affect both tables.

Trigger conditions: Rehashing is initiated based on the load factor (used / size):

• If the load factor is ≥ 1 and no RDB snapshot (bgsave) or AOF rewrite is in progress.
• If the load factor is ≥ 5, rehashing is forced regardless of background tasks.

Integer Set

An integer set is an underlying implementation for Set objects when all elements are integers and few in number. It is a contiguous memory block defined as:

typedef struct intset {
    uint32_t encoding;  // Encoding type
    uint32_t length;    // Number of elements
    int8_t contents[];  // Element array
} intset;

The array type depends on the encoding.

Upgrade mechanism: When adding a new integer larger than the current type, the set upgrades by expanding the existing array to accommodate the larger type. For example, if encoding is INTSET_ENC16 and a 32-bit integer is added, the array expands each element to 32 bits. This saves memory by not pre-allocating larger types unnecessarily.

Skip List

The Zset (sorted set) object in Redis uses a skip list to support O(log N) node queries. The Zset structure is:

typedef struct zset {
    dict *dict;         // Hash table for single-point queries
    zskiplist *zsl;     // Skip list for range queries
} zset;

Inserts and updates affect both the hash table and skip list to maintain consistency.

Skip list node structure:

typedef struct zskiplistNode {
    sds ele;                    // Element value
    double score;               // Element weight
    struct zskiplistNode *backward; // Backward pointer
    struct zskiplistLevel {
        struct zskiplistNode *forward; // Forward pointer
        unsigned long span;            // Span to next node
    } level[];                  // Level array
} zskiplistNode;

Query process: Start from the highest level and traverse until finding a node with a value less than or equal to the target, then move down to the next level, repeating until the bottom level is reached.

Level distribution: The ideal ratio of nodes between adjacent levels is 2:1 for O(log N) performance. Redis randomly generates levels per node without strictly maintaining this ratio (using p=0.25, averaging 1.33 pointers per node).

Why Skip List Over Balanced Tree?

• Memory: Balanced trees need two pointers per node; skip lists average 1.33 pointers per node (with p=0.25).
• Range queries: Skip lists are simpler to implement for range scans.
• Implementation complexity: Skip lists are easier to code and maintain.

Quicklist

Introduced in Redis 3.2, the quicklist replaced the previous list of compressed lists or doubly linked lists. It combines a doubly linked list with compressed lists, where each linked list node contains a compressed list. By controlling the size or element count of each compressed list, it mitigates cascade update issues.

Structure:

typedef struct quicklist {
    quicklistNode *head;      // Head node
    quicklistNode *tail;      // Tail node
    unsigned long count;      // Total elements across all compressed lists
    unsigned long len;        // Number of nodes
} quicklist;

Node structure:

typedef struct quicklistNode {
    struct quicklistNode* prev; // Previous node
    struct quicklistNode* next; // Next node
    unsigned char *zl;          // Pointer to compressed list
    unsigned int sz;            // Size of compressed list in bytes
    unsigned int count : 16;    // Number of elements in compressed list
} quicklistNode;

When inserting, if the current node's compressed list can accommodate the new element, it is added there; otherwise, a new quicklist node is created.

Listpack

Introduced in Redis 5.0, listpack is designed to replace compressed lists. Its key feature is that each node no longer stores the length of the previous node, eliminating cascade updates entirely.

Structure:

The header contains total bytes and element count, followed by nodes, and ends with a terminator. Each node includes:

• Encoding type
• Actual data
• Total length of encoding and data

Unlike compressed lists, it does not store the previous node's length.