Redis-基础篇-①数据结构

学习核心

• Redis 核心基础 - 数据结构
  • 特性、实现、时间复杂度等各种操作
  • 热点：跳表、字典

学习资料

• Redis 数据结构
• 深入理解Redis跳跃表的基本实现和特性
• Redis 对象 学习资料

Redis Object

什么是Obejct？

​ Redis是key-value存储，key和value在Redis中都被抽象为对象，key只能是String对象，而Value支持丰富的对象种类，包括String、List、Set、Hash、Sorted Set、Stream等基础类型。

Object在内存中的定义

// from Redis 5.0.5
#define LRU BITS 24
typedef struct redisobject {
  unsigned type:4;
  unsigned encoding:4;
  unsigned lru:LRU BITS; /* LRU time or LFU data */
  int refcount;
  void *ptr;
} robj;

• type：是哪种Redis对象
• encoding：表示用哪种底层编码，用OBJECT ENCODING 「key] 可以看到对应的编码方式
• lru：记录对象访问信息，用于内存淘汰
• refcount：引用计数，用来描述有多少个指针，指向该对象
• ptr：内容指针，指向实际内容

对象与数据结构

​ 实际操作的主要有6个Redis对象，其底层依赖一些数据结构，包括字符串、跳表、哈希表、压缩列表、双端链表等，不同对象可能有依赖相同数据结构。在Redis学习中考虑实践优先于原理，先熟悉对象操作，再相应研究其底层结构实现，做相应的关联学习，理解记忆

Redis 基础类型

Redis 数据类型

​ Redis 提供了5种基本数据类型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。随着Redis的迭代升级，后又支持4种数据类型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）

​ 实践时可通过本机安装Redis或者Redis官网提供的在线Redis环境来敲命令

​ 学习Redis数据类型的时候可以从介绍、内部实现、常用命令、应用场景4个方面分别切入各个Redis数据类型的学习

Redis 数据类型应用

Redis 随着版本的升级，其数据类型和对应底层数据结构的实现也有所不同。理解每个基础类型的底层实现、基础应用和相应的业务场景：

• String 类型的应用场景：缓存对象、常规计数、分布式锁、共享session信息等；
• List 类型的应用场景：消息队列（有两个问题：1. 生产者需要自行实现全局唯一 ID；2. 不能以消费组形式消费数据）等；
• Hash 类型：缓存对象、购物车等；
• Set 类型：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等；
• Zset 类型：排序场景，比如排行榜、电话和姓名排序等；

​ Redis 后续版本又支持四种数据类型，它们的应用场景如下：

• BitMap（2.2 版新增）：二值状态统计的场景，比如签到、判断用户登陆状态、连续签到用户总数等；
• HyperLogLog（2.8 版新增）：海量数据基数统计的场景，比如百万级网页 UV 计数等；
• GEO（3.2 版新增）：存储地理位置信息的场景，比如滴滴叫车；
• Stream（5.0 版新增）：消息队列，相比于基于 List 类型实现的消息队列，有这两个特有的特性：自动生成全局唯一消息ID，支持以消费组形式消费数据；

​ 此外，针对消息队列的实现可以用Redis的List、Stream实现，结合消息队列实现的要素拆解其实现的核心，以及相应的优化场景

消息队列实现核心	基于List实现	基于Stream实现
消息保序	使用 LPUSH + RPOP	XADD/XREAD
阻塞读取	使用 BRPOP （队列为空阻塞消费者的读取操作，以减少CPU一直循环读取的性能损耗）	XREAD block
重复消息处理	生产者自行实现全局唯一 ID	Stream 在使用 XADD 命令，会自动生成全局唯一 ID；
消息的可靠性	使用 BRPOPLPUSH （读取消息时附带留存备份，当出现异常宕机的情况可从备份List中获取消息重新消费）	内部使用 PENDING List 自动保存消息，使用 XPENDING 命令查看消费组已经读取但是未被确认的消息，消费者使用 XACK 确认消息；
同一条消息可否多次消费	不支持	支持消费组形式消费数据

1.String

介绍

​ String 是最基本的 key-value 结构，key 是唯一标识，value 是具体的值，value其实不仅是字符串， 也可以是数字（整数或浮点数），value 最多可以容纳的数据长度是 512M

内部实现

String 底层实现

​ String 类型的底层的数据结构实现主要是 int 和 SDS（简单动态字符串）。SDS 和 C 字符串不太一样，之所以没有使用 C 语言的字符串表示，因为 SDS 相比于 C 的原生字符串：

• SDS 不仅可以保存文本数据，还可以保存二进制数据
  • 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，并且 SDS 的所有 API 都会以处理二进制的方式来处理 SDS 存放在 buf[] 数组里的数据；
  • 所以 SDS 不光能存放文本数据，而且能保存图片、音频、视频、压缩文件这样的二进制数据；
• SDS 获取字符串长度的时间复杂度是 O(1)
  • 因为 C 语言的字符串并不记录自身长度，所以获取长度的复杂度为 O(n)；
  • 而 SDS 结构里用 len 属性记录了字符串长度，所以复杂度为 O(1)；
• Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出
  • 因为 SDS 在拼接字符串之前会检查 SDS 空间是否满足要求，如果空间不够会自动扩容，所以不会导致缓冲区溢出的问题

字符串对象的内部编码（encoding）有 3 种 ：int、raw和 embstr。

• 如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成 long），并将字符串对象的编码设置为int
• 如果字符串对象保存的是一个字符串，并且这个字符申的长度小于等于 32 字节（redis 2.+版本），那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串，并将对象的编码设置为embstr， embstr编码是专门用于保存短字符串的一种优化编码方式
• 如果字符串对象保存的是一个字符串，并且这个字符串的长度大于 32 字节（redis 2.+版本），那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串，并将对象的编码设置为raw

​ embstr 编码和 raw 编码的边界在 redis 不同版本中是不一样的：

• redis 2.+ 是 32 字节
• redis 3.0-4.0 是 39 字节
• redis 5.0 是 44 字节

​ embstr和raw编码都会使用SDS来保存值，但不同之处在于embstr会通过一次内存分配函数来分配一块连续的内存空间来保存redisObject和SDS，而raw编码会通过调用两次内存分配函数来分别分配两块空间来保存redisObject和SDS。Redis这样做会有很多好处：

• embstr编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次；
• 释放 embstr编码的字符串对象同样只需要调用一次内存释放函数；
• 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面可以更好的利用 CPU 缓存提升性能。

但是 embstr 也有缺点的：

• 如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间，所以embstr编码的字符串对象实际上是只读的，redis没有为embstr编码的字符串对象编写任何相应的修改程序。当我们对embstr编码的字符串对象执行任何修改命令（例如append）时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令

常用命令

单个设定

# 设置 key-value 类型的值
> SET name haha
OK

# 根据 key 获得对应的 value
> GET name
"haha"

# 判断某个 key 是否存在
> EXISTS name
(integer) 1

# 返回 key 所储存的字符串值的长度
> STRLEN name
(integer) 4

# 删除某个 key 对应的值
> DEL name
(integer) 1

# 不存在就插入（not exists）
> SETNX key value
(integer) 1

批量处理

# 批量设置 key-value 类型的值
> MSET key1 value1 key2 value2 
OK

# 批量获取多个 key 对应的 value
> MGET key1 key2 
1) "value1"
2) "value2"

计数器

# 设置 key-value 类型的值
> SET number 0
OK

# 将 key 中储存的数字值加1
> INCR number
(integer) 1

# 将key中存储的数字值加10
> INCRBY number 10
(integer) 11

# 将 key 中储存的数字值减1
> DECR number
(integer) 10

# 将key中存储的数字值减10
> DECRBY number 10
(integer) 0

过期时间设定

# 设置 key 在 60 秒后过期（该方法是针对已经存在的key设置过期时间）
> EXPIRE name  60 
(integer) 1

# 查看数据还有多久过期
> TTL name 
(integer) 51

#设置 key-value 类型的值，并设置该key的过期时间为 60 秒
> SET key  value EX 60
OK

> SETEX key  60 value
OK

应用场景

（1）缓存对象

​ 使用 String 来缓存对象有两种方式：以缓存User对象为例（name、age属性）

• 方式1：直接缓存整个对象的 JSON（通过:进行分组）

  • 存储数据：SET user:1 '{"name":"holic-x", "age":18}'
  • 获取数据：GET user:1

• 方式2：采用将 key 进行分离为 user:ID:属性，采用 MSET 存储，用 MGET 获取各属性值

  • 存储数据：MSET user:2:name holic-x user:2:age 18 user:3:name 小黑 user:3:age 20
  • 获取数据：MGET user:2:name user:2:age

（2）常规计数

​ 因为Redis 处理命令是单线程，所以执行命令的过程是原子的。因此 String 数据类型适合计数场景，比如计算访问次数、点赞、转发、库存数量等

场景：计算文章的阅读量

# 初始化文章的阅读量
> SET aritcle:readcount:1001 0
OK

#阅读量+1
> INCR aritcle:readcount:1001
(integer) 1

#阅读量+1
> INCR aritcle:readcount:1001
(integer) 2

#阅读量+1
> INCR aritcle:readcount:1001
(integer) 3

# 获取对应文章的阅读量
> GET aritcle:readcount:1001
"3"

（3）分布式锁

​ 通过使用 SET 命令和 Lua 脚本在 Redis 单节点上完成了分布式锁的加锁和解锁

​ 分布式锁概念在MySQL高可用篇章的学习中有所扩展，其中提到使用Redis的SET命令来实现分布式锁：NX参数实现【key值不存在才插入】，并设定key的过期时间

SET lock_key unique_value NX PX 10000

• lock_key 就是 key 键；
• unique_value 是客户端生成的唯一的标识；
• NX 代表只在 lock_key 不存在时，才对 lock_key 进行设置操作；
• PX 10000 表示设置 lock_key 的过期时间为 10s，这是为了避免客户端发生异常而无法释放锁

​ 而解锁的过程就是将 lock_key 键删除，但不能乱删，要保证执行操作的客户端就是加锁的客户端。所以，解锁的时候，要先判断锁的 unique_value 是否为加锁客户端，是的话，才将 lock_key 键删除。解锁是有两个操作，这时就需要 Lua 脚本来保证解锁的原子性，因为 Redis 在执行 Lua 脚本时，可以以原子性的方式执行，保证了锁释放操作的原子性。

// 释放锁时，先比较 unique_value 是否相等，避免锁的误释放
if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

（4）共享session信息

