(轉載) VPP-Based-Optimization-for-NGINX

本文轉載自: https://sdic.sjtu.edu.cn/wp-content/uploads/2019/10/VPP-Based-Optimization-for-NGINX.pdf

Background

1. Session lock and session lock table in VPP

在VPP里，一个VPP session可以是一个网络流，可以将这个session理解为原来Linux内核的一个socket。为了处理多线程应用场景中多线程应用竞争socket的情况，Linux内核为socket引入了socket lock来解决socket竞争问题。而VPP将自己的网络协议栈实现在用户态的同时，也将原来Linux内核中的socket lock拿到了用户态去实现。VPP在用户态实现的这个lock就是VPP session lock。

在多线程应用的每个线程使用一个VPP session之前，线程需要首先获得相应的session lock。因此为了让所有线程都能访问到session lock，VPP就将所有的session lock放到线程均能访问到的共享内存中进行管理。而在共享内存中存储VPP session lock的数据结构，就是VPP session lock table。 

如下图。应用线程使用的FD（文件描述符）整数，实际上代表的是session lock table中一个表项的索引值。session lock table中的一个表项供一个VPP session使用，存放了该session的session index和session lock。Session lock table的访问通过lock table read/write lock（读写锁）进行管理。 

  • 当一个线程使用listen session时，它会首先去获取lock table的read lock。然后根据listenFD从lock table中获取listen session的表项，从表项中拿到listen session lock并加锁。加锁后就可以从表项中读出listen session index，并释放lock table的read lock。线程根据获取的listen session index从唯一的一个accept event FIFO中accept一个新的连接，并使用accept控制事件消息通知VPP worker thread线程已accept新的连接。之后线程就可以释放listen session lock。
  • 当一个线程使用普通的网络session时，同理，它也会先去获取lock table的read lock。然后根据使用的FD从lock table中找到相应的表项，并去获取session lock。成功加锁后便可以从表项中读取session index并释放之前的read lock。线程使用session index去实际访问和处理session。结束后便释放session lock。
  • 当一个线程accept一个新的网络连接时，一个新的session就会被创建。这时，新的表项就需要被写入session lock table。因此，当一个新的session被accept时，线程会首先去获取session lock table的write lock。成功获取后便可以新建一个表项，存放该session的sessionlock和session index，并将表项添加进lock table。之后write lock就可以被释放。然后新表项的索引值会以FD整型值的形式提供给线程使用。
VPP通过这套session lock和session lock table结构，为多线程应用提供正确的session访问和处理功能。

2. VPP event queue

VPP event queue支持多种消息类型，可以是I/O消息或控制消息等。如下图。一个VPP eventqueue由两大部分组成。其中一个部分是唯一个的一个message queue，用于存放message元数据。Message queue中的每个元素都存储着它的消息类型和其index索引值。另一个部分是多个data ring。每个data ring用于存储一种类型的消息。VPP worker thread会从message queue中取出一个元素，根据元素中的消息类型找到对应的data ring，并根据消息的index从该data ring中找到实际的消息数据存放位置。

对于应用线程向VPP event queue发送一条消息的过程，我们以线程accept一个新连接时向VPPevent queue发送一条accept控制事件消息为例进行讲解。如图。消息发送步骤如下：

  1. 消息数据块分配：首先，应用线程在控制事件data ring的tail处获得一块data slot供新消息使用。然后更新tail。整个过程由VPP event queue lock保证原子性。所以该步骤只有两个操作，一是读取data ring tail作为消息的index（也就是index = tail），二是对tail做“tail = (tail+ 1) % ring_length”操作。
  2. 消息数据块填充：在这一步骤里应用线程会向上一步分配的data slot中填充数据。由于要填充的data slot位置已经确定并且其他线程不会去使用该slot，因此该步骤可以不保证原子性。
  3. 消息元数据入队：将保存着消息类型和消息index的元数据添加进message queue。这个过程由VPP event queue lock保证原子性。

VPP event queue在设计时并没有将第三步的“消息元数据入队”放在第二步。理由是：如果应用线程向VPP event queue发送消息的三个步骤按照“消息数据块分配→①→消息元数据入队→②→消息数据块填充”来进行，那么VPP worker thread可能会在②处读取message queue中已经入队的元数据进行消息处理。而这时相应的消息数据块还没有被填充，VPP worker thread则会访问到数据块中没有意义的数据。

