Epoll技术补充及扩展

点击上方疾风先生可以订阅哦

在之前的文章中分别详细讲解网络IO模型以及IO复用模型技术实现的本质,关于epoll的技术分析,发现存在部分知识点不够严谨且也有些混乱,即epoll技术在linux底层内核源码实现中暂时没有看到有使用虚拟内存分配的技术实现,因此对此知识点持有怀疑但保留网络上的技术资料观点;其次关于epoll技术实现上,正是通过使用中间层的设计思想来解决本身select/poll无法扩展的局限性,同时借助分散的设计思想来解决select/poll存在的性能,最后我们会关注与epoll相关的其他高级轮询技术以及在早期中C10K问题是如何解决的,同时互联网技术发展至今,又出现C10M问题,解决思路有哪些可以借鉴的.

epoll技术补充

1. SLAB内存管理

SLAB内存管理特点

• 使用连续的内存地址空间来存储epitem/epoll,避免内存碎片(多个epoll的产生于多进程)
• 使用的epitem/epoll释放存放在"对象池"中进行重复利用，同时减少创建和销毁epitem带来的性能开销(内存申请和释放的开销),可以理解为高速缓存
• 内存分配原理如下:

epoll创建对象源码

// eventpoll.c
ep = kzalloc(sizeof(*ep), GFP_KERNEL);

// slab.h
static inline void *kzalloc(size_t size, gfp_t gfp)
{
     return kmalloc(size, gfp | __GFP_ZERO);
}

/* Slab cache used to allocate "struct epitem" */
static struct kmem_cache *epi_cache __read_mostly;

/* Slab cache used to allocate "struct eppoll_entry" */
static struct kmem_cache *pwq_cache __read_mostly;

通过上述可知,epoll技术在通过SLAB内存机制来创建epoll对象以及epitem对象,其一是避免产生内存碎片,其二是每当有一个客户端socket连接进来的时候,都需要创建对应的epitem,为了避免频繁创建和销毁epitem对象,通过池化技术与连续内存管理方式来提升性能.

2. epoll设计思想

采用中间层设计思想

• epoll空间以及epitem部分源代码

struct eventpoll {
    /* Wait queue used by sys_epoll_wait() */
    wait_queue_head_t wq;
    
    /* Wait queue used by file->poll() */
    wait_queue_head_t poll_wait;
    
    /* List of ready file descriptors */
    struct list_head rdllist;
    
    /* Lock which protects rdllist and ovflist */
    rwlock_t lock;  // 读写锁
    
    /* RB tree root used to store monitored fd structs */
    struct rb_root_cached rbr;  // 红黑树根节点
    
    /*
     * This is a single linked list that chains all the "struct epitem" that
     * happened while transferring ready events to userspace w/out
     * holding ->lock.
     */
    struct epitem *ovflist;    // 以单链表的形式将所有就绪epitem连接起来
}

struct epitem {
	union {
	/* RB tree node links this structure to the eventpoll RB tree */
	struct rb_node rbn;     //连接红黑树结构的节点
	/* Used to free the struct epitem */
	struct rcu_head rcu;
	};
    
    /* List header used to link this structure to the eventpoll ready list */
    struct list_head rdllink;   // 就绪队列header节点，与epoll空间的rdlist连接
    
    /* The file descriptor information this item refers to */
    struct epoll_filefd ffd;    // 存储注册的socket的fd以及对应的file
    
    /* The "container" of this item */
    struct eventpoll *ep;   // 指向epoll容器
	
    /* wakeup_source used when EPOLLWAKEUP is set */
    struct wakeup_source __rcu *ws;    // 可以理解为wake_up
    
    /* The structure that describe the interested events and the source fd */
    struct epoll_event event;   // 监听的事件变化结构
}

基于上述的部分源代码,现简单地将上述核心对象之间的关系串联起来如下所示:

epoll中间层设计分析

