epoll惊群效应深度剖析

1. 不使用epoll/select的情况下多进程是如何共享端口监听的？

不使用多路复用的情况下，进程要接受tcp连接必然要调用accept并且被阻塞，直到有一条连接到达，在这之前无法做别的事情，也即是说单个进程一次只能处理一条连接，业务处理完成之后调用close关闭连接，然后继续等待accept，循环往复，这种情况下是无法实现高并发的，所以一般会使用多进程再来同时处理更多的连接，多进程一般情况下有两种模式
第一种是由一个主进程进行accept监听，接受一个连接之后再fork出一个子进程，把连接丢给子进程去进行业务处理，然后主进程继续监听，这个是最简单的模式，由于只有一个进程在使用accept进行监听，不涉及多进程争抢的问题，当tcp连接事件到达后也只会唤醒这个监听进程，自然也不存在惊群效应

第二种形式是由主进程fork出一批子进程，子进程继承了父进程的这个监听端口，大家共享，然后一起监听。这里面就涉及到当多个进程在阻塞状态中等待同一个端口事件时内核的行为，接下来重点分析一下这个场景

// 进程调用accept时会进入inet_csk_accept，这是accept的核心所在
struct sock *inet_csk_accept(struct sock *sk, int flags, int *err)
{
	struct inet_connection_sock *icsk = inet_csk(sk);
	struct sock *newsk;
	int error;

	lock_sock(sk);

	/* We need to make sure that this socket is listening,
	 * and that it has something pending.
	 */
	error = -EINVAL;
    // 确认socket处于监听状态
	if (sk->sk_state != TCP_LISTEN)
		goto out_err;

	/* Find already established connection */
    /*接下来要找到一个建立好的连接*/
	if (reqsk_queue_empty(&icsk->icsk_accept_queue)) { // 如果sock的连接队列是空
		long timeo = sock_rcvtimeo(sk, flags & O_NONBLOCK);

		/* If this is a non blocking socket don't sleep */
		error = -EAGAIN;
		if (!timeo) // 如果设置了非阻塞模式则直接返回，err是喜闻乐见的-EAGAIN
			goto out_err;
        // 如果处于阻塞模式，则进入inet_csk_wait_for_connect，进程将处于阻塞状态，直接到新到的连接唤醒
		error = inet_csk_wait_for_connect(sk, timeo);
		if (error)
			goto out_err;
	}
    // 到这里，连接队列会有至少一条可用连接用到返回
	newsk = reqsk_queue_get_child(&icsk->icsk_accept_queue, sk);
	WARN_ON(newsk->sk_state == TCP_SYN_RECV);
out:
	release_sock(sk);
	return newsk;
out_err:
	newsk = NULL;
	*err = error;
	goto out;
}
EXPORT_SYMBOL(inet_csk_accept);

// inet_csk_wait_for_connect会将进程挂起，直到被新到的连接唤醒
static int inet_csk_wait_for_connect(struct sock *sk, long timeo)
{
	struct inet_connection_sock *icsk = inet_csk(sk);
	DEFINE_WAIT(wait); // 定义一个等待节点，用于挂在socket监听队列下
	int err;

	for (;;) {
        // 使用prepare_to_wait_exclusive确认互斥等待，在一个事件到达后内核只会唤醒等待队列中的一个进程
		prepare_to_wait_exclusive(sk_sleep(sk), &wait,
					  TASK_INTERRUPTIBLE);
		release_sock(sk);
		if (reqsk_queue_empty(&icsk->icsk_accept_queue))
            // 再一次判断队列是否空，空则进入调度，此时当前进程将被挂起
			timeo = schedule_timeout(timeo);
		lock_sock(sk);
		err = 0;
		if (!reqsk_queue_empty(&icsk->icsk_accept_queue))
			break;
		err = -EINVAL;
		if (sk->sk_state != TCP_LISTEN)
			break;
		err = sock_intr_errno(timeo);
		if (signal_pending(current))
			break;
		err = -EAGAIN;
		if (!timeo)
			break;
	}
	finish_wait(sk_sleep(sk), &wait);
	return err;
}

