Redis 为什么这么快？

Redis 内部做了非常多的性能优化，比较重要的有下面 3 点：

Redis 基于内存，内存的访问速度是磁盘的上千倍；
Redis 基于 Reactor 模式设计开发了一套高效的事件处理模型，主要是单线程事件循环和 IO 多路复用（Redis 线程模式后面会详细介绍到）；
Redis 内置了多种优化过后的数据结构实现，性能非常高。

下面这张图片总结的挺不错的，分享一下，出自 Why is Redis so fast? 。

why-redis-so-fast (1).png

下面我们会深入讲解数据结构模块

Redis 常用的数据结构有哪些？

5 种基础数据结构：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。
3 种特殊数据结构：HyperLogLogs（基数统计）、Bitmap （位存储）、Geospatial (地理位置)。

Redis 5 种基本数据结构详解

redis 共有 5 种基本数据结构：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。

这 5 种数据结构是直接提供给用户使用的，是数据的保存形式，其底层实现主要依赖这 8 种数据结构：简单动态字符串（SDS）、LinkedList（双向链表）、Hash Table（哈希表）、SkipList（跳跃表）、Intset（整数集合）、ZipList（压缩列表）、QuickList（快速列表）。

Redis 基本数据结构的底层数据结构实现如下：

String	List	Hash	Set	Zset
SDS	LinkedList/ZipList/QuickList	Hash Table、ZipList	ZipList、Intset	ZipList、SkipList

Redis 3.2 之前，List 底层实现是 LinkedList 或者 ZipList。 Redis 3.2 之后，引入了 LinkedList 和 ZipList 的结合 QuickList，List 的底层实现变为 QuickList。

你可以在 Redis 官网上找到 Redis 数据结构非常详细的介绍：

redis数据结构实现.png

未来随着 Redis 新版本的发布，可能会有新的数据结构出现，通过查阅 Redis 官网对应的介绍，你总能获取到最靠谱的信息。

String（字符串）

介绍

String 是 Redis 中最简单同时也是最常用的一个数据结构。

String 是一种二进制安全的数据结构，可以用来存储任何类型的数据比如字符串、整数、浮点数、图片（图片的 base64 编码或者解码或者图片的路径）、序列化后的对象。

虽然 Redis 是用 C 语言写的，但是 Redis 并没有使用 C 的字符串表示，而是自己构建了一种 简单动态字符串（Simple Dynamic String，SDS）。相比于 C 的原生字符串，Redis 的 SDS 不光可以保存文本数据还可以保存二进制数据，并且获取字符串长度复杂度为 O(1)（C 字符串为 O(N)）,除此之外，Redis 的 SDS API 是安全的，不会造成缓冲区溢出。

# 常用命令

命令	介绍
SET key value	设置指定 key 的值
SETNX key value	只有在 key 不存在时设置 key 的值
GET key	获取指定 key 的值
MSET key1 value1 key2 value2 …	设置一个或多个指定 key 的值
MGET key1 key2 …	获取一个或多个指定 key 的值
STRLEN key	返回 key 所储存的字符串值的长度
INCR key	将 key 中储存的数字值增一
DECR key	将 key 中储存的数字值减一
EXISTS key	判断指定 key 是否存在
DEL key（通用）	删除指定的 key
EXPIRE key seconds（通用）	给指定 key 设置过期时间

应用场景

需要存储常规数据的场景

举例：缓存 session、token、图片地址、序列化后的对象(相比较于 Hash 存储更节省内存)。
相关命令：SET、GET。

需要计数的场景

举例：用户单位时间的请求数（简单限流可以用到）、页面单位时间的访问数。
相关命令：SET、GET、 INCR、DECR 。

分布式锁

利用 SETNX key value 命令可以实现一个最简易的分布式锁（存在一些缺陷，通常不建议这样实现分布式锁）。

String 还是 Hash 存储对象数据更好呢？

String 存储的是序列化后的对象数据，存放的是整个对象。Hash 是对对象的每个字段单独存储，可以获取部分字段的信息，也可以修改或者添加部分字段，节省网络流量。如果对象中某些字段需要经常变动或者经常需要单独查询对象中的个别字段信息，Hash 就非常适合。
String 存储相对来说更加节省内存，缓存相同数量的对象数据，String 消耗的内存约是 Hash 的一半。并且，存储具有多层嵌套的对象时也方便很多。如果系统对性能和资源消耗非常敏感的话，String 就非常适合。

