端节点算法学

《端节点算法学》由会员分享，可在线阅读，更多相关《端节点算法学（27页珍藏版）》请在金锄头文库上搜索。

1、端节点算法学端节点算法学是网络算法学在端节点尤其是服务器上的运用。 我们可以认为它是建立高速服务器的一组系统性技术。随着网络功能虚拟化的提出， 将来数据中心绝大部分的网络设备都会在通用服务器上实现，因此端节点算法学的重要性就更突出了。消除不必要的拷贝如果我们跟踪一个网络包从进入网卡到完成处理的整个过程， 会发现网络包在终端中被拷贝了多次，具体场景稍后会看到。为什么我们要把数据拷贝这个问题单独提出来讨论， 是因为在计算机中进行拷贝会消耗两个非常宝贵的资源：内存带宽和内存本身。内存带宽反映了系统读写数据的能力。由于现代计算机中访存是最大的瓶颈，如果 web 服务器处理一个报文涉及到 k 次拷贝，那

2、么这个 web 服务器的吞吐量就可能降至 1/k。计算机中内存的容量是确定的，如果一个报文在内存中存 k 份，则会降低内存的有效容量。能够进入内存或 cache的数据量少了，访问数据的延迟就增大了。所以说数据拷贝是影响计算机系统性能的重要因素。 本章关注如何消除不必要的拷贝（ P1）。一个拷贝如果不是由硬件要求的，该拷贝是不必要的。 比如，网络适配器将收到的数据拷贝到计算机内存， 这是硬件要求的； 然而，应用程序和操作系统之间的拷贝， 主要是由操作系统的结构化产生的要求， 除此之外没有什么特别的理由，这个拷贝是可以考虑消除的。除了拷贝之外，这一章还将讨论其它需要对数据包载荷进行的操作（如计算检

3、查和）。5.1 为什么要拷贝数据我们首先看看在终端中数据的多次拷贝是怎么发生的。 考虑用户向 web 服务器请求一个静态文件，该文件在磁盘上； web 服务器从磁盘中读出文件，发送到网络上。我们关注在此过程中，数据在 web 服务器中的转移过程。图 5.2 给出了涉及到的计算机系统的主要部件和拷贝过程。涉及到的主要硬件为 CPU、存储器、内存总线、 I/O 总线、硬盘和网卡，主要软件为 web 应用程序和内核程序。这里涉及到两个主要的内核子系统，文件子系统和网络子系统。文件子系统负责文件管理，网络子系统负责报文收发和协议处理。为简单起见，图中只画出了一个 CPU（许多服务器有多个处理器） ，并

4、且只关注对静态内容的请求，即文件直接从磁盘中读出。如果请求的是动态内容，web 服务器后面还需要一个数据库，由服务器侧的一个CGI 程序处理请求，从数据库中读数据，构造网页，再传给web 服务器。注意，图中将文件子系统和网络子系统的代码画在处理器中。实际上，这些代码也存放在主存中，由处理器从主存中获取。然而，位于处理器指令cache中的代码可以看成是在处理器中的。一个简单的故事直观上，这个故事是很简单的。首先 web 应用程序通过一个系统调用（如read()）将文件从磁盘读入到它的缓冲区（应用缓冲区） ；然后构造一个 HTTP 响应头，通过一个系统调用（如 write() ）将响应头和缓冲区内

5、容交给网络子系统（ TCP/IP 程序）；网络子系统将数据划分成适当大小的块，加上各层协议头后交给网络适配器发送。如果讲原理，一般就讲到这个程度。一个真实的故事实际上，这个故事的细节要复杂得多。首先，文件一般先从硬盘读入到一个称为文件缓冲区的内核空间，我们称 copy 1。这个做法是值得提倡的，这样随后对该文件的请求就可以直接从内存得到， 而不需要每次都去读硬盘。 所有的 web 服务器都是这么做的，这样可以极大地减小响应时间。其次，文件数据从文件缓冲区拷贝到web 程序的应用缓冲区，我们称 copy 2。接着，web 程序对一个 TCP 套接字执行一个 write() 系统调用。在 writ

