Redis核心原理

1. 持久化

• Redis是内存数据库，宕机后数据会消失。

• Redis重启后快速恢复数据，要提供持久化机制

• Redis持久化是为了快速的恢复数据而不是为了存储数据

• Redis有两种持久化方式：RDB和AOF

  注意：Redis持久化不保证数据的完整性。

  当Redis用作DB时，DB数据要完整，所以一定要有一个完整的数据源（文件、mysql）在系统启动时，从这个完整的数据源中将数据load到Redis中

  数据量较小，不易改变，比如：字典库（xml、Table）

  通过info命令可以查看关于持久化的信息

1.1 RDB

RDB（RedisDataBase），是redis默认的存储方式，RDB方式是通过快照（ snapshotting ）完成的。

• 触发方式

  • 符合自定义配置的快照规则
  • 执行save或者bgsave命令
  • 执行flushall命令
  • 执行主从复制操作 (第一次)

• 配置参数定期执行

  在redis.conf中配置：save 多少秒内 数据变了多少(漏斗设计)

  save "" # 不使用RDB存储 不能主从 
  save 900 1 # 表示15分钟（900秒钟）内至少1个键被更改则进行快照。 
  save 300 10 # 表示5分钟（300秒）内至少10个键被更改则进行快照。 
  save 60 10000 # 表示1分钟内至少10000个键被更改则进行快照。
  

• 命令显式触发

  在客户端输入bgsave命令

• RDB执行流程(原理)

  

  1. Redis父进程首先判断：当前是否在执行save，或bgsave/bgrewriteaof（aof文件重写命令）的子
  进程，如果在执行则bgsave命令直接返回。
  2. 父进程执行fork（调用OS函数复制主进程）操作创建子进程，这个复制过程中父进程是阻塞的，
  Redis不能执行来自客户端的任何命令。
  3. 父进程fork后，bgsave命令返回”Background saving started”信息并不再阻塞父进程，并可以响
  应其他命令。
  4. 子进程创建RDB文件，根据父进程内存快照生成临时快照文件，完成后对原有文件进行原子替换。
  （RDB始终完整）
  5. 子进程发送信号给父进程表示完成，父进程更新统计信息。
  6. 父进程fork子进程后，继续工作。
  

• RDB文件结构

  

  1、头部5字节固定为“REDIS”字符串

  2、4字节“RDB”版本号（不是Redis版本号），当前为9，填充后为0009

  3、辅助字段，以key-value的形式

  4、存储数据库号码

  5、字典大小

  6、过期key

  7、主要数据，以key-value的形式存储

  8、结束标志

  9、校验和，就是看文件是否损坏，或者是否被修改

  可以用winhex打开dump.rdb文件查看

• RDB优缺点

  • 优点

    RDB是二进制压缩文件，占用空间小，便于传输（传给slaver）

    主进程fork子进程，可以最大化Redis性能，主进程不能太大，Redis的数据量不能太大，复制过程中主进程阻塞

  • 缺点

    不保证数据完整性，会丢失最后一次快照以后更改的所有数据

1.2 AOF

AOF（append only fifile）是Redis的另一种持久化方式。Redis默认情况下是不开启的。开启AOF持久化后

Redis 将所有对数据库进行过写入的命令（及其参数）（RESP）记录到 AOF 文件， 以此达到记录数据库状态的目的，这样当Redis重启后只要按顺序回放这些命令就会恢复到原始状态了。

AOF会记录过程，RDB只管结果

• AOF持久化实现

  配置redis.conf

  # 可以通过修改redis.conf配置文件中的appendonly参数开启 
  appendonly yes 
  
  # AOF文件的保存位置和RDB文件的位置相同，都是通过dir参数设置的。 
  dir ./ 
  
  # 默认的文件名是appendonly.aof，可以通过appendfilename参数修改 
  appendfilename appendonly.aof
  

• AOF原理

  AOF文件中存储的是redis的命令，同步命令到 AOF 文件的整个过程可以分为三个阶段：

  • 命令传播：Redis 将执行完的命令、命令的参数、命令的参数个数等信息发送到 AOF 程序中。

  • 缓存追加：AOF 程序根据接收到的命令数据，将命令转换为网络通讯协议的格式，然后将协议内容追加到服务器的 AOF 缓存中。

  • 文件写入和保存：AOF 缓存中的内容被写入到 AOF 文件末尾，如果设定的 AOF 保存条件被满足的话，fsync 函数或者 fdatasync 函数会被调用，将写入的内容真正地保存到磁盘中。

  命令传播: 
  当一个 Redis 客户端需要执行命令时， 它通过网络连接， 将协议文本发送给 Redis 服务器。服务器在
  接到客户端的请求之后， 它会根据协议文本的内容， 选择适当的命令函数， 并将各个参数从字符串文
  本转换为 Redis 字符串对象（ StringObject ）。每当命令函数成功执行之后， 命令参数都会被传播到
  AOF 程序
  
  缓存追加:
  当命令被传播到 AOF 程序之后， 程序会根据命令以及命令的参数， 将命令从字符串对象转换回原来的
  协议文本。协议文本生成之后， 它会被追加到 redis.h/redisServer 结构的 aof_buf 末尾。
  redisServer 结构维持着 Redis 服务器的状态， aof_buf 域则保存着所有等待写入到 AOF 文件的协
  议文本（RESP）。
  
  文件写入和保存:
  每当服务器常规任务函数被执行、 或者事件处理器被执行时， aof.c/flushAppendOnlyFile 函数都会被
  调用， 这个函数执行以下两个工作：
  WRITE：根据条件，将 aof_buf 中的缓存写入到 AOF 文件。
  SAVE：根据条件，调用 fsync 或 fdatasync 函数，将 AOF 文件保存到磁盘中。
  

  AOF 保存模式

  Redis 目前支持三种 AOF 保存模式，它们分别是：

  • AOF_FSYNC_NO ：不保存。

    在这种模式下， 每次调用 flushAppendOnlyFile 函数， WRITE 都会被执行， 但 SAVE 会被略过。
    在这种模式下， SAVE 只会在以下任意一种情况中被执行：
    Redis 被关闭
    AOF 功能被关闭
    系统的写缓存被刷新（可能是缓存已经被写满，或者定期保存操作被执行）
    这三种情况下的 SAVE 操作都会引起 Redis 主进程阻塞。
    

  • AOF_FSYNC_EVERYSEC ：每一秒钟保存一次。（默认）

    在这种模式中， SAVE 原则上每隔一秒钟就会执行一次， 因为 SAVE 操作是由后台子线程（fork）调用
    的， 所以它不会引起服务器主进程阻塞
    

  • AOF_FSYNC_ALWAYS ：每执行一个命令保存一次。（不推荐）

    在这种模式下，每次执行完一个命令之后， WRITE 和 SAVE 都会被执行。
    另外，因为 SAVE 是由 Redis 主进程执行的，所以在 SAVE 执行期间，主进程会被阻塞，不能接受命令
    请求。
    AOF 保存模式对性能和安全性的影响
    

  

