为什么快

1. Redis是纯内存数据库，不需要读取磁盘操作，所以速度快。
2. Redis使用的是非阻塞IO模式，IO多路复用，主要采用epoll，事件驱动方式，使用了单线程来轮询文件描述符，将数据库的开、关、读、写都转换成了事件，减少了线程切换时上下文的切换和竞争。
3. Redis采用了单线程的方式，减少了线程的上下文切换和竞争。
4. 高效的数据结构，Redis全程使用hash结构，读取速度快，还有一些特殊的数据结构，对数据存储进行了优化，如：
5. 压缩表，对短数据进行压缩存储；
6. 跳表，使用有序的数据结构加快读取的速度；
7. SDS利用空间换时间预分配空间。

数据类型结构

参见：https://juejin.cn/post/6844903936520880135

简单动态字符串（SDS）

Redis是用C语言写的，但是Redis并没有使用C的字符串表示（C是字符串是以\0空字符结尾的字符数组），而是自己构建了一种简单动态字符串（simple dynamic string，SDS）的抽象类型，并作为Redis的默认字符串表示

SDS的定义

// 3.0struct sdshdr {    // 记录buf数组中已使用字节的数量，即SDS所保存字符串的长度    unsigned int len;    // 记录buf数据中未使用的字节数量    unsigned int free;    // 字节数组，用于保存字符串    char buf[];};

3.2版本之后，会根据字符串的长度来选择对应的数据结构

