关于redis:Redis核心原理与实践散列类型与字典结构实现原理

41次阅读

共计 8088 个字符,预计需要花费 21 分钟才能阅读完成。

Redis 散列类型能够存储一组无序的键值对,它特地实用于存储一个对象数据。

> HSET fruit name apple price 7.6 origin china
3
> 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 所示。

字典的定义如下:

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 展现了一个简略示例。

_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 所示。

函数 作用
dictAdd 插入键值对
dictReplace 替换或插入键值对
dictDelete 删除键值对
dictFind 查找键值对
dictGetIterator 生成不平安迭代器,能够对字典进行批改
dictGetSafeIterator 生成平安迭代器,不可对字典进行批改
dictResize 字典缩容
dictExpand 字典扩容

编码

散列类型有 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 所示。

当咱们须要操作 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)公布书中局部章节内容,作为书的预览内容,欢送大家查阅,谢谢。

京东链接
豆瓣链接

正文完
 0