Redis的数据结构(三)：字典

字典在redis的应用

字典在我们平时的编程中是一种非常常见的数据结构，它有着结构简单，查找快速的优点，而在redis中，字典的应用更是十分广泛。redis本身是一个key-value型的nosql数据库，因此数据库本身就是由字典而构成的，数据库的curd都是在此基础上进行的。除此之外，redis的map类型也是由字典这个结构实现的。

字典的实现

c语言不像我们平时用习惯的高级编程语言一样，它没有内置字典结构，因此redis自身实现了一套字典结构，下面我们来简单分析下实现字典的几个结构体。

1. 哈希表

typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

这里要注意的就是，table字段是一个可以保存多个dictEntry的数组，也就是一个哈希表里面会有多个哈希的实体类，也可以成为哈希节点。

2. 哈希节点

typedef struct dictEntry {
    
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

v字段表示哈希节点的值，使用union结构体表示这个值可以使void指针类型，也可以是uint64_t或者int64_t整数，这里我猜想是为了其他操作系统而做的一个兼容吧。尽管大部分哈希函数具有很强的防碰撞性，但是也会遇到哈希值相同的键值对，这个时候next字段就发挥作用了，它会把相同哈希值的键值对整理成一个单向链表结构来方便查找。

3. 字典

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

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

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

type字段提供了一组类型的操作函数：

typedef struct dictType {

    // 计算哈希值的函数
    unsigned int (*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;

这组函数可以让不同类型的键值对能够使用不同的方法进行复制、对比等操作，真正让redis实现了多态字典。

我们还可以见到，字典结构体内部包含了两个哈希表的数组，为什么需要两个哈希表呢？这就引入了一个rehash的概念了。

字典的rehash

当哈希表中的哈希节点，也就是键值对的数量越来越多或者越来越少的时候，原来分配的哈希表将会进行伸缩，redis会维护一个哈希表的负载因子，其中计算方式是：负载因子=哈希表的使用数量/哈希表的长度

当符合以下两个条件任何一个的时候就会进行reshash操作:

服务器没有执行BGSAVE或者BGREWRITEAOF命令，并且这个负载因子大于等于1的时候。
服务器在执行BGSAVE或者BGREWRITEAOF命令，并且负载因子超过5。

为什么在执行备份命令的时候，负载因子要比没有执行备份的时候大呢？原因就是redis在执行BGSAVE之类的备份命令时候，会fork一个子进程进行备份，而目前大部分操作系统都会采用copy on write也就是写时复制的技术，如果此时过多的去进行rehash会导致内存占用过多。

rehash的步骤：

为哈希表数组ht[1]进行空间分配。分配的原则是：扩容则分配ht[0].used*2，收缩则分配ht[0]*used/2。
重新计算ht[0]中的所有键值对，然后逐步迁移到ht[1]中。
当ht[0]所有键值对都迁移完毕之后，释放ht[0]所占空间，把ht[1]取代到ht[0]的位置，并且新创建一个空白的哈希表，也就是新的ht[1]，整个rehash步骤到此结束。

渐进式rehash

上面我们简单介绍了rehash的步骤，但是如果真是那么简单去实现的话，其实是有缺陷的。试想想，如果哈希表中拥有大量的键值对，一次性去进行rehash把大量的键值对进行迁移，势必会导致性能低下，并且影响redis的读写性能甚至导致服务被停止。因此，rehash是渐进的，并且是不能影响正常的redis读写服务的。以下就是渐进式rehash的一个过程：

为ht[1]分配空间，分配的规则上面已经写了，这里就不再重复描述。
此时字典会拥有ht[0]和ht[1]两个哈希表，字段rehashidx就能产生作用了。rehashidx默认值是-1，当它变为0说明rehash正式开始。
rehash开始，redis会把ht[0]中rehashidx索引中的键值对进行rehash到ht[1]，每次rehash完成都会让rehashidx递增1，然后重复这个过程。
在这个过程中，我们难免会对redis进行增删改查的操作，这个时候同时拥有两个哈希表的作用就发挥出来了。对于查找、删除、修改操作，redis会现在ht[0]中进行，如果找不到才会到ht[1]进行对应操作，而增加这些操作则会直接在ht[1]中进行，主要是让ht[0]只减不增，这样到了某个时刻，ht[0]的所有键值对一定会全部迁移到ht[1]。

领悟

redis这个字典的结构实现清晰明了，特别是其中的rehash机制很值得我去学习，这个对于一些数据迁移并且不能影响正常服务的编程实现非常有借鉴意义。

文章参考自：<<Redis设计与实现>> 第二版