Redis教程

Redis中key-value的实现原理

本文主要是介绍Redis中key-value的实现原理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

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

在众多可能的实现中, 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 目前使用两种不同的哈希算法:

  1. http://code.google.com/p/smhasher/ 。
  2. 基于 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 过程就会被激活:

  1. 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 的操作几乎一样,它执行以下步骤:

  1. 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=" color: rgb(34, 34, 34); font-size: 1.1em;">dictReleaseIterator 释放迭代器。 O(1)

小结¶

  • 字典由键值对构成的抽象数据结构。
  • Redis 中的数据库和哈希键都基于字典来实现。
  • Redis 字典的底层实现为哈希表,每个字典使用两个哈希表,一般情况下只使用 0 号哈希表,只有在 rehash 进行时,才会同时使用 0 号和 1 号哈希表。
  • 哈希表使用链地址法来解决键冲突的问题。
  • Rehash 可以用于扩展或收缩哈希表。
  • 对哈希表的 rehash 是分多次、渐进式地进行的。
这篇关于Redis中key-value的实现原理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!