读书笔记-Redis设计与实现

calendar May 30, 2020 · 21 min read · 读书笔记 redis  ·
分享到: linkedin copy

文章目录

redis-01

1. 前言

在开发LoRaWAN网络服务器的过程中，除了代码合并与重构外，最多的还是优化缓存。

原版的loraserver项目已经大量地应用了Redis，包括集合、分布式锁、队列、自动超时、事务、发布订阅等。合并代码后进一步使用了位图、哈希，添加了进程中的内存缓存，并移除掉了除历史数据入库外地所有数据库操作。NS性能进一步提升地同时，所有压力都交给了Redis，Redis已经不只是作为简单的KV数据库使用。

以一次节点数据上行为例：

  • 数据收集与去重：使用set收集数据、使用set NX PX命令生成自动超时的分布式锁、分布式锁持有者从set获取全部数据
  • 发布订阅：publish网关层实时数据
  • 获取节点Session：从devAddr为key的集合获取DevEUI列表、根据DevEUI获取Session进行校验
  • B/C类设备锁：为B/C类设备添加自动超时锁，防止并发调度
  • 发布订阅：publish节点协议层实时数据
  • MAC指令处理：获取上次下发的MAC指令、处理MAC指令后删除历史数据
  • 保存节点网关关联关系：以DevEUI为key，保存网关列表供B/C类主动下行和多播主动下行使用
  • 发布订阅：publish节点应用层实时数据
  • 节点应用层处理：可能需要处理多播下行响应
  • 保存一次节点Session
  • MAC指令生成：保存需要节点回复的MAC指令、获取自定义MAC指令
  • 发布订阅：publish节点协议层实时数据
  • 发布订阅：publish网关层实时数据
  • 保存一次节点Session
  • 保存下行数据帧：下行数据帧以token为key保存，设置自动超时
  • 网关回复处理：若网关回复无法入队列，取下行数据帧执行补发

总结下来，处理一包数据可能最少执行16次写入，6次读取，其他部分包括B/C类主动下行、多播下行、数据下发等，也无一例外需要多次读写Redis。因此很难根据业务拆分Redis，到目前只按数据拆分了三个Redis连接池，分别对应无需落盘的数据收集与去重、发布订阅，以及需要做数据落盘和备份的Session存储。

之前为了为了完成优化，把黄健宏的《Redis设计与实现》、《Redis使用手册》都读了好几遍，现在到了需要回顾的时候，复习一下Redis的设计与实现，书本的代码以Redis 3.0为准，下面的笔记使用Redis redis-4.0.14代码。

2. 对象

Redis基于基础数据结构构建了一个对象系统，即我们直接可操作的对象，如集合、字符串、列表、有序集合、哈希等。

Redis的key总是字符串对象，而value可以是所支持的任意一种对象，每个对象初始化时根据原始数据类型和数据大小选择合适的编码，value创建后也可能在操作中自动转换编码。

Redis的命令根据type和encoding实现多态。

可以在 server.h 文件中找到以下定义。

 1/*-----------------------------------------------------------------------------
 2 * Data types
 3 *----------------------------------------------------------------------------*/
 4
 5/* A redis object, that is a type able to hold a string / list / set */
 6
 7/* The actual Redis Object */
 8#define OBJ_STRING 0
 9#define OBJ_LIST 1
10#define OBJ_SET 2
11#define OBJ_ZSET 3
12#define OBJ_HASH 4
13
14/* Objects encoding. Some kind of objects like Strings and Hashes can be
15 * internally represented in multiple ways. The 'encoding' field of the object
16 * is set to one of this fields for this object. */
17#define OBJ_ENCODING_RAW 0     /* Raw representation */
18#define OBJ_ENCODING_INT 1     /* Encoded as integer */
19#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
20#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
21#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
22#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
23#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
24#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
25#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
26#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */

每个对象都由一个redisObject的结构表示，其中

  • type表示对象类型，type key 命令获取到的就是value对应的对象类型
  • encoding记录所使用的编码，即具体使用的基础数据结构类型，可使用 object encoding key 命令获取
  • ptr是指向底层实现数据结构的指针
  • refcount记录引用计数
  • lru记录了对象最后一次被命令程序访问的时间
1typedef struct redisObject {
2    unsigned type:4;
3    unsigned encoding:4;
4    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
5                            * LFU data (least significant 8 bits frequency
6                            * and most significant 16 bits access time). */
7    int refcount;
8    void *ptr;
9} robj;

