Redis-数据结构

tobing
理论学习

发布于：Jun 20, 2021
次浏览

Redis 是非常常见的中间件，本文将介绍 Redis 的数据结构。

Redis-数据结构与对象

一、常用数据结构

概述

Redis 底层的数据结构一共有 6 种，分别是：简单动态字符串（SDS）、双向链表、压缩列表、哈希表、跳表和整数数组。

Redis 的基础数据类型主要有 5 种，分别是：String、List、Hash、Sorted Set和Set。

其中，5 种基础数据类型通过底层 6 种数据结构实现，它们之间的对应关系如下图所示：

image-20210521220651124

  • 上图中，String的实现方式只有一种为SDS，而其他类型都由两种底层数据结构实现。

接下来我们分别学习这 6 种底层数据结构。

简单动态字符串

简单动态字符串，Simple Dynamic String，简称 SDS。顾名思义，SDS 类似于 ArrayList 是可以动态增长的。

SDS的结构如下：

image-20210524223843654

  • free ：记录buf数组中已使用的字节数量，等于 SDS 保存字符串的长度
  • len ：记录buf数组中未使用的字节数量
  • buf 数组：字节数组，用于保存字符串

SDS 遵循 C 语言规范，保存空字符串的一个字节不会计算到 SDS 的 len 属性中。

由于 Redis 对 String 进行了一层封装，因此 SDS 与原生的 C 语言中的字符串有所区别：

C字符串 SDS
获取字符串长度复杂度为O(n) 获取字符串长度复杂度为O(1)
API是不安全的，可能造成缓冲区溢出 API是安全的，不会造成缓冲区溢出
修改字符串长度N次必须重新分配N次内存 修改字符串长度N次最多需要重新分配N次内存
只能保存文本数据 可以保存文本或者二进制数据
可以使用所有<string.h>库中的函数 可以使用部分<string.h>库中的函数
  • 此处一个较为重大的区别就是 SDS 是二进制安全的，因此 SDS 还被用来实现位数组。

Redis 中，SDS的使用场景较为广泛：

  • 作为字符串对象的底层实现
  • 作为二进制位数组的底层实现
  • 作为AOF缓冲区和客户端状态的输入缓冲区

双向链表

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

双向链表的结构如下：

image-20210525211851539

双向链表的特征如下：

  • 双端：链表节点带prev和next指针，可以获取节点的前置和后置节点。
  • 无环：表头的prev指针和表为的next都为null，对链表的访问以null为结尾。
  • 带表头和表尾元素：通过list结构的head和list指针获取表头节点和表尾元素，时间复杂度为O(1)。
  • 带链表长度计数器：通过维护len来记录链表持有的节点。

同样地，双向链表的使用场景也很多：

  • 作为List的底层实现
  • 发布于订阅、慢查询、监视器等功能也用到链表
  • Redis服务器本身还使用链表来保存多个客户端的状态信息
  • Redis使用链表来构建客户端输出缓冲区

字典

字典，又称为符号表、关联数组或映射，是一种用来保存键值对的抽象数据结构。

Redis使用的C语言没有内置这种数据结构，因此Redis构建了自己的字典实现，结构如下：

image-20210527221333060

  • 【dict】：Redis中的字典通过dict结构管理
    • type和privdata是为储存不同类型键值对而存在
    • type是一个dictType指针，dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数；
    • privdata属性保存了需要特定传给那些类型特定函数的可选参数；
    • ht是一个长度为2的dicth数组，字典只使用ht[0]哈希表，ht[1]哈希表只在对ht[0]哈希表进行rehash时使用；
    • rehashindx属性记录rehash进度，如果当前没有进行rehash，值为-1。
  • 【dictht】：Redis字典中使用的哈希表dictht实现
    • table是一个数组，数组每个元素执行一个dictEntry结构的指针，每个dictEntry结构保存着一个键值对；
    • size属性记录了哈希表的大小，即table数组的大小；
    • used属性记录了哈希表目前已有的节点数量；
    • sizemask属性的值总是等于size-1，这个属性结合哈希值一起决定一个键应该被放到table数组的哪个索引上。
  • 【dictEntry】：哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对
    • key属性保存键值对中的键；
    • v属性保存键值对中的值，值可以一个指针，或一个uint64整数，有或者是一个int64_t整数;
    • next属性是执行另一个哈希表节点的指针，Redis通过链地址法来解决哈希冲突。

