关于java:Redis-IO多路复用技术及epoll实现原理

Redis 是一个单线程的但性能是十分好的内存数据库，次要用来作为缓存零碎。Redis 采纳网络 IO 多路复用技术来保障在多连贯的时候，零碎吞吐量高。
1、为什么 Redis 要应用 IO 多路复用?
首先，Redis 是跑在单线程中的，所有的操作都是程序线性执行的，然而因为读写操作期待用户输出或者输入都是阻塞的，所以 I / O 操作往往不能间接返回，这会导致某一文件的 I / O 阻塞导致整个过程无奈为客户服务，而 I / O 多路复用模型就是为了解决这个问题而呈现的。
select、poll、epoll 都是 IO 多路复用的模型。I/ O 多路复用就是通过一种机制，能够监督多个文件描述符，一旦某个描述符就绪，可能告诉应用程序进行相应操作。

Redis 的 I / O 模型应用的就是 epoll，不过它也提供了 select 和 kqueue 的实现，默认采纳 epoll。

2、epoll 实现机制
①场景举例
构想一个如下场景：

有 100W 个客户端同时与一个服务器放弃着 TCP 连贯。而每一时刻只有几百上千个 TCP 连贯是沉闷着的（事实上大部分场景都是这样的状况）。如何实现这样的高并发。

在 select/poll 时代，服务器过程每次都要把 100W 个连贯通知操作系统（从用户态复制句柄数据结构到内核态），让操作系统内核去查问这些套接字上是否有事件产生，轮询完后，再将句柄数据复制到用户态，让服务器应用程序轮询解决曾经产生的网络事件，这一过程资源耗费较大，因而 select/poll 个别只能解决几千的并发连贯。
如果没有 I / O 事件产生，咱们的程序就会阻塞在 select 处。然而仍然存在一个问题，咱们从 select 那里仅仅晓得了有 I / O 事件产生，但却并不知道是哪几个流（可能一个，多个，甚至全副），咱们只能无差别轮询所有流，找出能读出或者写入数据的流，对它们进行操作。
然而，应用 select，咱们有 O（n）无差别轮询复杂度，同时解决的流越多，每一次无差别的轮询工夫就越长。
select/poll 毛病
1、每次调用 select/poll 都须要把 fd 汇合从用户态拷贝到内核态，这个开销在 fd 很多时会很大；
2、同时每次调用 select/poll 都须要在内核遍历传进来的所有 fd，这个开销在 fd 很多时会很大；
3、select 反对的文件描述符数量太小，默认 1024；
4、select 返回的是含有整个句柄的数组，应用程序须要遍历整个数组能力发现哪些句柄产生了事件；
5、select 的触发形式是程度触发，应用程序如果没有实现对一个曾经就绪的文件描述符进行 IO 操作，那么之后每次 select 调用还是会将这些文件描述符告诉给过程；

 相比于 select 模型，poll 模型应用链表保留文件描述符，因而没有了监督文件数量的限度，然而其余毛病仍然存在。

epoll 实现机制

epoll 的设计和实现与 select 齐全不同。epoll 是 poll 的一种优化，返回后不须要对所有的 fd 进行遍历，它在内核中保护了 fd 列表。select 和 poll 是将这个内核列表维持在用户态，而后复制到内核态。与 select/poll 不同，epoll 不在是一个独自的调度零碎，而是由 epoll_create / epolll_ctl / epoll_wait 三个零碎组成，前面将会看到这样做的益处。epoll 在 2.6 当前的内核才反对。
epoll 通过在 Linux 内核中申请一个繁难的文件系统（文件系统个别用什么数据结构？B+ 树）。把原先的 select/poll 调用分成三个局部。
1、调用 epoll_create（）建设一个 epoll 对象（在 epoll 文件系统中为这个句柄对象分配资源）；
2、调用 epoll_ctl 向 epoll 对象中增加这 100W 个连贯的套接字；
3、调用 epoll_wait 收集在这下面产生的事件连贯。
如此一来，要实现下面所说的的场景，只有在过程启动的时候创立一个 epoll 对象，而后在须要的时候向这个 epoll 对象中增加或者删除 socket 连贯。同时，epoll_wait 的效率也是十分高的，因为调用 epoll_wait 时，并没有一股脑的向操作系统复制这 100W 个连贯的句柄数据，内核也不须要去遍历全副的连贯。
epoll 长处
1、epoll 没有最大并发连贯限度，下限是最大能够关上的文件的数目，这个数字远大于“2048”， 一般来说，这个数目跟零碎内存关系很大，具体数目能够 cat /proc/sys/fs/file-max 查看。
2、效率晋升，epoll 最大的长处就在于它只管你沉闷的连贯，而跟连贯总数无关，因而在理论的网络环境中，epoll 的效率会远远高于 select/poll。
3、无内存拷贝，epoll 在这点上应用了“共享内存”，这个内存拷贝也就省略了。
3、Redis epoll 底层实现
当某一过程调用 epoll_create 办法时，Linux 内核会创立一个 eventpoll 构造体，这个构造体中有两个成员与 epoll 的应用形式密切相关。

