Redis Set & Sorted‑Set Dual Encodings: intset, hashtable, skiplist, ziplist

Introduction

Redis uses two different internal representations for set objects and sorted‑set objects. For sets the representations are intset and hashtable ; for sorted sets they are skiplist and ziplist . The article explores why both are used and whether they double memory usage.

Set objects

intset encoding

intset stores only integer values using one of three integer types: int16_t, int32_t, or int64_t. The underlying C structure is:

typedef struct intset {
    uint32_t encoding;   // encoding type
    uint32_t length;    // number of elements
    int8_t contents[];  // actual elements, type determined by encoding
} intset;

The encoding field can be INTSET_ENC_INT16 , INTSET_ENC_INT32 , or INTSET_ENC_INT64 , which determines the range of values stored in contents[]. When a new element does not fit the current encoding, the set is upgraded through four steps: expand the array, convert existing elements, insert the new element at the appropriate end, and update encoding and length. Upgrades are one‑way; an intset never downgrades.

hashtable encoding

If a set contains any non‑integer element or more than set-max-intset-entries elements (default 512), Redis switches to a hash table representation.

Common set commands

sadd key member1 member2

– add members. sismember key member – test membership. srem key member1 member2 – remove members. smove source dest member – move a member. smembers key – list all members.

Sorted‑set objects

Sorted sets store a double‑precision score for each member and keep members ordered by score. Their internal representations are skiplist and ziplist .

skiplist encoding

A skiplist consists of nodes of type zskiplistNode:

typedef struct zskiplistNode {
    sds ele;                     // element string
    double score;                // score
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer
        unsigned long span;            // distance to next node
    } level[];
} zskiplistNode;

The skiplist object ( zskiplist) holds pointers to the header and tail, the total length, and the maximum level. Redis wraps the skiplist together with a hash table ( dict) in a zset structure, allowing O(1) look‑ups via the dictionary and O(log N) range queries via the skiplist.

ziplist encoding

A ziplist is used when the sorted set contains at most zset-max-ziplist-entries (default 128) elements and the total serialized length of all elements is less than zset-max-ziplist-value (default 64 bytes). Otherwise Redis falls back to the skiplist representation.

Common sorted‑set commands

zadd key score1 member1 [score2 member2 ...]

zscore key member

zincrby key increment member

zcount key min max

zrange key start stop

zrevrange key start stop

zrangebyscore key min max

zrevrangebyscore key max min

zrank key member

zrevrank key member

zlexcount key min max

Summary

The article analyses the internal storage structures of Redis set and sorted‑set objects, explains the conditions that trigger intset ↔ hashtable and skiplist ↔ ziplist conversions, and shows the key commands for working with these data types.