​ 在传统的单系统应用中，例如开发后台管理系统时，会使用 Session 来保存用户的会话(登录)状态，这些 Session 信息会被保存在服务器端，但对于分布式系统而言这种模式并不使用。例如用户01的 Session 信息被存储在服务器1，但第二次访问时用户01被分配到服务器2，这个时候服务器并没有用户01的 Session 信息，就会出现需要重复登录的问题，问题在于分布式系统每次会把请求随机分配到不同的服务器。

​ 通过引入Redis对这些Session信息进行统一的存储和管理，则无论请求发送到哪台服务器，服务器都会去同一个Redis获取相关的Session信息，以解决分布式系统下Session存储问题，对比分析图示如下

2.Hash

介绍

​ Hash 是一个键值对（key - value）集合，其中 value 的形式如： value=[{field1，value1}，...{fieldN，valueN}]。Hash 特别适合用于存储对象

​ String与Hash存储对象的区别在于：

内部实现

Hash 类型的底层数据结构是由压缩列表或哈希表实现的：

• 如果哈希类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；
• 如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的 底层数据结构。

在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现。

常用命令

# 存储一个哈希表key的键值
HSET key field value   

# 获取哈希表key对应的field键值
HGET key field

# 在一个哈希表key中存储多个键值对
HMSET key field value [field value...] 

# 批量获取哈希表key中多个field键值
HMGET key field [field ...]       
# 删除哈希表key中的field键值
HDEL key field [field ...]    

# 返回哈希表key中field的数量
HLEN key       
# 返回哈希表key中所有的键值
HGETALL key 

# 为哈希表key中field键的值加上增量n
HINCRBY key field n     

应用场景

（1）缓存对象

​ Hash 类型的 （key，field， value） 的结构与对象的（对象id， 属性， 值）的结构相似，也可以用来存储对象。

以存储用户信息为例

HSET uid:1 name tom
HSET uid:1 age 23

SET uid:2:name tom 
SET uid:2:age 23 

​ String类型的应用场景中也有存储对象的应用（String+Json、String字段拆分），那么在存储对象的时候该作何选择？

=》一般对象用 String + Json 存储，对象中某些频繁变化的属性可以考虑抽出来用 Hash 类型存储

（2）购物车

​ 以用户 id 为 key，商品 id 为 field，商品数量为 value，恰好构成了购物车的3个要素。则购物车的实现涉及命令分析如下：

• 添加商品：HSET cart:{用户id} {商品id} 1
• 添加数量：HINCRBY cart:{用户id} {商品id} 1
• 商品总数：HLEN cart:{用户id}
• 删除商品：HDEL cart:{用户id} {商品id}
• 获取购物车所有商品：HGETALL cart:{用户id}

当前仅仅是将商品ID存储到了Redis 中，在回显商品具体信息的时候，还需要根据商品 id 查询一次数据库，获取完整的商品的信息

3.List

介绍

​ List 列表是简单的字符串列表，按照插入顺序排序，可以从头部或尾部向 List 列表添加元素。列表的最大长度为 2^32 - 1，也即每个列表支持超过 40 亿个元素

内部实现

List 类型的底层数据结构是由双向链表或压缩列表实现的：

• 如果列表的元素个数小于 512 个（默认值，可由 list-max-ziplist-entries 配置），列表每个元素的值都小于 64 字节（默认值，可由 list-max-ziplist-value 配置），Redis 会使用压缩列表作为 List 类型的底层数据结构；
• 如果列表的元素不满足上面的条件，Redis 会使用双向链表作为 List 类型的底层数据结构；

但是在 Redis 3.2 版本之后，List 数据类型底层数据结构就只由 quicklist 实现了，替代了双向链表和压缩列表

常用命令

# 将一个或多个值value插入到key列表的表头(最左边)，最后的值在最前面
LPUSH key value [value ...] 
# 将一个或多个值value插入到key列表的表尾(最右边)
RPUSH key value [value ...]
# 移除并返回key列表的头元素
LPOP key     
# 移除并返回key列表的尾元素
RPOP key 

# 返回列表key中指定区间内的元素，区间以偏移量start和stop指定，从0开始
LRANGE key start stop

# 从key列表表头弹出一个元素，没有就阻塞timeout秒，如果timeout=0则一直阻塞
BLPOP key [key ...] timeout
# 从key列表表尾弹出一个元素，没有就阻塞timeout秒，如果timeout=0则一直阻塞
BRPOP key [key ...] timeout

应用场景

（1）消息队列

​ 消息队列在存取消息时，必须要满足三个需求，分别是消息保序、处理重复的消息和保证消息可靠性。Redis 的 List 和 Stream 两种数据类型，就可以满足消息队列的这三个需求。此处拆解List如何实现消息队列

【1】如何满足消息保序需求？

​ List 本身就是按先进先出的顺序对数据进行存取的，满足消息保序的需求，List 可以使用 LPUSH + RPOP （或者反过来，RPUSH+LPOP）命令实现消息队列。

• 生产者使用 LPUSH key value[value...] 将消息插入到队列的头部，如果 key 不存在则会创建一个空的队列再插入消息。
• 消费者使用 RPOP key 依次读取队列的消息，先进先出

​

​ 不过，在消费者读取数据时，有一个潜在的性能风险点。在生产者往 List 中写入数据时，List 并不会主动地通知消费者有新消息写入，如果消费者想要及时处理消息，就需要在程序中不停地调用 RPOP 命令（比如使用一个while(1)循环）。如果有新消息写入，RPOP命令就会返回结果，否则，RPOP命令返回空值，再继续循环。所以，即使没有新消息写入List，消费者也要不停地调用 RPOP 命令，这就会导致消费者程序的 CPU 一直消耗在执行 RPOP 命令上，带来不必要的性能损失。

​ 为了解决这个问题，Redis提供了 BRPOP 命令。BRPOP命令也称为阻塞式读取，客户端在没有读到队列数据时，自动阻塞，直到有新的数据写入队列，再开始读取新数据。和消费者程序自己不停地调用RPOP命令相比，这种方式能节省CPU开销

【2】如何处理重复的消息？

消费者要实现重复消息的判断，需要 2 个方面的要求：

• 每个消息都有一个全局的 ID
• 消费者要记录已经处理过的消息的 ID。当收到一条消息后，消费者程序就可以对比收到的消息 ID 和记录的已处理过的消息 ID，来判断当前收到的消息有没有经过处理。如果已经处理过，消费者程序就不再进行处理。

​ 但是 List 并不会为每个消息生成 ID 号，所以需要自行为每个消息生成一个全局唯一ID，在用 LPUSH 命令把消息插入 List 时，需要在消息中包含这个全局唯一 ID。

# 例如 执行以下命令，就把一条全局 ID 为 111000102、库存量为 99 的消息插入了消息队列
> LPUSH mq "111000102:stock:99"
(integer) 1

【3】如何保证消息的可靠性？

​ 当消费者程序从 List 中读取一条消息后，List 就不会再留存这条消息了。所以，如果消费者程序在处理消息的过程出现了故障或宕机，就会导致消息没有处理完成，那么，消费者程序再次启动后，就没法再次从 List 中读取消息了。为了留存消息，List 类型提供了 BRPOPLPUSH 命令，这个命令的作用是让消费者程序从一个 List 中读取消息，同时，Redis 会把这个消息再插入到另一个 List（可以叫作备份 List）留存。

​ 这样一来，如果消费者程序读了消息但没能正常处理，等它重启后，就可以从备份 List 中重新读取消息并进行处理了。

综上所述，基于 List 类型的消息队列，满足消息队列的三大需求（消息保序、处理重复的消息和保证消息可靠性）

• 消息保序：使用 LPUSH + RPOP；
• 阻塞读取：使用 BRPOP；（队列为空阻塞消费者的读取操作，以减少CPU一直循环读取的性能损耗）
• 重复消息处理：生产者自行实现全局唯一 ID；
• 消息的可靠性：使用 BRPOPLPUSH；（读取消息时附带留存备份，当出现异常宕机的情况可从备份List中获取消息重新消费）

List 作为消息队列的缺陷

​ List 不支持多个消费者消费同一条消息，因为一旦消费者拉取一条消息后，这条消息就从 List 中删除了，无法被其它消费者再次消费。

​ 要实现一条消息可以被多个消费者消费，那么就要将多个消费者组成一个消费组，使得多个消费者可以消费同一条消息，但是 List 类型并不支持消费组的实现。 Redis 从 5.0 版本开始提供的 Stream 数据类型，Stream 同样能够满足消息队列的三大需求，而且它还支持「消费组」形式的消息读取

4.Set

介绍

​ Set 类型是一个无序并唯一的键值集合，它的存储顺序不会按照插入的先后顺序进行存储。

​ 一个集合最多可以存储 2^32-1 个元素。概念和数学中个的集合基本类似，可以交集，并集，差集等等，所以 Set 类型除了支持集合内的增删改查，同时还支持多个集合取交集、并集、差集。

Set 类型和 List 类型的区别如下：

• List 可以存储重复元素，Set 只能存储非重复元素；
• List 是按照元素的先后顺序存储元素的，而 Set 则是无序方式存储元素的

内部实现

Set 类型的底层数据结构是由哈希表或整数集合实现的：

• 如果集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用整数集合作为 Set 类型的底层数据结构；
• 如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构

常用命令

Set 基础命令

# 往集合key中存入元素，元素存在则忽略，若key不存在则新建
SADD key member [member ...]
# 从集合key中删除元素
SREM key member [member ...] 
# 获取集合key中所有元素
SMEMBERS key
# 获取集合key中的元素个数
SCARD key

# 判断member元素是否存在于集合key中
SISMEMBER key member

# 从集合key中随机选出count个元素，元素不从key中删除
SRANDMEMBER key [count]
# 从集合key中随机选出count个元素，元素从key中删除
SPOP key [count]

Set 运算操作

# 交集运算
SINTER key [key ...]
# 将交集结果存入新集合destination中
SINTERSTORE destination key [key ...]

# 并集运算
SUNION key [key ...]
# 将并集结果存入新集合destination中
SUNIONSTORE destination key [key ...]

# 差集运算
SDIFF key [key ...]
# 将差集结果存入新集合destination中
SDIFFSTORE destination key [key ...]

应用场景

​ 集合的主要几个特性，无序、不可重复、支持并交差等操作。因此 Set 类型比较适合用来数据去重和保障数据的唯一性，还可以用来统计多个集合的交集、错集和并集等，当存储的数据是无序并且需要去重的情况下，比较适合使用集合类型进行存储。

​ 但此处有一个潜在的风险。Set 的差集、并集和交集的计算复杂度较高，在数据量较大的情况下，如果直接执行这些计算，会导致 Redis 实例阻塞。

