Redis源码分析-存储原理与数据模型

redis源码学习

redis是单线程，分治  ， 内存

wsl2安装

安装 WSL | Microsoft Docs

vscode

开始通过 WSL 使用 VS Code | Microsoft Docs

c/c++基本配置

Get Started with C++ and Windows Subsystem for Linux in Visual Studio Code

Redis是不是单线程？

单线程指什么？

        命令处理在一个线程中

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

单线程的局限：

1 不能有耗时的操作

2 对于redis而言会影响响应的性能

redis有没有io密集型或cpu密集型:

io密集型:

        磁盘io:

                1 redis通过fork子进程的方式，在子进程当中持久化。不会干扰主进程处理相对应的命令。

                2 异步刷盘：当前的这个进程接收到redis命令会引起数据变更的时候，直接在当前这个进程刷盘到aof文件中。

        网络io:

                1 服务多个客户，造成io密集

                2 数据请求或返回数据量比较大

                3 开启io多线程

cpu密集型:

        redis采用key ,value对，value支持丰富的数据结构，如果采用的数据结构不太高效

为什么不采用多线程？

1 加锁复杂，锁粒度不好控制。

2 频繁的cpu上下文切换，抵消多线程的优势。

字典实现

redis DB KV组织是通过字典来实现的；hash结构当节点超过 512 个或者单个字符串长度大于 64 时，hash结构采用字典实现；

 redis有16个db  通过   select + 编号   可以选择db  通常只用一个，最主要的是dict结构

 dicht 是 dic hash table ，最重要的一个数据结构

数据结构

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
typedef struct dictht {
    dictEntry **table;
    unsigned long size;// 数组长度
    unsigned long sizemask; //size-1
    unsigned long used;//当前数组当中包含的元素
} dictht;
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 从0位置开始rehash
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding
    error) 用于安全遍历*/
} dict;

1. 字符串经过hash函数运算得到64位整数；然后对size长度进行取余得到index

2. 相同字符串多次通过hash函数得到相同的64位整数；

3. 整数对2的n次幂取余可以转化为位运算；

4. 抽屉原理 n+1个苹果放在n个抽屉中，苹果最多的那个抽屉至少有2个苹果；64位整数远大于数组的长度，比如数组长度为4，那么1、5、9、1+4n都是映射到1号位数组；所以大概率会发生冲突；

冲突

 负载因子

负载因子 = used / size ； used 是数组存储元素的个数， size 是数组的长度； 负载因子越小，冲突越小；负载因子越大，冲突越大； redis的负载因子是 1 ；

扩容

如果负载因子 > 1 ，则会发生扩容；扩容的规则是翻倍；

如果正在 fork （在rdb、aof复写以及rdb-aof混用情况下）时，会阻止扩容；但是此时若负载因 子 > 5 ，索引效率大大降低， 则马上扩容；这里涉及到写时复制原理；

写时复制

写时复制核心思想：只有在不得不复制数据内容时才去复制数据内容；

 缩容

如果负载因子 < 0.1 ，则会发生缩容；缩容的规则是恰好包含 used 的 2的n次方；

恰好的理解：假如此时数组存储元素个数为9，恰好包含该元素的就是 ，也就是 16；

缩容之后会发生rehash,因为缩容之后size改了

为什么是<0.1而不是 < 1 , 因为如果是 < 1 的话会造成扩缩容频繁，会造成内存操作频繁，造成io密集。

渐进式rehash

当 hashtable 中的元素过多的时候，不能一次性 rehash 到 ht[1] ；这样会长期占用 redis ， 其他命令得不到响应；所以需要使用渐进式 rehash ；

rehash步骤：

将 ht[0] 中的元素重新经过hash函数生成64位整数，再对 ht[1] 长度进行取余，从而映射到 ht[1] ；

渐进式规则：

1. 分治的思想，将 rehash 分到之后的每步增删改查的操作当中；

2. 在定时器中，最大执行一毫秒 rehash ；每次步长 100 个数组槽位；

面试：

处于渐进式rehash阶段时，是否会发生扩容缩容？不会！

scan

提出疑问：扩容的情况 4 scan 0