在绝大部分情况，我们建议使用 String 来存储对象数据即可！

String 的底层实现是什么？

Redis 是基于 C 语言编写的，但 Redis 的 String 类型的底层实现并不是 C 语言中的字符串（即以空字符 \0 结尾的字符数组），而是自己编写了 SDS（Simple Dynamic String，简单动态字符串）来作为底层实现。

SDS 最早是 Redis 作者为日常 C 语言开发而设计的 C 字符串，后来被应用到了 Redis 上，并经过了大量的修改完善以适合高性能操作。

Redis7.0 的 SDS 的部分源码如下（github.com/redis/redis…

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

通过源码可以看出，SDS 共有五种实现方式 SDS_TYPE_5（并未用到）、SDS_TYPE_8、SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64，其中只有后四种实际用到。Redis 会根据初始化的长度决定使用哪种类型，从而减少内存的使用。

类型	字节	位
sdshdr5	< 1	<8
sdshdr8	1	8
sdshdr16	2	16
sdshdr32	4	32
sdshdr64	8	64

对于后四种实现都包含了下面这 4 个属性：

len：字符串的长度也就是已经使用的字节数
alloc：总共可用的字符空间大小，alloc-len 就是 SDS 剩余的空间大小
buf[]：实际存储字符串的数组
flags：低三位保存类型标志

SDS 相比于 C 语言中的字符串有如下提升：

可以避免缓冲区溢出：C 语言中的字符串被修改（比如拼接）时，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。SDS 被修改时，会先根据 len 属性检查空间大小是否满足要求，如果不满足，则先扩展至所需大小再进行修改操作。
获取字符串长度的复杂度较低：C 语言中的字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。SDS 的长度获取直接读取 len 属性即可，时间复杂度为 O(1)。
减少内存分配次数：为了避免修改（增加/减少）字符串时，每次都需要重新分配内存（C 语言的字符串是这样的），SDS 实现了空间预分配和惰性空间释放两种优化策略。当 SDS 需要增加字符串时，Redis 会为 SDS 分配好内存，并且根据特定的算法分配多余的内存，这样可以减少连续执行字符串增长操作所需的内存重分配次数。当 SDS 需要减少字符串时，这部分内存不会立即被回收，会被记录下来，等待后续使用（支持手动释放，有对应的 API）。
二进制安全：C 语言中的字符串以空字符 \0 作为字符串结束的标识，这存在一些问题，像一些二进制文件（比如图片、视频、音频）就可能包括空字符，C 字符串无法正确保存。SDS 使用 len 属性判断字符串是否结束，不存在这个问题。

很多文章里 SDS 的定义是下面这样的：

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

这个也没错，Redis 3.2 之前就是这样定义的。后来，由于这种方式的定义存在问题，len 和 free 的定义用了 4 个字节，造成了浪费。Redis 3.2 之后，Redis 改进了 SDS 的定义，将其划分为了现在的 5 种类型。

List（列表）

# 介绍

Redis 中的 List 其实就是链表数据结构的实现。

许多高级编程语言都内置了链表的实现比如 Java 中的 LinkedList，但是 C 语言并没有实现链表，所以 Redis 实现了自己的链表数据结构。Redis 的 List 的实现为一个 双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销。

# 常用命令

命令	介绍
RPUSH key value1 value2 …	在指定列表的尾部（右边）添加一个或多个元素
LPUSH key value1 value2 …	在指定列表的头部（左边）添加一个或多个元素
LSET key index value	将指定列表索引 index 位置的值设置为 value
LPOP key	移除并获取指定列表的第一个元素(最左边)
RPOP key	移除并获取指定列表的最后一个元素(最右边)
LLEN key	获取列表元素数量
LRANGE key start end	获取列表 start 和 end 之间的元素

应用场景

信息流展示

举例：最新文章、最新动态。
相关命令：LPUSH、LRANGE。

消息队列

Redis List 数据结构可以用来做消息队列，只是功能过于简单且存在很多缺陷，不建议这样做。

相对来说，Redis 5.0 新增加的一个数据结构 Stream 更适合做消息队列一些，只是功能依然非常简陋。和专业的消息队列相比，还是有很多欠缺的地方比如消息丢失和堆积问题不好解决。

list 的底层实现是什么？

上面说到 List 底层实现是 LinkedList 或者 ZipList。 Redis 3.2 之后，引入了 LinkedList 和 ZipList 的结合 QuickList，List 的底层实现变为 QuickList。