VPP event queue使用这种“message queue + data ring”的设计能降低添加消息和取出消息时 CPU的开销。Data ring中的空闲slot和已占用slot通过head和tail即可标记。在添加消息或者取出 消息时，只需要简单地更新data ring的tail或者head即可更新VPP event queue。


 3. VPP epoll handling

VPP直接为上层应用提供了名为ldp_epoll_wait()的API，以让应用程序能够使用VPP在用户态实现的epoll事件通知机制。但是VPP只为listen session和普通session提供了用户态的epoll事件通知支持。对于传统Linux内核使用的用于进程间通信的UNIX socket和eventfd，VPP并没有实现类似的功能。因为VPP的关注点是在网络通信而不是进程间通信。如果使用VPP的应用程序还需要使用UNIX socket或者eventfd进行进程间通信，那么它仍然需要使用内核提供的epoll为UNIX socket和eventfd提供事件通知支持。比如NGINX的master向worker进行信息传递时，就使用了socketpair()创建的UNIX socket。这个UNIX socket只能用内核的epoll_ctl进行注册，只能用内核的epoll_wait()进行事件监听。VPP的用户态epoll机制无法支持这个UNIX socket。因此，为了实现原来网络应用仅通过一个epoll_wait() API就能同时监听网络socket和UNIX socket的功能，VPP提供的ldp_epoll_wait() API实际通过循环方式不断穿插调用非阻塞的vppcom_epoll_wait(timeout=0)和非阻塞的epoll_wait(timeout=0)，分别查看VPP用户态的session epoll事件和内核的UNIX socket epoll事件到来情况。

3.1. VPP API ldp_epoll_wait()

ldp_epoll_wait()的详细实现流程如下图。ldp_epoll_wait()在等待所有epoll事件时会遇到四种情况： 

  1. 网络空闲同时无进程间通信：这种情况session epoll事件和UNIX socket epoll事件均未产生。在ldp_epoll_wait()的计时器未超时情况下，vppcom_epoll_wait(timeout=0)和epoll_wait(timeout=0)均不断地返回0，表示一直没有epoll事件到来。计时器超时后，ldp_epoll_wait()会直接返回0告诉应用没有事件产生。因此应用空闲时，应用线程通过ldp_epoll_wait()不断循环调用vppcom_epoll_wait()和epoll_wait()，导致CPU占用一直处于100%。
  2. 有网络事件但无进程间通信：这种情况ldp_epoll_wait()调用vppcom_epoll_wait(timeout=0)时，vppcom_epoll_wait()会直接给出被触发的session epoll事件，然后epoll_wait(timeout=0)将不会再被调用。ldp_epoll_wait()将返回本次触发的所有sessionepoll事件。
  3. 无网络事件但有进程间通信：这种情况ldp_epoll_wait()调用vppcom_epoll_wait(timeout=0)时，vppcom_epoll_wait()返回0表明无session epoll事件。但随后epoll_wait(timeout=0)将直接返回触发的UNIX socket epoll事件。vppcom_epoll_wait()将不会再被调用。ldp_epoll_wait()则直接将本次触发的所有UNIX socket epoll事件返回给应用线程。
  4. 有网络事件也有进程间通信：这种情况一次的ldp_epoll_wait()调用无法将所有的sessionepoll事件和所有的UNIX socket epoll事件同时返回给应用。第一次调用ldp_epoll_wait()时，vppcom_epoll_wait(timeout=0)返回了session epoll事件，这时ldp_epoll_wait()做了一个标记，标记本次返回的是session epoll事件，然后将事件返回给应用。第二次调用ldp_epoll_wait()时，它通过标记发现上次返回的是session epoll事件，于是这次它首先调用epoll_wait(timeout=0)而不是vppcom_epoll_wait()。epoll_wait()返回的所有UNIX socketepoll事件将被ldp_epoll_wait()直接返回给应用，并且标记被更改为本次返回的是UNIXsocket epoll事件。这里标记的作用是：如果没有该标记，每次ldp_epoll_wait()被调用时，都会先实际调用vppcom_epoll_wait(timeout=0)查看session epoll事件的情况；当网络负载较大时，vppcom_epoll_wait()总能先返回事件，导致epoll_wait(timeout=0)一直不能被调用返回UNIX socket的epoll事件；为了防止这种情况，才会引入一个标记让epoll_wait()在某次ldp_epoll_wait()调用时能先于vppcom_epoll_wait()被调用。 


3.2. Implementation of blocking vppcom_epoll_wait()