scan cursor [MATCH pattern] [COUNT count] [TYPE type]

采用高位进位加法的遍历顺序， rehash 后的槽位在遍历顺序上是相邻的；

遍历目标是：从scan开始那刻起redis已经存在的数据进行遍历,不会重复和遗漏 ; 

redis只能保证不遗漏，但是可能会重复。会出现一种重复的情况：在scan过程当中，发生两次缩容的时候，可能会发生数据重复；比如scan快结束了,现在插入大量数据,这些数据肯定遍历不到。扩容和缩容造成映射算法发生改变，但是使用高位进位累加的算法，可以对scan那刻起已经存在的数据的遍历不会出错。

如果项目中用到了scan命令,在server端要自己去重。

rehash源码

  移动1步

 对dict进行增删改查的时候，这里的增删改查对应了每一次客户端的命令操作，不可以一次性全部移动（耗时）

移动1ms

在定时器里调用，定时器每100ms调用一次进行1ms的渐进式rehash。reactor模型，一次事件循环，在网络事件处理完之后在定时事件当中分1ms处理一下

redis单线程为什么这么快？

redis对象编码

expire机制

# 只支持对最外层key过期；
expire key seconds   // 会加入到一个全局的字典当中
pexpire key milliseconds  // 设置key有效时间  毫秒为单位
ttl key              // 查看key还有多少秒过期
pttl key             // 查看key还有多少毫秒过期

惰性删除

分布在每一个命令操作时检查 key 是否过期；若过期删除 key ，再进行命令操作；

定时删除

在定时器中检查库中指定个数（25）个 key;

#define ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 20 /* Keys for each DB loop. */
/*The default effort is 1, and the maximum configurable effort
* is 10. */
config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now);

大KEY

在redis实例中形成了很大的对象，比如一个很大的hash或很大的zset，这样的对象在扩容的时 候，会一次性申请更大的一块内存，这会导致卡顿；如果这个大key被删除，内存会一次性回收， 卡顿现象会再次产生；

如果观察到redis的内存大起大落，极有可能因为大key导致的；

# 每隔0.1秒 执行100条scan命令
redis-cli -h 127.0.0.1 --bigkeys -i 0.1

跳表实现

 理想跳表

redis跳表

 从节约内存出发，redis 考虑牺牲一点时间复杂度让跳表结构更加变扁平，就像二叉堆改成四叉堆 结构；并且redis 还限制了跳表的最高层级为 32 ；

节点数量大于 128 或者有一个字符串长度大于 64 ，则使用跳表（ skiplist ）；

1 多层级有序链表

2 可以二分查找的数据结构

3 最底层包含所有元素

4 范围查询非常方便，通过O(log2n) 的时间复杂度快速找到边界，然后在最底层找到范围内的所有元素

5 增删改查时间复杂度都是O(log2n)

数据结构

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score; // WRN: score 只能是浮点数
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span; // 用于 zrank
    } level[];
} zskiplistNode;
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length; // zcard
    int level; // 最高层
} zskiplist;
typedef struct zset {
    dict *dict; // 帮助快速索引到节点
    zskiplist *zsl;
} zset;

结构图

应用

延时队列优化

前面实现的延时队列有很大的局限性；

1. 时间基准问题；两个应用程序如何保证时间一致；

2. 异步轮询的问题；耗性能，大量无意义的数据请求；

3. 原子性的问题；需要引入lua脚本来执行；

解决：

1. 以redis的时间为基准，redis为数据中心且为单点，时间准确性得到大幅提升；

2. 通过阻塞接口来实现，避免轮询；

3. 修改源码，直接实现原子接口；

思路

# 在redis当中 zset结构 score = time + 5
dq_add "delay_queue" 5 msg
# 如果没有消息pop，则将此连接加入阻塞队列，然后在redis的定时器中 比较 zset 最小的值与当前
time的大小 如果满足条件，通知阻塞队列中的连接；
dq_bpop "delay_queue" timeout 60

redis io多线程

使用io多线程总前提：      多个并发连接，一条连接是不会使用io多线程的

在redis.conf中有一个一个主线程，另外开了3个线程。