• AOF重写、触发方式、混合持久化

  AOF记录数据的变化过程，越来越大，需要重写“瘦身”

  Redis可以在 AOF体积变得过大时，自动地在后台（Fork子进程）对 AOF进行重写。重写后的新 AOF文件包含了恢复当前数据集所需的最小命令集合。 所谓的“重写”其实是一个有歧义的词语， 实际上，AOF 重写并不需要对原有的 AOF 文件进行任何写入和读取， 它针对的是数据库中键的当前值。

  举例如下：

  set s1 11
  set s1 22 ------- > set s1 33
  set s1 33
  没有优化的：
  set s1 11
  set s1 22
  set s1 33
  优化后：
  set s1 33
  

  Redis 不希望 AOF 重写造成服务器无法处理请求， 所以 Redis 决定将 AOF 重写程序放到（后台）子进程里执行， 这样处理的最大好处是：

  1、子进程进行 AOF 重写期间，主进程可以继续处理命令请求。
  2、子进程带有主进程的数据副本，使用子进程而不是线程，可以
  在避免锁的情况下，保证数据的安全性。
  

  不过， 使用子进程也有一个问题需要解决： 因为子进程在进行 AOF 重写期间， 主进程还需要继续处理命令， 而新的命令可能对现有的数据进行修改， 这会让当前数据库的数据和重写后的 AOF 文件中的数据不一致

  为了解决这个问题， Redis 增加了一个 AOF 重写缓存， 这个缓存在 fork 出子进程之后开始启用，Redis 主进程在接到新的写命令之后， 除了会将这个写命令的协议内容追加到现有的 AOF 文件之外，还会追加到这个缓存中

  重写过程分析（整个重写操作是绝对安全的）：

  Redis在创建新AOF文件的过程中，会继续将命令追加到现有的AOF文件里面，即使重写过程中发生停机，现有的AOF文件也不会丢失。而一旦新AOF文件创建完毕，Redis就会从旧AOF文件切换到新AOF文件，并开始对新AOF文件进行追加操作。

  当子进程在执行AOF重写时，主进程需要执行以下三个工作：

  处理命令请求。
  将写命令追加到现有的AOF文件中。
  将写命令追加到AOF重写缓存中。
  

  这样一来可以保证：现有的AOF功能会继续执行，即使在AOF重写期间发生停机，也不会有任何数据丢失。 所有对数据库进行修改的命令都会被记录到AOF重写缓存中.

  当子进程完成AOF重写之后，它会向父进程发送一个完成信号，父进程在接到完成信号之后，会调用一个信号处理函数，并完成以下工作：

  将AOF重写缓存中的内容全部写入到新AOF文件中。
  对新的AOF文件进行改名，覆盖原有的AOF文件。
  

  Redis数据库里的+AOF重写过程中的命令——->新的AOF文件—->覆盖老的

  当步骤1执行完毕之后，现有AOF文件、新AOF文件和数据库三者的状态就完全一致了。

  当步骤2执行完毕之后，程序就完成了新旧两个AOF文件的交替。

  这个信号处理函数执行完毕之后，主进程就可以继续像往常一样接受命令请求了。在整个AOF后台重写过程中，只有最后的写入缓存和改名操作会造成主进程阻塞，在其他时候，AOF后台重写都不会对主进程造成阻塞，这将AOF重写对性能造成的影响降到了最低。

  以上就是AOF后台重写，也即是BGREWRITEAOF命令(AOF重写)的工作原理。

  • 触发方式

    #1. 配置触发 redis.conf
    #表示当前aof文件大小超过上一次aof文件大小的百分之多少的时候会进行重写。如果之前没有重写过，以启动时aof文件大小为准
    auto-aof-rewrite-percentage100 
    #限制允许重写最小aof文件大小，也就是文件大小小于64mb的时候，不需要进行优化
    auto-aof-rewrite-min-size64mb
    
    #2.执行bgrewriteaof命令
    127.0.0.1:6379>bgrewriteaof 
    Background append only file rewriting started
    

  • 混合持久化

    RDB和AOF各有优缺点，Redis4.0开始支持rdb和aof的混合持久化。如果把混合持久化打开，aof rewrite的时候就直接把rdb的内容写到aof文件开: RDB的头+AOF的身体—->appendonly.aof

    # 开启
    aof-use-rdb-preamble yes 
    
    AOF文件是rdb文件的头和aof格式的内容，在加载时，首先会识别AOF文件是否以REDIS字符串开头，如果是就按RDB格式加载，加载完RDB后继续按AOF格式加载剩余部分
    

• AOF文件的载入与数据还原

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

  Redis读取AOF文件并还原数据库状态的详细步骤如下：

  1、创建一个不带网络连接的伪客户端（fakeclient）：因为Redis的命令只能在客户端上下文中执行，
  而载入AOF文件时所使用的命令直接来源于AOF文件而不是网络连接，所以服务器使用了一个没有网络
  连接的伪客户端来执行AOF文件保存的写命令，伪客户端执行命令的效果和带网络连接的客户端执行
  命令的效果完全一样
  2、从AOF文件中分析并读取出一条写命令
  3、使用伪客户端执行被读出的写命令
  4、一直执行步骤2和步骤3，直到AOF文件中的所有写命令都被处理完毕为止
  当完成以上步骤之后，AOF文件所保存的数据库状态就会被完整地还原出来
  

  整个过程如下图所示：

