Redis数据结构与类型

Redis 的数据结构

简单动态字符串（SDS）

• 简单动态字符串（SDS）：Redis 自己构建的抽象类型，并作为默认字符串类型使用

• C 字符串只会作为 Redis 字符串字面量用在一些无需对字符串进行修改的地方，比如打印日志

• 除了用来保存数据库的字符串外，SDS 还被用作缓冲区（buffer）：AOF 模块的 AOF 缓冲区，客户端状态中的输入缓冲区

• SDS 的优点：

  1. 常数复杂度获取字符串长度
  2. 杜绝缓冲区溢出
  3. 减少修改字符串长度时所需的内存重分配次数
  4. 二进制安全
  5. 兼容部分 C 字符串函数

SDS 的结构

• SDS 遵循 C 字符串中以空字符结尾的管理，保存空字符串的 1 字节空间不计算在 len 中
  • 好处是，SDS 可以直接复用 C 语言库中的一些函数

SDS 和 C 字符串的区别

• C 字符串不记录长度，O(n)获取长度，但是 SDS 可以在 O(1)复杂度获取长度
• C 字符串不记录长度可能会导致缓冲区溢出（buffer overflow），SDS API 需要对 SDS 修改时，会先检查是否满足修改所需的要求，如果不满足，就会自动将 SDS 的空间扩展至执行修改所需的大小

空间扩展策略

如果类似 C 字符串，每次修改字符串都要进行内存重分配的话，对性能会有很大影响

• SDS 数组里面可以 包含未使用的字节，由 free 属性记录
• 通过未使用空间，SDS 实现了 空间预分配 和 惰性空间释放 两种优化策略

1. 空间预分配

• 当 SDS 的 API 对一个 SDS 进行修改的适合，程序 不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间
• 如果 SDS 修改后长度小于 1MB，那么程序 分配和 len 同样大小的未使用空间（free）
• 如果修改后大于 1MB，那么程序会 分配 1MB 的未使用空间
• 通过预分配策略，SDS 将连续增长 N 次字符串所需的内存分配次数 从必定 N 次降低为最多 N 次

2. 惰性空间释放

• 当 SDS 的 API 缩短 SDS 保存的字符串时，程序不立刻使用内存重分配来回收缩短后多出来的字节，而是用 free 属性记录下来，下次使用

特性

• 二进制安全：SDS 使用 len 属性的值来记录长度，所以 SDS 可以存储一系列二进制数据（这样就不用担心碰到\0 就结束的问题了）

• 兼容部分 C 字符串函数：SDS 遵循以空字符串结尾的惯例，API 总会将 SDS 保存的数据的末尾置为空字符串，所以可以使用 C 语言的部分函数

SDS API

Redis 链表（list）

• 链表被广泛用于实现 Redis 的各种功能，比如列表键、发布与订阅、慢查询、监视器等

Redis 链表结构

• 链表结构体：

• 链表结点结构体：

• Redis 链表整体结构：

• list 结构为链表提供了表头指针 head 和表尾指针 tail，以及链表长度的计数器 len；
• dup、free、match 成员则用用于实现多态链表所需的类型特定函数（三个回调函数）：
  • dup 函数用于复制链表节点所保存的值
  • free 函数用于释放链表节点所保存的值
  • match 函数用于比对链表节点所保存的值和另一个输入值是否相等

特性

• 双端：链表节点带有 prev 和 next 指针
• 无环：表头的 prev 指针和表尾的 next 指针都指向 NULL
• 带表头指针和表尾指针，获取表头表尾复杂度都是 O(1)
• 带链表长度计数器：获取节点数量的复杂度为 O(1)
• 多态：链表节点用 void*保存节点值，通过 list 的 dup、free、match 为节点值设置类型特定的函数，所以链表可以保存不同类型的值

链表和链表节点 API

Redis 字典（dict）

• 字典：又称为符号表、关联数组或映射，是用于保存键值对的数据结构
• Redis 的数据库就是使用字典来作为底层实现的，对数据库的增删改查都是建立在字典的操作之上的

Redis 字典结构

Redis 字典所使用的哈希表结构：

• 每个 dictEntry 结构保存着一个键值对
• size 记录了哈希表的大小，也就是 table 数组的大小
• used 数据记录了哈希表目前已有节点（键值对）的数量
• sizemask 属性的值总是等于 size - 1，用于哈希算法相关

哈希表节点：

• key 保存键值对中的键，v 属性保存值：键值对的值可以是一个指针，或者是一个整数（多态）
• next 属性指向另一个哈希表节点的指针（拉链法解决哈希冲突）

