Redis 5 设计与源码分析

Redis 5.0 新特性

新增Streams数据类型，这是 Redis 5.0 最重要的改进之一。可以把Streams当作消息队列。
新的模块API、定时器、集群及字典。
RDB中持久化存储LFU和LRU的信息。
将集群管理功能完全用C语言集成到redis-cli中，Redis 3.x 和 Redis4.x 的集群管理是通过Ruby脚本实现的。
有序集合新增命令ZPOPMIN/ZPOPMAX。
改进HyperLogLog的实现。
新增Client Unblock和Client ID。
新增LOLWUT命令。
Redis主从复制中的从不再称为Slave，改称Replicas。
Redis 5.0引入动态哈希，以平衡CPU的使用率和相应性能，可以通过配置文件进行配置。Redis 5.0默认使用动态哈希。
Redis核心代码进行了部分重构和优化。

简单动态字符串

（1）长度小于 32 的短字符串

struct __attribute__ ((__packed__))sdshdr5 {
    unsigned char flags; // 低 3 位存储类型，高 5 位存储长度
    char buf[]; // 柔性数组
}

结构如下：

sdshdr5

（2）长度大于 31 的字符串

此处仅展示一个示例：

struct __attribute__ ((__packed__))sdshdr8 {
    uint8_t len; // 已使用长度
    uint8_t alloc; // 已分配的字节总长度
    unsigned char flags; // 低 3 位存储类型
    char buf[]; // 柔性数组
}

SDS 读操作的复杂度多为O(1)，直接读取成员变量；涉及修改的写操作，则可能会触发扩容。

跳跃表

对于有序集合的底层实现，我们可以使用数组、链表、平衡树等结构。数组不便于元素的插入和删除；链表的查询效率低，需要遍历所有元素；平衡树或者红黑树等结构虽然效率高但实现复杂。Redis采用了一种新型的数据结构——跳跃表。跳跃表的效率堪比红黑树，然而其实现却远比红黑树简单。

实现跳跃表

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zkiplist;

在Redis中，跳跃表主要应用于有序集合的底层实现（有序集合的另一种实现方式为压缩列表）。zset插入第一个元素时，会判断下面两种条件：

zset-max-ziplist-entries的值是否等于0；
zset-max-ziplist-value小于要插入元素的字符串长度。

满足任一条件Redis就会采用跳跃表作为底层实现，否则采用压缩列表作为底层实现方式。一般情况下，不会将zset-max-ziplist-entries配置成0，元素的字符串长度也不会太长，所以在创建有序集合时，默认使用压缩列表的底层实现。

zset新插入元素时，会判断以下两种条件：

zset中元素个数大于zset_max_ziplist_entries；
插入元素的字符串长度大于zset_max_ziplist_value。

当满足任一条件时，Redis便会将zset的底层实现由压缩列表转为跳跃表。值得注意的是，zset在转为跳跃表之后，即使元素被逐渐删除，也不会重新转为压缩列表。

跳跃表的原理简单，其查询、插入、删除的平均复杂度都为O(logN)。

压缩列表

压缩列表ziplist本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。

Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储结构。

压缩列表

元素的结构示意图：

压缩列表单个元素

字典

Redis自带客户端就是使用times 33散列函数来计算字符串的Hash值，Redis服务端的Hash函数使用的是siphash算法，主要功能与客户端Hash函数类似，其优点是针对有规律的键计算出来的Hash值也具有强随机分布性，但算法较为复杂。

字典结构

整数集合

整数集合（intset）是一个有序的、存储整型数据的结构。

127.0.0.1:6379> sadd testset 1 2 1 6
(integer) 4
127.0.0.1:6379> object encoding testset
"intset"

intset

intset是按从小到大有序排列的，所以通过防御性判断之后使用二分法进行元素的查找。

quicklist的实现

quicklist是Redis底层最重要的数据结构之一，它是Redis对外提供的6种基本数据结构中List的底层实现，在Redis 3.2版本中引入，能够在时间效率和空间效率间实现较好的折中。quicklist由List和ziplist结合而成。quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。

intset

Stream

Redis Stream的结构如图所示，它主要由消息、生产者、消费者、消费组4部分组成。

Stream

xadd mystream1 * name zk age 20

mystream1为Stream的名称；*代表由Redis自行生成消息ID;name、age为该消息的field; zk、20则为对应的field的值。

每个消息都由以下两部分组成。

每个消息有唯一的消息ID，消息ID严格递增。
消息内容由多个field-value对组成。