• RDB与AOF对比

  1、RDB存某个时刻的数据快照，采用二进制压缩存储，AOF存操作命令，采用文本存储(混合) 
  2、RDB性能高、AOF性能较低
  3、RDB在配置触发状态会丢失最后一次快照以后更改的所有数据，AOF设置为每秒保存一次，则最多
  丢2秒的数据
  4、Redis以主服务器模式运行，AOF不会保存过期键值对数据，Redis以从服务器模式运行，RDB会保
  存过期键值对，当主服务器向从服务器同步时，再清空过期键值对
  
  AOF写入文件时，对过期的key会追加一条del命令，当执行AOF重写时，会忽略过期key和del命令
  

• 应用场景

  内存数据库: rdb+aof 数据不容易丢

  有原始数据源： 每次启动时都从原始数据源中初始化 ，则 不用开启持久化 （数据量较小）

  缓存服务器: rdb 一般性能高

2. 底层数据结构

2.1 RedisDB结构

Redis中存在“数据库”的概念，该结构由redis.h中的redisDb定义。

当redis 服务器初始化时，会预先分配 16 个数据库

所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中

redisClient中存在一个名叫db的指针指向当前使用的数据库

typedef struct redisDb { 
  int id; //id是数据库序号，为0-15（默认Redis有16个数据库） 
  long avg_ttl; //存储的数据库对象的平均ttl（time to live），用于统计
  dict *dict; //存储数据库所有的key-value
  dict *expires; //存储key的过期时间
  dict *blocking_keys;//blpop 存储阻塞key和客户端对象 
  dict *ready_keys;//阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象 
  dict *watched_keys;//存储watch监控的的key和客户端对象 
} redisDb;

id: id是数据库序号，为0-15（默认Redis有16个数据库）

dict: 存储数据库所有的key-value

expires: 存储key的过期时间，后面要详细讲解

2.2 RedisObject结构

Value是一个对象, 包含字符串对象，列表对象，哈希对象，集合对象和有序集合对象

2.2.1 结构信息概览

typedef struct redisObject { 
  unsigned type:4;//类型 对象类型 
  unsigned encoding:4;//编码
  void *ptr;//指向底层实现数据结构的指针 
  //... 
  int refcount;//引用计数 
  //... 
  unsigned lru:LRU_BITS; //LRU_BITS为24bit 记录最后一次被命令程序访问的时间 
  //... 
}robj;

• 4位type

  表示对象的类型: REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。

  type key #获取对象类型
  

• 4位encoding

  表示对象的内部编码 object encoding key命令查看编码类型

• 24位LRU

  lru 记录的是对象最后一次被命令程序访问的时间，（ 4.0 版本占 24 位，2.6 版本占 22 位）。

  高16位存储一个分钟数级别的时间戳，低8位存储访问计数（lfu ： 最近访问次数）

  lru----> 高16位: 最后被访问的时间
  lfu----->低8位：最近访问次数
  

• refcount

  refcount 记录的是该对象被引用的次数，类型为整型

  refcount 的作用，主要在于对象的引用计数和内存回收

  当对象的refcount>1时，称为共享对象

  Redis 为了节省内存，当有一些对象重复出现时，新的程序不会创建新的对象，而是仍然使用原来的对象

• ptr

  ptr 指针指向具体的数据，比如：set hello world，ptr 指向包含字符串 world 的 SDS

2.2.2 7种type

• 字符串对象

  C语言： 字符数组 “\0”, Redis 使用了 SDS(Simple Dynamic String)。用于存储字符串和整型数据

  struct sdshdr{ 
    //记录buf数组中已使用字节的数量 
    int len; 
    //记录 buf 数组中未使用字节的数量 
    int free; 
    //字符数组，用于保存字符串 
    char buf[]; 
  }
  
  # buf[] 的长度=len+free+1
  

  SDS的优势：
  1、SDS在C字符串的基础上加入了free和len字段，获取字符串长度：SDS是O(1)，C字符串是O(n)。
  buf数组的长度=free+len+1 
  2、SDS由于记录了长度，在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。
  3、可以存取二进制数据，以字符串长度len来作为结束标识
  C：\0空字符串二进制数据包括空字符串，所以没有办法存取二进制数据
  SDS：非二进制\0
       二进制：字符串长度可以存二进制数据
  

  使用场景：存储字符串和整型数据、存储key、AOF缓冲区和用户输入缓冲

• 跳跃表

  跳跃表是有序集合（sorted-set）的底层实现，效率高，实现简单

  基本思想: 将有序链表中的部分节点分层，每一层都是一个有序链表

  查找: 在查找时优先从最高层开始向后查找，当到达某个节点时，如果next节点值大于要查找的值或next指针指向null，则从当前节点下降一层继续向后查找。

  例: 如下图, 查找9, 需遍历8个元素

  第一次分层: 遍历5次找到9（红色的线为查找路径）

  第二次分层: 遍历4次找到9

  第三次分层: 遍历4次找到9

  这种数据结构，就是跳跃表，它具有二分查找的功能。

  插入: 上面例子中，9个结点，一共4层，是理想的跳跃表。

  通过抛硬币（概率1/2）的方式来决定新插入结点跨越的层数

  正面:插入上层

  背面：不插入

  删除: 找到指定元素并删除每层的该元素即可

  跳跃表特点：

  ​ 每层都是一个有序链表

  ​ 查找次数近似于层数（1/2）

  ​ 底层包含所有元素

  ​ 空间复杂度 O(n) 扩充了一倍

  Redis跳跃表的实现

  //跳跃表节点 
  typedef struct zskiplistNode { 
    sds ele; /* 存储字符串类型数据 redis3.0版本中使用robj类型表示， 但是在redis4.0.1中直接使用sds类型表示 */ 
    double score;//存储排序的分值 
    struct zskiplistNode *backward;//后退指针，指向当前节点最底层的前一个节点 
    /* 层，柔性数组，随机生成1-64的值 */
    struct zskiplistLevel { 
      struct zskiplistNode *forward; //指向本层下一个节点 
      unsigned int span;//本层下个节点到本节点的元素个数 
    } level[]; 
  } zskiplistNode; 
  
  //链表
  typedef struct zskiplist{ 
    //表头节点和表尾节点 
    structz skiplistNode *header, *tail; 
    //表中节点的数量 
    unsigned long length; 
    //表中层数最大的节点的层数 
    int level; 
  }zskiplist;
  

  完整的跳跃表结构体：

  跳跃表的优势：

  1、可以快速查找到需要的节点 O(logn)

  2、可以在O(1)的时间复杂度下，快速获得跳跃表的头节点、尾结点、长度和高度。

  应用场景：有序集合的实现