​ 在主从集群中，为了避免主库因为 Set 做聚合计算（交集、差集、并集）时导致主库被阻塞，可以选择一个从库完成聚合统计，或者把数据返回给客户端，由客户端来完成聚合统计。

（1）点赞

​ Set 类型可以保证一个用户只能点一个赞，举例说明：key 是文章id，value 是用户id。uid:1 、uid:2、uid:3 三个用户分别对 article:1 文章点赞

# uid:1 用户对文章 article:1 点赞
> SADD article:1 uid:1
(integer) 1

# uid:2 用户对文章 article:1 点赞
> SADD article:1 uid:2
(integer) 1

# uid:3 用户对文章 article:1 点赞
> SADD article:1 uid:3
(integer) 1

# uid:1 用户取消对文章 article:1 的点赞
> SREM article:1 uid:1
(integer) 1

# 获取 article:1 文章所有点赞用户
SMEMBERS article:1
1) "uid:3"
2) "uid:2"

# 获取 article:1 文章的点赞用户数量
> SCARD article:1
(integer) 2

# 判断用户 uid:1 是否对文章 article:1 点赞了
SISMEMBER article:1 uid:1
(integer) 0  # 返回0说明没点赞，返回1则说明点赞了

（2）共同关注

​ Set 类型支持交集运算，所以可以用来计算共同关注的好友、公众号等。key 可以是用户id，value 则是已关注的公众号的id。

​ gzh:uid:1 用户关注公众号 id 为 5、6、7、8、9，gzh:uid:2 用户关注公众号 id 为 7、8、9、10、11

> SADD gzh:uid:1 5 6 7 8 9
> SADD gzh:uid:2 7 8 9 10 11

# 共同关注
> SINTER gzh:uid:1 gzh:uid:2
1) "7"
2) "8"
3) "9"

# 给 gzh:uid:2 推荐 gzh:uid:1 关注的公众号
> SDIFF gzh:uid:1 gzh:uid:2
1) "5"
2) "6"

# 验证某个公众号是否同时被 gzh:uid:1 或 gzh:uid:2 关注
> SISMEMBER gzh:uid:1 5
(integer) 1 # 返回0，说明关注了

> SISMEMBER gzh:uid:2 5
(integer) 0 # 返回0，说明没关注

（3）抽奖活动

​ 存储某活动中中奖的用户名 ，Set 类型因为有去重功能，可以保证同一个用户不会中奖两次。key为抽奖活动名，value为员工名称，把所有员工名称放入抽奖箱 ：

> SADD lucky Tom Jerry John Sean Marry Lindy Sary Mark
(integer) 5

​ 如果允许重复中奖，可以使用 SRANDMEMBER 命令（每次随机抽取元素）

# 抽取 1 个一等奖：
> SRANDMEMBER lucky 1
1) "Tom"
# 抽取 2 个二等奖：
> SRANDMEMBER lucky 2
1) "Mark"
2) "Jerry"
# 抽取 3 个三等奖：
> SRANDMEMBER lucky 3
1) "Sary"
2) "Tom"
3) "Jerry"

​ 如果不允许重复中奖，可以使用 SPOP 命令（每次随机抽取元素并将已抽取的元素剔除）

# 抽取一等奖1个
> SPOP lucky 1
1) "Sary"
# 抽取二等奖2个
> SPOP lucky 2
1) "Jerry"
2) "Mark"
# 抽取三等奖3个
> SPOP lucky 3
1) "John"
2) "Sean"
3) "Lindy"

5.Zset

介绍

​ Zset 类型（有序集合类型）相比于 Set 类型多了一个排序属性 score（分值），对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序集合的元素值，一个是排序值。

​ 有序集合保留了集合不能有重复成员的特性（分值可以重复），但不同的是，有序集合中的元素可以排序

内部实现

Zset 类型的底层数据结构是由压缩列表或跳表实现的：

• 如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表作为 Zset 类型的底层数据结构；
• 如果有序集合的元素不满足上面的条件，Redis 会使用跳表作为 Zset 类型的底层数据结构；

在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了

常用命令

Zset 常用操作

# 往有序集合key中加入带分值元素
ZADD key score member [[score member]...]   
# 往有序集合key中删除元素
ZREM key member [member...]                 
# 返回有序集合key中元素member的分值
ZSCORE key member
# 返回有序集合key中元素个数
ZCARD key 

# 为有序集合key中元素member的分值加上increment
ZINCRBY key increment member 

# 正序获取有序集合key从start下标到stop下标的元素
ZRANGE key start stop [WITHSCORES]
# 倒序获取有序集合key从start下标到stop下标的元素
ZREVRANGE key start stop [WITHSCORES]

# 返回有序集合中指定分数区间内的成员，分数由低到高排序。
ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]

# 返回指定成员区间内的成员，按字典正序排列, 分数必须相同。
ZRANGEBYLEX key min max [LIMIT offset count]
# 返回指定成员区间内的成员，按字典倒序排列, 分数必须相同
ZREVRANGEBYLEX key max min [LIMIT offset count]

Zset 运算操作（相比于 Set 类型，ZSet 类型没有支持差集运算）

# 并集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积
ZUNIONSTORE destkey numberkeys key [key...] 
# 交集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积
ZINTERSTORE destkey numberkeys key [key...]

应用场景

​ Zset 类型（Sorted Set，有序集合） 可以根据元素的权重来排序，可以自己来决定每个元素的权重值。比如说，可以根据元素插入 Sorted Set 的时间确定权重值，先插入的元素权重小，后插入的元素权重大。在面对需要展示最新列表、排行榜等场景时，如果数据更新频繁或者需要分页显示，可以优先考虑使用 Sorted Set

（1）排行榜

​ 有序集合比较典型的使用场景就是排行榜。例如学生成绩的排名榜、游戏积分排行榜、视频播放排名、电商系统中商品的销量排名等。

​ 以博文点赞排名为例，用户发表了五篇博文，分别获得赞为 200、40、100、50、150

# arcticle:1 文章获得了200个赞
> ZADD user:tom:ranking 200 arcticle:1
(integer) 1
# arcticle:2 文章获得了40个赞
> ZADD user:tom:ranking 40 arcticle:2
(integer) 1
# arcticle:3 文章获得了100个赞
> ZADD user:tom:ranking 100 arcticle:3
(integer) 1
# arcticle:4 文章获得了50个赞
> ZADD user:tom:ranking 50 arcticle:4
(integer) 1
# arcticle:5 文章获得了150个赞
> ZADD user:tom:ranking 150 arcticle:5
(integer) 1

# 文章 arcticle:4 新增一个赞，可以使用 ZINCRBY 命令（为有序集合key中元素member的分值加上increment）
ZINCRBY user:tom:ranking 1 arcticle:4

# 查看某篇文章的赞数，可以使用 ZSCORE 命令（返回有序集合key中元素个数）
ZSCORE user:tom:ranking arcticle:4

# 获取指定用户文章赞数最多的 3 篇文章，可以使用 ZREVRANGE 命令（倒序获取有序集合 key 从start下标到stop下标的元素）
ZREVRANGE user:tom:ranking 0 2 WITHSCORES

# 获取指定用户 100 赞到 200 赞的文章，可以使用 ZRANGEBYSCORE 命令（返回有序集合中指定分数区间内的成员，分数由低到高排序）
ZRANGEBYSCORE user:tom:ranking 100 200 WITHSCORES

（2）电话、姓名排序

​ 使用有序集合的 ZRANGEBYLEX 或 ZREVRANGEBYLEX 可以帮助我们实现电话号码或姓名的排序，我们以 ZRANGEBYLEX （返回指定成员区间内的成员，按 key 正序排列，分数必须相同）为例。

​ 注意：不要在分数不一致的 SortSet 集合中去使用 ZRANGEBYLEX和 ZREVRANGEBYLEX 指令，因为获取的结果会不准确

电话排序

​ 将电话号码存储到 SortSet 中，然后根据需要来获取号段

> ZADD phone 0 13100111100 0 13110114300 0 13132110901 
(integer) 3
> ZADD phone 0 13200111100 0 13210414300 0 13252110901 
(integer) 3
> ZADD phone 0 13300111100 0 13310414300 0 13352110901 
(integer) 3

​ 号码获取

# 获取所有号码
> ZRANGEBYLEX phone - +
1) "13100111100"
2) "13110114300"
3) "13132110901"
4) "13200111100"
5) "13210414300"
6) "13252110901"
7) "13300111100"
8) "13310414300"
9) "13352110901"

# 获取132的号码段
> ZRANGEBYLEX phone [132 (133
1) "13200111100"
2) "13210414300"
3) "13252110901"

# 获取132、133号段的号码
> ZRANGEBYLEX phone [132 (134
1) "13200111100"
2) "13210414300"
3) "13252110901"
4) "13300111100"
5) "13310414300"
6) "13352110901"

姓名排序

# 添加姓名
> zadd names 0 Toumas 0 Jake 0 Bluetuo 0 Gaodeng 0 Aimini 0 Aidehua 
(integer) 6

# 获取所有人的姓名
> ZRANGEBYLEX names - +
1) "Aidehua"
2) "Aimini"
3) "Bluetuo"
4) "Gaodeng"
5) "Jake"
6) "Toumas"

# 获取名字中大写字母A开头的所有人
> ZRANGEBYLEX names [A (B
1) "Aidehua"
2) "Aimini"

# 获取名字中大写字母 C 到 Z 的所有人
> ZRANGEBYLEX names [C [Z
1) "Gaodeng"
2) "Jake"
3) "Toumas"

6.BitMap

介绍

​ Bitmap，即位图，是一串连续的二进制数组（0和1），可以通过偏移量（offset）定位元素。BitMap通过最小的单位bit来进行0|1的设置，表示某个元素的值或者状态，时间复杂度为O(1)。

​ 由于 bit 是计算机中最小的单位，使用它进行储存将非常节省空间，特别适合一些数据量大且使用二值统计的场景。

内部实现

​ Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型。

​ String 类型是会保存为二进制的字节数组，所以，Redis 就把字节数组的每个 bit 位利用起来，用来表示一个元素的二值状态，可以把 Bitmap 看作是一个 bit 数组

常用命令

bit 基本操作

# 设置值，其中value只能是 0 和 1
SETBIT key offset value

# 获取值
GETBIT key offset

# 获取指定范围内值为 1 的个数，start 和 end 以字节为单位
BITCOUNT key start end

bit 运算操作

# BitMap间的运算
# operations 位移操作符，枚举值
  AND 与运算 &
  OR 或运算 |
  XOR 异或 ^
  NOT 取反 ~
  