我摘取了linux内核中关于accept部分的核心代码，Linux提供了accept4的系统调用，accept4最终将调用上述的inet_csk_accept，而inet_csk_accept最终调用inet_csk_wait_for_connect，如果此时没有连接可用，内核会将当前进程挂起，其中的点在于挂起进程使用的是prepare_to_wait_exclusive这个函数，不存在多进程唤醒
PS：如果对内核原理没有一定的基础，可能不会知道prepare_to_wait_exclusive是什么东西，简单来说linux的内核对进程唤醒提供了两种模式，一种是prepare_to_wait，一种是prepare_to_wait_exclusive，exclusive即互斥，如果调用的是prepare_to_wait_exclusive，则在对一个等待队列进程唤醒的时候，只会唤醒一个进程，而prepare_to_wait没有设置互斥位，会将挂在这个等待队列上的所有进程全部唤醒
综上可知，在普通的多进程共享监听端口的情况下，内核对一个新的连接事件的到达，只会唤醒其中一个进程

可直接看以上流程图，父进程创建的监听socket fd1由fork出来的两个子进程共享，这时候子进程的两个fd在内核中是属于同一个文件，被记录在open files table这个表中，接下来第4、5步，两个子进程同时调用accept进行阻塞监听，两个进程都会被挂起来，内核会在这个socket的等待队列wait queue链表中将两个PID记录下来以便唤醒；在第8步中一个连接事件到达，内核将对应socket下的等待队列取出来，对于tcp连接事件而言，内核对一个连接事件只会唤醒一个进程，取出wait queue链表的第一个节点，将对应的进程唤醒，此时PID1进程的accept成功取到连接并返回用户态，PID2没有被唤醒
其实在linux 2.6之前的版本中，accept也会全量唤醒wait queue中的所有进程，同样造成了惊群效应，在2.6中增加了互斥标志，修复了这个问题

2. epoll下共享监听端口的行为

接下来看看在使用epoll的情况下，也存在多个进程一起监听端口的情况，最经典的例如nginx，多个worker会一起监听同一个端口，而在它1.11版本之前，使用的是上述第一节讲的方式，master进程创建一个监听端口之后，通过fork的方式，让woker进程继承这个端口，然后放到epoll里面去进行监听，现在我们重点来看一下在这个场景下（epoll+accept）内核的行为是怎样的
与直接accept不同，epoll需要先调用epoll_create在内核中创建一个epoll文件，如下图

epoll会创建一个匿名的inode节点，这个节点指向的是一个epoll主结构，这个结构中有两个核心字段，一个是红黑树，用户态需要监听的文件都会挂在这个红黑树下面，实现lgn的查找、插入、更新的复杂度；另外一个是rdlist，即文件事件的就绪队列，指向的是一个链表，事件产生的时候，epoll会把对应的epitem（即红黑树上的节点）插入到这个链表中，当向用户态返回的时候，只需要遍历这个就绪链表即可，而不需要像select那样遍历所有文件，不过本文的重点是分析epoll的阻塞及唤醒过程，epoll本身的主结构简单带过，实际上这个结构是比较复杂的，可以看我之前写过的文章 ()

接下来看如何把要监听的socket fd挂在epoll上，这个过程调用的是epoll_ctl，将fd向内核传递，内核实际上会做两个事情

1. 将fd挂在红黑树中
2. 调用文件设备驱动的poll回调指针（这是重点）