• 字典(重点+难点)

  字典dict又称散列表（hash），是用来存储键值对的一种数据结构。

  Redis整个数据库是用字典来存储的。（K-V结构）

  对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。

  **数组：**用来存储数据的容器，采用头指针+偏移量的方式能够以O(1)的时间复杂度定位到数据所在的内存地址。

  Hash（散列）: 作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。

  hash函数可以把Redis里的key：包括字符串、整数、浮点数统一转换成整数。

  数组下标=hash(key)%数组容量(hash值%数组容量得到的余数)

  Hash冲突: 采用单链表在相同的下标位置处存储原始key和value, 当根据key找Value时，找到数组下标，遍历单链表可以找出key相同的value

  **Redis字典实现包括：**字典(dict)、Hash表(dictht)、Hash表节点(dictEntry)。

  // hash表
  typedef struct dictht {
    dictEntry **table; // 哈希表数组 
    unsigned long size; // 哈希表数组的大小 
    unsigned long sizemask; // 用于映射位置的掩码，值永远等于(size-1) 
    unsigned long used; // 哈希表已有节点的数量,包含next单链表数据 
  } dictht;
  
  //1、hash表的数组初始容量为4，随着k-v存储量的增加需要对hash表数组进行扩容，新扩容量为当前量的一倍，即4,8,16,32
  //2、索引值=Hash值&掩码值（Hash值与Hash表容量取余）
  

  //hash表节点
  typedef struct dictEntry { 
    void *key; // 键 
    union { // 值v的类型可以是以下4种类型 
      void *val; 
      uint64_t u64; 
      int64_t s64; 
      double d; 
    } v; 
    struct dictEntry *next; // 指向下一个哈希表节点，形成单向链表 解决hash冲突 
  } dictEntry;
  
  key字段存储的是键值对中的键
  v字段是个联合体，存储的是键值对中的值。
  next指向下一个哈希表节点，用于解决hash冲突
  

  

  //dict字典
  typedef struct dict { 
    dictType *type; // 该字典对应的特定操作函数 
    void *privdata; // 上述类型函数对应的可选参数 
    dictht ht[2]; /* 两张哈希表，存储键值对数据，ht[0]为原生 哈希表， ht[1]为 rehash 哈希表 */ 
    long rehashidx; /*rehash标识 当等于-1时表示没有在 rehash， 否则表示正在进行rehash操作，存储的值表示 hash表 ht[0]的rehash进行到哪个索引值 (数组下标)*/ 
    int iterators; // 当前运行的迭代器数量 
  } dict;
  
  type字段，指向dictType结构体，里边包括了对该字典操作的函数指针
  
  typedef struct dictType { 
    // 计算哈希值的函数 
    unsigned int (*hashFunction)(const void *key); 
    // 复制键的函数 
    void *(*keyDup)(void *privdata, const void *key); 
    // 复制值的函数 
    void *(*valDup)(void *privdata, const void *obj); 
    // 比较键的函数 
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); 
    // 销毁键的函数 
    void (*keyDestructor)(void *privdata, void *key); 
    // 销毁值的函数 
    void (*valDestructor)(void *privdata, void *obj); 
  } dictType;
  

  Redis字典除了主数据库的K-V数据存储以外，还可以用于：散列表对象、哨兵模式中的主从节点管理等在不同的应用中，字典的形态都可能不同，dictType是为了实现各种形态的字典而抽象出来的操作函数（多态）。

  完整的Redis字典数据结构：

  字典扩容: 字典达到存储上限（阈值 0.75），需要rehash（扩容）

  扩容流程:

  1. 初次申请默认容量为4个dictEntry，非初次申请为当前hash表容量的一倍。
  2. rehashidx=0表示要进行rehash操作。
  3. 新增加的数据在新的hash表h[1]
  4. 修改、删除、查询在老hash表h[0]、新hash表h[1]中（rehash中）
  5. 将老的hash表h[0]的数据重新计算索引值后全部迁移到新的hash表h[1]中，这个过程称为
  rehash。
  

  渐进式rehash: 当数据量巨大时rehash的过程是非常缓慢的，所以需要进行优化。

  服务器忙，则只对一个节点进行rehash

  服务器闲，可批量rehash(100节点)

  应用场景：

  1、主数据库的K-V数据存储

  2、散列表对象（hash）

  3、哨兵模式中的主从节点管理

• 压缩列表

  压缩列表（ziplist）是由一系列特殊编码的连续内存块组成的顺序型数据结构

  是一个字节数组，可以包含多个节点（entry）。每个节点可以保存一个字节数组或一个整数。

  zlbytes：压缩列表的字节长度

  zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量

  zllen：压缩列表的元素个数

  entry1..entryX : 压缩列表的各个节点

  zlend：压缩列表的结尾，占一个字节，恒为0xFF（255）

  

  previous_entry_length：前一个元素的字节长度

  encoding:表示当前元素的编码

  content:数据内容

  应用场景：
  
  sorted-set和hash元素个数少且是小整数或短字符串（直接使用）
  
  list用快速链表(quicklist)数据结构存储，而快速链表是双向列表与压缩列表的组合。（间接使用）
  