eventpoll 构造体如下所示：struct eventpoll{
 
    ……
    /* 红黑树根节点，这棵树中存储着所有增加到 epoll 中须要监控的事件 */
    struct rb_root rbr;
 
    /* 双链表中则寄存着将要通过 epoll_wait 返回给用户的满足条件的事件 */
    struct list_head rdlist;
    ……
 
};

每一个 epoll 对象都有一个独立的 eventpoll 构造体，用于寄存通过 epoll_ctl 办法向 epoll 对象中增加进来的事件。这些事件都会挂在红黑树中，如此，反复增加的事件就能够通过红黑树高效标识进去（红黑树插入事件效率是 lgn，其中 n 为树的高度）。
而所有增加到 epoll 中的事件都会与设施（网卡）驱动程序建设回调关系，也就是说，当相应的事件产生时，会调用这个回调办法。这个回调办法在内核中叫 ep_poll_callback，它会将产生的事件增加到 rdlist 双向链表中。

在 epoll 中，每个事件都会建设一个 epitem 构造体，如下所示：struct epitem{
    // 红黑树节点
    struct rb_node rbn;
 
    // 双向链表节点
    struct list_head rdlist;
 
    // 事件句柄信息
    struct epoll_filefd ffd;
 
    // 指向其所属的 eventpoll 对象
    struct eventpoll *ep;
 
    // 期待产生的事件类型
    struct epoll_event event;
 
}

当调用 epoll_wait 办法查看是否有事件产生时，只须要查看 eventpoll 对象中的 rdlist 双向链表中是否有 epitem 元素即可。如果 rdlist 不为空，则把产生的事件复制到用户态，同时将事件的数量返回给用户。
劣势：
1、不必反复传递。咱们调用 epoll_wait 时候就相当于以前调用 select/poll，但这时却不必传递 socket 文件句柄给内核，因为内核曾经在 epoll_ctl 中拿到了要监控的文件句柄列表。
2、在内核里，所有皆文件。所以，epoll 向内核注册了一个文件系统，用于存储上述被监控 socket。当你调用 epoll_create 时，就会在这个虚构的 epoll 文件系统中创立一个 file 结点。当然这个 file 不是一般的文件，它只服务于 epoll。
3、极其高效的起因。这是因为咱们在调用 epoll_create 时候，内核除了帮咱们在 epoll 文件系统中创立了 file 结点，在内核 cache 里创立了个红黑树用于贮存当前 epoll_ctl 传来的 socket 外，还会再建设一个 list 链表，用于存储准备就绪的事件，当 epoll_wait 调用时候，仅仅察看这个 list 链表有没有数据即可。如果有数据就立刻返回，没有数据就 sleep，等到 timeout 时候，即便 list 没有数据也返回。所以 epoll_wait 十分高效。
epoll 在被内核初始化时（操作系统启动），同时会开拓出 epoll 本人的内核高速 cache 区，用于安置咱们每一个想要监控的 socket，这些 socket 会以红黑树的模式保留在内核 cache 里，以反对疾速的查找、插入、删除。这个内核高速 cache 区，就是建设间断的物理内存页，而后在此之上建设 slab 层，简略的说，就是物理上调配好你想要的 size 内存对象，每次应用都是应用闲暇的曾经调配好的对象。
这个准备就绪的 list 链表是怎么保护的呢？
当咱们执行 epoll_ctl 时，除了把 socket 放到 epoll 文件系统里 file 对象对应的红黑树上之外，还会给内核中断处理程序注册一个回调函数，通知内核，如果这个句柄的中断到了，就把它放到准备就绪的 list 链表里。所以，当一个 socket 上有数据到了，内核再把网卡中的数据 copy 到内核中后，就把 socket 插入到准备就绪的链表里了。（备注：好好了解这句话）
从下面能够看出，epoll 根底就是回调。
如此，一颗红黑树，一张准备就绪的句柄链表，大量的内核 cache，就帮咱们解决了高并发下的 socket 解决问题。
执行 epoll_create 时，创立了红黑树和就绪链表，执行 epoll_ctl 时，如果减少 socket 句柄，则查看红黑树中是否存在，存在就立刻返回，不存在则增加进红黑树，而后向内核注册回调函数，用于当中断事件来长期向准备就绪链表中插入数据。执行 epoll_wait 时，立即返回准备就绪链表里的数据即可。
最初看看 epoll 独有的两种模式 LT 和 ET。无论是 LE 还是 ET 都实用于以上所说的流程。区别是，LT 模式下，只有一个句柄上的事件一次没有解决完，会在当前调用 epoll_wait 时此次返回这个句柄，而 ET 模式仅在第一次返回。
对于 LT 和 ET，有一段形容，LT 和 ET 都是电子外面的术语，ET 是边缘触发，LT 是程度触发，一个示意只有在变动的边际触发，一个示意在某个阶段都会触发。
LT，ET 这件事怎么做到的呢？当一个 socket 句柄上有事件时，内核会把该句柄插入下面所说的准备就绪的 list 链表，最初，epoll_wait 干了这件事件，就是查看这些 socket，如果不是 ET 模式（就是 LT 模式的句柄了），并且这些 socket 上的确有未解决的事件时，又把该句柄放回刚刚清空的准备就绪链表了。所以，非 ET 的句柄，只有它下面还有事件，epoll_wait 每次都会返回这个句柄。（从下面这段，能够看出，LT 还有一个回放过程，低效了。）