惊群效应是什么

惊群效应（thundering herd）是指多进程（多线程）在同时阻塞等待同一个事件的时候（休眠状态），如果等待的这个事件发生，那么他就会唤醒等待的所有进程（或者线程），但是最终却只能有一个进程（线程）获得这个时间的“控制权”，对该事件进行处理，而其他进程（线程）获取“控制权”失败，只能重新进入休眠状态，这种现象和性能浪费就叫做惊群效应。

惊群效应消耗了什么

Linux 内核对用户进程（线程）频繁地做无效的调度、上下文切换等使系统性能大打折扣。上下文切换（context switch）过高会导致 CPU 像个搬运工，频繁地在寄存器和运行队列之间奔波，更多的时间花在了进程（线程）切换，而不是在真正工作的进程（线程）上面。直接的消耗包括 CPU 寄存器要保存和加载（例如程序计数器）、系统调度器的代码需要执行。间接的消耗在于多核 cache 之间的共享数据。
为了确保只有一个进程（线程）得到资源，需要对资源操作进行加锁保护，加大了系统的开销。目前一些常见的服务器软件有的是通过锁机制解决的，比如 Nginx（它的锁机制是默认开启的，可以关闭）；还有些认为惊群对系统性能影响不大，没有去处理，比如 Lighttpd。

Accept惊群现象

我们知道，在网络分组通信中，网络数据包的接收是异步进行的，因为你不知道什么时候会有数据包到来。因此，网络收包大体分为两个过程：

1. 数据包到来后的事件通知
2. 收到事件通知的Task执行流，响应事件并从队列中取出数据包

数据包到来的通知分为两部分：

1. 网卡通知数据包到来，中断协议栈收包；
2. 协议栈将数据包填充 socket 的接收队列，通知应用程序有数据可读，这里仅讨论数据到达协议栈之后的事情。

应用程序是通过 socket 和协议栈交互的，socket 隔离了应用程序和协议栈，socket 是两者之间的接口，对于应用程序，它代表协议栈；而对于协议栈，它又代表应用程序，当数据包到达协议栈的时候，发生下面两个过程：

1. 协议栈将数据包放入socket的接收缓冲区队列，并通知持有该socket的应用程序；
2. 持有该socket的应用程序响应通知事件，将数据包从socket的接收缓冲区队列中取出

对于高性能的服务器而言，为了利用多 CPU 核的优势，大多采用多个进程(线程)同时在一个 listen socket 上进行 accept 请求。多个进程阻塞在 Accept 调用上，那么在协议栈将 Client 的请求 socket 放入 listen socket 的 accept 队列的时候，是要唤醒一个进程还是全部进程来处理呢？linux 内核通过睡眠队列来组织所有等待某个事件的 task，而 wakeup 机制则可以异步唤醒整个睡眠队列上的 task，wakeup 逻辑在唤醒睡眠队列时，会遍历该队列链表上的每一个节点，调用每一个节点的 callback，从而唤醒睡眠队列上的每个 task。这样，在一个 connect 到达这个 lisent socket 的时候，内核会唤醒所有睡眠在 accept 队列上的 task。N 个 task 进程(线程)同时从 accept 返回，但是，只有一个 task 返回这个 connect 的 fd，其他 task 都返回-1(EAGAIN)。这是典型的 accept"惊群"现象。

Linux 2.6 版本之后，通过添加了一个 WQ_FLAG_EXCLUSIVE 标记告诉内核进行排他性的唤醒，即唤醒一个进程后即退出唤醒的过程，解决掉了 accept 惊群效应。

具体分析会在代码注释里面，accept代码实现片段如下：