• 整数集合

  整数集合(intset)是一个有序的（整数升序）、存储整数的连续存储结构

  当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（2^64），使用该结构体存储。

  应用场景：可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

• 快速列表（重要）

  快速列表（quicklist）是Redis底层重要的数据结构。是列表的底层实现。（在Redis3.2之前，Redis采用双向链表（adlist）和压缩列表（ziplist）实现。）在Redis3.2以后结合adlist和ziplist的优势Redis设计出了quicklist。

  双向列表:

  双向链表优势：
  1. 双向：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。 2. 普通链表（单链表）：节点类保留下一节点的引用。链表类只保留头节点的引用，只能从头节点插
  入删除
  3. 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结
  束。
  环状：头的前一个节点指向尾节点
  4. 带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。 5. 多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。
  

  快速列表: quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。quicklist中的每个节点ziplist都能够存

  储多个数据元素

  数据压缩: quicklist每个节点的实际数据存储结构为ziplist，这种结构的优势在于节省存储空间。为了进一步降低ziplist的存储空间，还可以对ziplist进行压缩。Redis采用的压缩算法是LZF。其基本思想是：数据与前面重复的记录重复位置及长度，不重复的记录原始数据。压缩过后的数据可以分成多个片段，每个片段有两个部分：解释字段和数据字段

  应用场景: 列表(List)的底层实现、发布与订阅、慢查询、监视器等功能。

• 流对象

  stream主要由：消息、生产者、消费者和消费组构成。

  

  Redis Stream的底层主要使用了listpack（紧凑列表）和Rax树（基数树）。

  listpack: listpack表示一个字符串列表的序列化，listpack可用于存储字符串或整数。用于存储stream的消息内容

  Rax: Rax 是一个有序字典树 (基数树 Radix Tree)，按照 key 的字典序排列，支持快速地定位、插入和删除操作

  Rax 被用在 Redis Stream 结构里面用于存储消息队列，在 Stream 里面消息 ID 的前缀是时间戳 + 序号，这样的消息可以理解为时间序列消息。使用 Rax 结构 进行存储就可以快速地根据消息 ID 定位到具体的消息，然后继续遍历指定消息 之后的所有消息。

2.2.3 10种encoding

encoding 表示对象的内部编码，占 4 位。

Redis通过 encoding 属性为对象设置不同的编码

对于少的和小的数据，Redis采用小的和压缩的存储方式，体现Redis的灵活性, 大大提高了 Redis 的存储量和执行效率

• string: int, raw, embstr

int: REDIS_ENCODING_INT（int类型的整数）
embstr:  REDIS_ENCODING_EMBSTR(编码的简单动态字符串) 小字符串 长度小于44个字节
raw:  REDIS_ENCODING_RAW （简单动态字符串） 大字符串 长度大于44个字节

• list: 列表的编码是quicklist REDIS_ENCODING_QUICKLIST（快速列表）

• hash: 散列的编码是字典和压缩列表

dict: REDIS_ENCODING_HT（字典） 当散列表元素的个数比较多或元素不是小整数或短字符串时。
ziplsit: REDIS_ENCODING_ZIPLIST（压缩列表）当散列表元素的个数比较少，且元素都是小整数或短字符串时。

• set: 集合的编码是整形集合和字典

inset: REDIS_ENCODING_INTSET（整数集合）当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（<18446744073709551616）
dict: REDIS_ENCODING_HT（字典） 当Redis集合类型的元素是非整数或都处在64位有符号整数范围外（>18446744073709551616）

zset: 有序集合的编码是压缩列表和跳跃表+字典

ziplist REDIS_ENCODING_ZIPLIST（压缩列表）当元素的个数比较少，且元素都是小整数或短字符串时。
skiplist + dict: REDIS_ENCODING_SKIPLIST（跳跃表+字典）当元素的个数比较多或元素不是小整数或短字符串时。

3 缓存过期和淘汰策略

长期使用,key会不断增加,Redis作为缓存使用,物理内存占满,swap(内存与硬盘交换),IO性能急剧下降

3.1 maxmemory

• 不设置maxmemory

  key不能淘汰,如果作为DB使用, 可以做集群,横向扩展

  缓存淘汰策略: 禁止驱逐(默认)

• 设置maxmemory

  作为缓存使用,key不断增加, maxmemory ： 默认为0 不限制, 一般设置物理内存的3/4

  # redis.conf
  maxmemory 1024mb
  

  # 查看maxmemory
  CONFIG GET maxmemory
  

  设置maxmemory后，当趋近maxmemory时，通过缓存淘汰策略，从内存中删除对象

3.2 expire数据结构

在Redis中可以使用expire命令设置一个键的存活时间(ttl: time to live)，过了这段时间，该键就会自动被删除

expire命令的使用方法如下：expire key ttl(单位秒)

#示例
127.0.0.1:6379> expire name 2 #2秒失效 
(integer) 1 
127.0.0.1:6379> get name 
(nil) 
127.0.0.1:6379> set name zhangfei 
OK
127.0.0.1:6379> ttl name #永久有效 -1
(integer) -1 
127.0.0.1:6379> expire name 30 #30秒失效 
(integer) 1 
127.0.0.1:6379> ttl name #还有24秒失效 
(integer) 24 
127.0.0.1:6379> ttl name #失效 -2
(integer) -2

expire原理

typedef struct redisDb { 
  dict *dict; -- key Value 
  dict *expires; -- key ttl 
  dict *blocking_keys; 
  dict *ready_keys; 
  dict *watched_keys; 
  int id; 
} redisDb;

上面的代码是Redis 中关于数据库的结构体定义，这个结构体定义中除了 id 以外都是指向字典的指针，其中我们只看 dict 和 expires。

dict 用来维护一个 Redis 数据库中包含的所有 Key-Value 键值对，expires则用于维护一个 Redis 数据库中设置了失效时间的键(即key与失效时间的映射)。