epoll/select等这些模型要实现多路复用，实际上主要就是依赖于：将进程挂在对应的fd的等待队列上，这样当这个fd的事情产生的时候，设备驱动就会将这个队列上的进程唤醒，如果进程不依赖epoll，毫无疑问他无法将自己同时挂在多个fd的队列上，epoll帮他干了这个事情，而干这个事情的一个核心步骤，是调用对应fd驱动设备提供的poll方法
linux中，对设备模型进行了一个规范的标准化，比如设备分为字符设备、块设备、网络设备等，对于开发者而言，要给一个设备实现一个驱动程序就必须按照linux提供的规范来实现，其中对于跟用户层交互这块，内核要求开发者实现一个叫file_operations的结构，这个结构定义了一系列操作的回调指针，比如read、write等用户熟知的操作，当用户调用read、write等方法时，最终内核会回调到这个设备的file_operations.read、file_operations.write方法，这个方法的具体逻辑需由驱动开发者实现，比如本文的accept调用，实际上最终是调用了socket下面的file_operations.accept方法
综上所述，如果一个设备要支持epoll/select的调用，他必须实现file_operations.poll方法，epoll在处理用户层传入的fd时，实际上最终是调用了这个方法，而这个方法linux同样做了一系列规范，他要求开发者实现以下逻辑：

1. 要求poll方法返回用户感兴趣的事情的标志，比如当前fd是否可读、是否可写等
2. 如果poll传入一个poll专用的等待队列结构体，那他将会调用这个结构体，这个结构体中会有一个叫poll_table的东西，里面有一个回调函数，poll方法最终会调用这个回调，这个回调是由epoll来设定的，epoll在这个方法中实现的逻辑是：将当前进程挂在这个fd的等待队列上面

简单来说，如果是进程自己调用accept，则协议栈驱动会亲自把这个进程挂在等待队列上，如果是epoll来调用，则会回调poll方法，最终epoll亲自将进程挂在这个等待队列上面，记住这个结论，这是引发accept惊群效应的最根本原因 我们来看一下epoll是如何跟file_opreations->poll方法进行交互的，我画了一个简单的时序图

如上图，当用户调用epoll_ctl的添加事件的时候，在第6步中，epoll会把当前进程挂在fd的等待队列下，但是默认情况下这种挂载不会设置互斥标志，意思着当设备有事情产生进行等待队列唤醒的时候，如果当前队列有多个进程在等待，则会全部唤醒
可想而知，在下面的epoll_wait调用中，如果多个进程将同一个fd添加到epoll中进行监听，当事件到达的时候，这些进程将被一起唤醒
但是唤醒并不一定会向用户态返回，因为唤醒之后epoll还要遍历一次就绪列表，确认有至少一个事件发生才会向用户态返回
到此，我们可以想象出epoll是如何造成accept惊群的：

1. 当多个进程共享同一个监听端口并且都使用epoll进行多路复用的监听时，epoll将这些进程都挂在同一个等待队列下
2. 当事件产生时，socket的设备驱动都会尝试将等待队列的进行唤醒，但是由于挂载队列的时候使用的是epoll的挂载方式，没有设置互斥标志（取代了accept自己挂载队列的方式，如第一节所述），所以这个队列下的所有进程将全部被唤醒
3. 唤醒之后此时这些进程还处于内核态，他们都会立刻检查事件就绪列表，确认是否有事件发生，对accept而言，accept->poll方法将会检查在当前的socket的tcp全连接列表中是否有可用连接，如果是则返回可用事件标志
4. 当所有进程都被唤醒，但是还没有进行去真正做accept动作的时候，所有进行的事件检查都认为accept事件可用，所以这些进行都向用户态返回
5. 用户态检查到有accept事件可用，这时他们将会真正调用accept函数进行连接的获取
6. 此时只会有一个进行能真正获取连接，其他进行都会返回EAGAIN错误，使用strace -p PID命令可以跟踪到这种错误
7. 并不是所有进行都会返回用户态，关键点在于这些被唤醒的进行在检查事件的过程中，如果已经有进程成功accept到连接了，这时别的事情将不会检查到这个事情，从而他们会继续休眠，不会返回用户态
8. 虽然不一定会返回用户态，但也造成了内核上下文切换的发生，其实也是惊群效应的表现

3. 内核解决了惊群效应了吗

根本原因在于epoll的默认行为是对于多进程监听同一文件不会设置互斥，进而将所有进程唤醒，后续的内核版本主要提供了两种解决方案

