当前位置: 首页 > news >正文

Redis 5设计与源码分析读书笔记

目录

  • 引言
    • Redis 5.0的新特性
    • Redis源码概述
    • Redis安装与调试
  • 简单动态字符串
    • 数据结构
    • 基本操作
      • 创建字符串
      • 释放字符串
      • 拼接字符串
        • 扩容策略
      • 其余API
    • 本章小结
      • 兼容C语言字符串、保证二进制安全
      • sdshdr5的特殊之处是什么
      • SDS是如何扩容的
  • 跳跃表
    • 简介
    • 跳跃表节点与结构
      • 跳跃表节点
      • 跳跃表结构
    • 基本操作
      • 创建跳跃表
        • 节点层高
        • 创建跳跃表节点
        • 头节点
        • 创建跳跃表的步骤
      • 插入节点
        • 调整跳跃表高度
        • 调整backward
      • 删除节点
        • 设置span和forward
      • 删除跳跃表
    • 跳跃表的应用
    • 小结
  • 压缩列表
    • 压缩列表的存储结构
    • 结构体
    • 连锁更新
  • 字典
    • 基本概念
      • 数组
      • Hash函数
      • Hash冲突
    • Redis字典的实现
      • Hash表
      • Hash表节点
      • 字典
    • 基本操作
      • 字典初始化
      • 字典扩容
      • 渐进式rehash
      • 内存缩容
    • 字典的遍历
      • 迭代器遍历
        • 普通迭代器
        • 安全迭代器
      • 间断遍历
        • 遍历过程中始终未遇到rehash操作
        • 遍历过程中遇到rehash操作
  • 整数集合
    • 数据存储
  • quicklist的实现
    • quicklist简介
    • 数据存储
    • 数据压缩
      • 压缩
    • 更改元素
  • Stream
    • Stream简介
      • Stream底层结构listpack
      • Stream底层结构Rax简介
      • Stream结构
    • Stream底层结构listpack的实现
      • 增删改操作
    • Stream底层结构Rax的实现
      • 遍历元素
  • 命令处理生命周期
    • 基本知识
      • 对象结构体robj
      • 客户端结构体client
      • 服务端结构体redisServer
      • 命令结构体redisCommand
      • 事件处理
        • 文件事件
        • 时间事件
    • server启动过程

引言

Redis是目前最流行的键值对(key-value)数据库,以出色的性能著称,官方提供的数据是可以支持100000以上的+QPS。Redis具有高性能的主要原因如下:

  • Redis是基于内存的存储数据库,绝大部分的命令处理只是纯粹的内存操作,内存的读写速度非常快。
  • Redis是单进程线程的服务(实际上一个正在运行的Redis Server肯定不止一个线程,但只有一个线程来处理网络请求)​,避免了不必要的上下文切换,同时不存在加锁/释放锁等同步操作。
  • Redis使用多路I/O复用模型(select、poll、epoll)​,可以高效处理大量并发连接。
  • Redis中的数据结构是专门设计的,增、删、改、查等操作相对简单。

Redis 5.0的新特性

  • 新增Streams数据类型,这是Redis 5.0最重要的改进之一。可以把Streams当作消息队列,详细内容参见后续章节。
  • 新的模块API、定时器、集群及字典。
  • RDB中持久化存储LFU和LRU的信息。
  • 将集群管理功能完全用C语言集成到redis-cli中,Redis 3.x和Redis 4.x的集群管理是通过Ruby脚本实现的。
  • 有序集合新增命令ZPOPMIN/ZPOPMAX。
  • 改进HyperLogLog的实现。
  • 新增Client Unblock和Client ID。
  • 新增LOLWUT命令。
  • Redis主从复制中的从不再称为Slave,改称Replicas。
  • Redis 5.0引入动态哈希,以平衡CPU的使用率和相应性能,可以通过配置文件进行配置。Redis 5.0默认使用动态哈希。
  • Redis核心代码进行了部分重构和优化。

Redis源码概述

Redis源代码主要存放在src文件夹中,作者没有整理这些文件,统一存放到了一个文件夹中,如图所示。其中server.c为服务端程序,redis-cli.c为客户端程序。
在这里插入图片描述
Redis源代码的核心部分主要如下。

  1. 基本的数据结构
    • 动态字符串sds.c
    • 整数集合intset.c
    • 压缩列表ziplist.c
    • 快速链表quicklist.c
    • 字典dict.c
    • Streams的底层实现结构listpack.c和rax.c
  2. Redis数据类型的底层实现
    • Redis对象object.c
    • 字符串t_string.c
    • 列表t_list.c
    • 字典t_hash.c
    • 集合及有序集合t_set.c和t_zset.c
    • 数据流t_stream.c
  3. Redis数据库的实现
    • 数据库的底层实现db.c
    • 持久化rdb.c和aof.c
  4. Redis服务端和客户端实现
    • 事件驱动ae.c和ae_epoll.c
    • 网络连接anet.c和networking.c
    • 服务端程序server.c
    • 客户端程序redis-cli.c
  5. 其他
    • 主从复制replication.c
    • 哨兵sentinel.c
    • 集群cluster.c
    • 其他数据结构,如hyperloglog.c、geo.c等
    • 其他功能,如pub/sub、Lua脚本

Redis安装与调试

通过网址http://download.redis.io/releases/可以获得各个版本的Redis源码,本书以Redis 5.0为例,下载源码包并编译安装(源码包URL为http://download.redis.io/releases/redis-5.0.0.tar.gz)​。

    $ wget http://download.redis.io/releases/redis-5.0.0.tar.gz$ tar -zxvf redis-5.0.0.tar.gz$ cd redis-5.0.0$ make$ cd src$make install

到此,我们完成了Redis 5.0的编译安装,生成的可执行文件在/usr/local/bin目录中:
redis-benchmark redis-check-aof redis-check-rdb redis-cli redis-sentinel redis-server
其中redis-benchmark是官方自带的Redis性能测试工具;当AOF文件或者RDB文件出现语法错误时,可以使用redis-check-aof或者redis-check-rdb修复;redis-cli是客户端命令行工具,可以通过命令redis-cli -h {host} -p {port}连接到指定Redis服务器;redis-sentinel是Redis哨兵启动程序;redis-server是Redis服务端启动程序。

简单动态字符串

简单动态字符串(Simple Dynamic Strings, SDS)是Redis的基本数据结构之一,用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数,且在此基础上保证了二进制安全。

数据结构

什么是二进制安全?通俗地讲,C语言中,用“\0”表示字符串的结束,如果字符串中本身就有“\0”字符,字符串就会被截断,即非二进制安全;若通过某种机制,保证读写字符串时不损害其内容,则是二进制安全。