6、e() 调用中描述的应用缓冲区被拷贝到一个套接字缓冲区， 这是内核中不同于文件缓冲区和应用缓冲区的另一个缓冲区，这称为 copy 3。最后，每个数据块在加上了各层协议头之后，由驱动程序将数据包拷贝到位于网卡的缓冲区中，发送出去。这称为 copy 4。在传输到网络之前， TCP 程序还要扫描一遍数据，计算TCP 检查和。以上过程涉及到4 次拷贝和 1 次涉及全部包数据的检查和计算。资源消耗情况我们看一下资源消耗情况。不同内存区域之间的拷贝 （copy 2 和 copy 3）需要 CPU 的参与，每个字都要通过内存总线读一次和写一次，是消耗资源最多的。计算 TCP 检查和需对每个字读一次， 最后写

7、一个简单结果， 因此使用内存总线一次。涉及外设的拷贝（ copy 1 和 copy 4），如果由 CPU 来做拷贝（称程序输入输出），其代价与内存区域之间的拷贝一样，每个字都要通过内存总线读、写各一次。如果由设备来做拷贝 （DMA ），则每个字只需通过内存总线读一次或写一次。涉及外设的拷贝还会消耗I/O 总线带宽（ copy 1 和 copy 4）。对服务器吞吐量的影响在 web 服务器的例子中，即使使用了 DMA ，每一个字也要使用内存总线 7 次。因此， web 服务器的吞吐量不会超过 T/7，其中 T 为内存速度和内存总线速度中的较小值。其次，额外的拷贝消耗了内存。在图中，一个文件被存储

8、在文件缓冲区、应用缓冲区和套接字缓冲区。通常 web 服务器希望使用尽可能多的文件缓冲区来避免频繁地访问硬盘。 一个文件存在 3 处，将减少文件缓冲区可用的容量， 降低缓存命中率，从而极大地降低整个服务器的性能。总而言之，多余的拷贝在两个重要的方面损害了服务器的性能：1）由于使用了过多的总线和内存带宽，使得服务器的运行速度低于总线速度； 2）由于使用了过多的内存， 使得服务器不得不大量地去从磁盘读文件， 而不是从主存中读文件。需要注意的是，我们只描述了获取静态内容的情形，实际上相当一部分请求是关于动态内容的。动态内容通常由一个专门的 CGI 程序生成，然后通过某种进程间通信机制交给 web 服

9、务程序去发送，这里又会涉及到一次拷贝。下面我们将讨论这些拷贝，哪些是可以避免的，怎么避免。5.2 利用适配器内存消除copy 4我们首先关注与网络相关的拷贝，即copy 4。为什么需要 copy 4？一个简单的解释是，因为适配器内存位于适配器上，而内核存储空间位于存储子系统，不在同一个硬件上。但是这个理由并不充分。我们知道在一个内存映射的体系结构中，设备的寄存器被映射到一块内存区域， CPU 通过读写这块内存区域与设备通信。因此从理论上说，在一个内存映射的体系结构中，内存可以位于总线上的任何地方。所以，尽管内核存储空间通常是位于存储子系统的，但没有理由认为部分内核空间就不能位于网络适配器中（网

10、络适配器通常包含一定容量的存储器） 。利用网络适配器中已有的存储空间（P4）和内核存储空间放置的自由度（ P13），我们可以将套接字缓冲区放在网络适配器中。 这样应用缓冲区的内容直接拷贝到网络适配器的内存中。如何计算检查和？但是这里有一个问题，网络子系统在收发TCP 包时需要计算TCP 检查和，如果数据在应用缓冲区和适配器之间直接传递，那么TCP 检查和怎么计算呢？这里的一个想法是运用P2c（共享开销）。数据从应用缓冲区拷贝到适配器上的缓冲区，假如这个拷贝由CPU 完成，那么可以让 CPU 捎带着同时计算检查和。比如，使用一个寄存器， 对已经传输的数据进行累加。 但是这个方法有个致命的问题，就

