Redis笔记_5

QuickList

• ZipList虽然节省内存，但是申请的是连续的空间，如果内存占用较多，内存申请效率很低；
  • 这时候需要限制ZipList的长度或者entry大小；
  • 也可以创建多个ZipList分片存储数据
  • 但是拆分后比较分散，不方便管理和查找，所以引入了QuickList

• QuickList本质上是一个双端链表，其中的每一个节点都是ZipList
  
• 为了避免QuickList中每个ZipList的entry过多，可以配置list-max-ziplist-size来进行限制
  • 如果为正，表示ZipList的允许的entry最大个数
  • 如果为负，表示ZipList的最大内存大小，共五种情况

    情况	内存占用
    -1	<= 4KB
    -2(默认)	<= 8KB
    -3	<= 16KB
    -4	<= 32KB
    -5	<= 64KB

• QuickList同时可以对节点ZipList进行压缩，通过配置list-compress-depth控制。因为链表一般都是首尾访问较多，所以首尾不压缩。

  情况	含义
  0	不压缩
  1	表示QuickList首尾各有一个节点不压缩，中间节点压缩
  2	表示QuickList首尾各有两个节点不压缩，中间节点压缩
  …	… 以此类推

typedef struct quicklist{
    // 头节点
    quickliskNode *head;
    // 尾节点
    quicklistNode *tail;
    // 所有ziplist的entry数量
    unsigned long count;
    // ziplists总数
    unsigned long len;
    // ziplist的entry上限，默认为-2
    int fill : QL_RILL_BITS;
    // 首尾不压缩节点数量
    unsigned int compress : QL_COMP_BITS;
    // 内存重新分配时的书签数量以及数组，一般用不到
    unsigned int bookmark_count : QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistNode {
    // 前一个节点指针
    struct quicklistNode *prev;
    // 后一个
    struct quicklistNode *next;
    // 当前节点
    unsigned char *zl;
    // 当前节点的ZipList的entry个数
    unsigned int count : 16;
    // 编码方式: 1, ZipList; 2, lzf压缩模式
    unsigned int encoding : 2;
    // 数据容器类型(预留): 1, 其他; 2, ZipList
    unsigned int container : 2;
    // 是否被解压缩: 1, 被解压，需要重新压缩
    unsigned int recomress : 1;
    unsigned int attempted_compress : 1; // 测试用
    unsigned int extra : 10; // 预留字段
} quicklistNode;

特点:

1. 节点为ZipList的双端链表
2. 解决传统链表内存占用问题
3. 控制ZipList大小，解决连续内存空间申请效率问题
4. 中间节点可以压缩，进一步节省内存

SkipList

• 是一个链表，但是

  • 元素升序排列

  • 包含多级指针，指针跨度不同

  • 最多允许32级指针

    

特点:

1. 一个双向链表，每个节点包含score和ele值
2. 节点按照score值排序，如果相同则按照ele字典排序
3. 每个节点可以包含多层指针，层数是1~32的随机数
4. 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
5. 增删改查的效率与红黑树基本一致，实现更简单

RedisObject

• 任意的数据类型的键和值都会被封装成RedisObject

  typedef struct redisObject{
      unsigned type : 4;
      unsigned encoding : 4;
      unsigned lru : LRU_BITS;
      int refcount;
      void *ptr;
  } robj;

  • type: 对象类型，分别是string、hash、list、set、zset，占用4bits

    # define OBJ_STRING 0
    # define OBJ_LIST 1
    # define OBJ_SET 2
    # define OBJ_ZSET 3
    # define OBJ_HASH 4

  • encoding: 底层11种编码方式，占用4bits

    编号	编码方式	说明
    0	OBJ_ENCODING_RAW	raw编码动态字符串
    1	OBJ_ENCODING_INT	long类型整数字符串
    2	OBJ_ENCODING_HT	哈希表(字典dict)
    3	OBJ_ENCODING_ZIPMAP	废弃
    4	OBJ_ENCODING_LINKEDLIST	双端列表
    5	OBJ_ENCODING_ZIPLIST	压缩列表
    6	OBJ_ENCODING_INTSET	整数集合
    7	OBJ_ENCODING_SKIPLIST	跳表
    8	OBJ_ENCODING_EMBSTR	embstr动态字符串
    9	OBJ_ENCODING_QUICKLIST	快速列表
    10	OBJ_ENCODING_STREAM	stream流

    • 数据类型对应的编码方式

      数据类型	编码方式
      OBJ_STRING	int, embstr, raw
      OBJ_LIST	LinkedList和ZipList(3.2版本前)；QuickList(3.2版本后)
      OBJ_SET	intset，HT
      OBJ_ZSET	ZipList, HT, SkipList
      OBJ_HASH	ZipList, HT

  • lru: 该对象最后一次被访问的时间，占用24bits

  • refcount: 对象引用计数器，为0表示无人引用，可以被回收

  • *ptr: 指针，指向存放实际数据的空间

String

• 基本编码方式是RAW，基于SDS实现，上限为512MB
• 如果SDS长度小于44B，则会采用EMBSTR编码，此时objecthead与SDS是一段连续的空间，申请内存只需要调用一次内存分配函数，效率更高
• 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码，直接将数据保存在RedisObject的ptr指针位置，正好8B，就不需要SDS了

Zset

• 底层结构由Dict和SkipList实现，但是内存占用较高

• 所以还有第二种实现方式: 元素数量不多时，哈希表和SkipList优势不明显，更消耗内存，所以此时会用ZipList节省内存，不过需要同时满足

  1. 元素数量小于zset_max_ziplist_entries默认128，如果为0就禁用ZipList
  2. 每个元素都小于zset_max_ziplist_value字节，默认值64

• ZipList本身没排序功能，也没有键值对的概念，需要有ZSet通过编码实现

  • ZipList是连续内存，因此score和ele是紧挨在一起的两个entry，element在前，score在后
  • score越小越接近队首，score越大越接近队尾，按照score升序排列

• 两种不同的编码就涉及到编码转换，添加元素的时候会进行判断，如果是ZipList，就会进行判断，是否需要转换为HT+SL

Hash

• Hash底层跟ZSet基本一致，只是排序有关的SkipList去掉
• 默认采用ZipList，用来节省内存。ZipList中相邻两个entry分别保存field和value
• 数据量较大的时候，Hash会转换为Dict编码，触发条件有两个：
  • ZipList中元素数量超过了hash-max-ziplist-entries默认512B
  • ZipList中任意entry大小超过了hash-max-ziplist-value默认64B

用户空间和内核空间

1. 寻址空间分为两部分: 内核空间，用户空间
2. 用户空间只能执行受限的命令(Ring3)，不能直接调用系统资源，必须通过内核提供的接口来访问
3. 内核空间可以执行特权命令(Ring0)，调用一切系统资源

空间切换

为了提高IO效率，会在用户空间和内核空间都加入缓冲区

• 写数据时，要把用户缓冲数据拷贝到内核缓冲区，然后写入设备
• 读数据时，要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区

IO模型(5种)

阻塞IO

• 两个阶段都必须阻塞等待，性能差一些
  

非阻塞IO

• recvfrom操作会立即返回结果而不是阻塞用户进程，等待数据就绪的时候非阻塞的，实际上拷贝数据的时候还是阻塞的。
• 没啥用，没有提升系统性能，反而会提升CPU使用率。
  

• 阻塞IO和非阻塞IO都需要调用recvfrom来获取数据，差别在于无数据时的处理方案。

IO多路复用

• 如果客户端处理Socket请求时，单线程情况下，依次处理每一个Socket，如果正在处理的Socket恰好未就绪，数据不可读或不可写，则线程被阻塞，其他客户端Socket就必须等待，性能会很差。

• 文件描述符(FD): 从0开始递增的无符号整数，关联Linux中的一个文件

• IO多路复用就是用单线程，监听多个FD，在某个FD可读可写时得到通知，避免无效等待，充分利用CPU
  

• 有三种监听FD的方式

  1. select
  2. poll
  3. epoll

• select 和 poll只会通知用户进程有FD就绪，但是不确定是哪个FD，需要用户进程逐个遍历FD确认

• epoll会在通知用户进程FD就绪的通知，把已经就绪的FD写入用户空间

select

问题:

• 每次执行select都需要将整个fd_set从用户空间拷贝到内核空间，select结束还需要再次拷贝，因此涉及两次切换，两次拷贝
• select不知道是哪个FD就绪，需要遍历整个fd_set
• fd_set监听的FD数量不能超过1024

poll

IO流程:

1. 创建pollfd数组，向其中添加关注的FD信息，数组大小自定义
2. 调用poll函数，将pollfd数组拷贝到内核空间，转链表存储，无上限
3. 内核遍历FD，判断是否就绪
4. 数据就绪或超时后，拷贝pollfd数组到用户空间，返回就绪FD数量n
5. 用户进程判断n是否大于0
6. 大于0则遍历pollfd数组，找到就绪的FD

poll VS select:

• select模式中的fd_set大小固定为1024，pollfd在内核中采用链表，理论上没有上限
• 监听的FD越多，每次遍历的消耗的时间也越久，性能反而会下降

epoll

对select 和 poll的改进，提供了三个函数:

struct eventpoll{
    struct rb_root rbr; // 红黑树，记录所有监听的fd
    struct list_head rdlist;// 链表，记录就绪的FD
};
// 会在内核创建eventpoll结构体，返回对应的句柄epfd
int epoll_create(int size);

// 将一个FD添加到epoll红黑树中，并设置ep_poll_callback
// callback触发时，就把对应的FD添加到rdlist就绪列表中
int epoll_ctl(
    int epfd, // epoll实例的句柄
    int op, // 执行的操作，包括ADD、MOD、DEL
    int fd, // 监听的FD
    struct epoll_event *event // 监听的事件类型: 读，写，异常等
);

// 3检查rdlist列表是否为空，不为空则返回就绪的FD数量
int epoll_wait(
    int epfd, // eventpoll实例句柄
    struct epoll_event *events, // 空event数组，接收就绪FD
    int maxevents, // events数组的最大长度
    int timeout // 超时时间
);

特点:

• 基于epoll实例中的红黑树保存监听的FD，理论无上限，增删改查效率很高，性能不会随监听的FD数量增多而下降
• 每个FD只需要执行一次epoll_ctl添加到红黑树，每次epoll_wait无需参数，无需重复拷贝FD到内核
• 内核会将就绪的FD直接拷贝到用户空间的指定位置，用户进程无需遍历所有的FD就能知道就绪FD是谁

时间通知机制

有数据可读时，epoll_wait可以得到通知，但是通知模式有两种:

• LevelTriggered(默认): LT, 当FD有数据可读，会重复通知多次，直到数据处理完成
• EdgeTriggered: ET, 当FD有数据可读，只会通知一次，不管数据是否处理完成

基于epoll的web服务基本流程

信号驱动IO

• 与内核寄建立SIGIO的信号关联并设置回调，内核有FD就绪，就会发出SIGIO信号通知用户，期间用户可以执行其他业务，无需阻塞等待。比非阻塞IO性能好一些
  

问题:

• 如果有大量IO，信号较多SIGIO处理函数不能及时处理，可能导致信号队列溢出
• 内核空间与用户空间频繁信号交互性能较低

异步IO

• 一二阶段都是非阻塞的，但是因为不阻塞，用户进程调用完异步API以后就可以去做其他的事情，内核等到数据拷贝到用户空间后才会递交信号，通知用户进程。
• 但是因为不阻塞，导致用户进程一直接收请求，IO操作较慢，所以必须要做并发访问的限流
  

• 同步和异步需要看第二阶段是同步还是异步的，阻塞IO和非阻塞IO都是同步的，只有异步IO才是异步的

Redis网络模型

Redis是单线程还是多线程的

• 业务处理部分是单线程的
• 如果是整个Redis，则是多线程的
  • 引入了多线程异步处理一些耗时较长的任务，比如异步删除BigKey的命令unlink
  • 在核心网络模型中引入了多线程，进一步提高对于多核CPU的利用率

选择单线程的原因:

1. Redis纯内存操作，执行速度非常快，性能瓶颈是网络延迟而不是执行速度，因此多线程不会带来巨大的性能提升
2. 多线程会导致过多的上下文切换，带来不必要的开销
3. 引入多线程会面临线程安全问题，必然要引入线程锁，实现复杂度更高，性能大打折扣，而且需要考虑老代码的兼容问题

RESP数据类型

1. 单行字符串: 首字节是'+'，后面跟上单行字符串，以CRLF("\r\n")结尾。但是字符串内不能带有\r\n这种(可以理解成是二进制不安全的)
2. 错误: 首字节是'-'，与单行字符串格式一样，只是字符串是异常信息
3. 数值: 首字节是':' ，后面跟数字格式的字符串，以CRLF结尾
4. 多行字符串: 首字节是'$'，表示二进制安全的字符串，最大512MB，不用担心字符串内部出现\r\n
   • 例如: "$5\r\nhello\r\n"，这里的5表示要读五个字符
   • 如果是0表示空字符串"$0\r\n\r\n"
   • 如果是-1，表示不存在"$-1\r\n"
5. 数组: 首字符'*'，后面跟上数组元素个数，再跟上元素，元素类型不限

内存回收

过期策略

• expire对key设置TTL，超时自动释放内存

Redis如何知道一个key是否过期

• Redis的数据库结构体中，有两个dict，一个用来保存key-value，另一个用来记录key-TTL

是不是TTL到期就立即删除了

• 惰性删除，不是在TTL到期后就立即删除了，而是在访问一个key(增删改查)，检查key的存活时间，如果已经过期了，才执行删除
• 周期删除，一个定时任务，周期性抽样部分过期的key，然后执行删除，有两种周期
  1. Redis会设置一个定时任务serverCron()，会按照server.hz的频率来执行过期key的清理，模式为SLOW。(执行频率低，执行时间长)
  2. 每个事件循环前会调用beforeSleep()函数，执行过期key清理，模式为FAST(执行频率高，执行时间短，几十微秒)
     • SLOW模式规则
       • 执行频率受到server.hz影响，默认为10，每秒执行10次，每次100ms
       • 执行清理耗时不超过一次执行周期的25%
       • 逐个遍历DB，逐个遍历DB中的bucket，抽取20个key判断是否过期
       • 如果没有达到时间上限25ms并且过期key比例大于10%，再进行一次抽样，否则结束
     • FAST模式规则
       • 执行频率受到beforeSleep()调用频率影响，但是两次FAST模式间隔不超过2ms
       • 执行清理耗时不超过1ms
       • 逐个遍历DB，逐个遍历DB中的bucket，抽取20个key判断是否过期
       • 如果没有达到时间上限1ms并且过期key比例大于10%，再进行一次抽样，否则结束

淘汰策略

• 当Redis内存使用达到设置的阈值时，Redis主动挑选部分key删除以释放更多内存
• 在处理客户端命令方法processCommand()中尝试做内存淘汰
• 删除key策略：
  1. noeviction: 默认，不淘汰任何key，但是内存满时不允许写入新数据
  2. volatile-ttl：设置了TTLkey，比较key的剩余TTL值，TTL越小越先被淘汰
  3. allkeys-random: 对全体key，随机淘汰，也就是直接从db->dict中随机挑选
  4. volatile-random: 设置了TTL的key，随机淘汰，也就是从db->expires中随机挑选
  5. allkeys-lru：最少最近使用，当前时间减去最后一次访问时间，值越大淘汰优先级越高
  6. volatile-lru:对设置了TTL的key，使用LRU算法进行淘汰
  7. allkeys-lfu: 最少频率使用，会统计每个key的访问频率，值越小淘汰优先级越高
  8. volatile-lfu: 对设置了TTL的key，基于LFU算法进行淘汰

LRU, LFU记录在RedisObject中，LRU以秒为单位记录最近一次访问时间，长度为24bit
LFU的高16位以分钟为单位记录最近一次访问时间，低8位记录逻辑访问次数

• 逻辑访问次数，不是每次key访问都计数，而是运算得到
  • 生成0~1之间随机数R
  • 计算1 / (旧次数 * lfu_log_factor + 1)记录为P，lfu_log_factor默认为10
  • 如果R < P,则计数器+ 1，最大不超过255
  • 访问次数会随时间衰减，距离上一次访问时间间隔lfu_decay_time(分钟，默认1)，计数器-1