# result 计算的结果，会存储在该key中（key1 … keyn 参与运算的key，可以有多个，空格分割，not运算只能一个key）
# 当 BITOP 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0。返回值是保存到 destkey 的字符串的长度（以字节byte为单位），和输入 key 中最长的字符串长度相等。
BITOP [operations] [result] [key1] [keyn…]

# 返回指定key中第一次出现指定value(0/1)的位置
BITPOS [key] [value]

应用场景

​ Bitmap 类型非常适合二值状态统计的场景，这里的二值状态就是指集合元素的取值就只有 0 和 1 两种，在记录海量数据时，Bitmap 能够有效地节省内存空间

（1）签到统计

​ 在签到打卡的场景（典型的二值状态）中，只用记录签到（1）或未签到（0）。签到统计时，每个用户一天的签到用 1 个 bit 位就能表示，一个月（假设是 31 天）的签到情况用 31 个 bit 位就可以，而一年的签到也只需要用 365 个 bit 位，根本不用太复杂的集合类型。

​ 假设要统计 ID 100 的用户在 2022 年 6 月份的签到情况，就可以按照下面的步骤进行操作。

# 步骤1：执行下面的命令，记录该用户 6 月 3 号已签到
SETBIT uid:sign:100:202206 2 1

# 步骤2：检查该用户 6 月 3 日是否签到
GETBIT uid:sign:100:202206 2 

# 步骤3：统计该用户在 6 月份的签到次数
BITCOUNT uid:sign:100:202206

​ 统计本月首次打卡时间：Redis 提供了 BITPOS key bitValue [start] [end]指令，返回数据表示 Bitmap 中第一个值为 bitValue 的 offset 位置。在默认情况下， 命令将检测整个位图， 可以通过可选的 start 参数和 end 参数指定要检测的范围。所以可以通过执行这条命令来获取 userID = 100 在 2022 年 6 月份首次打卡日期

BITPOS uid:sign:100:202206 1
# offset 从 0 开始的，所以需要将返回的 value + 1 

（2）判断登录态

​ Bitmap 提供了 GETBIT、SETBIT 操作，通过一个偏移值 offset 对 bit 数组的 offset 位置的 bit 位进行读写操作，需要注意的是 offset 从 0 开始。

​ 只需要一个 key = login_status 表示存储用户登陆状态集合数据， 将用户 ID 作为 offset，在线就设置为 1，下线设置 0。通过 GETBIT判断对应的用户是否在线。 5000 万用户只需要 6 MB 的空间。

假如要判断 ID = 10086 的用户的登陆情况：

# 步骤1：执行以下指令，表示用户已登录
SETBIT login_status 10086 1

# 步骤2：检查该用户是否登陆，返回值 1 表示已登录
GETBIT login_status 10086

# 步骤3：登出，将 offset 对应的 value 设置成 0
SETBIT login_status 10086 0

（3）连续签到用户总数

统计出这连续 7 天连续打卡用户总数

​ 把每天的日期作为 Bitmap 的 key，userId 作为 offset，若是打卡则将 offset 位置的 bit 设置成 1。key 对应的集合的每个 bit 位的数据则是一个用户在该日期的打卡记录。一共有 7 个这样的 Bitmap，如果能对这 7 个 Bitmap 的对应的 bit 位做 『与』运算。同样的 UserID offset 都是一样的，当一个 userID 在 7 个 Bitmap 对应的 offset 位置的 bit = 1 就说明该用户 7 天连续打卡。

​ 结果保存到一个新 Bitmap 中，再通过 BITCOUNT 统计 bit = 1 的个数便得到了连续打卡 7 天的用户总数。

​ Redis 提供了 BITOP operation destkey key [key ...]这个指令用于对一个或者多个 key 的 Bitmap 进行位元操作。

• operation 可以是 and、OR、NOT、XOR。当 BITOP 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0 。空的 key 也被看作是包含 0 的字符串序列。

假设要统计 3 天连续打卡的用户数，则是将三个 bitmap 进行 AND 操作，并将结果保存到 destmap 中，接着对 destmap 执行 BITCOUNT 统计，如下命令：

# 与操作
BITOP AND destmap bitmap:01 bitmap:02 bitmap:03
# 统计 bit 位 =  1 的个数
BITCOUNT destmap

​ 即使一天产生一个亿的数据，Bitmap 占用的内存也不大，大约占 12 MB 的内存（10^8/8/1024/1024），7 天的 Bitmap 的内存开销约为 84 MB。同时最好给 Bitmap 设置过期时间，让 Redis 删除过期的打卡数据，节省内存

7.HyperLogLog

介绍

​ Redis HyperLogLog 是 Redis 2.8.9 版本新增的数据类型，是一种用于「统计基数」的数据集合类型，基数统计就是指统计一个集合中不重复的元素个数。但要注意，HyperLogLog 是统计规则是基于概率完成的，不是非常准确，标准误算率是 0.81%。所以，简单来说 HyperLogLog 提供不精确的去重计数。

​ HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的内存空间总是固定的、并且是很小的。在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数，和元素越多就越耗费内存的 Set 和 Hash 类型相比，HyperLogLog 就非常节省空间。

​ 对比举例分析：用 Java 语言来说，一般 long 类型占用 8 字节，而 1 字节有 8 位，即：1 byte = 8 bit，即 long 数据类型最大可以表示的数是：2^63-1。对应上面的2^64个数，假设此时有2^63-1这么多个数，从 0 ~ 2^63-1，按照long以及1k = 1024 字节的规则来计算内存总数，就是：((2^63-1) * 8/1024)K，这是很庞大的一个数，存储空间远远超过12K，而 HyperLogLog 却可以用 12K 就能统计完。

内部实现

​ HyperLogLog 的实现涉及到很多数学问题

常用命令

# 添加指定元素到 HyperLogLog 中
PFADD key element [element ...]

# 返回给定 HyperLogLog 的基数估算值。
PFCOUNT key [key ...]

# 将多个 HyperLogLog 合并为一个 HyperLogLog
PFMERGE destkey sourcekey [sourcekey ...]

应用场景

（1）百万级网页UV计数

​ Redis HyperLogLog 优势在于只需要花费 12 KB 内存，就可以计算接近 2^64 个元素的基数，和元素越多就越耗费内存的 Set 和 Hash 类型相比，HyperLogLog 就非常节省空间。所以，非常适合统计百万级以上的网页 UV 的场景。

# 在统计 UV 时，可以用 PFADD 命令（用于向 HyperLogLog 中添加新元素）把访问页面的每个用户都添加到 HyperLogLog 中
PFADD page1:uv user1 user2 user3 user4 user5

# 随后用 PFCOUNT 命令直接获得 page1 的 UV 值，这个命令的作用就是返回 HyperLogLog 的统计结果
PFCOUNT page1:uv

​ 不过，有一点需要注意，HyperLogLog 的统计规则是基于概率完成的，所以它给出的统计结果是有一定误差的，标准误算率是 0.81%。这也就意味着，使用 HyperLogLog 统计的 UV 是 100 万，但实际的 UV 可能是 101 万。虽然误差率不算大，但是，如果需要精确统计结果的话，最好还是继续用 Set 或 Hash 类型

8.GEO

介绍

​ Redis GEO 是 Redis 3.2 版本新增的数据类型，主要用于存储地理位置信息，并对存储的信息进行操作。

​ 在日常生活中，我们越来越依赖搜索“附近的餐馆”、在打车软件上叫车，这些都离不开基于位置信息服务（Location-Based Service，LBS）的应用。LBS 应用访问的数据是和人或物关联的一组经纬度信息，而且要能查询相邻的经纬度范围，GEO 就非常适合应用在 LBS 服务的场景中

内部实现

​ GEO 本身并没有设计新的底层数据结构，而是直接使用了 Sorted Set 集合类型。

​ GEO 类型使用 GeoHash 编码方法实现了经纬度到 Sorted Set 中元素权重分数的转换，这其中的两个关键机制就是「对二维地图做区间划分」和「对区间进行编码」。一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为 Sorted Set 元素的权重分数。

​ 这样一来，就可以把经纬度保存到 Sorted Set 中，利用 Sorted Set 提供的“按权重进行有序范围查找”的特性，实现 LBS 服务中频繁使用的“搜索附近”的需求

常用命令

# 存储指定的地理空间位置，可以将一个或多个经度(longitude)、纬度(latitude)、位置名称(member)添加到指定的 key 中。
GEOADD key longitude latitude member [longitude latitude member ...]

# 从给定的 key 里返回所有指定名称(member)的位置（经度和纬度），不存在的返回 nil。
GEOPOS key member [member ...]

# 返回两个给定位置之间的距离。
GEODIST key member1 member2 [m|km|ft|mi]

# 根据用户给定的经纬度坐标来获取指定范围内的地理位置集合。
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]

应用场景

（1）滴滴叫车

​ 以滴滴叫车的场景为例，介绍下具体如何使用 GEO 命令：GEOADD 和 GEORADIUS 这两个命令。

​ 假设车辆 ID 是 33，经纬度位置是（116.034579，39.030452），可以用一个 GEO 集合保存所有车辆的经纬度，集合 key 是 cars:locations。

# 执行下面的这个命令，就可以把 ID 号为 33 的车辆的当前经纬度位置存入 GEO 集合中
GEOADD cars:locations 116.034579 39.030452 33

​ 当用户想要寻找自己附近的网约车时，LBS 应用就可以使用 GEORADIUS 命令。

​ 例如，LBS 应用执行下面的命令时，Redis 会根据输入的用户的经纬度信息（116.054579，39.030452 ），查找以这个经纬度为中心的 5 公里内的车辆信息，并返回给 LBS 应用。

GEORADIUS cars:locations 116.054579 39.030452 5 km ASC COUNT 10

9.Stream

介绍

Redis Stream 是 Redis 5.0 版本新增加的数据类型，Redis 专门为消息队列设计的数据类型。

在 Redis 5.0 Stream 没出来之前，消息队列的实现方式都有着各自的缺陷，例如：

• 发布订阅模式，不能持久化也就无法可靠的保存消息，并且对于离线重连的客户端不能读取历史消息的缺陷；
• List 实现消息队列的方式不能重复消费，一个消息消费完就会被删除，而且生产者需要自行实现全局唯一 ID；

​ 基于以上问题，Redis 5.0 便推出了 Stream 类型也是此版本最重要的功能，用于完美地实现消息队列，它支持消息的持久化、支持自动生成全局唯一 ID、支持 ack 确认消息的模式、支持消费组模式等，让消息队列更加的稳定和可靠

内部实现

常用命令

Stream 消息队列操作命令：

