健兼
首页
关于
redis单机数据库
jianzhang

数据结构

简单动态字符串

image-20211206144025070

与C字符串的区别：

  1. redis字符串用 len 记录字符串的实际长度，所以获取字符串长度复杂度为O(1)；
  2. C字符串用空字符标记字符串结束，拼接函数也不检查目标字符串的空间是否足够，所以会导致内存溢出，redis字符串可以避免这个问题；
  3. 减少内存重分配的次数
    • 内存预分配，在分配内存时，预留一些未使用的空间
    • 惰性释放
  4. 不必受限于ASCII码，可以存储任何二进制数据

链表

节点结构，包含前驱指针、后继指针、节点数据

image-20211206160801876

链表结构，包含头节点、尾节点、节点数量、具体数据类型的处理函数指针，支持多态

image-20211206161042661

字典

哈希表

image-20211206162932497

哈希表节点，保存了键、值和指向下一个节点的指针，通过链表解决哈希冲突

image-20211206163113826

字典包含着两个哈希表、私有数据和类型特定的函数

image-20211206163736112

字典在扩容和收缩过程中，为了提高性能使用渐进式rehash：

  1. 字典持有两个哈希表，ht[0]用于正常提供服务，ht[1]用于扩容；
  2. 哈希表的负载大于负载因子时扩容，小于时收缩，都将将进行rehash，设置rehashidx为0，表明开始了rehash;
  3. 每次进行读取或写入操作时，顺带对rehashidx位置上的元素进行rehash，然后将rehashidx增加一；
  4. 当ht[0]中的元素全部迁移到ht[1]，rehashidx设置为-1，将ht[0]设置为ht[1]；

rehash期间，新增操作都在ht[1]上操作，其它操作先在ht[0]上，如果没有，就在ht[1]上操作；

跳跃表

跳跃表是在有序表的基础上，增加多层指向其他节点的指针加快访问，能达到O(logN)的复杂度。

结构

image-20211206183745938

表节点中保存着后退指针、分值、成员对象，还包括多个层，每层中保存前进指针和跨度

image-20211206183441934

跳跃表

image-20211206183609826

压缩列表

压缩列表是为了节约内存，由一定规则编码的连续内存块组成的顺序结构。

image-20211206185935819

各部分的含义：

  • zlbytes 长度4字节，记录着整个压缩列表的字节数；
  • zltail 长度4字节，记录尾节点距离压缩列表起始地址得字节数；
  • zllen 长度2字节，记录压缩列表包含的节点数；
  • entryX 节点，长度由内部结构决定；
  • zlend 长度1字节，特殊值0xFF，标记压缩列表结束；

节点结构

image-20211206200626192

  • previous_entry_length 前一个节点的字节数，pre_ptr+previous_entry_length=curent_ptr； 如果前一个节点长度小于254，就用一个字节；如果前一个节点长度大于254，第一个字节为0xFE，用后面4个字节
  • encoding 记录节点类型，01开头的，长度2字节，10开头的，长度5字节，其他都用1字节；
  • content 节点内容，长度由类型决定；

在压缩列表中间位置插入节点和删除节点会导致连锁更新previous_entry_length

对象

redis 中键和值都使用对象，对象底层使用上面的数据结构

image-20211206204541667

类型有字符串、列表、哈希、集合、有序集合

编码对应底层数据结构类型

事件

redis服务器是事件驱动的，分为文件事件和时间事件。

文件事件处理器

image-20211207134351163

文件事件处理器包括套接字、IO多路复用程序、事件派发器和处理器。IO多路复用程序监听套接字，将产生事件的套接字放在队列里，每次发送一个套接字给派发器，上一个处理完再发下一个；事件派发器根据事件类型选择不同的处理器处理。

事件分为可读事件和可写事件。

事件处理器分为连接应答处理器、命令请求处理器、命令回复处理器。

时间事件处理器

时间事件分为定时事件和周期性事件。事件的主要属性有自增序列ID、事件到达时间when、时间事件处理器timeProc。

时间事件创建时头插法放到链表中，每当时间执行器执行时，遍历链表针对已经到达的事件，调用处理函数。

image-20211207142847916

持久化

redis提供了持久化功能将内存数据保存到磁盘，避免数据丢失。

RDB持久化

RDB文件保存着键的二进制文件，通过save和bgsave命令生成RDB文件。

save会阻塞服务器，拒绝客户端的读写请求。

bgsave 在子进程中操作，服务器仍然可以处理客户端请求。

AOF持久化

服务器执行完写命令后，追加到AOF_BUF缓冲区中，每次事件循环结束时将缓存区内容刷新到操作系统的文件缓冲区，在写入磁盘。

image-20211207154448485

单机数据库

数据库

整个服务器的状态保存在RedisServer结构中；

RedisServer 中包含db数组，每个元素对应一个数据库；

每个客户端都对应着一个RedisClient结构，其中引用着正在使用的数据库；

db结构中，包含字典类型的键空间dict，而expires字典中存着每个键对应的毫秒级过期时间；

键的过期策略：

  • 定时删除，通过定时器，在键过期时立即删除
  • 惰性删除，获取键时，如果过期时就删除
  • 定期删除，每隔一段时间，扫描键，删掉过期的键

image-20211206213346465

image-20211206213431234

客户端

服务器中为每个客户端创建了RedisClient结构

image-20211207181217975

1
typedef struct redisClient{
2
  //...
3
  int fd;//套接字描述符
4
  robj *name;//名字
5
  int flags;//标志，客户端角色等
6
  sds querybuf;//输入缓冲区
7
  robj **argv;//命令数组
8
  int argc;//数组长度
9
  struct redisCommand *cmd;//命令实现函数
10
  char buf[REDIS_REPLY_CHUNK_BYTES];//输出缓冲区
11
  int bufpos;//输出缓冲区已经使用的长度
12
  list *reply;
13
  int authenticated;//是否已经经过验证
14
  //...
15
}redisClient;
  • 输入缓冲区，客户端发送的原始命令，以一定的协议格式存储在 querybuf 输入缓冲区中；
  • 命令数组，用于存放命令解析结果；
  • 命令解析后，会查找命令表，将命令实现函数放到 cmd 中；
  • 命令处理后的回复放在 buf 缓冲区中，比较长的放在 reply ；

服务器

服务器启动

  1. 服务器创建必须的数据结构；
  2. 从配置文件读取配置；
  3. 初始化数据结构；
  4. 载入持久化文件还原数据库；
  5. 执行事件循环;

命令请求过程

  1. 客户端发送命令请求，用户键入一个命令后，客户端会以协议的格式通过套接字发送到服务器；
  2. 因为客户端命令的写入，使得套接字可读，服务器调用命令处理器，将协议格式的命令保存到客户端结构的输入缓冲区 querybuf 中，进而解析到参数数组中；
  3. 调用命令执行器，在命令表中查找命令实现函数放到 cmd 中，经过预处理后，调用命令实现函数处理，将命令回复放到输出缓冲区里面，并关联命令回复处理器；
  4. 当套接字变为可写状态，就执行命令回复处理器，将命令回复发送给客户端；
  5. 客户端接受到命令回复，进行协议格式的解析及后续处理；
目录