Redis中key-value实现原理

实现字典的方法有很多种：

最简单的就是使用链表或数组， 但是这种方式只适用于元素个数不多的情况下；要兼顾高效和简单性，可以使用哈希表；如果追求更为稳定的性能特征， 并且希望高效地实现排序操作的话， 则可以使用更为复杂的平衡树；

在众多可能的实现中， Redis 选择了高效且实现简单的哈希表作为字典的底层实现。

dict 类型的 API ， 它们的作用及相应的算法复杂度：

操作类型操作函数算法复杂度创建创建一个新字典dictAddO(1)添加或更新给定键的值dictFindO(1)在字典中查找给定键的值dictGetRandomKeyO(N)删除根据给定键，删除字典中的键值对dictReleaseO(N)清空并重置（但不释放）字典dictResizeO(N)扩大字典dictRehashO(N)在给定毫秒内，对字典进行rehashdict 类型使用了两个指针分别指向两个哈希表。其中， 0 号哈希表（ht[1]）则只有在程序对 0 号哈希表进行 rehash 时才使用。

接下来两个小节将对哈希表的实现，以及哈希表所使用的哈希算法进行介绍。

哈希表实现¶

字典所使用的哈希表实现由 table 属性是一个数组， 数组的每个元素都是一个指向 dictEntry 都保存着一个键值对， 以及一个指向另一个 next 属性指向另一个 dictEntry 可以通过 dictht dictht 和数个 dict 类型，那么整个字典结构可以表示如下：

在上图的字典示例中， 字典虽然创建了两个哈希表， 但正在使用的只有 0 号哈希表， 这说明字典未进行 rehash 状态。

哈希算法

Redis 目前使用两种不同的哈希算法：

http://code.google.com/p/smhasher/ 。基于 djb 算法实现的一个大小写无关散列算法：具体信息请参考 dictCreate 函数创建并返回一个新字典：

dict

*

d

=

dictCreate(

&

hash_type, NULL);

table 属性分配任何空间：

ht[1]->table 的空间分配将在 rehash 开始时进行；

添加键值对到字典

根据字典所处的状态， 将一个给定的键值对添加到字典可能会引起一系列复杂的操作：

如果字典为未初始化（也即是字典的 0 号哈希表的 字典为空;添加新键值对时发生碰撞处理；添加新键值对时触发了 rehash 操作；

添加新元素到空白字典

当第一次往空字典里添加键值对时， 程序会根据 d->ht[0]->table 分配空间 （在目前的版本中， 4 ）。

以下是字典空白时的样子：

以下是往空白字典添加了第一个键值对之后的样子：

添加新键值对时发生碰撞处理

在哈希表实现中， 当两个不同的键拥有相同的哈希值时， 我们称这两个键发生碰撞（collision）， 而哈希表实现必须想办法对碰撞进行处理。

字典哈希表所使用的碰撞解决方法被称之为key4 和 key4 的哈希值和 0 号索引上发生碰撞。

通过将 key1-value1 两个键值对用链表连接起来， 就可以解决碰撞的问题：

添加新键值对时触发了 rehash 操作

对于使用链地址法来解决碰撞问题的哈希表 size属性）和它所保存的节点的数量（ht[0]）进行 rehash 操作： 在不修改任何键值对的情况下，对哈希表进行扩容， 尽量将比率维持在 1:1 左右。

ht[0] 进行检查， 对于 size 和 ratio =used / size 满足以下任何一个条件的话，rehash 过程就会被激活：

ratio >= 1 ，且变量

ratio

大于变量

dict_force_resize_ratio

的值为

什么时候 BGSAVE 或 copy on write 机制， 程序会会暂时将 dict_can_resize 会重新被设为真。

另一方面， 当字典满足了强制 rehash 的条件时， 即使 BGSAVE 或

创建一个比

ht[1]->table

；将

ht[1]->table

；将原有

ht[1]

替换为新的

设置字典的

0

，标识着 rehash 的开始；为

ht[0]->used

的两倍；

这时的字典是这个样子：

2. Rehash 进行中

在这个阶段， ht[1]->table ， 因为 rehash 是分多次进行的（细节在下一节解释）， 字典的 ht[0] 的哪个索引位置上。

以下是 2 时，字典的样子：

注意除了节点的移动外， 字典的 ht[0]->used 和 ht[0] 迁移到

释放

ht[1] 来代替

ht[1] 成为新的

ht[1] ；将字典的

-1 ，标识 rehash 已停止；

以下是字典 rehash 完毕之后的样子：

对比字典 rehash 之前和 rehash 之后， 新的 _dictRehashStep 和 _dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash ；

_dictRehashStep ，

ht[1]->table 。

在 rehash 开始进行之后（-1）， 每次执行一次添加、查找、删除操作， dictRehashMilliseconds 可以在指定的毫秒数内， 对字典进行 rehash 。

当 Redis 的服务器常规任务执行时， ht[0] 上进行，还需要在 ht[1] 而不是 ht[0] 的节点数量在整个 rehash 过程中都只减不增。

字典的收缩

上面关于 rehash 的章节描述了通过 rehash 对字典进行扩展（expand）的情况， 如果哈希表的可用节点数比已用节点数大很多的话， 那么也可以通过对哈希表进行 rehash 来收缩（shrink）字典。

收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样，它执行以下步骤：

ht[0]->table 小的

ht[0]->table 中的所有键值对迁移到

ht[0] 的数据清空，并将

ht[0] ；

扩展 rehash 和收缩 rehash 执行完全相同的过程， 一个 rehash 是扩展还是收缩字典， 关键在于新分配的 ht[1]->table 比 ht[1]->table 比 数据库》一章的《迭代器实现 —— 对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：

迭代器首先迭代字典的第一个哈希表， 然后，如果 rehash 正在进行的话， 就继续对第二个哈希表进行迭代。当迭代哈希表时， 找到第一个不为空的索引， 然后迭代这个索引上的所有节点。当这个索引迭代完了， 继续查找下一个不为空的索引， 如此循环， 一直到整个哈希表都迭代完为止。

整个迭代过程可以用伪代码表示如下：

def iter_dict(dict): # 迭代

0

号哈希表 iter_table(ht[

0

]

->

table) # 如果正在执行 rehash ，那么也迭代

1

号哈希表

if

dict.is_rehashing(): iter_table(ht[

1

]

->

table)def iter_table(table): # 遍历哈希表上的所有索引

for

index

in

table: # 跳过空索引

if

table[index].empty():

continue

# 遍历索引上的所有节点

for

node

in

table[index]: # 处理节点 do_something_with(node)

字典的迭代器有两种：

安全迭代器：在迭代进行过程中，可以对字典进行修改。不安全迭代器： 在迭代进行过程中，不对字典进行修改。

以下是迭代器的数据结构定义：

/*

* 字典迭代器

*/

typedef

struct

dictIterator { dict

*

d;

//

正在迭代的字典

int

table,

//

正在迭代的哈希表的号码（0 或者 1）

index,

//

正在迭代的哈希表数组的索引

safe;

//

是否安全？

dictEntry

*

entry,

//

当前哈希节点

*

nextEntry;

//

当前哈希节点的后继节点

} dictIterator;

以下函数是这个迭代器的 API ，它们的作用及相关算法复杂度：

函数作用算法复杂度dictGetSafeIterator创建一个安全迭代器。O(1)NULL 。O(1)dictReleaseIterator释放迭代器。O(1)