• XADD：插入消息，保证有序，可以自动生成全局唯一 ID；

• XLEN ：查询消息长度；

• XREAD：用于读取消息，可以按 ID 读取数据；

• XDEL ： 根据消息 ID 删除消息；

• DEL ：删除整个 Stream；

• XRANGE ：读取区间消息

• XREADGROUP：按消费组形式读取消息；

• XPENDING 和 XACK：

  • XPENDING 命令可以用来查询每个消费组内所有消费者「已读取、但尚未确认」的消息；
  • XACK 命令用于向消息队列确认消息处理已完成；

应用场景

（1）消息队列

生产者通过 XADD 命令插入一条消息：

# 往名称为 mymq 的消息队列中插入一条消息，消息的键是 name，值是 xiaobai，* 表示让 Redis 为插入的数据自动生成一个全局唯一的 ID
> XADD mymq * name xiaobai
"1721108689808-0"

插入成功后会返回全局唯一的 ID："1721108689808-0"。消息的全局唯一 ID 由两部分组成：

• 第一部分“1721108689808”是数据插入时，以毫秒为单位计算的当前服务器时间；
• 第二部分表示插入消息在当前毫秒内的消息序号，这是从 0 开始编号的。例如，“1721108689808-0”就表示在“1721108689808”毫秒内的第 1 条消息。

​ 消费者通过 XREAD 命令从消息队列中读取消息时，可以指定一个消息 ID，并从这个消息 ID 的下一条消息开始进行读取（注意是输入消息 ID 的下一条信息开始读取，不是查询输入ID的消息）

# 从 ID 号为 1721108689808-0 的消息开始，读取后续的所有消息（示例中一共 1 条）
> XREAD STREAMS mymq 1721108689808-0

1-1	        mymq
1-2-1-1	    1721109649796-0
1-2-1-2-1	  name
1-2-1-2-2	  xiaobai

​ 如果想要实现阻塞读（当没有数据时，阻塞住），可以调用 XRAED 时设定 BLOCK 配置项，实现类似于 BRPOP 的阻塞读取操作。

​ 参考下述实例，设置了 BLOCK 10000 的配置项，10000 的单位是毫秒，表明 XREAD 在读取最新消息时，如果没有消息到来，XREAD 将阻塞 10000 毫秒（即 10 秒），然后再返回。

# 命令最后的“$”符号表示读取最新的消息
> XREAD BLOCK 10000 STREAMS mymq $
(nil)
(10.00s)

​ Stream 的基础方法，使用 xadd 存入消息和 xread 循环阻塞读取消息的方式可以实现简易版的消息队列，交互流程如下图所示：

XGROUP 创建消费组

​ Stream 可以以使用 XGROUP 创建消费组，创建消费组之后，Stream 可以使用 XREADGROUP 命令让消费组内的消费者读取消息。

​ 创建两个消费组，这两个消费组消费的消息队列是 mymq，都指定从第一条消息开始读取：

# 创建一个名为 group1 的消费组，0-0 表示从第一条消息开始读取
> XGROUP CREATE mymq group1 0-0
OK
# 创建一个名为 group2 的消费组，0-0 表示从第一条消息开始读取
> XGROUP CREATE mymq group2 0-0
OK

消费组 group1 内的消费者 consumer1 从 mymq 消息队列中读取所有消息的命令如下：

# 命令最后的参数“>”，表示从第一条尚未被消费的消息开始读取。
> XREADGROUP GROUP group1 consumer1 STREAMS mymq >

1-1	        mymq
1-2-1-1	    1721108689808-0
1-2-1-2-1	  name
1-2-1-2-2	  xiaobai

​ 消息队列中的消息一旦被消费组里的一个消费者读取了，就不能再被该消费组内的其他消费者读取了，即同一个消费组里的消费者不能消费同一条消息。

​ 参考示例：执行完刚才的 XREADGROUP 命令后，再执行一次同样的命令，此时读到的就是空值了：

> XREADGROUP GROUP group1 consumer1 STREAMS mymq >
(nil)

​ 但是，不同消费组的消费者可以消费同一条消息（但是有前提条件，创建消息组的时候，不同消费组指定了相同位置开始读取消息）。

​ 参考示例：刚才 group1 消费组里的 consumer1 消费者消费了一条 id 为 1721108689808-0 的消息，现在用 group2 消费组里的 consumer1 消费者消费消息：

> XREADGROUP GROUP group2 consumer1 STREAMS mymq >

1-1	        mymq
1-2-1-1	    1721108689808-0
1-2-1-2-1	  name
1-2-1-2-2	  xiaobai

​ 因为创建两组的消费组都是从第一条消息开始读取，所以可以看到第二组的消费者依然可以消费 id 为 1721108689808-0 的这一条消息。因此，不同的消费组的消费者可以消费同一条消息。使用消费组的目的是让组内的多个消费者共同分担读取消息，所以，通常会让每个消费者读取部分消息，从而实现消息读取负载在多个消费者间是均衡分布的。

​ 参考示例：先生产三条消息，然后执行下列命令，让 group2 中的 consumer1、2、3 各自读取一条消息。

# 让 group2 中的 consumer1 从 mymq 消息队列中消费一条消息
> XREADGROUP GROUP group2 consumer1 COUNT 1 STREAMS mymq >
1-1	        mymq
1-2-1-1	    1721110235089-0
1-2-1-2-1	  name
1-2-1-2-2	  xiaobai

# 让 group2 中的 consumer2 从 mymq 消息队列中消费一条消息
> XREADGROUP GROUP group2 consumer2 COUNT 1 STREAMS mymq >
1-1	        mymq
1-2-1-1	    1721110236025-0
1-2-1-2-1	  name
1-2-1-2-2	  xiaobai

# 让 group2 中的 consumer3 从 mymq 消息队列中消费一条消息
> XREADGROUP GROUP group2 consumer3 COUNT 1 STREAMS mymq >
1-1	        mymq
1-2-1-1	    1721110236772-0
1-2-1-2-1	  name
1-2-1-2-2	  xiaobai

基于Stream 实现的消息队列，如何保证消费者在发生故障或宕机再次重启后，仍然可以读取未处理完的消息？

​ Streams 会自动使用内部队列（也称为 PENDING List）留存消费组里每个消费者读取的消息，直到消费者使用 XACK 命令通知 Streams“消息已经处理完成”。

​ 消费确认增加了消息的可靠性，一般在业务处理完成之后，需要执行 XACK 命令确认消息已经被消费完成，整个流程的执行如下图所示：

​ 如果消费者没有成功处理消息，它就不会给 Streams 发送 XACK 命令，消息仍然会留存。此时，消费者可以在重启后，用 XPENDING 命令查看已读取、但尚未确认处理完成的消息。

# 查看group2中各个消费者已读取、但尚未确认的消息个数
> XPENDING mymq group2

#	      Value
1	      5
2	      1721108689808-0   # 表示 group2 中所有消费者读取的消息最小 ID
3	      1721110236772-0   # 表示 group2 中所有消费者读取的消息最大 ID
4-1-1	  consumer1
4-1-2	  3
4-2-1	  consumer2
4-2-2	  1
4-3-1	  consumer3
4-3-2	  1

# 查看某个消费者具体读取了哪些数据
> XPENDING mymq group2 - + 10 consumer2
#	  Value
1-1	1721110236025-0
1-2	consumer2
1-3	579553
1-4	1

# 从上述结果可知，consumer2已读取的消息ID为1721110236025-0，一旦消息被消费者处理，则其可使用XACK命令通知Streams，然后这条数据就会被删除
> XACK mymq group2 1721110236025-0

# 再次使用XPENDING查看，会发现consumer2已经没有已读取但尚未确认处理的消息
> XPENDING mymq group2 - + 10 consumer2

基于Streams实现的消息队列

• 消息保序：XADD/XREAD
• 阻塞读取：XREAD block
• 重复消息处理：Stream 在使用 XADD 命令，会自动生成全局唯一 ID；
• 消息可靠性：内部使用 PENDING List 自动保存消息，使用 XPENDING 命令查看消费组已经读取但是未被确认的消息，消费者使用 XACK 确认消息；
• 支持消费组形式消费数据

Redis 基于 Stream 消息队列与专业的消息队列有哪些差距？

一个专业的消息队列，必须要做到两大块：

• 消息不丢
• 消息可堆积

【1】Redis Stream 消息会丢失吗？

​ 使用一个消息队列，其实就分为三大块：生产者、队列中间件、消费者，所以要保证消息就是保证三个环节都不能丢失数据

Redis Stream 消息队列能不能保证三个环节都不丢失数据？

• Redis 生产者会不会丢消息？生产者会不会丢消息，取决于生产者对于异常情况的处理是否合理。 从消息被生产出来，然后提交给 MQ 的过程中，只要能正常收到 （ MQ 中间件） 的 ack 确认响应，就表示发送成功，所以只要处理好返回值和异常，如果返回异常则进行消息重发，那么这个阶段是不会出现消息丢失的。

• Redis 消费者会不会丢消息？不会，因为 Stream （ MQ 中间件）会自动使用内部队列（也称为 PENDING List）留存消费组里每个消费者读取的消息，但是未被确认的消息。消费者可以在重启后，用 XPENDING 命令查看已读取、但尚未确认处理完成的消息。等到消费者执行完业务逻辑后，再发送消费确认 XACK 命令，也能保证消息的不丢失。

• Redis 消息中间件会不会丢消息？

  会，Redis 在以下 2 个场景下，都会导致数据丢失：

  • AOF 持久化配置为每秒写盘，但这个写盘过程是异步的，Redis 宕机时会存在数据丢失的可能
  • 主从复制也是异步的，主从切换时，也存在丢失数据的可能 (opens new window)。

​ 可以看到，Redis 在队列中间件环节无法保证消息不丢。像 RabbitMQ 或 Kafka 这类专业的队列中间件，在使用时是部署一个集群，生产者在发布消息时，队列中间件通常会写「多个节点」，也就是有多个副本，这样一来，即便其中一个节点挂了，也能保证集群的数据不丢失

【2】Redis Stream 消息可堆积吗？

​ Redis 的数据都存储在内存中，这就意味着一旦发生消息积压，则会导致 Redis 的内存持续增长，如果超过机器内存上限，就会面临被 OOM 的风险。所以 Redis 的 Stream 提供了可以指定队列最大长度的功能，就是为了避免这种情况发生。当指定队列最大长度时，队列长度超过上限后，旧消息会被删除，只保留固定长度的新消息。基于此，Stream 在消息积压时，如果指定了最大长度，还是有可能丢失消息的。

