乐趣区

关于redis:redis学习之三字典

之前相关联文章:
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 设计与实现》一书

退出移动版