深入理解Redis数据结构

程序员文章站 2022-07-05 18:17:06

...

深入理解Redis数据结构

Redis

Redis（REmote DIctionary Server）是一个key-value存储系统，由Salvatore Sanfilippo开发，使用ANSI C语言编写，遵守BSD协议。

Redis的特性

1. 速度快

2. 基于键值对的数据结构服务器

3. 丰富的功能

4. 简单稳定

5. 客户端语言多

6. 持久化

7. 主从复制

8. 高可用和分布式

Redis 版本

Redis 3.0

Redis Cluster：Redis 的官方分布式实现
全新的 embedded string 对象编码结果，优化小对象内存访问，在特定工作负载下速度大幅提升
lru 算法大幅提升
migrate 连接缓存，大幅提升键迁移的速度
新的 client pause 命令，在指定时间内停止处理客户端请求

Redis 3.2

SDS 在速度和节省空间上都做了优化
新的 List 编码类型：quickList
新的 RDB 格式，但是仍然兼容旧的 RDB
加速 RDB 的加载速度

Redis 4.0

提供了模块系统，方便第三方开发者拓展 Redis 的功能
PSYNC 2.0：优化了之前版本中，主从节点切换必然引起全量复制的问题
提供了 RDB-AOF 混合持久化格式，充分利用了 AOF 和 RDB 的各自优势
提供了新的缓存剔除算法：LFU（Last Frequently Used），并对已有算法进行了优化
提供了 memory 命令，实现对内存更为全面的监控统计

Value 的通用结构

RedisObject

typedef struct redisObject{
    // String、List 等结构化类型
    unsigned type: 4;
    // 结构化类型的具体承载方式，如String 可以用int 或char[]   
    unsigned encoding:4; 
    // 对象最后一次被命令程序访问的时，用于清理长久不适用的对象
    unsigned lru: REDIS_LRU_BITS; 
    // 应用计数垃圾回收
    int refcount; 
    // 指向具体实现结构的地址
    void *ptr; 
}

内存回收

对象的引用计数信息会随着对象的使用状态而不断变化：

当创建一个新对象时，引用计数的值会被初始化为 1
当对象被一个新程序使用时，引用计数值会加一
当对象不再被一个程序使用时，引用计数值会减一
当对象的引用计数变为 0 时，对象所占用的内存会被释放

对象共享

除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用

在 Redis 中，让多个键共享同一个值对象需要执行以下两个步骤：

将数据库键的值指针指向一个现有的值对象
将被共享的值对象的引用计数加一

redis 启动时会对 0-9999的整数进行预创建，并且后续如果有需要使用时会共享这些对象

五种数据类型

字符串
哈希
列表
集合
有序集合

字符串

字符串类型的值实际可以是字符串（简单字符串，复杂字符串：JSON/XML），数字（整数，浮点数），甚至是二进制（图片，音频，视频），但值最大不能超过 512MB。

常用命令

数据结构

字符串的数据结构实现有三种

1. Int

8个字节的长整型（long类型）

2. raw

3.0版本：大于39个字节的字符串
3.2版本：大于44个字节的字符串

Redis 没有直接使用C语言传统的字符串表示，而是自己构建了一种名为_简单动态字符串（simple dynamic string，SDS）_的抽象类型，并将 SDS 作为 Redis 的默认字符串表示。

SDS除了用来保存数据库中的字符串值之外，还被用作 缓冲区（buffer）：AOF 模块中的 AOF 缓冲区，以及客户端状态中的输入缓冲区。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xo7Pg3PL-1591104740277)($resource/sds.png)]

SDS的优点

常数复杂度获取字符串长度，O(n) -> O(1)，保证 strlen 命令的效率。
杜绝缓冲区溢出，SDS 在修改前会先检查空间大小是否满足，不满足先扩容再修改。
减少修改字符串时带来的内存重分配次数。在 SDS 中，buf 数组长度不一定是字符串长度，可以包含未使用空间，通过 SDS 的空间预分配和惰性空间释放减少内存重分配次数。
空间预分配： SDS 增长时，分配额外的未使用空间，sds分配空间时预留buf （len < 1MB ? len * 2 + 1 : 1MB）
惰性空间释放： SDS 缩短时，不会立即回收内存
二进制安全，因为 SDS 使用 len 属性判断字符串是否结束而不是空字符。