提到字典，不得不提到哈希冲突、rehash。

Redis 中字典采用链地址法连解决哈希冲突问题， 即每个哈希节点都有一个next指针，哈希索引相同的多个节点可以通过next构成一个单向链表，依次来解决哈希冲突。

随着操作不断执行，哈希表保存的键值对会逐渐增加或减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围，哈希表保存的键值数量太多或太少时，需要对哈希表的大小进行相应的扩展或收缩。

哈希表的扩展或收缩需要通过rehash（重新散列）来完成，主要步骤如下：

  1. 为字典ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量。
    • 当执行的是扩展操作，ht[1]大小为第一个大于等于ht[0].used*2的2的n次方幂
    • 当执行的是收缩操作，ht[1]大小为第一个大于等于ht[0].used的2的n次方幂（始终保证哈希表大小为2的n次幂）
  2. 将保持在ht[0]中的所有键值对rehash到ht[1]上面：rehash是指重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表指定的位置上。
  3. 当ht[0]包含的所有键值对都迁移到ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建空白哈希表，为下次rehash准备。

考虑到服务器性能的影响，在收缩或扩展哈希表时，将ht[0]的数据复制到ht[1]这个动作并不是一次性完成的，是分多次，渐进式完成的，详细步骤如下：

  1. 为ht[1]分配空间，字典同时持有ht[0]和ht[1]两个哈希表；
  2. 在字典中维持一个索引计数器变量rehashidx，将它设置为0，表示rehash工作正式开始
  3. 在rehash进行期间，每次对字典执行添加、删除、查找或更新操作时，程序除了完成指定操作，还会顺带将会ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当一次rehash工作完成，rehashidx属性值增一
  4. 随着字典操作不断执行，最终某个时间点上，ht[0]的所有键值都会被rehash到ht[1]，这是程序将rehashidx设置为-1，表示rehash操作已经完成。

上面过程体现了分而治之、均摊的思想，可以用于避免集中式rehash带来的庞大计算量。

在进行渐进式rehash过程中，字典会同时使用ht[0]和ht[1]两个哈希表，因此在rehash期间，字典的删除、查找、更新等操作会在两个哈希表上进行。如果要在字典中查找一个键时，会先到ht[0]中查找，没有则会到ht[1]中查找。

另外，渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]中，ht[0]不再进行任何添加按操作，这一措施保证ht[0]包含的键值对数量只减不增，而随着rehash操作的进行而最终变为空表。

注意：rehash的发生除了与负载因子有关，还需要考虑当前是否执行bgsave或bgrewrite命令。或者的目的都是为了降低服务器阻塞的可能。

跳跃表

跳跃表是一种有序的数据结构，通过维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。大部分情况下，跳跃表的效率和平衡树媲美，而且跳表实现比平衡树简单。

Redis使用跳跃表作为Sorted Set 的底层实现之一，如果Sorted Set的元素较多，或者其中元素是较长的字符串时，Redis会使用跳跃表作为Sorted Set的底层实现。

跳跃表的结构如下：

image-20210528092838914

  • 【zskiplist】：保存跳跃表节点的相关信息
    • header：指向跳跃表的表头节点，可以以O(1)时间复杂度访问头节点
    • tail：指向跳跃表的表尾节点，可以以O(1)时间复杂度访问尾节点
    • level：记录当前跳跃表层数最大的节点层数（表头层数不计算在内）
    • length：记录跳跃表的长度，跳跃表目前包含节点的数量（表头节点不计）
  • 【zskiplistNode】：用于表示跳跃表节点
    • level：层，节点中用L1、L2、L3等字样标记节点的各个层，L1表示第一层，L2表示第二层，以此类推。每个层都带有两个属性：前进指针和跨度。
      • 前进指针用于访问位于表尾方向的其他节点
      • 跨度记录了前进指针所指向节点和当前节点的距离，两个节点之间跨度很大，它们相距越远，指向null的所有前进指针的跨度为0
      • 跨度是用来计算排位（rank）：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计，得到的结果就是目标节点在跳跃表的排位。
      • 当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行
    • backward：后退指针，节点中用BW字样标记节点后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾先表头遍历时使用。
    • score：分值，各个节点中的1.0、2.0是节点所保存的分值。跳跃表中节点按各自保存的分值从小到大排列。
    • obj：成员对象，各个节点的o1、o2是节点所保存的成员对象。