11、是在接收数据包的时候， CPU 边拷贝数据边计算检查和，当发现数据接收错误时，数据已经进入到应用缓冲区中，这是违背 TCP 语义的。所以这个方法从未被实施。后来这个方法被HP 实验室的研究人员采纳，应用到他们的网络适配器（称为 Afterburner）中。数据传输不是由 CPU 完成，而是由网卡通过 DMA 完成。由于 CPU 不参与 DMA 过程，因此检查和计算是由网卡完成的。这种网卡称为 TCP 卸载引擎，它将 TCP 的数据传输下放到网卡上完成，以减轻 CPU 的负担。需要注意的是，考虑到 TCP 连接管理的复杂性， TCP 连接的管理（建立、关闭等）仍由主 CPU 完成，只是将建立好的

12、 TCP 连接移交给网络适配器。这种方法的问题是， 网络适配器需要很大的内存空间和较强的处理器来支持大量的 TCP 连接，网卡成本很高。5.3 消除 copy 3下面考虑消除 copy 3。注意，我们现在是独立地考虑每一种数据拷贝的消除方法，这些措施能否组合使用需要仔细考虑。应用和内核之间需要一次拷贝有两个原因。 （1）应用和内核使用不同的虚拟地址空间，需要通过拷贝传递数据。 但是这个理由不是充分的， 因为完全可以通过内存映射，将套接字缓冲区映射给应用程序使用。 （2）socket API 使用拷贝语义，应用程序在将缓冲区的内容写入套接字（交给网络子系统）后，它可以往缓冲区中写入新的数据。但是

13、 TCP 通常需要缓存数据以备重发，因此 TCP 不能与应用共用一块缓冲区，需要通过数据拷贝来解除应用和内核之间的耦合。第 2 个理由使得拷贝看起来是必要的。如果不能避免拷贝，那我们能够减小拷贝的开销吗？特别是， 如果应用并不需要立即写缓冲区， 那么每次都执行拷贝是否必要？写时拷贝有些操作系统（如 Mac）提供写时拷贝（ copy-on-write）功能，在很多情况下可以避免实际的拷贝。写时拷贝的实现写时拷贝的基础是虚拟内存。程序使用虚拟地址，虚拟地址通过一个页表映射到物理地址，页表用虚拟页号（虚拟地址的高 20 位）进行索引。如果需要的页不在内存中， 硬件产生一个缺页中断， 操作系统将相应的

14、页读入内存。 查找页表的开销可以通过使用TLB 来消除。我们用一个例子说明写时拷贝的实现。假定进程P1 的虚拟页X 映射到物理页 L ，需要复制 X 的内容到进程 P2 的虚拟页 Y 。写时拷贝（续）：不幸的是，许多操作系统（如 UNIX 和 Windows）不提供写时拷贝。但是理解了写时拷贝的原理之后，类似的效果是可以实现的。因为现代计算机都使用虚拟内存， 通过修改页表来避免物理拷贝是能够做到的，只是需要找到一种替代 COW 位的保护机制。（ COW 保护机制采用硬件检测、触发操作系统异常来解决）5.4 优化页面重映射写时拷贝的例子忽略了很多细节， 以致于让人觉得页面重映射是很简单的一个操作

15、，一个大的缓冲区通过一个写页表操作就可以从应用程序传递到内核 （或反过来）。比如在图 5.5 中，假定操作系统希望将进程 P1 的虚拟页 10（VT 10 ）拷贝到进程 P2（如内核）的虚拟页 8（ VT 8），其中 VT 10 指出一个存放包数据的物理页。过于简单的想法是只需要修改 VT 8 的页表表项，使其指向存放包数据的物理页就可以了。这种过于简单的看法是很误导人的。页面重映射的开销有好几个额外的开销被这种简单的描述给掩盖了。（1）多级页表大多数现代的计算机系统使用多级页表映射（至少有两级） ，实际映射时可能要求修改多级页表，由此可能涉及多次写。为了实现跨平台运行， 有些操作系统同时维护了机器无关页表和机器相关页表，则涉及的写操作更多。当页表不在内存中时，