// 当accept的时候，如果没有连接则会一直阻塞（没有设置非阻塞）
// 其阻塞函数就是：inet_csk_accept（accept的原型函数）  
struct sock *inet_csk_accept(struct sock *sk, int flags, int *err)
{
    ...  
    // 等待连接
    error = inet_csk_wait_for_connect(sk, timeo);
    ...  
}
static int inet_csk_wait_for_connect(struct sock *sk, long timeo)
{
    ...
    for (;;) {  
        // 只有一个进程会被唤醒。
        // 非exclusive的元素会加在等待队列前头，exclusive的元素会加在所有非exclusive元素的后头。
        prepare_to_wait_exclusive(sk_sleep(sk), &wait,TASK_INTERRUPTIBLE);  
    }  
    ...
}
void prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state)  
{  
    unsigned long flags;  
    // 设置等待队列的flag为EXCLUSIVE，设置这个就是表示一次只会有一个进程被唤醒，我们等会就会看到这个标记的作用。  
    // 注意这个标志，唤醒的阶段会使用这个标志。
    wait->flags |= WQ_FLAG_EXCLUSIVE;  
    spin_lock_irqsave(&q->lock, flags);  
    if (list_empty(&wait->task_list))  
        // 加入等待队列  
        __add_wait_queue_tail(q, wait);  
    set_current_state(state);  
    spin_unlock_irqrestore(&q->lock, flags);  
}

唤醒阻塞的 accept 代码片段如下：