2.1 字符串对象（OBJ_STRING）

  • OBJ_ENCODING_INT：如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码设置为int
  • OBJ_ENCODING_RAW：如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw
  • OBJ_ENCODING_EMBSTR：如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值，优化短字符串保存

字符串对象是Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

字符串命令：https://redis.io/commands#string

2.2 列表对象（OBJ_LIST）

  • OBJ_ENCODING_ZIPLIST：压缩列表，每个压缩列表节点（entry）保存了一个列表元素
  • OBJ_ENCODING_LINKEDLIST：双端链表，每个双端链表节点（node）都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素

当列表对象保存的所有字符串元素的长度都小于64字节，且列表对象保存的元素数量小于512个时，使用压缩列表，否则使用双端链表。

redis 4.0中引入了quicklist代替了linkedlist，对应编码 OBJ_ENCODING_QUICKLIST

列表命令：https://redis.io/commands#list

2.3 集合（OBJ_SET）

  • OBJ_ENCODING_INTSET：整数集合，集合对象包含的所有元素都被保存在整数集合里面
  • OBJ_ENCODING_HT：字典，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL

当集合对象保存的所有元素都是整数值，且集合对象保存的元素数量不超过512个时，使用整数集合，否则使用字典。

列表命令：https://redis.io/commands#set

2.4 有序集合（OBJ_ZSET）

  • OBJ_ENCODING_ZIPLIST：压缩列表，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score），集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向
  • OBJ_ENCODING_SKIPLIST：跳跃表+字典，使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表
    • 跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素，跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值，支持对有序集合进行范围型操作
    • 字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素，字典的键保存了元素的成员，而字典的值则保存了元素的分值，支持用O（1）复杂度查找给定成员的分值
    • zset结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存

当有序集合保存的元素数量小于128个，且有序集合保存的所有元素成员的长度都小于64字节时，使用压缩列表，否则使用跳跃表。

列表命令：https://redis.io/commands#sorted_set

2.5 哈希对象（OBJ_HASH）

  • OBJ_ENCODING_ZIPLIST：压缩列表，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾，因此：
    • 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后
    • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向
  • OBJ_ENCODING_HT：字典，哈希对象中的每个键值对都使用一个字典键值对来保存
    • 字典的每个键都是一个字符串对象，对象中保存了键值对的键
    • 字典的每个值都是一个字符串对象，对象中保存了键值对的值

当哈希对象保存的所有键值对的键和值的字符串长度都小于64字节，且哈希对象保存的键值对数量小于512个时，使用压缩列表，否则使用字典。

哈希命令：https://redis.io/commands#hash

3. 基础数据结构

3.1 简单动态字符串

每个sds.h/sdshdr结构表示一个SDS值：

  • len记录buf数组中已经使用字节的数量，等于SDS所保存字符串的长度
  • free记录buf数组中未使用字节的数量
  • buf为字节数组，用于保存字符串
 1typedef char *sds;
 2
 3/* Note: sdshdr5 is never used, we just access the flags byte directly.
 4 * However is here to document the layout of type 5 SDS strings. */
 5struct __attribute__ ((__packed__)) sdshdr5 {
 6    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 7    char buf[];
 8};
 9struct __attribute__ ((__packed__)) sdshdr8 {
10    uint8_t len; /* used */
11    uint8_t alloc; /* excluding the header and null terminator */
12    unsigned char flags; /* 3 lsb of type, 5 unused bits */
13    char buf[];
14};
15struct __attribute__ ((__packed__)) sdshdr16 {
16    uint16_t len; /* used */
17    uint16_t alloc; /* excluding the header and null terminator */
18    unsigned char flags; /* 3 lsb of type, 5 unused bits */
19    char buf[];
20};
21struct __attribute__ ((__packed__)) sdshdr32 {
22    uint32_t len; /* used */
23    uint32_t alloc; /* excluding the header and null terminator */
24    unsigned char flags; /* 3 lsb of type, 5 unused bits */
25    char buf[];
26};
27struct __attribute__ ((__packed__)) sdshdr64 {
28    uint64_t len; /* used */
29    uint64_t alloc; /* excluding the header and null terminator */
30    unsigned char flags; /* 3 lsb of type, 5 unused bits */
31    char buf[];
32};

重点

  • Redis只会使用C字符串作为字面量，在大多数情况下使用SDS作为字符串表示
  • SDS相比C字符串有以下优点：
    • 常数复杂度获取字符串长度
    • 杜绝缓冲区溢出
    • 减少修改字符串长度时所需的内存重分配次数
    • 二进制安全
    • 兼容部分C字符串函数