3. embstr

3.0版本：小于等于39个字节的字符串
3.2版本：小于等于44个字节的字符串

embstr 编码是专门用于保存短字符串的一种优化编码方式，这种编码和 raw 编码一样，都使用 redisObject 结构和 sdshdr 结构来表示字符串对象。

raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构。
embstr 编码通过调用一次内存分配函数来分配一块连续的空间

Redis 没有为 embstr 编码的字符串对象编写任何相应的修改程序，所以 embstr 编码的字符串对象实际上是只读的。当我们对 embstr 编码的字符串对象执行任何修改命令时，程序会先将对象的编码从 embstr 转换成 raw ，然后再执行修改命令。

embstr编码的优点

embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降为一次。
释放 embstr 编码的字符串对象只需调用一次内存释放函数
数据保存在一块连续的内存里面，能够更好地利用缓存带来的优势

使用场景

利用Int 类型的 incr、decr 原子操作做计数器
限流，如同一手机号一分钟之内只能有5次请求，利用key 的计数限流，利用key过期取消限制
共享session，如Spring session
json序列化后的对象存储，用于对象内部属性不常变化的场景
利用setnx特性做分布式锁

List

列表类型是用来存储多个 有序、可重复 的字符串，一个列表最多可以存储 2^32 -1 个元素。在Redis中，可以对列表两端插入（ push）和弹出（ pop），还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是一种比较灵活的数据结构，可以充当栈和队列的角色。

常用命令

数据结构

List 内部有3种实现

1. zipList

列表元素个数小于 list-max-ziplist-entries 配置（默认512个）
同时列表中每个元素的值都小于 list-max-ziplist-value 配置（默认64字节）

ziplist的结构
[zlbytes][zltail][zllen][entry][entry]...[zlend]

zlbytes ：zipList总长度
zltail ：指向最末尾的元素
zllen：元素个数
zlend：恒定为 0xFF 定界符
entry：value元素
- 相邻前一个entry长度 previous_entry_length
- entry字描述内容类型和长度 encoding
- 内容本身，内容的长度由encoding 决定 content

entry字描述内容

❑ 00xxxxxx:String类型；长度小于64,0～63可由6位bit表示，即xxxxxx表示长度。
❑ 01xxxxxx|yyyyyyyy:String类型；长度范围是[64,16383]，可由14位bit表示，即xxxxxxyyyyyyyy表示长度。
❑ 10xxxxxx|yy…(32个).y:String类型，长度大于16383。
❑ 1111xxxx:integer型，integer本身内容存储在xxxx中，只能是1～13之间的这13个取值，即本类型长度部分已经包含了内容本身。
❑ 11? ? ? ? ? ? ：其余情况下redis用1个字节的类型长度部分表示了integer的其他几种情况，例如int_32、int_24等。

ziplist的连锁更新问题

每个节点的 previous_entry_length 属性占用的字节数与前一个节点的长度有关，当插入或删除节点时，节点长度变化，有可能导致 previous_entry_length 的内存扩容（1字节 -> 5字节），进而引发一系列连锁扩容。

LinkedList

linkedlist 编码的列表对象使用双端链表作为底层实现，每个双端链表节点（node）都保存了一个字符串对象，每个字符串对象都保存了一个列表元素。

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点灵活调整链表长度。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LhpOywVI-1591104740291)($resource/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8.png)]

双向链表的优点：

双端： 链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1)。

无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以NULL为终点。

带表头指针和表尾指针： 程序获取链表的表头节点和表尾节点的复杂度为 O(1)。

带链表长度计数器： 程序获取链表中节点数量的复杂度为 O(1)。

