Understanding Redis Object Types and Their Underlying Data Structures

1. Object Types and Encoding

Redis stores keys and values as redisObject structures, which contain three fields: type (the object type), encoding (the internal representation), and ptr (a pointer to the underlying data structure).

typedef struct redisObject {
    unsigned type:4;      // object type
    unsigned encoding:4;  // internal encoding
    void *ptr;            // pointer to actual data
} robj;

The key object is always a string, while the value object can be one of the five supported types, each with one or more possible encodings.

2. String Objects

String values can be encoded as int, raw, or embstr. An int encoding stores a numeric value directly as a C long. raw uses a Simple Dynamic String (SDS) for strings longer than 39 bytes, while embstr uses an embedded SDS for shorter strings.

2.1 Simple Dynamic String (SDS)

SDS is defined by the sdshdr structure:

struct sdshdr {
    int len;   // length of the string
    int free;  // unused bytes in the buffer
    char buf[]; // actual character data
};

SDS stores the length explicitly, allowing O(1) length queries, preventing buffer overflows, reducing reallocations, and providing binary safety.

2.2 raw vs. embstr

When a string exceeds 39 bytes, Redis creates a raw encoded object whose ptr points to an SDS allocated separately. For strings ≤39 bytes, Redis uses embstr, allocating a single memory block that contains both the redisObject and the SDS header, saving one allocation.

2.3 Encoding Conversion

If a string initially encoded as int or embstr is modified so that it no longer fits the original criteria, Redis automatically converts it to raw encoding.

3. List Objects

Lists can be encoded as linkedlist or ziplist. The linkedlist implementation uses a doubly‑linked list of listNode structures, while ziplist is a compact sequential memory layout used when the list is small (elements < 64 bytes and count < 512).

typedef struct listNode {
    struct listNode *prev; // previous node
    struct listNode *next; // next node
    void *value;           // stored value
} listNode;

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

The list structure provides O(1) access to head/tail and length, and supports polymorphic values via void* pointers.

4. Hash Objects

Hashes can be encoded as ziplist (for small hashes) or hashtable. The hashtable implementation uses the generic Redis dictionary.

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

typedef struct dictEntry {
    void *key;            // key object
    union {
        void *val;      // value object
        uint64_t u64;    // unsigned integer value
        int64_t s64;     // signed integer value
    } v;
    struct dictEntry *next; // next entry in the same bucket (chaining)
} dictEntry;

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

When the hash’s total key/value length is < 64 bytes and the number of fields < 512, Redis uses a ziplist; otherwise it falls back to the hashtable.

Rehashing

Redis performs incremental rehashing to avoid long pauses. It allocates a second table ht[1], then gradually moves buckets from ht[0] to ht[1] during normal dictionary operations, updating rehashidx until migration completes.

5. Set Objects

Sets are encoded as intset when all members are integers and the set size ≤ 512; otherwise a hashtable is used.

typedef struct intset {
    uint32_t encoding; // 16, 32 or 64‑bit integer encoding
    uint32_t length;   // number of elements
    int8_t contents[]; // sorted array of integers (actual type depends on encoding)
} intset;

The integer set maintains elements in sorted order without duplicates, enabling O(log N) searches and O(1) memory usage for small integer collections.

6. Sorted Set Objects

Sorted sets can be encoded as ziplist (for very small sets) or skiplist. The skiplist implementation stores elements in a zskiplist structure and also keeps a hash table for O(1) member‑to‑score lookups.

typedef struct zskiplistNode {
    struct zskiplistNode *backward; // backward pointer
    double score;                  // sorting score
    robj *obj;                     // member object
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer for this level
        unsigned int span;              // distance to the next node at this level
    } level[];
} zskiplistNode;

typedef struct zset {
    zskiplist *zs1; // skiplist of (score, member) pairs
    dict *dict;     // hash table mapping member -> score
} zset;

The skiplist provides O(log N) range queries by score, while the dictionary enables O(1) exact member lookups.

7. Summary

Redis’s core in‑memory data structures include Simple Dynamic Strings (SDS), linked lists, dictionaries, skiplists, integer sets, and ziplists. These structures underpin the five primary object types—strings, lists, hashes, sets, and sorted sets—each offering multiple encodings that trade memory usage for performance based on size and access patterns.