• 周五. 10月 7th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

字典 -《Redis设计与实现》读书笔记

admin

11月 28, 2021

使用场景

  1. 当哈希键包含数量比较多的键值对 或者 键值对中的元素都是比较长的字符串时,使用字典实现哈希键
  2. Redis的数据库,对数据库的curd操作也是构建在对字典的操作之上的

定义

// 哈希表节点
typedef struct dictEntry {
    // 键
    void *key;

    // 值
    union {
        // 可以是指针
        void *val;
        // 可以是uint64_t整数
        uint64_t u64;
        // 可以是int64_t整数
        int64_t s64;
        // 可以是双精度浮点数
        double d;
    } v;

    // 指向下个哈希表节点,形成链表
    // 将多个哈希值相同的键值对连接在一起,解决键冲突的问题
    struct dictEntry *next;
} dictEntry;

// 类型特定函数
typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*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 (*keyDestructor)(void *privdata, void *key);
    
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
    
    // 内存块分配检查函数
    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;

// 哈希表
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码,用于计算索引值,决定键存放索引位置
    // 总等于size-1
    unsigned long sizemask;

    // 哈希表已有节点的数量
    unsigned long used;
} dictht;

// 字典
typedef struct dict {
    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash索引,记录rehash的进度
    // 当rehash不在进行时,值为-1
    // rehash 指的是重新计算键的哈希值和索引值, 然后将键值对放置到 ht[1]哈希表的指定位置上
    long rehashidx;

    // 如果>0,则暂停rehash
    // 如果<0,则表示编码错误
    int16_t pauserehash; 
} dict;

哈希算法

Redis计算哈希值和索引值的步骤

需要将一个键值对k0和v0添加到字典中

  1. 使用字典设置的哈希函数,计算键值对的键k0的哈希值
    hash = dict->type->hasFunction(k0);

  2. 使用哈希表的sizemask属性和哈希值,计算出索引值
    index = hash & dict->ht[x].sizemask;

计算哈希值的函数hasFunction

  1. 默认是siphash算法
  2. 当字典被用作数据库的底层实现 或者 哈希值的底层实现时,Redis使用MurmurHash2算法来计算键的哈希值

解决键冲突

Redis的哈希表使用 链地址法 来解决键冲突,

具体实现就是每个哈希表节点dictEntry都有一个next指针,
相同哈希值 分配到同一个索引上 的 多个节点 用 next指针 构成一个单向链表,

由于dictEntry节点结构没有指向链表表尾的指针,所以总是将新节点添加到链表的表头位置,排在其他已有节点的前面,

重新排列Rehash

Redis对字典的哈希表执行rehash的步骤

  1. 为字典的ht[1]哈希表分配空间,
    这个哈希表的空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量ht[0].used

    如果执行的操作是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n的值,
    比如ht[0].used = 5,ht[0].used*2 = 10 < 2^4 = 16,所以ht[0].size = 16

    如果执行的操作是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2^n的值,
    比如ht[0].used = 5,ht[0].used = 5 < 2^3 = 8,所以ht[0].size = 8

  2. 将保存在ht[0]中的所有键值对渐进式rehash到ht[1]上面(rehash指的是重新计算键的哈希值和索引值),
    然后将键值对放置到ht[1]哈希表的指定位置上

  3. 当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],
    并在ht[1]新创建一个空白哈希表,为下一次rehash做准备

哈希表的扩展与收缩

对哈希表执行扩展操作的条件(满足以下其中一条即可)

  1. 服务器目前没有在执行BGSAVE命令 or BGREWRITEAOF命令,并且哈希表的负载因子 >= 1
  2. 服务器目前正在执行BGSAVE命令 or BGREWRITEAOF命令,并且哈希表的负载因子 >= 5

根据BGSAVE命令 or BGREWRITEAOF命令是否正在执行,服务器执行扩展操作所需的负载因子不相同的原因
在执行BGSAVE命令 or BGREWRITEAOF命令的过程中,Redis需要创建当前服务器进行的子进程,而大多数操作系统都采用写时复制技术来优化子进程的使用效率,所以在子进程存在期间,服务器会提高执行扩展操作所需的负载因子,从而尽可能地避免在子进程存在期间进行哈希表扩展操作,这可以避免不必要的内存写入操作,最大限度地节约内存。

哈希表的负载因子计算公式
负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

对哈希表执行收缩操作的条件
当哈希表的负载因子小于0.1

渐进式Rehash
为了避免rehash对服务器性能造成影响,服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]中的,
而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1]中

渐进式Rehash执行期间的哈希表操作
因为在进行渐进式rehash的过程中,字典会同时使用ht[0]和ht[1]两个哈希表,
所以在渐进式rehash进行期间,字典的删除、查找、更新等操作会在两个哈希表上进行,而新增操作仅针对ht[1]进行,

源码阅读

  1. 文件:src/dict.h 和 src/dict.c
只言片语任我说,提笔句句无需忖。落笔不知寄何人,唯有邀友共斟酌。

发表回复

您的电子邮箱地址不会被公开。