redis源码剖析

发表于 | 分类于 |
字数统计: 10.5k | 阅读时长 ≈ 39

[TOC]

https://juejin.im/post/6855129008091332615

本文 知识 脑图 如下：

在这里插入图片描述

一、Redis的数据模型

用 键值对 name："小明"来展示Redis的数据模型如下：

在这里插入图片描述

  • dictEntry: 在一些编程语言中，键值对的数据结构被称为字典，而在Redis中，会给每一个key-value键值对分配一个字典实体，就是“dicEntry”。dicEntry包含三部分： key的指针、val的指针、next指针，next指针指向下一个dicteEntry形成链表，这个next指针可以将多个哈希值相同的键值对链接在一起，通过链地址法来解决哈希冲突的问题
  • sds ：Simple Dynamic String，简单动态字符串，存储字符串数据。
  • redisObject：Redis的5种常用类型都是以RedisObject来存储的，redisObject中的type字段指明了值的数据类型（也就是5种基本类型)。ptr字段指向对象所在的地址。

RedisObject对象很重要，Redis对象的类型、内部编码、内存回收、共享对象等功能，都是基于RedisObject对象来实现的。

这样设计的好处是：可以针对不同的使用场景，对5种常用类型设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。

Redis将jemalloc作为默认内存分配器，减小内存碎片。jemalloc在64位系统中，将内存空间划分为小、大、巨大三个范围；每个范围内又划分了许多小的内存块单位；当Redis存储数据时，会选择大小最合适的内存块进行存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * Redis 对象
 */
typedef struct redisObject {
 
    // 类型
    unsigned type:4;        
 
    // 不使用(对齐位)
    unsigned notused:2;
 
    // 编码方式
    unsigned encoding:4;
 
    // LRU 时间（相对于 server.lruclock）
    unsigned lru:22;
 
    // 引用计数
    int refcount;
 
    // 指向对象的值
    void *ptr;
 
} robj;

二、Redis支持的数据结构

Redis支持的数据结构有哪些？

如果回答是String、List、Hash、Set、Zset就不对了，这5种是redis的常用基本数据类型，每一种数据类型内部还包含着多种数据结构。

用encoding指令来看一个值的数据结构。比如：

1
2
3
4
5
127.0.0.1:6379> set name tom
OK
127.0.0.1:6379> object encoding name
"embstr"
复制代码

此处设置了name值是tom，它的数据结构是embstr，下文介绍字符串时会详解说明。

1
2
3
4
5
127.0.0.1:6379> set age 18
OK
127.0.0.1:6379> object encoding age
"int"
复制代码

如下表格总结Redis中所有的数据结构类型：

底层数据结构 编码常量 object encoding指令输出
整数类型 REDIS_ENCODING_INT “int”
embstr字符串类型 REDIS_ENCODING_EMBSTR “embstr”
简单动态字符串 REDIS_ENCODING_RAW “raw”
字典类型 REDIS_ENCODING_HT “hashtable”
双端链表 REDIS_ENCODING_LINKEDLIST “linkedlist”
压缩列表 REDIS_ENCODING_ZIPLIST “ziplist”
整数集合 REDIS_ENCODING_INTSET “intset”
跳表和字典 REDIS_ENCODING_SKIPLIST “skiplist”

补充说明

假如面试官问：redis的数据类型有哪些？

回答：String、list、hash、set、zet

一般情况下这样回答是正确的，前文也提到redis的数据类型确实是包含这5种，但细心的同学肯定发现了之前说的是“常用”的5种数据类型。其实，随着Redis的不断更新和完善，Redis的数据类型早已不止5种了。

登录redis的官方网站打开官方的数据类型介绍：

redis.io/topics/data…

在这里插入图片描述

发现Redis支持的数据结构不止5种，而是8种，后三种类型分别是：

  • 位数组（或简称位图）：使用特殊命令可以处理字符串值，如位数组：您可以设置和清除各个位，将所有位设置为1，查找第一个位或未设置位，等等。
  • HyperLogLogs：这是一个概率数据结构，用于估计集合的基数。不要害怕，它比看起来更简单。
  • Streams：仅附加的类似于地图的条目集合，提供抽象日志数据类型。

