redis设计与实现

第一章 数据结构与对象：

Redis数据库里面每个键值对都是有 对象组成的，其中：
1、 数据库键总是一个字符串对象
2、 而数据库键的值 可以是 字符串对象String、列表对象List、 哈希对象Hash、集合对象set、有序集合对象sorted set object。 每一种数据结构，都有它适用的应用场景。

Redis没有直接使用C语言传统字符串表示（以空字符结尾的字符数组），而是自己构建一种名为“简单动态字符串”（simple dynamic string SDS）,用作Redis的默认字符串表示。

SDS定义

2、SDS与C字符串的区别

C语言使用长度为N+1的字符数组来表示长度为N的字符串，并且字符数组的最后一个元素总是空字符 ‘\0’

image.png

1、常数复杂度获取字符串长度

在redis，程序只要访问SDS的len属性、就能立即知道SDS的长度。通过使用SDS而不是字符串、Redis将获取字符串长度所需的复杂度从O(N)降低到了O(1)。这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。

redis SDS定义

2、 杜绝缓冲区溢出

image.png

减少修改字符串时带来的内存重新分配次数

image.png

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

image.png image.png image.png image.png

第三章 redis链表

作为一种常用的数据结构、链表内置在很多高级的编程语言里面，因为Redis使用的C语言并没有内置这种数据结构，所以Redis构建了自己的链表实现。
链表在Redis中的应用非常广泛、比如列表键的底层实现之一就是链表。当一个列表键包含很多数量的元素，Redis就会用链表作为列表建为底层实现。
链表结构：

typedef struct listNode{
  struct listNode *prev;
  struct listNode *next;
  void *value;
}listNode;

链表结构 image.png image.png

哈希表

image.png
image.png image.png image.png image.png image.png image.png image.png

5、跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过对每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。 当我们在做 大量数据排序显示的功能，比如“拍卖行、排行榜”的时候，需要维护一个多变切有序的数据结构。而跳跃表就很符合这种场景。

1634442454(1).png
Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合中包含的元素数量比较多。又或者有序集合中元素的成员是比较长的字符串，Redis就会使用跳跃表作为有序集合键的底层实现。 跳跃表的实现

6、整数集合的实现

整数集合（intset）是集合键的底层实现之一 、当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。(因为底层用的是数组存储)
集合中不会出现重复的元素且有序。

image.png image.png image.png image.png

压缩列表

image.png image.png image.png image.png image.png image.png
image.png

八、对象

Redis使用对象来表示数据库中的键和值、每当我们在redis数据库中创建一个键值对，我们至少会创建两个对象、一个对象为键值对的键，另一个对象为键值对的值。每个对象都由一个redisObject结构表示、该结构中和保存数据有关的三个属性分别是 type、encoding属性、prt属性.

typedef struct redisObject{
  unsigned type:4;
  unsigned encoding: 4;
  void *ptr;
}

下面为redis的五种对象类型：

image.png

每种类型的对象都至少使用两种不同的编码、对象的ptr指针指向对象的底层实现数据结构、而这些数据结构由对象的encoding属性决定。

image.png image.png

通过encoding属性来设定对象所使用的编码、而不是特定类型的对象关联一种固定的编码，极大地提升了redis的灵活性和效率，因为Redis可以根据不同使用场景来为一个对象设置不同的编码、从而优化对象在某一场景的效率。
1、因为压缩列表比双端列表更节约内存、并且在元素较少的情况下、在内存中连续方式保存的压缩列表比起双端链表可以更快的载入缓存。
2、 随着列表对象包含的元素越来越多、使用压缩列表来保存元素的优势逐渐消失、对象就会将底层从压缩列表转向功能更强、更适合保存大量元素的双端链表上面。

image.png image.png image.png image.png image.png image.png image.png 22.png

8.5 集合对象

集合对象的编码可以是intset 或者 hashtable
intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。

image.png

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

image.png

8.6 有序集合对象

有序集合编码可以是 ziplist 或者skiplist
ziplist 编码的压缩列表对象使用压缩列表作为底层实现，每个元素使用两个紧挨在一起的压缩列表节点来保存，每个节点保存的元素的成员，第二个元素保存元素的分值（score）。
压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素放置在靠近表头的方向，而分值较大的元素放置在靠近表尾的方向

image.png 1.png image.png image.png

第10章 RDB持久化

Redis是内存数据库、它将自己的数据库状态存储在内存里面，所以如果不想办法将存储在内存中的数据保存在磁盘里，一旦服务器进程退出，服务器中的数据库状态也会消失不见。
为了解决这个问题，Redis提供了RDB持久化功能，这个功能可以将Redis在内存中数据库状态保存在磁盘里面，避免数据意外丢失。
RDB文件是一个经过压缩的二进制文件。

image.png

RDB文件的创建与载入

有两个Redis命令可以用于生成RDB文件，一个是SAVE,另一个是BGSAVE。
SAVE命令会阻塞Redis服务器进程，直到RDB文件创建完毕为止，在服务器进程阻塞期间，服务器不能进行任何命令请求。
和SAVE命令不同，BGSAVE命令会派生出一个子进程，然后由子进程负责创建RDB文件，服务器进程继续处理命令请求。
Redis没有载入RDB文件的命令，RDB文件的载入工作是在服务器启动时自动执行的。
另外，因为AOF文件的更新频率通常比RDB文件的更新频率高，所以：
如果服务器开启了AOF持久化功能，那么服务器器会优先使用AOF文件来还原数据库状态。
只有在AOF持久化功能处于关闭状态，服务器才会使用RDB文件来还原数据库状态。