static inline char sdsReqType(size_t string_size) {    if (string_size < 1<<5)  // 32        return SDS_TYPE_5;    if (string_size < 1<<8)  // 256        return SDS_TYPE_8;    if (string_size < 1<<16)   // 65536 64k        return SDS_TYPE_16;    if (string_size < 1ll<<32)  // 4294967296 4G        return SDS_TYPE_32;    return SDS_TYPE_64;}

下面以3.2版本的sdshdr8看一个示例

• len：记录当前已使用的字节数（不包括'len：记录当前已使用的字节数（不包括'\0'），获取SDS长度的复杂度为O(1)'），获取SDS长度的复杂度为O(1)
• alloc：记录当前字节数组总共分配的字节数量（不包括'alloc：记录当前字节数组总共分配的字节数量（不包括'\0'）'）
• flags：标记当前字节数组的属性，是sdshdr8还是sdshdr16等，flags值的定义可以看下面代码
• buf：字节数组，用于保存字符串，包括结尾空白字符'buf：字节数组，用于保存字符串，包括结尾空白字符'\0''

SDS与C字符串的区别

1. 常数复杂度获取字符串长度

C字符串不记录字符串长度，获取长度必须遍历整个字符串，复杂度为O(N)；而SDS结构中本身就有记录字符串长度的len属性，所有复杂度为O(1)。Redis将获取字符串长度所需的复杂度从O(N)降到了O(1)，确保获取字符串长度的工作不会成为Redis的性能瓶颈

2. 杜绝缓冲区溢出，减少修改字符串时带来的内存重分配次数

C字符串不记录自身的长度，每次增长或缩短一个字符串，都要对底层的字符数组进行一次内存重分配操作。如果是拼接append操作之前没有通过内存重分配来扩展底层数据的空间大小，就会产生缓存区溢出；如果是截断trim操作之后没有通过内存重分配来释放不再使用的空间，就会产生内存泄漏

而SDS通过未使用空间解除了字符串长度和底层数据长度的关联，3.0版本是用free属性记录未使用空间，3.2版本则是alloc属性记录总的分配字节数量。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化的空间分配策略，解决了字符串拼接和截取的空间问题

3. 二进制安全

C字符串中的字符必须符合某种编码，除了字符串的末尾，字符串里面是不能包含空字符的，否则会被认为是字符串结尾，这些限制了C字符串只能保存文本数据，而不能保存像图片这样的二进制数据

而SDS的API都会以处理二进制的方式来处理存放在buf数组里的数据，不会对里面的数据做任何的限制。SDS使用len属性的值来判断字符串是否结束，而不是空字符

4. 兼容部分C字符串函数

虽然SDS的API是二进制安全的，但还是像C字符串一样以空字符结尾，目的是为了让保存文本数据的SDS可以重用一部分C字符串的函数

链表

链表是一种比较常见的数据结构了，特点是易于插入和删除、内存利用率高、且可以灵活调整链表长度，但随机访问困难。许多高级编程语言都内置了链表的实现，但是C语言并没有实现链表，所以Redis实现了自己的链表数据结构

链表在Redis中应用的非常广，列表（List）的底层实现就是链表。此外，Redis的发布与订阅、慢查询、监视器等功能也用到了链表

链表节点和链表的定义

typedef struct listNode {    // 前置节点    struct listNode *prev;    // 后置节点    struct listNode *next;    // 节点值    void *value;} listNode;

typedef struct list {    // 链表头节点    listNode *head;    // 链表尾节点    listNode *tail;    // 节点值复制函数    void *(*dup)(void *ptr);    // 节点值释放函数    void (*free)(void *ptr);    // 节点值对比函数    int (*match)(void *ptr, void *key);    // 链表所包含的节点数量    unsigned long len;} list;

每个节点listNode可以通过prev和next指针分布指向前一个节点和后一个节点组成双端链表，同时每个链表还会有一个list结构为链表提供表头指针head、表尾指针tail、以及链表长度计数器len，还有三个用于实现多态链表的类型特定函数

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

特性

• 双端链表：带有指向前置节点和后置节点的指针，获取这两个节点的复杂度为O(1)
• 无环：表头节点的prev和表尾节点的next都指向NULL，对链表的访问以NULL结束
• 链表长度计数器：带有len属性，获取链表长度的复杂度为O(1)
• 多态：链表节点使用 void*指针保存节点值，可以保存不同类型的值

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。字典中的每一个键都是唯一的，可以通过键查找与之关联的值，并对其修改或删除。

Redis的键值对存储就是用字典实现的，散列（Hash）的底层实现之一也是字典。

字典的定义实现

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

哈希表结构定义，dict.h/dictht

typedef struct dictht {    // 哈希表数组    dictEntry **table;    // 哈希表大小    unsigned long size;    // 哈希表大小掩码，用于计算索引值，等于size-1    unsigned long sizemask;    // 哈希表已有节点的数量    unsigned long used;} dictht;

哈希表是由数组table组成，table中每个元素都是指向dict.h/dictEntry结构的指针，哈希表节点的定义如下。

typedef struct dictEntry {    // 键    void *key;    // 值    union {        void *val;        uint64_t u64;        int64_t s64;        double d;    } v;    // 指向下一个哈希表节点，形成链表    struct dictEntry *next;} dictEntry;

其中key是我们的键；v是键值，可以是一个指针，也可以是整数或浮点数；next属性是指向下一个哈希表节点的指针，可以让多个哈希值相同的键值对形成链表，解决键冲突问题

最后就是我们的字典结构，dict.h/dict

typedef struct dict {    // 和类型相关的处理函数    dictType *type;    // 私有数据    void *privdata;    // 哈希表    dictht ht[2];    // rehash 索引，当rehash不再进行时，值为-1    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    // 迭代器数量    unsigned long iterators; /* number of iterators currently running */} dict;

type属性和privdata属性是针对不同类型的键值对，用于创建多类型的字典，type是指向dictType结构的指针，privdata则保存需要传给类型特定函数的可选参数，关于dictType结构和类型特定函数可以看下面代码

typedef struct dictType {    // 计算哈希值的行数    uint64_t (*hashFunction)(const void *key);    // 复制键的函数    void *(*keyDup)(void *privdata, const void *key);    // 复制值的函数    void *(*valDup)(void *privdata, const void *obj);    // 对比键的函数    int (*keyCompare)(void *privdata, const void *key1, const void *key2);    // 销毁键的函数    void (*keyDestructor)(void *privdata, void *key);    // 销毁值的函数    void (*valDestructor)(void *privdata, void *obj);} dictType;

dict的ht属性是两个元素的数组，包含两个dictht哈希表，一般字典只使用ht[0]哈希表，ht[1]哈希表会在对ht[0]哈希表进行rehash（重哈希）的时候使用，即当哈希表的键值对数量超过负载数量过多的时候，会将键值对迁移到ht[1]上

rehashidx也是跟rehash相关的，rehash的操作不是瞬间完成的，rehashidx记录着rehash的进度，如果目前没有在进行rehash，它的值为-1

结合上面的几个结构，我们来看一下字典的结构图（没有在进行rehash）

在这里，哈希算法和rehash(重新散列)的操作不再详细说明，有机会以后单独介绍

当一个新的键值对要添加到字典中时，会根据键值对的键计算出哈希值和索引值，根据索引值放到对应的哈希表上，即如果索引值为0，则放到ht[0]哈希表上。当有两个或多个的键分配到了哈希表数组上的同一个索引时，就发生了键冲突的问题，哈希表使用链地址法来解决，即使用哈希表节点的next指针，将同一个索引上的多个节点连接起来。当哈希表的键值对太多或太少，就需要对哈希表进行扩展和收缩，通过rehash(重新散列)来执行

rehash

参见：https://tech.meituan.com/2018/07/27/redis-rehash-practice-optimization.html

跳跃表

一个普通的单链表查询一个元素的时间复杂度为O(N)，即便该单链表是有序的。使用跳跃表（SkipList）是来解决查找问题的，它是一种有序的数据结构，不属于平衡树结构，也不属于Hash结构，它通过在每个节点维持多个指向其他节点的指针，而达到快速访问节点的目的

跳跃表是有序集合（Sorted Set）的底层实现之一，如果有序集合包含的元素比较多，或者元素的成员是比较长的字符串时，Redis会使用跳跃表做有序集合的底层实现

跳跃表的定义

跳跃表其实可以把它理解为多层的链表，它有如下的性质

• 多层的结构组成，每层是一个有序的链表
• 最底层（level 1）的链表包含所有的元素
• 跳跃表的查找次数近似于层数，时间复杂度为O(logn)，插入、删除也为 O(logn)
• 跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)

那么如何来理解跳跃表呢，我们从最底层的包含所有元素的链表开始，给定如下的链表

然后我们每隔一个元素，把它放到上一层的链表当中，这里我把它叫做上浮（注意，科学的办法是抛硬币的方式，来决定元素是否上浮到上一层链表，我这里先简单每隔一个元素上浮到上一层链表，便于理解），操作完成之后的结构如下

查找元素的方法是这样，从上层开始查找，大数向右找到头，小数向左找到头，例如我要查找17，查询的顺序是：13 -> 46 -> 22 -> 17；如果是查找35，则是 13 -> 46 -> 22 -> 46 -> 35；如果是54，则是 13 -> 46 -> 54

上面是查找元素，如果是添加元素，是通过抛硬币的方式来决定该元素会出现到多少层，也就是说它会有 1/2的概率出现第二层、1/4 的概率出现在第三层......

跳跃表节点的删除和添加都是不可预测的，很难保证跳表的索引是始终均匀的，抛硬币的方式可以让大体上是趋于均匀的

假设我们已经有了上述例子的一个跳跃表了，现在往里面添加一个元素18，通过抛硬币的方式来决定它会出现的层数，是正面就继续，反面就停止，假如我抛了2次硬币，第一次为正面，第二次为反面

跳跃表的删除很简单，只要先找到要删除的节点，然后顺藤摸瓜删除每一层相同的节点就好了

跳跃表维持结构平衡的成本是比较低的，完全是依靠随机，相比二叉查找树，在多次插入删除后，需要Rebalance来重新调整结构平衡

压缩列表

参考：https://www.cnblogs.com/chenchuxin/p/14199444.html

压缩列表 ziplist 在 redis 中的应用也非常广泛，它是我们常用的 zset ，list 和 hash 结构的底层实现之一。当我们的容器对象的元素个数小于一定条件时，redis 会使用 ziplist 的方式储存，来减少内存的使用。

为什么要在元素较少的时候使用 ziplist ？

因为 redis 中的集合容器中，很多情况都用到了链表的实现，元素和元素之间通过储存的关联指针有序的串联起来，但是这样的指针往往是 随机I/O，也就是指针地址是不连续的（分布不均匀）。而我们的 ziplist 它本身是一块连续的内存块，所以它的读写是 顺序I/O，从底层的磁盘读写来说，顺序I/O 的效率肯定是高于 随机I/O 。你可能会问了，那为什么不都用 顺序I/O 的 ziplist 代替 随机I/O 呢，因为 ziplist 是连续内存，当你元素数量多了，意味着当你创建和扩展的时候需要操作更多的内存，所以 ziplist 针对元素少的时候才能提升效率。

压缩列表结构

压缩列表节点结构

节点的结构一般是：<prevlen> <encoding> <entry-data>

• prevlen：前一个 entry 的大小，用于反向遍历。
• encoding：编码，由于 ziplist 就是用来节省空间的，所以 ziplist 有多种编码，用来表示不同长度的字符串或整数。
• data：用于存储 entry 真实的数据；

prevlen

prevlen：表示该节点前一个节点的字节长度。 prevlen的长度可能是1个字节，也可能是5个字节。

当前一个节点的长度小于254个字节时， prevlen的长度为1个字节，直接存储前一个节点的字节长度；

当前一个节点的长度大于或等于254个字节时， prevlen的长度为5个字节，其中的第一个字节被设置为0xFE，随后的四个字节保存前一个节点的字节长度。

可以通过 prevlen和压缩列表结构中的xltail逆序遍历压缩列表。

encoding

encoding表示该节点中保存数据的类型和长度。

当encoding的最高位以00开头时，表示最大长度为63的短字符串，此时encoding的长度为1个字节，其后面6个位表示字符串的字节长度；

当encoding的最高位以01开头时，表示最大长度为16383的中等长度的字符串，此时encoding的长度为2个字节，其后面14个位表示字符串的字节长度；

当encoding的最高位以10开头时，表示最大长度为4294967295的特长的字符串，此时encoding的长度为5个字节，其后面4个字节表示字符串的字节长度；

当encoding的最高位以11开头时，表示整数值，此时encoding的长度为1个字节，其后面6个位表示整数值的类型和长度。

content

content用于存储节点的值，节点的值可以是一个字节数组，也可以是正数，其类型和长度由encoding决定。

连锁更新

通过上面的分析，我们知道：

• 前个节点的长度小于 254 的时候，用 1 个字节保存 prevlen
• 前个字节的长度大于等于 254 的时候，用 5 个字节保存 prevlen

现在我们来考虑一种情况：假设一个压缩列表中，有多个长度 250 ~ 253 的节点，假设是 entry1 ~ entryN。 因为都是小于 254，所以都是用 1 个字节保存 prevlen。 如果此时，在压缩列表最前面，插入一个 254 长度的节点，此时它的长度需要 5 个字节。 也就是说 entry1.prevlen 会从 1 个字节变为 5 个字节，因为 prevlen 变长，entry1 的长度超过 254 了。 这下就糟糕了，entry2.prevlen 也会因为 entry1 而变长，entry2 长度也会超过 254 了。 然后接着 entry3 也会连锁更新。。。直到节点不超过 254， 噩梦终止。。。

这种由于一个节点的增删，后续节点变长而导致的连续重新分配内存的现象，就是连锁更新。最坏情况下，会导致整个压缩列表的所有节点都重新分配内存。

每次分配空间的最坏时间复杂度是 O(n)，所以连锁更新的最坏时间复杂度高达 O(n*n)!

虽然说，连锁更新的时间复杂度高，但是它造成大的性能影响的概率很低，原因如下：

1. 压缩列表中需要需要有连续多个长度刚好为 250 ~ 253 的节点，才有可能发生连锁更新。实际上，这种情况并不多见。
2. 即使有连续多个长度刚好为 250 ~ 253 的节点，连续的个数也不多，不会对性能造成很大影响

因此，压缩列表插入操作，平均复杂度还是 O(n).

IO多路复用

参考：

https://blog.csdn.net/a972627721/article/details/127835650

https://xie.infoq.cn/article/b3816e9fe3ac77684b4f29348

概念

1、多进程

对于并发情况，假如一个进程不行，那搞多个进程不就可以同时处理多个客户端连接了么？

多进程这种方式的确可以解决了服务器在同一时间能处理多个客户端连接请求的问题，但是仍存在一些缺点：

• fork()等系统调用会使得进程上下文进行切换，效率较低
• 进程创建的数量随着连接请求的增加而增加。比如 10w 个请求，就要 fork 10w 个进程，开销太大
• 进程与进程之间的地址空间是私有、独立的，使得进程之间的数据共享变得困难

2、多线程

线程是运行在进程上下文的逻辑流，一个进程可以包含多个线程，多个线程运行在同一进程上下文中，因此可共享这个进程地址空间的所有内容，解决了进程与进程之间通信难的问题。

同时，由于一个线程的上下文要比一个进程的上下文小得多，所以线程的上下文切换，要比进程的上下文切换效率高得多。

3、IO 多路复用

简单理解就是：一个服务端进程可以同时处理多个套接字描述符。

• 多路：多个客户端连接（连接就是套接字描述符）
• 复用：使用单进程就能够实现同时处理多个客户端的连接

以上是通过增加进程和线程的数量来并发处理多个套接字，免不了上下文切换的开销，而 IO 多路复用只需要一个进程就能够处理多个套接字，从而解决了上下文切换的问题。

其发展可以分 select->poll→epoll 三个阶段来描述。

理解select/poll/epoll

select

select是Linux中最早的I/O多路复用实现方案，并且windows操作系统上只支持select。这就是为啥window发挥不出redis的最大性能的一个原因。

select函数执行流程

1. 用户空间创建fd_set，把需要监听的位置置1，比如 1，2，5
2. 用户空间拷贝fd_set（注册的事件集合）到内核空间
3. 内核遍历所有fd文件，并将当前进程挂到每个fd的等待队列中，当某个fd文件设备收到消息后，会唤醒设备等待队列上睡眠的进程，那么当前进程就会被唤醒
4. 内核如果遍历完所有的fd没有I/O事件，则当前进程进入睡眠，当有某个fd文件有I/O事件或当前进程睡眠超时后，当前进程重新唤醒再次遍历所有fd文件
5. 内核有事件产生，会把fd_set中有事件的位置保留为1，没有事件的位置擦除为0.
6. 内核拷贝fd_set给用户空间
7. 用户空间线程被唤醒，遍历fd_set为1的位置，确认是哪些fd有就绪事件，然后开始处理
8. 用户空间处理完事件，再一次将要监听的fd_set设置为1，重复之前的监听动作

根据上面可以很清楚的看出整个执行流程在用户空间和内核空间的切换。

select函数的缺点

• 单个进程所打开的FD是有限制的，通过 FD_SETSIZE 设置，默认1024
• 每次调用 select，都需要把 fd 集合从用户态拷贝到内核态，这个开销在 fd 很多时会很大
• 每次调用select都需要将进程加入到所有监视socket的等待队列，每次唤醒都需要从每个队列中移除
• select函数在每次调用之前都要对参数进行重新设定，这样做比较麻烦，而且会降低性能
• 进程被唤醒后，程序并不知道哪些socket收到数据，还需要遍历一次

poll

poll本质上和select没有区别，它将用户传入的数据拷贝到内核空间，然后查询每个fd对应的设备状态， 但是它没有最大连接数的限制，原因是它是基于链表来存储的

poll运行流程：

①创建pollfd数组， 向其中添加关注的fd信息，数组大小自定义

②调用poll函数，将pollfd数组拷贝到内核空间，转链表存储，无上限

③内核遍历fd,判断是否就绪

④数据就绪或超时后，拷贝pollfd数组到用户空间，返回就绪fd数量n

⑤用户进程判断n是否大于0

⑥大于0则遍历pollfd数组,找到就绪的fd

与select对比

• select模式中的fd_ set大小固定为1024,而pollfd在内核中采用链表，理论上无上限.
• 监听FD越多，每次遍历消耗时间也越久，性能反而会下降
• poll还是没有解决需要遍历判断fd事件的方式，只是增加了监听数量，在fd很多的情况下，性能下降的更加严重

epoll

epoll可以理解为event pool，不同与select、poll的轮询机制，epoll采用的是事件驱动机制，每个fd上有注册有回调函数，当网卡接收到数据时会回调该函数，同时将该fd的引用放入rdlist就绪列表中。

当调用epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可。如果rdlist不为空，则把发生的事件复制到用户态，同时将事件数量返回给用户。

他主要有三个函数，epoll的执行流程

1. 调用epoll_create创建一个eventpoll结构体，这个结构体有一个监听事件红黑色，和一个就绪链表（这个链表只会存放就绪fd，避免我们无效的遍历所有fd）

2. 调用epoll_ctl向eventpoll中注册一个监听的fd，并且注册上fd对应事件的回调函数。

3. 调用epoll_wait开始阻塞等待事件到来
4. 内核将监听到的事件添加一份到就绪队列list_head

5. 内核唤醒用户线程，并将就绪链表拷贝到用户空间

6. 用户应用只需要关心这些就绪的fd事件，直接取出结构体里关联的回调函数进行回调即可处理事件。

对应的redis的server执行流程

1. 调用epoll_create创建一个eventpoll结构体
2. 调用epoll_ctl向eventpoll中注册一个监听连接的serverSocket，并关联上处理accept事件的函数
3. 调用epoll_wait阻塞等待fd事件（等待客户端连接）
4. 用户程序被唤醒，事件到来（现在只有连接事件）。根据生成的客户端的FD，调用epoll_ctl注册一个监听，并且关联上处理read事件的函数和处理write事件的函数。
5. 继续调用epoll_wait阻塞等待fd事件（等待客户端连接或客户端命令执行请求）
6. 用户程序被唤醒，事件到来（连接事件或者命令执行请求），假设是客户端执行请求事件，根据客户端的fd对应的read事件直接调用绑定的回调函数来处理，将结果再写回到fd缓存中。
7. 继续调用epoll_wait等待accept，read，write事件。

epoll优点

• EPOLL支持的最大文件描述符上限是整个系统最大可打开的文件数目, 1G内存理论上最大创建10万个文件描述符
• 每个文件描述符上都有一个callback函数，当socket有事件发生时会回调这个函数将该fd的引用添加到就绪列表中，select和poll并不会明确指出是哪些文件描述符就绪，而epoll会。造成的区别就是，系统调用返回后，调用select和poll的程序需要遍历监听的整个文件描述符找到是谁处于就绪，而epoll则直接处理即可
• select、poll采用轮询的方式来检查文件描述符是否处于就绪态，而epoll采用回调机制。造成的结果就是，随着fd的增加，select和poll的效率会线性降低，而epoll不会受到太大影响，除非活跃的socket很多

5种I0模型

参见：

https://blog.csdn.net/Bb15070047748/article/details/124699009

https://javaguide.cn/java/io/io-model.html#i-o