​ 但 Kafka、RabbitMQ 专业的消息队列它们的数据都是存储在磁盘上，当消息积压时，无非就是多占用一些磁盘空间。因此，把 Redis 当作队列来使用时，会面临 2 个问题：

• Redis 本身可能会丢数据；
• 面对消息挤压，内存资源会紧张；

所以，能不能将 Redis 作为消息队列来使用，关键看业务场景：

• 如果业务场景足够简单，对于数据丢失不敏感，而且消息积压概率比较小的情况下，把 Redis 当作队列是完全可以的
• 如果业务有海量消息，消息积压的概率比较大，并且不能接受数据丢失，还是用专业的消息队列中间件

Redis 发布/订阅机制为什么不可以作为消息队列？

发布订阅机制存在以下缺点，都是跟丢失数据有关：

• 发布/订阅机制没有基于任何数据类型实现，所以不具备「数据持久化」的能力，也就是发布/订阅机制的相关操作，不会写入到 RDB 和 AOF 中，当 Redis 宕机重启，发布/订阅机制的数据也会全部丢失
• 发布订阅模式是“发后即忘”的工作模式，如果有订阅者离线重连之后不能消费之前的历史消息
• 当消费端有一定的消息积压时，也就是生产者发送的消息，消费者消费不过来时，如果超过 32M 或者是 60s 内持续保持在 8M 以上，消费端会被强行断开，这个参数是在配置文件中设置的，默认值是 client-output-buffer-limit pubsub 32mb 8mb 60

所以，发布/订阅机制只适合即时通讯的场景，比如构建哨兵集群 的场景采用了发布/订阅机制

Redis 数据结构

​ **Redis 为什么那么快？**除了它是内存数据库，使得所有的操作都在内存上进行之外，还有一个重要因素，它实现的数据结构，使得我们对数据进行增删查改操作时，Redis 能高效的处理

​ 此处需理解一个概念：Redis 数据结构并不是指 String（字符串）对象、List（列表）对象、Hash（哈希）对象、Set（集合）对象和 Zset（有序集合）对象，因为这些是 Redis 键值对中值的数据类型，也就是数据的保存形式，这些对象的底层实现的方式就用到了数据结构

​ Redis 数据类型的底层数据结构随着版本的更新也有所不同，参考版本图示分析：

​ 结合新旧版本的数据结构学习，一种有8种数据结构：SDS、双向链表、压缩链表、哈希表、整数集合、跳表、quicklist、listpack，首先需理解对象和数据结构的关系

键值对数据库是如何实现的？

​ Redis 的键值对中的 key 就是字符串对象，而 value 可以是字符串对象，也可以是集合数据类型的对象，比如 List 对象、Hash 对象、Set 对象和 Zset 对象

# name 是一个字符串键，因为键的值是一个字符串对象
> SET name "noob"

# person 是一个哈希表键，因为键的值是一个包含两个键值对的哈希表对象
> HSET person name "noob" age 18

# stu 是一个列表键，因为键的值是一个包含两个元素的列表对象
> RPUSH stu "noob" "tom"

​ Redis 是使用了一个「哈希表」保存所有键值对，哈希表的最大好处就是可以用 O(1) 的时间复杂度来快速查找到键值对。哈希表其实就是一个数组，数组中的元素叫做哈希桶。

​ ==Redis 的哈希桶是怎么保存键值对数据的呢？==哈希桶存放的是指向键值对数据的指针（dictEntry*），这样通过指针就能找到键值对数据，然后因为键值对的值可以保存字符串对象和集合数据类型的对象，所以键值对的数据结构中并不是直接保存值本身，而是保存了 void * key 和 void * value 指针，分别指向了实际的键对象和值对象，这样一来，即使值是集合数据，也可以通过 void * value 指针找到。

​

• redisDb 结构，表示 Redis 数据库的结构，结构体里存放了指向了 dict 结构的指针；
• dict 结构，结构体里存放了 2 个哈希表，正常情况下都是用「哈希表1」，「哈希表2」只有在 rehash 的时候才用；
• ditctht 结构，表示哈希表的结构，结构里存放了哈希表数组，数组中的每个元素都是指向一个哈希表节点结构（dictEntry）的指针；
• dictEntry 结构，表示哈希表节点的结构，结构里存放了 *void * key 和 void * value 指针， key 指向的是 String 对象，而 *value 则可以指向 String 对象，也可以指向集合类型的对象，比如 List 对象、Hash 对象、Set 对象和 Zset 对象。

​ void * key 和 void * value 指针指向的是 Redis 对象，Redis 中的每个对象都由 redisObject 结构表示，如下图：

对象结构里包含的成员变量：

• type，标识该对象是什么类型的对象（String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对象）；
• encoding，标识该对象使用了哪种底层的数据结构；
• ptr，指向底层数据结构的指针

Redis 键值对数据库的全景图分析如下，进一步掌握Redis 对象和数据结构的关系

1.SDS

​ Redis 是用 C 语言实现的，但是它没有直接使用 C 语言的 char* 字符数组来实现字符串，而是自己封装了一个名为简单动态字符串（simple dynamic string，SDS） 的数据结构来表示字符串，也就是 Redis 的 String 数据类型的底层数据结构是 SDS。

C 语言字符串的缺陷

​ char* name = noob其底层存储是字符数组，分别存储每个字符内容和一个结尾符（n、o、o、b、\0）。在C 语言里，对字符串操作时，char * 指针只是指向字符数组的起始位置，而字符数组的结尾位置就用“\0”表示，代表指字符串的结束。C 语言标准库中的字符串操作函数就通过判断字符是不是 “\0” 来决定要不要停止操作，如果当前字符不是 “\0” ，说明字符串还没结束，可以继续操作，如果当前字符是 “\0” 是则说明字符串结束了，就要停止操作。

​ 但其相应也存在缺陷，当字符数组中有”\0“字符，那么在操作字符串的时候就会遇到提前结束的情况，是因为程序误将字符数组的”\0“字符当做结束符了。也是基于这个限制导致C语言的字符串只能存储文本数据，不能保存图片、音频、视频文件等这样的二进制数据

​ 且C语言标准库中字符串的操作函数是很不安全的，对程序员不太优化，稍微不注意就会导致缓冲区溢出。例如char *strcat(char *dest, const char* src);实现字符串拼接，C 语言的字符串是不会记录自身的缓冲区大小的，所以假定在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立，就会发生缓冲区溢出将可能会造成程序运行终止

​ 综上所述可以总结C语言字符串的不足之处和待改进的点：

• 获取字符串长度的时间复杂度为 O（N）；
• 字符串的结尾是以 “\0” 字符标识，字符串里面不能包含有 “\0” 字符，因此不能保存二进制数据；
• 字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能会造成程序运行终止；

​ Redis 则通过实现SDS结构，从而避免了上述问题

SDS 结构设计

​ Redis 5.0 中的SDS 数据结构

​

• len：记录了字符串长度
  • 获取字符串长度的时候，只需返回这个成员变量值，时间复杂度为 O（1）
• alloc：分配给字符数组的空间长度
  • 修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现缓冲区溢出的问题。
• flags：用来表示不同类型的 SDS
  • 设计了5 种类型：sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，其主要区别在于其数据结构中的len和alloc成员变量的数据类型不同
  • 之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间
• buf[]，字符数组，用来保存实际数据
  • 不仅可以保存字符串，也可以保存二进制数据（len变量用于记录字符串长度，因此无序使用\0作为结尾符，则可存储包含\0的数据，但为了兼容C语言标准库的函数，SDS字符串结尾还是会加上\0）

总的来说，Redis 的 SDS 结构在原本字符数组之上，增加了三个元数据：len、alloc、flags，用来解决 C 语言字符串的缺陷

SDS 结构设计优势

【1】O（1）获取字符串长度

​ C语言的字符串长度获取函数strlen 是通过遍历的方式统计字符串长度，时间复杂度是O（N）

​ SDS通过引入len记录字符串长度，时间复杂度只需要O（1）

【2】支持二进制数据存储

​ C语言的字符串是通过”\0“标记结尾，因此无法存储包含"\0"的字符串数据，进而无法支持图片、二进制数据等内容

​ SDS通过引入len记录字符串长度，因此不需要使用"\0"作为标记符，以此支持存储包含"\0"的字符串数据以及其他格式数据，但但为了兼容C语言标准库的函数，SDS字符串结尾还是会加上\0

【3】不会发生缓冲区溢出

​ C语言的字符串操作（例如追加字符串函数strcat）都是不安全的，因为这些函数将缓冲区大小是否满足操作需求的工作交由开发者来保证，程序内部并不会判断缓冲区大小是否够用，当发生了缓冲区溢出就有可能造成程序异常结束

​ SDS提供了自动扩容机制，在操作字符串的时候通过allo-len计算剩余空间大小，用于判断是否满足操作需求，如果不满足则自动将SDS的空间进行扩容后才执行实际的修改操作。因此使用SDS既不需要手动修改SDS的大小，也不会出现缓冲区溢出的问题。

【4】节省内存空间

​ 内存空间的节省可以从两方面进行切入：设计了5种不同的SDS类型（每种类型的len、alloc不同）、编译优化

​ SDS引入了flags：用来表示不同类型的 SDS，并设计了5中不同的SDS类型，其主要区别在于其数据结构中的len和alloc成员变量的数据类型不同，用于灵活保存不同大小的字符串，从而有效节省内存空间（在保存小字符串时，结构头占用空间也比较少）

​ 编译优化：Redis在编程上还使用了专门的编译优化来节省内存空间，即在 struct 声明了 __attribute__ ((packed)) ，它的作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。因为默认情况下编译器使用的是【字节对齐】的方式分配内存

# 编译优化案例
#include <stdio.h>
struct test1 {
    char a;
    int b;
 } test1;
 
int main() {
     printf("%lu\n", sizeof(test1));
     return 0;
}

​ 默认情况下采用【字节对齐】的方式分配内存，因此这个结构体的大小是8（char 1；int 4，但是字节对齐都取4，多余的3个字节是为了字节对齐而分配的，相当于有3个字节被浪费掉了），通过__attribute__ ((packed)) 属性定义下面的结构体 ，同样包含 char 和 int 两个类型的成员变量，则其会按照紧凑方式进行内存分配以节省空间（实际占用5个字节）

#include <stdio.h>

struct __attribute__((packed)) test2  {
    char a;
    int b;
 } test2;
 
int main() {
     printf("%lu\n", sizeof(test2));
     return 0;
}

2.链表

链表结构设计

​ C 语言本身没有链表这个数据结构的，所以 Redis 自己设计了一个链表数据结构，这是一个双向链表（有前置节点和后置节点）

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