本文主要介绍5种常用的数据类型，上述三种以后再共同探索。

2.1 string字符串

字符串类型是redis最常用的数据类型，在Redis中，字符串是可以修改的，在底层它是以字节数组的形式存在的。

Redis中的字符串被称为简单动态字符串「SDS」，这种结构很像Java中的ArrayList，其长度是动态可变的.

1
2
3
4
5
6
struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte[] content; // 数组内容
}
复制代码

在这里插入图片描述

content[] 存储的是字符串的内容，capacity表示数组分配的长度，len表示字符串的实际长度。

字符串的编码类型有int、embstr和raw三种，如上表所示，那么这三种编码类型有什么不同呢？

1
2
3
4
5
6
7
8
9
struct sdshdr {    //简单动态字符串(simple dynamic string, SDS)的抽象类型
  // 用于记录buf数组中使用的字节的数目
  // 和SDS存储的字符串的长度相等  
	int len;    
  // 用于记录buf数组中没有使用的字节的数目   
	int free;    
  // 字节数组，用于储存字符串
	char buf[];   //buf的大小等于len+free+1，其中多余的1个字节是用来存储’\0’的。
};
  • int 编码：保存的是可以用 long 类型表示的整数值。
  • raw 编码：保存长度大于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。
  • embstr 编码：保存长度小于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。

img

设置一个值测试一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
127.0.0.1:6379> set num 300
127.0.0.1:6379> object encoding num
"int"
127.0.0.1:6379> set key1 wealwaysbyhappyhahaha
OK
127.0.0.1:6379> object encoding key1
"embstr"
127.0.0.1:6379> set key2 hahahahahahahaahahahahahahahahahahahaha
OK
127.0.0.1:6379> strlen key2
(integer) 39
127.0.0.1:6379> object encoding key2
"embstr"
127.0.0.1:6379> set key2 hahahahahahahaahahahahahahahahahahahahahahaha
OK
127.0.0.1:6379> object encoding key2
"raw"
127.0.0.1:6379> strlen key2
(integer) 45
复制代码

raw类型和embstr类型对比

embstr编码的结构:

在这里插入图片描述

raw编码的结构：

raw编码

embstr和raw都是由redisObject和sds组成的。不同的是：embstr的redisObject和sds是连续的，只需要使用malloc分配一次内存；而raw需要为redisObject和sds分别分配内存，即需要分配两次内存。

所有相比较而言，embstr少分配一次内存，更方便。但embstr也有明显的缺点：如要增加长度，redisObject和sds都需要重新分配内存。

上文介绍了embstr和raw结构上的不同。重点来了~ 为什么会选择44作为两种编码的分界点？在3.2版本之前为什么是39？这两个值是怎么得出来的呢？

1） 计算RedisObject占用的字节大小

1
2
3
4
5
6
7
8
struct RedisObject {
    int4 type; // 4bits
    int4 encoding; // 4bits
    int24 lru; // 24bits
    int32 refcount; // 4bytes = 32bits
    void *ptr; // 8bytes，64-bit system
}
复制代码
  • type: 不同的redis对象会有不同的数据类型(string、list、hash等)，type记录类型，会用到4bits。
  • encoding：存储编码形式，用4bits。
  • lru：用24bits记录对象的LRU信息。
  • refcount：引用计数器，用到32bits。
  • ptr：指针指向对象的具体内容，需要*64bits**。

计算： 4 + 4 + 24 + 32 + 64 = 128bits = 16bytes

第一步就完成了，RedisObject对象头信息会占用16字节的大小，这个大小通常是固定不变的.

2) sds占用字节大小计算

旧版本：

1
2
3
4
5
6
struct SDS {
    unsigned int capacity; // 4byte
    unsigned int len; // 4byte
    byte[] content; // 内联数组，长度为 capacity
}
复制代码

这里的unsigned int 一个4字节，加起来是8字节.

内存分配器jemalloc分配的内存如果超出了64个字节就认为是一个大字符串，就会用到raw编码。

前面提到 SDS 结构体中的 content 的字符串是以字节\0结尾的字符串，之所以多出这样一个字节，是为了便于直接使用 glibc 的字符串处理函数，以及为了便于字符串的调试打印输出。所以我们还要减去1字节 64byte - 16byte - 8byte - 1byte = 39byte