为何弄了这么多数据结构呀？

antirez 所做的这一切都是为了在内存空间开销与访问性能之间做取舍和平衡，跟着我去吃透每个类型的设计思想和不足，你就明白了。

linkedlist（双端列表）

redis链表实现.jpg

普通的 linkedlist 有 prev、next 两个指针，当存储数据很小的情况下，指针占用的空间会超过数据占用的空间，这就离谱了，是可忍孰不可忍。
linkedlist 是链表结构，在内存中不是连续的，遍历的效率低下。

ziplist（压缩列表）

为了解决上面两个问题，antirez 创造了 ziplist 压缩列表，是一种内存紧凑的数据结构，占用一块连续的内存空间，提升内存使用率。

当一个列表只有少量数据的时候，并且每个列表项要么是小整数值，要么就是长度比较短的字符串，那么我就会使用 ziplist 来做 List 的底层实现。

压缩列表结构webp.webp

Ziplist的特点

从上面的结构我们也比较容易就能看出Ziplist的结构特点：

结构紧凑，占用一块连续的内存空间，相对于Linkedlist，没有前项指针和后项指针，内存占用更小，不容易产生内存碎片
逆向遍历，ziplist中的元素只记录了前一个元素的长度。所以，在遍历查找的时候只能从尾部开始遍历查找；而插入元素时则只能从表头开始，找到对应的位置插入元素
连锁更新，同样因为ziplist中的元素只记录了前一个元素的长度，更新的时候，则会导致被更新的元素后续的元素都需要被移动或更新，最坏的时间复杂度为 Q(N2)
后期作者也读写连锁更新做了优化 Listpack——Ziplist的优化

分而治之QuickList——Ziplist + Linkedlist

我们可以参考二叉树的结构设计，顶层和索引层则采用Linkedlist来存储索引信息，采用Ziplist来存储真正存储元素数据。

顶层结构属性

所以，Quicklist最顶层结构属性如下：

struct quicklist {
    quicklistNode *head; // 头部索引节点的指针
    quicklistNode *tail; // 尾部索引节点的指针
    unsigned long count; // 所有元素个数
    unsigned int len; // 索引节点个数
    int fill; // 存储元素数据的ziplist大小
    unsigned int compress; // ziplist压缩深度
}

索引节点的结构属性

索引节点需要能够记录前后节点的指针，方便遍历；对应存储元素数据的ziplist的指针；ziplist存储的元素个数；ziplist大小用来判断是需要生成新的索引节点，还是直接向ziplist中插入数据。

其实Redis中Quicklist还考虑到了数据压缩的场景，这里则需要记录数据是否被压缩。

所以，索引节点quicklistNode的结构属性如下：

struct quicklistNode {
    struct quicklistNode *prev;     //前驱节点指针
    struct quicklistNode *next;     //后继节点指针
    unsigned char *zl; // 节点的ziplist索引
    unsigned int sz; // 节点中ziplist的字节数
    unsigned int count;  // 节点中存储的元素个数
    unsigned int encoding; // 表示表示节点是否被压缩
    unsigned int container; // 表示节点存储的数据结构类型
    unsigned int recompress; // 是否被压缩
    unsigned int attempted_compress; // 是否尝试过压缩
    unsigned int extra; // 预留扩展空间
}

内存中的结构

根据以上的结构属性，我们可以得出quicklist在内存中的结构：

特点

从上面的结构中我们可以看出，quick同时结合了Linkedlist和Ziplist的优点，当存储元素较多时也能保持良好的性能表现。当quicklist进行数据更新时，避免了整个list的元素的连锁更新。连锁更新只会在单个节点上发生。

总结

Quicklist是Redis针对List存储元素较多的场景时设计，同时结合了Linkedlist和Ziplist的优点，避免了整个list的元素的连锁更新，当存储元素较多时也能保持良好的性能表现。

Hash（哈希）

# 介绍

Redis 中的 Hash 是一个 String 类型的 field-value（键值对）的映射表，特别适合用于存储对象，后续操作的时候，你可以直接修改这个对象中的某些字段的值。

Hash 类似于 JDK1.8 前的 HashMap，内部实现也差不多(数组 + 链表)。不过，Redis 的 Hash 做了更多优化。

# 常用命令

