Redis字典实现

前言

        字典又称符号表，关联数组或者映射(map)。是一种保存键值对的抽象数据结构。在字典中一个键和一个值进行关联。这些关联的值被称为键值对。

        字典中每一个键都是独一无二的，没有重复的。我们可以通过键来查找值，更新值或者删除整个键值对等操作。

        字典在Redis中应用广泛，比如Redis数据库的底层就是使用字典来实现的。对数据库的增删查改，该操作也是构建在对字典的操作之上。

        出来用来表示数据库外，字典还是哈希键(说的是Redis的key)的底层实现之一，当一个哈希键包含的哈希键比较多，又或者键值对中的元素都是比较长的字符串时，Redis会使用字典作为哈希键的底层实现。

        由于Redis是用C语言实现的，没有内置字典数据结构，Redis自己构建了字典的实现。

一.字典的实现

        Redis的字典使用作为底层实现，每一个哈希表节点就保存了字典中的一个键值对。

        1.1 哈希表

        Redis字典所使用的哈希表有dict.h/dictht结构来定义：

/* 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;
    //哈希表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;
    //该哈希表已有的节点数
    unsigned long used;
} dictht;

• table: 是一个数组，数值中的每一个元素都是指向dictEntry类型指针，每一个dictEntry中都保存着一个键值对。
• size: 记录了哈希表的大小，也就是table的大小。
• used: 记录了哈希表中已有的节点(键值对)数。
• sizemask: 值总是等于size-1，这个属性和哈希值共同决定了一个键应该被放到table数组的哪一个索引上。

        1.2 哈希表节点

        哈希表的节点使用dictEntry结构表示，每一个dictEntry都保存这一个键值对：

typedef struct dictEntry {
    //键
    void *key;
    //值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //指向下一个节点，形成链表
    struct dictEntry *next;
} dictEntry;

• key: 保存键值对中的键
• v: 保存键值对中的值。可以是一个指针，或者是上面的三种类型
• next: 指向另一个哈希表节点的指针，可以将哈希值相同的节点连接到一起，解决哈希冲突。

        1.3 字典

        Redis的字典由dict.h/dict结构表示：

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];

    //rehash索引
    //当rehash不在进行时，值为-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    //rehash中断标志
    //大于0表示rehash被中断
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

        type和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：

• type: 属性是指向一个dictType结构的指针，每一个dictType结构中保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同类型的特定函数。
• privdata: 属性保存了需要传给那些类型特定函数的可选参数。

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);

    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;

• ht属性: 是一个包含两个项的数组，每一个项都是一个dict哈希表。一般情况下，字典只是用ht[0]哈希表，ht[1]只会在对对ht[0]进行rehash时使用。
• rehashidx: 记录rehash进度，如果没有进行rehash该值为-1。

        1.4 哈希算法

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

//Redis计算哈希值和索引值方法：
//使用字典设置的哈希函数，计算key的哈希值
hash = dict->type->hashFunction(key);

//使用哈希表的sizemask属性和哈希值，计算出索引值
//根据情况不同，ht[x]可以是ht[0]或ht[1]
index = hash & dict->ht[x].sizemask;

        当字典被作为数据库或者哈希见底层实现时，Redis使用的是MurmurHash算法来计算键的哈希值。MurmurHash算法是由Austin Appleby于2008年发明，这种算法有点在于，即使输入的键是有规律的，算法仍然能给出很好的随机分布，而且算法速度也很快。MurmurHash现在也有很多版本。

        1.5 解决键冲突

        当由两个或者两个以上的键被分配到哈希表的同一个索引上，我们称这些键发生了冲突。

        Redis的哈希表使用链地址法来解决键冲突。实际Redis的哈希表是一个哈希桶，哈希表的节点中有一个next指针，冲突的键会以单向链表的方式连接在哈希表的同一索引位置。

        程序会使用头插法，将新节点加到链表中。

        哈希表介绍链接：【精选】哈希表(散列表)介绍_hash表_两片空白的博客-CSDN博客

        1.6 rehash 

        1.6.1 步骤

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

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

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

• 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂。比如：used为3，3*2等于6，第一个大于等于6的2的n次方幂为8，ht[1]的大小为8。
• 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂。

        2. 将保存在ht[0]中的所有键值对rehash到ht[1]上，rehash是指以ht[1]哈希表重新计算键的哈希值和索引值，然后将键值对按照索引放到ht[1]指定位置。

        3. 将ht[0]包含的所有键值对都迁移到ht[1]后，ht[0]就变成了一个空的哈希表。释放ht[0]空间，将ht[1]设置为ht[0]，并在ht[1]新创建一个空的哈希表，为下一次rehash做准备。

        举个例子：

        假设程序要对下面的字典的ht[0]进行扩展操作，那么程序会进行以下操作：

• ht[0].used当前的值为4，4*2=8，正好是2的3次幂，所以程序会将ht[1]哈希表的大小设置为8。下图为分配空间之后的样子：

• 将ht[0]包含的4个键值对都rehash到ht[1]

• 释放ht[0]，将ht[1]设置为ht[0]，然后为ht[1]分配一个空哈希表。至此，对哈希表的扩展执行完毕，程序成功将哈希表的大小从原来的4扩展到8。    

         1.6.2 哈希表的扩展和收缩

        1. 当以下任意一个条件满足时，程序会自动开始对哈希表执行扩展操作：

• redis服务器目前没有进行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
• redis服务器正在进行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。

        哈希表的负载因子公式：load_factor = ht[0].used / ht[0].size

        根据BGSAVE命令或者BGREWRITEAOF命令是否正在执行，服务器执行扩展操作的负载因子不同，这是因为在执行BGSAVE命令或者BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都是通过写时复制技术来优化子进程效率。所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，为了避免子进程存在期间进行哈希表的扩展操作，从而避免不必要的内存写入，最大限度的节约内存。

        2. 当哈希表的负载因子小于0.1时，程序自动开始对哈希表进行收缩操作。

        1.7 渐进式rehash

        1.7.1 步骤

        在字典进行扩展和收缩操作时，需要将哈希表ht[0]上所有键值对rehash到ht[1]上，但是rehash的动作并不是一次性，集中完成的，而是分多次，渐进式完成的。

        原因是，当哈希表中保存的键值对数量很大，那么要一次性的将所有键值对全部rehash到ht[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

         哈希表渐进式rehash的详细步骤：

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

        渐进式rehash好处在于它采用分而治之的方式，将rehash键值对所需要的计算工作均摊到对字典进行查找，插入，删除或更新操作上，从而避免集中式rehash带来的庞大工作量。

        rehash演示：

        1.7.2 渐进式rehash期间对哈希表的操作

         因为在rehash期间，字典中同时存在ht[0]和ht[1]两张哈希表。字典在进行查找，插入，删除和更新操作时会在两个哈希表上进行操作。例如：在字典中查找某一个键时，程序会先在ht[0]中查找，如果没有找到，会继续再ht[1]中查找。

        另外再rehash期间，新增到字典中的键值对一律会保存到ht[1]中，而ht[0]不会进行任何添加操作，这一操作保证了ht[0]包含的键值对的数量只减不增，并且随着rehash操作最终会变成一个空表。

        1.8 API