image.png

RDB文件自动间隔性保存

用户可以通过save选项设置多个保存条件，但只要其中任意-一个条件被满足，服务器用户可以
通过save选项设置多个保存条件，但只要其中任意-一个条件被满足，服务器就会执行BGSAVE命令。

举个例子，如果我们向服务器提供以下配置:
save 900 1
save 300 10
save 60 10000
那么只要满足以下三个条件中的任意-一个，BGSAVE命令就会被执行:
服务器在900秒之内，对数据库进行了至少1次修改。
服务器在300秒之内，对数据库进行了至少10次修改。
服务器在60秒之内，对数据库进行了至少10000次修改。

当Redis服务器启动时，用户可以通过指定配置文件或者传人启动参数的方式设置save选项，如果用户没有主动设置save选项，那么服务器会为save选项设置默认条件:
save 900 1
save 300 10
save 60 10000

AOF持久化

除了RDB持久化功能之外，Redis 还提供了AOF ( Append Only File )持久化功能。与
RDB持久化通过保存数据库中的键值对来记录数据库状态不同，AOF持久化是通过保存
Redis服务器所执行的写命令来记录数据库状态的，如图11-1 所示。

image.png image.png

AOF持久化功能的实现可以分为 命令追加（append）,文件写入，文件同步（sync）三个步骤
1、命令追加，当AOF持久化功能打开状态时，服务器在执行完一个写命令后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾。
2、文件写入。
因为服务器在处理文件事件时可能会执行写命令，使得- -些内容被追加到aof_ buf 缓冲
区里面,所以在服务器每次结束-个事件循环之前，它都会调用flushAppendOnlyFile函数，考虑是否需要将aof_ buf缓冲区中的内容写人和保存到AOF文件里面。
flushAppend0nlyFile函数的行为由服务器配置的appendfsync选项的值来决定，各个不同值产生的行为如表11-1所示。

image.png image.png image.png

AOF文件的载入与数据还原

因为AOF文件里面包含了重建数据库状态所需的所有写命令，所以服务器只要读人并重新执行一-遍 AOF文件里面保存的写命令，就可以还原服务器关闭之前的数据库状态。

image.png

AOF重写

因为AOF持久化是通过保存被执行的写命令来记录数据库状态的，所以随着服务器运行时间的流逝，AOF文件中的内容会越来越多，文件的体积也会越来越大，如果不加以控制的话，体积过大的AOF文件很可能对Redis服务器、甚至整个宿主计算机造成影响，并且AOF文件的体积越大，使用AOF文件来进行数据还原所需的时间就越多。

为了解决AOF文件体积膨胀的问题，Redis提供了AOF文件重写(rewrite)功能。通过该功能，Redis 服务器可以创建-一个新的AOF文件来替代现有的AOF文件，新旧两个AOF文件所保存的数据库状态相同，但新AOF文件不会包含任何浪费空间的冗余命令，所以新AOF文件的体积通常会比旧AOF文件的体积要小得多。

虽然Redis将生成新AOF文件替换旧AOF文件的功能命名为“AOF文件重写”，但实际上，AOF文件重写并不需要对现有的AOF文件进行任何读取、分析或者写人操作，这个功能是通过读取服务器当前的数据库状态来实现的。

事务

Redis通过MULTI、EXEC、WATCH等命令来实现事务( transaction)功能。事务提供了一种将多个命令请求打包，然后- -次性、 按顺序地执行多个命令的机制，并且在事务执行期间，服务器不会中断事务而改去执行其他客户端的命令请求，它会将事务中的所有命令都放人事务当中，最后由EXEC命令将这个事务提交( commit)给服务器执行:

image.png

命令入队

当一个客户端处于非事务状态时，这个客户端发送的命令会立即被服务器执行
与此不同的是，当一个客户端切换到事务状态后，服务器会根据这个客户端的命令执行不同的操作：

image.png

当一个处于事务状态的客户端向服务器发送EXEC命令时,这个EXEC命令将立即被服务器执行。服务器会遍历这个客户端的事务队列，执行队列中保存的所有命令，最后将执行命令所得的结果全部返回给客户端。

WATCH命令的实现

WATCH命令是- - 个乐观锁( optimistic locking),它可以在EXEC命令执行之前，监视任意数量的数据库键，并在EXEC命令执行时，检查被监视的键是否至少有-一个已经被修改，如果是的话，服务器将拒绝执行事务，并向客户端返回代表事务执行失败的空回复。

image.png

watch命令原理
每个Redis数据库都保存着- -个watched_ keys 字典，这个字典的键是某个被WATCH命令监视的数据库键，而字典的值则是一个链表， 链表中记录了所有监视相应数据库键的客户端:

image.png

通过watched_keys字典，服务器可以清楚地知道哪些数据库键正在被监视，以及哪
些客，户端正在监视这些数据库键。

image.png image.png