Cat Slave

Redis

2018/09/17

Redis/Memcached基于key-value的内存存储系统，非常适合于读多写少的业务场景。而Redis是一个基于多种数据结构的内存存储系统。

事件驱动模型

Redis内部有一个小型的事件驱动，依托于操作系统的I/O多路复用技术（Reactor模型），监听感兴趣的事件。当事件触发时，从而实现回调。

事件驱动数据结构

  • 事件循环结构体
  • 文件事件结构体
  • 时间事件结构体
  • 触发事件结构体

事件循环结构体维护I/O事件表，定时事件表和触发事件表。

// File event structure
typedef struct aeFileEvent {
    int mask; // readable|writable
    aeFileProc *rfileProc; // 回调函数指针
    aeFileProc *wfileProc;
    void *clientData; // 指向redisClient的指针
} aeFileEvent;
// Time event structure
typedef struct aeTimeEvent {
    long id; // time event identifier.
    long when_sec; // seconds
    long when_ms; // milliseconds
    aeTimeProc *timeProc; // 定时回调函数指针
    aeEventFinalizerProc *finalizerProc; // 定时事件清理函数，当删除定时事件的时候会被调用
    void *clientData; // 指向redisClient的指针
    struct aeTimeEvent *next; // 定时事件链表
} aeTimeEvent;
// A fired event
typedef struct aeFiredEvent {
    int fd;
    int mask;
} aeFiredEvent;
// State of an event based program
typedef struct aeEventLoop {
    int maxfd; // highest file descriptor currently registered.
    int setsize; // max number of file descriptors tracked.
    long timeEventNextId; // 记录最大的定时事件id+1
    aeFileEvent *events; // Registered events
    aeFiredEvent *fired; // Fired events
    aeTimeEvent *timeEventHead; // 定时事件表
    int stop; // 事件循环结束标识
    void *apidata; // polling api specific data 不同I/O技术有不同的数据
    aeBeforeSleepProc *beforesleep; // 新的循环前需要执行的操作
} aeEventLoop;

Redis主函数main()中的iniServer()函数的主要作用：

  1. 初始化事件循环中心（EventLoop）
  2. 注册文件I/O事件到EventLoop
  3. 绑定套接字启动监听
  4. 为监听套接字注册读事件

main()的aeMain()函数调用aeProcessEvents()进去事件循环：

  1. 调用aeApiPoll()函数进去监听轮询。底层调用I/O多路复用的select/epoll等函数。
  2. port_getn()函数从指定端口获取事件
  3. 处理事件

事件循环中心

Redis主函数调用iniServer()函数初始化事件循环中心（EventLoop），iniServer函数调用aeCreateEventLoop()初始化。初始化完后再注册事件。

事件注册

文件I/O事件注册在aeCreateFileEvent方法中完成。fd_set封转在了struct aeApiState结构内，aeApiCreate的时候将aeApiState赋值给eventLoop.apidata属性。

typedef struct aeApiState {
    fd_set rfds, wfds;
    fd_set _rfds, _wfds; // 对fd_set的备份
} aeApiState;

事件监听

Redis提供了TCP和Unix域套接字两种工作方式。

套接字注册事件

接收套接字与客户端建立连接后，调用acceptCommonHandler方法：

  1. 建立并保存服务端与客户端的连接信息，存在struct redisClient结构体中；
  2. 为客户端套接字注册读事件，回调函数为readQueryFromClient()：从套接字读取数据，执行相应操作并返回客户端。

Redis事件驱动总结：

  • 初始化事件循环结构体
  • 注册监听套接字的读事件
  • 注册定时事件
  • 进去事件循环
  • 如果监听套接字变为可读，会接收客户端请求，并为对应的套接字注册读事件
  • 如果与客户端连接的套接字变为可读，执行相应的操作

Redis如何提供服务的

Redis服务器为什么能够使用单一进程单线程的方法来处理命令请求，且性能高效呢？是因为其使用了I/O多路复用（multiplexing 时分复用）技术，I/O多路复用技术特点就是可以使用单线程技术来处理多个socket（I/O）流事件。在单个线程通过记录跟踪每一个Socket（I/O流）的状态来同时管理多个I/O流。通过监听多个流事件来选择对应的socket来处理事件。I/O多路复用技术的实现有select、poll、epoll/kqueue等。Redis服务器启动的时候会根据当前操作系统选择最优的解决方案。优先选择epoll，否则select。

启动过程

Redis启动过程，首先初始化服务器配置，创建redisServer结构体，再创建事件循环中心，注册回调函数acceptTcpHandler。最后等待接收请求。

新连接

