As an in-memory engine, Redis organizes key-value pairs using specific object types. There are five primary value categories supported: String, Hash, List, Set, and Sorted Set. While these interfaces remain consistent for developers, the underlying storage mechanisms vary dynamically based on data content to optimize performance and memory usage.

Each object is defined by a structure containing metadata about its type, encoding, and a pointer to the actual data. This design allows Redis to adapt the implementation of an abstract type to concrete scenarios.

Core Object Structure

The fundamental unit storing keys and values utilizes a structure containing three main fields:

typedef struct robj {
    // Defines the logical type (String, List, etc.)
    unsigned int obj_type : 4;
    // Specifies the internal representation format
    unsigned int enc_method : 4;
    // Pointer to the concrete underlying data
    void *data_ptr;
} redis_object;

The obj_type field identifies the conceptual category (e.g., string), while enc_method dictates the specific algorithm used to store it (e.g., raw string vs. integer encoding). The data_ptr references the heap-allocated memory holding the actual payload. Note that for keys, this is always a string type; for values, it matches the selected object type.

String Objects and SDS

Strings are the most frequent object type. Internally, they can be encoded as integers, simple dynamic strings (SDS), or embedded strings depending on the value size.

Integer Encoding

If a string contains a numeric value fitting within a standard long integer range, Redis optimizes storage by using the int encoding. For instance, setting a value like 10086 stores the raw integer rather than string bytes.

Simple Dynamic Strings (SDS)

For text data, Redis relies on SDS instead of standard C strings. An SDS header manages buffer management:

struct sds_header {
    // Actual length of the stored string
    int string_len;
    // Unused space available in the buffer
    int free_bytes;
    // Byte array holding the content
    char buf[];
};

Unlike C strings, SDS does not rely on null terminators for length calculations. Instead, it tracks string_len explicitly. This provides several engineering benefits:

1. Length Retrieval: Accessing the string length is O(1) because the length is pre-calculated in the header.
2. Buffer Safety: Operations check bounds before writing, eliminating buffer overflow risks common with C string functions like strcat.
3. Memory Efficiency: Modifications trigger fewer reallocations due to reserved space logic.
4. Binary Compliance: Unlike C strings which stop at null characters, SDS supports binary-safe data, allowing storage of arbitrary byte sequences.

Raw vs. Embstr Encodings

When the string exceeds 39 bytes, the system uses raw encoding. This allocates two separate blocks: one for the header structure (redis_object) and another for the buffer (sdshdr). Conversely, short strings (≤ 39 bytes) use embstr. In this mode, both structures share a single contiguous memory allocation, improving cache locality and reducing allocation overhead. Any modification to an embstr object forces a conversion back to raw encoding.

List Implementations

Lists support double-ended queue operations. The storage choice depends on element count and size thresholds defined in the configuration.

Linked List

By default, larger lists utilize a doubly-linked list structure. Each node contains forward and backward pointers along with the payload:

typedef struct list_element {
    struct list_element *prev_node;
    struct list_element *next_node;
    void *element_value;
}

The container maintains head and tail pointers for efficient access at both ends, plus a counter for instant length retrieval.

Compression List (ZipList)

To save memory on small lists, Redis employs a ZipList. This is a serialized sequence of variable-length entries stored contiguously in memory. It avoids per-node pointer overhead but offers slower insertion/deletion compared to linked lists due to shifting elements during modifications. Switching occurs when the number of elements or their total size exceeds specific limits (default: 512 items or 64 bytes per item).

Hash Table Structures

Hash objects map keys to values. The backend switches between a compact linear structure and a full hash table.

Dictionary Implementation

The standard dictionary utilizes a hash tible structure:

typedef struct dict_table {
    dict_entry **table_array;
    unsigned long current_size;
    unsigned long size_mask;
    unsigned long active_count;
} hash_table;

Entries handle collisions via chaining, pointing to the next entry if bucket indices collide.

Incremental Rehashing

To prevent locking the server during massive resizing, Redis employs incremental rehashing across two tables (ht[0] and ht[1]). When the load factor triggers growth:

1. Allocate a new empty table (ht[1]).
2. Distribute the rehash_index from the start point.
3. On every dictionary operation, migrate a few slots from ht[0] to ht[1] alongside the requested action.
4. Continue until ht[0] is empty, then swap roles and clear ht[1].

This spreads the CPU cost of moving keys over time rather than batching it.

Set Objects

Sets require unique elements. Storage depends on element types and volume.

IntSet

For small sets composed purely of integers, Redis uses IntSet. This structure maintains a sorted, compact array without pointers.

typedef struct int_container {
    uint32_t encoding_type; // INTSET_ENC_INT16/32/64
    uint32_t item_count;
    int8_t contents[];
}

Crucially, contents type varies based on the encoding_type. If a new integer exceeds the capacity of the current integer type (e.g., moving from 32-bit to 64-bit), the entire array upgrades to accommodate the larger type. Downgrades are not performed once promoted.

Hash Table Mode

Non-integer data or large volumes switch the set to a dictionary-based structure, where keys represent elements and values are null pointers.

Sorted Sets

Sorted sets combine uniqueness with ranking. They balance Ziplists for small datasets and Skip Lists for complex queries.

Skip List Mechanism

A skip list acts as a multi-level index over sorted nodes. Each node points to multiple successors, enabling logarithmic search time.

typedef struct skip_list_node {
    struct skip_list_node *backwards;
    double rank_score;
    redis_object *member_ref;
    struct level_node {
        struct skip_list_node *forward_ref;
        unsigned int span;
    } levels[];
}

The structure is paired with a dictionary for O(1) lookups of a member's score. The combined approach ensures fast range scans via the Skip List and instant score retrieval via the Dictionary.

Small sorted sets retain the Ziplist optimization for space efficiency, switching to Skip Lists only when the item count or member length crosses configured thresholds.