How Redis Implements the Hash Type

How Redis Implements the Hash Type

The Hash type is one of the basic data types in Redis and is very widely used. Here we analyze how the Hash type is implemented.

Redis Data Structures from a Macro Perspective

Before analyzing the Hash data type, we need to understand how Redis is organized as a whole. After Redis starts, it calls the initServer function to initialize the global variable struct redisServer server;, which holds all database information, and then calls aeMain(server.el); to enter the event loop, continuously receiving and executing client commands. Data is also stored in the redisDB within redisServer. The redisDB stores all key-value pairs through a dictionary dict, and the dictionary dict is implemented via the hash table dictht.

redisServer   // global variable server, holds all database information
--> redisDB   // database info, 16 databases by default
    --> dict   // dictionary, holds all key-value pairs
        --> dictht   // hash table, the underlying data structure

The important data structure definitions are as follows:

// redisServer holds all database information
struct redisServer {
    redisDb *db;  // database array, 16 databases by default
    // ...
}
// redis database, 16 databases by default
typedef struct redisDb {
    dict *dict;  // dictionary, holds all key-value pairs
    // ...
    int id;    // database id
} redisDb;
// dictionary, holds all key-value pairs
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

typedef struct dictEntry {
    void *key;    // key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;    // value
    struct dictEntry *next;   // points to the next node
} dictEntry;

In the hash table dictht, key-value pairs are stored via dictEntry. Both key and value are redisObject objects. The key is always a string-type object, while the value differs depending on the underlying data structure of the specific data type—it can be a string, a hash table, and so on.

Note that the source code analyzed here is from redis-6.2.8; implementation details may differ from the latest code.

See also Redis[4] Redis Data Structures from a Macro Perspective

The Dictionary

The dictionary is the data structure Redis uses to store key-value pair data; its implementation is based on the hash table. As you can see, the dictionary structure defines dictht ht[2]—it is implemented with two hash tables. Why two? This is to solve the dictionary’s resize problem by implementing incremental rehashing, avoiding the performance hit of a one-shot rehash.

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

Let us look at the dictRehash function, which migrates n elements to the new table; the migration finds the next element to migrate, moves it to the new table, sets the old bucket to NULL, and updates rehashidx.

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    unsigned long s0 = d->ht[0].size;
    unsigned long s1 = d->ht[1].size;
    // check whether rehashing is allowed
    if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;
    if (dict_can_resize == DICT_RESIZE_AVOID &&
        ((s1 > s0 && s1 / s0 < dict_force_resize_ratio) ||
         (s1 < s0 && s0 / s1 < dict_force_resize_ratio)))
    {
        return 0;
    }

    while(n-- && d->ht[0].used != 0) { // run n steps, each step migrates one node from ht[0] to ht[1]
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1; // skip empty buckets
        }
        de = d->ht[0].table[d->rehashidx]; // get the element of the current bucket
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;   // insert the element into the new hash bucket
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;  // set the old hash bucket to empty
        d->rehashidx++;   // index of the next bucket to process
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {  // if ht[0] is already empty, rehash is complete
        zfree(d->ht[0].table);  // free ht[0]
        d->ht[0] = d->ht[1];  // reset ht[0]
        _dictReset(&d->ht[1]);  // reset ht[1]
        d->rehashidx = -1;   // set rehashidx to -1, indicating rehash is complete
        return 0;
    }

    /* More to rehash... */
    return 1;
}

The migration is incremental—only n buckets are migrated at a time. There are generally two processes that perform migration: during normal command requests, 1 bucket is migrated; and the periodic task serverCron periodically calls incrementallyRehash, which in turn calls dictRehashMilliseconds, which calls dictRehash, migrating 100 buckets each time.

Reference: Redis Design and Implementation

The Hash Type Implementation

After introducing Redis data structures from a macro perspective and the dictionary, we can get to the main point: how the Hash type is implemented.

The Hash type is implemented via the compressed list (ziplist) and the dictionary (dict) underneath. Because the ziplist saves more memory than the dict, when a new Hash key is created, the program uses the ziplist as the underlying implementation by default, and only converts the underlying implementation from ziplist to dict when needed.

