03.Redis底层存储常识原理

Redis 使用五种数据类型：String、List、Hash、Set、ZSet

每个类型都有不同的底层实现以提高内存效率和性能String 类型支持整数、短字符串（embstr）和长字符串（raw）存储

List 类型使用 quicklist 结构，结合了双向链表和压缩列表（listpack）

Hash 类型根据数据量使用 ziplist/listpack 或 hashtable 存储

Redis 通过这些结构优化了内存占用和查询效率，适合缓存、计数器、分布式锁等场景

# 00.Redis描述数据类型

通常我们了解的数据结构有字符串、双端链表、字典、压缩列表、整数集合等

但是Redis为了加快读写速度，并没有直接使用这些数据结构，而是在此基础上又包装了一层称之为RedisObject

RedisObject 有五种对象：String、List、Hash、Set、ZSet

首先Redis内部使用一个RedisObject对象来表示所有的key和value
RedisObject最主要的信息如下图所示
- type 代表一个value对象具体是何种数据类型
- encoding是不同数据类型在Redis内部的存储方式
- 普通字符串（type=string，encoding=raw或int）
- 如果是int则代表实际Redis内部是按数值型类存储，比如:"123" "456"这样的字符串
上面说的这种方法比较浪费内存，实际Redis提供了其他方法

# 01.字符串（string）

# 0、概述

扩容机制
- 当字符串长度小于1M时，扩容就是加倍现有空间（扩容机制）
- 如果字符串长度操作1M时，扩容时最多扩容1M空间，字符串最大长度为 512M
string使用场景
- string 类型可以用来存储，比如数字、文本、二进制数据等
- 1）缓存数据：提高访问速度和降低数据库压力
- 2）计数器：String 类型支持自增和自减操作，可以用来实现计数器功能
- 3）分布式锁：String 类型可以通过 SETNX 命令来实现分布式锁的功能
- 4）会话管理：存储用户的会话信息，比如用户 ID、登录状态、令牌等，通过设置过期时间来控制会话的有效期
- 5）序列化对象：比如 JSON、XML 等格式的数据，可以使用 Redis 的序列化和反序列化功能来实现对象的读写操作
- 6）限流：利用 expire 命令实现时间窗口内的访问控制

# 1、string三种存储结构

String 类型的值对象可以使用不同的底层结构来实现，包括embstr、raw 和 int 三种

String 类型的值对象并不是数组，但是它的 value 数据结构确实类似于数组

value 数据结构是一个字节数组（byte array），也就是一个连续的字节序列

这和数组的底层实现类似，数组也是一段连续的内存空间

和数组一样，Redis 中的 String 类型的值对象的长度也是固定的，不支持动态扩容

在创建 String 类型的值对象时，需要指定它的初始长度（数组可以动态扩容）

1）int：存储整数类型
- 当保存的是Long 类型整数时，RedisObject 中的指针就直接赋值为整数数据了
- 这样就不用额外的指针再指向整数了，这种保存方式通常也叫作 int 编码方式
2）embstr （小于等于 44 字节）
- 当保存的是字符串数据，并且字符串小于等于 44 字节时
- RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片
3）raw （大于 44 字节）
- 当字符串大于 44 字节时，是会给 SDS 分配独立的空间，并用指针指向 SDS 结构

# 2、embstr&raw 结构图

embstr存储结构图
- 占用64Bytes的空间，存储44Bytes的数据
- 前19个byte用于存储embstr 结构
- 中间的44个byte存储数据，最后为\0符号

raw 结构
- 当字符串大于 44 字节时，是会给 SDS 分配独立的空间，并用指针指向 SDS 结构

# 3、SDS结构体

当你保存的数据中包含字符时，String 类型就会用简单动态字符串（Simple Dynamic String，SDS）结构体来保存

buf：字节数组，保存实际数据，在数组最后加一个'\0'，会额外占用 1 个字节开销
len：表示 buf 的已用长度，不包括'\0'
alloc：表示 buf 的实际分配长度，不包括'\0'
flags：占 1 个字节，标记当前字节数组的属性，是sdshdr8还是sdshdr16等

下图表示：sdshdr8类型的字节数组，实际分配了 8 个长度，已使用 5 个长度

结构图长下面这个样子()

struct __attribute__ ((__packed__)) hisdshdr8 {
    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[];
};

