Inside Redis: How Memory Structures and Encoding Power Its 5 Data Types

Redis Memory Structures and Encoding

Redis supports five logical data types (String, List, Set, Sorted Set, Hash) but each type is backed by a specific in‑memory data structure and encoding. The choice of structure depends on the stored value’s size, type, and usage pattern.

OBJECT and DEBUG OBJECT Commands

The OBJECT ENCODING key command reveals the internal encoding of a key, while DEBUG OBJECT key provides additional details such as reference count, serialized length, and idle time, which influence eviction decisions.

Simple Dynamic String (SDS)

SDS is Redis’s own string implementation. It stores the length, free space, and a character buffer, enabling O(1) length queries and efficient memory management.

struct sdshdr {
    unsigned int len;   // current length of the string
    unsigned int free;  // unused space allocated after the string
    char buf[];         // actual characters
};

Utility functions such as sdslen return the length directly:

static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

Linked List

Redis List is implemented as a doubly linked list in Redis 3.0, providing O(1) push/pop at both ends.

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

Since Redis 3.2, the quicklist combines linked lists with zip‑lists to improve memory efficiency.

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;   // total entries in all zip‑lists
    unsigned int len;      // number of quicklist nodes
    int fill : 16;         // fill factor for nodes
    unsigned int compress : 16; // depth of nodes not compressed
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;    // pointer to zip‑list data
    unsigned int sz;      // zip‑list size in bytes
    unsigned int count : 16; // number of entries in this zip‑list
    unsigned int encoding : 2; // RAW or LZF
    unsigned int container : 2; // NONE or ZIPLIST
    unsigned int recompress : 1;
    unsigned int attempted_compress : 1;
    unsigned int extra : 10;
} quicklistNode;

Dictionary (hash table)

Redis Hashes are stored in a hash table (dict) that uses chaining to resolve collisions and a progressive rehash algorithm to avoid long pauses.

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx;   // -1 when not rehashing
    int iterators;
} dict;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

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

The rehash process creates a new dictht at ht[1] and gradually moves entries from ht[0] while rehashidx advances.

Skip List (Sorted Set)

Sorted Sets (ZSET) use a skip list for fast range queries and ordered iteration.

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

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level; // current max level
} zskiplist;

Integer Set (intset)

Sets that contain only integers within a limited range are stored as a compact array called intset.

typedef struct intset {
    uint32_t encoding;   // size of each integer (16, 32 or 64 bits)
    uint32_t length;     // number of elements
    int8_t contents[];  // actual integer values
} intset;

When a larger integer is added, the encoding is upgraded (e.g., from INT16 to INT32) but never downgraded.

Zip List (compressed list)

Zip lists are used as a memory‑efficient representation for small Lists, Hashes and Sorted Sets.

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;
    unsigned char *p;
} zlentry;

Configuration parameters such as hash-max-ziplist-entries, list-max-ziplist-value, etc., control when zip lists are used.

Redis Object Mapping

Every logical data type is wrapped in a redisObject that stores the type, encoding, reference count, LRU idle time and a pointer to the underlying data structure.

typedef struct redisObject {
    unsigned type:4;      // REDIS_STRING, REDIS_LIST, …
    unsigned encoding:4; // RAW, INT, HT, ZIPMAP, LINKEDLIST, ZIPLIST, INTSET, SKIPLIST, EMBSTR
    unsigned lru:REDIS_LRU_BITS;
    int refcount;
    void *ptr;           // pointer to the actual data structure
} robj;

Constants define the type and encoding values (e.g., REDIS_STRING 0, REDIS_ENCODING_EMBSTR 8).

Memory Management Strategies

Redis maintains a separate dict for each database (key space). Each client is attached to a specific DB index.

typedef struct redisClient {
    uint64_t id;
    int fd;
    redisDb *db;
} redisClient;

typedef struct redisDb {
    dict *dict;          // main key space
    dict *expires;       // expiration timestamps
    dict *blocking_keys;
    dict *ready_keys;
    dict *watched_keys;
    struct evictionPoolEntry *eviction_pool;
    int id;
    long long avg_ttl;
} redisDb;

Expiration timestamps are stored in redisDb->expires and are checked by the event loop.

Expiration Policies

Redis offers two deletion strategies:

Lazy deletion : When a key is accessed, expireIfNeeded checks its TTL and deletes it if expired.

Periodic deletion : The server’s event loop runs activeExpireCycle to sample random keys and delete expired ones.

robj *lookupKeyRead(redisDb *db, robj *key) {
    expireIfNeeded(db,key);
    return lookupKey(db,key);
}

int expireIfNeeded(redisDb *db, robj *key) {
    mstime_t when = getExpire(db,key);
    if (when < 0) return 0; // no expiration
    mstime_t now = mstime();
    if (now <= when) return 0; // not yet expired
    // delete the key
    server.stat_expiredkeys++;
    propagateExpire(db,key);
    notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,"expired",key,db->id);
    return dbDelete(db,key);
}

LRU Eviction

When maxmemory is reached, Redis applies a policy such as noeviction, allkeys-lru, volatile-lru, allkeys-random, volatile-random or volatile-ttl. The algorithm samples a configurable number of keys ( maxmemory-samples) to approximate the least‑recently‑used entries.

Persistence: RDB and AOF

Redis supports two persistence mechanisms:

RDB (snapshot): Triggered by the save configuration (e.g., save 900 1 means save after 1 change within 900 seconds). It can run in the background via BGSAVE or block the server with SAVE.

AOF (append‑only file): Every write command is appended to a log. The appendfsync setting controls how often the log is flushed to disk ( always, everysec, no). AOF files are periodically rewritten to shrink size.

struct redisServer {
    long long dirty;          // changes since last save
    time_t lastsave;           // timestamp of last successful save
    long long dirty_before_bgsave;
    pid_t rdb_child_pid;
    struct saveparam *saveparams; // array of save points
};

typedef struct saveparam {
    time_t seconds;
    int changes;
} saveparam;

During loading, Redis prefers AOF over RDB. If a key is already expired when an RDB snapshot is taken, it is omitted; during AOF replay, expired keys are removed via DEL commands.

Understanding these internal structures and policies helps developers tune Redis for performance, memory usage, and durability according to their specific workloads.