当我们使用 expire命令设置一个key的失效时间时，Redis 首先到 dict 这个字典表中查找要设置的key是否存在，如果存在就将这个key和失效时间添加到 expires 这个字典表。

当我们使用 setex命令向系统插入数据时，Redis 首先将 Key 和 Value 添加到 dict 这个字典表中，然后将 Key 和失效时间添加到 expires 这个字典表中。

简单地总结来说就是，设置了失效时间的key和具体的失效时间全部都维护在 expires 这个字典表中。

3.3 删除策略

Redis的数据删除有定时删除、惰性删除和主动删除三种方式。

Redis目前采用惰性删除+主动删除的方式。

• 定时删除

  在设置键的过期时间的同时，创建一个定时器，让定时器在键的过期时间来临时，立即执行对键的删除操作。需要创建定时器，而且消耗CPU，一般不推荐使用。

• 惰性删除

  在key被访问时如果发现它已经失效，那么就删除它。调用expireIfNeeded函数，该函数的意义是：读取数据之前先检查一下它有没有失效，如果失效了就删除它。

• 主动删除

  在redis.conf文件中可以配置主动删除策略,默认是no-enviction（不删除）

  maxmemory-policy allkeys-lru
  

LRU:

LRU (Least recently used) 最近最少使用，算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下:

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。
4. 在Java中可以使用LinkHashMap（哈希链表）去实现LRU

Redis的LRU数据淘汰机制

在服务器配置中保存了 lru 计数器 server.lrulock，会定时（redis 定时程序 serverCorn()）更新，server.lrulock 的值是根据 server.unixtime 计算出来的

另外，从 struct redisObject 中可以发现，每一个 redis 对象都会设置相应的 lru。可以想象的是，每一次访问数据的时候，会更新 redisObject.lru。

LRU 数据淘汰机制是这样的：在数据集中随机挑选几个键值对，取出其中 lru 最大的键值对淘汰。

• volatile-lru: 从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰
• allkeys-lru: 从数据集（server.db[i].dict）中挑选最近最少使用的数据淘汰

LFU: LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小,volatile-lfu allkeys-lfu

RANDOM: 随机,volatile-random allkeys-random

TTL: 从过期时间的表中随机挑选几个键值对，取出其中 ttl 最小的键值对淘汰, volatile-ttl

NOENVICTION: 禁止驱逐数据，不删除(默认)

策略选择:
allkeys-lru ： 在不确定时一般采用策略。 冷热数据交换
volatile-lru ： 比allkeys-lru性能差 存: 过期时间
allkeys-random ： 希望请求符合平均分布(每个元素以相同的概率被访问)
自己控制：volatile-ttl 缓存穿透

4. 通讯协议及事件处理机制

4.1 通信协议

Redis是单进程单线程的。应用系统和Redis通过Redis协议（RESP）进行交互

4.1.1 请求响应模式

Redis协议位于TCP层之上，即客户端和Redis实例保持双工的连接

• 串行的请求响应模式(ping-pong)

  串行化是最简单模式，客户端与服务器端建立长连接, 连接通过心跳机制检测（ping-pong） ack应答, 客户端发送请求，服务端响应，客户端收到响应后，再发起第二个请求，服务器端再响应

  telnet和redis-cli 发出的命令 都属于该种模式

  网络传输耗时,性能低

• 双工的请求响应模式

  批量请求,批量响应, 请求响应交叉进行，不会混淆(TCP双工)

  pipeline的作用是将一批命令进行打包，然后发送给服务器，服务器执行完按顺序打包返回。

  通过pipeline，一次pipeline（n条命令）=一次网络时间 + n次命令时间

  通过jedis可以很方便的使用pipeline

  Jedis redis = new Jedis("192.168.1.111", 6379); 
  redis.auth("12345678");//授权密码 对应redis.conf的requirepass密码 
  Pipeline pipe = jedis.pipelined(); 
  for (int i = 0; i <50000; i++) { 
    pipe.set("key_"+String.valueOf(i),String.valueOf(i)); 
  }
  //将封装后的PIPE一次性发给
  redis pipe.sync();
  

• 原子化的批量请求响应模式(事务)

  Redis可以利用事务机制批量执行命令

• 发布订阅模式(pub/sub)

  发布订阅模式是：一个客户端触发，多个客户端被动接收，通过服务器中转

• 脚本化的批量执行(lua)

  客户端向服务器端提交一个lua脚本，服务器端执行该脚本

4.1.2 请求数据格式

Redis客户端与服务器交互采用序列化协议（RESP）。

请求以字符串数组的形式来表示要执行命令的参数, Redis使用命令特有（command-specifific）数据类型作为回复

Redis通信协议的主要特点有：

• 客户端和服务器通过 TCP 连接来进行数据交互， 服务器默认的端口号为 6379 。

• 客户端和服务器发送的命令或数据一律以 \r\n （CRLF）结尾。

• 在这个协议中， 所有发送至 Redis 服务器的参数都是二进制安全（binary safe）的。

• 简单，高效，易读。

• 内联格式

  可以使用telnet给Redis发送命令，首字符为Redis命令名的字符，格式为 str1 str2 str3…

• 规范格式(redis-cli) RESP

  1、间隔符号，在Linux下是\r\n，在Windows下是\n
  2、简单字符串 Simple Strings, 以 "+"加号 开头
  3、错误 Errors, 以"-"减号 开头
  4、整数型 Integer， 以 ":" 冒号开头
  5、大字符串类型 Bulk Strings, 以 "$"美元符号开头，长度限制512M
  6、数组类型 Arrays，以 "*"星号开头
  

  用SET命令来举例说明RESP协议的格式。

  redis> SET mykey Hello 
  "OK"
  

  实际发送的请求数据：

  *3\r\n$3\r\nSET\r\n$5\r\nmykey\r\n$5\r\nHello\r\n 
  *3
  $3
  SET 
  $5
  mykey 
  $5
  Hello
  

  实际收到的响应数据：

  +OK\r\n
  

4.1.3 命令处理流程

整个流程包括：服务器启动监听、接收命令请求并解析、执行命令请求、返回命令回复等。