• epoll技术在逻辑设计上,epoll空间作为epitem的容器,同时将注册的socket绑定到epitem中,并且epoll空间与epitem在逻辑设计存储上用红黑树结构进行存储,方便在调用epoll_ctl的时候通过socket的fd快速定义到对应的epitem,并确定是否存在来创建epitem
• epoll空间通过ovflist将所有就绪的epitem以单链表的结构连接起来
• epitem包含wake_up唤醒函数以及对应的socket描述符信息，同时在注册新的socket的时候绑定对应的一个epitem,而每个epitem都将添加到对应的epoll_entry节点上,并将epoll_entry节点添加到epoll空间下的等待队列中,在系统调用epoll_wait的时候进行轮询
• 内核通过epoll容器下的等待队列wait_queue轮询每个epoll_entry等待节点,通过对每个节点下的epitem(即包装socket的中间层)来完成事件监听操作,首先当用户进程调用ep_wait方法的时候内核会在epoll空间下的wait_queue进行事件轮询,每次事件轮询都会调用vfs_loop()方法,并将其添加到轮询队列poll_wait中,当监听到有对应的就绪事件的时候就会将epoll_entry节点上的epitem连接到epoll空间下的单链表ovflist,接着在完成事件轮询之后且会将对应的就绪单链表epitem下的socket连接到epoll空间下的rdlist中,最后在返回给用户空间之前将epoll空间下的rdlist拷贝到当前epitem下的rdllink并执行epitem的wake_up触发回调函数callback以便于让处理read_process加入到cpu的就绪队列中等待cpu调度
• 通过上述我们知道,wake_up是在事件就绪之后通过对应的epitem来触发执行,相比select/poll技术在整个过程中只会执行一次,同时会只会返回所有就绪的socket信息

采用分散设计思想

从整体宏观上来看select/poll技术的处理流程:

• 当我们调用select/poll系统函数的时候都会等待内核事件准备就绪
• 当服务端scoket已经就绪的时候,就会有对应的一个客户端socket连接进来,这个时候我们需要采取类似FD_SET的方式将文件描述符fd保存到fd的集合中
• 其次当处理业务逻辑完成之后再次进入select/poll的轮询调用,这个时候我们就会将保存下来的其中也包括新注册的socket的fd一起拷贝到内核中等待就绪事件发生
• 从上述可知,select/poll将等待逻辑与新连接注册逻辑都统一放在一起操作,也就是频繁的轮询等待操作与频繁的大内存拷贝是叠加在一起执行,如下图:

而相比select/poll技术而言,epoll在技术实现流程如下:

• 等待就绪事件发生的操作将使用epoll_wait函数来实现与select/poll等同的效果
• 当服务socket已经就绪的时候,就会有对应的一个客户端socket连接进来,这个时候我们直接通过epoll_ctl函数发送fd到内核并交由内核负责创建绑定客户端文件描述符socket的epitem对象,然后在逻辑存储上通过红黑树的数据结构来维护epoll容器与epitem的存储逻辑,内核可以直接通过epoll空间对注册的fd进行事件监听
• 从上述可知,epoll技术将等待与注册新连接的操作分离,降低调用注册新连接socket的频数,同时当有连接过来的时候是直接将对应的客户端socket拷贝到内核,不需要保存在用户进程的一个集合容器中,避免大内存容器的数据拷贝,如下图所示:

3. Epoll其他技术要点

边缘与条件触发

了解到epoll技术实现之后,我们还需关心一个数据读取问题,也就是用户进程中的用户缓冲区与内核中的缓冲区之间的数据读取策略,一个完整的网络数据读取流程简要如下所示:

关于在上一节中讲述到边缘触发与条件触发本质在于:

• 边缘触发:如果socket缓冲区有接收到网卡数据,那么就会被触发告诉用户进程可以将数据缓冲区进行读取
• 水平触发:如果socket缓冲区非空,那么用户进程就会不断地读取缓冲区的数据,直到数据为空为止
• 在linux内核中实现的核心代码如下:

