Epoll技术补充及扩展

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;

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将等待逻辑与新连接注册逻辑都统一放在一起操作,也就是频繁的轮询等待操作与频繁的大内存拷贝是叠加在一起执行,如下图: 

  

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

  
  

  

3. 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)

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

使用锁的技术

• 读写锁:内核在操作对象进行轮询的时候加读锁,而通过加写锁为了保证唤醒只执行一次,即在网络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执行流程

• 打开/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问题

并发连接与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技术补充及扩展