SDS既然是字符串,那么首先需要一个字符串指针;为了方便上层的接口调用,该结构还需要记录一些统计信息,如当前数据长度和剩余容量等,例如:

    struct sds {int len; // buf中已占用字节数int free; // buf中剩余可用字节数char buf[]; // 数据空间};

SDS结构示意如图所示,在64位系统下,字段len和字段free各占4个字节,紧接着存放字符串:在这里插入图片描述
Redis 3.2之前的SDS也是这样设计的。这样设计有以下几个优点:

  • 有单独的统计变量len和free(称为头部)​。可以很方便地得到字符串长度。
  • 内容存放在柔性数组buf中,SDS对上层暴露的指针不是指向结构体SDS的指针,而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容,兼容C语言处理字符串的各种函数。
  • 由于有长度统计变量len的存在,读写字符串时不依赖“\0”终止符,保证了二进制安全。

上例中的buf[​]是一个柔性数组。柔性数组成员(flexible array member)​,也叫伸缩性数组成员,只能被放在结构体的末尾。包含柔性数组成员的结构体,通过malloc函数为柔性数组动态分配内存

之所以用柔性数组存放字符串,是因为柔性数组的地址和结构体是连续的,这样查找内存更快(因为不需要额外通过指针找到字符串的位置)​;可以很方便地通过柔性数组的首地址偏移得到结构体首地址,进而能很方便地获取其余变量。

结合两个问题,5种类型(长度1字节、2字节、4字节、8字节、小于1字节)的SDS至少要用3位来存储类型(23=8),1个字节8位,剩余的5位存储长度,可以满足长度小于32的短字符串。在Redis 5.0中,我们用如下结构来存储长度小于32的短字符串:

    struct __attribute__ ((__packed__))sdshdr5 {unsigned char flags; /* 低3位存储类型,高5位存储长度 */char buf[]; /*柔性数组,存放实际内容*/};

sdshdr5结构中,flags占1个字节,其低3位(bit)表示type,高5位(bit)表示长度,能表示的长度区间为0~31(25-1), flags后面就是字符串的内容。
在这里插入图片描述
而长度大于31的字符串,1个字节依然存不下。我们按之前的思路,将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同,sdshdr16结构如图所示。
在这里插入图片描述
其中“表头”共占用了S[2(len)+2(alloc)+1(flags)]个字节。flags的内容与sdshdr5类似,依然采用3位存储类型,但剩余5位不存储长度。在Redis 5.0中,sdshdr8、sdshdr16、sdshdr32和sdshdr64的数据结构如下:

    struct __attribute__((__packed__))sdshdr8 {uint8_t len; /* 已使用长度,用1字节存储 */uint8_t alloc; /* 总长度,用1字节存储*/unsigned char flags; /* 低3位存储类型,高5位预留 */char buf[]; /*柔性数组,存放实际内容*/};struct __attribute__((__packed__))sdshdr16 {uint16_t len; /*已使用长度,用2字节存储*/uint16_t alloc; /* 总长度,用2字节存储*/unsigned char flags; /* 低3位存储类型,高5位预留 */char buf[]; /*柔性数组,存放实际内容*/};struct __attribute__((__packed__))sdshdr32 {uint32_t len; /*已使用长度,用4字节存储*/uint32_t alloc; /* 总长度,用4字节存储*/unsigned char flags; /* 低3位存储类型,高5位预留 */char buf[]; /*柔性数组,存放实际内容*/};struct __attribute__((__packed__))sdshdr64 {uint64_t len; /*已使用长度,用8字节存储*/uint64_t alloc; /* 总长度,用8字节存储*/unsigned char flags; /* 低3位存储类型,高5位预留 */char buf[]; /*柔性数组,存放实际内容*/};

可以看到,这4种结构的成员变量类似,唯一的区别是len和alloc的类型不同。结构体中4个字段的具体含义分别如下:

  1. len:表示buf中已占用字节数。
  2. alloc:表示buf中已分配字节数,不同于free,记录的是为buf分配的总长度。
  3. flags:标识当前结构体的类型,低3位用作标识位,高5位预留。
  4. buf:柔性数组,真正存储字符串的数据空间。

结构最后的buf依然是柔性数组,通过对数组指针作“减一”操作,能方便地定位到flags。

这样做有以下两个好:

  • 节省内存,例如sdshdr32可节省3个字节(12-9)​。
  • SDS返回给上层的,不是结构体首地址,而是指向内容的buf指针。因为此时按1字节对齐,故SDS创建成功后,无论是sdshdr8、sdshdr16还是sdshdr32,都能通过(char*)sh+hdrlen得到buf指针地址(其中hdrlen是结构体长度,通过sizeof计算得到)​。修饰后,无论是sdshdr8、sdshdr16还是sdshdr32,都能通过buf[-1]找到flags,因为此时按1字节对齐。若没有packed的修饰,还需要对不同结构进行处理,实现更复杂。

基本操作

数据结构的基本操作不外乎增、删、改、查,SDS也不例外。由于Redis 3.2后的SDS涉及多种类型,修改字符串内容带来的长度变化可能会影响SDS的类型而引发扩容。

创建字符串

创建SDS的大致流程:首先计算好不同类型的头部和初始长度,然后动态分配内存。需要注意以下3点。

  1. 创建空字符串时,SDS_TYPE_5被强制转换为SDS_TYPE_8。
  2. 长度计算时有“+1”操作,是为了算上结束符“\0”​。
  3. 返回值是指向sds结构buf字段的指针。

从源码中我们可以看到,其实s就是一个字符数组的指针,即结构中的buf。这样设计的好处在于直接对上层提供了字符串内容指针,兼容了部分C函数,且通过偏移能迅速定位到SDS结构体的各处成员变量。

释放字符串

SDS提供了直接释放内存的方法——sdsfree,该方法通过对s的偏移,可定位到SDS结构体的首部,然后调用s_free释放内存。

为了优化性能(减少申请内存的开销), SDS提供了不直接释放内存,而是通过重置统计值达到清空目的的方法——sdsclear。该方法仅将SDS的len归零,此处已存在的buf并没有真正被清除,新的数据可以覆盖写,而不用重新申请内存。

所以真清除,假清除,要看安迪雷斯的心情了

拼接字符串

拼接字符串操作本身不复杂,可用sdscatsds来实现。sdscatsds是暴露给上层的方法,其最终调用的是sdscatlen。由于其中可能涉及SDS的扩容,sdscatlen中调用sdsMakeRoomFor对带拼接的字符串s容量做检查,若无须扩容则直接返回s;若需要扩容,则返回扩容好的新字符串s。函数中的len、curlen等长度值是不含结束符的,而拼接时用memcpy将两个字符串拼接在一起,指定了相关长度,故该过程保证了二进制安全。最后需要加上结束符。

扩容策略

扩容策略如下:

  • 若sds中剩余空闲长度avail大于新增内容的长度addlen,直接在柔性数组buf末尾追加即可,无须扩容
  • 若sds中剩余空闲长度avail小于或等于新增内容的长度addlen,则分情况讨论:新增后总长度len+addlen<1MB的,按新长度的2倍扩容;新增后总长度len+addlen>1MB的,按新长度加上1MB扩容。
  • 最后根据新长度重新选取存储类型,并分配空间。此处若无须更改类型,通过realloc扩大柔性数组即可;否则需要重新开辟内存,并将原字符串的buf内容移动到新位置。

其余API

SDS暴露给上层的是指向柔性数组buf的指针。读操作的复杂度多为O(1),直接读取成员变量;涉及修改的写操作,则可能会触发扩容。

本章小结

兼容C语言字符串、保证二进制安全

SDS对象中的buf是一个柔性数组,上层调用时,SDS直接返回了buf。由于buf是直接指向内容的指针,故兼容C语言函数。而当真正读取内容时,SDS会通过len来限制读取长度,而非“\0”​,保证了二进制安全。

sdshdr5的特殊之处是什么

sdshdr5只负责存储小于32字节的字符串。一般情况下,小字符串的存储更普遍,故Redis进一步压缩了sdshdr5的数据结构,将sdshdr5的类型和长度放入了同一个属性中,用flags的低3位存储类型,高5位存储长度。创建空字符串时,sdshdr5会被sdshdr8替代。

SDS是如何扩容的

SDS在涉及字符串修改处会调用sdsMakeroomFor函数进行检查,根据不同情况动态扩容,该操作对上层透明。

跳跃表

有序集合在生活中较常见,如根据成绩对学生进行排名、根据得分对游戏玩家进行排名等。对于有序集合的底层实现,我们可以使用数组、链表、平衡树等结构。数组不便于元素的插入和删除;链表的查询效率低,需要遍历所有元素;平衡树或者红黑树等结构虽然效率高但实现复杂。Redis采用了一种新型的数据结构——跳跃表。跳跃表的效率堪比红黑树,然而其实现却远比红黑树简单。

简介

通过将有序集合的部分节点分层,由最上层开始依次向后查找,如果本层的next节点大于要查找的值或next节点为NULL,则从本节点开始,降低一层继续向后查找,依次类推,如果找到则返回节点;否则返回NULL。采用该原理查找节点,在节点数量比较多时,可以跳过一些节点,查询效率大大提升,这就是跳跃表的基本思想。跳跃表的实现过程如图所示:
在这里插入图片描述
从图中我们可以看出跳跃表有如下性质:

  1. 跳跃表由很多层构成。
  2. 跳跃表有一个头(header)节点,头节点中有一个64层的结构,每层的结构包含指向本层的下个节点的指针,指向本层下个节点中间所跨越的节点个数为本层的跨度(span)​。
  3. 除头节点外,层数最多的节点的层高为跳跃表的高度(level)​,图中跳跃表的高度为3。
  4. 每层都是一个有序链表,数据递增。
  5. 除header节点外,一个元素在上层有序链表中出现,则它一定会在下层有序链表中出现。
  6. 跳跃表每层最后一个节点指向NULL,表示本层有序链表的结束。
  7. 跳跃表拥有一个tail指针,指向跳跃表最后一个节点。
  8. 最底层的有序链表包含所有节点,最底层的节点个数为跳跃表的长度(length)​(不包括头节点)​,图中跳跃表的长度为7。
  9. 每个节点包含一个后退指针,头节点和第一个节点指向NULL;其他节点指向最底层的前一个节点。

跳跃表每个节点维护了多个指向其他节点的指针,所以在跳跃表进行查找、插入、删除操作时可以跳过一些节点,快速找到操作需要的节点。归根结底,跳跃表是以牺牲空间的形式来达到快速查找的目的。跳跃表与平衡树相比,实现方式更简单,只要熟悉有序链表,就可以轻松地掌握跳跃表。

跳跃表节点与结构

跳跃表节点

下面我们来看跳跃表节点的zskiplistNode结构体:

    typedef struct zskiplistNode {sds ele;double score;struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned int span;} level[];} zskiplistNode;