接收新的请求，Redis对于每一个客户端的连接，都会对应的创建一个结构体struct redisClient。在createClient中，会在事件中心为客户端连接的套接字注册readQueryFromClient函数。

请求处理

readQueryFromClient函数接收客户端的数据，接下来会调用processInputBuffer方法解析命令和processCommand方法执行命令。 执行命令的时候Redis首先根据客户端给的命令在命令表中查找对应的struct redisCommand。Redis在初始化的时候初始化了所有的命令，即多个struct redisCommand。在struct redisCommand中有该命令对应的回调函数。找到命令结构后，则开始执行命令，核心调用是call()。

call方法调用命令的回调函数。

回复客户端

最后，回到setGenericCommand()函数，会调用addReply()。addReply函数会为与客户端连接的套接字注册可写事件，把’ok’添加到客户端的回复缓存中。待再一次回到事件循环的时候，如果这个套接字可写，该回调函数就会被调用，数据就会发送给客户端。

数据结构

字符串

简单动态字符串（simple dynamic string, SDS）,Redis没有直接使用C语言的字符串表示，而是自己构建了一种简单动态字符串抽象类型，作为默认字符串表示。

struct sdshdr {
    int len; // buf数组已使用字节数量
    int free; // buf数组中未使用字节数量
    char buf[]; // 字节数组，用于保存字符串
}

C字符串与SDS之间的区别

  1. C字符串获取自身长度信息需要遍历整个字符串，对每个字符进行计数，复杂度为O(N)。SDS在len属性记录了本身的长度，所以获取一个SDS长度的复杂度为O(1)。

  2. C字符串拼接函数char *strcat(char *dest, const char *src);注意说明：1）函数调用前dest必须初始化；2）strcat需要先找到dest的结尾才能继续追加。可能会发生内存溢出。SDS做了空间判断，所以不会造成缓冲区溢出。

  3. C字符串在执行拼接或截断操作的时候会按需对内存进行一次重分配来扩展或释放内存空间。SDS实现了空间预分配和惰性空间释放两种优化策略避免N次内存重分配。

  4. C字符串里面不能包含空字符，只能保存文本数据，否则会被程序读入误认为字符串结尾。SDS API都以处理二进制的方式来处理数据，所以buf数组被称为字节数组，保存的都是一系列的二进制数据。

列表

链表节点数据结构，双端链表 adlist.h/listNode

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

链表数据结构 adlist.h/list

typedef struct list {
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup)(void *ptr); // 复制链表节点
    void *(*free)(void *ptr); // 释放节点
    int (*match)(void *ptr, void *key);
} list;

Redis链表特性：

  • 双端
  • 无环
  • 带表头表尾指针
  • 带链表长度计数器
  • 多态：使用void *指针来保存节点值，可以保持各种不同类型的值。
  • 集合

字典

Redis字典使用hash表作为底层实现。 hash表数据结构，dict.h/dictht

typedef struct dictht {
    dictEntry **table; // hash table
    unsigned long size; // hash table size
    unsigned long sizemask; // index 
    unsigned long used; // hashed size
} dictht;

table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry的结构的指针。 hash节点数据结构，dict.h/dictEntry

typedef struct dictEntry {
    void *key; // key
    union { // value
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next; // next dictEntry
} dictEntry;

next指针可以将多个hash值相同的键值对连接在一起，以此来解决键冲突（collision）的问题。

字典数据结构， dict.h/dict

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx;
} dict;

type和privdata属性是针对不同类型的键值对，为创建多态字典而设置的；ht属性包含两个数组，每个数组对应一个hash表。字典只使用ht[0]作哈希表，ht[1]在rehash时使用。（rehash为什么要多一个hash来呢？）；rehashidx表示rehash目前进度，没有进行rehash默认值为-1.

总结： 字典使用hash表作为底层实现，每个字典带有两个hash表，一个日常使用，一个rehash使用。 使用MurmurHash2算法来计算键的hash值。 hash使用链地址法来解决键冲突。 在对hash表进行扩展或收缩操作时，程序需要将现有hash内的所有键值对rehash到新的hash表，并且这个rehash不是一次性完成，而是渐进式地完成。（rehash如何保证原子性？）

  • 散列
  • 有序集合

跳跃表

skiplist是一种有序数据结构，每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。查找时间复杂度最优为O(logN)。skiplist作为有序集合的底层实现之一。

skiplist由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，zskiplistNode结构表示skiplist节点，zskiplist结构保存节点信息，比如节点数量、表头表尾节点指针等。

skiplist节点数据结构 redis.h/zskiplistNode

typedef struct zskiplistNode {
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
} zskiplistNode;

整数集合

