【Redis】字典

Metadata

title: 【Redis】 字典
date: 2023-07-09 08:31
tags:
  - 行动阶段/完成
  - 主题场景/数据存储
  - 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
  - 细化主题/数据存储/Redis
categories:
  - 数据存储
keywords:
  - 数据存储/Redis
description: 【Redis】 字典

概述

字典又称符号表，关联数组或映射，用于保存键值对的抽象数据结构。当一个哈希键包含的键值对比较多时，或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希键的底层实现。

字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。

Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用。
当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的。

字典的实现

Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，每个哈希表节点保存了字典中的一个键值对。

哈希表

使用dict.h/dictht结构定义：

typedef struct dictht{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
}dictht;

数组中的每个元素都是指向dict.h/dictht的结构，dictEntry 就是一个键值对。

哈希表节点

哈希表节点使用 dictEntry 实现，每个 dictEntry 都存储着一个键值对：

typedef struct dictEntry{
    //键
    void *key;
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

键值对的值可以是一个指针，或一个uint64_t整数，或一个int64_t整数。next 是指向另一个哈希节点的指针，可将多个哈希值相同的键值对连接在一起，以此来解决冲突。

如图，表示的是两个哈希值相同的节点，通过指针连接在一起。

字典

Redis 中的字典由dict.h/dict实现，由这个数据结构将字典组织在一起。

typedef struct dict{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash索引
    //当rehash不在进行时，值为-1
    int rehashidx;
} dict;

type 和 privdata 属性是针对不同类型的键值对，为丰富键值对的使用场景而设置的。

type 属性是一个指向 dictType 的结构指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 为用途不同的字典设置不同类型特定函数。

typedef struct dictType{
    //计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    //复制键的函数
    void *(*keyDup)(void *privdata,const void *key)
    ...
}

privdata 属性保存了需要传给那些类型特定函数的可选参数。
ht 属性是包含两个项的数组，每项都是一个哈希表，ht[0] 平时使用，而 ht[1] 仅在 rehash 时使用。
rehashidx 记录了 rehash 的进度，初始为 - 1。

哈希算法

Redis 计算哈希值方法： hash=dict->type->hashFunction(key);
计算索引值的方法：index=hash & dict->ht[x].sizemask;

当字典被用作数据库的底层实现或哈希键的底层实现时，Redis 使用 MurmurHash2 算法来计算键的哈希值。优点在于即使输入的键是有规律的，算法仍然能给出很好的随机分布性，并且计算速度飞快。

解决键冲突

当有两个或以上的键被分配到哈希表的同个索引，那么就发生了冲突。Redis 使用链地址法来解决冲突，被分配到索引的多个节点使用链表连接。为了提高速度，每次都是将新节点添加到链表的表头位置。

rehash

为了让哈希表的负载因子维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行响应的扩容或缩容。扩容和缩容通过执行 rehash 来完成，Redis 中重新散列的步骤如下：

为字典 ht[1] 哈希表分配空间，大小取决于要执行的操作与 ht[0] 当前键值对的数量。
将保存在 ht[0] 中的所有键值对存放到 ht[1] 指定的位置
当 ht[0] 的所有键值对都迁移完毕后，释放 ht[0]，并指向 ht[1]，并在 ht[1] 上创建一个空的哈希表，为下次 rehash 准备。

扩容与缩容场景

扩容操作场景：

服务器目前没有在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子 >=1。
服务器正在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子 >=5。

负载因子 = 哈希表已存储节点数 / 哈希表大小
load_factor=ht[0].used/ht[0].size

为什么根据**BGSAVE命令或BGREWRITEAOF命令来判断是否扩展？
因为执行这些命令时，Redis 需要创建当前服务器进程的子进程，大多数操作系统采用写时复制技术**来优化子进程使用效率，此时提高负载因子，可以尽量避免子进程对哈希表扩展，避免不必要的内存写入操作，节约内存。

缩容操作场景：负载因子 < 0.1 时，自动对哈希表执行收缩操作。

渐进式 rehash 的过程

rehash 时会将 ht[0] 中所有的键值对 rehash 到 ht[1]，如果键值对很多并且一次性操作的话，容易导致服务器在一段时间内停止服务。为避免这种情况，Redis 采用渐进式 rehash，将 ht[0] 中的键值对分多次，慢慢的 rehash 到 ht[1] 之中。

步骤：

为 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 的期间，字典同时使用 ht[0]，ht[1] 两个哈希表。对哈希表的操作会在两个表上进行，比如查找键时，先在 ht[0] 里面查找，如果为空，就继续到 ht[1] 里查找。在此期间，新增的键值对都会被添加到 ht[1] 中，ht[0] 不承担任何添加操作，保证 ht[0] 中的键值对只能是越来越少。

字典时间复杂度

字典相关操作及时间复杂度：

操作	时间复杂度
添加键值对	O(1)
返回给定键的值	O(1)
删除给定键的值	“O(N),N为链表长度”
释放字典	“O(N),N为字典包含的键值对数”

字典API

函数	作用	时间复杂度
dictCreate	创建一个新的字典	O(1)
dictAdd	将给定的键值对添加到字典里面	O(1)
dictReplace	“将给定的键值对添加到字典里面,如果键已经存在于字典,那么用新值取代原有的值”	0(1)
dictFetchValue	返回给定键的值	O(1)
dictGetRandomKey	从字典中随机返回一个键值对	0(1)
dictDelete	从字典中删除给定键所对应的键值对	0(1)
dictRelease	“释放给定字典,以及字典中包含的所有键值对”	“O(N), N为字典包含的键值对数量”