命令	介绍
HSET key field value	设置指定哈希表中指定字段的值
HSETNX key field value	只有指定字段不存在时设置指定字段的值
HMSET key field1 value1 field2 value2 …	同时将一个或多个 field-value (域-值)对设置到指定哈希表中
HGET key field	获取指定哈希表中指定字段的值
HMGET key field1 field2 …	获取指定哈希表中一个或者多个指定字段的值
HGETALL key	获取指定哈希表中所有的键值对
HEXISTS key field	查看指定哈希表中指定的字段是否存在
HDEL key field1 field2 …	删除一个或多个哈希表字段
HLEN key	获取指定哈希表中字段的数量
HINCRBY key field increment	对指定哈希中的指定字段做运算操作（正数为加，负数为减）

应用场景

对象数据存储场景

举例：用户信息、商品信息、文章信息、购物车信息。
相关命令：HSET （设置单个字段的值）、HMSET（设置多个字段的值）、HGET（获取单个字段的值）、HMGET（获取多个字段的值）。

Hash 的底层实现是什么？

1. 压缩列表（Ziplist）

当Hash类型的元素数量和单个元素的大小都较小的时候，Redis会选择ziplist作为存储结构。ziplist是一个特殊的线性表，它能够在空间效率和查询效率之间取得良好的平衡。

2. 哈希表（Hashtable）

当Hash类型的元素数量较大，或者单个元素的大小较大的时候，Redis会使用hashtable作为存储结构。Hashtable的查询效率非常高，但是空间效率较低。

redishash结构.png

Set（集合）

# 介绍

Redis 中的 Set 类型是一种无序集合，集合中的元素没有先后顺序但都唯一，有点类似于 Java 中的 HashSet 。当你需要存储一个列表数据，又不希望出现重复数据时，Set 是一个很好的选择，并且 Set 提供了判断某个元素是否在一个 Set 集合内的重要接口，这个也是 List 所不能提供的。

你可以基于 Set 轻易实现交集、并集、差集的操作，比如你可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。这样的话，Set 可以非常方便的实现如共同关注、共同粉丝、共同喜好等功能。这个过程也就是求交集的过程。

# 常用命令

命令	介绍
SADD key member1 member2 …	向指定集合添加一个或多个元素
SMEMBERS key	获取指定集合中的所有元素
SCARD key	获取指定集合的元素数量
SISMEMBER key member	判断指定元素是否在指定集合中
SINTER key1 key2 …	获取给定所有集合的交集
SINTERSTORE destination key1 key2 …	将给定所有集合的交集存储在 destination 中
SUNION key1 key2 …	获取给定所有集合的并集
SUNIONSTORE destination key1 key2 …	将给定所有集合的并集存储在 destination 中
SDIFF key1 key2 …	获取给定所有集合的差集
SDIFFSTORE destination key1 key2 …	将给定所有集合的差集存储在 destination 中
SPOP key count	随机移除并获取指定集合中一个或多个元素
SRANDMEMBER key count	随机获取指定集合中指定数量的元素

应用场景

需要存放的数据不能重复的场景

举例：网站 UV 统计（数据量巨大的场景还是 HyperLogLog更适合一些）、文章点赞、动态点赞等场景。
相关命令：SCARD（获取集合数量）。

需要获取多个数据源交集、并集和差集的场景

举例：共同好友(交集)、共同粉丝(交集)、共同关注(交集)、好友推荐（差集）、音乐推荐（差集）、订阅号推荐（差集+交集）等场景。
相关命令：SINTER（交集）、SINTERSTORE （交集）、SUNION （并集）、SUNIONSTORE（并集）、SDIFF（差集）、SDIFFSTORE （差集）。

需要随机获取数据源中的元素的场景

举例：抽奖系统、随机点名等场景。
相关命令：SPOP（随机获取集合中的元素并移除，适合不允许重复中奖的场景）、SRANDMEMBER（随机获取集合中的元素，适合允许重复中奖的场景）。

set 的底层实现是什么？

Set 的编码有2种：INTSET 和 HASHTABLE(HT)。当集合中所有的元素都是整数，并且个数不超过512时，采用 INTSET 编码，否则采用 HASHTABLE(HT) 编码

Sorted Set（有序集合）

# 介绍

Sorted Set 类似于 Set，但和 Set 相比，Sorted Set 增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列，还可以通过 score 的范围来获取元素的列表。有点像是 Java 中 HashMap 和 TreeSet 的结合体。

# 常用命令