需要注意的是，表头节点和其他节点构造不一样，表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性不会被用到，因此在图中省略了这些部分。

整数数组

当一个集合只包含整数元素并且这个集合的元素数量不多时，Redis 会使用整数数组作为 Set 的底层实现。

整数数组的结构如下：

image-20210528130231842

  • contents数组是集合的底层实现，整数集合的每个元素都是contents数组的每个数组项，各个项在数组中按值的大小从小到大有序排列，且数组中不会出现重复项。
  • length记录了整数集合包含的元素数量，即contents数组的长度。
  • 虽然contents声明为int8_t，但实际上储存取决于encoding的值
    • encoding=INTSET_ENC_INT16，contents为int16_t类型的数组；（-32768，32767）
    • encoding=INTSET_ENC_INT32，contents为int32_t类型的数组；（-2147483648，2147483647）
    • encoding=INTSET_ENC_INT64，contents为int64_t类型的数组；（- 9223372036854775808，9223372036854775807）

每当一个新元素添加当整数数组的时候，并且新元素的类型比这整数数组的所有元素的了类型都要长，整数数组需要先升级，然后才能将元素添加到整数数组中。

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

每次向整数集合中添加新元素都可能引起升级，而每次升级都需要对底层数据已有的所有元素进行类型转换，所以先整数集合添加新元素的时间复杂度为O(N)。

需要注意的是，升级之后新元素的摆放位置：

因为引发升级的新元素的长度总是要比整数集合现有的所有数据要大，因此这个新元素的值要么“大于”所有现有元素，要么就“小于”所有现有元素。

  • 新元素“小于”所有现有元素的情况下，新元素会被放置到底层数组的最开头位置【负数】
  • 新元素“大于”所有现有元素的情况下，新元素会被放置到底层数组的最末尾位置【正数】

通过升级策略，整数集合具有两个好处，一是提高整数集合的灵活性，另一个是尽可能地节省内存。

  • 灵活性：可以随意将int16_t、int32_t或者int64_t类型的数据添加到集合中，而不用担心出现类型错误
  • 节约内存：如果不考虑内存占用，可以直接用int64_t保存所有的数据，但是这不符合Redis的节约风格，因此采用上面方式

需要注意：整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级的状态。

压缩表

压缩列表是列表键和哈希键的底层实现之一。

当一个List只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

当一个Hash只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。

压缩列表是Redis为了节约内存开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多节点（entry），每个节点可以保存一个字节数组或一个整数值。压缩表的结构如下：

image-20210528165256106

属性 类型 长度 用途
zlbytes uint32_t 4字节 记录ziplist占用的内存字节，在对ziplist进行内存重新分配或减少zlend的位置时使用
zltail uint32_t 4字节 记录ziplist尾节点距离压缩列表的起始地址有多少字节，通过偏移量无需变量整个ziplist可以确定表尾节点地址
zllen uint16_t 2字节 记录ziplist节点数，当属性小于65535，这个属性值就是压缩列表包含节点的数量，等于65536时需要遍历计算
entryN 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定
zlend uint8_t 1字节 特殊值0xFF，用来标记压缩列表末端

对于压缩表的每个节点，结构如下：