• server启动时监听socket

  启动调用 initServer方法：
  	创建eventLoop（事件机制）
  	注册时间事件处理器
  	注册文件事件（socket）处理器
  	监听 socket 建立连接
  

• 建立client

  redis-cli建立socket
  redis-server为每个连接（socket）创建一个 Client 对象
  创建文件事件监听socket
  指定事件处理函数
  

• 读取socket数据到输入缓冲区

  从client中读取客户端的查询缓冲区内容。

• 解析获取命令

  将输入缓冲区中的数据解析成对应的命令, 判断是单条命令还是多条命令并调用相应的解析器解析

• 执行命令

  

4.1.4 协议响应格式

• 状态回复

  "+OK"
  

• 错误回复

  1. -ERR unknown command 'foobar' 
  2. -WRONGTYPE Operation against a key holding the wrong kind of value
  

• 整数回复

  ":6"
  

• 批量回复

  "$6 foobar"
  

• 多条批量回复

  "*3"
  

4.1.5 协议解析处理

• 协议解析

  用户在Redis客户端键入命令后，Redis-cli会把命令转化为RESP协议格式，然后发送给服务器。服务器再对协议进行解析

  1.解析命令请求参数数量
    命令请求参数数量的协议格式为"*N\r\n" ,其中N就是数量
  2.循环解析请求参数
    首字符必须是"$"，使用"/r"定位到行尾，之间的数是参数的长度，从/n后到下一个"$"之间就是参数的值了
    循环解析直到没有"$"
  

• 协议执行

  协议的执行包括命令的调用和返回结果

  判断参数个数和取出的参数是否一致

  RedisServer解析完命令后,会调用函数processCommand处理该命令请求

  1. quit校验，如果是“quit”命令，直接返回并关闭客户端
  2. 命令语法校验，执行lookupCommand，查找命令(set)，如果不存在则返回：“unknowncommand”错误。
  3. 参数数目校验，参数数目和解析出来的参数个数要匹配，如果不匹配则返回：“wrong number of arguments”错误。
  4. 此外还有权限校验，最大内存校验，集群校验，持久化校验等等
  

  校验成功后，会调用call函数执行命令，并记录命令执行时间和调用次数

  如果执行命令时间过长还要记录慢查询日志

  执行命令后返回结果的类型不同则协议格式也不同

4.2 事件处理机制

Redis服务器是典型的事件驱动系统

4.2.1 文件事件

文件事件即Socket的读写事件，也就是IO事件。 fifile descriptor （文件描述符）

客户端的连接、命令请求、数据回复、连接断开

• socket

  套接字（socket）是一个抽象层，应用程序可以通过它发送或接收数据。

• Reactor

  Redis事件处理机制采用单线程的Reactor****模式，属于I/O****多路复用的一种常见模式。

  IO多路复用( I/O multiplexing ）指的通过单个线程管理多个Socket。

  Reactor pattern(反应器设计模式)是一种为处理并发服务请求，并将请求提交到 一个或者多个服务处理程序的事件设计模式。

  Reactor模式是事件驱动的
  	有一个或多个并发输入源（文件事件）
  	有一个Service Handler
  	有多个Request Handlers
  
  这个Service Handler会同步的将输入的请求（Event）多路复用的分发给相应的Request Handler
  

  

  Handle：I/O操作的基本文件句柄，在linux下就是fd（文件描述符）
  Synchronous Event Demultiplexer ：同步事件分离器，阻塞等待Handles中的事件发生。（系统）
  Reactor: 事件分派器，负责事件的注册，删除以及对所有注册到事件分派器的事件进行监控， 当事件
  				 发生时会调用Event Handler接口来处理事件。
  Event Handler: 事件处理器接口，这里需要Concrete Event Handler来实现该接口
  Concrete Event Handler：真实的事件处理器，通常都是绑定了一个handle，实现对可读事件 进行读
  				 取或对可写事件进行写入的操作。
  

  

• 4种IO多路复用模型与选择

  select，poll，epoll、kqueue都是IO多路复用的机制。

  I/O多路复用就是通过一种机制，一个进程可以监视多个描述符（socket），一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作

  • select

    int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
    

    select 函数监视的文件描述符分3类，分别是: writefds, readfds, exceptfds

    调用后select函数会阻塞，直到有描述符就绪（有数据可读、可写、或者有except），或者超时（timeout指定等待时间，如果立即返回设为null即可），函数返回。当select函数返回后，可以通过遍历fd列表，来找到就绪的描述符。

    优点: select目前几乎在所有的平台上支持，其良好跨平台支持也是它的一个优点

    缺点: 单个进程打开的文件描述是有一定限制的，它由FD_SETSIZE设置，默认值是1024，采用数组存储, 另外在检查数组中是否有文件描述需要读写时，采用的是线性扫描的方法，即不管这些socket是不是活跃的，都轮询一遍，所以效率比较低

  • poll

    int poll (struct pollfd *fds, unsigned int nfds, int timeout); 
    struct pollfd { 
      int fd; //文件描述符 
      short events; //要监视的事件 
      short revents; //实际发生的事件 
    };
    

    poll使用一个 pollfd的指针实现，pollfd结构包含了要监视的event和发生的event，不再使用select“参数-值”传递的方式

    优点: 采样链表的形式存储，它监听的描述符数量没有限制，可以超过select默认限制的1024大小

    缺点: 另外在检查链表中是否有文件描述需要读写时，采用的是线性扫描的方法，即不管这些socket是不是活跃的，都轮询一遍，所以效率比较低

  • epoll

    epoll是在linux2.6内核中提出的，是之前的select和poll的增强版本。相对于select和poll来说，epoll更加灵活，没有描述符限制。epoll使用一个文件描述符管理多个描述符，将用户关系的文件描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的copy只需一次。

    int epoll_create(int size)
    
    //创建一个epoll的句柄。自从linux2.6.8之后，size参数是被忽略的。需要注意的是，当创建好epoll
    //句柄后，它就是会占用一个fd值，在linux下如果查看/proc/进程id/fd/，是能够看到这个fd的，所
    //以在使用完epoll后，必须调用close()关闭，否则可能导致fd被耗尽
    

    int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)
    
    //epoll的事件注册函数，它不同于select()是在监听事件时告诉内核要监听什么类型的事件，而是在这里先
    //注册要监听的事件类型
    //第一个参数是epoll_create()的返回值。
    //第二个参数表示动作，用三个宏来表示
      	EPOLL_CTL_ADD：注册新的fd到epfd中；
    		EPOLL_CTL_MOD：修改已经注册的fd的监听事件；
    		EPOLL_CTL_DEL：从epfd中删除一个fd；
    //第三个参数是需要监听的fd
    //第四个参数是告诉内核需要监听什么事
    

    int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
    //等待内核返回的可读写事件，最多返回maxevents个事件。
    

    优点: epoll 没有最大并发连接的限制，上限是最大可以打开文件的数目，举个例子,在1GB内存的机器上大约是10万左右, 效率提升， epoll 最大的优点就在于它只管活跃的连接 ，而跟连接总数无关，因此在实际的网络环境 中， epoll 的效率就会远远高于 select 和 poll , epoll使用了共享内存，不用做内存拷贝

  • kqueue

    kqueue 是 unix 下的一个IO多路复用库。最初是2000年Jonathan Lemon在FreeBSD系统上开发的一个高性能的事件通知接口。注册一批socket描述符到 kqueue 以后，当其中的描述符状态发生变化时，kqueue 将一次性通知应用程序哪些描述符可读、可写或出错了

    优点: 能处理大量数据，性能较高

