字典也被称为映射(map),经常作为一种数据结构内置在很多高级编程语言里面。但是Redis所使用的C语言并没有内置这种数据结构,因此Redis构建了自己的字典实现。
字典在Redis中的应用相当广泛,比如Redis的数据库就是使用字典来作为底层实现的,对数据库的增删改查也是构建在对字典的操作之上的。字典还是哈希键的底层实现之一。当一个哈希键包含的键值对比较多,又或者键值对中的元素都是比较长的字符串时,Redis就会使用字典作为哈希键的底层实现。
字典的实现
Redis 的字典使用哈希表作为底层实现, 一个哈希表里面可以有多个哈希表节点, 而每个哈希表节点就保存了字典中的一个键值对。
接下来的三个小节将分别介绍 Redis 的哈希表、哈希表节点、以及字典的实现。
哈希表
Redis 字典所使用的哈希表由 dict.h/dictht
结构定义:
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
table
属性是一个数组, 数组中的每个元素都是一个指向 dict.h/dictEntry
结构的指针, 每个 dictEntry
结构保存着一个键值对。
size
属性记录了哈希表的大小, 也即是 table
数组的大小, 而 used
属性则记录了哈希表目前已有节点(键值对)的数量。
sizemask
属性的值总是等于 size - 1
, 这个属性和哈希值一起决定一个键应该被放到 table
数组的哪个索引上面。
下图是一个大小为4的空哈希表:
哈希表节点
哈希表节点使用 dictEntry
结构表示, 每个 dictEntry
结构都保存着一个键值对:
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
key
属性保存着键值对中的键, 而 v
属性则保存着键值对中的值, 其中键值对的值可以是一个指针, 或者是一个 uint64_t
整数, 又或者是一个 int64_t
整数。
next
属性是指向另一个哈希表节点的指针, 这个指针可以将多个哈希值相同的键值对连接在一次, 以此来解决键冲突(collision)的问题。
下图展示了Redis中如何用拉链法解决键冲突:
字典
Redis 中的字典由 dict.h/dict
结构表示:
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} 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, void *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
ht
属性是一个包含两个项的数组, 数组中的每个项都是一个 dictht
哈希表, 一般情况下, 字典只使用 ht[0]
哈希表, ht[1]
哈希表只会在对 ht[0]
哈希表进行 rehash 时使用。
除了 ht[1]
之外, 另一个和 rehash 有关的属性就是 rehashidx
: 它记录了 rehash 目前的进度, 如果目前没有在进行 rehash , 那么它的值为 -1
。
下图展示了一个没有进行rehash的字典:
哈希算法
当要将一个新的键值对添加到字典里面时, 程序需要先根据键值对的键计算出哈希值和索引值, 然后再根据索引值, 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
Redis 计算哈希值和索引值的方法如下:
# 使用字典设置的哈希函数,计算键 key 的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 属性和哈希值,计算出索引值
# 根据情况不同, ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;
当字典被用作数据库的底层实现, 或者哈希键的底层实现时, Redis 使用 MurmurHash2 算法来计算键的哈希值。
解决键冲突
如在字典的实现一节中所述,在Redis中是用拉链法来解决键冲突问题的。
rehash
随着操作的不断执行, 哈希表保存的键值对会逐渐地增多或者减少, 为了让哈希表的负载因子(load factor)维持在一个合理的范围之内, 当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行 rehash (重新散列)操作来完成, Redis 对字典的哈希表执行 rehash 的步骤如下:
-
为字典的
ht[1]
哈希表分配空间, 这个哈希表的空间大小取决于要执行的操作, 以及ht[0]
当前包含的键值对数量 (也即是ht[0].used
属性的值):- 如果执行的是扩展操作, 那么
ht[1]
的大小为第一个大于等于ht[0].used * 2
的 $2^n$(2
的n
次方幂); - 如果执行的是收缩操作, 那么
ht[1]
的大小为第一个大于等于ht[0].used
的 $2^n$ 。
- 如果执行的是扩展操作, 那么
-
将保存在
ht[0]
中的所有键值对 rehash 到ht[1]
上面: rehash 指的是重新计算键的哈希值和索引值, 然后将键值对放置到ht[1]
哈希表的指定位置上。 -
当
ht[0]
包含的所有键值对都迁移到了ht[1]
之后 (ht[0]
变为空表), 释放ht[0]
, 将ht[1]
设置为ht[0]
, 并在ht[1]
新创建一个空白哈希表, 为下一次 rehash 做准备。
哈希表扩展与收缩的条件:
- 当以下条件中的任意一个被满足时, 程序会自动开始对哈希表执行扩展操作:
- 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于
1
;
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于
5
;其中哈希表的负载因子可以通过公式:
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size
- 当哈希表的负载因子小于
0.1
时, 程序自动开始对哈希表执行收缩操作。
渐进式 rehash
当哈希表里面保存有大量的键值对的时候,如果rehash是一次性、集中式地完成,那么庞大的计算量可能会导致服务器在一段时间内停止服务。因此,Redis中的rehash动作是分多次、渐进式地完成的,称之为渐进式rehash。
以下是哈希表渐进式 rehash 的详细步骤:
- 为
ht[1]
分配空间, 让字典同时持有ht[0]
和ht[1]
两个哈希表。 - 在字典中维持一个索引计数器变量
rehashidx
, 并将它的值设置为0
, 表示 rehash 工作正式开始。 - 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将
ht[0]
哈希表在rehashidx
索引上的所有键值对 rehash 到ht[1]
, 当 rehash 工作完成之后, 程序将rehashidx
属性的值增一。 - 随着字典操作的不断执行, 最终在某个时间点上,
ht[0]
的所有键值对都会被 rehash 至ht[1]
, 这时程序将rehashidx
属性的值设为-1
, 表示 rehash 操作已完成。
渐进式 rehash 的好处在于它采取分而治之的方式, 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上, 从而避免了集中式 rehash 而带来的庞大计算量。
渐进式 rehash 执行期间的哈希表操作:
因为在进行渐进式 rehash 的过程中, 字典会同时使用 ht[0]
和 ht[1]
两个哈希表, 所以在渐进式 rehash 进行期间, 字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行: 比如说, 要在字典里面查找一个键的话, 程序会先在 ht[0]
里面进行查找, 如果没找到的话, 就会继续到 ht[1]
里面进行查找, 诸如此类。
另外, 在渐进式 rehash 执行期间, 新添加到字典的键值对一律会被保存到 ht[1]
里面, 而 ht[0]
则不再进行任何添加操作: 这一措施保证了 ht[0]
包含的键值对数量会只减不增, 并随着 rehash 操作的执行而最终变成空表。
文章评论