Redis 设计与实现——字典

喜欢ヅ旅行 2022-09-03 04:21 170阅读 0赞

# 字典 #

字典中，一个键key和一个值value关联起来，这称为键值对。  
字典中的每个键都是独一无二的， 程序可以在字典中根据键查找与之关联的值， 或者通过键来更新值， 又或者根据键来删除整个键值对， 等等。

## Redis字典的实现 ##

Redis 的字典使用**哈希表**作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。

### 哈希表 ###

typedef struct dictht {
        
        dictEntry **table; // 哈希表数组
        unsigned long size; // 哈希表大小
        unsigned long sizemask; // 哈希表大小掩码
        unsigned long used; // 该哈希表已有节点的数量
    } dictht;

table是一个数组，其中每个元素都是一个指向dictEntry结构的指针。

### 哈希表节点 ###

typedef struct dictEntry {
        
        void *key; // 键
        union {
        
            void *val; 
            uint64_t u64;
            int64_t s64;
            double d;
        } v; // 值
        struct dictEntry *next; // 指向下一个哈希表节点，形成链表，因此是通过链地址法来
    } dictEntry;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]  
我们发现在dictEntry定义中有next指针指向下一个哈希表节点，举个例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 1]

### 字典 ###

typedef struct dict {
        
        dictType *type; // 类型特定函数
        void *privdata; // 私有数据
        dictht ht[2]; // 哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时进行
    
        // rehash索引
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    } dict;

普通状态下的字典如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 2]

## Redis哈希算法 ##

当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

// 使用字典设置的哈希函数，计算键 key 的哈希值
    hash = dict->type->hashFunction(key);
    
    // 使用哈希表的 sizemask 属性和哈希值，计算出索引值
    // 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
    index = hash & dict->ht[x].sizemask;

当字典被用作数据库的底层实现，或哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。

## Redis 解决键冲突 ##

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上时，就发生了冲突。  
Redis 的哈希表使用链地址法（separate chaining）来解决键冲突： 每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。

## Redis rehash ##

随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行 rehash （重新散列）操作来完成。Redis 对字典的哈希表执行 rehash 的步骤如下：

1.  为字典的 ht\[1\] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht\[0\] 当前包含的键值对数量 （也即是ht\[0\].used 属性的值）：

*  如果执行的是扩展操作， 那么 ht\[1\] 的大小为第一个大于等于 ht\[0\].used \* 2 的 2^n （2 的 n 次方幂）；
 *  如果执行的是收缩操作， 那么 ht\[1\] 的大小为第一个大于等于 ht\[0\].used 的 2^n 。

1.  将保存在 ht\[0\] 中的所有键值对 rehash 到 ht\[1\] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht\[1\] 哈希表的指定位置上。
2.  当 ht\[0\] 包含的所有键值对都迁移到了 ht\[1\] 之后 （ht\[0\] 变为空表）， 释放 ht\[0\] ， 将 ht\[1\] 设置为 ht\[0\] ， 并在 ht\[1\] 新创建一个空白哈希表， 为下一次 rehash 做准备。

如果哈希表中保持的键值对数量是非常大的，一次性将这些键值对全部rehash到ht\[1\]的话，则会对服务器性能造成影响。服务器不是一次性将 ht\[0\] 里面的所有键值对全部 rehash 到 ht\[1\] ， 而是分多次、渐进式地将 ht\[0\] 里面的键值对慢慢地 rehash 到 ht\[1\] 。这叫做渐进式rehash。以下是哈希表渐进式 rehash 的详细步骤：

1.  为 ht\[1\] 分配空间， 让字典同时持有 ht\[0\] 和 ht\[1\] 两个哈希表。
2.  在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
3.  在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht\[0\] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht\[1\] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
4.  随着字典操作的不断执行， 最终在某个时间点上， ht\[0\] 的所有键值对都会被 rehash 至 ht\[1\] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]: /images/20220829/7f13f966f11a44068b3a75781478f283.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 1]: /images/20220829/7e5b9a36f43f43b5815537fbf6974dd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 2]: /images/20220829/60792119e8ba4f73b64664ba8a941d01.png