该结构体包含如下属性:

  1. ele:用于存储字符串类型的数据。
  2. score:用于存储排序的分值。
  3. backward:后退指针,只能指向当前节点最底层的前一个节点,头节点和第一个节点——backward指向NULL,从后向前遍历跳跃表时使用。
  4. level:为柔性数组。每个节点的数组长度不一样,在生成跳跃表节点时,随机生成一个1~64的值,值越大出现的概率越低。level数组的每项包含以下两个元素:
    • orward:指向本层下一个节点,尾节点的forward指向NULL。
    • span:forward指向的节点与本节点之间的元素个数。span值越大,跳过的节点个数越多。

跳跃表是Redis有序集合的底层实现方式之一,所以每个节点的ele存储有序集合的成员member值,score存储成员score值。所有节点的分值是按从小到大的方式排序的,当有序集合的成员分值相同时,节点会按member的字典序进行排序。

跳跃表结构

除了跳跃表节点外,还需要一个跳跃表结构来管理节点,Redis使用zskiplist结构体,定义如下:

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

该结构体包含如下属性:

  1. header:指向跳跃表头节点。头节点是跳跃表的一个特殊节点,它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值,ele值为NULL, score值为0;也不计入跳跃表的总长度。头节点在初始化时,64个元素的forward都指向NULL, span值都为0。(就是常用的哨兵节点)
  2. tail:指向跳跃表尾节点。
  3. length:跳跃表长度,表示除头节点之外的节点总数。
  4. level:跳跃表的高度。

基本操作

创建跳跃表

节点层高

节点层高的最小值为1,最大值是ZSKIPLIST_MAXLEVEL, Redis5中节点层高的值为64。Redis通过zslRandomLevel函数随机生成一个1~64的值,作为新建节点的高度,值越大出现的概率越低。节点层高确定之后便不会再修改。

创建跳跃表节点

跳跃表的每个节点都是有序集合的一个元素,在创建跳跃表节点时,待创建节点的层高、分值、member等都已确定。对于跳跃表的每个节点,我们需要申请内存来存储。zskiplistNode结构体的最后一个元素为柔性数组,申请内存时需要指定柔性数组的大小,一个节点占用的内存大小为zskiplistNode的内存大小与level个zskiplistLevel的内存大小之和。

头节点

头节点是一个特殊的节点,不存储有序集合的member信息。头节点是跳跃表中第一个插入的节点,其level数组的每项forward都为NULL, span值都为0。

创建跳跃表的步骤

创建完头节点后,就可以创建跳跃表。创建跳跃表的步骤如下。

  1. 创建跳跃表结构体对象zsl。
  2. 将zsl的头节点指针指向新创建的头节点。
  3. 跳跃表层高初始化为1,长度初始化为0,尾节点指向NULL。

插入节点

插入节点的步骤:① 查找要插入的位置;② 调整跳跃表高度;③插入节点;④ 调整backward。

调整跳跃表高度

由上文可知,插入节点的高度是随机的,假设要插入节点的高度为3,大于跳跃表的高度2,所以我们需要调整跳跃表的高度。

调整backward

根据update的赋值过程,新插入节点的前一个节点一定是update[0]​,由于每个节点的后退指针只有一个,与此节点的层数无关,所以当插入节点不是最后一个节点时,需要更新被插入节点的backward指向update[0]​。如果新插入节点是最后一个节点,则需要更新跳跃表的尾节点为新插入节点。

删除节点

删除节点的步骤:1)查找需要更新的节点;2)设置span和forward。

设置span和forward

删除节点需要设置update数组中每个节点的span和forward。

删除跳跃表

获取到跳跃表对象之后,从头节点的第0层开始,通过forward指针逐步向后遍历,每遇到一个节点便将释放其内存。当所有节点的内存都被释放之后,释放跳跃表对象,即完成了跳跃表的删除操作。

跳跃表的应用

在Redis中,跳跃表主要应用于有序集合的底层实现(有序集合的另一种实现方式为压缩列表)​。
Redis的配置文件中关于有序集合底层实现的两个配置:

  • zset-max-ziplist-entries 128:zset采用压缩列表时,元素个数最大值。默认值为128。
  • zset-max-ziplist-value 64:zset采用压缩列表时,每个元素的字符串长度最大值。默认值为64。

值得注意的是,zset在转为跳跃表之后,即使元素被逐渐删除,也不会重新转为压缩列表。

小结

跳跃表的原理简单,其查询、插入、删除的平均复杂度都为O(logN)。跳跃表主要应用于有序集合的底层实现。

压缩列表

压缩列表ziplist本质上就是一个字节数组,是Redis为了节约内存而设计的一种线性数据结构,可以包含多个元素,每个元素可以是一个字节数组或一个整数。

Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。 当有序集合或散列表的元素个数比较少,且元素都是短字符串时,Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表(quicklist)数据结构存储,而快速链表就是双向链表与压缩列表的组合。

压缩列表的存储结构

Redis使用字节数组表示一个压缩列表,压缩列表结构示意如图所示:
在这里插入图片描述
图中各字段的含义如下:

  1. zlbytes:压缩列表的字节长度,占4个字节,因此压缩列表最多有2^32-1个字节。
  2. zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量,占4个字节。
  3. zllen:压缩列表的元素个数,占2个字节。zllen无法存储元素个数超过65535(216-1)的压缩列表,必须遍历整个压缩列表才能获取到元素个数。
  4. entryX:压缩列表存储的元素,可以是字节数组或者整数,长度不限。entry的编码结构将在后面详细介绍。
  5. zlend:压缩列表的结尾,占1个字节,恒为0xFF。

压缩列表元素的编码结构:在这里插入图片描述
previous_entry_length字段表示前一个元素的字节长度,占1个或者5个字节,当前一个元素的长度小于254字节时,用1个字节表示;当前一个元素的长度大于或等于254字节时,用5个字节来表示。而此时previous_entry_length字段的第1个字节是固定的0xFE,后面4个字节才真正表示前一个元素的长度。假设已知当前元素的首地址为p,那么p-previous_entry_length就是前一个元素的首地址,从而实现压缩列表从尾到头的遍历。

encoding字段表示当前元素的编码,即content字段存储的数据类型(整数或者字节数组)​,数据内容存储在content字段。为了节约内存,encoding字段同样长度可变。

可以看出,根据encoding字段第1个字节的前2位,可以判断content字段存储的是整数或者字节数组(及其最大长度)​。当content存储的是字节数组时,后续字节标识字节数组的实际长度;当content存储的是整数时,可根据第3、第4位判断整数的具体类型。而当encoding字段标识当前元素存储的是0~12的立即数时,数据直接存储在encoding字段的最后4位,此时没有content字段

结构体

我们发现对于压缩列表的任意元素,获取前一个元素的长度、判断存储的数据类型、获取数据内容都需要经过复杂的解码运算。解码后的结果应该被缓存起来,为此定义了结构体zlentry,用于表示解码后的压缩列表元素。

    typedef struct zlentry {unsigned int prevrawlensize;unsigned int prevrawlen;unsigned int lensize;unsigned int len;unsigned char encoding;unsigned int headersize;unsigned char *p;} zlentry;

回顾压缩列表元素的编码结构,可变因素实际上不止3个:previous_entry_length字段的长度(prevrawlensize)​、previous_entry_length字段存储的内容(prevrawlen)​、encoding字段的长度(lensize)​、encoding字段的内容(len表示元素数据内容的长度,encoding表示数据类型)和当前元素首地址(p)​;而headersize则表示当前元素的首部长度,即previous_entry_length字段长度与encoding字段长度之和。

连锁更新

压缩列表连锁更新示意如图所示,删除压缩列表zl1位置P1的元素entryX,或者在压缩列表zl2位置P2插入元素entryY时,会出现什么情况呢?
在这里插入图片描述
压缩列表zl1中,由于元素entryX+1长度的增大,元素entryX+2的previous_entry_length字段同样需要改变。依此类推,由于删除了元素entryX,之后的所有元素(entryX+1、entryX+2等)的长度都必须扩展,而每次扩展都将重新分配内存,导致效率很低。压缩列表zl2中,插入元素entryY时同样会出现这种情况,称为连锁更新。从以上分析可以看出,连锁更新会导致多次重新分配内存及数据复制,效率很低。但是出现这种情况的概率是很低的,因此对于删除元素和插入元素操作,Redis并没有为了避免连锁更新而采取措施。