​ Redis在listNode结构体基础上又封装了list数据结构，便于操作链表

typedef struct list {
    //链表头节点
    listNode *head;
    //链表尾节点
    listNode *tail;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void (*free)(void *ptr);
    //节点值比较函数
    int (*match)(void *ptr, void *key);
    //链表节点数量
    unsigned long len;
} list;

优缺点

Redis的链表实现优点

• listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；
• list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；
• list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1)；
• listNode 链表节使用 void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

Redis的链表实现缺点

• 链表每个节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存（对比之下，数组的内存是连续的，可以充分利用 CPU 缓存来加速访问）
• 保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大

​ 因此，Redis 3.0 的 List 对象在数据量比较少的情况下，会采用「压缩列表」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。

​ 不过，压缩列表存在性能问题，所以 Redis 在 3.2 版本设计了新的数据结构 quicklist，并将 List 对象的底层数据结构改由 quicklist 实现。然后在 Redis 5.0 设计了新的数据结构 listpack，沿用了压缩列表紧凑型的内存布局，最终在最新的 Redis 版本，将 Hash 对象和 Zset 对象的底层数据结构实现之一的压缩列表，替换成由 listpack 实现。

3.压缩列表

​ 压缩列表的最大特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。

但是，压缩列表的缺陷也是有的：

• 不能保存过多的元素，否则查询效率就会降低；
• 新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题；

因此，Redis 对象（List 对象、Hash 对象、Zset 对象）包含的元素数量较少，或者元素值不大的情况才会使用压缩列表作为底层数据结构。

压缩列表结构设计

​ 压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组

• zlbytes，记录整个压缩列表占用对内存字节数；
• zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
• zllen，记录压缩列表包含的节点数量；
• zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）。

​ 在压缩列表中，如果要查找定位第一个元素和最后一个元素，可以通过表头三个字段（zllen）的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。

​ 压缩节点包括三部分内容：

• prevlen，记录了「前一个节点」的长度，目的是为了实现从后向前遍历；
• encoding，记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
• data，记录了当前节点的实际数据，类型和长度都由 encoding 决定；

​ 当往压缩列表中插入数据时，压缩列表就会根据数据类型是字符串还是整数，以及数据的大小，会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。

​ prevlen 和 encoding 是根据数据的大小和类型来进行不同的空间大小分配，压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」，而且 prevlen 属性的空间大小跟前一个节点长度值有关，比如：

• 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
• 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

encoding 属性的空间大小跟数据是字符串还是整数，以及字符串的长度有关，如下图（下图中的 content 表示的是实际数据，即本文的 data 字段）：

• 如果当前节点的数据是整数，则 encoding 会使用 1 字节的空间进行编码，也就是 encoding 长度为 1 字节。通过 encoding 确认了整数类型，就可以确认整数数据的实际大小了，比如如果 encoding 编码确认了数据是 int16 整数，那么 data 的长度就是 int16 的大小
• 如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节/2字节/5字节的空间进行编码，encoding 编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度，即 data 的长度

连锁更新问题

​ 压缩列表除了查找复杂度高的问题，还存在”连锁更新问题“

​ 压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配：

• 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
• 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

​ 现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，目前这些节点的长度值都小于254，所以prelen属性需要使用1个字节的空间来保存其各自上一个节点的长度值。如果将一个长度大于等于254字节的新节点加入到压缩列表的表头，则新节点的插入则引起后面多个节点的内存空间重新扩展，即触发了连锁更新问题

​ 因为new节点的长度超过254字节，所以其后面一个节点e1的prevlen属性需要使用5个字节的空间来保存这个长度值，因此需要进行扩展，则其扩展长度范围为 254～257已经超出了254字节。则相应地e1的后一个节点e2的prevlen属性需要使用5个字节的空间来保存e1的长度值，以此类推，直到所有的节点扩展完成。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」，就像多米诺牌的效应一样，第一张牌倒下了，推动了第二张牌倒下；第二张牌倒下，又推动了第三张牌倒下....

​

压缩列表的不足

• 基于紧凑型的内存布局能节省内存开销，但对于中间节点的查找复杂度高
• 存在连锁更新问题：空间扩展操作（即重新分配内存），连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能

​ 所以说，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，最糟糕的是会有「连锁更新」的问题。因此，压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新，也是能接受的。

​ 虽说如此，Redis 针对压缩列表在设计上的不足，在后来的版本中，新增设计了两种数据结构：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。这两种数据结构的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的「连锁更新」的问题。

4.哈希表

​ 哈希表是一种保存键值对（key-value）的数据结构。哈希表中的每一个 key 都是独一无二的，程序可以根据 key 查找到与之关联的 value，或者通过 key 来更新 value，又或者根据 key 来删除整个 key-value等等。

​ 哈希表优点在于它能以 O(1) 的复杂度快速查询数据。因为哈希表实际上是数组，所以可以通过索引值快速查询到数据（将 key 通过 Hash 函数的计算，就能定位数据在表中的位置），但是存在的风险也是有，在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也会越高。

​ 解决哈希冲突的方式，有很多种。Redis 采用了「链式哈希」来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接，以便这些数据在表中仍然可以被查询到

哈希表结构设计

哈希表结构

typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;  
    //哈希表大小掩码，用于计算索引值
    unsigned long sizemask;
    //该哈希表已有的节点数量
    unsigned long used;
} dictht;

​ 可以看到，哈希表是一个数组（dictEntry **table），数组的每个元素是一个指向「哈希表节点（dictEntry）」的指针

哈希表节点结构

typedef struct dictEntry {
    //键值对中的键
    void *key;
  
    //键值对中的值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

​ dictEntry 结构里不仅包含指向键和值的指针，还包含了指向下一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对链接起来，以此来解决哈希冲突的问题，这就是链式哈希。

​ 此外，dictEntry 结构里键值对中的值是一个「联合体 v」定义的，因此，键值对中的值可以是一个指向实际值的指针，或者是一个无符号的 64 位整数或有符号的 64 位整数或double 类的值。这么做的好处是可以节省内存空间，因为当「值」是整数或浮点数时，就可以将值的数据内嵌在 dictEntry 结构里，无需再用一个指针指向实际的值，从而节省了内存空间

哈希冲突问题

​ 哈希表实际上是一个数组，数组里多每一个元素就是一个哈希桶。当一个键值对的键经过 Hash 函数计算后得到哈希值，再将(哈希值 % 哈希表大小)取模计算，得到的结果值就是该 key-value 对应的数组元素位置，也就是第几个哈希桶。

什么是哈希冲突？

​ 举个例子，有一个可以存放 8 个哈希桶的哈希表。key1 经过哈希函数计算后，再将「哈希值 % 8 」进行取模计算，结果值为 1，那么就对应哈希桶 1，类似的，key9 和 key10 分别对应哈希桶 1 和桶 6。此处key1 和 key9 对应到了相同的哈希桶中，这就发生了哈希冲突。

​ 当有两个以上数量的 kay 被分配到了哈希表中同一个哈希桶上时，此时称这些 key 发生了冲突

链式哈希 =》用于解决哈希冲突问题

​ Redis 采用了「链式哈希」的方法来解决哈希冲突。实现的方式就是每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用 next 指针构成一个单项链表，被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来，这样就解决了哈希冲突。

​ 以前面的哈希冲突案例进行分析，key1 和 key9 经过哈希计算后，都落在同一个哈希桶，链式哈希的话，key1 就会通过 next 指针指向 key9，形成一个单向链表。

​

​ 不过，链式哈希局限性也很明显，随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O(n)。要想解决这一问题，就需要进行 rehash，也就是对哈希表的大小进行扩展

rehash

​ Redis 使用 dictht 结构体表示哈希表。不过，在实际使用哈希表时，Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）。

typedef struct dict {
    …
    //两个Hash表，交替使用，用于rehash操作
    dictht ht[2]; 
    …
} dict;

​ 之所以定义了 2 个哈希表，是因为进行 rehash 的时候，需要用上 2 个哈希表：

【1】rehash的触发条件

​ rehash的触发条件与负载因子（load factor）有关，负载因子计算公式为：负载因子=哈希表已保存节点数量/哈希表大小

​ 触发 rehash 操作的条件，主要有两个：

• 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
• 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作

【2】rehash过程分析

​ 在正常服务请求阶段，插入的数据，都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间。随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：

• 给「哈希表 2」 分配空间，一般会比「哈希表 1」 大一倍（两倍的意思）；
• 将「哈希表 1 」的数据迁移到「哈希表 2」 中；
• 迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备

​ 这个过程看起来简单，但是其实第二步很有问题，如果「哈希表 1 」的数据量非常大，那么在迁移至「哈希表 2 」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。

渐进式rehash

​ 为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。渐进式 rehash 步骤如下：

• 给「哈希表 2」 分配空间；
• 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；
• 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。

​ 在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。

• 查找操作：先在「哈希表 1」 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。

• 新增操作：在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，以保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表

5.整数集合

​ 整数集合是 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素，并且元素数量不大时，就会使用整数集这个数据结构作为底层实现

整数集合结构设计

整数集合本质上是一块连续内存空间，它的结构定义如下：

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

​ 保存元素的容器是一个 contents 数组，虽然 contents 被声明为 int8_t 类型的数组，但是实际上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值。比如：

• 如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
• 如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
• 如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；

不同类型的 contents 数组，意味着数组的大小也会不同。

整数集合的升级操作

​ 整数集合会有一个升级规则：当将一个新元素加入到整数集合里面，如果新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时，整数集合需要先进行升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间大小，然后才能将新元素加入到整数集合里。升级的过程中，也要维持整数集合的有序性。

​ 整数集合升级的过程不会重新分配一个新类型的数组，而是在原本的数组上扩展空间，然后在将每个元素按间隔类型大小分割，如果 encoding 属性值为 INTSET_ENC_INT16，则每个元素的间隔就是 16 位。

​ 举个例子，假设有一个整数集合里有 3 个类型为 int16_t 的元素

​ 往这个整数集合中加入一个新元素 65535，这个新元素需要用 int32_t 类型来保存，所以整数集合要进行升级操作，首先需要为 contents 数组扩容，在原本空间的大小之上再扩容多 80 位（4x32-3x16=80），这样就能保存下 4 个类型为 int32_t 的元素。

​ 扩容完 contents 数组空间大小后，需要将之前的三个元素转换为 int32_t 类型，并将转换后的元素放置到正确的位上面，并且需要维持底层数组的有序性不变，整个转换过程如下

整数集合升级特点

​ 一般场景中如果要让个数组同时保存 int16_t、int32_t、int64_t 类型的元素，最简单做法就是直接使用 int64_t 类型的数组。不过这样的话，当如果元素都是 int16_t 类型的，就会造成内存浪费的情况。

​ 通过引入整数集合升级机制，如果一直向整数集合添加 int16_t 类型的元素，那么整数集合的底层实现就一直是用 int16_t 类型的数组，只有在要将 int32_t 类型或 int64_t 类型的元素添加到集合时，才会对数组进行升级操作，进而节省内存资源

​ 整数集合升级不支持降级操作，一旦对数组进行了升级，就会一直保持升级后的状态。参考上述案例，如果删除了 65535 元素，整数集合的数组还是 int32_t 类型的，并不会因此降级为 int16_t 类型

6.跳表

​ Redis 只有 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。zset 结构体里有两个数据结构：一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。

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

​ Zset 对象在执行数据插入或是数据更新的过程中，会依次在跳表和哈希表中插入或更新相应的数据，从而保证了跳表和哈希表中记录的信息一致。

​ Zset 对象能支持范围查询（如 ZRANGEBYSCORE 操作），这是因为它的数据结构设计采用了跳表，而又能以常数复杂度获取元素权重（如 ZSCORE 操作），这是因为它同时采用了哈希表进行索引。

​ 为什么概念介绍中说 Zset 对象的底层数据结构是「压缩列表」或者「跳表」，而没有说哈希表呢？

​ Zset 对象在使用跳表作为数据结构的时候，是使用由「哈希表+跳表」组成的 struct zset，但是讨论的时候，都会说跳表是 Zset 对象的底层数据结构，而不会提及哈希表，是因为 struct zset 中的哈希表只是用于以常数复杂度获取元素权重，大部分操作都是跳表实现的。

跳表结构设计

​ 链表在查找元素的时候，因为需要逐一查找，所以查询效率非常低，时间复杂度是O(N)，于是就出现了跳表。跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。

​ 下图展示了一个层级为 3 的跳表

图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

• L0 层级共有 5 个节点，分别是节点1、2、3、4、5；
• L1 层级共有 3 个节点，分别是节点 2、3、5；
• L2 层级只有 1 个节点，也就是节点 3 。

​ 如果要在链表中查找节点 4 这个元素，只能从头开始遍历链表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再往前遍历找到节点 4。这个查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度就是 O(logN)。

# 跳表节点 数据结构
typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

​ Zset 对象要同时保存「元素」和「元素的权重」，对应到跳表节点结构里就是 sds 类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针（struct zskiplistNode *backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

​ 跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。

​ level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」，跨度时用来记录两个节点之间的距离。

​ 跨度实际上是为了计算这个节点在跳表中的排位。因为跳表中的节点都是按序排列的，那么计算某个节点排位的时候，从头节点点到该结点的查询路径上，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位。

​ 举个例子，查找图中节点 3 在跳表中的排位，从头节点开始查找节点 3，查找的过程只经过了一个层（L2），并且层的跨度是 3，所以节点 3 在跳表中的排位是 3。

​ 另外，图中的头节点其实也是 zskiplistNode 跳表节点，只不过头节点的后向指针、权重、元素值都没有用到，所以图中省略了这部分。

==由谁定义哪个跳表节点是头节点呢？==这就介绍「跳表」结构体了，如下所示：

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

跳表结构里包含了：

• 跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
• 跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量；
• 跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量；

跳表节点查询过程

​ 查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，共有两个判断条件：

• 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
• 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。

​ 如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

以下图示3层级跳表为例，查找【元素abcd、权重4】的节点

• 先从头节点的最高层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；
• 但是该层的下一个节点是空节点（ leve[2]指向的是空节点），于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[1];
• 「元素：abc，权重：3」节点的 leve[1] 的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据「大于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]；
• 「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束

