Redis设计与实现之字典
目录
Note:什么时候 dict_can_resize 会为假？
一、字典
字典(dictionary)，又名映射(map)或关联数组(associative array)， 它是一种抽象数据结 构，由一集键值对(key-value pairs)组成，各个键值对的键各不相同，程序可以将新的键值对 添加到字典中，或者基于键进行查找、更新或删除等操作。
本章先对字典在 Redis 中的应用进行介绍，接着讲解字典的具体实现方式，以及这个字典实现 要解决的问题，最后，以对字典迭代器的介绍作为本章的结束。
1、 字典的应用
字典在 Redis 中的应用广泛，使用频率可以说和 SDS 以及双端链表不相上下，基本上各个功能模块都有用到字典的地方。 其中，字典的主要用途有以下两个:
1. 实现数据库键空间(key space);
2.用作 Hash类型键的其中一种底层实现；
以下两个小节分别介绍这两种用途。
实现数据库键空间
Redis是一个键值对数据库，数据库中的键值对就由字典保存：每个数据库都有一个与之相对应的字典，这个字典被称之为键空间（ key space ） 。
当用户添加一个键值对到数据库时（不论键值对是什么类型） ，程序就将该键值对添加到键空间；当用户从数据库中删除一个键值对时，程序就会将这个键值对从键空间中删除；等等。
举个例子，执行 FLUSHDB 可以清空键空间上的所有键值对数据：
redis>FLUSHDB
OK执行 DBSIZE 则返回键空间上现有的键值对：
redis>DBSIZE
(integer) 0还可以用 SET设置一个字符串键到键空间，并用 GET从键空间中取出该字符串键的值：
redis>SET number 10086
OK
redis>GET number
"10086"
redis>DBSIZE
(integer) 1后面的《 数据库》一章会对键空间以及数据库的实现作详细的介绍，到时我们将看到，大部分针对数据库的命令，比如 DBSIZE 、FLUSHDB 、:ref: RANDOMKEY ，等等，都是构建于对字典的操作之上的；而那些创建、更新、删除和查找键值对的命令，也无一例外地需要在键空间上进行操作。
用作Hash类型键的其中一种底层实现
Redis的 Hash类型键使用以下两种数据结构作为底层实现 :
1.字典；
2.压缩列表 ；
因为压缩列表比字典更节省内存，所以程序在创建新 Hash键时，默认使用压缩列表作为底层实现，当有需要时，程序才会将底层实现从压缩列表转换到字典。
当用户操作一个 Hash键时，键值在底层就可能是一个哈希表：
redis>HSET book name "The design and implementation of Redis "
(integer) 1
redis>HSET book type "source code analysis "
(integer) 1
redis>HSET book release -date"2013.3.8 "
(integer) 1
redis>HGETALL book
1)"name"
2)"The design and implementation of Redis "
3)"type"
4)"source code analysis "
5)"release-date "
6)"2013.3.8 "《哈希表》章节给出了关于哈希类型键的更多信息，并介绍了压缩列表和字典之间的转换条件。
介绍完了字典的用途，现在让我们来看看字典数据结构的定义。
2、字典的实现
实现字典的方法有很多种：
?最简单的就是使用链表或数组，但是这种方式只适用于元素个数不多的情况下；
?要兼顾高效和简单性，可以使用哈希表；
?如果追求更为稳定的性能特征，并且希望高效地实现排序操作的话，则可以使用更为复杂的平衡树；
在众多可能的实现中， Redis选择了高效且实现简单的哈希表作为字典的底层实现。
dict.h/dict 给出了这个字典的定义：
/*
*字典
*
*每个字典使用两个哈希表，用于实现渐进式 rehash
*/
typedef structdict {
//特定于类型的处理函数
dictType *type;
//类型处理函数的私有数据
void*privdata;
//哈希表（ 2个）
dictht ht[ 2];
//记录rehash进度的标志，值为 -1表示rehash未进行
intrehashidx;
//当前正在运作的安全迭代器数量
intiterators;
} dict;以下是用于处理 dict类型的 API，它们的作用及相应的算法复杂度：
注意dict类型使用了两个指针分别指向两个哈希表。
其中， 0号哈希表（ ht[0]）是字典主要使用的哈希表，而 1号哈希表（ ht[1]）则只有在程序对 0号哈希表进行 rehash时才使用。
接下来两个小节将对哈希表的实现，以及哈希表所使用的哈希算法进行介绍。
哈希表实现
字典所使用的哈希表实现由 dict.h/dictht 类型定义：
/*
*哈希表
*/
typedef structdictht {
//哈希表节点指针数组（俗称桶， bucket）
dictEntry **table;
//指针数组的大小
unsigned longsize;
//指针数组的长度掩码，用于计算索引值
unsigned longsizemask;
//哈希表现有的节点数量
unsigned longused;
} dictht;table属性是一个数组，数组的每个元素都是一个指向 dictEntry 结构的指针。
每个dictEntry 都保存着一个键值对，以及一个指向另一个 dictEntry 结构的指针：
/*
*哈希表节点
*/
typedef structdictEntry {
//键
void*key;
//值
union{
void*val;
uint64_t u64;
int64_t s64;
} v;
//链往后继节点
struct dictEntry *next;
} dictEntry;next属性指向另一个 dictEntry 结构，多个 dictEntry 可以通过 next指针串连成链表，从这里可以看出， dictht使用链地址法来处理键碰撞 ：当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。
下图展示了一个由 dictht和数个dictEntry 组成的哈希表例子：
如果再加上之前列出的 dict类型，那么整个字典结构可以表示如下：
在上图的字典示例中，字典虽然创建了两个哈希表，但正在使用的只有 0号哈希表，这说明字典未进行 rehash状态。
哈希算法
Redis目前使用两种不同的哈希算法：
1. MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好，具体信息请参考 Mur-murHash 的主页： http://code.google.com/p/smhasher/ 。
2.基 于 djb算 法 实 现 的 一 个 大 小 写 无 关 散 列 算 法： 具 体 信 息 请 参 考http://www.cse.yorku.ca/~oz/hash.html 。
使用哪种算法取决于具体应用所处理的数据：
?命令表以及 Lua脚本缓存都用到了算法 2。
?算法 1的应用则更加广泛：数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。
3、创建新字典
dictCreate 函数创建并返回一个新字典：
dict*d=dictCreate( &hash_type, NULL);d的值可以用图片表示如下：
新创建的两个哈希表都没有为 table属性分配任何空间：
?ht[0]->table 的空间分配将在第一次往字典添加键值对时进行；
?ht[1]->table 的空间分配将在 rehash开始时进行；
4、添加键值对到字典
根据字典所处的状态，将一个给定的键值对添加到字典可能会引起一系列复杂的操作：
?如果字典为未初始化（也即是字典的 0号哈希表的 table属性为空） ，那么程序需要对 0号哈希表进行初始化；
?如果在插入时发生了键碰撞，那么程序需要处理碰撞；
?如果插入新元素使得字典满足了 rehash条件，那么需要启动相应的 rehash程序；当程序处理完以上三种情况之后，新的键值对才会被真正地添加到字典上。
整个添加流程可以用下图表示：
在接下来的三节中，我们将分别看到添加操作如何在以下三种情况中执行：
1.字典为空 ;
2.添加新键值对时发生碰撞处理；
3.添加新键值对时触发了 rehash操作；
5、添加新元素到空白字典
当第一次往空字典里添加键值对时，程序会根据 dict.h/DICT_HT_INITIAL_SIZE 里指定的大小为d->ht[0]->table 分配空间（在目前的版本中， DICT_HT_INITIAL_SIZE 的值为4） 。
以下是字典空白时的样子：
以下是往空白字典添加了第一个键值对之后的样子：
6、添加新键值对时发生碰撞处理
在哈希表实现中，当两个不同的键拥有相同的哈希值时，我们称这两个键发生碰撞（ collision），而哈希表实现必须想办法对碰撞进行处理。
字典哈希表所使用的碰撞解决方法被称之为 链地址法 ：这种方法使用链表将多个哈希值相同的节点串连在一起，从而解决冲突问题。
假设现在有一个带有三个节点的哈希表，如下图：
对于一个新的键值对 key4和value4，如果key4的哈希值和 key1的哈希值相同，那么它们
将在哈希表的 0号索引上发生碰撞。
通过将key4-value4 和key1-value1 两个键值对用链表连接起来，就可以解决碰撞的问题：
7、添加新键值对时触发了 rehash操作
对于使用链地址法来解决碰撞问题的哈希表 dictht来说，哈希表的性能依赖于它的大小（ size属性）和它所保存的节点的数量（ used属性）之间的比率：
?比率在 1:1时，哈希表的性能最好；
?如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表本身的性能优势就不再存在；
举个例子，对于下面这个哈希表，平均每次失败查找只需要访问 1个节点（非空节点访问 2次，空节点访问 1次） ：
而对于下面这个哈希表，平均每次失败查找需要访问 5个节点：
为了在字典的键值对不断增多的情况下保持良好的性能，字典需要对所使用的哈希表（ ht[0]）进行 rehash操作：在不修改任何键值对的情况下，对哈希表进行扩容，尽量将比率维持在 1:1左右。
dictAdd 在每次向字典添加新键值对之前，都会对哈希表 ht[0]进行检查，对于 ht[0]的size和used属性，如果它们之间的比率 ratio = used / size 满足以下任何一个条件的话，rehash过程就会被激活：
1.自然 rehash：ratio >= 1 ，且变量 dict_can_resize 为真。
2.强 制 rehash：ratio大 于 变 量 dict_force_resize_ratio （目 前 版 本 中，dict_force_resize_ratio 的值为5） 。
Note:什么时候 dict_can_resize 会为假？
在前面介绍字典的应用时也说到过，一个数据库就是一个字典，数据库里的哈希类型键也是一个字典，当 Redis使用子进程对数据库执行后台持久化任务时（比如执行 BGSAVE或BGREWRITEAOF 时） ，为了最大化地利用系统的 copy on write 机制，程序会暂时将dict_can_resize 设为假，避免执行自然 rehash，从而减少程序对内存的触碰（ touch） 。
当持久化任务完成之后， dict_can_resize 会重新被设为真。
另一方面，当字典满足了强制 rehash的条件时，即使 dict_can_resize 不为真（有 BGSAVE或BGREWRITEAOF 正在执行） ，这个字典一样会被 rehash。
8、Rehash执行过程
字典的 rehash操作实际上就是执行以下任务：
1.创建一个比 ht[0]->table 更大的ht[1]->table ；
2.将ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
3.将原有ht[0]的数据清空，并将 ht[1]替换为新的 ht[0]；
经过以上步骤之后，程序就在不改变原有键值对数据的基础上，增大了哈希表的大小。
作为例子，以下四个小节展示了一次对哈希表进行 rehash的完整过程。
1.开始rehash
这个阶段有两个事情要做：
1.设置字典的 rehashidx 为0，标识着 rehash的开始；
2.为ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍；
这时的字典是这个样子：
2. Rehash 进行中
在这个阶段， ht[0]->table 的节点会被逐渐迁移到 ht[1]->table ，因为 rehash是分多次进行的（细节在下一节解释） ，字典的 rehashidx 变量会记录 rehash进行到ht[0]的哪个索引位置上。
以下是rehashidx 值为2时，字典的样子：
注意除了节点的移动外，字典的 rehashidx 、ht[0]->used 和ht[1]->used 三个属性也产生了变化。
3.节点迁移完毕
到了这个阶段，所有的节点都已经从 ht[0]迁移到ht[1]了：
4. Rehash 完毕
在 rehash的最后阶段，程序会执行以下工作：
1.释放ht[0]的空间；
2.用ht[1]来代替ht[0]，使原来的 ht[1]成为新的 ht[0]；
3.创建一个新的空哈希表，并将它设置为 ht[1]；
4.将字典的 rehashidx 属性设置为 -1，标识 rehash已停止；
以下是字典 rehash完毕之后的样子：
对比字典 rehash之前和 rehash之后，新的 ht[0]空间更大，并且字典原有的键值对也没有被修改或者删除。
9、渐进式rehash
在上一节，我们了解了字典的 rehash过程，需要特别指出的是， rehash程序并不是在激活之后就马上执行直到完成的，而是分多次、渐进式地完成的。
假设这样一个场景：在一个有很多键值对的字典里，某个用户在添加新键值对时触发了 rehash过程，如果这个 rehash过程必须将所有键值对迁移完毕之后才将结果返回给用户，这样的处理方式将是非常不友好的。
另一方面，要求服务器必须阻塞直到 rehash完成，这对于 Redis服务器本身也是不能接受的。为了解决这个问题， Redis使用了渐进式（ incremental ）的 rehash方式：通过将 rehash分散到多个步骤中进行，从而避免了集中式的计算。
渐进式 rehash主要由_dictRehashStep 和dictRehashMilliseconds 两个函数进行：
?_dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash；
?dictRehashMilliseconds 则由 Redis服务器常规任务程序（ server cron job ）执行，用于对数据库字典进行主动 rehash；
_dictRehashStep
每次执行 _dictRehashStep ，ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全部迁移到 ht[1]->table 。
在 rehash开始进行之后（ d->rehashidx 不为-1） ，每次执行一次添加、查找、删除操作，
_dictRehashStep 都会被执行一次：
因为字典会保持哈希表大小和节点数的比率在一个很小的范围内，所以每个索引上的节点数量不会很多（从目前版本的 rehash条件来看，平均只有一个，最多通常也不会超过五个） ，所以在执行操作的同时，对单个索引上的节点进行迁移，几乎不会对响应时间造成影响。
dictRehashMilliseconds
dictRehashMilliseconds 可以在指定的毫秒数内，对字典进行 rehash。
当 Redis的服务器常规任务执行时， dictRehashMilliseconds 会被执行，在规定的时间内，尽可能地对数据库字典中那些需要 rehash的字典进行 rehash，从而加速数据库字典的 rehash进程（ progress） 。
其他措施
在哈希表进行 rehash时，字典还会采取一些特别的措施，确保 rehash顺利、正确地进行：
?因为在 rehash时，字典会同时使用两个哈希表，所以在这期间的所有查找、删除等操作，除了在ht[0]上进行，还需要在 ht[1]上进行。
?在执行添加操作时，新的节点会直接添加到 ht[1]而不是ht[0]，这样保证 ht[0]的节点数量在整个 rehash过程中都只减不增。
10、字典的收缩
上面关于 rehash的章节描述了通过 rehash对字典进行扩展（ expand）的情况，如果哈希表的可用节点数比已用节点数大很多的话，那么也可以通过对哈希表进行 rehash来收缩（ shrink）字典。
收缩 rehash和上面展示的扩展 rehash的操作几乎一样，它执行以下步骤：
1.创建一个比 ht[0]->table 小的ht[1]->table ；
2.将ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
3.将原有ht[0]的数据清空，并将 ht[1]替换为新的 ht[0]；
扩展 rehash和收缩 rehash执行完全相同的过程，一个 rehash是扩展还是收缩字典，关键在于新分配的 ht[1]->table 的大小：
?如果 rehash是扩展操作，那么 ht[1]->table 比ht[0]->table 要大；
?如果 rehash是收缩操作，那么 ht[1]->table 比ht[0]->table 要小；
字典的收缩规则由 redis.c/htNeedsResize 函数定义：
/*
*检查字典的使用率是否低于系统允许的最小比率
*
*是的话返回 1，否则返回 0。
*/
int htNeedsResize (dict*dict) {
long longsize, used;
//哈希表已用节点数量
size=dictSlots(dict);
//哈希表大小
used=dictSize(dict);
//当哈希表的大小大于 DICT_HT_INITIAL_SIZE并且字典的填充率低于REDIS_HT_MINFILL 时，返回1
return(size&&used&&size>DICT_HT_INITIAL_SIZE &&
(used*100/size<REDIS_HT_MINFILL));
}在默认情况下， REDIS_HT_MINFILL 的值为10，也即是说，当字典的填充率低于 10%时，程序就可以对这个字典进行收缩操作了。
字典收缩和字典扩展的一个区别是：
?字典的扩展操作是自动触发的（不管是自动扩展还是强制扩展） ；
?而字典的收缩操作则是由程序手动执行。
因此，使用字典的程序可以决定何时对字典进行收缩：
?当字典用于实现哈希键的时候，每次从字典中删除一个键值对，程序就会执行一次htNeedsResize 函数，如果字典达到了收缩的标准，程序将立即对字典进行收缩；
?当 字 典 用 于 实 现 数 据 库 键 空 间 （ key space ） 的 时 候， 收 缩 的 时 机 由redis.c/tryResizeHashTables 函数决定；
11、字典其他操作
除了添加操作和伸展 /收缩操作之外，字典还定义了其他一些操作，比如常见的查找、删除和更新。
因为链地址法哈希表实现的相关信息可以从任何一本数据结构或算法书上找到，这里不再对字典的其他操作进行介绍，不过前面对创建字典、添加键值对、收缩和扩展 rehash的讨论已经涵盖了字典模块的核心内容。
12、字典的迭代
字典带有自己的 迭代器实现——对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：
?迭代器首先迭代字典的第一个哈希表，然后，如果 rehash正在进行的话，就继续对第二个哈希表进行迭代。
?当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
?当这个索引迭代完了，继续查找下一个不为空的索引，如此循环，一直到整个哈希表都迭代完为止。
整个迭代过程可以用伪代码表示如下：
defiter_dict (dict):
#迭代0号哈希表
iter_table(ht[ 0]->table)
#如果正在执行 rehash，那么也迭代 1号哈希表
if dict.is_rehashing(): iter_table(ht[ 1]->table)
defiter_table (table):
#遍历哈希表上的所有索引
for index intable:
#跳过空索引
if table[index] .empty():
continue
#遍历索引上的所有节点
for node in table[index]:
#处理节点
do_something_with(node)字典的迭代器有两种：
?安全迭代器：在迭代进行过程中，可以对字典进行修改。
?不安全迭代器：在迭代进行过程中，不对字典进行修改。
以下是迭代器的数据结构定义：
/*
*字典迭代器
*/
typedef structdictIterator {
dict*d; //正在迭代的字典
int table, //正在迭代的哈希表的号码（ 0或者1）
index, //正在迭代的哈希表数组的索引
safe; //是否安全？
dictEntry *entry, //当前哈希节点
*nextEntry; //当前哈希节点的后继节点
} dictIterator;以下函数是这个迭代器的 API，它们的作用及相关算法复杂度：
二、Redis的字典存在哪些常见的问题和限制？
Redis的字典存在以下常见问题和限制：
-
内存占用：Redis的字典数据都存放在内存中，如果存储的数据量过大，可能会导致内存溢出。
-
查询速度：虽然Redis的字典采用了哈希表来实现，查询速度较快，但在数据量较大时，查询性能可能会下降。
-
并发性：Redis的字典是单线程执行的，对于高并发的场景，可能会导致性能瓶颈。
-
数据类型限制：Redis的字典只支持字符串类型的键和值，不支持复杂的数据结构。
-
内存回收机制：Redis使用了一些内存回收机制来优化内存使用，但这可能导致一些数据丢失或被删除。
-
遍历效率：Redis的字典不支持全局遍历，只能通过遍历部分数据或使用命令来获取特定的数据。
-
数据一致性：Redis的字典在出现系统故障或断电等情况时，可能导致数据丢失或不一致。
需要注意的是，虽然Redis的字典存在一些问题和限制，但它仍然是一个高性能、可靠的键值存储系统，在大多数场景下能够满足需求。
三、字典的使用场景有哪些？
Redis字典（也称为哈希表）是Redis中一种非常常见和重要的数据结构，它具有以下几个常见的使用场景：
-
缓存：字典是Redis常用的缓存数据结构之一。可以将经常需要读取的数据存储在字典中，以便快速访问，提高系统的读取性能。
-
数据存储：字典可以用于存储各种类型的数据，如用户信息、配置信息等。使用字典可以方便地进行数据的存储、读取和更新。
-
计数器：字典可以用于实现计数器功能。通过将计数器的值存储在字典中，并使用字典提供的自增、自减等操作，可以方便地实现计数功能。
-
统计信息：字典可以用于存储和统计信息。例如，可以使用字典记录用户的访问次数、浏览次数等信息，然后通过字典提供的操作进行统计和分析。
-
分布式锁：字典可以用于实现分布式锁。通过将锁的状态存储在字典中，并使用字典提供的原子操作来控制锁的获取和释放，可以实现多个进程或线程之间的同步和互斥。
-
快速查找：字典提供了快速的查找功能，可以根据给定的键快速地定位到对应的值，这在一些需要频繁查找和访问数据的场景中非常有用。
总的来说，Redis字典的使用场景非常广泛，可以满足许多不同的需求，提供高效的数据存储和操作能力。
四、字典是否支持并发访问？
Redis 字典是一个单线程的数据结构，不支持并发访问。只有在 Redis 服务器的事件循环机制下，才能实现并发的访问。当多个客户端同时发起操作时，Redis 会通过事件循环机制交替执行客户端请求，并保证每次只有一个请求被处理，避免并发访问的问题。
五、字典的扩容和缩容是如何实现的？
Redis中的字典是一种使用哈希表实现的键值对集合，其扩容和缩容过程如下：
扩容：
- 当字典中的元素数量超过字典的负载因子时，就需要进行扩容。负载因子是指字典中元素数量与哈希表大小的比值，一般设置为0.75。
- 当需要扩容时，Redis会创建一个新的哈希表，大小是原来哈希表的两倍。
- 然后，Redis会遍历原哈希表中的所有元素，并将它们重新插入到新哈希表中。这个过程称为rehash。
- 在rehash过程中，Redis会为每个元素重新计算哈希值，并将其插入到新哈希表对应的位置上。
- 扩容过程完成后，系统会将新哈希表替代原哈希表，然后释放原哈希表的内存空间。
缩容：
- 当字典中的元素数量远小于哈希表的大小，并且没有进行扩容操作一段时间后，Redis会考虑进行缩容。
- 缩容的目的是减少内存的使用，提高字典的性能。
- 当需要缩容时，Redis会创建一个新的哈希表，大小是原来哈希表的一半。
- 然后，Redis会遍历原哈希表中的所有元素，并将它们重新插入到新哈希表中。
- 缩容过程完成后，系统会将新哈希表替代原哈希表，然后释放原哈希表的内存空间。
需要注意的是，在扩容和缩容过程中，由于需要遍历原哈希表中的所有元素，所以可能会对系统的性能造成一定的影响。因此，Redis会将这个操作分为多个小步骤来执行，以减少对系统的影响。
六、字典是否支持持久化存储？
Redis字典支持持久化存储。Redis提供了两种持久化方式：
- RDB持久化：将内存中的数据以快照的形式保存到磁盘上的RDB文件中。通过配置Redis可以定期自动执行快照操作，也可以手动触发。
- AOF持久化：将写入Redis的每个操作以追加的方式写入磁盘上的AOF文件中。通过配置Redis可以选择将AOF文件同步到磁盘的频率，可以选择每秒同步、每个命令同步或者不同步。
这两种持久化方式可以同时使用，也可以选择其中一种。持久化可以确保Redis在重启后能恢复之前的数据。
七、小结
?字典由键值对构成的抽象数据结构。
? Redis中的数据库和哈希键都基于字典来实现。
? Redis字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用 0号哈希表，只有在 rehash进行时，才会同时使用 0号和 1号哈希表。
?哈希表使用链地址法来解决键冲突的问题。
? Rehash可以用于扩展或收缩哈希表。
?对哈希表的 rehash是分多次、渐进式地进行的。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！