Redis 核心原理与实践 -- 散列类型与字典结构实现原理

关注

发布于: 刚刚

Redis 散列类型可以存储一组无序的键值对，它特别适用于存储一个对象数据。

> HSET fruit name apple price 7.6 origin china3> HGET fruit price"7.6"

复制代码

本文分析 Redis 中散列类型以及其底层数据结构--字典的实现原理。

字典

Redis 通常使用字典结构存储用户散列数据。

字典是 Redis 的重要数据结构。除了散列类型，Redis 数据库也使用了字典结构。

Redis 使用 Hash 表实现字典结构。

分析 Hash 表，我们通常关注以下几个问题：

（1）使用什么 Hash 算法？

（2）Hash 冲突如何解决？

（3）Hash 表如何扩容？

提示：本章代码如无特别说明，均在 dict.h、dict.c 中。

定义

字典中键值对的定义如下：

typedef struct dictEntry {    void *key;    union {        void *val;        uint64_t u64;        int64_t s64;        double d;    } v;    struct dictEntry *next;} dictEntry;

复制代码

key、v：键、值。
next：下一个键值对指针。可见 Redis 字典使用链表法解决 Hash 冲突的问题。

提示：C 语言 union 关键字用于声明共用体，共用体的所有属性共用同一空间，同一时间只能储存其中一个属性值。也就是说，dictEntry.v 可以存放 val、u64、s64、d 中的一个属性值。使用 sizeof 函数计算共用体大小，结果不会小于共用体中最大的成员属性大小。

字典中 Hash 表的定义如下：

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

复制代码

table：Hash 表数组，负责存储数据。
used：记录存储键值对的数量。
size：Hash 表数组长度。

dictht 的结构如图 3-1 所示。

图3-1

图 3-1

字典的定义如下：

typedef struct dict {    dictType *type;    void *privdata;    dictht ht[2];    long rehashidx;     unsigned long iterators;} dict;

复制代码

type：指定操作数据的函数指针。
ht[2]：定义两个 Hash 表用于实现字典扩容机制。通常场景下只使用 ht[0]，而在扩容时，会创建 ht[1]，并在操作数据时中逐步将 ht[0]的数据移到 ht[1]中。
rehashidx：下一次执行扩容单步操作要迁移的 ht[0]Hash 表数组索引，-1 代表当前没有进行扩容操作。
iterators：当前运行的迭代器数量，迭代器用于遍历字典键值对。

dictType 定义了字典中用于操作数据的函数指针，这些函数负责实现数据复制、比较等操作。

typedef struct dictType {    uint64_t (*hashFunction)(const void *key);    void *(*keyDup)(void *privdata, const void *key);    void *(*valDup)(void *privdata, const void *obj);    int (*keyCompare)(void *privdata, const void *key1, const void *key2);    void (*keyDestructor)(void *privdata, void *key);    void (*valDestructor)(void *privdata, void *obj);} dictType;

复制代码

通过 dictType 指定操作数据的函数指针，字典就可以存放不同类型的数据了。但在一个字典中，键、值可以是不同的类型，但键必须类型相同，值也必须类型相同。

Redis 为不同的字典定义了不同的 dictType，如数据库使用的 server.c/dbDictType，散列类型使用的 server.c/setDictType 等。

操作分析