3.2 压缩列表

压缩列表（ziplist）是列表对象、有序集合、哈希对象的底层实现之一，适用于元素数量和元素大小较小的场景。

压缩列表没有明确的结构体定义，而是按二进制格式直接排列，如下

1<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
  • zlbytes：uint32类型，长度4字节，记录整个压缩列表占用的字节数，对压缩列表进行内存重分配或计算zlend的位置时使用
  • ztail：uint32类型，长度4字节，记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量可以无需遍历整个压缩列表获取表位节点的地址
  • zllen：uint16类型，长度2字节，记录了压缩列表包含的节点数量，当该数值小于65535时，表示压缩列表包含的节点的数量，大于65535时，节点真实数量需要遍历整个压缩列表才能计算得出
  • entry：列表节点，长度不定，由节点保存的内容决定
  • zlend：uint8类型，长度1字节，保存特殊值0xFF，标记压缩列表的末端

压缩列表的节点构成如下

1<prevlen> <encoding> <entry-data>
  • prevlen：以字节为单位，记录压缩列表中前一个节点的长度，以便根据当前节点的起始地址来计算出前一个节点的起始地址
  • encoding：记录节点的entry-data属性所保存的数据类型及长度
  • entry-data：保存节点的值，可以是一个字节数组或者整数

重点

  • 压缩列表是一种为节约内存而开发的顺序型数据结构
  • 压缩列表（ziplist）是列表对象、有序集合、哈希对象的底层实现之一
  • 压缩列表可包含多个节点，每个节点可以保存一个字节数组或整数值
  • 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高

3.3 链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

每个链表节点使用一个adlist.h/listNode结构来表示，多个listNode可以通过prev和next指针组成双端链表。

1typedef struct listNode {
2    struct listNode *prev;
3    struct listNode *next;
4    void *value;
5} listNode;

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

1typedef struct list {
2    listNode *head;
3    listNode *tail;
4    void *(*dup)(void *ptr);
5    void (*free)(void *ptr);
6    int (*match)(void *ptr, void *key);
7    unsigned long len;
8} list;

链表实现的特性总结如下：

  • 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）
  • 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
  • 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）
  • 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）
  • 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值

重点

  • 链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等
  • 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表
  • 每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表
  • 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值

Redis 4.0中已经使用quicklist代替linkedlist作为列表对象的底层实现之一，如下：

 1/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 2 * We use bit fields keep the quicklistNode at 32 bytes.
 3 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 4 * encoding: 2 bits, RAW=1, LZF=2.
 5 * container: 2 bits, NONE=1, ZIPLIST=2.
 6 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 7 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 8 * extra: 12 bits, free for future use; pads out the remainder of 32 bits */
 9typedef struct quicklistNode {
10    struct quicklistNode *prev;
11    struct quicklistNode *next;
12    unsigned char *zl;
13    unsigned int sz;             /* ziplist size in bytes */
14    unsigned int count : 16;     /* count of items in ziplist */
15    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
16    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
17    unsigned int recompress : 1; /* was this node previous compressed? */
18    unsigned int attempted_compress : 1; /* node can't compress; too small */
19    unsigned int extra : 10; /* more bits to steal for future usage */
20} quicklistNode;
21
22/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
23 * 'sz' is byte length of 'compressed' field.
24 * 'compressed' is LZF data with total (compressed) length 'sz'
25 * NOTE: uncompressed length is stored in quicklistNode->sz.
26 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
27typedef struct quicklistLZF {
28    unsigned int sz; /* LZF size in bytes*/
29    char compressed[];
30} quicklistLZF;
31
32/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
33 * 'count' is the number of total entries.
34 * 'len' is the number of quicklist nodes.
35 * 'compress' is: -1 if compression disabled, otherwise it's the number
36 *                of quicklistNodes to leave uncompressed at ends of quicklist.
37 * 'fill' is the user-requested (or default) fill factor. */
38typedef struct quicklist {
39    quicklistNode *head;
40    quicklistNode *tail;
41    unsigned long count;        /* total count of all entries in all ziplists */
42    unsigned long len;          /* number of quicklistNodes */
43    int fill : 16;              /* fill factor for individual nodes */
44    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
45} quicklist;

3.4 整数集合

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

每个intset.h/intset结构表示一个整数集合：

