乐趣区

关于redis:redis学习之三字典

jiezi

之前相关联文章：
redis 学习之一 SDS
redis 学习之二链表

一 字典相干的数据结构

哈希表定义：

typedef struct dictht{
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值，总是等于 size -1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
}dictht;

哈希表节点定义：

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

字典定义：

typedef struct dict{
    // 类型函数
    dictType *type;
    // 公有数据
    void *private;
    // 哈希表
    dictht ht[2];
    //rehash 索引，当 rehash 不再进行时值为 -1，// 每次进行 rehash 时，rehashidx 的值就是对应 ht[0]里 dictht 中 dictEntry 数组的索引
    int rehashidx;
}dict;

上面是没有进行 rehash 的字典意识图：

redis 应用 MurmurHash2 算法来计算键的哈希值，应用链地址法解决键抵触。

rehash 与渐进式 rehash

二 扩容与缩容过程
当哈希表保留的键值对数量太多或太少的时候，哈希表会进行扩大或膨胀。rehash 的步骤如下：

  1. 为字典 ht[1]调配空间。
    扩容：ht[1]的大小为第一个大于等于 ht[0].used* 2 的 2 的 n 次幂；
    缩容：ht[1]的大小为第一个大于等于 ht[0].used 的 2 的 n 次幂。
  2. 将保留在 ht[0]中的所有键值对 rehash 到 ht[1]下面，在这个过程中会从新计算键的哈希值与索引值。
  3. 当 ht[0]所有键值都迁徙到了 ht[1]之后，开释 ht[0]，将 ht[1]设置为 ht[0]，并在 ht[1]新创建一个空白哈希表，为下次 rehash 做筹备。

三 扩容与缩容的机会

  1. 服务器没有执行 BGSAVE 或 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 1。
  2. 服务器正在执行 BGSAVE 或 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 5。
  3. 哈希表的负载因子小于 0.1。

四 渐进式 rehash

思考到 redis 服务性能，rehash 并不是一次性集中进行而是分屡次渐进式进行的，步骤如下：

  1. 为 ht[1]调配空间，让字典同时持有 ht[0] ht[1]两个哈希表。
  2. 将下面定义的 dict 构造里的 rehashidx 值设置为 0，示意 rehash 开始进行。
  3. 每次对字典进行增加、删除、查找或更新时，除了进行这些操作外，还会将 ht[0]在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，rehash 的过程上中 rehashidx 值为增 1。
  4. ht[0]里所有键值对 rehash 到 ht[1]后，将 rehashidx 值置为 -1，rehash 完结。

上面是两 rehash 的过程图：

这个还没进行 rehash，所以这里的 rehashidx 值为 -1，留神 ht[0]里 dictEntry 里的值。

这里 rehashidx 值为 3，这是在对 ht[0]里 dictEntry 里第 3 个键值对（k1,v1）进行 rehash。

此文大部分内容都来自于黄健宏《Redis 设计与实现》一书

退出移动版