Redis 的字典结构

• type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的，每个dictType结构保存了一簇用于特定特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数

• privdata 属性保存了需要传递给那些特定函数的可选参数
• ht 属性包含两个项的数组，数组的每个项都是一个哈希表，一般只使用 ht [0]，ht[1]仅在rehash的时候使用（rehash 时将 ht [0] 的键值 hash 到 ht [1] 上，然后再将 ht [0] 置为 ht [1]）
• rehashidx 也与 rehash 有关，记录了rehash目前的进度，如果目前没有在执行rehash，它的值为-1

哈希算法

• Redis 用 MurmurHash2算法 作为计算键的哈希值：即使输入的键有规律，该算法也能给出一个很好的随机分布性，计算速度也很快

• Redis 的哈希表使用 链地址法来解决键冲突

• 因为 dictEntry 节点组成的链表没有指向表尾链表的指针，所以用 头插法 插入冲突

哈希表的扩展与收缩

当以下条件之一被满足时，程序会自动开始对哈希表执行 扩展 操作：

1. 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且 哈希表的负载因子大于等于 1
2. 服务器目前正在执行 BGSAVE 命令或者 BGREWEITEAOF 命令，并且 哈希表的负载因子大于等于 5

根据 BGSAVE 和 BGREWRITEAOF 命令是否正在执行，服务器进行扩展的负载因子不相同，这是因为 Redis 需要创建当前服务器进程的子进程，而大多操作系统采用写时复制（WriteOnCopy）技术来优化子进程的使用效率，所以 Redis 尽量避免在子进程存在期间进行哈希扩容，这可以避免不必要的内存写入操作，最大限度节约内存

当哈希表的 负载因子小于 0.1 时 ，程序自动开始对哈希表执行 收缩 操作

Redis 的 rehash

• 为了让哈希表的负载因子维持到一个合理的范围内，程序需要对哈希表的大小进行相应的扩展和收缩
• 扩展和收缩哈希表的工作可以通过执行 rehash（重新散列）操作来完成
• rehash 步骤：
  1. 为字典的 ht [1] 哈希表分配空间：
     • 如果是扩展，ht [1] 的大小为第一个大于等于 ht [0].used*2 的 \(2^n\)
     • 如果是收缩，那么 ht [1] 的大小为第一个大于等于 ht [0].used 的 \(2^n\)
  2. 将保存在 ht [0] 中的所有键值对 rehash 到 ht [1] 上面
  3. 当都迁移到 ht [1] 上之后，释放 ht [0]，将 ht [1] 设置为 ht [0]，并为 ht [1] 新创建一个空白哈希表，为下一次 rehash 做准备

渐进式 Rehash

• redis 的 rehash 不是一次性、集中性地完成的，而是 分多次、渐进式地完成（在数据量特别大的情况下，避免对服务器性能造成影响）

渐进式 Rehash 步骤：