image-20210528170328489

  • pervious_entry_length：字节为单位，记录压缩列表中前一个字节长度。这个属性长度可以是1字节或5字节
    • 如果长度小于254，pervious_entry_length长度为1字节，前一个节点长度就保存在这一个字节
    • 如果长度大于等于254，pervious_entry_length长度为5字节，其中第一个字节设置为0XFF，之后四个字节保存前一节点长度
    • 通过pervious_entry_length属性记录前一个节点长度，程序可以通过指针运算，根据当前节点的起始地址计算出前一个节点的起始地址
    • 压缩列表从表尾到表头的变量使用找一个原理实现，只有拥有执行某个节点的起始地址的指针，通过这个指针和pervious_entry_length属性即可往前一个节点回溯，最终到达表头节点。
  • encoding：记录了节点的content属性保存数据的类型以及长度
    • 一字节、两字节或五字节长，值的最高位为00、01或10的是字节数组编码：这种编码表示节点的content属性保存字节数组，数组长度由编码的最高两位去除之后的其他为的记录
    • 一字节长，值的最高位以11开头的整数编码：这种编码表示节点的content属性保存整数值，整数值的类型和长度由编码除去除最高两位之后的其他位记录
  • content：负责保存节点的值，节点的值可以是一个字节数组或者整数，值的类型和长度由节点encoding属性决定

在使用压缩表的时候，需要注意连锁更新问题：假如在一个列表中，有多个连续的、长度介于250字节到253字节的元素e1到eN。

此时由于长度介于250字节到253字节之间，因此这些元素的pervious_entry_length的属性只需要占用一个字节。

但是这时，在e1前面插入了一个新的元素，其大小大于等于254。这时e1的pervious_entry_length将会占用5个字节，此时e1的长度将要大于等于254，导致在扩展的过程中，e1的长度也需要额外增加。以此类推，由于e1之后的大量元素都会存在同样的情况，所以程序不断对压缩列表执行空间重分配，直到eN为止。

Redis将这种特殊情况产生的连续多次空间控制操作称之为“连锁更新”（casacde update）。

但实际上，出现这种的概率很低，因此压缩表的push平均时间复杂度为O(N)。

二、对象

概述

前面主要介绍了 Redis 中底层的数据结构。Redis 并未直接使用这些底层的数据结构来实现键值对数据库，而是基于这些键值对创建一个对象系统，包含了 String 对象、List 对象、Hash 对象、Set 对象和 Sorted Set 对象。这五种对象中至少使用了一种数据结构作为其底层实现。

通过上述提到的五种对象，可以给 Redis 带来诸多好处：

  • 可以在执行命令前根据对象类型判断一个对象是否可以执行给定的命令。（如 Hash 对象才允许HSET命令）

  • 可以针对不同场景为对象设置不同的数据结构实现，从而优化不同场景下的效率。（如除了 String 对象，其他对象都有两种底层实现）

  • 可以使用基于引用计数算法判断某个对象是否可以进行内存回收。

  • 对象可以保存额外的信息，如访问时间等，利用这些信息可以进行一些的操作。（如利用访问时间计算数据库键的空转时长，在服务器启用了maxmemory的时候，空转时长较大的键可能会优先被服务器删除。）

为了表示不同对象的不同底层实现，Redis 中使用 redisObject 结构保存表示两者的关系：

image-20210530114714443

String 对象

字符串编码可以是int、raw和embstr。

*当一个字符串对象保存的是整数值，并且这个整数值可以用long来表示，此时字符串对象会将整数值保存在字符串结构的ptr属性（将void转换为long），并将字符串对象的编码设置为int。**

image-20210530120044561

当一个字符串对象保存的是一个字符串值，并且这个字符串值长度大于32字节，那么整个字符 串将使用SDS来保存字符串值，并将对象编码设置为raw。

image-20210530120159431

当一个字符串对象保存的是一个字符串值，并且字符串值长度小于等于32字节，那么字符串对象将使用embstr编码方式保存这个字符串。

image-20210530120253880

embstr是专门用于保存短字符串的一种优化编码方式，和raw一样，都是用redisObject结果和sdshdr结构来表示字符串对象。但raw编码会调用两次内存分配函数分别创建redisObject和sdshdr，而embstr通过调用一次内存分配函数分配一块连续内存。

embstr编码保存短字符串有以下好处：

  • embstr内存分配raw的两次变为一次
  • 释放embstr编码的字符串对象只需要调用一次内存释放，而raw需要两次
  • embstr字符串对象保存在连续内存，比raw编码的字符串对象更好利用缓存

除此之外，字符串可保存long double类型浮点数。这时，程序会先将浮点数转成字符串值，再保存转换得到的字符串。