// 默认为水平触发对应标志为EPOLLONESHOT, 边缘触发标志为EPOLLET
list_for_each_entry_safe(epi, tmp, head, rdllink) {
		if (esed->res >= esed->maxevents)
			break;
        
        // 执行唤醒逻辑
		ws = ep_wakeup_source(epi);
		if (ws) {
			if (ws->active)
				__pm_stay_awake(ep->ws);
			__pm_relax(ws);
		}

        // 移除epitem下的ready_list
		list_del_init(&epi->rdllink);

        
        // 重新轮询事件收集就绪事件
		revents = ep_item_poll(epi, &pt, 1);
		if (!revents)
			continue;

        // 将就绪事件拷贝到用户空间中
		if (__put_user(revents, &uevent->events) ||
		    __put_user(epi->event.data, &uevent->data)) {
			list_add(&epi->rdllink, head);
			ep_pm_stay_awake(epi);
			if (!esed->res)
				esed->res = -EFAULT;
			return 0;
		}
		esed->res++;
		uevent++;
	    
	    
		if (epi->event.events & EPOLLONESHOT)
		    // 当前事件可能包含多种事件模式,对当前的事件模式重新设置为EP_PRIVATE_BITS集合中的一个子交集
		    epi->event.events &= EP_PRIVATE_BITS;
		else if (!(epi->event.events & EPOLLET)) {
		// 当前socket已经被设置为水平触发模式，需要重新添加到ready_list以便于调用epoll_wait的时候能够检查到事件可用
		    list_add_tail(&epi->rdllink, &ep->rdllist);
		    ep_pm_stay_awake(epi);
		}
		
		// 如果为边缘事件模式,不会添加到ready_list队列中,也就是说
	}
/* Epoll private bits inside the event mask */
#define EP_PRIVATE_BITS (EPOLLWAKEUP | EPOLLONESHOT | EPOLLET | EPOLLEXCLUSIVE)

从上述看到,可以看到对于水平触发的方式,epoll技术实现是将socket进行事件轮询之后重新添加到ready_list队列的尾部,以便于用户进程调用epoll_wait函数的时候能够再次检测到socket缓冲区的数据是否处于就绪状态,而对于边缘触发方式则轮询一次之后就停止了,需要等待下一次socket缓冲区有接收到网卡发送过来的数据报,对此,在上图中,如果完整的数据报大小为512kb,而如果用户空间的用户缓冲区仅为128kb,这个时候水平触发与边缘触发的模式处理策略如下:

• 对于水平触发模式,首先用户进程接收到数据缓冲区可读的时候,将数据copy到用户缓冲区中,发现这个时候缓冲区大小不够仅能将缓冲区数据大小的数据copy到用户缓冲区中进行读取,然后从上述代码可知,在轮询过程我们会调用epoll_wait的方式,那么这个时候再次轮询调用就知道当前缓冲区还有数据就绪,可以继续读取直到socket缓冲区为空,再次轮询的时候没有数据继续就会跳过.
• 对于边缘触发模式,同样也是将与用户缓冲区大小的数据从socket缓冲区中拷贝到内核中,然而进程是不知道数据是不是读取完全,但是通过上述代码可知,再次调用epoll_wait的时候必须等待网卡设备向socket缓冲区发送数据报才会触发,那么也就是下次读取数据的时候才能再次从socket缓冲区中读取,但是此时仍然是前一次的数据报信息并非网卡新发送的数据报信息,对此我们很容易想到两个问题,一个缓冲区数据堆积,一个是数据读取不及时不完整,可能出现数据丢失的情况(machine broken down)

对此,两者模式对比起来,其实水平触发模式会更为符合我们网络IO编程的设计思路,而对于边缘触发而言,虽然说可以通过调整用户进程的缓冲区大小来降低降低缓冲区的数据堆积,但仍然是治标不治本,我们很难预测网卡接收到的数据大小(或许有同学会认为socket本身接收数据报大小也是有上限的,有办法计算,但还有一个问题)以及网卡何时会有数据报的接收(这点很关键,毕竟缓冲区是存储在内存中,对内存压力还有的),而水平触发可以在接收数据报的短时间内处理掉并降低数据丢失的风险,减缓内存压力,但是水平触发就需要不断轮询通过上述图解流程来完成数据的读取过程.

