Redis是业界普遍应用的缓存组件,研究一个组件框架,最直观的办法就是从应用方的角度出发,将每个步骤考虑一遍,从这些步骤入手去研究往往能够最快的体会到一个组件框架的设计哲学。以Redis为例,每当发起一条请求时,Redis是如何管理网络请求,收到请求后。。。。。

网络模型

Redis是典型的基于事件的驱动模型,单进程,高效的框架总是类似的。网络模型与spp的异步模型几乎一致。 Redis流程上整体分为接受请求处理器、响应处理器和应答处理器三个同步模块,每一个请求都要经历着三个部分。 Redis的网络模型有这所有事件驱动模型的优点,高效低耗。但是面对耗时较长的操作的时候,同样无法处理请求,只能等到事件处理完毕才能响应,比如:删除Redis中全量的key-value,所以了解清楚网络模型有助于在业务中扬长避短,减少长耗时的请求,尽可能多使用一些简单的短耗时请求,发挥异步模型的最大威力。

数据结构

字符串

  • 结构 Redis的字符串是对C语言原始字符串的二次封装,结构如下:
    struct sdshdr{
    //记录buf数组中以使用字节的数量
    //等于字符串的长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组,用于保存字符串
    char buf[];
    };

    可以看出,每当定义一个字符串时,除了保留字符的空间,Redis还分配了额外的空间用于管理属性字段。

  • 内存管理方式 每次修改字符串内容时,首先检查内存空间是否符合要求,否则就扩大2倍;减少字符串内容时,内存并不会立刻回收,而是按需回收。

    字典(哈希)

    字典的底层是hash,涉及到hash,一定会涉及到hash算法,冲突的解决方法,和hash表扩容和缩容

  • hash算法 Redis的hash算法用的是Murmurhash2
  • hash冲突解决方法 链表法解决hash冲突,并且每次产生冲突都把新结点放到表头,不遍历链表,复杂度为O(1)
  • hash扩容和缩容 宏观上看,扩容和缩容都是这几步操作:分配一个新内存块,老数据搬到新内存块上,释放旧内存块。 为了解决一次性copy耗时过多的情况,采用惰性方案:当装载因子触达阈值之后,我们只申请新空间,但并不将老的数据搬移到新散列表中。当有新数据要插入的时候,新散列表中插入数据,并从老的散列表中取一个数据插入新散列表,每次插入都重复此过程,老的散列表中的数据就一点一点全部搬移到新散列表中了。

    整数集合(intSet)

  • 结构
    typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
    } intset;

    变长整数存储,可以保存16/32/64三种长度的整数,底层实现为数组,数组以有序、无重复的方式保存集合元素

    跳跃表

    Redis的有序集合,底层实现是跳跃表,跳跃表又zskiplist和zskiplistNode两个结构构成 跳跃表中结点按照score大小进行排序,当score相同时,结点按照成员对象的大小进行排序

    链表

    Redis的list的键用到了链表 用到的是双向非循环链表,因为list只支持pop和push操作,链表的这两个操作复杂度都是O(1),而且支持左右pop,push,因此使用双向链表

    对象

    上面介绍了Redis用到的数据结构,比如简单动态字符串(SDS)、双向链表、字典、跳表等,Redis并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象, 每种对象都用到了至少一种我们前面所介绍的数据结构。

内存管理

内存回收

Redis使用引用计数实现内存回收机制

typedef struct redisObject {
    // …
    // 引用计数
    int refcount;
    // …
} robj;
  • 在创建一个新的对象时, 引用计数的值会被初始化为 1 ;
  • 当对象被一个新程序使用时, 它的引用计数值会被增加1;
  • 当对象不再被一个程序使用时, 它的引用计数值会被减1;
  • 当对象的引用计数值变为 0 时, 对象所占用的内存会被释放。

    内存共享

    命令1:SET keya 100 命令2:SET keyb 100 Redis的做法:创建一个包含整数100的字符串对象,将keya的指针指向此对象 执行命令2时,将keyb的指针指向此对象,并将被共享的值对象的引用计数+1 内存共享机制可以节约内存。

目前来说, Redis 会在初始化服务器时, 创建一万个字符串对象, 这些对象包含了从 0 到 9999 的所有整数值, 当服务器需要用到值为 0 到 9999 的字符串对象时, 服务器就会使用这些共享对象, 而不是新创建对象。

例如执行以下代码:

redis> SET A 100
OK

redis> OBJECT REFCOUNT A  //此命令可以查看键A的值对象的引用计数
(integer) 2

可以看到值对象的引用计数为2,说明在创建A的值对象时,已经创建过了 Redis只对包含整数值的字符串对象共享,因为在验证已存在的对象和要创建的对象是否完全相同时,对象越复杂,验证的时间复杂度越高,因此受CPU的限制,只对包含整数值的字符串对象共享