详解Redis中字典的内部原理和使用方法

前言

在 Redis 中,字典是一种运用特别广泛的数据结构,基本上各个功能模块都有使用到。

  • 主要用途是两个方面
    • 作为数据库键空间
    • 作为 Hash 类型键的底层实现之一

目录

  1. 字典的使用示例
  2. 字典的底层结构和源码解析
  3. Rehash 的过程
  4. 业务场景的实际运用

1. 字典使用示例

1.1 实现数据库键空间
  • 清除数据库里面的所有键值对

    1
    2
    redis> FLUSHDB
    OK
  • 获得数据库里面所有键值对的数量

    1
    2
    redis> DBSIZE
    (integer) 0
  • 设置键值对空间

    1
    2
    3
    4
    5
    redis> set space dong
    OK

    redis> get space
    "dong"

以上的这三种就是字典在 Redis 数据库里面作为键空间的示例,操作数据库的命令,实际上就是在字典上操作的。

1.2 Hash 类型键的底层实现

在 Hash 键底层是有两种数据结构来实现的,一种是压缩列表,一种是字典
默认是由压缩列表来实现,等到符合条件后才会实现转换。

条件:

  • 哈希表中的某个键或者某个值的长度大于 64 的时候
  • 哈希表中的节点 (entry) 数量大于 512 的时候
使用示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
redis> HSET spacedong redis "redis"
(integer) 1

redis> HSET spacedong mysql "mysql"
(integer) 1

redis>HSET spacedong memcached "memcached"
(integer) 1

redis> HGETALL spacedong
1) "mysql"
2) "mysql"
3) "redis"
4) "redis"
5) "memcached"
6) "memcached"

2. 字典的底层结构和源码解析

2.1 字典的结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* 字典
*
* 每个字典使用两个哈希表,用于实现渐进式 rehash
*/
typedef struct dict {

// 特定于类型的处理函数
dictType *type;

// 类型处理函数的私有数据
void *privdata;

// 哈希表(2 个)
dictht ht[2];

// 记录 rehash 进度的标志,值为 -1 表示 rehash 未进行
int rehashidx;

// 当前正在运作的安全迭代器数量
int iterators;

} dict;
  • 这里的哈希表有两个指针,分别指向的是两个hash表。ht[0] 指向的是 0 号 hash 表,0 号 hash 表是正在使用的那张表,1 号 hash 表是当 0 号 hash 表正在 rehash 的时候才会使用的到,稍后会详细讲解 rehash 的过程。
    2.2 Hash表的结构
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /*
    * 哈希表
    */
    typedef struct dictht {

    // 哈希表节点指针数组(俗称桶,bucket)
    dictEntry **table;

    // 指针数组的大小
    unsigned long size;

    // 指针数组的长度掩码,用于计算索引值
    unsigned long sizemask;

    // 哈希表现有的节点数量
    unsigned long used;

    } dictht;

Hash表结构

  • Hash 表中的 table 是一个数组来的,是由一个个dictEntry组成,在图中所示的就是一个长度为 4 的空 table 。

    2.3 DictEntry的结构
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
    void *val;
    uint64_t u64;
    int64_t s64;
    } v;

    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;

    } dictEntry;
  • key中保存的是键,在v中保存的可能是指针,或者是 unit64_t 的整数,或者是 int64_t 的整数。next 指针指向的是下一个 hash 表节点,形成链表的结构,如下图。

DictEntry的内部结构

2.3 解决键冲突

当 hash 表出现键冲突的时候,Redis中的处理是直接把插入进来的这个键的 next 指针指向当前的键,通俗的理解就是直接插入到这个节点的头部,形成链表。

3. Rehash 过程

  • 先是 Hash 表进行判断是否需要扩展或者是收缩
  • 其次是在 ht[1] 中进行扩展或者收缩,每次的扩展或者收缩为原来的hash表的量的一倍或者一半,比如原本的hash表节点是8,扩展完成的话就是16,收缩完成的话就是4.
  • 接着就是 Rehash 的过程
    3.1 满足以下 ReHash 的前提条件任意一个,就会进行扩展 Hash 表
  • 服务器目前没有在执行 BGSAVE 或者是 BGREWRITEAOF 命令的时候,当前的负载因子大于等于 1
  • 服务器目前在执行 BGSAVE 或者是 BGREWRITAOF 的命令时候,当前的负载因子大于等于 5

补充:

当服务器在进行执行 BGSAVE 或者是 BGREWRITEAOF 的命令时,这个时候服务器在创建子进程完成备份,操作系统一般都是使用写时复制的(copr-on-write) 来优化子进程的效率,所以在子进程执行期间就会扩大负载因子,这样就可以尽可能地避免存在子进程期间进行扩展表,减少不必要的内存消耗。

负载因子(load_factor) = 已存在的节点数量 \ 能容纳的节点数量

  • 如果是收缩的话,只需要负载因子小于 0.1 即可
3.2 Rehash 过程
  1. 先进行 Hash 表扩展
    image
  2. 接着就是 Hash 表中的表 0 向表 1 迁移的过程

image

  1. ReHash 过程结束后
    image

4.实际运用场景分析

  • 存储对象的信息

根据以上字典的特性,我们知道,字典和 HashMap 的特性是差不多的,也是基于数组和链表的组合,所以一般都是用来存储键值对的。不过在实际运用场景中,我们会经常用来存储一个对象的信息。例如:一个对象的属性如 name ,age ,weight 等属性,可以直接当做一个个键值对存储在这个字典下,这样做的好处是,在需要用到这个对象的属性时,不用把这个对象全部序列化,只需要取出特定的就可以,而在传统的需要全部序列化,相比来讲就比较消耗资源。

参考书籍:Redis设计与实现

spacedong wechat
愿意交个朋友吗~
觉得有收获么