• 文件事件分派器

  在redis中，对于文件事件的处理采用了Reactor模型。采用的是epoll的实现方式

  Redis在主循环中统一处理文件事件和时间事件，信号事件则由专门的handler来处理

• 事件处理器

  • 连接处理函数 acceptTCPHandler

    当客户端向 Redis 建立 socket时，aeEventLoop 会调用 acceptTcpHandler 处理函数，服务器会为每个链接创建一个 Client 对象，并创建相应文件事件来监听socket的可读事件，并指定事件处理函数。

  • 请求处理函数 readQueryFromClient

    当客户端通过 socket 发送来数据后，Redis 会调用 readQueryFromClient 方法,readQueryFromClient方法会调用 read 方法从 socket 中读取数据到输入缓冲区中，然后判断其大小是否大于系统设置的client_max_querybuf_len，如果大于，则向 Redis返回错误信息，并关闭 client

  • 命令回复处理器 sendReplyToClient

    sendReplyToClient 函数是Redis的命令回复处理器，这个处理器负责将服务器执行命令后得到的命令回复通过套接字返回给客户端。

    1、将outbuf内容写入到套接字描述符并传输到客户端

    2、aeDeleteFileEvent 用于删除 文件写事件

4.2.2 时间事件

一个时间事件主要由以下三个属性组成：

• id(全局唯一id)

• when (毫秒时间戳，记录了时间事件的到达时间)

• timeProc（时间事件处理器，当时间到达时，Redis就会调用相应的处理器来处理事件）

serverCron

时间事件的最主要的应用是在redis服务器需要对自身的资源与配置进行定期的调整，从而确保服务器的长久运行，这些操作由redis.c中的serverCron函数实现。该时间事件主要进行以下操作：

 1）更新redis服务器各类统计信息，包括时间、内存占用、数据库占用等情况。
 2）清理数据库中的过期键值对。
 3）关闭和清理连接失败的客户端。
 4）尝试进行aof和rdb持久化操作。
 5）如果服务器是主服务器，会定期将数据向从服务器做同步操作。
 6）如果处于集群模式，对集群定期进行同步与连接测试操作。
 
 redis服务器开启后，就会周期性执行此函数，直到redis服务器关闭为止。默认每秒执行10次，平
均100毫秒执行一次，可以在redis配置文件的hz选项，调整该函数每秒执行的次数

server.hz: 即1秒内执行的次数

# redis.conf
hz 10 #100毫秒一次,1秒执行10次

run_with_period: 定时任务执行都是在10毫秒的基础上定时处理自己的任务(run_with_period(ms))，即调用run_with_period(ms)[ms是指多长时间执行一次，单位是毫秒]来确定自己是否需要执行。返回1表示执行。假如有一些任务需要每500ms执行一次，就可以在serverCron中用run_with_period(500)把每500ms需要执行一次的工作控制起来

• 定时事件

  让一段程序在指定的时间之后执行一次,aeTimeProc（时间处理器）的返回值是AE_NOMORE, 该事件在达到后删除，之后不会再重复

• 周期性事件

  让一段程序每隔指定时间就执行一次,aeTimeProc（时间处理器）的返回值不是AE_NOMORE,当一个时间事件到达后，服务器会根据时间处理器的返回值，对时间事件的 when 属性进行更新，让这个事件在一段时间后再次达到。

  serverCron就是一个典型的周期性事件

4.2.3 aeEventLoop

aeEventLoop 是整个事件驱动的核心，Redis自己的事件处理机制

它管理着文件事件表和时间事件列表

不断地循环处理着就绪的文件事件和到期的时间事件。

文件事件: events, fired, apidata

时间事件: timeEventHead, feforesleep, aftersleep

4.2.4 aeMain

aeMain 函数其实就是一个封装的 while 循环，循环中的代码会一直运行直到 eventLoop 的 stop 被设置为1(true)。它会不停尝试调用 aeProcessEvents 对可能存在的多种事件进行处理，而aeProcessEvents 就是实际用于处理事件的函数

aemain函数中，首先调用Beforesleep。这个方法在Redis每次进入sleep/wait去等待监听的端口发生I/O事件之前被调用。当有事件发生时，调用aeProcessEvent进行处理

4.2.5 aeProcessEvent

首先计算距离当前时间最近的时间事件，以此计算一个超时时间；

然后调用 aeApiPoll 函数去等待底层的I/O多路复用事件就绪；

aeApiPoll 函数返回之后，会处理所有已经产生文件事件和已经达到的时间事件。