1typedef struct intset {
2    uint32_t encoding;
3    uint32_t length;
4    int8_t contents[];
5} intset;
6
7#define INTSET_ENC_INT16 (sizeof(int16_t))
8#define INTSET_ENC_INT32 (sizeof(int32_t))
9#define INTSET_ENC_INT64 (sizeof(int64_t))
  • encoding：编码方式，可选int16、int32、int64
  • length：记录了整数集合包含的元素数量，也即是contents数组的长度
  • contents：整数集合的每个元素都是contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项

整数集合中的所有数组项的编码方式都一致，编码取集合中最大item所需的空间大小，若所有成员都是int16类型，则保持 INTSET_ENC_INT16 编码，若新添加了一个 INTSET_ENC_INT64 类型数据，则整体进行升级，扩展整数集合底层数组的空间大小。

重点

  • 整数集合是集合对象的底层实现之一
  • 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型
  • 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存
  • 整数集合只支持升级操作，不支持降级操作

3.5 字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。

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

 1typedef struct dictEntry {
 2    void *key;
 3    union {
 4        void *val;
 5        uint64_t u64;
 6        int64_t s64;
 7        double d;
 8    } v;
 9    struct dictEntry *next;
10} dictEntry;

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

  • k保存键，一个指向字符串对象的指针
  • v属性保存值，值可以为数值类型或指向字符串对象的指针
  • next是指向下一个哈希表节点的指针，以拉链法解决索引冲突问题
1/* This is our hash table structure. Every dictionary has two of this as we
2 * implement incremental rehashing, for the old to the new table. */
3typedef struct dictht {
4    dictEntry **table;
5    unsigned long size;
6    unsigned long sizemask;
7    unsigned long used;
8} dictht;

哈希表结构由dictht定义：

  • table是一个数组，数组中的每一个元素都是一个指向哈希表节点的指针
  • size记录了哈希表的大小，即table数组的大小
  • used记录哈希表目前已有的节点数量
  • sizemask值固定为size-1，用于与哈希值一起与运算确定table数组索引
 1typedef struct dictType {
 2    uint64_t (*hashFunction)(const void *key);
 3    void *(*keyDup)(void *privdata, const void *key);
 4    void *(*valDup)(void *privdata, const void *obj);
 5    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
 6    void (*keyDestructor)(void *privdata, void *key);
 7    void (*valDestructor)(void *privdata, void *obj);
 8} dictType;
 9
10typedef struct dict {
11    dictType *type;
12    void *privdata;
13    dictht ht[2];
14    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
15    unsigned long iterators; /* number of iterators currently running */
16} dict;

字典结构由dict定义：

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

字典的其他特性如下：

  • 哈希算法：新键值对添加到字典时，首先根据key计算出哈希值和索引值，再根据索引值将包含新键值对的节点添加到指定的索引上，Redis使用MurmurHash2算法来计算键的哈希值
  • 冲突解决：哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，新节点总是添加到链表的表头位置（复杂度为O（1））
  • 重新散列：
    • 装填因子=哈希表已保存节点数量/哈希表大小
    • 重新散列时可能扩展或收缩哈希表，使用ht[1]保存新哈希表，渐进式执行rehash，当ht[0]包含的所有数据都迁移后，释放h[0]，将h[1]设置为h[0]
    • 扩容时（装填因子大于等于1），h[1]的size为第一个大于等于h[0].used*2的2^n
    • 缩容时（装填因子小于0.1），h[1]的size为第一个大于等于h[0].used的2^n
    • 执行BGSAVE或BGREWRITEAOF时，扩容的装填因子上限会取5，避免进行哈希扩容操作
    • 为了避免rehash对服务器性能造成影响，Redis将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，初始化rehashidx为0后，每完成一次rehash，将rehashidx值加1
    • 渐进式rehash过程中，字典同时使用ht[0]和ht[1]，删除、查找和更新会在两个哈希表上进行，新添加的键值对则一律保存到ht[1]，确保ht[0]只减不增

重点

  • 字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希对象
  • Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用
  • 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值
  • 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表
  • 在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的

3.6 跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

1typedef struct zskiplistNode {
2    sds ele;
3    double score;
4    struct zskiplistNode *backward;
5    struct zskiplistLevel {
6        struct zskiplistNode *forward;
7        unsigned int span;
8    } level[];
9} zskiplistNode;

