Redis中key-value实现

2023-11-07

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

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

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

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

操作类型	操作	函数	算法复杂度
创建	创建一个新字典	`dictAdd`	O(1)
添加或更新给定键的值	`dictFind`	O(1)
在字典中查找给定键的值	`dictGetRandomKey`	O(N)
删除	根据给定键，删除字典中的键值对	`dictRelease`	O(N)
清空并重置（但不释放）字典	`dictResize`	O(N)
扩大字典	`dictRehash`	O(N)
在给定毫秒内，对字典进行rehash	`dict` 类型使用了两个指针分别指向两个哈希表。其中， 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)
<tt literal"="" style="background-color: transparent; color: rgb(34, 34, 34); font-size: 1.1em;">dictReleaseIterator	释放迭代器。	O(1)

小结¶

字典由键值对构成的抽象数据结构。
Redis 中的数据库和哈希键都基于字典来实现。
Redis 字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用 0 号哈希表，只有在 rehash 进行时，才会同时使用 0 号和 1 号哈希表。
哈希表使用链地址法来解决键冲突的问题。
Rehash 可以用于扩展或收缩哈希表。
对哈希表的 rehash 是分多次、渐进式地进行的。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

NoSQL