字典

基本概念

字典又称散列表,是用来存储键值(key-value)对的一种数据结构,在很多高级语言中都有实现,如PHP的数组。但是C语言没有这种数据结构,Redis是K-V型数据库,整个数据库是用字典来存储的,对Redis数据库进行任何增、删、改、查操作,实际就是对字典中的数据进行增、删、改、查操作。根据Redis数据库的特点,便可知字典有如下特征:

  • 可以存储海量数据,键值对是映射关系,可以根据键以O(1)的时间复杂度取出或插入关联值。
  • 键值对中键的类型可以是字符串、整型、浮点型等,且键是唯一的。例如:执行set test "hello world"命令,此时的键test类型为字符串,如test这个键存在数据库中,则为修改操作,否则为插入操作。
  • 键值对中值的类型可为String、Hash、List、Set、SortedSet。

数组

当需要对数组a中元素进行操作时,C语言需通过下标找到其对应的内存地址,然后才能对这块内存进行对应的操作。例如,读取a[9]的值, C语言实际上会先转换为*(a+9)的形式,a[9]与*(a+9))这两种形式是等价的,我们对等式两边再取地址,便可得出&a[9]==a+9,也就是说,要得到a[9]的地址,可以通过对数组a的首地址偏移9个元素就行。由此也可以知道,数组根据下标取值时,是通过头指针和偏移量来实现。

通过前文数组介绍可知,​“下标”的含义是数组中第几个元素的意思,只能为整数。根据第2个特征中键的描述:​“键值对中键的类型可以为字符串、整型、浮点型等”​,显然不能直接当成下标使用,此时,需要对键做一些特殊处理,处理过程我们称为Hash。

Hash函数

在应用上,通常使用现成的开源Hash算法,例如Redis自带客户端就是使用“times 33”散列函数来计算字符串的Hash值,Redis服务端的Hash函数使用的是siphash算法,主要功能与客户端Hash函数类似,其优点是针对有规律的键计算出来的Hash值也具有强随机分布性,但算法较为复杂。

那过大的Hash值与较小的数组下标怎么关联呢?最简单的办法是,用Hash值与数组容量取余,会得到一个永远小于数组容量大小的值,此时的值也就恰好可以当作数组下标来使用,我们把取余之后的值称为键在该字典中的索引值,即“索引值==数组下标值”​,拿到“键”的索引值后,我们就知道数组中哪个元素是用来存储键值对中的“值”了。但此方法并不是完美的,还会出现一个问题,Hash冲突。

Hash冲突

为了解决Hash冲突,所以数组中的元素除了应把键值对中的“值”存储外,还应该存储“键”信息和一个next指针,next指针可以把冲突的键值对串成单链表,​“键”信息用于判断是否为当前要查找的键。

Redis字典的实现

Redis字典实现依赖的数据结构主要包含了三部分:字典、Hash表、Hash表节点。字典中嵌入了两个Hash表,Hash表中的table字段存放着Hash表节点,Hash表节点对应存储的是键值对。

Hash表

Hash表,与5.1节设计的字典结构体类似,在Redis源码中取名为Hash表,其数据结构如下:

typedef struct dictht {dictEntry **table;            /*指针数组,用于存储键值对*/unsigned long size;            /*table数组的大小*/unsigned long sizemask;        /*掩码 = size -1 */unsigned long used;            /*table数组已存元素个数,包含next单链表的数据*/
} dictht;

Hash表的结构体整体占用32字节,其中table字段是数组,作用是存储键值对,该数组中的元素指向的是dictEntry的结构体,每个dictEntry里面存有键值对。size表示table数组的总大小。used字段记录着table数组已存键值对个数。

sizemask字段用来计算键的索引值,sizemask的值恒等于size-1。我们知道,索引值是键Hash值与数组总容量取余之后的值,而Redis为提高性能对这个计算进行了优化,具体计算步骤如下:

  • 人为设定Hash表的数组容量初始值为4,随着键值对存储量的增加,就需对Hash表扩容,新扩容的容量大小设定为当前容量大小的一倍,也就是说,Hash表的容量大小只能为4,8,16,32…。而sizemask掩码的值就只能为3,7,15,31…,对应的二进制为11,111,1111,11111…,因此掩码值的二进制肯定是每一位都为1。
  • 索引值=Hash值&掩码值,对应Redis源码为:idx = hash & d->ht[table].sizemask,其计算结果等同Hash值与Hash表容量取余,而计算机的位运算要比取余运算快很多。

Hash表节点

Hash表中的元素是用dictEntry结构体来封装的,主要作用是存储键值对,具体结构体如下:

    typedef struct dictEntry {void *key;                      /*存储键*/union {void *val;                  /*db.dict中的val*/uint64_t u64;int64_t s64;                /*db.expires中存储过期时间*/double d;} v;                            /*值,是个联合体*/struct dictEntry *next;        /*当Hash冲突时,指向冲突的元素,形成单链表*/} dictEntry;

Hash表中元素结构体和我们前面自定义的元素结构体类似,整体占用24字节,key字段存储的是键值对中的键。v字段是个联合体,存储的是键值对中的值,在不同场景下使用不同字段。 例如,用字典存储整个Redis数据库所有的键值对时,用的是*val字段,可以指向不同类型的值;再比如,字典被用作记录键的过期时间时,用的是s64字段存储;当出现了Hash冲突时,next字段用来指向冲突的元素,通过头插法,形成单链表。

字典

Redis字典实现除了包含前面介绍的两个结构体Hash表及Hash表节点外,还在最外面层封装了一个叫字典的数据结构,其主要作用是对散列表再进行一层封装,当字典需要进行一些特殊操作时要用到里面的辅助字段。

    typedef struct dict {dictType *type;           /*该字典对应的特定操作函数*/void *privdata;           /*该字典依赖的数据*/dictht ht[2];              /*Hash表,键值对存储在此*/long rehashidx;            /*rehash标识。默认值为-1,代表没进行rehash操作;不为-1时,代表正进行rehash操作,存储的值表示Hash表ht[0]的rehash操作进行到了哪个索引值*/unsigned long iterators;   /* 当前运行的迭代器数*/} dict;

Redis字典这个数据结构,除了主数据库的K-V数据存储外,还有很多其他地方会用到。例如,Redis的哨兵模式,就用字典存储管理所有的Master节点及Slave节点;再如,数据库中键值对的值为Hash类型时,存储这个Hash类型的值也是用的字典。在不同的应用中,字典中的键值对形态都可能不同,而dictType结构体,则是为了实现各种形态的字典而抽象出来的一组操作函数。
在这里插入图片描述

基本操作

字典初始化

在redis-server启动中,整个数据库会先初始化一个空的字典用于存储整个数据库的键值对。初始化一个空字典,调用的是dict.h文件中的dictCreate函数。

字典扩容

扩容主要流程为:① 申请一块新内存,初次申请时默认容量大小为4个dictEntry;非初次申请时,申请内存的大小则为当前Hash表容量的一倍。② 把新申请的内存地址赋值给ht[1]​,并把字典的rehashidx标识由-1改为0,表示之后需要进行rehash操作。扩容后,字典容量及掩码值会发生改变,同一个键与掩码经位运算后得到的索引值就会发生改变,从而导致根据键查找不到值的情况。解决这个问题的方法是,新扩容的内存放到一个全新的Hash表中(ht[1]​)​,并给字典打上在进行rehash操作中的标识(即rehashidx! =-1)​。此后,新添加的键值对都往新的Hash表中存储;而修改、删除、查找操作需要在ht[0]​、ht[1]中进行检查,然后再决定去对哪个Hash表操作。除此之外,还需要把老Hash表(ht[0]​)中的数据重新计算索引值后全部迁移插入到新的Hash表(ht[1])中,此迁移过程称作rehash。

渐进式rehash

rehash除了扩容时会触发,缩容时也会触发。Redis整个rehash的实现,主要分为如下几步完成:

  • 给Hash表ht[1]申请足够的空间;扩容时空间大小为当前容量2,即d->ht[0]. used2;当使用量不到总空间10%时,则进行缩容。缩容时空间大小则为能恰好包含d->ht[0].used个节点的2^N次方幂整数,并把字典中字段rehashidx标识为0。
  • 进行rehash操作调用的是dictRehash函数,重新计算ht[0]中每个键的Hash值与索引值(重新计算就叫rehash)​,依次添加到新的Hash表ht[1]​,并把老Hash表中该键值对删除。把字典中字段rehashidx字段修改为Hash表ht[0]中正在进行rehash操作节点的索引值。
  • rehash操作后,清空ht[0]​,然后对调一下ht[1]与ht[0]的值,并把字典中rehashidx字段标识为-1。