dictAddRaw 函数可以在字典中插入或查找键：

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){    long index;    dictEntry *entry;    dictht *ht;    // [1]    if (dictIsRehashing(d)) _dictRehashStep(d);
    // [2]    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)        return NULL;    // [3]    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];    // [4]    entry = zmalloc(sizeof(*entry));    entry->next = ht->table[index];    ht->table[index] = entry;    ht->used++;
    // [5]    dictSetKey(d, entry, key);    return entry;}

复制代码

参数说明：

existing：如果字典中已存在参数 key，则将对应的 dictEntry 指针赋值给*existing，并返回 null，否则返回创建的 dictEntry。

【1】如果该字典正在扩容，则执行一次扩容单步操作。

【2】计算参数 key 的 Hash 表数组索引，返回-1，代表键已存在，这时 dictAddRaw 函数返回 NULL，代表该键已存在。

【3】如果该字典正在扩容，则将新的 dictEntry 添加到 ht[1]中，否则添加到 ht[0]中。

【4】创建 dictEntry，头插到 Hash 表数组对应位置的链表中。Redis 字典使用链表法解决 Hash 冲突，Hash 表数组的元素都是链表。

【5】将键设置到 dictEntry 中。

dictAddRaw 函数只会插入键，并不插入对应的值。可以使用返回的 dictEntry 插入值：

    entry = dictAddRaw(dict,mykey,NULL);    if (entry != NULL) dictSetSignedIntegerVal(entry,1000);

复制代码

Hash 算法

dictHashKey 宏调用 dictType.hashFunction 函数计算键的 Hash 值：

#define dictHashKey(d, key) (d)->type->hashFunction(key)

复制代码

Redis 中字典基本都使用 SipHash 算法（server.c/dbDictType、server.c/setDictType 等 dictType 的 hashFunction 属性指向的函数都使用了 SipHash 算法）。该算法能有效地防止 Hash 表碰撞攻击，并提供不错的性能。

Hash 算法涉及较多的数学知识，本书并不讨论 Hash 算法的原理及实现，读者可以自行阅读相关代码。

提示：Redis 4.0 之前使用的 Hash 算法是 MurmurHash。即使输入的键是有规律的，该算法计算的结果依然有很好的离散性，并且计算速度非常快。Redis 4.0 开始更换为 SipHash 算法，应该是出于安全的考虑。

计算键的 Hash 值后，还需要计算键的 Hash 表数组索引：

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing){    unsigned long idx, table;    dictEntry *he;    if (existing) *existing = NULL;
    // [1]    if (_dictExpandIfNeeded(d) == DICT_ERR)        return -1;    // [2]    for (table = 0; table <= 1; table++) {        idx = hash & d->ht[table].sizemask;        he = d->ht[table].table[idx];        while(he) {            if (key==he->key || dictCompareKeys(d, key, he->key)) {                if (existing) *existing = he;                return -1;            }            he = he->next;        }        // [3]        if (!dictIsRehashing(d)) break;    }    return idx;}

复制代码

【1】根据需要进行扩容或初始化 Hash 表操作。

【2】遍历 ht[0]、ht[1]，计算 Hash 表数组索引，并判断 Hash 表中是否已存在参数 key。若已存在，则将对应的 dictEntry 赋值给*existing。

【3】如果当前没有进行扩容操作，则计算 ht[0]索引后便退出，不需要计算 ht[1]。

扩容

Redis 使用了一种渐进式扩容方式，这样设计，是因为 Redis 是单线程的。如果在一个操作内将 ht[0]所有数据都迁移到 ht[1]，那么可能会引起线程长期阻塞。所以，Redis 字典扩容是在每次操作数据时都执行一次扩容单步操作，扩容单步操作即将 ht[0].table[rehashidx]的数据迁移到 ht[1]。等到 ht[0]的所有数据都迁移到 ht[1]，便将 ht[0]指向 ht[1]，完成扩容。

_dictExpandIfNeeded 函数用于判断 Hash 表是否需要扩容：

static int _dictExpandIfNeeded(dict *d){    ...
    if (d->ht[0].used >= d->ht[0].size &&        (dict_can_resize ||         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))    {        return dictExpand(d, d->ht[0].used*2);    }    return DICT_OK;}

复制代码

扩容需要满足两个条件：

（1）d->ht[0].used≥d->ht[0].size：Hash 表存储的键值对数量大于或等于 Hash 表数组的长度。

（2）开启了 dict_can_resize 或者负载因子大于 dict_force_resize_ratio。

d->ht[0].used/d->ht[0].size，即 Hash 表存储的键值对数量/Hash 表数组的长度，称之为负载因子。dict_can_resize 默认开启，即负载因子等于 1 就扩容。负载因子等于 1 可能出现比较高的 Hash 冲突率，但这样可以提高 Hash 表的内存使用率。dict_force_resize_ratio 关闭时，必须等到负载因子等于 5 时才强制扩容。用户不能通过配置关闭 dict_force_resize_ratio，该值的开关与 Redis 持久化有关，等我们分析 Redis 持久化时再讨论该值。

dictExpand 函数开始扩容操作：

int dictExpand(dict *d, unsigned long size){    ...    // [1]    dictht n;     unsigned long realsize = _dictNextPower(size);    ...
    // [2]    n.size = realsize;    n.sizemask = realsize-1;    n.table = zcalloc(realsize*sizeof(dictEntry*));    n.used = 0;
    // [3]    if (d->ht[0].table == NULL) {        d->ht[0] = n;        return DICT_OK;    }
    // [4]    d->ht[1] = n;    d->rehashidx = 0;    return DICT_OK;}

复制代码

参数说明：

size：新 Hash 表数组长度。

【1】_dictNextPower 函数会将 size 调整为 2 的 n 次幂。

【2】构建一个新的 Hash 表 dictht。

【3】ht[0].table==NULL，代表字典的 Hash 表数组还没有初始化，将新 dictht 赋值给 ht[0]，现在它就可以存储数据了。这里并不是扩容操作，而是字典第一次使用前的初始化操作。

【4】否则，将新 dictht 赋值给 ht[1]，并将 rehashidx 赋值为 0。rehashidx 代表下一次扩容单步操作要迁移的 ht[0] Hash 表数组索引。

为什么要将 size 调整为 2 的 n 次幂呢？这样是为了 ht[1] Hash 表数组长度是 ht[0] Hash 表数组长度的倍数，有利于 ht[0]的数据均匀地迁移到 ht[1]。

我们看一下键的 Hash 表数组索引计算方法：idx=hash&ht.sizemask，由于sizemask= size-1，计算方法等价于：idx=hash%(ht.size)。

因此，假如 ht[0].size 为 n，ht[1].size 为 2×n，对于 ht[0]上的元素，ht[0].table[k]的数据，要不迁移到 ht[1].table[k]，要不迁移到 ht[1].table[k+n]。这样可以将 ht[0].table 中一个索引位的数据拆分到 ht[1]的两个索引位上。图 3-2 展示了一个简单示例。

图3-2

_dictRehashStep 函数负责执行扩容单步操作，将 ht[0]中一个索引位的数据迁移到 ht[1]中。 dictAddRaw、dictGenericDelete、dictFind、dictGetRandomKey、dictGetSomeKeys 等函数都会调用该函数，从而逐步将数据迁移到新的 Hash 表中。

_dictRehashStep 调用 dictRehash 函数完成扩容单步操作：

int dictRehash(dict *d, int n) {    int empty_visits = n*10;     // [1]    if (!dictIsRehashing(d)) return 0;
    while(n-- && d->ht[0].used != 0) {        dictEntry *de, *nextde;
        assert(d->ht[0].size > (unsigned long)d->rehashidx);        // [2]        while(d->ht[0].table[d->rehashidx] == NULL) {            d->rehashidx++;            if (--empty_visits == 0) return 1;        }        // [3]        de = d->ht[0].table[d->rehashidx];        while(de) {            uint64_t h;
            nextde = de->next;            h = dictHashKey(d, de->key) & d->ht[1].sizemask;            de->next = d->ht[1].table[h];            d->ht[1].table[h] = de;            d->ht[0].used--;            d->ht[1].used++;            de = nextde;        }        d->ht[0].table[d->rehashidx] = NULL;        d->rehashidx++;    }
    // [4]    if (d->ht[0].used == 0) {        zfree(d->ht[0].table);        d->ht[0] = d->ht[1];        _dictReset(&d->ht[1]);        d->rehashidx = -1;        return 0;    }    return 1;}

复制代码

参数说明：

n：本次操作迁移的 Hash 数组索引的数量。

【1】如果字典当前并没有进行扩容，则直接退出函数。

【2】从 rehashidx 开始，找到第一个非空索引位。如果这里查找的的空索引位的数量大于 n×10，则直接返回。

【3】遍历该索引位链表上所有的元素。计算每个元素在 ht[1]的 Hash 表数组中的索引，将元素移动到 ht[1]中。

【4】ht[0].used==0，代表 ht[0]的数据已经全部移到 ht[1]中。释放 ht[0].table，将 ht[0]指针指向 ht[1]，并重置 rehashidx、d->ht[1]，扩容完成。

缩容

执行删除操作后，Redis 会检查字典是否需要缩容，当 Hash 表长度大于 4 且负载因子小于 0.1 时，会执行缩容操作，以节省内存。缩容实际上也是通过 dictExpand 函数完成的，只是函数的第二个参数 size 是缩容后的大小。

dict 常用的函数如表 3-1 所示。

编码

散列类型有 OBJ_ENCODING_HT 和 OBJ_ENCODING_ZIPLIST 两种编码，分别使用 dict、ziplist 结构存储数据（redisObject.ptr 指向 dict、ziplist 结构）。Redis 会优先使用 ziplist 存储散列元素，使用一个 ziplist 节点存储键，后驱节点存放值，查找时需要遍历 ziplist。使用 dict 存储散列元素，字典的键和值都是 sds 类型。散列类型使用 OBJ_ENCODING_ZIPLIST 编码，需满足以下条件：

（1）散列中所有键或值的长度小于或等于 server.hash_max_ziplist_value，该值可通过 hash-max-ziplist-value 配置项调整。

（2）散列中键值对的数量小于 server.hash_max_ziplist_entries，该值可通过 hash-max- ziplist-entries 配置项调整。散列类型的实现代码在 t_hash.c 中，读者可以查看源码了解更多实现细节。

数据库

Redis 是内存数据库，内部定义了数据库对象 server.h/redisDb 负责存储数据，redisDb 也使用了字典结构管理数据。

typedef struct redisDb {    dict *dict;                     dict *expires;                  dict *blocking_keys;            dict *ready_keys;               dict *watched_keys;             int id;                         ...} redisDb;

复制代码

dict：数据库字典，该 redisDb 所有的数据都存储在这里。
expires：过期字典，存储了 Redis 中所有设置了过期时间的键及其对应的过期时间，过期时间是 long long 类型的 UNIX 时间戳。
blocking_keys：处于阻塞状态的键和相应的客户端。
ready_keys：准备好数据后可以解除阻塞状态的键和相应的客户端。
watched_keys：被 watch 命令监控的键和相应客户端。
id：数据库 ID 标识。

Redis 是一个键值对数据库，全称为 Remote Dictionary Server（远程字典服务），它本身就是一个字典服务。redisDb.dict 字典中的键都是 sds，值都是 redisObject。这也是 redisObject 作用之一，它将所有的数据结构都封装为 redisObject 结构，作为 redisDb 字典的值。一个简单的 redisDb 结构如图 3-3 所示。

图3-3

当我们需要操作 Redis 数据时，都需要从 redisDb 中找到该数据。db.c 中定义了 hashTypeLookupWriteOrCreate、lookupKeyReadOrReply 等函数，可以通过键找到 redisDb.dict 中对应的 redisObject，这些函数都是通过调用 dict API 实现的，这里不一一展示，感兴趣的读者可以自行阅读代码。

总结：

Redis 字典使用 SipHash 算法计算 Hash 值，并使用链表法处理 Hash 冲突。
Redis 字典使用渐进式扩容方式，在每次数据操作中都执行一次扩容单步操作，直到扩容完成。
散列类型的编码格式可以为 OBJ_ENCODING_HT、OBJ_ENCODING_ZIPLIST。

本文内容摘自作者新书《Redis 核心原理与实践》，这本书深入地分析了 Redis 常用特性的内部机制与实现方式，大部分内容源自对 Redis 6.0 源码的分析，并从中总结出设计思路、实现原理。通过阅读本书，读者可以快速、轻松地了解 Redis 的内部运行机制。
经过该书编辑同意，我会继续在个人技术公众号（binecy）发布书中部分章节内容，作为书的预览内容，欢迎大家查阅，谢谢。

京东链接

豆瓣链接

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/176ee8036e73290e4f08fb23b】。文章转载请联系作者。