新版本：

1
2
3
4
5
6
7
struct SDS {
    int8 capacity; // 1byte
    int8 len; // 1byte
    int8 flags; // 1byte
    byte[] content; // 内联数组，长度为 capacity
}
复制代码

这里unsigned int 变成了uint8_t、uint16_t.的形式，还加了一个char flags标识，总共只用了3个字节的大小。相当于优化了sds的内存使用，相应的用于存储字符串的内存就会变大。

然后进行计算：

在这里插入图片描述

64byte - 16byte -3byte -1byte = 44byte。

总结：

所以，redis 3.2版本之后embstr最大能容纳的字符串长度是44，之前是39。长度变化的原因是SDS中内存的优化。

2.2 List

Redis中List对象的底层是由quicklist(快速列表)实现的，快速列表支持从链表头和尾添加元素，并且可以获取指定位置的元素内容。

那么，快速列表的底层是如何实现的呢？为什么能够达到如此快的性能？

罗马不是一日建成的，quicklist也不是一日实现的，起初redis的list的底层是ziplist（压缩列表）或者是 linkedlist（双端列表）。先分别介绍这两种数据结构。

ziplist 压缩列表

1
ziplist是由一系列特殊编码的连续内存块组成的顺序存储结构，类似于数组，ziplist在内存中是连续存储的，但是不同于数组，为了节省内存 ziplist的每个元素所占的内存大小可以不同。ziplist的每个节点的长度是可以不一样的。ziplist将一些必要的偏移量信息记录在了每一个节点里，使之能跳到上一个节点或下一个节点。

测试：

1
2
3
4
127.0.0.1:6379> rpush dotahero sf qop doom
(integer) 3
127.0.0.1:6379> object encoding dotahero
"ziplist"

此处使用老版本redis进行测试，向dota英雄列表中加入了qop痛苦女王、sf影魔、doom末日使者三个英雄，数据结构编码使用的是ziplist。

所以 ziplist是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。具体结构相对比较复杂，大家有兴趣地话可以深入了解。

1
2
3
4
5
6
7
8
struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}
复制代码

在这里插入图片描述

双端列表（linkedlist）

双端列表大家都很熟悉，这里的双端列表和java中的linkedlist很类似。

在这里插入图片描述

从图中可以看出Redis的linkedlist双端链表有以下特性：节点带有prev、next指针、head指针和tail指针，获取前置节点、后置节点、表头节点和表尾节点、获取长度的复杂度都是O(1)。

压缩列表占用内存少，但是是顺序型的数据结构，插入删除元素的操作比较复杂，所以压缩列表适合数据比较小的情况，当数据比较多的时候，双端列表的高效插入删除还是更好的选择

在Redis开发者的眼中，数据结构的选择，时间上、空间上都要达到极致，所以，他们将压缩列表和双端列表合二为一，创建了快速列表（quicklist）。和java中的hashmap一样，结合了数组和链表的优点。

快速列表（quicklist）

  • rpush: listAddNodeHead —O(1)
  • lpush: listAddNodeTail —O(1)
  • push:listInsertNode —O(1)
  • index : listIndex —O(N)
  • pop:ListFirst/listLast —O(1)
  • llen:listLength —O(N)

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct ziplist {
    ...
}
struct ziplist_compressed {
    int32 size;
    byte[] compressed_data;
}
struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl; // 指向压缩列表
    int32 size; // ziplist 的字节总数
    int16 count; // ziplist 中的元素数量
    int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储
    ...
}
struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count; // 元素总数
    int nodes; // ziplist 节点的个数
    int compressDepth; // LZF 算法压缩深度
    ...
}
复制代码

quicklist 默认的压缩深度是 0，也就是不压缩。压缩的实际深度由配置参数list-compress-depth决定。为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。如果深度为 2，表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

2.3 Hash

Hash数据类型的底层实现是ziplist（压缩列表）或字典（也称为hashtable或散列表）。这里压缩列表或者字典的选择，也是根据元素的数量大小决定的。

在这里插入图片描述