Redis优化的思想很巧妙,利用分而治之的思想了进行rehash操作,大致的步骤如下:
执行插入、删除、查找、修改等操作前,都先判断当前字典rehash操作是否在进行中,进行中则调用dictRehashStep函数进行rehash操作(每次只对1个节点进行rehash操作,共执行1次)​。除这些操作之外,当服务空闲时,如果当前字典也需要进行rehsh操作,则会调用incrementallyRehash函数进行批量rehash操作(每次对100个节点进行rehash操作,共执行1毫秒)​。在经历N次rehash操作后,整个ht[0]的数据都会迁移到ht[1]中,这样做的好处就把是本应集中处理的时间分散到了上百万、千万、亿次操作中,所以其耗时可忽略不计。

内存缩容

当字典中数据经过一系列操作后,使用量不到总空间<10%时,就会进行缩容操作,将Redis数据库占用内存保持在合理的范围内,不浪费内存。整个缩容的步骤大致为:判断当前的容量是否达到最低阈值,即used/size<10%,达到了则调用dictResize函数进行缩容,缩容后的函数容量实质为used的最小2N整数。缩容操作和扩容操作实质差不多,最终调用的都是dictExpand函数,之后的操作与扩容一致,不再重复讲解。

字典的遍历

遍历Redis整个数据库主要有两种方式:全遍历(例如keys命令)​、间断遍历(hscan命令)​,这两种方式将在下面进行详细讲解。

迭代器遍历