1. 既然默认不会设置互斥，那就加一个互斥功能好了:-)，linux4.5内核之后给epoll添加了一个EPOLLEXCLUSIVE的标志位，如果设置了这个标志位，那epoll将进程挂到等待队列时将会设置一下互斥标志位，这时实现跟内核原生accept一样的特性，只会唤醒队列中的一个进程
2. 第二种方法：linux 3.9内核之后给socket提供SO_REUSEPORT标志，这种方式解决得更彻底，他允许不同进程的socket绑定到同一个端口，取代以往需要子进程共享socket监听的方式，这时候，每个进程的监听socket将指向open_file_tables下的不同节点，也就是说不同进程是在自己的设备等待队列下被挂起的，不存在共享fd的问题，也就不存在被同时唤醒的可能时，而内核则在驱动中将设置了SO_REUSEPORT并且绑定同一端口的这些socket分到同一个group中，当有tcp连接事件到达的时候，内核将会对源IP+源端口取hash然后指定这个group中其中一个进程来接受连接，相当于在内核级别中实现了一个负载均衡

基于以上两种方法，其实epoll生态在目前来说不存在所谓的惊群效应了，除非：你溢用epoll，比如多进程之间共享了同一个epfd（父进程创建epoll由多个子进程来调用），那就不能怪epoll了，因为这时候多个进程都被挂到这个epoll下，这种情况下，已经不是仅仅是惊群效应的问题了，比如说，A进程在epoll挂了socket1的连接事件，B进程调用了epoll_wait，由于属于同一个epfd，当socket1产生事件的时候，进程B也会被唤醒，而更严重的事情在于，在B的空间下并不存在socket1这个fd，从而把问题搞得很复杂。总结：千万不要在多线程/多进程之间共享epfd

4. Nginx是如何解决惊群效应的

nginx在1.11版本以上，已经默认打开了SO_REUSEPORT选项，解决了这个问题，应用层不需要做特别的事情，而在这之前，nginx解决惊群的方式是加锁，多个进程之间共享一个文件锁，只有在抢到这个锁的时候，这个进程才会将要监听的端口放到epoll中，当epoll_wait返回之后，nginx会调用accept把连接取出来，然后释放文件锁，让别的进程去监听。这是一种折衷的办法，并没有很完美，首先进程间争抢锁会有性能开耗（即使是非阻塞的锁），中间可能会有小段时间没有进程去获取锁，比如A进程拿到锁，其他进程将会过一小段时间尝试再去获取锁，而这小段时间里面如果请求量很大，A仅接受一小部分请求就让出锁，则中间过程会有一些连接事件被hang住，总而言之，升级nginx版本吧，不要再依靠这种模式了！

5. uwsgi是如何解决惊群效应的

[https://uwsgi-docs.readthedocs.io/en/latest/articles/SerializingAccept.html](Serializing accept(), AKA Thundering Herd, AKA the Zeeg Problem - uWSGI 2.0 documentation)

以上是uwsgi官方的说明，认为uwsgi应用一般不追求并发量，在实际上并不需要特殊关注惊群的问题，同时也提供了一个-thunder-lock的选项，实现了一个锁用于进程间争抢accept，当然了，在新版本中也支持了SO_REUSEPORT并且默认打开，不过在实际运行中发现，如果不打开这个锁的情况下，惊群效应对uwsgi导致的结果是：CPU倾斜
在所有进行都在监听的情况下，谁先从内核层中返回用户态并accept，谁就能成功拿到socket，而拿到socket之后通常会继续将这个socket添加到epoll中用来监听收到数据的事件，如果一个进程在epoll中添加的socket越多，那么他被唤醒的概率越大，唤醒之后他会检查accept，所以他成功accept的概率也越高，久而久之，你会看到总是有少数几个worker在处理请求，而其他worker被饿死
不过对这种情况我还没有进行详细思考，后面有机会的话单独给uwsgi写一篇
完结