使用锁的技术

• 读写锁:内核在操作对象进行轮询的时候加读锁,而通过加写锁为了保证唤醒只执行一次,即在网络socket数据报可达,通过中断上下文调用wake_up()方法来触发回调callback方法的执行,通过callback方法将执行的task添加到CPU就绪队列️中，方便CPU进行调度执行
• 使用epoll空间的内置的锁mtx:当事件就绪的时候,内核需要将就绪的socket拷贝到用户空间,为了保证期间能够被拷贝而能够进行休眠,休眠的过程需要进行加锁
• 全局锁:通过加全局锁释放epoll容器下的资源,避免产生死锁

epoll技术思考

• 对于select/poll技术实现,为了能够向用户进程提供就绪描述符列表fdset,采取引入中间层设计思想解决,由内核通过中间层来对fd实现事件监听并负责将就绪的fd串联起来,对比到我们大型互联网应用中,常见手段也会有通过中间层来扩展组件原本的功能,通过中间层擅长的功能特征来帮助我们更好地扩展我们的系统应用.
• 对于性能问题,面对频繁调用的等待处理与大内存拷贝的操作,采用分散设计的方式来提升性能,相比分布式系统设计,面对高并发处理,我们采取集群手段,同时在实现的技术中,为了提升并发效率,也会通过分散机制来实现,比如ConcurrentHashMap&LongAdder等技术手段.
• 另外,从epoll技术可以看到,为了提升性能,实现更好的扩展性,也作了一些牺牲,相比select/poll技术实现,epoll技术会占用更多的内存空间,通过牺牲空间换取性能的手段,对比到我们高并发系统设计也常常需要考虑性能与空间之间的平衡点.
• 同时,我们也看到,实质上不论是select/poll/epoll_wait的阻塞等待机制,其实是利用了并发编程的锁机制,而通过linux内核的唤醒与回调机制可知,加锁的本质就是排队,如果谁获取到执行权就从队列中移除,没有获取到执行权就添加到等待队列中等待被唤醒.

高级轮询技术

/dev/poll

• 核心api如下:

struct dvpoll{
    struct pollfd* dp_fds;      // 链表的形式,指向一个缓冲区,提供给ioctl返回的时候存储一个链表的数组
    int            dp_nfds;     // 缓冲区成员大小
    int            timeout;
}

wfd = open(`/dev/poll`, O_RDWR, 0);
Write(wfd, pollfd, MAX_SIZE)    # pollfd 为poll结构体
ioctl(wfd, DP_POLL, &dvpoll)

• /dev/poll执行流程

是Solaris操作系统上名为/dev/poll的特殊文件提供了可扩展的轮询大量描述,相比select技术,其轮询技术可以预先设置好待查询的文件描述符列表,然后进入一个循环等待事件发生,每次循环回来之后不需要再设置该列表,其流程如下:

• 打开/dev/poll文件，然后初始化一个pollfd结构数组(poll使用的结构),向/dev/poll提供描述符列表
• 调用write方法往/dev/poll写这个结构数组并传递给内核
• 执行io_ctl的DP_POLL阻塞自身以等待就绪事件的发生

kqueue技术

• FreeBSD4.1引入kqueue技术,允许进程向内核注册描述所关注的kqueue事件的事件过滤器(event filter),其api如下:

// 返回一个新的kqueue描述符,用户后续的kevent调用
int kqueue(void);

// 用于注册事件也用于确定是否有事件发生
int kevent(int kq,                                                                  // kqueue的注册事件fd
           const struct kevent *changelist, int nchanges,                           // 给出关注事件作出的更改,无更改为NULL & 0
           struct kevent *eventlist, int nevents,                                   // kevent结构数组
           const struct timespc *timeout);                                          // 超时

