redis是不是单线程？

• redis内部是多线程的；
• 但是redis的业务（命令）处理是单线程的；

redis线程

1. redis-server ： 处理命令、网络事件监听（主线程）
2. bio_close_file : 异步关闭大文件
3. bio_aof_fsync : 异步aof刷盘
4. bio_lazy_free : 异步清理大块内存
5. io_tid_* ： io多线程
6. jemalloc_bg_thd ： jemalloc后台线程

命令处理为什么是单线程？

1. 为什么不采用多线程 ：
   1. 加锁复杂、锁粒度不好控制（对象类型stirng、list、hash、set、zset或由多个类型组合而成，加锁复杂）
   2. 频繁的cpu上下文切换，抵消多线程的优势
2. redis中是存在io密集型和cpu密集型操作的：（所以redis的多线程就是为了帮助主线程处理这些操作的，需要学习redis是如何进行优化的）
   1. io密集型（网络io：服务多个客户，造成io密集、数据请求和返回数据量大、开启io多线程；磁盘io：fork进程，子线程持久化、异步刷盘）
   2. cpu密集型
3. 单线程的局限 ：
   1. 不能有耗时操作（cpu运算、io阻塞）
   2. 对于redis而言会影响响应性能

单线程的业务逻辑如果做到高性能？

机制

1. 内存数据库：没有磁盘操作，所以快
2. 数据组织方式：hashtable，查找O(1)快
3. 数据结构高效：（数据结构会根据数据占用量的大小进行切换，数据量小时主要考虑占用空间，数据量大的时候主要考虑时间复杂度）
4. 高效的reactor的网络模型（非阻塞io + io多路复用进行io托管）

数据组织方式

1
2
3
4
5
6
7
8
9
10
11

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* 记录过期时间 */
    dict *blocking_keys;        /* 记录和阻塞有关的key */
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* watch multi exec有关的key */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

• redis所有的数据都是用dict结构组织的

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  typedef struct dictEntry { void *key; // key的真实存储位置 union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; // 因为是链表组织的，所以需要指向下一个的指针 } dictEntry; typedef struct dictht { dictEntry **table; // 指向dictEntry数组的指针 unsigned long size;// 数组长度 unsigned long sizemask; //size-1 unsigned long used;//当前数组当中包含的元素 } dictht; typedef struct dict { dictType *type; void *privdata; dictht ht[2]; // ！！准备两个ht，一个存储老的数组，一个用于扩容的时候存储新的 long rehashidx; /* rehashing not in progress if rehashidx == -1 */ int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) 用于安全遍历*/ } dict;

• redis解决hash冲突：相同key的使用链表进行存储
• 单个ht指向的数组长度为2^n，因为这样 index= hash(kay) % size 可以优化为 index = hash(key)&(2^n-1)
• 一个dict准备两个ht，一个存储老的数组，一个用于扩容的时候存储新的
• 解决查询退化成O（n）的方式
  1. hash函数选择，选择siphash（强随机分布性 + key相近的情况下也保持强随机分布性）
  2. 避免hash冲突激烈程度：
     1. 负载因子 = used（存储的个数） / size（数组长度），redis的负载因子维持 == 1
     2. 负载因子 > 1会发生扩容，规则是数组长度翻倍
     3. 如果负载因子 < 0.1 会发生缩容，缩容的规则是恰好包含used值的2^n，如：used=9，那么缩容后size=2^4=16
• 扩容规则：假设size=4，k1与k2都在0号索引下，扩容后在哪里？因为hash值没变，变得是 index = hash（key）% 2*size，那么只可能在0或4
• scan（分片查询keys）是如何保证遍历结果不被其他节点的插入、删除操作影响的（不遗漏不重复）：遍历规则是index的高位+1往低位进位，index是0123，实际是0213
• 扩容和缩容后会进行rehash
• 渐进式rehash：（优化cpu运算的方式，扩容不会阻塞线程）
  1. 分治的思想，将 rehash 分到之后的每步增删改查的操作当中；（为什么可以这么做？因为scan的数学关系证明，后续的操作不会影响我们查询的结果）
  2. 在定时器中，最大执行一毫秒 rehash ；每次步长 100 个数组槽位；

数据结构高效

• 对象编码：（这些数据可以在redis.conf中配置）

1. zset
   1. skiplist（跳表）：数量大于128或者有一个字符串长度大于64
   2. ziplist（压缩列表）：子节点数量小于等于128且字符串长度小于等于64
2. set
   1. intset（整数数组）：元素都为整数且节点数量小于等于512
   2. dict（字典）：元素有一个不为整数或者数量大于512
3. hash
   1. dict（字典）：节点数量大于512或字符串长度大于64
   2. ziplist（压缩列表）：节点数量小于等于512且字符串长度小于等于64
4. list
   1. quicklist（双向队列）
   2. ziplist（压缩列表）：间接使用
5. string
   1. int：字符串长度小于等于20且能转换成整数
   2. raw：字符串长度大于44
   3. embstr：字符串小于等于44

skiplist跳表结构

• 多层级 有序链表
• 优势：范围查询、有序
• 完美跳表：假设有一个有序链表如下，想要在O(logn)复杂度下快速找到12这个节点
  
  1. 首先构建两个层级，规则是每间隔一个节点就构造上一个层级的节点
  2. 从最顶层先找到10节点，再比较30节点，找到范围，向下一个层级移动
  3. 找到10节点和20节点，再向下一层级移动
  4. 找到12节点
• 完美跳表的问题：每次增加节点需要重新构建跳表结构
• 解决：随机层数，添加上一层级的节点（数学证明可以结果无限趋近于完美跳表）
• 举例：在上述完美跳表结构中增加21这个节点
  1. 先像查找过程一样找到21应该添加的位置，即最底层的20和30之间
  2. 开始随机，redis使用的是1/4的概率，rocksdb也是1/4的概率，也就是1/4的概率在第二层添加一个节点
  3. 假设第二次随机到了添加，那么关注到最顶层，依然是开始随机，也是1/4的概率随机添加（即第三层仅有1/16的概率被添加节点）
• 跳表的特点
  1. 多层级有序链表
  2. 可以二分查找的数据结构
  3. 最底层包含所有的数据
  4. 范围查询非常方便，通过O(log2n)的时间复杂度快速找到边界，然后在最底层找到范围内的所有数据
  5. 增删改查的时间复杂度都是O(log2n)
• redis的跳表还添加了一个dict的附属数据结构，用于快速定位某一个节点，那么redis的跳表的查询和修改可以做到O(1)的复杂度

优化

1. 分治：rehash分摊到每个操作中；定时器
2. 为了数据结构的高效，在空间和复杂度间进行平衡，会切换数据结构

看源码VSCode插件

• c/c++
• clangd
• bear(c语言和makefile生成，c/c++ cmake不需要)

redis io_tid_* IO多线程

• redis流程：read decode compute encode send
• io多线程优化位置：read decode encode send
  

1. 主线程监听客户端发送的数据，触发回调readQueryFromClient
2. 主线程收集命令，放到server.clients_pending_*队列中
3. 主线程通过handleClientsWithPendingReadsUsingThreads将任务分发到不同的IO从线程的专属队列当中
4. IO线程仍然调用的是readQueryFromClient，再调用processInputBuffer解析协议，再调用processPendingCommandsAndResetClient
5. 回到主线程执行指令
6. 主线程收集结果，放到server.clients_pending_*队列中
7. 主线程通过handleClientsWithPendingReadsUsingThreads将任务分发到不同的IO从线程的专属队列当中
8. IO线程调用_writeToClient编码协议再发送出去