前面已经提到，vppcom_epoll_wait()是专门监听用户态VPP session epoll事件的函数。像传统Linux的epoll_wait()一样，vppcom_epoll_wait()也实现了阻塞功能。通过设置timeout参数，vppcom_epoll_wait()可以以阻塞或者非阻塞的方式工作。VPP实现其阻塞功能的方式有两种，一种是通过条件变量实现，另一种是通过eventfd实现。

  1. 条件变量实现vppcom_epoll_wait()的阻塞功能
    • vppcom_epoll_wait()使用的epoll事件队列在VPP中名为app event queue。每个app eventqueue有一个Linux内核提供的条件变量condvar。当应用线程调用阻塞的vppcom_epoll_wait()时，线程实际调用了pthread_cond_wait()或pthread_cond_timewait()阻塞在这个条件变量上。当VPP worker thread向app event queue添加epoll事件消息后，VPP worker thread会通过pthread_cond_broadcast()唤醒阻塞在condvar上的应用线程。这时应用线程便可以从app event queue中取出触发的epoll事件。VPP的vppcom_epoll_wait()默认使用基于条件变量的阻塞方式。
  2. eventfd实现vppcom_epoll_wait()的阻塞功能
    • eventfd是Linux内核提供的可用于用户态应用之间进行轻量化通信的事件等待/通知机制。在开启eventfd功能后，每个app event queue会拥有一个eventfd对象。当应用线程调用阻塞的vppcom_epoll_wait()时，线程实际调用了内核的epoll_wait()去监听eventfd的epoll事件。当VPP worker thread向app event queue添加事件消息后，VPP worker thread会去写eventfd以触发其epoll事件，从而将应用线程唤醒。如果要使用基于eventfd的阻塞功能，需要在vcl.conf文件中指定use-mq-eventfd。

Challenge

1. VPP session lock和session lock table的读写锁对NGINX短连接的影响

使用VPP的NGINX worker在accept一个新的连接时，做了两步关键性的操作

  1. 第一步是：先获取listen session的session lock并拿到listen session index，然后从acceptevent FIFO中取出新连接的session index。接着向VPP event queue中发送一条accept控制消息，通知VPP worker thread新连接已被accept。最后会释放listen session lock。
  2. 第二步是：获取session lock table的写锁。将新连接的session index和分配的session lock放入新的session lock table表项中，并将新表项添加至session lock table中。最后释放写锁。新表项的索引被作为FD传给NGINX worker使用。
这两步的操作对于多个NGINX worker并行地accept短连接有很大的影响。如下图。影响原因如下：
  1. 第一步的影响：NGINX是多进程-单线程应用。NGINX在做fork()时，VPP为NGINX的每个新的worker进程都分配了一个accept event FIFO。虽然每个进程都有自己独立的accept eventFIFO，但是当一个进程获取了listen session lock时，其他进程没法操作自己的accept eventFIFO，也没法向VPP event queue发送accept控制消息。只有当持有listen session lock的进程完成了accept event FIFO的操作，发送了accpet控制消息，并释放了listen session lock之后，其他进程才有机会竞争到listen session lock并完成自己相应的操作。
  2. 第二步的影响：一方面，当一个NGINX worker进程做accept时拿到了session lock table的写锁，其他进程accept新连接时将被阻塞（无法获取写锁），而且正要做session数据读写（比如read(FD)或者write(FD)）的进程由于无法获取session lock table的读锁，也将被阻塞。另一方面，只要有任意一个进程因为要做session数据读写而持有session lock table的读锁时，其他任何进程想要accept新连接时都因无法获得写锁而被阻塞。

因此，上述listen session lock和session lock table读写锁带来的竞争问题，导致了NGINX在多worker情况下处理大量短连接时性能的下降。NGINX worker越多，处理短连接时锁竞争的影响就会越大。

因为NGINX是多进程-单线程应用，且VPP实现的fork()机制让每个NGINX worker进程都拥有一个 独立的accept event FIFO，因此每个worker进程处理自己的accept event FIFO时并不需要listen session lock的保护，而且worker与worker进程之间不会竞争session也使得session不需要 session lock的保护。所以，我们可以为NGINX优化掉VPP的session lock（包括listen session lock），从而优化掉session lock table，以消除listen session lock和session lock table的读写锁 带来的锁竞争问题。

我们使用VPP session index透传将session lock和session lock table优化掉