如图hset了三个键值对，每个值的字节数不超过64的时候，默认使用的数据结构是ziplist。

在这里插入图片描述

当我们加入了字节数超过64的值的数据时，默认的数据结构已经成为了hashtable。

Hash对象只有同时满足下面两个条件时，才会使用ziplist（压缩列表）：

  • 哈希中元素数量小于512个；
  • 哈希中所有键值对的键和值字符串长度都小于64字节。

压缩列表刚才已经了解了，hashtables类似于jdk1.7以前的hashmap。hashmap采用了链地址法的方法解决了哈希冲突的问题。想要深入了解的话可以参考之前写的一篇博客： hashmap你真的了解吗

Redis中的字典

典， 又称符号表（symbol table）、关联数组（associative array）或者映射（map）， 是一种用于保存键值对（key-value pair）的抽象数据结构。在字典中， 一个键（key）可以和一个值（value）进行关联（或者说将键映射为值）， 这些关联的键和值就被称为键值对。

字典中的每个键都是独一无二的， 程序可以在字典中根据键查找与之关联的值， 或者通过键来更新值， 又或者根据键来删除整个键值对， 等等。

实现分析

Redis 的字典采用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。所以咱们依次来分析一下哈希表、哈希表节点、以及字典的结构。

1.哈希表结构

哈希表结构定义 （dict.h/dictht）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

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

} dictht;
复制代码

描述：

1
2
3
4
5
6
table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
复制代码

结构图解：一个空的哈希表

Redis五种数据类型

2.哈希表节点

一个哈希表里面可以有多个哈希表节点，那么每个哈希表节点的结构以及多个哈希表节点之间的存储关系是怎么样的呢？

哈希表节点结构定义 （dictEntry）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct dictEntry {

    // 键
    void *key;

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

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

} dictEntry;
复制代码

描述：

1
2
3
4
5
key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 
或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 
复制代码

以此来解决键冲突（collision）的问题。

结构图解：多个哈希值相同的键值对存储结构，解决键冲突

Redis五种数据类型

3.字典结构实现

字典结构定义 （dict.h/dict）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

描述：type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，
Redis 会为用途不同的字典设置不同的类型特定函数。

privdata 属性则保存了需要传给那些类型特定函数的可选参数。
复制代码
typedef struct dictType {

    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);

    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);

    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);

    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);

    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);

} dictType;
复制代码

ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

结构图解：普通状态下（没有进行 rehash）的字典

Redis五种数据类型

哈希表分析

1.哈希算法

当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

Redis 计算哈希值和索引值的方法如下：

1
2
3
4
5
6
7
# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;
复制代码

如图 4-4：

Redis五种数据类型

举个例子， 对于图 4-4 所示的字典来说， 如果我们要将一个键值对 k0 和 v0 添加到字典里面， 那么程序会先使用语句：

1
2
hash = dict->type->hashFunction(k0);
复制代码

计算键 k0 的哈希值。

假设计算得出的哈希值为 8 ， 那么程序会继续使用语句：

1
2
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;
复制代码

计算出键 k0 的索引值 0 ， 这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引 0 位置上， 结构图解：图 4-5

Redis五种数据类型

2.键冲突解决

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时， 我们称这些键发生了冲突（collision）。

Redis 的哈希表使用链地址法（separate chaining）来解决键冲突： 每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。

举个例子， 假设程序要将键值对 k2 和 v2 添加到图 4-6 所示的哈希表里面， 并且计算得出 k2 的索引值为 2 ， 那么键 k1 和 k2 将产生冲突， 而解决冲突的办法就是使用 next 指针将键 k2 和 k1 所在的节点连接起来。 结构图解：图 4-7

Redis五种数据类型

Redis五种数据类型

因为 dictEntry 节点组成的链表没有指向链表表尾的指针， 所以为了速度考虑， 程序总是将新节点添加到链表的表头位置（复杂度为 O(1)）， 排在其他已有节点的前面。

3.rehash

