Redis - 链表与字典的实现

Love The Way You Lie 2022-12-19 06:03 167阅读 0赞

### 文章目录 ###

*  1. Redis链表的结构
 *  2. Redis字典的结构
 *   *  hash表
     *  哈希表结点
     *  字典
     *  hash函数
     *  rehash（渐进式）
 *  3. 字典的遍历 \*
 *   *  3.1 迭代器遍历(全遍历)
     *   *  普通迭代器
     *  安全迭代器
     *  3.2 间断遍历

> Redis为单进程单线程模式

# 1. Redis链表的结构 #

基础是双向链表

typedef struct listNode{ 
    struct listNode *prev;
    struct listNode *next;
    void* value;
    }listNode;

外层还有一层封装

typedef struct list{ 
    
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup)(void *ptr);//结点复制函数
    void *(*free)(void *ptr);//结点释放函数
    int (*match)(void *ptr,void *key);//结点值比对函数
    }list;

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

有一定数据结构基础的这些都不难看懂，list是对一个底层是双向链表的结构的封装；因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表。

# 2. Redis字典的结构 #

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。  
这是一种非常常用的数据结构:

set str "redis"

## hash表 ##

其C语言代码如下：

typedef struct dictht{ 
    dictEntry **table;//hash表数组
    unsigned long size;//hash表大小
    unsigned long sizeMask;//大小掩码，总时等于size-1
    unsigned long used;//已有节点数
    }dictht;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 1]

## 哈希表结点 ##

typedef struct dictEntry{ 
    //键
    void *key;
    //值
    union { 
    void *val; //可以指向不同类型的值
    uint64_tu64;
    int64_ts64;
    }v;
    //hash表下一个结点的指针
    struct dictEntry *next;
    }dictEntry;

key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64\_t整数，又或者是一个int64\_t整数。next属性是指向另一个哈希表节点的指针，**这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 2]

## 字典 ##

typedef struct dict{ 
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //hash表
    dictht ht[2];
    //rehash索引，rehash不存在 值为1
    int rehashidx;
    }dict;

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

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。  
privdata属性则保存了需要传给那些类型特定函数的可选参数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 3]

## hash函数 ##

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

//首先拿到key 计算出key的hash值
    hash = dict -> type -> hashFunction(key);
    //使用hashht的sizeMask属性和hash值计算出要放入的位置
    //根据情况不同放入ht[0]还是ht[1] 后面会说
    index = hash& dict->ht[x].sizemask;

## rehash（渐进式） ##

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

**即新添加的键值对都往新的Hash表中存储；而修改、删除、查找操作需要在ht\[0\]、ht\[1\]中进行检查，然后再决定去对哪个Hash表操作。**

例如：**ht\[0\]包含的所有键值对都迁移到了ht\[1\]之后（ht\[0\]变为空表），释放ht\[0\]，将ht\[1\]设置为ht\[0\]，并在ht\[1\]新创建一个空白哈希表，为下一次rehash做准备。**

> 其次：  
> 如果执行的是扩展操作，那么ht\[1\]的大小为第一个大于等于ht\[0\].used\*2的2的n次方幂  
> 如果执行的是收缩操作，那么ht\[1\]的大小为第一个大于等于ht\[0\].used的2的n次方幂  
> 其次扩容时机:  
> 1）服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。  
> 2）服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。  
> 负载因子=hash表已保存节点数/hash表大小

此外，当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。  
这个渐变式的过程就需要用到索引计数器变量rehashidx，在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht\[0\]哈希表在rehashidx索引上的所有键值对rehash到ht\[1\]，当rehash工作完成之后，程序将rehashidx属性的值增一。在结束时，将rehashidx置为-1代表完成rehash过程；

# 3. 字典的遍历 \* #

遍历数据库的原则为：① 不重复出现数据；② 不遗漏任何数据。  
遍历Redis整个数据库主要有两种方式：全遍历（例如keys命令）、间断遍历（hscan命令）：

*  全遍历：一次命令执行就遍历完整个数据库。
 *  间断遍历：每次命令执行只取部分数据，分多次遍历。

## 3.1 迭代器遍历(全遍历) ##

字典迭代器主要用于迭代字典这个数据结构中的数据;

> 其中会存在问题，既然是遍历，那么在扩容过程中可能会导致一个元素被遍历多次。

1）普通迭代器，只遍历数据；  
2）安全迭代器，遍历的同时删除数据。

typedef struct dictIterator{ 
    dict *d;//迭代的字典
    int index;//当前迭代到hash表中的索引
    int table,safe;//safe表示是否使用安全迭代器，table 代表ht[0]还是ht[1]
    dictEntry *entry,*nextEntry;//当前结点，下一个结点
    long long fingerprint;//字典未改变该值不改变，改变则跟着改变
    }

### 普通迭代器 ###

普通迭代器迭代字典中数据时，会对迭代器中fingerprint字段的值作严格的校验，来保证迭代过程中字典结构不发生任何变化，确保读取出的数据不出现重复。

即迭代过程中字典数据的修改、添加、删除、查找等操作都不能进行，只能调用dictNext函数迭代整个字典，否则就报异常，由此来保证迭代器取出数据的准确性。

例如sort命令。sort命令主要作用是对给定列表、集合、有序集合的元素进行排序，如果给定的是有序集合，其成员名存储用的是字典，分值存储用的是跳跃表，则执行sort命令读取数据的时候会用到迭代器来遍历整个字典。

所以说，普通迭代器具有很大的局限性；

## 安全迭代器 ##

安全迭代器确保读取数据的准确性，不是通过限制字典的部分操作来实现的，而是通过限制rehash的进行来确保数据的准确性，因此迭代过程中可以对字典进行增删改查等操作。  
原理上很简单，如果当前字典有安全迭代器运行，**则不进行渐进式rehash操作，rehash操作暂停**，字典中数据就不会被重复遍历，由此确保了读取数据的准确性。

当Redis执行部分命令时会使用安全迭代器迭代字典数据，例如keys命令。keys命令主要作用是通过模式匹配，返回给定模式的所有key列表，遇到过期的键则会进行删除操作。Redis数据键值对都存储在字典中，因此keys命令会通过安全迭代器来遍历整个字典。

## 3.2 间断遍历 ##

执行keys命令进行一次数据库全遍历，耗时肯定不短，会造成短暂的Redis不可用。  
而dictScan是“间断遍历”中的一种实现，主要在迭代字典中数据时使用，例如hscan命令迭代整个数据库中的key，以及zscan命令迭代有序集合所有成员与值时，都是通过dictScan函数来实现的字典遍历。dictScan遍历字典过程中是可以进行rehash操作的，通过算法来保证所有的数据能被遍历到。

具体细节请看书《Redis5 设计与源码分析》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/71bd3688c71f4b61b1796e3cd596e3ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/9d3a79e7bf8f44c19ea4488844d17e26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020110516274787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201105163610234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70#pic_center