Redis设计与实现——字典

3个月前 (05-30) wang 技术杂谈 0评论 已收录 67℃ 浏览数:44

字典又称符号表,是一种用于保存键值对的抽象数据结构。

在字典中,一个键(key)和一个值(value)进行关联,这些关联的键和值就成为键值对。

字典中的每一个键都是独一无二的,程序可以在字典中根据键查找与之关联的值,或者通过键更新值,或者根据键来删除整个键值对。

Redis的数据库的底层实现就是字典,对数据库的增删改查就是建立在字典的基础上。字典也是哈希键的底层实现之一。

Redis字典使用哈希表作为底层实现,一个哈希表里面有多个哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。

1.1哈希表

Redis字典所使用的哈希表由dict.h/dictht结构定义

typedef struct dictht{

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

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

    // 该哈希表已有的节点数量
    unsinged long usedl
}dictht;

tabel属性是一个数组,数组中的每个元素都是一个指向dict.h/dictEntry结构的指针,每个dictEntry结构保存一个键值对。size属性记录了哈希表的大小,也就是tabel数组的长度,used属性记录记录了哈希表目前已有节点的数量。sizemask属性的值总是等于size-1,这个数字和哈希值一起决定一个键应该被放到table数组的哪个索引上面。

1.2哈希表节点

哈希表节点使用dictEntry结构表示,每个dictEntry结构都保存着一个键值对:

typedef struct dictEntry{

    // 键
    void *key;

    // 值
    union{
        void *val;
        uint64_tu64;;
        int64_ts64;
    } v;

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

key属性保存着键值对中的键,v属性保存着键值对中的值,其中键值对中的值可能是一个指针,或者是uint64_t的整数,或者是一个int64_t的整数。
next属性是一个指向另一个哈希表节点的指针,解决键冲突的问题。

1.3字典

Redis的字典由dict.h/dict结构表示:

typedef struct dict{

    // 类型特定函数
    dictType *type;

    // 值
    void *privdata;

    // 哈希表
    dichth ht[2];

    // rehash索引
    // 当rehash不在进行时,值为-1
    int trehashidx;
}dict;

type属性和privdata属性是针对不同结构的键值对,为创建多态字典而设置的:

  • type属性是一个指向dictType结构的指针,每个dictType结构保存了一个用于执行特定类型键值对的函数,Redis为那些用途不同的字典设置了不同类型的特定函数。
  • privdata属性保存了需要传给那些类型特定函数的可选参数。
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 (*keyDestructor) (void *privdata, const void *key;

    // 销毁值得函数
    void (*valDestructor) (void *privdata, const void *obj);
}dictType;

ht属性是一个包含两个项的数组,数组中的每个项都一个dictht哈希表,一般情况下,字典使用ht[0]哈希表,ht[1]哈希表在ht[0]rehash的时候使用。
另一个有关于rehash的属性是rehashidx,它记录了rehash当前的进度,如果目前没有在rehash,那么他的值为-1。

2.1哈希算法

当一个新的键值对添加到字典里面时,程序首先根据键计算出哈希值和索引值,然后根据索引值,将包含新键值对的哈希表节点放到指定索引上去。


Redis计算哈希值和索引值的方法如下:

# 使用字典设置的哈希函数,计算key的哈希值

hash = dict -> type -> hashFunction(key);

#使用哈希表的sizemask属性和哈希值,计算出索引值

#根据情况不同,ht[x]可能为ht[0]或ht[1]

index = hash & dict -> ht[x].sizemask

2.2解决键冲突

当两个或以上数量的键分配到了哈希表数组的同一个索引上面,我们成为发成了冲突。

Redis的哈希表使用链地址法解决冲突,每个哈希表节点都有一个next指针,多个哈希表节点可以通过next指针构成一个单向链表,被分配到同一个索引上的多个节点可以用单向链表连接起来,解决了键冲突的问题。

dictEntry节点组成的链表没有指向链表表尾的指针,所以为了速度考虑,程序总是添加节点到表头位置。

2.3rehash

随着操作的执行,哈希表保存的键值对在逐渐的增多或者减少,为了让哈希表的负载因子维持在一个合理的范围内,当哈希表保存对的键值对数量太多或者太少,程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩可以通过rehash操作来完成,Redis对字典的哈希表执行rehash步骤如下:

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

  • 如果执行的是扩展操作,ht[1]的大小是第一个大于等于ht[0].used*2的2的n次幂
  • 如果执行的是收缩操作,ht[1]的大小是第一个大于等于ht[0].used的2的n次幂

2、将保存在ht[0]中的键值对rehash到ht[1]上面,rehash值得是重新计算键的哈希值和索引值,然后将键值对放置到ht[1]的指定位置

3、当ht[0]所包含的键值对全部迁移到ht[1]的时候,释放ht[0],将ht[1]设置为ht[0],然后在ht[1]处新建一个空白哈希表,为下一次rehash做准备。

2.4哈希表的扩展与收缩

当以下条件任意一个被满足时,程序会自动开始对哈希表执行扩展操作:

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

负载因子 = 哈希表已保存节点数量 / 哈希表大小

当哈希表的负载因子小于0.1时,程序开始自动对哈希表执行收缩操作。

2.5渐进式rehash

扩展和收缩哈希表需要将ht[0]里面所有的键值对rehash到ht[1]里面,但是不是一次性、集中式完成的,而是分多次、渐进式完成的。

这样做的原因是,如果哈希表里保存的键值对是四百万或者更多的键值对,那么一次性的rehash,庞大的计算量会让服务器在一段时间内停止服务器。所以简直是的rehash可以避免对服务器性能造成影响。

以下是rehash的详细步骤:

  1. 为ht[1]分配空间,字典拥有ht[0]和ht[1]两个哈希表
  2. 在字典中维持一个索引计数器变量rehashidx,初始化为0,表示rehash正式开始
  3. 在rehash期间,每次对字典进行增删改查,程序执行特定的操作,同时还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成以后,程序将rehashidx属性加一
  4. 随着字典操作的不断进行,最终全部完成,这时程序将rehashidx属性设置为-1,表示rehash已经完成

在渐进式rehash过程中,字典会同时使用两个哈希表,所以在rehash的过程中,字典的增删改查会在两个哈希表进行,比如在字典中查找一个键,在ht[0]中没有找到,那么程序会继续去ht[1]中查找。

另外,在rehash过程中,新添加到字典的键值对一律被保存到ht[1]中,对ht[0]不进行任何添加操作,保证ht[0]包含的键值对只减不增,最后变成空表。

博主

Just do it. Now or never.

相关推荐

嗨、骚年、快来消灭0回复。