robj *createHashObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;   // underlying implementation is the ziplist
    return o;
}

So when does the conversion happen?

• When the number of elements exceeds the threshold server.hash_max_ziplist_entries, conversion occurs.
• When the length of some key or value exceeds the threshold server.hash_max_ziplist_value, conversion also occurs.

void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
    int i;
    size_t sum = 0;

    if (o->encoding != OBJ_ENCODING_ZIPLIST) return;

    for (i = start; i <= end; i++) {
        if (!sdsEncodedObject(argv[i]))
            continue;
        size_t len = sdslen(argv[i]->ptr);
        if (len > server.hash_max_ziplist_value) { // when value length exceeds this value, convert
            // convert the ziplist to a hash table
            // the conversion process: create a hash table, traverse the ziplist, get key/value, then insert into the hash table
            hashTypeConvert(o, OBJ_ENCODING_HT);
            return;
        }
        sum += len;
    }
    if (!ziplistSafeToAdd(o->ptr, sum))
        hashTypeConvert(o, OBJ_ENCODING_HT);
}

Let us look at the hset command implementation, i.e., adding data to a Hash-type data structure:

void hsetCommand(client *c) {
    int i, created = 0;
    robj *o;

    if ((c->argc % 2) == 1) {  // argument count must be even, so field and value come in pairs
        addReplyErrorFormat(c,"wrong number of arguments for '%s' command",c->cmd->name);
        return;
    }

    // check whether the key exists in the keyspace; if not, create a new hash object
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
    // try to convert the type, checking the length of key/value; if over a certain size, convert ziplist to hash table
    hashTypeTryConversion(o,c->argv,2,c->argc-1);

    // iterate over all fields and values, inserting into the underlying data structure
    // the specific insertion must check whether it is a ziplist or a hash table
    for (i = 2; i < c->argc; i += 2)
        created += !hashTypeSet(o,c->argv[i]->ptr,c->argv[i+1]->ptr,HASH_SET_COPY);

    /* HMSET (deprecated) and HSET return value is different. */
    char *cmdname = c->argv[0]->ptr;
    if (cmdname[1] == 's' || cmdname[1] == 'S') {
        /* HSET */
        addReplyLongLong(c, created);
    } else {
        /* HMSET */
        addReply(c, shared.ok);
    }
    signalModifiedKey(c,c->db,c->argv[1]);  // notify the database that the key was modified
    // publish keyspace notification
    notifyKeyspaceEvent(NOTIFY_HASH,"hset",c->argv[1],c->db->id);
    server.dirty += (c->argc - 2)/2;   // increment the database dirty counter
}

Let us look specifically at the compressed list data structure. The ziplist layout is: <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

Field	Type	Description
zlbytes	uint32_t	total byte count (including its own 4 bytes)
zltail	uint32_t	offset of the last entry (supports fast pop)
zllen	uint16_t	entry count (set to 2^16-1 when exceeding 2^16-2, needs full traversal to count)
zlend	uint8_t	end marker (0xFF)

Each entry’s layout is: <prevlen> <encoding> <entry-data>

• prevlen: length of the previous entry (dynamically encoded)
• encoding: data type and encoding method
• entry-data: the actual data

The dynamic encoding is used to save storage space, similar in principle to varint in protobuf encoding.

The field and value of the corresponding Hash type are stored in entry-data, with adjacent nodes storing field and value alternately, e.g. [field1,value1,field2,value2,field3,value3]—each field or value is an entry, arranged in sequence.

Core operations:

• hashTypeSet: appends a new element via ziplistPush
• hashTypeGetFromZiplist: uses the ziplistFind function to traverse and look up
• Automatic conversion: when inserting a new element causes the length/value to exceed the threshold, hashTypeConvert is called to convert

The compressed list is more suitable for small data volumes. Each time a new element is inserted, if the ziplist capacity is insufficient, memory is reallocated, the original data is copied into the new space, and the new element is inserted. When the data volume is large, each memory allocation and data copy incurs significant extra overhead, so when the data volume is large, the program considers converting the compressed list to a hash table for storage—which is exactly the dictionary dict introduced earlier, and we will not repeat it here.