rehash 操作不是一次性完成，而是采用渐进方式，这是为了避免一次性执行过多的 rehash 操作给服务器带来过大
的负担。
渐进式 rehash 通过记录 dict 的 rehashidx 完成，它从 0 开始，然后每执行一次 rehash 都会递增。例如在一次
rehash 中，要把 dict[0] rehash 到 dict[1]，这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1]
上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。
在 rehash 期间，每次对字典执行添加、删除、查找或者更新操作时，都会执行一次渐进式 rehash。
采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上，因此对字典的查找操作也需要到对应的 dictht 去执
行。

4. 扩容或者缩容

  • 随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩
  • 扩展和收缩哈希表的工作可以

哈希表的自动扩展与收缩

  • 当以下条件中的任意一个被满足时，程序

    会自动开始对哈希表执行扩展操作：

    • ①服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
    • ②服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5

  • 其中哈希表的\负载因子可以通过下列公式得出：**

1
2
#负载因子= 哈希表已保存节点数量/哈希表大小
load_factor = ht[0].used/ht[0].size
  • 例如，对于一个大小为4，包含4个键值对的哈希表来说，这个哈希表的负载因子为：
1
load_factor = 4/4 = 1
  • 又例如，对于一个大小为512，包含256个键值对的哈希表来说，这个哈希表的负载因子为：
1
load_factor = 256/512=0.5
  • 根据BGSAVE命令或BGREWRITEAOF命令是否正在执行，服务器执行扩展操作所需的负载因子并不相同，这是因为在执行BGSAVE命令或BGREWRITEAOF命令的过程中，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技 术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负 载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内 存写入操作，最大限度地节约内存
  • 另一方面，当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作

如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2^{n}（2的n次方幂）； ·如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^{n}

5.渐进式rehash执行期间的哈希表操作

  • 因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐 进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两 个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如 果没找到的话，就会继续到ht[1]里面进行查找，诸如此类
  • 另外，在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而 ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着 rehash操作的执行而最终变成空表

四、要点总结

1.字典 ht 属性是包含两个哈希表项的数组，一般情况下， 字典只使用 ht[0]， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash (下节分析) 时使用

redis中的dict 结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。

在这里插入图片描述

2.4 Set

Set数据类型的底层可以是intset(整数集)或者是hashtable(散列表也叫哈希表)。

当数据都是整数并且数量不多时，使用intset作为底层数据结构；当有除整数以外的数据或者数据量增多时，使用hashtable作为底层数据结构。

1
2
3
4
5
6
7
8
9
127.0.0.1:6379> sadd myset 111 222 333
(integer) 3
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset hahaha
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable"
复制代码

inset的数据结构为：

1
2
3
4
5
6
7
8
9
typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;
复制代码

intset底层实现为有序、无重复数的数组。 intset的整数类型可以是16位的、32位的、64位的。如果数组里所有的整数都是16位长度的，新加入一个32位的整数，那么整个16的数组将升级成一个32位的数组。升级可以提升intset的灵活性，又可以节约内存，但不可逆。

2.5 Zset

Redis中的Zset，也叫做有序集合。它的底层是ziplist（压缩列表）或 skiplist（跳跃表）。

压缩列表前文已经介绍过了，同理是在元素数量比较少的时候使用。此处主要介绍跳跃列表。

  跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

  跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

  在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

  Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员(member)是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

  和链表、字典等数据结构被广泛地应用在Redis内部不同，Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。

跳跃表的实现

跳跃表（skiplist）是一种有序数据链表结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。查询平均性能为O(logN)，最坏的情况会出现O(N)情况，而redis中的zset在数据较多的时候底层就是采用跳跃表去实现的，元素较少的时候会进行小对象压缩采用压缩列表实现。

img

从上述图我们可以看出跳跃表有以下几个特点：

  • 跳跃表的每个节点都有多层构成。

  • 跳跃表存在一个头结点，该头结点有64层结构，每层都包含指向下个节点的指针，指向本层下个节点中间所跨越的节点个数为跨度（span）。

  • 除头结点以外，层高最高的节点为该跳跃表的level，图中的跳跃表level为3。

  • 每层都是一个有序链表。

  • 最底层的有序链表包含所有的节点数，也即是整个跳跃表的长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    typedef struct zskiplistNode {
        robj *obj;  /*成员对象*/
        double score;   /*分值*/
        struct zskiplistNode *backward; /*后退指针*/
        struct zskiplistLevel { /*层*/
            struct zskiplistNode *forward;  /*前进指针*/
            unsigned int span;  /*跨度*/
        } level[];
    } zskiplistNode;