// 更新事件函数
void EV_SET(struct kevent *kev, uintptr_t ident, short filter, u_short flags, u_int fflags, intptr_r data, void *udata);

// kevent结构体
struct kevent {
    uintptr_t   ident;
    short filter;
    u_short flags;
    u_int fflags;
    intptr_r data;
    void *udata;
}

• 从上述的结构可以推测出与epoll的实现原理类似,只不过相比epoll实现,增加更多事件的监听(异步IO/文件修改通知/进程跟踪/信号处理等)
• 但是和/dev/poll一样存在的兼容性问题,目前是在FreeBSD系统中
• 对应不同的事件以及事件的过滤器，如下：

高级轮询技术与epoll对比

• kqueue技术在应用FreeBSD系统中,而/dev/poll技术是应用在Solaris操作系统上,故而存在移植的兼容性问题
• 两者与epoll技术设计上原理类似,采用分散与中间层的方式来解决select/poll本身存在的问题,只是上述高级轮询技术在具体实现的方案与设计初衷与epoll技术不尽相同,故而在我们做系统设计的时候都需要思考一个问题,那就是面向通用型设计还是面向定制设计,这也将决定我们因目标的设计不同而采取相应的解决方案,并可能会影响到后期的发展问题

C10K问题

什么是C10K问题

摘录wiki百科解释,即要实现一个能支撑1w的并发连接处理的服务程序,我们如何通过优化来解决这个问题

并发连接与QPS

• 并发连接:主要体现在服务端程序高效的连接调度机制上,也就是说服务端能够在一定的时间段内能够正确地响应给每个连接的请求即可,换言之就是并发连接都要保证服务能够可靠响应给客户端的请求,对系统的要求追求是能确定调度响应每个连接请求即可.
• QPS:主要体现在处理业务请求的速度上,比如说70QPS/s也就意味着1s内能够处理正确处理70个业务请求,对系统的要求是追求快速的性能.
• 可以用下图体现:

解决方案

• 使用单线程(1:M)+IO复用技术(select/poll/kqueue/dev/poll)+水平触发方式
• 使用单线程(1:M)+IO复用技术(Linux内核2.6之后的kqueue/epoll)+就绪可读事件的实时信号通知(边缘触发)
• 使用单线程(1:M)+AIO(Unix对AIO的支持,而Window上的IOCP利用AIO的思想来实现异步处理)
• 使用多线程方式(M:N模式),在Linux2.6之后的版本,使用Linux的本地Posix线程库NPTL技术实现分配线程,对于Linux而言,1:1线程是指将所有线程库存放在内核中,而对于M:N而言,是将部分线程移入到用户空间使用

存在的技术问题

• 每个操作系统都存在文件描述符个数的限制,需要进行配置
• 线程数瓶颈,一般会通过池化技术实现资源重复利用或者是使用其他方案的连接调度策略来分担并发连接
• 内存机制,需要引入一些特殊的内存管理机制,减少内存副本之间的拷贝问题,可以使用使用虚拟内存mmap方式来降低内存副本之间的拷贝
• 有时候由于调用write进行写数据的时候,如果数据较小,内核会频繁发送小数据,无法充分利用缓冲的作用,而新套接字选项TCP_CORK告诉内核避免发送部分帧,当然有时候一部分小数据是无法共存的时候必须通过flush的方式刷新

成熟技术方案

• Nginx是解决C10K而被设计出来的,在实际应用场景,我们也是使用nginx技术来实现高并发的连接请求调度,可作为接入层接收大并发连接
• IO框架技术,比如libevent
• 基于Reactor事件驱动设计,比如Netty

关于C10K与C10M参考连接

https://en.wikipedia.org/wiki/C10k_problem
http://www.kegel.com/c10k.html

## C10M问题
http://highscalability.com/blog/2013/5/13/the-secret-to-10-million-concurrent-connections-the-kernel-i.html

至此,epoll相关技术将告一段落,如果有用欢迎转发或好看,感谢!