Redis源码中迭代器实现的基本数据结构如下:

    typedef struct dictIterator {dict *d;                //迭代的字典int index;              //当前迭代到Hash表中哪个索引值int table, safe;        //table用于表示当前正在迭代的Hash表,即ht[0]与ht[1], safe用于表示当前创建的是否为安全迭代器dictEntry *entry, *nextEntry; //当前节点,下一个节点long long fingerprint; //字典的指纹,当字典未发生改变时,该值不变,发生改变时则值也随着改变} dictIterator;

fingerprint字段是一个64位的整数,表示在给定时间内字典的状态。在这里称其为字典的指纹,因为该字段的值为字典(dict结构体)中所有字段值组合在一起生成的Hash值,所以当字典中数据发生任何变化时,其值都会不同。

普通迭代器

普通迭代器迭代字典中数据时,会对迭代器中fingerprint字段的值作严格的校验,来保证迭代过程中字典结构不发生任何变化,确保读取出的数据不出现重复。

当Redis执行部分命令时会使用普通迭代器迭代字典数据,例如sort命令。sort命令主要作用是对给定列表、集合、有序集合的元素进行排序,如果给定的是有序集合,其成员名存储用的是字典,分值存储用的是跳跃表,则执行sort命令读取数据的时候会用到迭代器来遍历整个字典。

安全迭代器

安全迭代器和普通迭代器迭代数据原理类似,也是通过循环调用dictNext函数依次遍历字典中Hash表的节点。安全迭代器确保读取数据的准确性,不是通过限制字典的部分操作来实现的,而是通过限制rehash的进行来确保数据的准确性,因此迭代过程中可以对字典进行增删改查等操作。

原理上很简单,如果当前字典有安全迭代器运行,则不进行渐进式rehash操作,rehash操作暂停,字典中数据就不会被重复遍历,由此确保了读取数据的准确性。当Redis执行部分命令时会使用安全迭代器迭代字典数据,例如keys命令。keys命令主要作用是通过模式匹配,返回给定模式的所有key列表,遇到过期的键则会进行删除操作。Redis数据键值对都存储在字典中,因此keys命令会通过安全迭代器来遍历整个字典。

间断遍历

在Redis在2.8.0版本后新增了scan操作,也就是“间断遍历”​。而dictScan是“间断遍历”中的一种实现,主要在迭代字典中数据时使用,例如hscan命令迭代整个数据库中的key,以及zscan命令迭代有序集合所有成员与值时,都是通过dictScan函数来实现的字典遍历。dictScan遍历字典过程中是可以进行rehash操作的,通过算法来保证所有的数据能被遍历到。

dictScan函数间断遍历字典过程中会遇到如下3种情况。

  1. 从迭代开始到结束,散列表没有进行rehash操作。
  2. 从迭代开始到结束,散列表进行了扩容或缩容操作,且恰好为两次迭代间隔期间完成了rehash操作。
  3. 从迭代开始到结束,某次或某几次迭代时散列表正在进行rehash操作。
遍历过程中始终未遇到rehash操作

Redis为了做到不漏数据且尽量不重复数据,统一采用了一种叫作reverse binary iteration的方法来进行间断数据迭代。整个迭代过程强依赖游标值v变量,根据v找到当前需读取的Hash表元素,然后遍历该元素单链表上所有的键值对,依次执行fn函数指针执行的函数,对键值对进行读取操作。为了兼容迭代间隔期间可能发生的缩容与扩容操作,每次迭代时都会对v变量(游标值)进行修改,以确保迭代出的数据无遗漏。

这里还有一种特殊的情况没说明,比如多次间断遍历的时候该字典缩容了两次,则可能造成遍历的数据出现重复,但现实生产环境中,一般Redis短时间内频繁缩容了两次的概率不大,因此影响也有限。

遍历过程中遇到rehash操作

从迭代开始到结束,某次或某几次迭代时散列表正在进行rehash操作,rehash操作中会同时并存两个Hash表:一张为扩容或缩容后的表ht[1]​,一张为老表ht[0], ht[0]的数据通过渐进式rehash会逐步迁移到ht[1]中,最终完成整个迁移过程。因为大小两表并存,所以需要从ht[0]和ht[1]中都取出数据,整个遍历过程为:先找到两个散列表中更小的表,先对小的Hash表遍历,然后对大的Hash表遍历。

这套算法能满足这样的特点,主要是巧妙地利用了扩容及缩容正好为整数倍增长或减少的原理,根据这个特征,很容易就能推导出同一个节点的数据扩容/缩容后在新的Hash表中的分布位置,从而避免了重复遍历或漏遍历。

整数集合

整数集合(intset)是一个有序的、存储整型数据的结构。我们知道Redis是一个内存数据库,所以必须考虑如何能够高效地利用内存。当Redis集合类型的元素都是整数并且都处在64位有符号整数范围之内时,使用该结构体存储。

数据存储

整数集合在Redis中可以保存int16_t、int32_t、int64_t类型的整型数据,并且可以保证集合中不会出现重复数据。每个整数集合使用一个intset类型的数据结构表示:
在这里插入图片描述

    typedef struct intset {uint32_t encoding; //编码类型uint32_t length; //元素个数int8_t contents[]; //柔性数组,根据encoding字段决定几个字节表示一个元素} intset

因为encoding字段实际取值为2、4、8,所以encoding字段可以直接比较大小。当待插入值的encoding字段大于待插入intset的encoding时,说明需要进行扩容操作,并且也能表明该待插入值在该intset中肯定不存在。

quicklist的实现

quicklist是Redis底层最重要的数据结构之一,它是Redis对外提供的6种基本数据结构中List的底层实现,在Redis 3.2版本中引入。在引入quicklist之前,Redis采用压缩链表(ziplist)以及双向链表(adlist)作为List的底层实现。

quicklist简介

quicklist是Redis 3.2中新引入的数据结构,能够在时间效率和空间效率间实现较好的折中。Redis中对quciklist的注释为A doubly linked list of ziplists。顾名思义,quicklist是一个双向链表,链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。

数据存储

如前文所述,quicklist是一个由ziplist充当节点的双向链表。quicklist的存储结构如图所示:在这里插入图片描述
其中head、tail指向quicklist的首尾节点;count为quicklist中元素总数;len为quicklist Node(节点)个数;fill用来指明每个quicklistNode中ziplist长度,当fill为正数时,表明每个ziplist最多含有的数据项数。

考虑quicklistNode节点个数较多时,我们经常访问的是两端的数据,为了进一步节省空间,Redis允许对中间的quicklistNode节点进行压缩,通过修改参数list-compress-depth进行配置,即设置compress参数,该项的具体含义是两端各有compress个节点不压缩,当compress为1时,quicklistNode个数为3时,其结构图如图所示:
在这里插入图片描述
quicklistNode是quicklist中的一个节点,其结构如下:

    typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *zl;unsigned int sz;                /* ziplist size in bytes */unsigned int count : 16;      /* count of items in ziplist */unsigned int encoding : 2;    /* RAW==1 or LZF==2 */unsigned int container : 2;   /* NONE==1 or ZIPLIST==2 */unsigned int recompress : 1; /* was this node previous compressed? */unsigned int attempted_compress : 1; /* node can't compress; too small */unsigned int extra : 10;      /* more bits to steal for future usage */} quicklistNode;

其中,prev、next指向该节点的前后节点;zl指向该节点对应的ziplist结构;sz代表整个ziplist结构的大小;encoding代表采用的编码方式:1代表是原生的,2代表使用LZF进行压缩;container为quicklistNode节点zl指向的容器类型:1代表none,2代表使用ziplist存储数据;recompress代表这个节点之前是否是压缩节点,若是,则在使用压缩节点前先进行解压缩,使用后需要重新压缩,此外为1,代表是压缩节点;attempted_compress测试时使用;extra为预留。

当我们使用quicklistNode中ziplist中的一个节点时,Redis提供了quicklistEntry结构以便于使用,该结构如下:

    typedef struct quicklistEntry {const quicklist *quicklist;quicklistNode *node;unsigned char *zi;unsigned char *value;long long longval;unsigned int sz;int offset;} quicklistEntry;

其中,quicklist指向当前元素所在的quicklist; node指向当前元素所在的quicklistNode结构;zi指向当前元素所在的ziplist; value指向该节点的字符串内容;longval为该节点的整型值;sz代表该节点的大小,与value配合使用;offset表明该节点相对于整个ziplist的偏移量,即该节点是ziplist第多少个entry。

数据压缩

quicklist每个节点的实际数据存储结构为ziplist,这种结构的主要优势在于节省存储空间。为了进一步降低ziplist所占用的空间,Redis允许对ziplist进一步压缩,Redis采用的压缩算法是LZF,压缩过后的数据可以分成多个片段,每个片段有2部分:一部分是解释字段,另一部分是存放具体的数据字段。解释字段可以占用1~3个字节,数据字段可能不存在。具体而言,LZF压缩的数据格式有3种,即解释字段有3种:

  • 字面型,解释字段占用1个字节,数据字段长度由解释字段后5位决定。
  • 简短重复型,解释字段占用2个字节,没有数据字段,数据内容与前面数据内容重复,重复长度小于8
  • 批量重复型,解释字段占3个字节,没有数据字段,数据内容与前面内容重复。

压缩

LZF数据压缩的基本思想是:数据与前面重复的,记录重复位置以及重复长度,否则直接记录原始数据内容。

更改元素

quicklist更改元素是基于index,主要的处理函数为quicklistReplaceAtIndex。其基本思路是先删除原有元素,之后插入新的元素。quicklist不适合直接改变原有元素,主要由于其内部是ziplist结构,ziplist在内存中是连续存储的,当改变其中一个元素时,可能会影响后续元素。故而,quicklist采用先删除后插入的方案。

Stream

消息队列是分布式系统中不可缺少的组件之一,主要有异步处理、应用解耦、限流削峰的功能。目前应用较为广泛的消息队列有RabbitMQ、RocketMQ、Kafka等。Redis在最新的5.0.0版本中也加入了消息队列的功能,这就是Stream。

Stream简介

Redis中的消息,通过如下指令可以创建一个消息流并向其中加入一条消息:xadd mystream1 * name hb age 20。其中,mystream1为Stream的名称;*代表由Redis自行生成消息ID; name、age为该消息的field; hb、20则为对应的field的值。每个消息都由以下两部分组成:

  • 每个消息有唯一的消息ID,消息ID严格递增。
  • 消息内容由多个field-value对组成。

生产者负责向消息队列中生产消息,消费者消费某个消息流。消费者可以归属某个消费组,也可以不归属任何消费组。当消费者不归属于任何消费组时,该消费者可以消费消息队列中的任何消息。消费组是Stream的一个重要概念,具有以下特点:

  • 每个消费组通过组名称唯一标识,每个消费组都可以消费该消息队列的全部消息,多个消费组之间相互独立。
  • 每个消费组可以有多个消费者,消费者通过名称唯一标识,消费者之间的关系是竞争关系,也就是说一个消息只能由该组的一个成员消费。
  • 组内成员消费消息后需要确认,每个消息组都有一个待确认消息队列(pending entry list, pel)​,用以维护该消费组已经消费但没有确认的消息。
  • 消费组中的每个成员也有一个待确认消息队列,维护着该消费者已经消费尚未确认的消息。

Stream底层结构listpack

Redis源码对于listpack的解释为A lists of strings serialization format,一个字符串列表的序列化格式,也就是将一个字符串列表进行序列化存储。

listpack由4部分组成:Total Bytes、Num Elem、Entry以及End,下面介绍各部分的具体含义:

  1. Total Bytes为整个listpack的空间大小,占用4个字节,每个listpack最多占用4294967295Bytes。
  2. Num Elem为listpack中的元素个数,即Entry的个数,占用2个字节,值得注意的是,这并不意味着listpack最多只能存放65535个Entry,当Entry个数大于等于65535时,Num Elem被设置为65535,此时如果需要获取元素个数,需要遍历整个listpack。
  3. End为listpack结束标志,占用1个字节,内容为0xFF。
  4. Entry为每个具体的元素。

Entry为listpack中的具体元素,其内容可以为字符串或者整型,每个Entry由3部分组成,每部分的具体含义如下:Encode为该元素的编码方式,占用1个字节,之后是内容字段content,二者紧密相连。backlen记录了这个Entry的长度(Encode+content)​,注意并不包括backlen自身的长度,占用的字节数小于等于5。backlen所占用的每个字节的第一个bit用于标识;0代表结束,1代表尚未结束,每个字节只有7 bit有效。值得一提的是,backlen主要用于从后向前遍历,当我们需要找到当前元素的上一个元素时,我们可以从后向前依次查找每个字节,找到上一个Entry的backlen字段的结束标识,进而可以计算出上一个元素的长度。

Stream底层结构Rax简介

前缀树是字符串查找时,经常使用的一种数据结构,能够在一个字符串集合中快速查找到某个字符串。由于树中每个节点只存储字符串中的一个字符,故而有时会造成空间的浪费。Rax的出现就是为了解决这一问题。Redis对于Rax的解释为A radix tree implement,基数树的一种实现。Rax中不仅可以存储字符串,同时还可以为这个字符串设置一个值,也就是key-value。

Rax树通过节点压缩节省空间,含有两个key(foobar, footer)的Rax树结构图如图所示:
在这里插入图片描述

Stream结构

Redis Stream的实现依赖于Rax结构以及listpack结构。从下图中可以看出,每个消息流都包含一个Rax结构。以消息ID为key、listpack结构为value存储在Rax结构中。每个消息的具体信息存储在这个listpack中。
在这里插入图片描述

  • 每个listpack都有一个master entry,该结构中存储了创建这个listpack时待插入消息的所有field,这主要是考虑同一个消息流,消息内容通常具有相似性,如果后续消息的field与master entry内容相同,则不需要再存储其field。
  • 每个listpack中可能存储多条消息。

Stream底层结构listpack的实现

listpack是Stream用于存储消息内容的结构,该结构查询效率低,并且只适合于末尾增删。考虑到消息流中,通常只需要向其末尾增加消息,故而可以采用该结构。

增删改操作

listpack提供了2种添加元素的方式:一种是在任意位置插入元素,一种是在末尾插入元素。在末尾插入元素的底层实现通过调用任意位置插入元素进行,具体实现为lpInsert函数。listpack的删除操作被转换为用空元素替换的操作。listpack的替换操作(即改操作)的底层实现也是通过lpInsrt函数实现的。

Stream底层结构Rax的实现

Stream的消息内容存储在listpack中,但是如果将所有消息都存储在一个listpack中,则会存在效率问题。例如,查询某个消息时,需要遍历整个listpack;插入消息时,需要重新申请一块很大的空间。为了解决这些问题,Redis Stream通过Rax组织这些listpack。

遍历元素

为了能够遍历rax中所有的key, Redis提供了迭代器操作。Redis中实现的迭代器为双向迭代器,可以向前,也可以向后,顺序是按照key的字典序排列的。

命令处理生命周期

Redis服务器是典型的事件驱动程序,因此事件处理显得尤为重要,而Redis将事件分为两大类:文件事件与时间事件。文件事件即socket的读写事件,时间事件用于处理一些需要周期性执行的定时任务。

基本知识

对象结构体robj

Redis是一个key-value型数据库,key只能是字符串,value可以是字符串、列表、集合、有序集合和散列表,这5种数据类型用结构体robj表示,我们称之为Redis对象。结构体robj的type字段表示对象类型。针对某一种类型的对象,Redis在不同情况下可能采用不同的数据结构存储,结构体robj的encoding字段表示当前对象底层存储采用的数据结构,即对象的编码,总共定义了11种encoding常量。
在这里插入图片描述
对象的整个生命周期中,编码不是一成不变的,比如集合对象。当集合中所有元素都可以用整数表示时,底层数据结构采用整数集合;当执行sadd命令向集合中添加元素时,Redis总会校验待添加元素是否可以解析为整数,如果解析失败,则会将集合存储结构转换为字典。

对象在不同情况下可能采用不同的数据结构存储,那对象可能同时采用多种数据结构存储吗?根据上面的表格,有序集合可能采用压缩列表、跳跃表和字典存储。使用字典存储时,根据成员查找分值的时间复杂度为O(1),而对于zrange与zrank等命令,需要排序才能实现,时间复杂度至少为O(NlogN);使用跳跃表存储时,zrange与zrank等命令的时间复杂度为O(logN),而根据成员查找分值的时间复杂度同样是O(logN)。字典与跳跃表各有优势,因此Redis会同时采用字典与跳跃表存储有序集合。这里有读者可能会有疑问,同时采用两种数据结构存储不浪费空间吗?数据都是通过指针引用的,两种存储方式只需要额外存储一些指针即可,空间消耗是可以接受的。

结构体robj的定义:

    #define LRU_BITS 24typedef struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS;  //缓存淘汰使用int refcount;           //引用计数void *ptr;} robj;
  1. ptr是void*类型的指针,指向实际存储的某一种数据结构,但是当robj存储的数据可以用long类型表示时,数据直接存储在ptr字段。可以看出,为了创建一个字符串对象,必须分配两次内存,robj与sds存储空间;两次内存分配效率低下,且数据分离存储降低了计算机高速缓存的效率。因此提出OBJ_ENCODING_EMBSTR编码的字符串,当字符串内容比较短时,只分配一次内存,robj与sds连续存储,以此提升内存分配效率与数据访问效率。
  2. refcount存储当前对象的引用次数,用于实现对象的共享。共享对象时,refcount加1;删除对象时,refcount减1,当refcount值为0时释放对象空间。
  3. lru字段占24比特,用于实现缓存淘汰策略,可以在配置文件中使用maxmemory-policy配置已用内存达到最大内存限制时的缓存淘汰策略。lru根据用户配置的缓存淘汰策略存储不同数据,常用的策略就是LRU与LFU。LRU的核心思想是,如果数据最近被访问过,那么将来被访问的几率也更高,此时lru字段存储的是对象访问时间;LFU的核心思想是,如果数据过去被访问多次,那么将来被访问的频率也更高,此时lru字段存储的是上次访问时间与访问次数。LRU_CLOCK函数用于获取当前时间,注意此时间不是实时获取的,Redis以1秒为周期执行系统调用获取精确时间,缓存在全局变量server.lruclock, LRU_CLOCK函数获取的只是该缓存时间。可以发现lru的低8比特存储的是对象的访问次数,高16比特存储的是对象的上次访问时间,以分钟为单位;需要特别注意的是函数LFUDecrAndReturn,其返回计数值counter,对象的访问次数在此值上累加。为什么不直接累加呢?因为假设每次只是简单的对访问次数累加,那么越老的数据一般情况下访问次数越大,即使该对象可能很长时间已经没有访问,相反新对象的访问次数通常会比较小,显然这是不公平的。因此访问次数应该有一个随时间衰减的过程,函数LFUDecrAndReturn实现了此衰减功能。

客户端结构体client

Redis是典型的客户端服务器结构,客户端通过socket与服务端建立网络连接并发送命令请求,服务端处理命令请求并回复。Redis使用结构体client存储客户端连接的所有信息,包括但不限于客户端的名称、客户端连接的套接字描述符、客户端当前选择的数据库ID、客户端的输入缓冲区与输出缓冲区等。结构体client字段较多,此处只介绍命令处理主流程所需的关键字段。

    typedef struct client {uint64_t id;int fd;redisDb *db;robj *name;time_t lastinteractionsds querybuf;int argc;robj **argv;struct redisCommand *cmd;list *reply;unsigned long long reply_bytes;size_t sentlen;char buf[PROTO_REPLY_CHUNK_BYTES];int bufpos;} client;
  • id为客户端唯一ID,通过全局变量server.next_client_id实现。
  • fd为客户端socket的文件描述符。
  • name:客户端名称,可以使用命令CLIENT SETNAME设置。
  • lastinteraction:客户端上次与服务器交互的时间,以此实现客户端的超时处理。
  • querybuf:输入缓冲区,recv函数接收的客户端命令请求会暂时缓存在此缓冲区。
  • argc:输入缓冲区的命令请求是按照Redis协议格式编码字符串,需要解析出命令请求的所有参数,参数个数存储在argc字段,参数内容被解析为robj对象,存储在argv数组。
  • cmd:待执行的客户端命令;解析命令请求后,会根据命令名称查找该命令对应的命令对象,存储在客户端cmd字段,可以看到其类型为struct redisCommand
  • reply:输出链表,存储待返回给客户端的命令回复数据。
  • db为客户端使用select命令选择的数据库对象。redisDb结构体定义如下:
    typedef struct redisDb {int id;long long avg_ttl;dict *dict;dict *expires;dict *blocking_keys;dict *ready_keys;dict *watched_keys;} redisDb;
  • id为数据库序号,默认情况下Redis有16个数据库,id序号为0~15。
  • dict存储数据库所有键值对。
  • expires存储键的过期时间。
  • avg_ttl存储数据库对象的平均TTL,用于统计。

Redis支持事务,命令multi用于开启事务,命令exec用于执行事务;但是开启事务到执行事务期间,如何保证关心的数据不会被修改呢?Redis采用乐观锁实现。开启事务的同时可以使用watch key命令监控关心的数据键,而watched_keys字典存储的就是被watch命令监控的所有数据键,其中key-value分别为数据键与客户端对象。当Redis服务器接收到写命令时,会从字典watched_keys中查找该数据键,如果找到说明有客户端正在监控此数据键,于是标记客户端对象为dirty;待Redis服务器收到客户端exec命令时,如果客户端带有dirty标记,则会拒绝执行事务。

服务端结构体redisServer

结构体redisServer存储Redis服务器的所有信息,包括但不限于数据库、配置参数、命令表、监听端口与地址、客户端列表、若干统计信息、RDB与AOF持久化相关信息、主从复制相关信息、集群相关信息等。结构体redisServer的字段非常多,这里只对部分字段做简要说明,以便读者对服务端有个粗略了解,至于其他字段在讲解各知识点时会进行说明。结构体redisServer定义如下:

    struct redisServer {char *configfile;int dbnum;redisDb *db;dict *commands;aeEventLoop *el;int port;char *bindaddr[CONFIG_BINDADDR_MAX];int bindaddr_count;int ipfd[CONFIG_BINDADDR_MAX];int ipfd_count;list *clients;int maxidletime;}
  • configfile:配置文件绝对路径。
  • dbnum:数据库的数目,可通过参数databases配置,默认16。
  • db:数据库数组,数组的每个元素都是redisDb类型。
  • commands:命令字典,Redis支持的所有命令都存储在这个字典中,key为命令名称,vaue为struct redisCommand对象。
  • el:Redis是典型的事件驱动程序,el代表Redis的事件循环,类型为aeEventLoop。
  • port:服务器监听端口号,可通过参数port配置,默认端口号6379。
  • bindaddr:绑定的所有IP地址,可以通过参数bind配置多个,例如bind 192.168.1.10010.0.0.1, bindaddr_count为用户配置的IP地址数目;CONFIG_BINDADDR_MAX常量为16,即最多绑定16个IP地址;Redis默认会绑定到当前机器所有可用的Ip地址。
  • ipfd:针对bindaddr字段的所有IP地址创建的socket文件描述符,ipfd_count为创建的socket文件描述符数目。
  • clients:当前连接到Redis服务器的所有客户端。
  • maxidletime:最大空闲时间,可通过参数timeout配置,结合client对象的lastinteraction字段,当客户端没有与服务器交互的时间超过maxidletime时,会认为客户端超时并释放该客户端连接。

命令结构体redisCommand

Redis支持的所有命令初始都存储在全局变量redisCommandTable,类型为redisCommand,定义及初始化如下:

    struct redisCommand redisCommandTable[] = {{"get", getCommand,2, "rF",0, NULL,1,1,1,0,0},{"set", setCommand, -3, "wm",0, NULL,1,1,1,0,0},…………}

结构体redisCommand相对简单,主要定义了命令的名称、命令处理函数以及命令标志等:

    struct redisCommand {char *name;redisCommandProc *proc;int arity;char *sflags;int flags;long long microseconds, calls;};

各字段含义如下:

  • name:命令名称。
  • proc:命令处理函数。
  • arity:命令参数数目,用于校验命令请求格式是否正确;当arity小于0时,表示命令参数数目大于等于arity;当arity大于0时,表示命令参数数目必须为arity;注意命令请求中,命令的名称本身也是一个参数,如get命令的参数数目为2,命令请求格式为get key。
  • sflags:命令标志,例如标识命令时读命令还是写命令,注意到sflags的类型为字符串,此处只是为了良好的可读性。
  • flags:命令的二进制标志,服务器启动时解析sflags字段生成。
  • calls:从服务器启动至今命令执行的次数,用于统计。
  • microseconds:从服务器启动至今命令总的执行时间,microseconds/calls即可计算出该命令的平均处理时间,用于统计。

当服务器接收到一条命令请求时,需要从命令表中查找命令,而redisCommandTable命令表是一个数组,意味着查询命令的时间复杂度为O(N),效率低下。因此Redis在服务器初始化时,会将redisCommandTable转换为一个字典存储在redisServer对象的commands字段,key为命令名称,value为命令redisCommand对象。对于经常使用的命令,Redis甚至会在服务器初始化的时候将命令缓存在redisServer对象,这样使用的时候就不需要每次都从commands字典中查找了。

事件处理

Redis服务器是典型的事件驱动程序,而事件又分为文件事件(socket的可读可写事件)与时间事件(定时任务)两大类。无论是文件事件还是时间事件都封装在结构体aeEventLoop中:

    typedef struct aeEventLoop {int stop;aeFileEvent *events;aeFiredEvent *fired;aeTimeEvent *timeEventHead;void *apidataaeBeforeSleepProc *beforesleep;aeBeforeSleepProc *aftersleep;} aeEventLoop;

stop标识事件循环是否结束;events为文件事件数组,存储已经注册的文件事件;fired存储被触发的文件事件;Redis有多个定时任务,因此理论上应该有多个时间事件,多个时间事件形成链表,timeEventHead即为时间事件链表头节点;Redis服务器需要阻塞等待文件事件的发生,进程阻塞之前会调用beforesleep函数,进程因为某种原因被唤醒之后会调用aftersleep函数。Redis底层可以使用4种I/O多路复用模型(kqueue、epoll等), apidata是对这4种模型的进一步封装

文件事件

Redis客户端通过TCP socket与服务端交互,文件事件指的就是socket的可读可写事件。socket读写操作有阻塞与非阻塞之分。采用阻塞模式时,一个进程只能处理一条网络连接的读写事件,为了同时处理多条网络连接,通常会采用多线程或者多进程,效率低下;非阻塞模式下,可以使用目前比较成熟的I/O多路复用模型,如select/epoll/kqueue等,视不同操作系统而定。

epoll是Linux内核为处理大量并发网络连接而提出的解决方案,能显著提升系统CPU利用率。epoll使用非常简单,总共只有3个API:epoll_create函数创建一个epoll专用的文件描述符,用于后续epoll相关API调用;epoll_ctl函数向epoll注册、修改或删除需要监控的事件;epoll_wait函数会阻塞进程,直到监控的若干网络连接有事件发生 int epoll_create(int size)。输入参数size通知内核程序期望注册的网络连接数目,内核以此判断初始分配空间大小;注意在Linux 2.6.8版本以后,内核动态分配空间,此参数会被忽略。返回参数为epoll专用的文件描述符,不再使用时应该及时关闭此文件描述符。
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event):
函数执行成功时返回0,否则返回-1,错误码设置在变量errno,输入参数含义如下:

  • epfd:函数epoll_create返回的epoll文件描述符。
  • op:需要进行的操作,EPOLL_CTL_ADD表示注册事件,EPOLL_CTL_MOD表示修改网络连接事件,EPOLL_CTL_DEL表示删除事件。
  • fd:网络连接的socket文件描述符。
  • event:需要监控的事件,结构体epoll_event定义如下:
    struct epoll_event {__uint32_t events;epoll_data_t data;};typedef union epoll_data {void *ptr;int fd;__uint32_t u32;__uint64_t u64;} epoll_data_t;

