[大数据]Redis 是如何实现高性能的IO多路复用

场景

????????有100万个客户端同时与一个服务器进程保持着TCP连接。而每一时刻，通常只有几百上千个TCP连接是活跃的 (事实上大部分场景都是这种情况)。如何实现这样的高并发？

为什么使用IO多路复用

????????Redis 是跑在单线程中的，所有的操作都是按照顺序线性执行的，但是由于读写操作等待用户输入或输出都是阻塞的，所以 I/O 操作在一般情况下往往不能直接返回，这会导致某一文件的 I/O 阻塞导致整个进程无法对其 它客户提供服务，而 I/O 多路复用就是为了解决这个问题而出现的。

?

select模式

????????服务器进程每次都把这100万个连接告诉操作系统(从用户态复制句柄数据结构到内核态)，让 操作系统内核去查询这些套接字上是否有事件发生，轮询完后，再将句柄数据复制到用户态，让服务器应用程序轮询 处理已发生的网络事件，这一过程资源消耗较大，因此，select/poll一般只能处理几千的并发连接。

?特点：

????????如果没有I/O事件产生，我们的程序就会阻塞在select处。但是依然有个问题，我们从select那里仅仅知道了，有 I/O事件发生了，但却并不知道是那几个流（可能有一个，多个，甚至全部），我们只能无差别轮询所有流，找出能 读出数据，或者写入数据的流，对他们进行操作。

????????select返回的是含有整个句柄的数组，应用程序需要遍历整个数组才能发现哪些句柄发生了事件。使用select，我们有O(n)的无差别轮询复杂度，同时处理的流越多，每一次无差别轮询时间就越长。针对select支持的文件描述符数量太小了，默认是1024（并发处理能力有限，一般是几千）。

缺点：

1. 每次调用select/poll，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大
2. 同时每次调用select/poll都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
3. 针对select支持的文件描述符数量太小了，默认是1024
4. select返回的是含有整个句柄的数组，应用程序需要遍历整个数组才能发现哪些句柄发生了事件；
5. select的触发方式是水平触发，应用程序如果没有完成对一个已经就绪的文件描述符进行IO操作，那么之后每次 select调用还是会将这些文件描述符通知进程。

poll模式

????????相比select模型，poll使用链表保存文件描述符，因此没有了监视文件数量的限制，但其他三个缺点依然存在。

epoll模式（默认）

总体流程

????????执行epoll_create时，创建了红黑树和就绪链表，执行epoll_ctl时，如果增加 socket句柄，则检查在红黑树中是否存在，存在立即返回，不存在则添加到树干 上，然后向内核注册回调函数，用于当中断事件来临时向准备就绪链表中插入数 据。执行epoll_wait时立刻返回准备就绪链表里的数据即可。

特点：

????????epoll是poll的一种优化，返回后不需要对所有的fd进行遍历，在内核中维持了fd的列表（过在Linux内核中申请一个简易的文件系统）。

????????与poll/select不同，epoll不再是一个单独的系统调用，而是由epoll_create、epoll_ctl、epoll_wait三个系统调用组成。

1. 调用epoll_create()建立一个epoll对象(在epoll文件系统中为这个句柄对象分配资源)
2. 调用epoll_ctl向epoll对象中添加这100万个连接的套接字
3. 调用epoll_wait收集发生的事件的连接

????????如此一来，只需要在进程启动时建立一个epoll对象，然后在需要的时候向这个epoll对象 中添加或者删除连接。同时，epoll_wait的效率也非常高，因为调用epoll_wait时，并没有一股脑的向操作系统复 制这100万个连接的句柄数据，内核也不需要去遍历全部的连接（socket资源就绪之后会返回到一个就绪链表上，epoll_wait只要处理就绪链表上的socket即可）。

?

底层实现：

????????当某一进程调用epoll_create方法时，Linux内核会创建一个eventpoll结构体，这个结构体有两个关键的成员，内核文件（红黑树的根节点），就绪链表（双向链表的表头，供epoll_wait使用）

????????每一个epoll对象都有一个独立的eventpoll结构体，用于存放通过epoll_ctl方法向epoll对象中添加进来的事 件。这些事件都会挂载在红黑树中，如此，重复添加的事件就可以通过红黑树而高效的识别出来(红黑树的插入时间 效率是lgn，其中n为树的高度)

????????所有添加到epoll中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当相应的事件发生时会调用这个 回调方法。这个回调方法在内核中叫ep_poll_callback,它会将发生的事件添加到rdlist双链表中

????????在epoll中，对于每一个事件，都会建立一个epitem结构体，如下所示：

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

如何维护就绪列表？

????????执行epoll_ctl时，除了把socket放到epoll文件系统里file对象对应的红黑树上之外，还会给内核中断处理程序注册一个回调函数，告诉内核，如果这个句柄的中断到了，就把它放到准备就绪list链表里。所以，当一个 socket上有数据到了，内核在把网卡上的数据copy到内核中后就来把socket插入到准备就绪链表里了。epoll的基础就是回调！

优势：

1. 减少内存复制的开销，不用重复传递
2. 向内核注册了一个文件系统，用于存储上述的被监控socket（效率更高）
3. 良好的数据结构设计（文件系统使用红黑树，增删改查效率相比轮询更快，就绪列表可以减少无效的查询）

LE和ET模式

????????LT和ET模式，都适用于以上所说的流程。

1. ET是（边缘触发）：调用epoll_wait仅在第一次返回。
2. LT（水平触发）：只要一个句柄上的事件一次没有处理完，会在以后调用epoll_wait时次次返回这个句柄。

LT和ET模式是如何做到的？

????????当一个socket句柄上有事件时，内核会把该句柄插入上面所说的准备就绪list链表， 这时我们调用epoll_wait，会把准备就绪的socket拷贝到用户态内存，然后清空准备就绪list链表，最后， epoll_wait干了件事，就是检查这些socket，如果不是ET模式（就是LT模式的句柄了），并且这些socket上确实有未处理的事件时，又把该句柄放回到刚刚清空的准备就绪链表了。所以，非ET的句柄，只要它上面还有事件， epoll_wait每次都会返回这个句柄。（从上面这段，可以看出，LT还有个回放的过程，低效了）