2. 去锁引起的VPP event queue消息乱序问题

在background一章中我们提到了VPP event queue的设计和这种设计的目的。VPP event queue通过data ring的head和ring来标记空闲和非空闲的data slot。只要简单更新data ring的tail和head便可实现消息的分配和释放，从而简化VPP event queue的操作，节省CPU。而这种设计一定要保证data slot的分配顺序与最后相应的消息元数据进入message queue的顺序一致。否则，message queue中的消息元数据一旦乱序，VPP event queue按照乱序的消息进行处理时会通过更新data ring head错误地将未处理的消息的data slot标记为空闲slot，导致这个实际有未被处理数据的slot在后面可能被分配给别的消息使用。

当NGINX worker在向VPP event queue发送accept控制事件时，它要按照“消息数据块分配→消息数据块填充→消息元数据入队”的顺序完成操作。原来这三个过程在有listen session lock保护的情况下是一次性且顺序地完成的，中间不会与其他NGINX worker的这三个过程发生交错。但是当我们优化掉listen session lock后，不同NGINX worker的这三个步骤可能会发生交错，导致VPPevent queue的message queue里的消息元数据乱序。如下图。【按图补充描述。】

而上述这个accpet控制消息乱序的情况其实是较少会发生的。通过实验我们发现，在使用4个Nginx worker和1个VPP worker thread的情况下，每100~300个左右的accpet控制消息中才会出现1个乱序的消息。也就是说在没有listen session lock的情况下，大部分时候accept控制消息不会乱序，很少才会出现1个乱序的消息。因此，如果为了保证很少才可能出现的乱序消息的顺序而把原来优化掉的session lock再引回来，会得不偿失。本来优化掉listen session lock是为了消去其引起的锁竞争，现在又要将其引回来做消息保序肯定是不行的。所以我们需要寻找其他不引入锁的低开销方式保证VPP event queue的消息顺序。我们使用基于token的消息保序机制来保证其消息顺序。

3. ldp_epoll_wait()占用CPU和频繁进行系统调用的问题

由于ldp_epoll_wait()通过循环不断调用非阻塞的vppcom_epoll_wait(timeout=0)和非阻塞的epoll_wait(timeout=0)分别检查session和UNIX socket的epoll事件，因此在NGINX worker空闲时，即使没有session和UNIX socket的epoll事件，它还是会100%占用CPU。这会导致不必要的能源和CPU资源浪费。

另外，在background章节中我们提到ldp_epoll_wait()使用一个标记来防止网络高负载时epoll_wait()长期无法被调用的情况。这会导致，在NGINX worker处理大量网络流时，所有的ldp_epoll_wait()调用中，每一个调用vppcom_epoll_wait(timeout=0)的ldp_epoll_wait()会穿插一个调用epoll_wait(timeout=0)的ldp_epoll_wait()。vppcom_epoll_wait()负责处理实际的网络流事件，但是epoll_wait()的调用只为了检查UNIX socket的epoll事件。实际上，NGINX worker在正常工作时并不会有UNIX socket的epoll事件产生。只有网络管理员想要停止、重启或者更新NGINX的时候，才会让NGINX master向worker通过UNIX socket发送进程间消息。因此，ldp_epoll_wait()目前通过这个标记实现的工作机制会让NGINX worker在正常工作时频繁地调用内核的epoll_wait()。这样频繁的系统调用会占用vppcom_epoll_wait()能够处理网络事件的时间。

所以，我们希望能够做到：

  1. NGINX worker进程在闲置时能够被阻塞，而不是繁忙地占用CPU。
  2. NGINX worker在处理高负载的网络请求时，不会频繁地调用epoll_wait(timeout=0)进行高开销的检查。但同时NGINX worker又要能在NGINX worker关闭、重启、更新时及时处理UNIXsocket的epoll事件。

对第一种情况，我们可以基于vppcom_epoll_wait()的阻塞机制实现NGINX worker在闲置时被阻塞的功能。至于是选择基于条件变量还是基于eventfd的阻塞机制，我们通过实验发现，使用基于条件变量的方式在请求处理速率和延迟方面要优于基于使用eventfd的方式。这也是vppcom_epoll_wait()默认使用条件变量的原因。所以我们选择基于条件变量实现NGINX worker闲置时阻塞功能。

