Redis-底层原理

Created at 2019-11-10 Updated at 2020-07-29 Category 中间件 Tag Redis views

高并发和快速的原因

redis 是基于内存的
redis 是单线程的，省去了很多上下文切换线程的时间
redis 使用多路复用技术，可以处理并发的连接。非阻塞 IO 内部实现采用 epoll，采用了 epoll + 自己实现的简单的事件框架。epoll 中的读、写、关闭、连接都转化成了事件，然后利用 epoll 的多路复用特性，绝不在 IO 上浪费一点时间。

为什么单线程

Redis 的性能瓶颈不在于 CPU 资源，而在于内存访问和网络 IO。采用单线程设计的好处是，极大简化了数据结构和算法的实现，不需要各种锁的性能消耗。Redis 通过异步 IO 和 pipeline 等机制来实现高速的并发访问。

其他开源软件采用的模型

Nginx 多进程单线程
Memcached 单进程多线程

单线程的劣势

无法发挥多核 CPU 的性能，不过可以通过在单机开多个 Redis 实例来完善。

过期策略

定期删除 + 惰性删除

定期删除：默认 100ms 随机抽一些设置了过期时间的 key，去检查是否过期，过期了就删除。
惰性删除：等到查询的时候判断是否过期，过期就删除

淘汰策略

noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。
allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。推荐使用。
allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。
volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。这种情况一般是把redis既当缓存，又做持久化存储的时候才用。
volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。
volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。

底层数据结构

SDS 简单动态字符串

SDS 包含三个部分,free,len,buf[]

buf[]：字节数组，用来存放实际字符串
len：记录 buf 数组中已经使用的字节数量
free：记录 buf 数组中未使用的字节的数量

O(1) 获取字符串的长度

直接获取 len。

杜绝缓冲区溢出

C 语言字符串不记录自身长度，所以 strcat 假定用户在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出。

SDS 的 SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。

减少内存分配次数

而在 SDS 中我们在对一个 SDS 初始化的时候会根据实际 buf[] 字符串的长度进行预先空间分配，并且标记为 free。这种方式叫做空间预分配。free 的空间分配的策略是根据 buf[] 大小来决定的，如果 buf[] 大小小于 1MB，则 len 多大 free 就多大；如果 buf[] 大小大于 1MB，则 free 固定设置为 1MB。

如果 SDS 的字符串长度减少，那么 SDS 会将减少的长度存放到 free 中，而不是直接回收，这样可以方便下次如果再次使用，减少内存重新分配。这种策略叫做惰性空间释放。

二进制安全

这是由于 Redis 不依赖一 ‘\0’ 空字符作为结束字符。C 语言之所以不支持就是因为二进制流中会携带 ‘\0’ 字符，导致无法知道字符串真实的结束位置。这就带来了另一个 Redis 特性，就是二进制的安全性。

robj（Redis Object）

类似于 php 的 zvalue

dict 字典

Redis 的一个 database 中所有的 key 到 value 的映射，就是使用一个 dict 来维护的。
一个 Redis hash 结构，当它的 field 较多时，会采用 dict 来存储。
zset 使用 dict 和 skiplist 共同维护

Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表的节点，而每个哈希表节点就保存了字典的一个键值对。

哈希表

typedef struct dictht{
    //哈希表数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。
    dictEntry **table;

    //哈希表大小
    unsigned long size;

    //哈希表大小掩码，用于计算索引值
    //总是等于 size-1
    unsigned long sizemask;

    //该哈希表已有节点的数量，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
    unsigned long userd;
} dictht;

哈希表节点

typedef struct dictEntry{
    //键
    void *key;

    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    //指向下个哈希表节点，形成链表
    //这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突的问题
    struct dictEntry *next;
} dictEntry;

字典

typedef struct dict{
    //类型特定函数
    dictType *type;

    //私有数据
    void *privdata;

    //哈希表
    dictht ht[2];

    //rehash 索引
    //当 rehash 不在进行时，值为 -1
    int rehashidx;
} dict;

type 属性是一个指向 dictType 结构的指针，每个 ditType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。
privdata 属性保存了需要传给那些类型特定函数的可选参数。
ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
rehashidx 记录了 rehash 目前的进度，如果目前没有在进行 rehash ，那么它的值为 -1 。

哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

解决键冲突

Redis 的哈希表使用拉链法解决冲突，每个哈希表都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表。

rehash（重新散列）

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
负载因子 = 哈希表已保存节点数量 / 哈希表大小

为字典的 hash[1] 哈希表分配空间
将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上。
当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后（ht[0] 变为空表），释放 ht[0] ，将 ht[1] 设置为 ht[0] ，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

渐进式 rehash

为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表
在字典中维持一个索引计数器变量 rehashidx，并将它的值设为 0，表示 rehash 工作正式开始
在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将 rehashidx 属性的值增一。
rehash 操作完成后，程序将 rehashidx 属性的值设为 -1。
渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。

因为在进行渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。比如说，要在字典里面查找一个键的话，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找，诸如此类。

另外，在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到 ht[1] 里面，而 ht[0] 则不再进行任何添加操作。这一措施保证了 ht[0] 包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。

链表

链表由 list 结构和 listNode 结构组成。

listNode 结构有 prev，next，value。

list 结构为链表提供了表头指针 head、表尾指针 tail、以及链表长度计数器 len ，而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数：

dup 函数用于复制链表节点所保存的值
free 函数用于释放链表节点所保存的值
match 函数用于对比链表节点所保存的值和另一个输入值是否相等

跳跃表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。zskiplistNode 结构用于表示跳跃表节点，而 zskiplist 结构用于保存跳跃表节点的相关信息。

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

zskiplist 结构

header 指向跳跃表的表头节点
tail 表头节点的层数不计算在内
level 记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）
length 记录跳跃表的长度（表头节点的层数不计算在内）

zskiplistNode 结构

typedef struct zskiplistNode {

    // 后退指针
    // 在程序从表尾向表头遍历时使用
    struct zskiplistNode *backward;

    // 分值
    // 节点按各自所保存的分值从小到大排列
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        // 用于从表头向表尾方向访问节点
        struct zskiplistNode *forward;

        // 跨度
        // 用于记录两个节点之间的距离
        unsigned int span;

    } level[];

} zskiplistNode;

层（level）

level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度。

每次创建一个新的跳跃表节点的时候，程序都根据幂次定律随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的“高度”。一般来说，层的数量越多，访问其他节点的速度就越快。

跨度（span）：用户记录两个几点之间的距离，跨度是用来计算排位的（rank），在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

为什么用跳表不用平衡树

范围查找时用跳表更加方便，平衡树需要中序遍历
平衡树的插入与删除可能引发子树的调整，而跳表只要修改相邻节点的指针，简单又快速
内存占用上，跳表比平衡树更加灵活，一般平衡树一个节点包含两个指针，而跳表的每个节点包含的指针数目平均为 1/(1-p)，具体取决于 p 的大小，Redis 中 p = 1/4。
跳表的算法实现难度更低