大家知道，Redis 有 5 种常用的数据类型，分别是：String、List、Hash、Set 和 ZSet（有序集合）。对于这五种数据类型，实际上，Redis 都至少使用了两种不同的数据结构（编码形式）。那 Redis 的底层数据结构是如何实现的，本文会带领大家分析一下。
1. 全局Hash表、dictEntry 、redisObject
1.1 全局Hash表
- 何为全局 Hash 表：为了实现从键到值的快速访问，Redis使用了一个全局哈希表来保存所有键值对。也就是说，上面提到的五种数据类型，都会以键值对形式，存储在一个全局 Hash 表中。dictEntry 包含具体的键值对内容。
-
数据如何定位：计算数据键的哈希值，找到对应的哈希桶位置，即可访问相应的 entry 元素。
例如执行 hset schhash0417 key1 value1。Redis会根据键值 schhash0417 进行位置定位。 - 哈希冲突：使用链式哈希。同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。
-
链表过长：不同于 Java 中的 HashMap 会将链表结构转换成红黑树的处理，Redis 对于哈希冲突越来越多，链表过长的情况，会进行 Rehash 操作。当然，为了避免 Rehash 耗时带来的请求阻塞，Redis 使用了两个全局哈希表和渐进式 Rehash。
① 两个全局哈希表：哈希表 1 和哈希表 2。一开始，刚插入数据，默认使用哈希表1，此时的哈希表2并没有被分配空间。随着数据增多，给哈希表 2 分配更大的空间，Redis 开始执行 rehash，把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中，并释放哈希表 1 的空间。
② 渐进式 Rehash：Redis 仍正常处理客户端请求，每处理一个请求，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 dictEntry 元素拷贝到哈希表 2 中，等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 dictEntry 元素。
1.2 dictEntry 和 redisObject
1.2.1 dictEntry 说明
- dictEntry 上面已经提到过，全局哈希表的每一项是一个 dictEntry 对象。
-- dictEntry 结构中有三个 8 字节的指针，分别指向 key、value 以及下一个 dictEntry
typedef struct dictEntry {
void *key; -- 指向包含key信息的redisObject
void *val; -- 指向包含值信息的redisObject
struct dictEntry *next;
} dictEntry;
- 举个例子，执行以下命令，对于集合schlist041701，*key会指向包含字符串值 "schlist041701" 的redisObject，*val 会指向一个包含 list 集合的redisObject。
127.0.0.1:6379> rpush schlist041701 1 2 3
(integer) 3
1.2.2 redisObject 说明
Redis 的数据类型有很多，不同的数据类型都有些相同的对象信息要记录，比如对象类型，内部编码方式，最后一次访问的时间、被引用的次数等等。所以，Redis 用了一个 redisObject 结构体来统一记录对象的这些信息。当然了，还有一个指向真正数据的指针。
#define OBJ_SHARED_REFCOUNT INT_MAX
typedef struct redisObject {
unsigned type:4; -- 对象类型，包含String、List、Hash、Set 和 ZSet 等对象类型
unsigned encoding:4; -- 内部编码类型
unsigned lru:LRU_BITS; -- 最后一次命令访问的时间。
-- 当Redis的缓存淘汰策略为LRU时，24位bit存储的为时间戳；
-- 淘汰策略为LFU，前 16bit为数据的访问时间戳；后 8bit为数据的访问次数。
int refcount; -- redis内存回收机制，所使用的引用计数信息。
void *ptr; -- 指向真正的数据
} robj;
- 举个例子，创建一个 list 集合对象，查看包含值信息的redisObject
127.0.0.1:6379> lpush schlist041702 a b c
(integer) 3
① redisObject 的 type
127.0.0.1:6379> type schlist041702
list
② redisObject 的 encoding
127.0.0.1:6379> object encoding schlist041702
"quicklist"
③ redisObject 的最近访问时间
127.0.0.1:6379> object refcount schlist041702
(integer) 1
④ redisObject 的最近访问时间 (idletime，返回的是自上次访问该键以来经过的秒数)
127.0.0.1:6379> object idletime schlist041702
(integer) 401
2. 底层数据结构总览
好了，上面讲这么多，这里要步入正题了，标题就是底层数据结构。没错，就是 RedisObject 的 encoding（内部编码类型）的详细描述。
2.1 数据类型 type 和 编码 encoding 的关系
- 以 Hash 数据类型为例，数据结构实现有压缩列表和哈希表两种结构（编码）类型。Redis 会根据，哈希对象保存的键值对数据量大小，以及保存的所有键值对的键和值的字符串长度，来选择用哪种方式实现。
- List 数据类型：需要注意一点的是，v3.2 以后， List 数据类型，统一用 quicklist 来存储 List 列表对象，quicklist 是一个双向链表，每个节点都是一个压缩列表。
3. 底层数据结构详述
3.1 简单动态字符串
3.1.1 组成结构
1. 简单动态字符串（Simple Dynamic String，SDS），String 类型使用的结构体，主要有三部分组成。
2. len：占 4 个字节，表示 buf 的已用长度。
3. alloc：占个 4 字节，表示 buf 的实际分配长度，一般大于 len。
4. buf：字节数组，保存实际数据。为了表示字节数组的结束，Redis会自动在数组最后加一个“\0”。
3.1.2 优点
-
获取字符串长度的复杂度O(1)
1、为何是O(1)：因为在 SDS 中，len 记录了实际使用的字符串长度，所以为O(1)。但是，在C语言中，C字符串并不记录自身的长度信息，必须遍历整个字符串来进行计数，直到遇到空字符为止，这个操作的复杂度为O(N)。注意这里的空字符，不是空格SP，为"\0"，代表C字符串的结尾，根据ASCII表，空字符对应二进制为0000 0000。
2、二进制数据支持：在C字符串，除了字符串的末尾之外，字符串里面不能包含空字符。由于这些原因，C字符串只能保存文本数据，而不能保存图片、音频等二进制数据。由于SDS，使用len值，而不是空字符来判断字符串是否结束，所以可以保存一系列二进制数据。
3、Redis既然记录了长度信息，但是为何也会在数组最后加一个“\0”：兼容部分C字符串函数，让保存文本数据的SDS，重用一部分<string.h>库定义的函数。
4、个人想法：既然在SDS中，len要记录使用的字符串长度，则需要在创建和修改SDS对象时，维护这个len长度。在Redis的缓存应用场景中，大部分是查询操作，低成本的len维护，为高频率的查询带来可观的查询效率，也是一个我们值得借鉴的地方。 - 杜绝缓冲区的溢出：当需要对SDS进行修改时，Redis会先检查SDS的空间是否满足修改所需的要求，如果不满足，会自动将SDS的空间扩展至执行修改所需的大小。
- 减少内存分配次数：创建字符串对象实际不仅申请了要使用的内存，还额外申请了一些空间，避免下次增大字符串的长度又需要重新申请内存。
3.2 双向链表
- 我们所熟知的 List 集合，有数组和链表两种实现方式，此刻此景，大家脑补一下Java 的 ArrayList 和 LinkedList。数组的优势在于数据定位以及减小内存碎片。链表的优势在于增加、删除操作。Redis采用了链表的方式，而且是一个双向链表。
- Redis 的双向链表，包含了head（头结点）、tail（尾节点)、len（链表节点数量）。所以定位头尾元素、执行PUSH和POP操作、获取List长度，操作都非常快，时间复杂度O(1)。
- 双向链表：由于使用双向链表，而且List 结构记录了tail 节点信息，所以对于一些获取链表末尾元素的操作有很好的支持，例如获取集合 schlist041703 的最后三个元素。
127.0.0.1:6379> lpush schlist041703 a
(integer) 1
127.0.0.1:6379> lpush schlist041703 b
(integer) 2
127.0.0.1:6379> rpush schlist041703 c
(integer) 3
127.0.0.1:6379> rpush schlist041703 d
(integer) 4
127.0.0.1:6379> lrange schlist041703 -3 -1
1) "a"
2) "c"
3) "d"
3.3 压缩列表（ziplist ）
3.2.1 结构
zlbytes：列表的长度
zltail：列表尾的偏移量
zllen：entry 个数
entry：列表元素
zlend：列表结尾
- 获取列表长度，定位尾部元素、以及获取entry个数，时间复杂度均为O(1)。
3.2.2 列表元素 entry
- prevlen：当前 entry 的前一个 entry 节点的长度（prevlen）。我们可以根据当前节点的起始地址来计算出前一个节点的起始地址，也可以利用这个原理，从表尾向表头遍历压缩列表。
- encoding：记录了 data 属性所保存数据的类型和长度。
- data：entry节点的值。数据类型为 string 或 int 类型。
3.2.3 优缺点
- 优点：由连续内存块组成，节省内存，并且减少内存碎片。
- 缺点：
① 分配大块连续内存空间的难度比较大；
② 由于当前 entry 会记录前一个 entry 节点的长度。如果前一个节点长度发生变更，如果当前 entry 记录前节点长度的字节数发生变化，又会导致自身长度发生变化，继而导致后面 entry 更新，甚至造成连锁更新。
3.4 quicklist
3.4.1 结构说明
typedef struct quicklist {
quicklistNode *head; -- 列表头节点
quicklistNode *tail; -- 列表尾节点
unsigned long count; -- 所有 ziplist 加起来的 entry 元素统计
unsigned long len; -- quicklistNode的数量
int fill : 16; -- 单个节点的填充因子，对应 list-max-ziplist-size 参数配置
-- 用于指定每个ziplist节点允许的最大大小或最大元素数。
unsigned int compress；-- 压缩深度设置，对应 list-compress-depth 参数配置
-- 压缩深度：是指quicklist压缩中，需要从两侧排除的ziplist节点数量
-- 0：禁止所有压缩
-- 1：除去head 和 tail，其他节点都压缩
-- 2：除去head or head->next or tail->prev or tail，其他都压缩
-- N：除去 quicklist 两侧 N 个节点，其他压缩
} quicklist;
3.4.2 版本说明
- v3.2以前，当 List 数据类型，在同时满足以下两个条件时，使用 ziplist 编码，否则使用双向链表的编码方式。
① 列表对象保存的所有字符串元素的长度都小于64字节
② 列表对象保存的元素数量小于512个 - v3.2以后，统一用 quicklist 来存储 List 列表对象，quicklist 是一个双向链表，每个节点都是一个 ziplist。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。
3.5 哈希表
3.5.1 结构说明
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
dictEntry **table; -- 哈希表数组
unsigned long size; --哈希表大小
unsigned long sizemask; -- 哈希表大小掩码，用于计算索引值，值为 size-1
-- 掩码：指是一串用于与目标数据进行按位操作的二进制数字
unsigned long used; -- 数组已使用的位置
} dictht;
3.5 跳表
3.5.1 跳表原理：
-
有序链表：对于一个有序的单链表来讲，如果我们要想在其中查找某个数据，只能从头到尾遍历链表。查找效率就比较低，时间复杂度为是 O(n)。
- 跳表结构：一个有序链表加多层级索引的结构。跳表支持快速插入、删除、查找操作，时间复杂度都是 O(logn)，可以替代红黑树的应用场景。优点是实现简单，缺点是建立多级索引的空间消耗。
-
元素查找：以图中所示为例，查找温度为 25 摄氏度的城市。当然，案例比较简单，只是说明查找方式。当节点数据量比较多，以及层数越高时，查询效率提升很明显。
1. 最高层遍历
先从第一个节点（haerbin/5）和最高索引层（第四层）遍历。
当遍历到（haikou/30）时，发现 30 > 25，然后跳到第三个索引层进行遍历。
2. 第三层遍历
从（haerbin/5），下降到第三层后，遍历到（hangzhou/20），20 < 25 ，继续遍历。
当遍历到（haikou/30）时，30 > 25，确认范围在（hangzhou/20）和（haikou/30）两个节点之内。
3. 第二层遍历
下降到第二层，从（hangzhou/20）节点开始遍历，遍历到（shanghai/21），21 < 25，继续遍历，
当遍历到（haikou/30）时，30 > 25，然后确认，找的范围就在（shanghai/21）和 （haikou/30）两个节点之内。
4. 第一层遍历
下降到第一层，从（shanghai/21）开始遍历，就找到了（guangzhou/25）节点。
3.5.2 Redis跳表实现
3.5.2.1 跳表对象（zskiplist）
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
*header：头指针 header，查找表头的时间复杂度为O(1)。
*tail：尾部指针，查找表尾的时间复杂度为O(1)。
length：节点长度 length，不包含表头节点。图中的 length 为 7。
level：所有节点层数最大的 level，不包含表头节点。图中的 level 为 4。
3.5.2.2 数据节点（zskiplistNode）
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
- sds：字符串对象，存储的实际数据。图中存储的是，城市名称的SDS字符串对象。
- score：分值，节点按各自所保存的分值从小到大排列。如果分值相同，则按照成员变量在字典序中的顺序进行排序。图中，分值即为温度的数值，元素也是按照温度从低到高进行排序的。
- backward：后退指针，每次只能后退至前一个节点。Redis可以首先通过跳跃表的tail指针访问表尾节点，然后，向表头遍历元素。
- level [] ：level数组。
3.5.2.3 level 数组对象（zskiplistLevel）
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
-
数组对象
① level 数组的每个元素对象为 zskiplistLevel。zskiplistLevel 对象有一个指向其他节点的指针（*forward），以及与其他节点间的跨度（span）。
② 图中，level [] 数组对象下面的方框（中间一个点），代表一个zskiplistLevel对象。后面的箭头，代表指向节点的指针，上面的数字，代表的是到这个节点的跨度值。每一层所有的跨度值，加起来都等于数据节点（zskiplistNode）的数目。 -
跨度。
这是Redis的跳跃表，与普通跳跃表的区别之一。Redis 借助于该属性，可以获取元素在集合中的排名。原理就是，在查找某个节点的过程中，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳跃表中的排位。例如，zrank命令，获取hangzhou温度的排位值（第 1 位从 0 开始计数）。
127.0.0.1:6379> zrank schzset0416 hangzhou
(integer) 3
- 数组大小：每次创建一个新节点的时候，随机生成一个介于 1 到 32 之间的值作为 level 数组的大小，也即，层的高度。第一层，为 level [0]，第二层是 level [1]，以此类推。图中，hangzhou对应的Node的数组大小为 3 。Head 节点，初始化的时候，层高默认为 32。
3.5 整数数组
3.5.1 结构说明
typedef struct intset {
uint32_t encoding; -- 编码方式
uint32_t length; -- 集合包含的元素数量
int8_t contents[]; -- 保存元素的数组，虽然 contents 属性声明为 int8_t 类型的数组
-- 但在实际应用中，取决于 encoding 属性的值。
-- 对应 contents 有 int16_t，int32_t，int64_t 三种类型的值
} intset;
- 当我们将一个新元素添加到整数集合里面时，并且该新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级(upgrade)，然后才能将新元素添加到整数集合里面。例如int16_t 类型升级为 int32_t 类型。
- 整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。
3.5.2 简单测试
-
int16_t测试
-- 插入三个元素 127.0.0.1:6379> sadd schsetnumber 1 2 3 (integer) 3 127.0.0.1:6379> object encoding schsetnumber "intset" -- 用redis-rdb-tools 查看对象占用内存 #redis-memory-for-key schsetnumber Key schsetnumber Bytes 70 Type set Encoding intset Number of Elements 3 Length of Largest Element 8 -- 127.0.0.1:6379> sadd schsetnumber 4 (integer) 1 #redis-memory-for-key schsetnumber Key schsetnumber Bytes 72 Type set Encoding intset Number of Elements 4 Length of Largest Element 8由此推算出contents数组类型为int16_t。
-
int32_t测试
-- int16_t能表示的最大数为65535，我们添加一个新元素 70000 127.0.0.1:6379> sadd schsetnumber 70000 (integer) 3 -- 查看对象占用内存 #redis-memory-for-key schsetnumber Key schsetnumber Bytes 84 Type set Encoding intset Number of Elements 5 Length of Largest Element 8由此推算出 contents 数组类型为 int32_t：（72 - 4 * 2 ）+ 5 * 4 = 84
-
int64_t测试
-- int64_t 能表示的最大数为 2 147 483 647，再插入一个元素，2 147 483 650 127.0.0.1:6379> sadd schsetnumber 2147483650 (integer) 1 -- 查看对象占用内存 #redis-memory-for-key schsetnumber Key schsetnumber Bytes 112 Type set Encoding intset Number of Elements 6 Length of Largest Element 8由此推算出contents数组类型为 int64_t：（84 - 5 * 4 ）+ 6 * 8 = 112
-
降级测试
127.0.0.1:6379> sadd schsetnumber 5 (integer) 1 #redis-memory-for-key schsetnumber Key schsetnumber Bytes 120 Type set Encoding intset Number of Elements 7 Length of Largest Element 8对象长度为：112 + 1 * 8 = 120
参考资料
- 《Redis 设计与实现》
- 官网文档：https://redis.io/documentation
- github：https://github.com/redis/redis