1
2
3
4
5
6

# 02.list（列表）

list 类似双向链表结构，首尾增删改查 O(1)，中间增删改查O(n)

# 0、概述

结构替换
- 在Redis3.2之前，list使用的是linkedlist和ziplist
- 在Redis3.2~Redis7.0之间，list使用的是quickList，是linkedlist和ziplist的结合
- 在Redis7.0之后，list使用的也是quickList，只不过将ziplist转为listpack
list 使用场景
- 消息队列：可以作为消息队列使用
- 最新列表：
  - Redis List 类型可以用来存储最新的 N 个元素，比如最新的日志信息、最新的新闻、最新的评论等
  - 通过 LPUSH 和 LTRIM 命令可以实现在列表头部插入元素并保持列表长度不超过 N
  - 历史列表：
    - Redis List 类型可以用来存储历史记录，比如用户的浏览历史、购物历史等
    - 通过 LPUSH 命令可以在列表头部插入元素，通过 LRANGE 命令可以获取列表中的一段元素
- 延时队列：
  - Redis List 类型可以用来实现延时队列
  - 通过 LPUSH 和 BRPOP 命令可以实现在列表头部插入元素并在列表尾部阻塞取出元素
  - 如果列表为空，BRPOP 命令会等待指定的超时时间
几种数据类型对比
- linkedlist：本质是一个双向链表
- ziplist：字节小于 64 字节，数量小于 512 个，使用 ziplist 存储（占用一块连续的内存空间)
- quicklist: “链表 + ziplist” 组成的 quicklist 来避免单个 ziplist 过大，降低连锁更新的影响范围
- listpack: 和 ziplist 类似，不记录上一项的长度，解决了ziplist连锁更新问题

# 1、linkedlist（双端列表）

linkedlist 实际上使用的就是双向链表数据结构类型存储
likedlist 弊端
- linkedlist 有 prev、next 两个指针，数据量小时，指针占用的空间会超过数据占用的空间
- linkedlist 是链表结构，在内存中不是连续的，遍历的效率低下

# 2、ziplist（压缩列表）

List 的每个元素的占用的字节小于 64 字节，数量小于 512 个，使用 ziplist 存储

ziplist 压缩列表，占用一块连续的内存空间，适合存储小量数据，内存使用率高

ziplist 由多个部分组成，具体如下

ziplist 中可以包含多个 entry 节点，每个节点可以存放整数或者字符串
1）元数据：
- zlbytes：4 字节，记录 ziplist 占用的总字节数
- zltail：4 字节，指向最后一个 entry 的偏移量，便于快速定位
- zllen：2 字节，记录 entry 的总数
- zlend：1 字节，结束标志，值为 255

2）entry 节点：
- prevlen：记录前一个 entry 占用的字节数，支持逆序遍历
- encoding：当前 entry 的类型和长度；若为 "11"，则表示存放的是整数，其它值表示存放字符串
- entry-data：实际存放数据的区域如果 entry 是整数类型，则 entry-data 与 encoding 合并，不单独存在

ziplist 比 linkedlist 优势在哪里
- 省去 prev 和 next 指针的开销，使用连续内存存储
- 支持 O(1) 的时间复杂度来访问和修改节点
ziplist 不能保存过多数据
- ziplist 存储空间是连续的，当插入新的 entry 时
- 内存空间不足就需要重新分配一块连续的内存空间，引发连锁更新的问题
连锁更新
- 每个 entry 都用 prevlen 记录了上一个 entry 的长度
- 从当前 entry B 前面插入一个新的 entry A 时，会导致 B 的 prevlen 改变，也会导致 entry B 大小发生变化
- entry B 后一个 entry C 的 prevlen 也需要改变，以此类推，就可能造成了连锁更新
- 连锁更新会导致 ziplist 的内存空间需要多次重新分配，直接影响 ziplist 的查询性能

# 3、quicklist

quicklist 由多个 ziplist 组成，每个 ziplist 被称为一个“块”，这些块通过双向链表链接
每个块可以独立扩展，适应更多元素，避免单个 ziplist 的大小限制
其实这样实现依旧没有解决ziplist连锁更新的问题
最后7.0 设计了另一个内存紧凑型数据结构 listpack版本替换掉 ziplist

# 4、listpack