int和embstr类型的字符串可能会在某些情况下被转换为raw类型。如在int类型的字符串执行了APPEND命令之后会被转换为raw。

同时Redis没有为embstr（嵌入式字符串，嵌入到redisObject）编写任何修改程序，因此embstr实际上是只读的。因此对embstr执行修改会先转换为raw。

List 对象

列表的编码可以是ziplist或者linkedlist。

ziplist编码方式使用压缩列表来作为底层实现，每个压缩列表节点保存一个列表元素。

image-20210530122109584

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

image-20210530122227676

注意，linkedlist编码的列表对象在底层的双端链表中包含了多个字符串对象。字符串对象是Redis五种类型中唯一一种会被其他四种类型对象嵌套的对象。

当列表满足一下两个条件时，列表对象使用ziplist编码：

  • 列表对象保存的所有字符串长度小于64；
  • 列表对象保存的元素数量小于512个；
  • 除此之外列表对象需要使用linkedlist编码。

Hash 对象

哈希对象的编码可以使用ziplist或者hashtable。

ziplist编码方式的哈希对象底层使用压缩列表作为实现。

每当有新的键值对要加入到哈希对象时，程序会分别将键和值的压缩列表节点推入到压缩列表表尾，因此，保存同一键值对的连个节点总是紧挨着，键前值后。同时可以知道，先添加到的哈希对象键值对在前面，后添加的在后面。

image-20210530123617211

image-20210530123633305

hashtable编码方式的哈希对象底层使用字典作为实现。

哈希对象的每个键值对都使用一个字典键值对来保存。

image-20210530123848268

当满足以下条件，哈希对象使用ziplist编码：

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  • 哈希对象保存的键值对数量小于512个
  • 其他情况使用hashtable编码

Set 对象

集合对象的编码可以是inset或hashtable。

intset编码的集合对象使用整数集合作为底层实现，集合对象包含私有元素都被保存在整数集合中。

image-20210530124454845

hashtable编码的集合对象使用字典作为底层实现，字典中每一个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字符串的值全部被设置为NULL。

image-20210530124523993

集合元素满足以下条件是，对象使用intset

  • 集合对象保存的所有元素都是整数值
  • 集合对象保存的元素个数不超过512
  • 不满足以上条件使用hashtable

Sorted Set 对象

有序集合对象可以是ziplist或skiplist。

ziplist编码的有序集合对象使用压缩列表作为底层实现。

此时每个集合元素使用紧挨着列表节点保存，一个保存元素成员（member），另一个保存元素的分值（score）。

image-20210530125029479

image-20210530125047702

压缩列表中集合元素按分值从小到大排序，分值较小的处于表头。

skiplist编码的有序集合对象使用zset结构作为底层实现。

1
2
3
4
typedef struct zset {
    zskiplist *zsl;
    dict *dict;
}

zset结构中的zsl跳跃表按分值大小从小到大保存所有集合元素，每个跳跃表节点都保存了一个集合元素（object保存元素，score保存元素分值）。ZRANGE和ZRANK通过跳跃表API实现。

除此之外，zset的dict字典为有序集合创建一个从成员到分值的银蛇，字典的每个键值对都保存一个集合元素（键为元素，值为分数）。ZSCORE通过字典实现O(1)复杂度查找指定成员分值。

有序集合每个元素的成员都是一个字符串对象，每个元素的分值都是一个double类型浮点数。

虽然zset结构同时使用跳跃表和字典来保存有序集合，但是两种数据结构通过共享指针来共享相同的元素和分值。

总的来说，zset结构同时使用跳跃表和字典是兼顾了两种数据结构的特性：字典无序但取值很快，skiplist需要遍历查找取值，但是使用与范围查找。

image-20210530130015295

image-20210530130033435

有序集合满足一下条件，ziplist编码：

  • 有序集合保存的所有元素成员的长度都小于64字节
  • 有序集合保存的元素小于128
  • 不满足以上条件使用skiplist编码

三、总结

五大对象

image-20210620224118167

四、参考文献

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://tobing.top/2021/06/20/Redis-Datastruct/

更新于：Jun 20, 2021

中间件 - Redis

评论