Redis中的字典

简介

字典是一种在 Redis 中高频使用的用于保存键值对的抽象数据结构,在 Java 中常用的有 HasmMap 等。

由于字典中键的唯一性,所以在 Redis 中得到了广泛的应用。

实现

Redis 中的字典是基于哈希表 (dictht, dict hash table)实现的,哈希表中的每个节点保存一个键值对。哈希表的结构体定义如下:

typedef struct dictht {
  // 哈希表数组
  dictEntry **table;
  // 哈希表大小
  unsigned long size;
  // 哈希表大小掩码,用于计算索引值 size - 1,用来计算键值对放在哪个索引上
  unsigned long sizemask;
  // 哈希表已有节点的数量
  unsigned long used;
} dictht;

哈希表节点 dictEntry 的结构则如下所示:

typedef struct dictEntry {
  // 键
  void *key;
  // 值
  union {
    void *val;
    uint64_t u64;
    int64_t s64;
  }v;
  // 指向下个哈希表节点
  struct dictEntry *next;
} dictEntry;

dictEntry 中的值有些特别,它表示其值有可能是一个指针或者是一个 uint64_t 整数,或者是一个 int64_t 整数。

因为存在 next 属性,很显然它是使用链地址法解决的哈希键冲突。

接下来我们看一下字典(dict)的定义:

typedef struct dict {
  // 类型特定函数
  dictType *type;
  // 私有数据
  void *privdata;
  // 哈希表
  dictht ht[2];
  // rehash 索引 当不在进行 rehash 的时候,值为-1
  int trehashids; 
} dict;

属性 type 是一个指向 dictType 结构体的指针,每个 dictType 保存了一些用于操作特定类型键值对的函数。

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 (*valDestructor)(void *privdata, void *obj);
} dictType;

ht 数组表示存储两个哈希表,平常情况下只使用 ht[0] ,只有在 rehash 时才会使用到 h[1]trehashids

字典的结构就是,一个字典中有两个哈希表,平时只用一个哈希表。另一个哈希表在 rehash 的时候使用。每个哈希表中存在一个节点数组,节点则用于存放键值对。

新增键值对

新增键值对就意味着需要计算键的哈希值,从而得出索引值。根据索引值将键值对的哈希节点放到哈希表的指定位置上。计算哈希值使用的是字典结构体中的 type 中的函数,即 hash = dict->type->hashFunction(key) 。计算索引值则是 index = hash & dict->ht[x].sizemask ,x 取决于当前使用的是ht[1]还是ht[2]。

不过,总会有不同的键对应相同的索引值,产生冲突。Redis 中使用了常用的“链地址法”来解决这个问题,当出现冲突时就把新节点放到表头的位置。

Rehash

随着字典中键值对数量的不断变化,为了保证哈希表的空间利用率以及效率,在哈希表过大或者过小是要对哈希表大小进行调整。如果过小,则会不断发生键冲突导致效率低下,如果过大则会浪费存储空间。所以,经过不断调整可以使其维持在一个合理的范围。

步骤

  1. ht[1] 分配空间,大小取决于是扩大哈希表还是缩小哈希表。如果扩大,其大小为第一个大于等于 ht[0].used * 2 且同时为2的n次方幂 的值。如果缩小,其大小为第一个大于等于 ht[0].used 其同时为 2的n次方幂 的值。
  2. 将保存在 ht[0] 中所有的键值对重新计算哈希值和索引值后,存放在 ht[1] 中。
  3. 当迁移完所有的键值之后,释放原 ht[0] 的空间,将原 h[1] 改为 h0, 并在 ht[1] 新创建一个空白哈希表。

那么何时扩展哈希表大小呢? 一是当没有在执行 BGSAVE 或者 BGREWRITEAOF 命令时,并且哈希表的负载因子大于等于1时。 二是当在执行这俩命令,但是负载因子大于等于5时(节约内存,上述两命令消耗内存)。

负载因子计算公式为:负载因子 = 哈希表保存节点数量/哈希表大小

那么何时缩小哈希表大小呢? 当哈希表负载因子小于 0.1 时则会进行缩小。

渐进式 Rehash

其实对于上述步骤 2 ,普通人觉得这不就是把键值对重新分配一下吗?但是如果此时存在百万、千万甚至亿级的键值对时,恐怕就是不是一眨眼的功夫就可以完成的了。如果非得一次性完成,那么可能会导致服务器的不可用。所以为了解决这个问题,Redis 采用了慢慢来的办法渐进式 Rehash

其主要步骤与前面的有些相似,只不过在渐进式Rehash中使用到了 dict->trehashids 值来记录当前rehash到了哪个索引。在 Rehash 期间,可以对字典正常进行增加、删除、查找和更新。然后同时也会将 trehashids 上记录的索引值上的节点迁移到 h[1] 上。并且所有的新增节点都会放到 h[1]中,这样就会导致 h[0] 中的节点越来越少,最终完成 rehash。其它的操作则会在两个表上进行。

发布者

常轩

常轩

总要做点什么吧!

发表评论

电子邮件地址不会被公开。 必填项已用*标注