zskiplistNode结构定义了跳跃表节点：

  • ele为成员对象，它指向一个字符串对象，而字符串对象则保存着一个SDS值
  • score为分值，在跳跃表中，节点按各自所保存的分值从小到大排列
  • 跳跃表节点的level数组可以包含多个元素，每个元素包含一个指向其他节点的指针，每创建一个新跳跃表节点时，随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”
    • 每个层都有一个指向表尾方向的前进指针（forward），用于从表头向表尾方向访问节点
    • 跨度（span）记录了前进指针所指的节点与当前节点的距离，跨度越大则两个节点相距越远，指向NULL的所有前进指针的跨度都为0
  • 后退指针（backward）用于从表尾向表头方向访问节点，

在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）。

1typedef struct zskiplist {
2    struct zskiplistNode *header, *tail;
3    unsigned long length;
4    int level;
5} zskiplist;

zskiplist描述了跳跃表的结构：

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

重点

  • 跳跃表是有序集合的底层实现之一
  • Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点
  • 每个跳跃表节点的层高都是1至32之间的随机数
  • 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的
  • 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序

4. 其他

4.1 数据库

  • Redis服务器的所有数据库都保存在redisServer.db数组中，而数据库的数量则由redisServer.dbnum属性保存
  • 客户端通过修改目标数据库指针，让它指向redisServer.db数组中的不同元素来切换不同的数据库
  • 数据库主要由dict和expires两个字典构成，其中dict字典负责保存键值对，而expires字典则负责保存键的过期时间
  • 因为数据库由字典构成，所以对数据库的操作都是建立在字典操作之上的
  • 数据库的键总是一个字符串对象，而值则可以是任意一种Redis对象类型，包括字符串对象、哈希表对象、集合对象、列表对象和有序集合对象，分别对应字符串键、哈希表键、集合键、列表键和有序集合键
  • expires字典的键指向数据库中的某个键，而值则记录了数据库键的过期时间，过期时间是一个以毫秒为单位的UNIX时间戳
  • Redis使用惰性删除和定期删除两种策略来删除过期的键：惰性删除策略只在碰到过期键时才进行删除操作，定期删除策略则每隔一段时间主动查找并删除过期键

4.2 服务器

  • 一个命令请求从发送到完成主要包括以下步骤：
    • 1）客户端将命令请求发送给服务器
    • 2）服务器读取命令请求，并分析出命令参数
    • 3）命令执行器根据参数查找命令的实现函数，然后执行实现函数并得出命令回复
    • 4）服务器将命令回复返回给客户端
  • serverCron函数默认每隔100毫秒执行一次，它的工作主要包括更新服务器状态信息，处理服务器接收的SIGTERM信号，管理客户端资源和数据库状态，检查并执行持久化操作等等
  • 服务器从启动到能够处理客户端的命令请求需要执行以下步骤：
    • 1）初始化服务器状态
    • 2）载入服务器配置
    • 3）初始化服务器数据结构
    • 4）还原数据库状态
    • 5）执行事件循环

4.3 发布与订阅

  • 服务器状态在pubsub_channels字典保存了所有频道的订阅关系：SUBSCRIBE命令负责将客户端和被订阅的频道关联到这个字典里面，而UNSUBSCRIBE命令则负责解除客户端和被退订频道之间的关联
  • 服务器状态在pubsub_patterns链表保存了所有模式的订阅关系：PSUBSCRIBE命令负责将客户端和被订阅的模式记录到这个链表中，而PUNSUBSCRIBE命令则负责移除客户端和被退订模式在链表中的记录
  • PUBLISH命令通过访问pubsub_channels字典来向频道的所有订阅者发送消息，通过访问pubsub_patterns链表来向所有匹配频道的模式的订阅者发送消息
  • PUBSUB命令的三个子命令都是通过读取pubsub_channels字典和pubsub_patterns链表中的信息来实现的

4.4. 事务

  • 事务提供了一种将多个命令打包，然后一次性、有序地执行的机制
  • 多个命令会被入队到事务队列中，然后按先进先出（FIFO）的顺序执行
  • 事务在执行过程中不会被中断，当事务队列中的所有命令都被执行完毕之后，事务才会结束
  • 带有WATCH命令的事务会将客户端和被监视的键在数据库的watched_keys字典中进行关联，当键被修改时，程序会将所有监视被修改键的客户端的REDIS_DIRTY_CAS标志打开
  • 只有在客户端的REDIS_DIRTY_CAS标志未被打开时，服务器才会执行客户端提交的事务，否则的话，服务器将拒绝执行客户端提交的事务
  • Redis的事务总是具有ACID中的原子性、一致性和隔离性，当服务器运行在AOF持久化模式下，并且appendfsync选项的值为always时，事务也具有耐久性