// 当有tcp连接完成，就会从半连接队列拷贝socket到连接队列，这个时候我们就可以唤醒阻塞的accept了。
int tcp_v4_do_rcv(struct sock *sk, struct sk_buff *skb)
{
    ...
    // 关注此函数
    if (tcp_child_process(sk, nsk, skb)) {
        rsk = nsk;  
        goto reset;  
    }
    ...
}
int tcp_child_process(struct sock *parent, struct sock *child, struct sk_buff *skb)
{
    ...
    // Wakeup parent, send SIGIO 唤醒父进程
    if (state == TCP_SYN_RECV && child->sk_state != state)  
        // 调用sk_data_ready通知父进程
        // 查阅资料我们知道tcp中这个函数对应是sock_def_readable
        // 而sock_def_readable会调用wake_up_interruptible_sync_poll来唤醒队列
        parent->sk_data_ready(parent, 0);  
    }
    ...
}
void __wake_up_sync_key(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, void *key)  
{  
    ...  
    // 关注此函数
    __wake_up_common(q, mode, nr_exclusive, wake_flags, key);  
    spin_unlock_irqrestore(&q->lock, flags);  
    ...  
}
static void __wake_up_common(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, int wake_flags, void *key)
{
    ...
    // 传进来的nr_exclusive是1
    // 所以flags & WQ_FLAG_EXCLUSIVE为真的时候，执行一次，就会跳出循环
    // 我们记得accept的时候，加到等待队列的元素就是WQ_FLAG_EXCLUSIVE的
    list_for_each_entry_safe(curr, next, &q->task_list, task_list) {  
        unsigned flags = curr->flags;  
        if (curr->func(curr, mode, wake_flags, key)
        && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
        break;
    }
    ...
}

这样，在 linux 2.6 以后的内核，用户进程 task 对 listen socket 进行 accept 操作，如果这个时候如果没有新的 connect 请求过来，用户进程 task 会阻塞睡眠在 listent fd 的睡眠队列上。这个时候，用户进程 Task 会被设置 WQ_FLAG_EXCLUSIVE 标志位，并加入到 listen socket 的睡眠队列尾部(这里要确保所有不带 WQ_FLAG_EXCLUSIVE 标志位的 non-exclusive waiters 排在带 WQ_FLAG_EXCLUSIVE 标志位的 exclusive waiters 前面)。根据前面的唤醒逻辑，一个新的 connect 到来，内核只会唤醒一个用户进程 task 就会退出唤醒过程，从而不存在了"惊群"现象。

Epoll "惊群"现象

虽然accept上已经不存在惊群问题了,但是以目前的服务器架构,都不会简单的使用accept阻塞等待新的连接了,而是使用epoll等I/O多路复用机制。早期的linux,调用epoll_wait后,当有读/写事件发生时,会唤醒阻塞在epoll_wait上的所有进程/线程,造成惊群现象。不过这个问题已经被修复了,使用类似于处理accpet导致的惊群问题的方法,当有事件发生时,只会唤醒等待队列中的第一个exclusive进程来处理。不过随后就可以看到,这种方法并不能完全解决惊群问题。

这里需要区分一下两种不同的情况：

1. 多个进程/线程使用同一个epfd然后调用epoll_wait
2. 多个进程/线程有自己的epfd,然后监听同一个socket

其实也就是epoll_create和fork这两个函数调用的先后顺序问题。第一种情况,先调用epoll_create获取epfd,再使用fork,各进程共用同一个epfd;第二种情况,先fork,再调用epoll_create,各进程独享自己的epfd。

而nginx面对的是第二种情况,这点需要分清楚。因为nginx的每个worker进程相互独立,拥有自己的epfd,不过根据配置文件中的listen指令都监听了同一个端口,调用epoll_wait时,若共同监听的套接字有事件发生,就会造成每个worker进程都被唤醒。

Nginx 的 epoll"惊群"避免

Nginx 中有个标志 ngx_use_accept_mutex，当 ngx_use_accept_mutex 为 1 的时候（当 nginx worker 进程数>1 时且配置文件中打开 accept_mutex 时，这个标志置为 1），表示要进行 listen fdt"惊群"避免。

Nginx 的 worker 进程在进行 event 模块的初始化的时候，在 core event 模块的 process_init 函数中(ngx_event_process_init)将 listen fd 加入到 epoll 中并监听其 READ 事件。Nginx 在进行相关初始化完成后，进入事件循环(ngx_process_events_and_timers 函数)，在 ngx_process_events_and_timers 中判断，如果 ngx_use_accept_mutex 为 0，那就直接进入 ngx_process_events(ngx_epoll_process_events)，在 ngx_epoll_process_events 将调用 epoll_wait 等待相关事件到来或超时，epoll_wait 返回的时候该干嘛就干嘛。这里不讲 ngx_use_accept_mutex 为 0 的流程，下面讲下 ngx_use_accept_mutex 为 1 的流程。

Nginx 解决方案之锁的设计

首先我们要知道在用户空间进程间锁实现的原理，起始原理很简单，就是能弄一个让所有进程共享的东西，比如 mmap 的内存，比如文件，然后通过这个东西来控制进程的互斥。
Nginx 中使用的锁是自己来实现的，这里锁的实现分为两种情况，一种是支持原子操作的情况，也就是由 NGX_HAVE_ATOMIC_OPS 这个宏来进行控制的，一种是不支持原子操作，这是是使用文件锁来实现。

锁结构体

如果支持原子操作，则我们可以直接使用 mmap，然后 lock 就保存 mmap 的内存区域的地址
如果不支持原子操作，则我们使用文件锁来实现，这里 fd 表示进程间共享的文件句柄，name 表示文件名

typedef struct {
#if (NGX_HAVE_ATOMIC_OPS)
    ngx_atomic_t  *lock;
#else
    ngx_fd_t       fd;
    u_char        *name;
#endif
} ngx_shmtx_t;

原子锁创建

// 如果支持原子操作的话，非常简单，就是将共享内存的地址付给loc这个域
ngx_int_t ngx_shmtx_create(ngx_shmtx_t *mtx, void *addr, u_char *name)
{
    mtx->lock = addr;
   return NGX_OK;
}

原子锁获取

TryLock，它是非阻塞的，也就是说它会尝试的获得锁，如果没有获得的话，它会直接返回错误。
Lock，它也会尝试获得锁，而当没有获得他不会立即返回，而是开始进入循环然后不停的去获得锁，知道获得。不过 Nginx 这里还有用到一个技巧，就是每次都会让当前的进程放到 CPU 的运行队列的最后一位，也就是自动放弃 CPU。

原子锁实现

如果系统库支持的情况，此时直接调用OSAtomicCompareAndSwap32Barrier，即 CAS。

#define ngx_atomic_cmp_set(lock, old, new)
    OSAtomicCompareAndSwap32Barrier(old, new, (int32_t *) lock)

如果系统库不支持这个指令的话，Nginx 自己还用汇编实现了一个。

static ngx_inline ngx_atomic_uint_t ngx_atomic_cmp_set(ngx_atomic_t *lock, ngx_atomic_uint_t old,
    ngx_atomic_uint_t set)
{
    u_char  res;
    __asm__ volatile (
         NGX_SMP_LOCK
    "    cmpxchgl  %3, %1;   "
    "    sete      %0;       "
    : "=a" (res) : "m" (*lock), "a" (old), "r" (set) : "cc", "memory");
    return res;
}

原子锁释放

Unlock 比较简单，和当前进程 id 比较，如果相等，就把 lock 改为 0，说明放弃这个锁。

#define ngx_shmtx_unlock(mtx) (void) ngx_atomic_cmp_set((mtx)->lock, ngx_pid, 0)

解决过程

1. 进入ngx_trylock_accept_mutex，加锁抢夺accept权限（ngx_shmtx_trylock(&ngx_accept_mutex)），加锁成功，则调用ngx_enable_accept_events(cycle) 来将一个或多个listen fd加入epoll监听READ事件(设置事件的回调函数ngx_event_accept)，并设置ngx_accept_mutex_held = 1;标识自己持有锁。

2. 如果ngx_shmtx_trylock(&ngx_accept_mutex)失败，则调用ngx_disable_accept_events(cycle, 0)来将listen fd从epoll中delete掉。

3. 如果ngx_accept_mutex_held = 1(也就是抢到accept权)，则设置延迟处理事件标志位flags |= NGX_POST_EVENTS; 如果ngx_accept_mutex_held = 0(没抢到accept权)，则调整一下自己的epoll_wait超时，让自己下次能早点去抢夺accept权。

4. 进入ngx_process_events(ngx_epoll_process_events)，在ngx_epoll_process_events将调用epoll_wait等待相关事件到来或超时。

5. epoll_wait返回，循环遍历返回的事件，如果标志位flags被设置了NGX_POST_EVENTS，则将事件挂载到相应的队列中(Nginx有两个延迟处理队列，(1)ngx_posted_accept_events：listen fd返回的事件被挂载到的队列。(2)ngx_posted_events：其他socket fd返回的事件挂载到的队列)，延迟处理事件，否则直接调用事件的回调函数。

6. ngx_epoll_process_events返回后，则开始处理ngx_posted_accept_events队列上的事件，于是进入的回调函数是ngx_event_accept，在ngx_event_accept中accept客户端的请求，进行一些初始化工作，将accept到的socket fd放入epoll中。

7. ngx_epoll_process_events处理完成后，如果本进程持有accept锁ngx_accept_mutex_held = 1，那么就将锁释放。

8. 接着开始处理ngx_posted_events队列上的事件。

Nginx 通过一次仅允许一个进程将 listen fd 放入自己的 epoll 来监听其 READ 事件的方式来达到 listen fd"惊群"避免。然而做好这一点并不容易，作为一个高性能 web 服务器，需要尽量避免阻塞，并且要很好平衡各个工作 worker 的请求，避免饿死情况，下面有几个点需要大家留意：

1. 避免新请求不能及时得到处理的饿死现象
   工作worker在抢夺到accept权限，加锁成功的时候，要将事件的处理delay到释放锁后在处理(为什么ngx_posted_accept_events队列上的事件处理不需要延迟呢？ 因为ngx_posted_accept_events上的事件就是listen fd的可读事件，本来就是我抢到的accept权限，我还没accept就释放锁，这个时候被别人抢走了怎么办呢？)。否则，获得锁的工作worker由于在处理一个耗时事件，这个时候大量请求过来，其他工作worker空闲，然而没有处理权限在干着急。
2. 避免总是某个worker进程抢到锁，大量请求被同一个进程抢到，而其他worker进程却很清闲。
   Nginx有个简单的负载均衡，ngx_accept_disabled表示此时满负荷程度，没必要再处理新连接了，我们在nginx.conf曾经配置了每一个nginx worker进程能够处理的最大连接数，当达到最大数的7/8时，ngx_accept_disabled为正，说明本nginx worker进程非常繁忙，将不再去处理新连接。每次要进行抢夺accept权限的时候，如果ngx_accept_disabled大于0，则递减1，不进行抢夺逻辑。

Nginx 采用在同一时刻仅允许一个 worker 进程监听 listen fd 的可读事件的方式，来避免 listen fd 的"惊群"现象。

部分引用《什么是惊群，如何有效避免惊群?》