1
2
3
4
5
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    //header指向跳跃表的表头节点，tail指向跳跃表的表尾节点
    unsigned long length;   //记录跳跃表的长度，也即是，跳跃表目前包含节点的数量(表头节点不计算在内)
    int level;  //记录目前跳跃表内，层数最大的那个节点的层数(表头节点的层数不计算在内)
} zskiplist;

跳跃表\每个节点都维护了多个指向其他节点的指针\，*所以在进行查询、更新、删除等操作的时候不需要进行整条链表的遍历*，*可以通过维护的指针过滤掉中间的很多节点，从而达到很快速的访问效果***，一般情况来说跳跃表的性能能与平衡树相媲美的，而且跳跃表实现较为简单，所以这也是\redis为什么采用跳跃表来作为zset底层的数据结构实现**。

查找过程

跳跃表的查询，跳跃表有多层的情况下查询复杂度为O(logN)，如果跳跃表就一层那么查询复杂度会上升为O(N)，接下来我们就用图1的实例来模拟下查询score为70的节点的具体查询过程。

img

如图所示我们需要找到score为70的节点，查找首先从header开始，因为level为3我们先从L2开始往后开始遍历，查找到第一个节点，发现score比70小，继续往后遍历查找到第五个节点，发现score比70大，于是从当前节点往下一层进行查找，查找到节点3，以此类推，最终查询到score为70的节点。

插入以及更新过程
插入过程：跳跃表插入节点的时候，首先需要通过score找到自己的位置，也就是需要先走一步查找过程，找到新节点所处的位置的时候就创建一个新节点，并对新节点分配一个层数（这里层数的分配redis采用的是random随机机制，分配层数从1开始，每次晋升为上一层的概率为0.25），层数分配完了之后将前后指针进行赋值将新节点与旧节点串起来，\如果层数大于当前的level还需要进行level的更新操作。**

更新过程：更新过程会稍微复杂一些，更新其实就是插入，只不过插入的时候发现value已经存在了，只是需要调整一下score值，如果更新的score值不会带来位置上的改变，那么直接更新score就行不需要进行调整位置，但是如果新score会导致排序改变，那么就需要调整位置了，redis采用的方式比较直接就是先删除这个元素然后再插入这个元素即可，前后需要两次路径搜索

  Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中zskiplistNode结构用于表示跳跃表节点，而zskiplist结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。

一个跳跃表

  上图展示了一个跳跃表示例，位于图片最左边的是zskiplist结构，该结构包含以下属性：

  • header：指向跳跃表的表头节点
  • tail：指向跳跃表的表尾节点
  • level：记录目前跳跃表内，层数最大的那个节点的层数(表头节点的层数不计算在内)
  • length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量(表头节点不计算在内)

  位于zskiplist结构右方的是四个zskiplistNode结构，该结构包含以下属性：

  • 层(level)：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，依次类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
  • 后退(backward)指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
  • 分值(score)：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
  • 成员对象(obj)：各个节点中的o1、o2和o3是节点所保存的成员对象。

  注意表头节点和其他节点的构造是一样的：表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性都不会被用到，所以图中省略了这些部分，只显示了表头节点的各个层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#### **跳跃表节点**

  跳跃表节点的实现由redis.h/zskiplistNode结构定义：