跳表节点层数设置

​ 跳表的相邻两层的节点数量的比例会影响跳表的查询性能。如下图示跳表，第二层的节点数量只有 1 个，而第一层的节点数量有 6 个。

​ 此时如果查找节点6，会发现这个场景的查询操作和链表的查询复杂度一样，需要在第一层的节点中依次顺序查找（复杂度就是 O(N) ）。因此为了降低查询复杂度，需要维持相邻层结点数间的关系

​ 跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)

​ 如何维持相邻两层的节点数量的比例为 2 : 1 ？

​ 如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。

​ Redis 则采用一种巧妙的方法是，跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

​ 具体的做法是，跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 64。

​ 虽然案例中的跳表的「头节点」都是 3 层高，但是其实如果层高最大限制是 64，那么在创建跳表「头节点」的时候，就会直接创建 64 层高的头节点。

为什么用跳表而不用平衡树？

​ 参考问题：为什么 Zset 的实现用跳表而不用平衡树（如 AVL树、红黑树等）？

• 从内存占用上来比较，跳表比平衡树更灵活一些（单节点的指针数）：
  • 平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小
  • 如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势
• 在做范围查找的时候，跳表比平衡树操作要简单
  • 平衡树的范围检索需进行中序遍历，如果不对平衡树做改造，这个操作实现比较复杂
  • 在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现
• 从算法实现难度上来比较，跳表比平衡树要简单得多
  • 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂
  • 跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速

7.quicklist

​ 在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候，List 对象的底层改由 quicklist 数据结构实现。

​ 其实 quicklist 就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

​ 在对压缩列表介绍时提到其不足，虽然压缩列表是通过紧凑型的内存布局节省了内存开销，但是因为它的结构设计，如果保存的元素数量增加，或者元素变大了，压缩列表会有「连锁更新」的风险，一旦发生，会造成性能下降。

​ quicklist 解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能

quicklist结构设计

​ quicklist 的结构体跟链表的结构体类似，都包含了表头和表尾，区别在于 quicklist 的节点是 quicklistNode。

typedef struct quicklist {
    //quicklist的链表头
    quicklistNode *head;      //quicklist的链表头
    //quicklist的链表尾
    quicklistNode *tail; 
    //所有压缩列表中的总元素个数
    unsigned long count;
    //quicklistNodes的个数
    unsigned long len;       
    ...
} quicklist;

​ 接下来看看，quicklistNode 的结构定义：

typedef struct quicklistNode {
    //前一个quicklistNode
    struct quicklistNode *prev;     //前一个quicklistNode
    //下一个quicklistNode
    struct quicklistNode *next;     //后一个quicklistNode
    //quicklistNode指向的压缩列表
    unsigned char *zl;              
    //压缩列表的的字节大小
    unsigned int sz;                
    //压缩列表的元素个数
    unsigned int count : 16;        //ziplist中的元素个数 
    ....
} quicklistNode;

​ 可以看到，quicklistNode 结构体里包含了前一个节点和下一个节点指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以 quicklistNode 结构体里有个指向压缩列表的指针 *zl。

​ 在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

​ quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题

8.listpack

​ quicklist 虽然通过控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来减少连锁更新带来的性能影响，但是并没有完全解决连锁更新的问题。

​ 因为 quicklistNode 还是用了压缩列表来保存元素，压缩列表连锁更新的问题，来源于它的结构设计，所以要想彻底解决这个问题，需要设计一个新的数据结构。

​ 于是，Redis 在 5.0 新设计一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

​

listpack结构设计

​ listpack 采用了压缩列表的很多优秀的设计，比如还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。

​ listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量， listpack 末尾也有个结尾标识， listpack entry 是 listpack 的节点。

主要包含三个方面内容：

• encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
• data，实际存放的数据；
• len，encoding+data的总长度；

​ 可以看到，listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

9.数据结构总结

SDS

​ 结合C语言字符串不足展开对SDS概念引入的理解：SDS的引入主要是为了解决C语言字符串的缺陷

• 引入len属性，优化获取字符串长度的时间复杂度
• 不依赖\0结尾标记，以支持二进制数据存储
• 引入allo、len属性，实现自动扩容机制，不会发生缓冲区溢出问题
• 通过设计多种不同类型的SDS数据结构、优化编译以节省内存空间

链表

​ 引入链表可以支持灵活存储不同类型的数据，但由于节点之间的存储内存不连续，因而无法充分利用CPU缓存的优势。且每个节点都要一个链表节点头的定义，内存开销比较大

压缩列表

​ 压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。其存在如下不足

• 基于紧凑型的内存布局能节省内存开销，但对于中间节点的查找复杂度高
• 存在连锁更新问题：空间扩展操作（即重新分配内存），连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能

​ 因此，压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新，也是能接受的。

哈希表

​ 哈希表是一种保存键值对（key-value）的数据结构，其优点在于它能以 O(1) 的复杂度快速查询数据。因为哈希表实际上是数组，所以可以通过索引值快速查询到数据（将 key 通过 Hash 函数的计算，就能定位数据在表中的位置），但是存在的风险也是有，在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也会越高。结合下述四个部分进一步掌握哈希表概念

• 什么是哈希冲突？=》当有两个以上数量的 kay 被分配到了哈希表中同一个哈希桶上时，此时称这些 key 发生了冲突
• 如何解决哈希冲突？=》Redis通过rehash、渐进式rehash方式解决哈希冲突
  • rehash：
    • rehash触发的条件：与负载因子有关
    • rehash过程：
      • 【1】正常请求与哈希表1交互
      • 【2】当触发了rehash操作，则将哈希表1的数据全部迁到哈希表2
      • 【3】rehash完成，将哈希表1内存释放，将哈希表2设置为哈希表1，并创建一个空白的哈希表以为下次rehash做准备
  • 渐进式rehash：为了解决上述rehash步骤【2】可能出现的大数据迁移导致Redis性能阻塞问题，将一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作
    • 渐进式rehash过程
      • 【1】给「哈希表 2」 分配空间
      • 【2】在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上

整数集合

​ 整数集合本质上是一块连续内存空间。整数集合的升级操作目的在于节省内存空间，且一旦进行了升级就无法降级

跳表

​ 跳表的引入是为了优化链表的查询效率，它是在链表基础上改进过来的，实现了一种「多层」的有序链表，以实现快速定位数据的目的。结合下述几个方面理解跳表的概念核心：跳表仅适用于元素有序的情况

• 跳表结构设计：多层的有序链表
• 跳表节点查询过程：从最高的节点开始按照规则依次检索，不满足条件则递减层级
• 跳表节点层数设置：层数的设置决定着检索的效率，跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)
• 为什么用跳表而不用平衡树？：从内存占用、范围查找效率、算法实现复杂度三个方面扩展

quicklist

​ quicklist 就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

​ quicklist 的引入可避免压缩列表的连锁更新风险，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能

listpack

​ listpack 采用了压缩列表的很多优秀的设计，比如还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。最主要的一点是，listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。