命令	介绍
ZADD key score1 member1 score2 member2 …	向指定有序集合添加一个或多个元素
ZCARD KEY	获取指定有序集合的元素数量
ZSCORE key member	获取指定有序集合中指定元素的 score 值
ZINTERSTORE destination numkeys key1 key2 …	将给定所有有序集合的交集存储在 destination 中，对相同元素对应的 score 值进行 SUM 聚合操作，numkeys 为集合数量
ZUNIONSTORE destination numkeys key1 key2 …	求并集，其它和 ZINTERSTORE 类似
ZDIFFSTORE destination numkeys key1 key2 …	求差集，其它和 ZINTERSTORE 类似
ZRANGE key start end	获取指定有序集合 start 和 end 之间的元素（score 从低到高）
ZREVRANGE key start end	获取指定有序集合 start 和 end 之间的元素（score 从高到底）
ZREVRANK key member	获取指定有序集合中指定元素的排名(score 从大到小排序)

应用场景

需要随机获取数据源中的元素根据某个权重进行排序的场景

举例：各种排行榜比如直播间送礼物的排行榜、朋友圈的微信步数排行榜、王者荣耀中的段位排行榜、话题热度排行榜等等。
相关命令：ZRANGE (从小到大排序)、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)。
需要存储的数据有优先级或者重要程度的场景 比如优先级任务队列。
举例：优先级任务队列。
相关命令：ZRANGE (从小到大排序)、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)。

Zset 的底层实现是什么？

Zset的编码实现有2种：SKIPLIST(跳跃列表)+ HT(哈希表) 结合、ZIPLIST(压缩列表，6版本之前)或LISTPACT(6版本之后) 。当有序集合的元素个数小于128，每个元素都小于64字节时，采用ZIPLIST编码，否则采用 ZIPLIST(压缩列表)+ HT(哈希表) 结合的编码。LISTPACK编码上面已经讲解过

redis调表.png

源码结构( tag 6.2.8)：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

从结构图和源码可知，每个kv对应 zskiplistNode 结构，其实 sds 存储集合元素，score 表示分数，backward 指向后向一个节点，通过这个可以反向遍历，zskiplistLevel 数组，存储多层的指向前向节点的指针以及跨度span（用于计算节点的排名）

跳表是空间换时间的思想，通过构建多级索引，实现基于链表层面的 “二分查找“（当构建索引的节点为多个时，还可实现多分查找）。跳表是一种动态的数据结构，支持快速查询以进行插入，更新和删除操作，时间复杂度为 O(logn)，空间复杂度为 O(n)。

redisObject

redis 是KV(key-value pair)存储，不管是K还是V，底层都是对象（object 组成）的，其中K是一个字符串对象(string object)，V 分别有我们常听说的5种数据类型，分别是字符串(String)、列表(List)、哈希(Hash)、集合(Set)、有序集合(Zset)。不过是K还是V，底层都是用 redisObject 数据结构表示，如下：
redisObject 数据结构表示，如下：

struct redisObject {
    unsigned type:4;//4 bit
    unsigned encoding:4;//4 bit
    //24 bit=3byte
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    
    int refcount;//4byte
    void *ptr;//8type
};

其中 type 表示对象的类型，分别有 REDIS_STRING(字符串)，REDIS_LIST(列表)，REDIS_HASH(哈希)，REDIS_SET(集合对象)，REDIS_ZSET(有序集合)；

encoding 字段表示底层的编码实现，因为每种数据类型其实底层实现数据结构至少有2种，根据不同的条件选择不同的数据结构，而且会根据条件的变化升级或者更换数据结构，最终的目的是尽可能压缩存储和提升效率

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END

# 数据结构 # Redis

Redis 数据结构底层讲解（1）-5 种基本数据结构

Redis 为什么这么快？

Redis 常用的数据结构有哪些？

Redis 5 种基本数据结构详解

String（字符串）

介绍

# 常用命令

应用场景

String 还是 Hash 存储对象数据更好呢？

String 的底层实现是什么？

List（列表）

# 介绍

# 常用命令

应用场景

list 的底层实现是什么？

linkedlist（双端列表）

ziplist（压缩列表）

Ziplist的特点

分而治之QuickList——Ziplist + Linkedlist

顶层结构属性

索引节点的结构属性

内存中的结构

特点

总结

Hash（哈希）

# 介绍

# 常用命令

应用场景

Hash 的底层实现是什么？

Set（集合）

# 介绍

# 常用命令

应用场景

set 的底层实现是什么？

Sorted Set（有序集合）

# 介绍

# 常用命令

应用场景

Zset 的底层实现是什么？

redisObject