多态： 链表节点使用指针来保存节点值，并且可以通过 list 结构的 dup（复制节点的函数）、free（释放节点内存的函数）、match（比较节点是否相等的函数）三个属性为节点设置类型特定函数，所以链表可用于各种不同类型的值。

quicklist

quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 让存储紧凑，多个 ziplist 之间使用双向指针串接起来。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dV4NrLuZ-1591104740293)($resource/quicklist.png)]

使用场景

列表、栈等
- lpush + lpop = 栈
- lpush + rpop = 队列
- lpush + brpop = 消息队列
- lpush + ltrim = 有限集合
可以作为简单的消息队列，生产消费者任务容器
定时更新的排行榜
最新列表, 朋友圈点赞，评论列表等

Hash

存储key-value结构，其中value只能是 string型，不能继续存储 hash等结构

常用命令

存储结构

hashtable

和大多数哈希表实现相同

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mkzAfHF8-1591104740295)($resource/hash.png)]

zipList

哈希类型元素个数小于 hash-max-ziplist-entries 配置（默认512个）
同时所有值都小于 hash-max-ziplist-value 配置（默认64字节）

与list的不同的是，hash中 entry的个数总是偶数，奇数放key，偶数放value。

使用场景

hash 和购物车的使用场景非常契合，这也是hash的一个经典使用
对象存储，用于对象中部分属性频繁变化的场景

Set

集合（set）类型也是用来保存多个字符串元素，但和列表不同，集合 不允许有重复元素，且集合中的元素是无序的，不能通过索引下标获取元素。

一个集合最多可存储 2 ^32 -1 个元素，Redis除了支持集合内的增删改查，还支持多个集合取交集、并集、差集。

常用命令

存储结构

Set在Redis中以intset或hashtable来存储

intset

集合中的元素都是整数且元素个数小于 set-max-intset-entries 配置（默认512个）

intset 是 Redis 用于保存 整数值 的、有序的集合抽象数据类型，它可以保存类型为 int16_t、 int32_t 或 int64_t 的整数值，并且保证集合中不会出现重复元素。
intset查找时由于是有序数组，因此使用二分查找。并且为了提高二分查找效率，intset使用的保存数据的数组是int8_t [-128，127]。如果突然插入大于127的数字，则整个数组会升级为每2个int_8存放一个值，原数组的数据会向后扩展。

hashtable

hashtable中的value永远为NULL。

使用场景

好友、关注、粉丝、感兴趣的人等集合，并且set的一些操作很适合这类业务的特点
a. sinter命令可以获得A和B两个用户的共同好友
b. sismember命令可以判断A是否是B的好友
c. scard命令可以获取好友数量
d. 关注时，smove命令可以将B从A的粉丝集合转移到A的好友集合
随机展示，srandmember命令则可以从中随机获取几个
黑名单/白名单

Sorted-set

有序的set集合

常用命令

存储结构

ziplist

对于数据量很小的场景使用ziplist，参考hash的ziplist

hashable + skiplist

skiplist

和通用的跳表实现不同，Redis为每一个level对象增加了span字段，表示该level指向的forward节点和当前节点的距离，使得getByRank类的操作效率提升。skiplist每个节点高度随机生成。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-19EocxlD-1591104740296)($resource/skip-list.png)]

hashtable

跳表是一种实现顺序相关操作的较高效的数据结构，但它对于简单的ZSCORE操作效率并不高，hashtable的存在使得sorted-set中的map特性操作复杂度从O(N)降低为O(1)。

使用场景

排行榜系统
例如视频网站需要对用户上传的视频做排行榜，榜单的维度可能是多方面的：时间、播放数、获赞数。将获赞数作为分数（score）与用户ID绑定，可以实现获赞最多的排行，以及所有用户的获赞排行等。
延时队列
延时队列可以通过 Redis 的 zset 来实现。我们将消息序列化成一个字符串作为 zset 的 value，这个消息的到期处理时间作为 score，然后用多个线程轮询 zset 获取到期的任务进行处理。多个线程是为了保障可用性，但同时需要考虑并发争抢任务，确保任务不会被多次执行。

深入理解Redis数据结构