其中events表示需要监控的事件类型,比较常用的是EPOLLIN文件描述符可读事件,EPOLLOUT文件描述符可写事件;data保存与文件描述符关联的数据。

int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout):
函数执行成功时返回0,否则返回-1,错误码设置在变量errno;输入参数含义如下:

  • epfd:函数epoll_create返回的epoll文件描述符;
  • epoll_event:作为输出参数使用,用于回传已触发的事件数组;
  • maxevents:每次能处理的最大事件数目;
  • timeout:epoll_wait函数阻塞超时时间,如果超过timeout时间还没有事件发生,函数不再阻塞直接返回;当timeout等于0时函数立即返回,timeout等于-1时函数会一直阻塞直到有事件发生。

Redis并没有直接使用epoll提供的API,而是同时支持4种I/O多路复用模型,并将这些模型的API进一步统一封装,由文件ae_evport.c、ae_epoll.c、ae_kqueue.c和ae_select.c实现。而Redis在编译阶段,会检查操作系统支持的I/O多路复用模型,并按照一定规则决定使用哪种模型。

时间事件

前面介绍了Redis文件事件,已经知道事件循环执行函数aeProcessEvents的主要逻辑:① 查找最早会发生的时间事件,计算超时时间;② 阻塞等待文件事件的产生;③ 处理文件事件;④处理时间事件。时间事件的执行函数为processTimeEvents。

