Understanding Redis Data Types and Their Internal Memory Implementations

Preface

Redis is a non‑relational, key‑value database known for its high read/write speed, making it popular as a cache. It stores data using five object types: String, List, Hash, Set, and Sorted Set. All keys are strings, while values can be any of these five object types.

The internal memory layout of a Redis object is illustrated in the first diagram.

1. String Objects

Keys are always string objects, and values can also be created as strings. Depending on the encoding, strings use one of three formats: int, raw, or embstr.

1.1 int encoding

When the stored value is an integer, Redis uses int encoding, keeping the data directly in memory without extra structures.

1.2 raw encoding

Raw encoding stores data using the SDS (Simple Dynamic String) structure. The SDS header is defined as:

/*
 *  Structure that stores a string object
 */
struct sdshdr {
    // length of used space in buf
    int len;
    // free space in buf
    int free;
    // actual character buffer
    char buf[];
};

The len field records the used length, free the remaining capacity, and buf holds the characters. SDS provides O(1) length retrieval, reduces reallocations by pre‑checking free space, and can store binary data because it tracks length explicitly.

1.3 embstr encoding

Embstr also uses SDS but allocates a single contiguous block for both the redisObject header and the string data when the string is ≤ 32 bytes. This reduces the two‑allocation overhead required by raw encoding.

2. List Objects

Lists can be encoded as either ziplist or linkedlist. Ziplist is a compact sequential memory layout used when all elements are < 64 bytes and the list has < 512 entries. Linkedlist uses a doubly linked list for larger lists.

2.1 ziplist encoding

A ziplist consists of a series of specially encoded entries stored in a contiguous memory block. The following image shows its structure.

2.2 linkedlist encoding

When ziplist conditions are not met, Redis falls back to a doubly linked list where each node stores a string object.

3. Hash Objects

Hashes can be stored as ziplist (for small hashes) or as a hashtable.

3.1 ziplist encoding

Similar to list ziplist, but entries are stored as alternating key‑value pairs.

3.2 hashtable encoding

The hashtable uses a dict structure defined as:

typedef struct dictht {
    // array of dictEntry pointers
    dictEntry **table;
    // size of the hash table (power of two)
    unsigned long size;
    // mask for indexing (size‑1)
    unsigned long sizemask;
    // number of used entries
    unsigned long used;
} dictht;

Keys are hashed to an index; collisions are resolved by chaining. When the load factor grows, Redis performs a rehash, allocating a larger table (next power‑of‑two size) and gradually moving entries.

4. Set Objects

Sets are stored either as an intset (when all members are integers and the set size < 512) or as a hashtable. The intset uses a compact integer array, while the hashtable stores generic objects.

5. Sorted Set Objects

Sorted sets use ziplist for small collections (elements < 64 bytes, count < 128) or a skiplist combined with a hashtable for larger sets.

5.1 ziplist

Elements are stored as value, score pairs in a compact list, preserving order by score.

5.2 skiplist

The skiplist merges the O(1) lookup of a hash table with the ordered traversal of a skiplist. Its node structure is:

typedef struct zskiplistNode {
    // array of levels, each with forward pointer and span
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
    // backward pointer
    struct zskiplistNode *backward;
    // score used for ordering
    double score;
    // actual member object
    robj *obj;
} zskiplistNode;

Each node contains forward pointers for multiple levels, a backward pointer, the score, and the member object, enabling O(log N) range queries while maintaining fast exact lookups via the accompanying hash table.

Conclusion

Redis provides a variety of data types to support different business scenarios such as follower lists, leaderboards, and more. Each type employs specific encodings and underlying data structures to balance memory efficiency and query speed, illustrating Redis’s careful design for high‑performance in‑memory storage.

References

"Redis Design and Implementation (Second Edition)"