Redis专题2Redis数据结构底层探秘

jiezi

6 年前

上篇文章 Redis 闲谈（1）：构建知识图谱介绍了 redis 的基本概念、优缺点以及它的内存淘汰机制，相信大家对 redis 有了初步的认识。互联网的很多应用场景都有着 Redis 的身影，它能做的事情远远超出了我们的想像。Redis 的底层数据结构到底是什么样的呢，为什么它能做这么多的事情？本文将探秘 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 存储数据时，会选择大小最合适的内存块进行存储。

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

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

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

127.0.0.1:6379> set name tom
OK
127.0.0.1:6379> object encoding name
"embstr"

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

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 种了。

https://redis.io/topics/data-types-intro

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

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

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

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

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

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte[] content; // 数组内容}

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

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

int 编码：保存的是可以用 long 类型表示的整数值。
raw 编码：保存长度大于 44 字节的字符串（redis3.2 版本之前是 39 字节，之后是 44 字节）。
embstr 编码：保存长度小于 44 字节的字符串（redis3.2 版本之前是 39 字节，之后是 44 字节）。

设置一个值测试一下：

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

embstr 编码的结构:

raw 编码的结构：

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

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

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

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

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 占用字节大小计算

旧版本：

struct SDS {
    unsigned int capacity; // 4byte
    unsigned int len; // 4byte
    byte[] content; // 内联数组，长度为 capacity}

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

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

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

新版本：

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 中内存的优化。

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

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

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

当一个列表中只包含少量列表项，且是小整数值或长度比较短的字符串时，redis 就使用 ziplist（压缩列表）来做列表键的底层实现。

测试：

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

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

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

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

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

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

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)

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 都不压缩。

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

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

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

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

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

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

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

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

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

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 的数据结构为：

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];} intset;

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

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

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

跳跃列表，顾名思义是可以跳的，跳着查询自己想要查到的元素。大家可能对这种数据结构比较陌生，虽然平时接触的少，但它确实 是一个各方面性能都很好的数据结构，可以支持快速的查询、插入、删除操作，开发难度也比红黑树要容易的多。

为什么跳表有如此高的性能呢？它究竟是如何“跳”的呢？跳表利用了二分的思想，在数组中可以用二分法来快速进行查找，在链表中也是可以的。

举个例子，链表如下：

假设要找到 10 这个节点，需要一个一个去遍历，判断是不是要找的节点。那如何提高效率呢？mysql 索引相信大家都很熟悉，可以提高效率，这里也可以使用索引。抽出一个索引层来：

这样只需要找到 9 然后再找 10 就可以了，大大节省了查找的时间。

还可以再抽出来一层索引，可以更好地节约时间:

这样基于链表的“二分查找”支持快速的插入、删除，时间复杂度都是 O(logn)。

由于跳表的快速查找效率，以及实现的简单、易读。所以 Redis 放弃了红黑树而选择了更为简单的跳表。

Redis 中的跳跃表：

typedef struct zskiplist {
     // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
 } zskiplist;
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
     // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
         // 跨度 --- 前进指针所指向节点与当前节点的距离
        unsigned int span;
    } level[];} zskiplistNode;

zadd—zslinsert— 平均 O(logN), 最坏 O(N)

zrem—zsldelete— 平均 O(logN), 最坏 O(N)

zrank–zslGetRank— 平均 O(logN), 最坏 O(N)

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

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

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

作者：杨亨

拓展阅读：Redis 闲谈（1）：构建知识图谱

来源：宜信技术学院

Redis专题2Redis数据结构底层探秘

前言

一、Redis 的数据模型

二、Redis 支持的数据结构

2.1 string 字符串

raw 类型和 embstr 类型对比

2.2 List

ziplist 压缩列表

双端列表（linkedlist）

快速列表（quicklist）

2.3 Hash

Redis 中的字典

2.4 Set

2.5 Zset

跳表

总结