当一个集合只包含整数值元素，且元素数量不多，Redis就会使用整数集合(intset)来作为集合键的底层实现。

整数集合数据结构，intset.h/intset，保存的类型为int16_t，int32_t或者int64_t的整数值，集合元素不重复。

typedef struct intset {
    uint32_t encoding;
    uint32_t length; // 集合元素数量
    int8_t contents[]; // 集合元素数组，有序、无重复方式保存
} intset;

压缩列表

ziplist是列表键和hash键的底层实现之一。压缩列表是Redis为节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保持一个字节数组或一个整数值。

对象

Redis并不是直接保存上述数据结构的，而是存储在Redis对象里面。Redis对象包含字符串对象、列表对象、哈希对象、集合对象和有序对象这五种类型的对象。一个对象可以包含多种不同的数据结构实现，对象还实现了基于引用计数技术的内存回收机制和对象共享机制。Redis对象还带有访问时间记录信息，可以用于计算数据库键的空转时长，在服务器启用了maxmemory功能下，空转时长较大的键会优先被服务器删除。 redisObject数据结构 server.h/redisObject

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4; // 记录对象所使用的编码（有多个），决定了ptr底层实现的数据结构
    unsigned lru:LRU_BITS;

    int refcount;
    void *ptr; // 指向底层实现数据结构的指针
} robj;

Redis数据库，键总是字符串对象。

字符串对象

字符串对象的编码可以是int、raw或者embstr。embstr专门用于保存短字符串的一种优化方式。 embstr：

  • embstr编码创建字符串对象所需的内存分配次数从raw编码的两次降低为一次。
  • 释放embstr编码的字符串对象只需调用一次内存释放函数，而raw编码需要两次。
  • embstr编码字符串对象的所有数据保存在一块连续的内存里面，所以比raw编码能够更好的利用缓存带来的优势。

列表对象

列表对象的编码可以是ziplist或者linkedlist。 ziplist编码的列表使用压缩列表作为底层实现，每个压缩列表节点（entry）保存了一个列表元素。linkedlist编码的列表使用双端链表作为底层实现，每个双端链表节点（node）都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。

编码转换规则：

  • 列表对象保存的所有字符串元素长度都小于64字节；
  • 列表对象保存的元素数量小于512个； 以上两个条件都满足时使用ziplist，否则都是使用linkedlist。

哈希对象

哈希对象的编码可以是ziplist或者hashtable。 ziplist编码的列表使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表头，然后再将保存了值的压缩列表节点推入到压缩列表表尾，因此：

  • 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；
  • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

集合对象

集合对象的编码可以是intset或者hashtable。

有序集合对象

有序集合的编码可以是ziplist或者skiplist。

内存回收

因为C语言不具备内存自动回收功能，所以Redis在对象中构建了一个引用计数（reference counting）技术实现内存回收机制。每个对象的引用计数信息由redisObject结构的refcount的属性记录。

对象共享

引用计数除了用于内存回收机制之外，还带有对象共享的作用。Redis中，让多个键共享同一个值对象步骤：

  1. 将数据库键的值指针指向一个现有的值对象；
  2. 将被共享的值对象的引用计数+1。

对象的空转时长

redisObject结构的lru属性，记录对象最后一次被命令程序访问的时间。OBJECT IDLETIME命令会输出给定键的空转时长，通过将当前时间减去lru时间计算得出。

如果服务器打开了maxmemory选项，并且内存回收算法maxmemory-policy选项设置为volatile-lru或者allkeys-lru，那么当内存数超过maxmemroy时，空转时长较高的键会优先被服务器释放，从而回收内存。

数据库

服务器状态数据结构 redis.h/redisServer

struct redisServer {
    redisDb * db; // 一个数组，保存服务器中的所有数据库
    int dbnum; // 初始化服务器数量
};

切换数据库，通过修改客户端的redisClient.db指针的引用来实现的，这就是SELECT命令的实现原理。redisClient.db指针指向redisServer.db数组的其中一个元素。

typedef struct redisClient {
    redisDb * db; // 记录客户端当前正在使用的数据库
} redisClient;

Redis是一个键值对（key-value pair）数据库服务器，服务器中的每个数据库都由一个redis.h/redisDb结构表示，redisDb.dict字典保存了数据库中的所有键值对，我们将这个字典称为键空间（key space）。

typedef struct redisDb {
    dict *dict; // 数据库键空间，保存着数据库中的所有键值对

    dict *expires; // 过期字典，保存着键的过期时间
} redisDb;

过期键删除策略：

  • 定时删除：创建一个定时器（timer），在指定过期时间删除键。
  • 惰性删除：获取键的时候判断是否过期，过期则删除。
  • 定期删除：每个一段时间，程序对数据库进行一次检查，删除过期键。