1. 为 ht [1] 分配空间，让字典 同时持有ht[0]和ht[1]两个哈希表
2. 在字典中维护一个索引计数器变量 rehashidx，并值设置为 0，表示 rehash 工作正式开始（没开始是-1）
3. rehash 内，如果执行增删改查，程序会将顺带将 ht [0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht [1]，当rehash工作完成之后，程序将rehashidx属性的值增一
4. 当整体 rehash 完毕之后，rehashidx 值重新置为-1，表示 rehash 结束

渐进式 rehash 执行期间内的哈希表操作

• rehash 时，字典同时又两个哈希表，删除、更新、查找操作会在两个哈希表（没有新增！）
• 如果查找一个键的话，会 先在ht[0]上查找，如果没有找到就会在ht[1]上查找
• 渐进式 rehash 时，新添加的键值对一律被保存到ht[1]中，ht[0]不进行任何添加操作，这保证了 ht [0] 包含的键值对只减不增，最后 ht [0] 会变成空表

字典 API

跳跃表（skiplist）

• 跳跃表（skiplist）是一种有序的数据结构，查找平均 O(logN)，最差 O(N)

跳跃表的实现

typedef struct zskiplist {
 // 表头和表尾
 structz skiplistNode *header, *tail;
 //表中节点数量
 unsigned long length;
 // 表中层数最大的节点的层数
 int level;
} zskiplist;

• header：指向跳表表头节点
• tail：指向跳表表尾节点
• level：记录目前跳表层数最大的那个节点的层数（表头节点层数不算）
• length：记录跳表的长度（不算表头）

跳跃表节点

• 层：level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，可以通过这些层加快访问其他节点的速度

  • 每次创建一个新节点，会根据 幂次定律 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，大小就是高度

• 前进指针：用于从表头向表尾方向访问节点

• 跨度（level [i].span）：用于记录两个节点之间的距离，两个节点跨度越大，相距越远

  • 指向 NULL 的所有前进指针跨度为 0
  • 所有沿途访问过的所有层的跨度加起来，就是目标节点在跳跃表中的排位

• 后退指针：每个节点都只有一个后退指针，每个节点 只能通过后退指针跳到前一个节点

• 分值和成员：

  • 分值（score）是一个 double 类型的浮点数，节点按分值从小到大排序
  • 成员（obj）是一个指针，指向一个字符串对象，字符串对象保存一个 SDS

同一个跳跃表中，各个节点的 obj 必须是唯一的，但是 score 可以是多个

跳跃表 API

整数集合（intset）

intset 是 Redis 用于保存整数值的抽象数据结构，可以保存类型为 int16_t, int32_t, int64_t 的整数值

只包含整数值元素的集合，是 集合键的底层实现之一

• 以有序、无重复的方式保存集合元素，有需要时会自动根据新添加的元素类型改变数组类型

整数集合结构

contents 数组是整数集合的底层实现：每个元素都是 contents 数组的一个数组项（item），各个项从小到大排序，并且不包含任何重复项

• length：记录了 contents 整数集合的元素个数

• contents：属性声明为 int8_t 类型的数组，实际上不保存任何 int8_t 类型的值，真正类型取决于 encoding 属性的值

• encoding：

  • INTSET_ENC_INT16，就是保存 int16_t 类型的数组

  • INTSET_ENC_INT32，就是保存 int32_t 类型的数组

  • INTSET_ENC_INT64，就是保存 int64_t 类型的数组

编码升级

如果新增元素的值超出当前编码类型的值范围，就会进行 upgrade 操作，然后才能将新元素添加进去

升级整数集合并添加新元素分为三步进行：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2. 将底层数组现有的所有元素转换成与新元素相同的类型，并将转换后的元素放置到正确的位置，放置元素过程中，需要维持底层数组的有序性不变
3. 将新元素添加到底层数组中

升级之后新元素的摆放位置

因为引发升级意味新元素比现有所有元素长度都长，所以要么大于所有元素，要么小于所有元素（负数）

• 小于情况，新元素放置在底层数组的最开头
• 大于情况：新元素放置在底层数组的最末尾

升级的好处：

• 提升整数数组的灵活性：可以随意添加不同类型的元素，会自动升级，不必担心类型错误
• 尽可能节约内存空间：可以同时保存三种类型的值，只在有需要的时候升级

整数集合不支持降级操作，一旦升级就会保持升级的状态

整数集合 API

压缩列表（ziplist）

压缩列表是列表键和哈希键的底层实现之一，是 Redis 为了节约内存开发的

压缩列表的结构

一个压缩列表可以保存任意多个节点，每个节点可以保存一个字节数组或者一个整数值

• zlbytes：记录整个压缩列表占用的内存字节数：对压缩列表内存重分配或计算 zlend 时使用
• zltail：表尾节点距离起始地址有多少字节
• zllen：记录了压缩列表包含的节点数量
  • 当该值小于 UINT16_MAX（65535）时，这个属性的值就是压缩列表包含节点的数量；
  • 等于 UINT16_MAX 时，节点真实数量需要遍历得到
• entryX：压缩列表包含的各个节点，长度由节点保存的内容决定
• zlend：特殊值 0xFF（十进制 255），用于标记压缩列表的末端

压缩列表的节点构成

• 节点可以保存一个字节数组或者一个整数值
• previous_entry_length：记录压缩列表中前一个节点的长度
  • 如果前一个节点的长度小于 254 字节，那么该属性长度为 1 字节
  • 如果大于等于 254 字节，那么该属性长度为 5 字节：其中属性的第一字节会被设置为 0xFE(十进制值 254)，之后四个字节用于保存前一个节点的长度
• encoding：记录节点的 content 属性所保存的数据类型和长度

• content：负责保存节点的值，值的类型和长度由节点的 encoding 属性决定

连锁更新

因为 previous_entry_length 属性记录了前一个节点的长度，如果在表头插入一个超过 254 长度的节点，第二个节点会 previous_entry_length 会扩展到 5 字节，此时后续节点也会因为前一个节点长度变长后（如果超过 254 字节），就会引发升级；

• 连锁更新最坏情况下回对压缩列表执行 N 次空间重分配操作，而每次重分配的最坏复杂度在 O(N)，所以连锁更新最坏复杂度在 O(N^2)

当时造成性能问题概率很低：很难大量节点同时处于 250~254 长度之间

压缩列表 API

数据类型（对象）

Redis 没有直接使用上面的数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统：

• 包括了 字符串对象、列表对象、哈希对象、集合对象 和 有序集合对象 这五种类型的对象

对象的类型和编码

Redis 创建键值对时，至少创建两个对象，一个对象用作 Key，另一个用作 Value

• Redis 的每个对象都由一个 redisObject 结构表示，该结构中和保存数据有关的三个属性分别是 type 属性、encoding 属性和 ptr 属性

• type：记录了对象的类型

  • REDIS_STRING：字符串对象 "string"
  • REDIS_LIST：列表对象 "list"
  • REDIS_HASH：哈希对象 "hash"
  • REDIS_SET：集合对象 "set"
  • REDIS_ZSET：有序集合对象 "zset"

• encoding：记录了对象所使用的编码，也就是这个对象使用了上面数据结构作为底层实现

  • 有 long类型整数、embstr编码的SDS、SDS、字典、双端链表、压缩列表、整数集合、跳跃表和字典

Redis3.2 后，列表的 ziplist 和 linkedlist 都被 quicklist 取代，quicklist 成为了 list 的唯一实现，quicklist 结合了 ziplist 和 linkedlist

• 每种类型的对象都至少使用了两种不同的编码，使用 OBJECT ENCODING 命令可以查看一个数据库键的值对象的编码

String 字符串

• 字符串对象的编码可以是 int、raw 或者 embstr
• 如果字符串保存的是一个整数值，并且这个整数值可以用 long 类型来表示，那么对象会用将其转换成整数值保存
• 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于 32 字节，那么字符串对象使用一个 SDS 来保存这个值
• 如果保存的是字符串值，长度小于 32 字节，那么会用 embstr 编码方式来保存这个字符串值

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

• 但 raw 会调用两次内存分配函数来分布创建 redisObject 和 sdshdr
• 但是 embstr 只会调用一次来分配连续的内存块，存储 redisObject 和 sdshdr

优点：

• 创建调用两次内存分配变为一次

• 释放也只需要一次

• embstr 因为所有数据保存在一块连续的内存中，所以更好利用缓存带来的优势

• 可以用 long double 表示的浮点数在 redis 中也是用字符串保存的

编码的转换

• int 和 embstr 的字符串对象在条件满足的情况下会被转换成 raw 编码的字符串（比如使用 append 命令）
• Redis 没有为 embstr 编写任何相应的修改程序，所以 embstr 编码的字符串对象实际上是只读的，对 embstr 修改会先被转换成 raw 再修改

字符串相关命令

List 列表

• 列表对象的编码使用 quicklist（Redis3.2 前使用 ziplist 和 linkedlist）
• 在 Reids3.2 前，当所有字符串元素长度小于 64 字节并且元素数量小于 512 个，用 ziplist；否则用 linkedlist

列表命令

Hash 哈希

• 哈希对象的编码可以是 ziplist 和 hashtable
• ziplist 编码的哈希对象使用压缩列表作为底层实现，保存了同以键值对的两个节点总是紧挨再一起，保存键的在前，值的灾后
• hashtable 编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存
  • 字典的每个键都是一个字符串类型，对象中保存了键值对的键
  • 字典中的每个值都是一个字符串类型，对象中保存了键值对的值

编码转换

• 当哈希对象同时曼珠以下两个条件时，哈希对象使用 ziplist 编码：

  1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节

  2. 哈希对象保存的键值对数量小于 512 个；不能满足这两个条件的哈希对象需要使用 hashtable 编码

• 当任意一个条件不被满足，就会转换成 hashtable

哈希命令

Set 集合

• 集合对象的编码可以是 intset 和 hashtable

• intset 编码的集合对象使用整数集合作为底层实现

• hashtable 使用字典，字典的每个键都是一个字符串对象，而值都是 NULL

编码转换

当集合对象同时满足，对象使用 intset 编码：

1. 集合对象保存的值都是整数值
2. 集合对象保存的元素数量不超过 512 个

集合命令

ZSet 有序集合

• 有序集合的编码可以是 ziplist 和 skiplist

• ziplist 编码使用压缩列表，第一个节点保存元素成员（member），第二个节点保存元素的分值（score）

• skiplist 编码使用 zset 作为底层实现，一个 zset 结构同时 包含一个字典和一个跳跃表

• 虽然 zset 同时使用跳表和字典来保存有序集合元素，但 这两种数据结构都会通过指针来共享相同的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存

为什么同时用字典和跳表？

• 只用字典：字典可以 O(1)复杂度查找成员，但是因为字典以无序存储对象，在每次执行范围操作——比如 ZRANK、ZRANGE 命令，程序要对字典保存的所有元素排序

• 只用跳跃表：范围操作优点保留，但是查找分值会从 O(1)上升到 O(logN)

所以同时使用字典和跳表，这样优点都可以被保留

编码转换

当同时满足以下条件，对象使用 ziplist：

1. 有序集合保存的元素数量小于 128 个
2. 有序集合保存的所有元素成员长度都小于 64 字节

有序集合命令

BitMap 位图

BitMap 位图：一串连续的二进制数组，可以通过偏移量来定位元素，使用用于数据量大且二值统计的场景

• 应用场景：二值状态统计的场景，比如签到、判断用户登陆状态、连续签到用户总数等；
  

• 使用字符串类型作为底层实现类型

位图命令

HyperLogLog 超日志

Redis HyperLogLog 是用来做基数统计的算法，HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。

作用：有一个容器，判断该容器当中有多少个不一样的 Key

误差：0.8125%

• Redis 的 HyperLogLog 分为 密集存储结构 和 稀疏存储结构

• 密集存储结构就是分配一个连续的数组，存储 16384 个 6bit 组成的桶

• 如果比较多的计数值是 0，那么就会采用稀疏存储的结构：

  • 对于连续多个计数值为 0 的桶，Redis 使用的存储方式是：00xxxxxx，前缀两个 0，后面 6 位的值加 1 表示有连续多少个桶的计数值为 0，由于 6bit 最大能表示 64 个桶，所以 Redis 又设计了另一种表示方法：01xxxxxx yyyyyyyy，这样后面 14bit 就可以表示 16384 个桶了，而一个初始状态的 HyperLogLog 对象只需要用 2 个字节来存储
  • 如果连续的桶数都不是 0，那么 Redis 的表示方式为 1vvvvvxx，即为连续(xx+1)个桶的计数值都是(vvvvv+1)。例如，10011110 表示连续 3 个 8。这里使用 5bit，最大只能表示 32。因此，当某个计数值大于 32 时，Redis 会将这个 HyperLogLog 对象调整为密集存储

• 任意一个计数值从 32 变成 33，因为 VAL 指令已经无法容纳，它能表示的计数值最大为 32

• 稀疏存储占用的总字节数超过 3000 字节，这个阈值可以通过 hll_sparse_max_bytes 参数进行调整。

超日志命令

GEO 地理位置

• 用来存储地理位置信息，并对存储的信息进行操作，Redis3.2之后
• 空间存储的方案：ArcSDE、Oracle、SQL Server、mysql、redis、es、mongodb、postgreSQL

GEO命令

georadius 以给定的经纬度为中心， 返回键包含的位置元素当中， 与中心的距离不超过给定最大距离的所有位置元素。

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]

