Redis数据结构之字典

不念不忘少年蓝@ 2022-11-05 11:48 168阅读 0赞

# 一：字典表的实现 #

*  字典是一种用来保存键值对的抽象数据结构。
 *  Redis字典的底层是使用哈希表实现的，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

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

一个空的哈希表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

*  哈希表节点由一个键值对和一个指向下一个键值对的指针域构成

typedef struct dictEntry {
        //键
        void *key;
        //值
        void *val;
        //指向下一个哈希表节点，形成链表
        struct dictEntry *next;
    } dictEntry;

\*next属性是用来解决哈希冲突问题的。

如K1和K2的hash冲突了，就可以通过链地址法进行解决哈希冲突。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

## 2. 字典表 ##

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

typedef struct dict {
        //类型特定函数
        dictType *type;
        //私有数据
        void *privdata;
        //哈希表
        dictht ht[2];
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        unsigned long iterators; /* number of iterators currently running */
    } dict;

type属性是一个指向dictType结构的指针，每个dictType结构保存了一些针对不同数据类型键值对处理的函数。

privdata属性则保存了需要传给特定函数的可选参数。

ht\[2\]是表示两个哈希表，其中H\[0\]是用来保存数据的，H\[1\]是用来做rehash算法的。

*  dictType结构如下：

typedef struct dictType {
        //计算hash值函数
        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;

## 3. rehash的实现 ##

随着redis的操作不断进行，hash表中存储的数据不断增加或者减少，为了让hash表的负载因子维持在一个合理的范围，则需要对hash表的size进行扩展或者收缩。

### 3.1. 哈希表扩张或者收缩的条件 ###

3.1.1. 哈希表扩张的条件

*  当服务器目前没有执行BGSAVE或者BGWRITEAOF命令，并且哈希表的负载因子大于等于1
 *  当服务器目前正在执行BGSAVE或者BGWRITEAOF命令，并且哈希表的负载因子大于等于5

负载因子 = 哈希表已保存的节点数量/哈希表大小

//能够rehash扩容的负载因子
    static int dict_can_resize = 1;
    //强制rehash扩容的负载因子
    static unsigned int dict_force_resize_ratio = 5;
    
    /* Expand the hash table if needed */
    static int _dictExpandIfNeeded(dict *d)
    {
        /* Incremental rehashing already in progress. Return. */
        if (dictIsRehashing(d)) return DICT_OK;
    
        /* If the hash table is empty expand it to the initial size. */
        if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    
        /* If we reached the 1:1 ratio, and we are allowed to resize the hash
         * table (global setting) or we should avoid it but the ratio between
         * elements/buckets is over the "safe" threshold, we resize doubling
         * the number of buckets. */
        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;
    }

在执行BGSAVE或者BGWRITEAOF命令，Redis需要创建当前进程的字进程，而大多数操作系统都是采用写时复制（copy-on-write）来优化子进程的使用效率，所以在子进程存在的时候会避免rehash操作，这样可以避免不必要的内存写入操作，最大限度节约内存。

*  ### **写时复制** ###

在不使用写时复制技术的情况下，我们为进程创建一个子进程时会导致子进程拷贝父进程的数据段，堆，栈，仅有正文段不会被拷贝。
    
    而在使用写时复制技术的情况下，我们为进程创建一个子进程时不会拷贝任何数据，此时父进程和自己成共享同一份数据，仅当父进程或者自己成需要对这份数据进行写入时，才为子进程分配相应的物理空间。

3.1.2. 哈希表收缩的条件

*  当哈希表的负载因子小于0.1的时候，程序会自动对哈希表进行收缩操作。

### 3.2 rehash是渐进式的 ###

哈希表的rehash不是一次性就将H\[0\]的数据rehash到H\[1\]的，而是分多次，渐进式的。所以当哈希表再rehash的时候可能H\[0\]和H\[1\]都有数据。

一次rehash的操作：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 7][]

判断一个字典表是否已经进行rehash操作，直接看字典表的rehashidx的值，如果值为-1的时候，则表示为进行rehash，每完成一次rehash，rehashidx的值加一，并将H\[0\]的键值rehash给H\[1\]，当最后一次rehash完成并且H\[0\]的数据全部rehash到H\[1\]的时候，则将H\[1\]置为H\[0\]，将原来的H\[0\]置为H\[1\]，rehashidx的值也设置为-1。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/d94adc9e2d0a42fb82a90567ac3c1f4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221023/bbf3fedac74845f29fd62bd2829c01a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2]: /images/20221023/b8cb7effbe574968bd9ca145e6340946.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 3]: /images/20221023/d1f4b7bdf0bd4d9296790e3d7a594616.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 4]: /images/20221023/19c85050e99143e88a332f30fa16dcd6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 5]: /images/20221023/5b03e91408d3423c845aa762c04ffbac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 6]: /images/20221023/3a0a1f95bc8f4af09a2e60985ffed9d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 7]: /images/20221023/36754fa335cc41ed8df34c476c414c8f.png