listpack和 ziplist 类似，也是用一块连续的内存空间来保存数据
一共四部分组成
- tot-bytes：记录 listpack 占用的总字节数
- num-elements：占用 2 字节，记录 listpack elements 元素个数
- elements：listpack 元素，保存数据的部分
- listpack-end-byte：结束标志，占用 1 字节，值固定为 255

listpack 如何解决连锁更新问题
- listpack和 ziplist 类似，最大的区别是 elements 部分
- 每个 element 只记录自己的长度，不像 ziplist 的 entry，记录上一项的长度
- 当修改或者新增元素的时候，不会影响后续 element 的长度变化，解决了连锁更新的问题
listpack 查找效率会稍低
- listpack 中的元素是连续存储的，但由于采用了可变长度编码，查找时需要解析每个元素的长度
- 因此在查找时需要额外的计算时间来确定每个元素的起始位置
ziplist 查找效率相对高
- ziplist 每个元素（entry）都包含一个 prevlen 字段，用于记录前一个元素的长度
- 你可以直接计算下一个元素的起始位置，而无需逐个比较

# 03.hash（字典）

# 0、概述

hash 说明
- Redis中的字典也是HashMap（数组+列表）的二维结构
- 不同的是Redis的字典的值只能是字符串
- 最多可以存储 2^32 - 1 个字段
Hash类型的底层实现有三种
- 1）ziplist：Redis7.0之前使用
- 2）listpack：Redis7.0之后使用
- 3）hashtable：哈希表，类似map
  - 个数超过512或任意一个键或者值得长度大于64个才会使用 hashtable 存储
  - 这样做是因为数据量小时使用 ziplist 更节省内存
应用场景
- 用户信息: 利用 hset 和 hget 命令实现对象属性的增删改查
- 购物车: 利用 hincrby 命令实现商品数量的增减
- 配置信息: 利用 hmset 和 hmget 命令实现批量设置和获取配置项

# 1、ziplist&listpack

ziplist所有的字段和值顺序地存储在一块连续的内存中
每个字段都用一个字节数组来存储，数组包含了两部分数据，即 key 和 value
查询操作的时间复杂度是 O(N)，其中 N 是 Hash 中的字段数量
显然是ziplist在field个数太大、key太长、value太长三者有其一的时候会有以下问题
- ziplist每次插入都有开辟空间，连续的
- 查询的时候，需要从头开始计算，查询速度变慢
- 所以个数超过512个时会使用 ziplist 存储，节省内存

listpack和 ziplist 类似，不记录上一项的长度，解决了ziplist连锁更新问题

# 2、hashTable

hashTable是一种散列表结构，它将字段和值分别存储在两个数组中，并通过哈希函数计算字段在数组中的索引
如果field的个数超过512个或者field中任意一个键或者值得长度大于64个byte会使用 hashTable 存储
eg: (name=zhangsan)
- 哈希表使用两个数组分别存储字段（field）和对应的值（value）
- Redis 同样使用哈希函数计算字段（name）的哈希值，并找到对应的索引
- 通过计算的索引，Redis 访问存储字段和对应值的数组，查找 name 的值（在本例中为 zhangsan）

hashTable 扩容

1）初始化新的hash表
- 首先，Redis会创建一个新的hash表，这个hash表的大小是当前hash表大小的2倍
- 所以当负载因子（元素数量/哈希桶数量）超过1时，就需要扩容来减少哈希冲突
2）迁移数据
- Redis会逐步将旧hash表中的数据迁移到新的hash表中
- 这个过程是逐步进行的，而不是一次性完成，主要是为了避免在迁移数据时阻塞Redis的其他操作
- 处理命令前，Redis会迁移一部分数据，然后再去处理命令请求(包子服务可用的同时迁移数据)
- 实现方案
  - 具体来说，Redis会维护一个rehash索引，这个索引表示当前已经迁移的哈希桶的位置
  - 每次迁移数据时，都会从这个位置开始，迁移一部分数据，然后更新这个索引
当所有的数据都迁移到新的hash表中后，就完成了rehash过程
这个时候，Redis会释放旧的hash表，将新的hash表设置为当前的hash表
对于读操作，Redis会首先在新的hash表中查找，如果没有找到，再去旧的hash表中查找
对于写操作，Redis会直接在新的hash表中进行

# 04.set（集合）