​```c
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    robj *obj;  /*成员对象*/
    double score;   /*分值*/
    struct zskiplistNode *backward; /*后退指针*/
    struct zskiplistLevel { /*层*/
        struct zskiplistNode *forward;  /*前进指针*/
        unsigned int span;  /*跨度*/
    } level[];
} zskiplistNode;
​

  1、分值和成员

  节点的分值(score属性)是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。

  节点的成员对象(obj属性)是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。

  在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分至相同的节点将按照成员对象在字典中的大小来进行排序，成员对象较小的节点会排在前面(靠近表头的方向)，而成员对象较大的节点则会排在后面(靠近表尾的方向)。

  举个例子，在下图中所示的跳跃表中，三个跳跃表节点都保存了相同的分值10086.0，但保存成员对象o1的节点却排在保存成员对象o2和o3的节点的前面，而保存成员对象o2的节点又排在保存成员对象o3的节点之前，由此可见，o1、o2、o3三个成员对象在字典中的排序为o1<=o2<=o3。

三个带有相同分值的跳跃表节点

  2、后退指针

  节点的后退指针(backward属性)用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

  下图用虚线展示了如何从表尾向表头遍历跳跃表中的所有节点：程序首先通过跳跃表的tail指针访问表尾节点，然后通过后退指针访问倒数第二个节点，之后再沿着后退指针访问倒数第三个节点，再之后遇到指向NULL的后退指针，于是访问结束。

从表尾向表头方向遍历跳跃表

  3、层

  跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。

  每次创建一个新跳跃表节点的时候，程序根据幂次定律(power law，越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。

  下图分别展示了三个高度为1层、3层和5层的节点，因为C语言的数组索引总是从0开始的，所以节点的第一层是level[0]，而第二层是level[1]，依次类推。

带有不同层高的节点

  4、前进指针

  每个层都有一个指向表尾方向的前进指针(level[i].forward属性)，用于从表头向表尾方向访问节点。下图用虚线表示出了程序从表头向表尾方向，遍历跳跃表中所有节点的路径：

遍历整个跳跃表

  1) 迭代程序首先访问跳跃表的第一个节点(表头)，然后从第四层的前进指针移动到表中的第二个节点。
  2) 在第二个节点时，程序沿着第二层的前进指针移动到表中的第三个节点。
  3) 在第三个节点时，程序同样沿着第二层的前进指针移动到表中的第四个节点。
  4) 当程序再次沿着第四个节点的前进指针移动时，它碰到一个NULL，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历。

  5、跨度

  层的跨度(level[i].span属性)用于记录两个节点之间的距离：

  • 两个节点之间的跨度越大，它们相距得就越远。
  • 指向NULL的所有前进指针的跨度都为0，因为它们没有连向任何节点。

  初看上去，很容易以为跨度和遍历操作有关，但实际上并不是这样的，遍历操作只使用前进指针就可以完成了，跨度实际上是用来计算排位(rank)的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

  举个例子，下图用虚线标记了在跳跃表中查找分值为3.0、成员对象为o3的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3，所以目标节点在跳跃表中的排位为3。

计算节点的排位

  再举个例子，下图用虚线标记了在跳跃表中查找分值为2.0、成员对象为o2的节点时，沿途经历的层：在查找节点的过程中，程序经过了两个跨度为1的节点，因此可以计算出，目标节点在跳跃表中的排位为2。

另一个计算节点排位的例子

跳跃表

  仅靠多个跳跃表节点就可以组成一个跳跃表，如下图所示：

多个跳跃节点组成的跳跃表

  但通过使用一个zskiplist结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，或者快速地获取跳跃表节点的数量(也即是跳跃表的长度)等信息，如下图所示：

带有zskiplist结构的跳跃表

  zskiplist结构的定义如下：

​c typedef struct zskiplist { struct zskiplistNode *header, *tail; //header指向跳跃表的表头节点，tail指向跳跃表的表尾节点 unsigned long length; //记录跳跃表的长度，也即是，跳跃表目前包含节点的数量(表头节点不计算在内) int level; //记录目前跳跃表内，层数最大的那个节点的层数(表头节点的层数不计算在内) } zskiplist;12345 ​

  这样获取表头、表尾节点，表长，以及表中最高层数的复杂度均为O(1)。

```

总结

本文大概介绍了Redis的5种常用数据类型的底层实现，希望大家结合源码和资料更深入地了解。

数据结构之美在Redis中体现得淋漓尽致，从String到压缩列表、快速列表、散列表、跳表，这些数据结构都适用在了不同的地方，各司其职。

不仅如此，Redis将这些数据结构加以升级、结合，将内存存储的效率性能达到了极致，正因为如此，Redis才能成为众多互联网公司不可缺少的高性能、秒级的key-value内存数据库。

作者：宜信技术学院
链接：https://juejin.im/post/6844903863145742350
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。