在执行SAVE命令或BGSAVE命令创建一个新的RDB文件时，程序会对数据库中的键进行检查，过滤过期的键。 AOF持久化模式，是当键过期的时候，会向AOF文件追加（append）一条DEL命令，来显示地记录该键已被删除。

事件

Redis服务器是一个事件驱动程序，服务器需要处理以下两类事件：

  • 文件事件（file event）：Redis服务器与客户端的通信会产生相应的文件事件，而服务器则通过监听并处理这些事件来完成一些列网络通信操作。
  • 时间事件（time event）：Redis服务器中的一些操作（比如serverCron函数）需要在给定的时间点执行，而时间事件就是服务器对这类定时操作的抽象。

文件事件 Redis基于Reactor模式开发自己的网络处理器：文件事件处理器（file event handler）：

  • 使用I/O多路复用（multiplexing）程序来同时监听多个套接字，并根据套接字目前执行的任务来关联不同的事件处理器。
  • 当被监听的套接字准备好执行操作时，与操作相对应的文件事件就会产生，文件事件处理器就会调用关联好的处理器来处理事件。

客户端/服务端

服务端数据结构 redis.h/redisServer

struct redisServer {
    list *clients; // 一个链表，维护所有客户端状态。CLIENT命令能够列出目前所有连接到服务器的普通客户端。

    redisClient *lua_client; // Lua脚本的伪客户端。该伪客户端会一直存在直到服务器关闭。
};

客户端

Redis客户端分为两个类型，一种是普通客户端，另一种是伪客户端。普通客户端使用套接字与服务器进行通信，伪客户端主要作用于AOF文件或者Lua脚本，不需要套接字连接。Lua伪客户端在服务器运行周期内一直存在，AOF伪客户端在服务器载入AOF文件时创建，并在载入完成后关闭。

客户端数据结构 redis.h/redisClient

struct redisClient {
    int fd; // 客户端套接字描述符；普通客户端值大于1，伪客户端值为-1.
    robj *name; // 客户端的名字，默认为null。CLIENT setname 命令设置名字。
    int flags; // 记录客户端的角色以及目前所处状态。可以是单/多个标志的二进制域，所有标志定义在redis.h文件里。

    sds querybuf; // 输入缓冲区，保存客户端发送的命令请求。缓冲区大小会根据输入内容动态调整，最大不超过1GB，超过会关闭客户端。

    /* 通过对输入缓冲区querybuf保存的命令进行解析得到的命令参数以及个数进行保存 */
    robj **argv; // 参数数组，每一项是一个字符串对象，argv[0]是要执行的命令，之后项是传给命令的参数
    int argc; // 参数个数

    struct redisCommand *cmd; // 命令实现函数结构，保存命令对应的实现函数。根据argv[0]提供的命令，在命令表字典中查找对应的redisCommand结构。然后使用redisCommand结构，以及argv、arvc属性调用命令实现函数，执行客户端指定的命令。

    /* 输出缓冲区，命令执行结果。发送给客户端后会清空。 */
    char buf[REDIS_REPLY_CHUNK_BYTES]; // 固定大小输出缓冲区16KB，字节数组
    int bufpos; // 保存数组已使用字节数量

    list *reply; // 可变大小输出缓冲区，链表连接多个字符串对象

    int authenticated; // 身份验证 1-通过验证；0-未通过验证。配置文件requirepass启动身份验证功能该属性才有用。


    time_t ctime; // 客户端创建时间
    time_t lastinteraction; // 最后一次交互时间
    time_t obuf_soft_limit_reached_time; // 输出缓冲区容量第一次超过软性限制（soft limit，对输出缓冲区的限制手段）时的时间

} redisClient ;

为了避免客户端的回复过大，占用过多的服务器资源，服务器会时刻检查客户的输出缓冲区的大小，并在缓冲区超出范围时，执行相应的限制操作。服务器使用两种模式来限制客户端的输出缓冲区大小：

  1. 硬性限制（hard limit）：超过该大小立即关闭客户端。
  2. 软性限制（soft limit）：超过该大小会记录该时间作为起始时间；之后如果继续超出，且持续时间超过服务器设定的时长，则将客户端关闭。如果在指定时间内不再超出该大小，则将时间清零。

服务器

  1. 执行命令请求

  2. 定期执行serverCron函数 serverCron函数默认每隔100毫秒执行一次。

Lua脚本

Redis2.6版本开始支持Lua脚本，在服务器嵌入Lua环境，Redis客户端可以使用Lua脚本。

Post Directory