set 介绍
- set是一个无序的字符串集合，它不允许重复的元素
- 一个 set类型的键最多可以存储 2^32 - 1 个元素
set底层结构
- intset，整数集合
  - intset是一种紧凑的数组结构，它只保存int类型的数据
  - 它将所有的元素按照从小到大的顺序存储在一块连续的内存中
- hashtable（哈希表）
  - 哈希表和 hash 类型的哈希表相同，它将元素存储在一个数组中
  - 并通过哈希函数计算元素在数组中的索引
set 应用场景
- 去重，利用 sadd 和 scard 命令实现元素的添加和计数
- 交集，并集，差集，利用 sinter，sunion 和 sdiff 命令实现集合间的运算
- 随机抽取，利用 srandmember 命令实现随机抽奖或者抽样

# 05.zset（有序集合）

# 0、概述

zset说明
- zset是一种有序集合类型，它可以存储不重复的字符串元素
- 通过权重值来为集合中的元素进行从小到大的排序
- zset 的成员是唯一的，但权重值可以重复
- 一个 zset类型的键最多可以存储 2^32 - 1 个元素
结构说明
- 元素个数小于128，长度小于 64 时使用ziplist 和 listpack
  - ziplist（Redis7.0之前使用）和listpack（Redis7.0之后使用）
- 否则使用 skiplist 跳表
zset应用场景
- 排行榜，利用 zadd 和 zrange 命令实现分数的更新和排名的查询
- 延时队列，利用 zadd 和 zpopmin 命令实现任务的添加和执行，并且可以定期地获取已经到期的任务
- 访问统计，可以使用 zset 来存储网站或者文章的访问次数，并且可以按照访问量进行排序和筛选
value的数据结构（跳跃列表+字典）
- 1.zset一方面是一个set，保证了内部的唯一性
- 2.另一方面它可以给每一个value赋予一个score，代表这个value的权重
- 3.zset内部实现用的是一种叫做“跳跃列表”的数据结构
- 4.zset最后一个元素被移除后，数据结构就会被自动删除，内存也会被回收

# 1、普通有序链表演变

普通有序链表演变
- 假如我们每相邻两个节点增加一个指针，让指针指向下下节点
- 新增加的指针连成了一个新的链表，但是它包含的节点个数只有原来的一半

但是新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的 2:1 的对应关系
如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整
这会让时间复杂度重新退化为 O(N)，删除数据也有同样的问题
skiplist 方案
- skiplist 为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系
- 而是为每个节点随机出一个层数（level），新插入的节点就会根据自己的层数决定该节点是否在这层的链表上

# 2、skiplist 跳跃表

Redis 的跳跃表是由Redis.h/zskiplistNode 和 Redis.h/zskiplist 两个结构定义

zskiplistNode 用于表示跳跃节点

而 zskiplist 结构则用于保存跳跃表节点的相关信息（如节点数量、头位指针）
比如节点的数量以及指向表头节点和表尾节点的指针等等

1）zskiplist(跳跃节点)
- header：指向跳跃表的表头节点
- tail：指向跳跃表的表尾节点
- level：记录目前跳跃表内，层数最大的那个节点层数（表头节点的层数不计算在内）
- length：记录跳跃表的长度，也就是跳跃表目前包含节点的数量（表头节点不计算在内）

2）zskiplistNode(位于 zskiplist 结构右侧)
- 层（level）
  - 节点中用L1、L2、L3 等字样标记节点的各个层
  - 每个层都带有两个属性：前进指针和跨度
    - 前进指针用于访问位于表尾方向的其它节点
    - 跨度则记录了前进指针所指向节点和当前节点的距离
- 后退（backward）指针
  - 节点中用 BW 字样标识节点的后退指针，它指向位于当前节点的前一个节点
  - 后退指针在程序从表尾向表头遍历时使用
- 分值（score）
  - 各个节点中的 1.0、2.0 和 3.0 是节点所保存的分值
  - 在跳跃表中，节点按各自所保存的分值从小到大排列
- 成员对象（obj）
  - 各个节点中的 o1、o2 和 o3 是节点所保存的成员对象

# 3、skiplist 插入数据

