【死磕 Redis】----- Redis 数据结构：dict

vlambda
2020-08-30

【死磕 Redis】----- Redis 数据结构：dict

字典，又称映射，是一种用于保存键值对的抽象数据结构。在 Redis 中，字典得到了广泛的使用，比如 Redis 的数据库就是使用字典来作为底层实现的

Redis 中的字典有 dict.h/dict 结构表示，如下：

 
   
   
 
  
    
    
  typedefstruct dict {
  
    
    
  // 类型特定函数
  
    
    
  // type里面主要记录了一系列的函数,可以说是规定了一系列的接口
  
    
    
   dictType *type;
  
    
    
  

  
    
    
  // 私有数据
  
    
    
  // privdata保存了需要传递给那些类型特定函数的可选参数
  
    
    
  void*privdata;
  
    
    
  

  
    
    
  //两张哈希表
  
    
    
   dictht ht[2];
  
    
    
  

  
    
    
  //rehash 索引，并没有rehash时，值为 -1
  
    
    
  long rehashidx;
  
    
    
  

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

type：是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。
privdata：保存了需要传给那些类型特定函数的可选参数
ht[2]：表示两张 hash 表（dictht），一般情况下只使用 ht[0]，ht[1] 用于 rehash 时
rehashidx：记录 rehash 目前的进度，如果目前没有在进行 rehash，那么他的值就是 -1

结构如下图：

Redis 字典底层是用哈希表（dictht）实现，dictht 结构如下：

 
   
   
 
  
    
    
  typedefstruct dictht {
  
    
    
  

  
    
    
  // 哈希表数组, 每个元素都是一条链表
  
    
    
   dictEntry **table;
  
    
    
  

  
    
    
  // 哈希表大小
  
    
    
  unsignedlong size;
  
    
    
  

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

  
    
    
  // 该哈希表已有节点的数量
  
    
    
  unsignedlong used;
  
    
    
  } dictht;

table：是一个数组，数组中的每个元素都是一个指向 dictEntry 结构的指针，每个 dictEntry 结构都保存着一个键值对的链表
size：表示哈希表的大小
sizemask：哈希表大小掩码，用于计算索引值，其值总是等于 size-1
used：表示该哈希表已有节点的数量

结构如下图：

【死磕 Redis】----- Redis 数据结构：dict

哈希表的节点用 dictEntry 表示，如下：

 
   
   
 
  
    
    
  typedefstruct dictEntry {
  
    
    
  

  
    
    
  // 键
  
    
    
  void*key;
  
    
    
  

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

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

key：保存键值对中的键
v：保存键值对中的值，可以是一个指针，可以是unit64t的一个整数，也可以是int64t的一个整数

结构如下：

至此，整个字典的结构已经介绍完毕，下图是一个完整的结构图：

当我们需要将一个键值对插入到字典里面，需要先用哈希函数计算 key 的哈希值，然后借助 sizemask 和哈希值得到索引值 index，根据得到的索引值找到对应 dictEntry* 然后插入。插入节点和查找节点的逻辑其实和 HashMap 的 put 和 get 的逻辑没区别，这里就不介绍，下面重点介绍 rehash 过程。

当哈希表的数据越来越多时，链表的长度就会越来越长，这样查询的效率就会降低，所以有必要进行哈希表扩展。而随着元素的过期在不增加元素的前提下会导致哈希表的键值对很少但是 size 比较大，这个时候又会造成内存的浪费，所以有必要进行哈希表收缩。这里扩展、收缩的过程就是 rehash 的过程。

Redis 对字典的哈希表进行 rehash 的过程如下：

为 dict 的 ht[1] 分配内存空间，分配内存空间的大小取决于操作类型以及 ht[0].used:

如果执行的操作是扩展操作，则 ht[1] 的大小为第一个大于等于 $ht[0].used * 2 * 2^n$ 的整数
如果执行的操作是收缩操作，则 ht[1] 的大小为第一个大于等于 $ht[0].used * 2^n$ 的整数

重新计算 ht[0] 中所有的键值对，将其迁移到 ht[1] 指定的位置。需要注意的是，这个过程并不是一次性完成的，而是渐进式完成的。
当 ht[0] 中所有的键值对都迁移到 ht[1] 中去后（ht[0] 为空），则把 ht[0] 释放掉，把ht[1] 设置为 ht[0] ，并重新在 ht[1] 上新建一个空表，为下次 rehash 做准备。

ht[0] 采用渐进式的方式将其中元素迁移到 ht[1] 中的主要原因为了避免对服务器性能造成影响，因为如果 ht[0] 中的元素非常多，几百万，几千万甚至上亿，那么要一次性将这些键值对全部迁移到 ht[1] 中的话，庞大的计算可能会造成服务器在一定时间内停止服务，所以需要采用渐进式、分多次的方式进行 rehash。详细步骤如下：

为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表
在字典中维持一个索引计数器变量 rehashidx，并将其值设置为 0，表示 rehash 过程正式开始
在 rehash 期间，每次对字典执行任意操作时，程序除了执行对应操作之外，还会顺带将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ，操作完后将 rehashidx 的值加一
在 rehash 期间，对字典进行 ht[0].size 次操作之后，rehashidx 的值会增加到 ht[0].size，此时 ht[0] 的所有键值对都已经迁移到 ht[1] 了，程序会将 rehashidx 重新置为-1，以此表示 rehash 完成

这里需要注意的是，在 rehash 的过程中，ht[0] 和 ht[1] 可能同时存在键值对，因此在执行查询操作的时候两个哈希表都得查，而如果是执行插入键值对操作，则直接在 ht[1] 上操作就行，不在 ht[0] 上进行任何的添加操作。

租后再说下 Redis 在什么条件下会对哈希表进行扩展或者收缩呢：