Redis服务器内部有很多定时任务需要执行,比如定时清除超时客户端连接,定时删除过期键等,定时任务被封装为时间事件aeTimeEvent对象,多个时间事件形成链表,存储在aeEventLoop结构体的timeEventHead字段,它指向链表首节点。时间事件aeTimeEvent定义如下:

    typedef struct aeTimeEvent {long long id;long when_sec;long when_ms;aeTimeProc *timeProc;aeEventFinalizerProc *finalizerProc;void *clientData;struct aeTimeEvent *next;} aeTimeEvent;

各字段含义如下。

  • id:时间事件唯一ID,通过字段eventLoop->timeEventNextId实现;
  • when_sec与when_ms:时间事件触发的秒数与毫秒数;
  • timeProc:函数指针,指向时间事件处理函数;
  • finalizerProc:函数指针,删除时间事件节点之前会调用此函数;
  • clientData:指向对应的客户端对象;
  • next:指向下一个时间事件节点。

时间事件执行函数processTimeEvents的处理逻辑比较简单,只是遍历时间事件链表,判断当前时间事件是否已经到期,如果到期则执行时间事件处理函数timeProc。

需要特别注意一点,serverCron函数的执行时间不能过长,否则会导致服务器不能及时响应客户端的命令请求。下面以过期键删除为例,分析Redis是如何保证serverCron函数的执行时间。过期键删除由函数activeExpireCycle实现,由函数databasesCron调用。

server启动过程


http://www.mrgr.cn/news/82712.html

相关文章:

  • vsFTPd服务部署和用户模式简介
  • 【Linux】揭开套接字编程的神秘面纱(上)
  • JavaScript语言的字符串处理
  • 软件安全测试的核心内容与方法详解
  • 前端基础函数算法整理应用(sort+reduce+date+双重for循环)
  • doris:N-Gram 索引
  • 33.时间函数相关 C#例子
  • 下载excel
  • node.js之---集群(Cluster)模块
  • 单片机-串转并-74HC595芯片
  • Java虚拟机(Java Virtual Machine,JVM)
  • 学习Video.js
  • K8s高可用集群之Kubernetes集群管理平台、命令补全工具、资源监控工具部署及常用命令
  • 第四、五章补充:线代本质合集(B站:小崔说数)
  • [SAP ABAP] SMARTFORMS表单开发
  • Nginx (40分钟学会,快速入门)
  • 【操作系统不挂科】操作系统期末考试卷<2>(单选题&简答题&计算与分析题&程序分析题&应用题)
  • 01:C语言的本质
  • 深入探索 Kubernetes:从基础概念到实战运维
  • LLM - 使用 LLaMA-Factory 部署大模型 HTTP 多模态服务 教程 (4)
  • 多模态论文笔记——CogVLM和CogVLM2
  • 毕业项目推荐:基于yolov8/yolov5的行人检测识别系统(python+卷积神经网络)
  • 【Unity3D】UGUI Canvas画布渲染流程
  • TP8 前后端跨域访问请求API接口解决办法
  • 基于海思soc的智能产品开发(camera sensor的两种接口)
  • 【Vim Masterclass 笔记05】第 4 章:Vim 的帮助系统与同步练习(L14+L15+L16)