1）查找数据
- 在skiplist中查询一个元素的时间复杂度为 O(log N)，其中 N 是 skiplist 中的节点数量
- 第一，首先从 skiplist 的顶层开始，遍历每一层的节点
- 第二，如果当前节点的下一个节点的值大于要查询的值，就转到当前节点的下一层继续搜索
- 第三，直到找到要查询的节点或者搜索到了最底层
2）插入数据
- 在skiplist中插入一个元素的时间复杂度也为 O(log N)
- 第一，从 skiplist 的顶层开始，查找插入位置
- 第二，然后将新元素插入到适当的位置中
  - 插入节点，并调整受影响节点每层的 forward 指针和 span
  - 调整 backward
- 第三，插入新元素时，需要随机生成一个层数，然后将新元素插入到这个层数及其以下的所有层中

# 06.Bitmap

概述
- bitmap不是一个独立的数据类型，而是一种特殊的 string 类型
- 它可以将一个 string 类型的值看作是一个由二进制位组成的数组，并提供了一系列操作二进制位的命令
- 一个 bitmap 类型的键最多可以存储 2^32 - 1 个二进制位
- 它和 string 类型相同，只是在操作时会将每个字节拆分成 8 个二进制位
应用场景
- 统计用户活跃度，利用 setbit 和 bitcount 命令实现每天或每月用户登录次数的统计
- 实现布隆过滤器，利用 setbit 和 getbit 命令实现快速判断一个元素是否存在于一个集合中
- 实现位图索引，利用 bitop 和 bitpos 命令实现对多个条件进行位运算和定位
bitmap 存储结构

# 07.stream

概述
- stream 是一个类似于日志的数据结构，它可以记录一系列的键值对，每个键值对都有一个唯一的 ID
- 一个 stream 类型的键最多可以存储 2^64 - 1 个键值对
- stream 类型的底层实现是 rax（基数树），它是一种压缩的前缀树结构
- 它将所有的键值对按照 ID 的字典序存储在一个树形结构中
- rax 可以快速地定位、插入、删除任意位置的键值对
应用场景
- 消息队列，利用 xadd 和 xread 命令实现生产者消费者模式
- 操作日志，利用 xadd 和 xrange 命令实现操作记录和回放
- 数据同步，利用 xadd 和 xreadgroup 命令实现多个消费者组之间的数据同步

# 08.Hyperloglog

概述
- HyperLogLog 是一种概率数据结构，用于在恒定的内存大小下估计集合的基数（不同元素的个数）
- 它不是一个独立的数据类型，而是一种特殊的 string 类型
- 它可以使用极小的空间来统计一个集合中不同元素的数量，也就是基数
- 一个 hyperloglog 类型的键最多可以存储 12 KB 的数据
- 注：hyperloglog 误差率为 0.81%（真实基数为 1000，结果在 981 到 1019 ）
应用场景
- 统计网站的独立访客数（UV）
- 统计在线游戏的活跃用户数（DAU）
- 统计电商平台的商品浏览量
- 统计社交网络的用户关注数
- 统计日志分析中的不同事件数

# 09.GEO

概述
- geospatial 是一种用于存储和查询地理空间位置的数据类型
- 它基于 sorted set 数据结构实现，利用 geohash 算法将经纬度编码为二进制字符串，并作为 sorted set 的 score 值
- Redis geospatial 提供了一系列的命令来添加、删除、搜索和计算地理空间位置
应用场景
- 统计某个区域内的商家或用户数量
- 查询某个位置附近的餐馆或酒店
- 计算两个位置之间的距离或行驶时间
- 显示某个位置周围的景点或活动

# 10.Bitfield

概述
- bitfield结构是基于字符串类型的一种扩展
- 可以让你对一个字符串中的任意位进行设置，增加和获取操作，就像一个位数组一样
使用场景
- 用一个32位的无符号整数来表示用户的金币数量，用一个32位的无符号整数来表示用户杀死的怪物数量，可以方便地对这些数值进行设置，增加和获取
- 用一个16位的有符号整数来表示用户的等级，用一个16位的有符号整数来表示用户的经验值，可以方便地对这些数值进行设置，增加和获取
- 用一个8位的无符号整数来表示用户的性别，用一个8位的无符号整数来表示用户的年龄，可以方便地对这些数值进行设置，增加和获取

Bitfield的使用场景与bitmap类似，主要是一些需要用不同位长度的整数来表示状态或属性的场合

参考博客1 (opens new window) 参考博客2 (opens new window)

← 02.Redis基础 04.各种数据类型操作→