georadiusbymember 和 GEORADIUS 命令一样， 都可以找出位于指定范围内的元素， 但是 georadiusbymember 的中心点是由给定的位置元素决定的， 而不是使用经度和纬度来决定中心点。

GEORADIUSBYMEMBER key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]

对象的特性

类型检查与命令多态

• Redis中用于操作键的命令分为两种类型

  1. 可以对任意类型的键操作，比如DEL、EXPIRE、RENAME、TYPE、OBJECT

  2. 只能对特定类型的键执行

• 类型检查的实现：类型特定命令所进行的检查通过redisObject的type属性来实现

• 多态命令的实现：根据redisObject的encoding字段来决定执行哪个数据结构的API

内存回收

• C语言不具备自动内存回收的功能，所以Redis在对象系统构建了一个引用计数技术来实现内存回收机制
• 对象的生命周期可以划分为创建对象、操作对象、释放对象三个过程

对象共享

• 对象的引用计数属性除了用于内存回收，还带有对象共享的做作用
• 多个键共享一个值需要执行两步：
  1. 将数据库键的值指针指向一个现有的值对象
  2. 将被共享的值对象的引用计数增一

Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0~9999的所有整数值，当需要用上的时候，就会共享这些对象，而不是创建新对象

（类似于Java的Integer类的常量缓存池）

• 尽管共享更复杂的对象可以节约更多内存，但是收到CPU时间的限制，Redis只对包含整数值的字符串对象进行共享

对象空转时长

• redisObject结构包含的最后一个属性为lru属性，记录了该对象最后一次被程序访问的时间
• 如果服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么当内存超过了maxmemory，服务器会优先释放空转时间长的那部分键，从而回收内存