Redis Internal Data Structures and Object Implementations

1. Introduction and Applications

Redis is a high‑performance, network‑enabled, in‑memory key‑value database written in ANSI C, with persistence support and APIs for multiple languages. It primarily provides five data types: String, List, Hash, Set, and ZSet.

Typical Redis use cases in internet companies include:

String: caching, rate limiting, counters, distributed locks, distributed sessions.

Hash: storing user information, homepage visit counts, composite queries.

List: timeline lists for followers, simple queues.

Set: likes, dislikes, tags, friend relationships.

ZSet: leaderboards.

For example, during a large e‑commerce promotion, a design may directly decrement inventory in Redis, log the operation, and synchronize to a database via a worker that must handle concurrency and duplicate processing.

2. Redis Object redisObject

When executing SET hello world, Redis creates a dictEntry for the key‑value pair, stores the key as an SDS (Simple Dynamic String), and stores the value in a redisObject. The redisObject holds a type field indicating the value type and a ptr field pointing to the actual data structure.

All five Redis data types are represented by redisObject, allowing each type to have multiple internal encodings, memory‑reclamation strategies, and shared objects, which optimizes performance for different scenarios.

Memory for these objects is allocated by a memory allocator such as jemalloc, which reduces fragmentation by categorizing allocations into small, large, and huge ranges and selecting the best‑fit block.

The encoding attribute of a redisObject determines the concrete data structure used. For example, the following command shows the encoding for the key hello:

3. String

String objects can be encoded as int, raw, or embstr. The embstr encoding allocates a single contiguous memory block, while raw requires two allocations.

Strings up to 39 bytes use embstr, 8‑byte integers use int, and larger strings use raw.

The underlying SDS structure is similar to C++ std::string or Java ArrayList and stores length, free space, and a null‑terminated buffer:

struct sdshdr {
    // length of used space in buf
    int len;
    // length of free space in buf
    int free;
    // data buffer
    char buf[]; // '\0' terminated
};

get: sdsrange – O(n)

set: sdscpy – O(n)

create: sdsnew – O(1)

len: sdslen – O(1)

Because the length is stored in the structure, retrieving an SDS length is O(1). SDS also employs pre‑allocation, lazy free space, and automatic buffer‑overflow protection.

4. List

List objects are implemented with quicklist, a hybrid of ziplist (compressed list) and linkedlist (doubly linked list). Redis lists support push/pop on both ends, random access, and can act as arrays, queues, or stacks.

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

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

rpush: listAddNodeHead – O(1)

lpush: listAddNodeTail – O(1)

push: listInsertNode – O(1)

index: listIndex – O(N)

pop: ListFirst/ListLast – O(1)

llen: listLength – O(N)

When the list contains few elements, Redis may use a ziplist; otherwise it uses a linkedlist. The quicklist combines multiple ziplist segments linked together, with the first and last segments uncompressed for fast push/pop. Compression depth can be adjusted, and LZF compression may be applied.

5. Hash

Hash objects are implemented either as ziplist (compressed) or as a hashtable. A hash uses the compressed representation when the number of entries is less than 512 and each key/value is shorter than 64 bytes.

The hashtable provides O(1) read/write performance. Its core structures are shown below:

typedef struct dict {
    // type‑specific functions
    dictType *type;
    // private data
    void *privdata;
    // hash tables (two for incremental rehashing)
    dictht ht[2];
    // rehash index (-1 when not rehashing)
    int rehashidx;
    // number of active safe iterators
    int iterators;
} dict;

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

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

Redis uses two hash tables during rehashing: the active table ht[0] and a new table ht[1]. Keys are gradually moved from the old to the new table to keep the load factor within a reasonable range.

6. Set

Set objects are backed by either an intset (integer set) when all members are integers and the set is small, or a hashtable for general cases.

typedef struct intset {
    // encoding (16, 32 or 64 bit)
    uint32_t encoding;
    // number of elements
    uint32_t length;
    // array of integers
    int8_t contents[];
} intset;

sadd: intsetAdd – O(1)

smembers: intsetGet – O(N)

srem: intsetRemove – O(N)

slen: intsetlen – O(1)

The intset stores elements in a sorted, duplicate‑free array. When a larger integer size is needed, the array is upgraded (e.g., from 16‑bit to 32‑bit), which improves flexibility while saving memory.

7. ZSet (Sorted Set)

ZSet objects are implemented with either a ziplist (for small sorted sets) or a skiplist (for larger sets or long members). The skiplist provides O(log N) average search time, comparable to balanced trees but with simpler implementation.

typedef struct zskiplist {
    // head and tail nodes
    struct zskiplistNode *header, *tail;
    // number of nodes
    unsigned long length;
    // max level of any node
    int level;
} zskiplist;

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

Operations such as ZADD, ZREM, and ZRANK have average complexities of O(log N) and worst‑case O(N).

In summary, Redis achieves high efficiency and stability through carefully designed internal objects, multiple encoding strategies, and memory‑friendly data structures such as SDS, quicklist, hashtable, intset, and skiplist.

PS: If you find this sharing useful, feel free to like and share.