对第二种情况，我们不让NGINX worker主动调用高开销的epoll_wait(timeout=0)检查UNIXsocket epoll事件。而是在NGINX master向NGINX worker发送进程间通信消息时，让master主动通过worker阻塞时使用的条件变量来唤醒worker进程。由于安全性考虑，VPP将这个条件变量放在只有使用该变量的那个NGINX worker和VPP worker thread共享的内存中，而其他NGINXworker和NGINX master无法直接访问该变量。因此我们还要基于共享内存，引入中间变量去间接唤醒NGINX worker。具体方法会在实现章节进行介绍。


Design Approach

1. VPP session index passthrough

我们不再将VPP session lock table里表项的索引号码作为FD传递给NGINX worker使用。我们在这里使用了VPP session index透传机制，将VPP session index直接传递给NGINX worker作为FD来使用。当新连接被accept时，新session的session index不会再放入新建的一个session locktable表项中，而是直接传给了NGINX worker。为了读写而使用一个session时，session index也不再从session lock table表项中获取，而是通过读取FD获得。NGINX worker使用listen session时，也是直接通过透传的FD拿到listen session index。虽然每个NGINX worker使用的listensession的index是相同的，但是NGINX worker使用listen session时，会从自己独立拥有的acceptevent FIFO中获取新的accpet事件。

Session index透传让我们能优化掉session lock和session lock table。这样NGINX worker在做accept()时不会再使用listen session lock，并且读写session和创建session时也不会再使用session lock table的读写锁。因为避开了listen session lock和session lock table读写锁导致的锁竞争，多个NGINX worker在处理大量短连接请求时的请求处理速率会得到提升。

2. Token-based VPP event queue message order-preserving

我们使用基于token的方式完成VPP event queue中accept控制消息的保序。一个NGINX worker向VPP event queue中发送accept控制消息时，在分配消息的数据块这一步骤中会获得一个带有编号的token。这个编号的值是上一个token值加1。如果这个token是第一次分配，那么这个token的值被设为一个指定的初始值F。这样NGINX worker就可以继续在分配到的数据块中进行数据操作。最后在将包含该数据块index的消息元数据添加到message queue的队尾时，messagequeue的token checker会检查要入队的消息的token编号是否等于应入队编号。Token checker持有的应入队编号的初始值也是F。如果检查结果为真，则消息可入队，并且应入队编号自增1，用于下一次检查。如果检查结果为假，则当前NGINX worker会以自旋的方式循环进行相同的检查，直到token checker的应入队编号被更新，使得检查结果为真。此时消息可入队。由于乱序消息的发生概率为数百分之一，因此token编号检查结果为假的概率也是数百分之一。因此，自旋检查的发生概率很低，引入的开销会远小于使用listen session lock的开销。同时考虑到token编号检查的结果大概率为真，我们使用分支预测来优化token编号检查，从而优化CPU pipeline的处理。

3. 基于共享内存和条件变量的统一epoll事件管理

我们为每个NGINX worker创建了一个名为“中间人”的线程。该线程也拥有一个条件变量，我们称之为中间人条件变量。中间人条件变量通过共享内存能被其他NGINX worker或者NGINX master访问。中间人线程会阻塞在自己的中间人条件变量上。NGINX worker在使用ldp_epoll_wait()时会阻塞在vppcom_epoll_wait()中实现的app event queue的条件变量上。

  1. 当有网络session事件产生时，VPP worker thread会signal这个app event queue条件变量从而将NGINX worker唤醒。NGINX worker会检查唤醒者标记。此时唤醒者标记为VPP，则NGINX worker最后会从app event queue中获取session的epoll事件。
  2. 当NGINX master向某个NGINX worker发送进程间通信事件时，master会通过共享内存signal该NGINX worker的中间人线程的中间人条件变量。当该中间人线程被唤醒后，它会访问自己所在的NGINX worker进程的app event queue条件变量并signal它，从而间接将NGINX worker唤醒。随后NGINX worker检查唤醒者标记，发现其为non-VPP。于是NGINXworker会实际调用epoll_wait()取得UNIX socket的epoll事件。
由于检查唤醒者标记会对CPU pipeline处理有性能上的影响，并且对NGINX而言绝大情况下唤醒者标记为VPP而非non-VPP，因此我们在这里也引入了分支预测来对该检查进行优化。这样，NGINX worker在空闲时会阻塞，并且在处理网络请求时也不会频繁通过epoll_wait()陷入到内核来检查UNIX socket的epoll事件。

Implementation


(注: 到這裡就沒了，我也好奇接下來寫什麼)

留言

張貼留言