端节点算法学

时间：2020-10-16 05:05:39 来源：蒲公英阅读网 本文已影响人

相关热词搜索：节点 算法

　端节点算法学 端节点算法学是网络算法学在端节点尤其是服务器上的运用。我们可以认为它是建立高速服务器的一组系统性技术。

　随着网络功能虚拟化的提出，将来数据中心绝大部分的网络设备都会在通用服务器上实现，因此端节点算法学的重要性就更突出了。

　消除不必要的拷贝 如果我们跟踪一个网络包从进入网卡到完成处理的整个过程，会发现网络包在终端中被拷贝了多次，具体场景稍后会看到。

　为什么我们要把数据拷贝这个问题单独提出来讨论，是因为在计算机中进行拷贝会消耗两个非常宝贵的资源：内存带宽和内存本身。

　内存带宽反映了系统读写数据的能力。由于现代计算机中访存是最大的瓶颈，如果 web 服务器处理一个报文涉及到 k 次拷贝，那么这个 web 服务器的吞吐量就可能降至 1/k。

　计算机中内存的容量是确定的，如果一个报文在内存中存 k 份，则会降低内存的有效容量。能够进入内存或 cache 的数据量少了，访问数据的延迟就增大了。

　所以说数据拷贝是影响计算机系统性能的重要因素。本章关注如何消除不必要的拷贝（P1）。一个拷贝如果不是由硬件要求的，该拷贝是不必要的。比如，网络适配器将收到的数据拷贝到计算机内存，这是硬件要求的；然而，应用程序和操作系统之间的拷贝，主要是由操作系统的结构化产生的要求，除此之外没有什么特别的理由，这个拷贝是可以考虑消除的。

　除了拷贝之外，这一章还将讨论其它需要对数据包载荷进行的操作（如计算检查和）。

　5.1 为什么要拷贝数据

　我们首先看看在终端中数据的多次拷贝是怎么发生的。考虑用户向 web 服务器请求一个静态文件，该文件在磁盘上；web 服务器从磁盘中读出文件，发送到网络上。我们关注在此过程中，数据在 web 服务器中的转移过程。

　图 5.2 给出了涉及到的计算机系统的主要部件和拷贝过程。涉及到的主要硬件为 CPU、存储器、内存总线、I/O 总线、硬盘和网卡，主要软件为 web 应用程序和内核程序。这里涉及到两个主要的内核子系统，文件子系统和网络子系统。文件子系统负责文件管理，网络子系统负责报文收发和协议处理。

　为简单起见，图中只画出了一个 CPU（许多服务器有多个处理器），并且只关注对静态内容的请求，即文件直接从磁盘中读出。如果请求的是动态内容，web 服务器后面还需要一个数据库，由服务器侧的一个 CGI 程序处理请求，从数据库中读数据，构造网页，再传给 web 服务器。

　注意，图中将文件子系统和网络子系统的代码画在处理器中。实际上，这些代码也存放在主存中，由处理器从主存中获取。然而，位于处理器指令 cache 中的代码可以看成是在处理器中的。

　一个简单的故事

　直观上，这个故事是很简单的。首先 web 应用程序通过一个系统调用（如read()）将文件从磁盘读入到它的缓冲区（应用缓冲区）；然后构造一个 HTTP 响应头，通过一个系统调用（如 write()）将响应头和缓冲区内容交给网络子系统

　（TCP/IP 程序）；网络子系统将数据划分成适当大小的块，加上各层协议头后交给网络适配器发送。如果讲原理，一般就讲到这个程度。

　 一个真实的故事 实际上，这个故事的细节要复杂得多。首先，文件一般先从硬盘读入到一个称为文件缓冲区的内核空间，我们称 copy 1。这个做法是值得提倡的，这样随后对该文件的请求就可以直接从内存得到，而不需要每次都去读硬盘。所有的 web服务器都是这么做的，这样可以极大地减小响应时间。

　其次，文件数据从文件缓冲区拷贝到 web 程序的应用缓冲区，我们称 copy 2。

　接着，web 程序对一个 TCP 套接字执行一个 write()系统调用。在 write()调用中描述的应用缓冲区被拷贝到一个套接字缓冲区，这是内核中不同于文件缓冲区和应用缓冲区的另一个缓冲区，这称为 copy 3。

　最后，每个数据块在加上了各层协议头之后，由驱动程序将数据包拷贝到位于网卡的缓冲区中，发送出去。这称为 copy 4。

　在传输到网络之前，TCP 程序还要扫描一遍数据，计算 TCP 检查和。

　以上过程涉及到 4 次拷贝和 1 次涉及全部包数据的检查和计算。

　资源消耗 情况 我们看一下资源消耗情况。

　不同内存区域之间的拷贝（copy 2 和 copy 3）需要 CPU 的参与，每个字都要通过内存总线读一次和写一次，是消耗资源最多的。

　计算 TCP 检查和需对每个字读一次，最后写一个简单结果，因此使用内存总线一次。

　涉及外设的拷贝（copy 1 和 copy 4），如果由 CPU 来做拷贝（称程序输入输出），其代价与内存区域之间的拷贝一样，每个字都要通过内存总线读、写各一次。如果由设备来做拷贝（DMA），则每个字只需通过内存总线读一次或写一次。

　涉及外设的拷贝还会消耗 I/O 总线带宽（copy 1 和 copy 4）。

　对服务器吞吐量的影响

　在 web 服务器的例子中，即使使用了 DMA，每一个字也要使用内存总线 7次。因此，web 服务器的吞吐量不会超过 T/7，其中 T 为内存速度和内存总线速度中的较小值。

　其次，额外的拷贝消耗了内存。在图中，一个文件被存储在文件缓冲区、应用缓冲区和套接字缓冲区。通常 web 服务器希望使用尽可能多的文件缓冲区来避免频繁地访问硬盘。一个文件存在 3 处，将减少文件缓冲区可用的容量，降低缓存命中率，从而极大地降低整个服务器的性能。

　总而言之，多余的拷贝在两个重要的方面损害了服务器的性能：1）由于使用了过多的总线和内存带宽，使得服务器的运行速度低于总线速度；2）由于使用了过多的内存，使得服务器不得不大量地去从磁盘读文件，而不是从主存中读文件。

　需要注意的是，我们只描述了获取静态内容的情形，实际上相当一部分请求是关于动态内容的。动态内容通常由一个专门的 CGI 程序生成，然后通过某种进程间通信机制交给 web 服务程序去发送，这里又会涉及到一次拷贝。

　下面我们将讨论这些拷贝，哪些是可以避免的，怎么避免。

　5.2 利用适配器内存消除 copy 4

　我们首先关注与网络相关的拷贝，即 copy 4。

　为什么需要 copy 4？一个简单的解释是，因为适配器内存位于适配器上，而内核存储空间位于存储子系统，不在同一个硬件上。

　 但是这个理由并不充分。我们知道在一个内存映射的体系结构中，设备的寄存器被映射到一块内存区域，CPU 通过读写这块内存区域与设备通信。因此从理论上说，在一个内存映射的体系结构中，内存可以位于总线上的任何地方。

　所以，尽管内核存储空间通常是位于存储子系统的，但没有理由认为部分内核空间就不能位于网络适配器中（网络适配器通常包含一定容量的存储器）。

　利用网络适配器中已有的存储空间（P4）和内核存储空间放置的自由度（P13），我们可以将套接字缓冲区放在网络适配器中。这样应用缓冲区的内容直接拷贝到网络适配器的内存中。

　如何计算检查和？

　但是这里有一个问题，网络子系统在收发 TCP 包时需要计算 TCP 检查和，如果数据在应用缓冲区和适配器之间直接传递，那么 TCP 检查和怎么计算呢？ 这里的一个想法是运用 P2c（共享开销）。数据从应用缓冲区拷贝到适配器上的缓冲区，假如这个拷贝由 CPU 完成，那么可以让 CPU 捎带着同时计算检查和。比如，使用一个寄存器，对已经传输的数据进行累加。但是这个方法有个致命的问题，就是在接收数据包的时候，CPU 边拷贝数据边计算检查和，当发现数据接收错误时，数据已经进入到应用缓冲区中，这是违背 TCP 语义的。所以这个方法从未被实施。

　后来这个方法被 HP 实验室的研究人员采纳，应用到他们的网络适配器（称为 Afterburner）中。数据传输不是由 CPU 完成，而是由网卡通过 DMA 完成。由于 CPU 不参与 DMA 过程，因此检查和计算是由网卡完成的。

　这种网卡称为 TCP 卸载引擎，它将 TCP 的数据传输下放到网卡上完成，以减轻 CPU 的负担。需要注意的是，考虑到 TCP 连接管理的复杂性，TCP 连接的管理（建立、关闭等）仍由主 CPU 完成，只是将建立好的 TCP 连接移交给网络适配器。

　这种方法的问题是，网络适配器需要很大的内存空间和较强的处理器来支持大量的 TCP 连接，网卡成本很高。

　5.3 消除 copy 3

　下面考虑消除 copy 3。注意，我们现在是独立地考虑每一种数据拷贝的消除方法，这些措施能否组合使用需要仔细考虑。

　应用和内核之间需要一次拷贝有两个原因。（1）应用和内核使用不同的虚拟地址空间，需要通过拷贝传递数据。但是这个理由不是充分的，因为完全可以通过内存映射，将套接字缓冲区映射给应用程序使用。（2）socket API 使用拷贝语义，应用程序在将缓冲区的内容写入套接字（交给网络子系统）后，它可以往缓冲区中写入新的数据。但是 TCP 通常需要缓存数据以备重发，因此 TCP 不能与应用共用一块缓冲区，需要通过数据拷贝来解除应用和内核之间的耦合。

　第 2 个理由使得拷贝看起来是必要的。如果不能避免拷贝，那我们能够减小拷贝的开销吗？特别是，如果应用并不需要立即写缓冲区，那么每次都执行拷贝

　是否必要？

　写时拷贝

　有些操作系统（如 Mac）提供写时拷贝（copy-on-write）功能，在很多情况下可以避免实际的拷贝。

　写时拷贝的实现 写时拷贝的基础是虚拟内存。程序使用虚拟地址，虚拟地址通过一个页表映射到物理地址，页表用虚拟页号（虚拟地址的高 20 位）进行索引。如果需要的页不在内存中，硬件产生一个缺页中断，操作系统将相应的页读入内存。查找页表的开销可以通过使用 TLB 来消除。

　我们用一个例子说明写时拷贝的实现。假定进程 P1 的虚拟页 X 映射到物理页 L，需要复制 X 的内容到进程 P2 的虚拟页 Y。……

　写时拷贝（续）：

　不幸的是，许多操作系统（如 UNIX 和 Windows）不提供写时拷贝。但是理解了写时拷贝的原理之后，类似的效果是可以实现的。

　因为现代计算机都使用虚拟内存，通过修改页表来避免物理拷贝是能够做到的，只是需要找到一种替代 COW 位的保护机制。

　（COW 保护机制采用硬件检测、触发操作系统异常来解决）

　5.4 优化页 面 重映射

　写时拷贝的例子忽略了很多细节，以致于让人觉得页面重映射是很简单的一个操作，一个大的缓冲区通过一个写页表操作就可以从应用程序传递到内核（或反过来）。

　比如在图 5.5 中，假定操作系统希望将进程 P1 的虚拟页 10（VT 10）拷贝到进程 P2（如内核）的虚拟页 8（VT 8），其中 VT 10 指出一个存放包数据的物理页。过于简单的想法是只需要修改 VT 8 的页表表项，使其指向存放包数据的物理页就可以了。这种过于简单的看法是很误导人的。

　页面重映射的开销 有好几个额外的开销被这种简单的描述给掩盖了。

　（1）多级页表 大多数现代的计算机系统使用多级页表映射（至少有两级），实际映射时可能要求修改多级页表，由此可能涉及多次写。

　为了实现跨平台运行，有些操作系统同时维护了机器无关页表和机器相关页表，则涉及的写操作更多。

　当页表不在内存中时，还需要在内存中为页表分配一个物理页帧，将页表调入物理页帧中，为此还需要修改目录页。

　（若使用 32 位的虚拟地址和 4KB 的页，一个进程可以有约一百万个页，所以页表也要分页。32 位机器一般使用两级页表：每 1024 个页表项组成一个页表，这些页表的起始地址（即页表所在的物理页帧号）保存在一个目录页中；目录页有1024 个表项，目录页的起始地址保存在一个全局寄存器中。虚拟地址的前 10 位用于查找目录页，得到页表的地址；虚拟地址的中间 10 位用于查找页表，得到

　虚拟页的物理页帧号。当包含虚拟页页号的页表已经在内存中时，页面映射只需修改对应的页表项；当页表不在内存中时，还需要在内存中为页表分配一个物理页帧，将页表调入物理页帧中，为此还需要修改目录页。）

　（2）要求锁 页表是共享资源，修改页表必须用锁保护，因此修改页表前后要有请求锁和释放锁的开销。

　（3）刷新 TLB 为节省地址转换时间，常用的页表映射缓存在 TLB 中。当一个新的虚拟页的地址映射写入页表时，相关的 TLB 表项要清除或修正。（TLB 只包括最近用到的虚拟页号，指令和数据页分开记录。TLB 分别保存 64 个最常用的指令和数据的虚拟页号，每个 TLB 项包括一个虚拟页号和相应的物理页帧号。）

　（4）在目标域中分配虚拟内存 需要为目标进程分配一个新的虚拟页（malloc）。新的虚拟页需要向系统去申请，为此，系统需要做一些计算在目标进程中找到一个空闲的页表表项。

　（5）锁住相应的页 物理页可能会被换出到磁盘上。为防止页被换出，页必须被锁住，这也需要开销。

　所有这些开销在多处理器系统中会被放大（以上不少操作都需要加锁，如malloc）。其结果是，尽管页表映射看起来非常好，即无论包大小如何，页面重映射只需常数时间，但这个常数因子实际上是一个很大的开销（Q4），有研究人员在 90 年代早期的实验中证实了这一点。也就是说，如果只是简单地使用页表重映射来避免拷贝，结果可能不像预期的那么好。

　那么怎么办？数据拷贝开销很大，但页面重映射看起来开销也不小，搞不好比拷贝一个数据包的开销还要大。那是不是说页面重映射就不能用了呢？ 好在研究人员并没有放弃这个想法，他们发明了一个称为 fbufs（fast buffers的简称）的操作系统设施，可以消除前 4 种页面映射开销的全部或大部分。

　Fbufs （fast buffers ）

　Fbufs 基于这样的观察：如果一个应用正在通过内核向网络发送大量的数据包，那么一个缓冲区可能会被重用多次。

　方法一：提前分配好需要的包缓冲区，并计算好所有的页面映射信息（P2a），发送时重复使用这些包缓冲区。问题是不好预先估计所要的缓冲区数量。

　方法二：当数据传输开始时才按需分配包缓冲区并计算页面映射（P2b），然后将其缓存起来（P11a）供后续数据包使用。尽管前几个包的延迟较大，但后续的包就免除了页面映射的开销。

　不管哪一种方法，都可以做到“映射一次，重复使用”。当需要传输的数据量很大时，页面映射的开销被平摊，可以认为开销为零。

　为应用分配一组固定的物理页

　为避免用户空间和内核空间之间的拷贝，将一组物理页 P1、P2、……同时映射到内核和应用的页表中，供它们使用。

　考虑到端系统上可能同时运行多个应用。为进行安全隔离，设计者将一个有序的安全域序列（数据包经过的一系列处理程序）定义为一条路径，并为每一条

　路径预留不同的一组物理页。

　图 5.6 是一个路径的例子，以太网软件实现为一个内核级的驱动，TCP/IP 栈实现为一个内核级的安全域，Web 应用实现在应用层。图中存在两条接收路径：（以太网，TCP/IP，web），（以太网，OSI，FTP）。将一定数量的物理页映射给接收路径（以太网、Tcp/IP 和 web 应用），再将另一组物理页映射给另一条接收路径。这样，每一个应用使用一组固定的物理页。

　为使该设计发挥作用，当一个数据包到达时，最底层的驱动（甚至是网络适配器）必须立即判断该数据包要被映射到哪条路径，从而将数据包拷贝到分配给这条路径的物理页中，这个功能称为提前解复用（early demultiplexing）。在图 5.6中，这是通过检查数据包的所有头部来确定的，比如，具有以太帧头、IP 头、TCP 头和端口 80 的包属于路径 1。

　映射到同一个物理页的虚拟页号相同 想一想，在进程间传递缓冲区描述符会有什么问题？理论上，各个进程映射到同一个物理页上的虚拟页号可能不同。比如，第一个进程的虚拟页 10 可能和第二个进程的虚拟页 8 映射到同一个物理页上。这是很麻烦的，因为第二个进程读入 VT 10 的描述符后，它必须要知道它对应了自己的虚拟页 8。

　为避免这种情况，设计者规定映射到同一个物理页的虚拟页号必须相同。为此，系统将将所有进程的虚拟内存中一定数量的起始页预留为 fbuf 页。

　收包处理过程 图中是只有两个安全域的一条路径。进程 1（writer）收到数据包后，从 free fbufs 队列取一个空闲缓冲区的描述符，将数据包写入该空闲缓冲区，然后将该缓冲区的描述符写入 written fbufs 队列；进程 2 从 written fbufs 队列中取包缓冲区描述符，从相应的包缓冲区中读数据处理，将释放的包缓冲区描述符写回到free fbufs 队列。

　到目前为止，接收路径的问题解决了。网卡驱动将数据包装入一个空闲的包缓冲区，包缓冲区的描述符沿着接收路径传递，每个进程访问同一个物理内存页进行数据包处理，数据包处理完后，包描述符归还给驱动程序进行重用，在此过程中没有发生物理拷贝。那么发送路径呢？

　如何添加包头？ 在发送路径上，每一个安全域都要给数据包加上一个包头。然而为了实现安全保护，我们对于每条路径只允许一个写者，其余为读者，这意味着页只能由写者来修改。那么，怎么允许其它进程添加包头呢？

　用 应用如何使用 fbufs ？ 现在还剩下一个重要的问题。大量已有的应用软件是使用标准拷贝语义的socket API 书写的，即应用执行了 write()系统调用后，就可以重用包缓冲区甚至释放了。然而使用了 fbufs 之后，在包缓冲区被其它进程使用完之前，应用是不允许写或释放包缓冲区的。这个问题怎么解决呢？

　用 修改应用 API

　该问题最终的解决方案是：API 不再保持拷贝语义，应用必须判断能不能写

　fbufs。当一个 fbuf 被交给内核后，应用不能写这个 fbuf，直至其被归还到空闲链表中。

　为防止出错或恶意的代码，当一个 fbuf 从应用转递到内核后，内核翻转一个写允许比特，归还 fbuf 时再重新设置该位。如果应用在不允许写的情况下做了一次写操作，则会产生一个异常，应用崩溃，但不会影响其它的进程。

　已有的网络应用软件必须重写吗？

　改变 API 听起来是一个很大的改动，这是否意味着大量已有的网络应用软件必须重写呢？这显然是不可能的，这里有几种解决方案。

　方法一：已有的 API 增加新的系统调用。比如，增广了 fbufs 的 Solaris 除了标准的 write()外，还增加了一个 uf_writer()调用。要求高性能的应用可以用新的调用进行重写。

　方法二：用新的扩展实现一个公共的 I/O 库。

　其实，这个问题最终的考虑不是 API 是否要变，而是修改应用程序来使用该API 有多难。实践表明，将应用移植到类 fbuf 的 API，对应用所做的修改不大，且是局部的。也就是说，Fbufs 方案是可行的。（可行性很重要，一个再好的方案如果推广起来难度大，也没有人使用）

　5.5 使用 RDMA 避免拷贝

　在前面考虑的 web 服务器场景中，web 服务器接收请求，然后将文件传输到网络上，Web 服务器作为接收端并不需要保存请求消息。下面考虑在两个终端之间传输一个大文件，接收端需要保存收到的包。

　用 采用 fbufs 收包 假如采用 fbufs，包到达网卡后被拷贝到一个包缓冲区，包缓冲区描述符在路径上传递，被各个安全域处理，在此过程中无数据拷贝。最后应用进程将数据拷贝到其应用缓冲区中，释放包缓冲区。

　为什么要拷贝？因为文件内容需要保存或被应用处理，而包缓冲区要被重用。（http 请求消息不需要保存，但是文件内容是需要保存的）

　用 采用 TOE 网卡收包 假设采用 TOE 网卡。包到达网卡后，被放入相应的套接字缓冲区进行协议处理和重组。DMA 引擎将数据送入应用缓冲区，向 CPU 发出中断。网卡驱动程序通知内核模块接收数据，交给应用程序（包缓冲区描述符）。应用程序将数据拷贝到文件缓冲区，应用缓冲区重新交给网卡使用。

　这里进行拷贝是为了归还应用缓冲区，为什么要重用应用缓冲区而不是重新分配一个呢？因为准备 DMA 缓冲区是一种耗时的操作，内核需要将应用缓冲区映射到连续的物理页上，将缓冲区的虚拟地址翻译成能够被 DMA 使用的总线地址，然后将地址传给网卡。将一大块应用缓冲区映射到连续的物理页上，并不总是可以做到的，所以 DMA 缓冲区在初始化时准备好，然后重复使用。

　由于给每个套接字分配的缓冲区是有限的，在传输一个大文件的过程中，需要多次中断 CPU 来接收数据和拷贝数据。

　（驱动程序用来管理设备资源，提供设备操作接口、收发数据接口、进行中断处理等。应用程序通过系统调用来使用设备。内核模块是连接应用层和协议处

　理引擎的钩子模块。）

　问 远程直接内存访问 RDMA

　通过网络进行 DMA 的愿景称 RDMA。其意图是……

　也就是说，数据一次传输到位，不需要 CPU 再去移动数据。

　RDMA 要解决的问题 毫无疑问，网络适配器应卸载全部的协议处理，TOE 网卡已经可以做到这一点。除此之外，还有两个问题需要解决：（1）接收端适配器如何知道应将数据放在哪儿？它不能向主机求助，否则就违背了这个意图。（2）如何保证安全，因为恶意的数据包可能会覆盖关键的内存区域。

　5.5.1 VAX 的 的 RDMA

　RDMA 在 VAX 集群中就已经被使用。计算机集群就是用一批廉价的计算机来代替昂贵的大型机，许多 web 服务器实际上就是服务器集群。DEC 引进的 VAX集群是一个成功的商用产品，为可伸缩应用（如数据库应用）提供计算平台。

　该系统的核心是一个 140Mb/s 的网络，称为计算机互联（Computer Interconnect，CL），使用一个以太网风格的协议。用户可以将许多 VAX 计算机和网络硬盘连接到 CL 上。

　VAX 的 的 RDMA 解决方案

　接收方应用进程锁住一些物理页，用作文件传输的目标存储区域，但呈现出来的逻辑视图是由一些地址连续的虚拟页组成的一个缓冲区。然后，缓冲区 ID被传送到发送端应用。

　发送端应用将缓冲区 ID 及包存放的偏移量随同数据包一起发送。

　数据包到达后，接收端适配器根据缓冲区 ID 和偏移量，将数据包内容拷贝到正确的位置。包全部到达后，接收端不需要进行任何的页面重映射。

　5.5.2 RDMA 在 在 SAN 中的应用 VAX 集群引入了一个非常早期的存储区域网络。存储区域网络是一个后端网络，它将大量计算机和网络硬盘连接在一起。

　现在 Infiniband 在数据中心非常火，因为数据中心的节点之间需要传输大量数据。尤其是现在数据中心部署了很多的分布式机器学习应用，如进行深度神经网络的训练，需要高吞吐低延迟的通信支持。

　总之，如果在两台计算机之间需要传输大量的数据，采用 RDMA 是非常高效的方法，它可以节省两侧 CPU 的时间，并且数据存放一次到位，没有多余的拷贝。

　5.6 把避免拷贝技术 扩展到文件系统

　前面我们讨论了如何消除与网络通信有关的拷贝，现在我们重新回到 web 服务器应用场景，考虑文件系统中的拷贝。

　为了提高响应速度，服务器通常将请求的文件先读入一个文件缓冲区（copy 1），然后从文件缓冲区拷贝到应用缓冲区（copy 2），这是必要的，因此 copy 1不在我们的考虑范围内。

　本节的主要目的是消除 copy 2。我们把之前讨论的避免拷贝技术扩展到文件系统，介绍三种消除文件系统冗余拷贝的技术。

　5.6.1 共享内存 方法

　有了前面通过页面重映射消除拷贝的经验（fbufs），我们自然想到是不是也能用内存映射的方法消除 copy 2 呢？ 类 UNIX 操作系统提供一个方便的系统调用，称为 mmap()，它允许应用（如web 服务器）将一个文件映射到它的虚拟内存地址空间。其它操作系统也提供类似的功能。

　概念上，当一个文件被映射到一个应用的地址空间，这个应用就好像在它的内存中缓存了这份文件。实际上，这个缓存的文件只是一组映射。也就是说，如果 web 程序将文件映射到了自己的地址空间，则它和文件 cache 访问的是同一组物理页，从而免除了拷贝的需要。

　Flash Web 服务器 我们看一下 Flash Web 服务器的做法。为加快响应速度，web 服务器将经常用到的文映射到自己的内存空间。

　注意，受到可分配给文件页的物理页数量及页表映射的限制，Flash Web 服务器只能缓存和映射最近常用的文件，不能用来长期存放大量的文件。

　事实上，Flash Web 服务器并没有缓存整个文件，只是缓存了一些文件分片，并使用 LRU（Least Recently Used）策略将最近一段时间未用的文件取消映射。

　只缓存一些文件分片有什么意义呢？可以提高响应速度。如果要访问的文件有一些分片在缓存中（通常是头几个分片），那么这些分片就立即可以发出去，然后再将其余的分片映射进来。

　尚未解决的问题 Flash Web 没有消除 CGI 程序和 web 服务器之间的拷贝。文件缓存只能缓存静态内容，动态网页要由 CGI 程序生成。CGI 程序生成的动态内容通过 UNIX管道传给 web 服务器；典型地，管道要在两个地址空间之间拷贝内容。

　其次，到目前为止我们的方案都没有涉及 TCP 检查和。假如同一个文件不断地被 cache 命中，那么返回的文件分片对所有请求都是一样的，为什么 TCP 检查和不能缓存呢？当然，这里的检查和是指数据部分的检查和，TCP 头是不同的，但是检查和可以增量计算。

　然而，这需要一个能够从数据包内容映射到检查和的高速缓存，这在传统缓存方案中是很低效的。高速缓存实际上是一个 <a, f(a)> 数组，这里 a 为数据包内容，f(a)为检查和。

　合 可以结合 fbufs 和 和 mmap 吗？

　我们介绍了 fbufs，可以消除应用-网络之间的多余拷贝；我们介绍了 mmap，可以消除文件系统的冗余拷贝。那么把 fbufs 和 mmap 结合起来，是不是就能消除 copy2 和 copy3 了呢？

　如果采用 fbufs，所有进程的虚拟内存中一定数量的起始页预留为 fbuf 页，应用进程的应用缓冲区不能被映射到这些物理页上。因此，如果应用将文件映射到其虚拟地址空间的一个缓冲区，那么这个缓冲区不能用 fbuf 发送，必须要有

　一次物理拷贝！

　 5.6.2 IO-Lite

　那么我们能够同时消除 copy2 和 copy3 吗？这里我们介绍一个称为 IO-Lite的方案，它可以一揽子解决前面所有的问题，它可以消除 copy2 和 copy3，可以消除 CGI 程序和 web 服务器之间的拷贝，还可以缓存之前传送过的数据包的检查和。

　由于 fbufs 和 mmap 不能同时使用，所以 IO-Lite 扩展 fbufs 到文件系统，使得可以不必使用 mmap。

　IO-lite 响应 get 请求的步骤

　图 5.10 给出了响应 GET 请求的步骤。当文件第一次从磁盘读入文件系统的高速缓存时，文件页被保存为 IO-Lite buffer。

　当应用通过一个调用来读文件时，没有进行物理拷贝，而是创建了一个缓冲区聚合体（以方便添加包头），指针指向 IO-Lite buffer。

　当应用发送文件给 TCP 进行传输时，网络系统得到一个指向相同 IO-Lite 页的指针。

　为防止出错，IO_Lite 系统为每个缓冲区维护一个引用计数器，仅当所有用户都使用完后才重新分配缓冲区。

　图 5.10 还给出了另外两个优化。应用将常用文件的 HTTP 响应维护在一个高速缓存中，通常只需简单地加上做了最小修改的标准响应。

　其次，IO-Lite 给每个缓冲区分配一个唯一的编号（P12，增加冗余状态），TCP 模块维护一个以缓冲区编号为索引的检查和高速缓冲。当一个文件被传输多次时，TCP 模块在第一次计算了检查和之后，就可以避免再计算检查和。

　注意到这些改变消除了图 5.2 中的 copy2 和 copy3，加快了响应的处理。

　现 实现 IO-Lite 尽管 IO-Lite 的核心思想很简单，但要与文件系统集成需要解决一些困难的问题。

　首先，IO-Lite 必须处理复杂的共享模式，……。

　其次，IO-Lite 页既可能是虚拟内存页又可能是文件页，……. 第三，需要找到一种干净的方法将 IO-Lite 集成到操作系统中，避免对 OS进行外科手术式的大改动。IO-Lite 已经在 UNIX 中实现了。

　5.6.3 使用 I/O 拼接 避免文件系统拷贝 对商用 web 服务器的商业测试表明，基于 IO-Lite 思想的 web 服务器技术领先，但是其它一些 web 服务器也有优秀的性能。

　基于 I/O 拼接的 web 服务器技术也可以消除 copy2 和 copy3。I/O 拼接技术的基本思想是引入一个新的系统调用，将读文件的调用和向网络发送消息的调用合并，达到避免冗余拷贝的目的。

　内核 1 2.1 版本中的 e sendfile 实现

　Sendfile()是在内核 2.1 版本引入的，其运行流程如下，……

　与传统的 read/write 方式相比，sendfile 减少了文件缓冲区到应用缓冲区、再由应用缓冲区到 socket 缓冲区的拷贝，简化为从文件缓冲区直接拷贝到套接字缓冲区，减少了一次拷贝。

　内核 4 2.4 版本之后的 e sendfile 实现

　在内核版本 2.4 之后，修改了文件描述符结构，sendfile 实现了更简单的方式。系统调用方式仍然一样，细节与 2.1 版本不同之处在于，当文件数据被复制到内核缓冲区后，不再将所有数据拷贝到 socket 缓冲区，而是将数据位置和长度的信息保存到 socket 缓冲区，而实际数据通过 DMA 直接发送到适配器。又减少了一次拷贝操作。

　尽管这个机制是成功的，但基于 sendfile 的机制不能很好地推广到与 CGI程序通信。Sendfile() 已用于 apache、nginx、lighttpd 等 web 服务器中。

　5.8 8

　扩展到数据操作之外

　 到目前为止，我们关注的是减少由数据操作引起的内存和总线带宽的消耗。这些技术的共同点是通过避免冗余的读/写来减少对内存和总线的压力。

　由于访存是现代计算机系统的最大瓶颈，接下来我们要进一步扩展我们的视野，除了数据拷贝和数据操作之外，还有哪些因素会影响内存总线的使用效率呢？接下来讨论一个极大地影响总线使用效率的架构因素：cache。

　5.8 8 .1 有效使用 I I- - cache

　 图 5.2 的架构模型回避了一个重要的细节，就是处理器中还有 cache，有一个或多个数据 cache（d-cache），以及一个或多个指令 cache（I-cache）。当需要的数据或指令已经在 cache 中了，就不需要消耗内存带宽了，因此我们要仔细研究一下数据包处理能否从这些 cache 中获得好处。

　一般而言，包数据几乎不能从数据 cache 获得好处，因为包数据几乎不被重用，不存在对同一个内存地址进行重复读写。当然这是指大多数的情况，如果需要对包数据进行加解密、内容反复扫描等操作，是可以从 cache 得到好处的。

　然而，另外两个存储在内存中的东西可以从 cache 获益。处理数据包需要的状态，比如一个连接表项、一个路由表项。对于同一个流中的数据包，处理第一个包查找到的表项如果在 cache 中，则下一个到来的包就可以直接使用该表项。还有一个就是处理数据包的程序代码。

　处理一个包需要的状态一般较小，但协议栈代码要大得多。比如，使用 1995年 NetBSD TCP 实现的协议栈代码为 34KB（不包括应用协议代码）。考虑到以太网上最大的数据包也就 1.5KB，将协议栈代码从内存中读入所需的内存带宽，比拷贝几次数据包所需的内存带宽都要大得多。

　现代计算机的内存虽然越来越大，但 I-cache 的大小并没有显著增大，一些CPU 仍然只有几百 KB，况且计算机中运行的其它程序也要使用 I-cache。因此，处理数据包的协议代码不可能全部都在 I-cache 中，这样高效地利用指令 cache就成为提高性能的一个关键。

　为了高效地使用指令 cache， 我们需要了解 I-cache 的实现特点。

　I I- -e Cache 的实现特点（1 1 ）

　大多数处理器使用直接映射的 I-cache，即用内存地址的低位比特检索I-cache 条目；如果高位比特匹配，就直接从 cache 返回内容；否则进行一个主存访问，并用新的内容替换原来的条目。也就是说，对于 32KB 的 I-cache 而言，内存地址最低 15 位相同的指令被存储在 cache 的同一个位置。

　图5.3给出了这种实现的后果。左图是两个网络函数的代码在内存中的布局，黑色表示不常使用的代码。X 和 Y 是两个经常被访问的代码行，如果它们的地址对 I-cache 的大小取模后相同（即具有相同的低位地址），则 X 和 Y 会被映射到I-cache 的同一位置。如果每一个包的处理都要用到 X 和 Y，它们会被相互地替换出去，即使它们都是经常被使用的代码。

　I I- -e Cache 的实现特点（2 2 ）

　每一条 I-cache 都包含了几条指令，可以看成是一个代码块数组。当取一条指令时，同一个代码块中的全部指令都会被读入。

　这是基于空间局部性假设而做的一个优化：当顺序执行时，后续若干条指令也可能要被执行，一次读入多条指令可以分担开销。

　举例

　这会有什么问题呢？我们知道，包处理代码有许多的条件分支。比如，许多网络代码包含错误检查，比如“if error E do X, else do Z”。Z 几乎从不被执行，但是编译器通常会将 Z 的代码紧接着放在 X 的后面。

　假设 Z 的代码紧接在 X 的后面，如果 X 和 Z 位于同一个指令块中，那么取经常使用的代码 X，会把不经常使用的代码 Z 也取进来，这使得取代码的工作变得低效（做了无用的工作，浪费了内存带宽），也使得 cache 的作用降低了（不常使用的代码在 cache 中，浪费了 cache 空间）。

　问题 与解决方法

　这两个结果和我们对于 cache 的一般预期不同。我们通常认为，经常使用的指令会驻留在 cache 中，不经常使用的指令很少会被调入 cache，而这两个结果恰恰相反。第一个结果是由一个不完美的哈希函数造成的，它导致两个经常被访问的地址发生冲突，经常使用的代码不在 cache 中。第二个结果是由于 cache针对空间局部性优化引起的，导致不经常使用的代码调入 cache。

　以上两个问题都可以通过重新组织代码来减轻，其方法是将经常使用的代码连续放置，避免它们的内存地址发生冲突，也避免将不常使用的代码调入 cache。

　重新组织代码

　当然，如果工作集（即几乎所有的数据包都要使用的代码集合）超过了I-cache 的大小，每次处理一个包都需要将全部代码调入，第一个问题仍会出现。但是，第二个问题仍然能够缓解，即每次只会装载有用的代码，不会将不用的代码装入。

　代码布局的主要思想是通过安排代码在内存中的位置，使得最常使用的代码驻留在 I-cache 中。很少有程序员在写网络代码时会意识到代码布局的问题。

　新的问题

　 尽管我们可以通过代码布局来提高常用代码驻留在 I-cache 中的可能性，但是由于 I-cache 的容量非常有限，并且计算机上的所有程序都要竞争 I-cache，因此，我们几乎可以肯定，处理一个包的协议代码是不可能都装入 I-cache 中的。

　那么问题就来了，如果我们收到一个包，调用协议栈代码把这个包处理完，然后再收下一个包进行处理，这个效率肯定非常的低。拷贝数据包的开销和将代码装入指令 cache 的开销比起来，简直就是微不足道的了。那我们有什么办法可以提高处理效率呢？

　局部性驱动 的协议层处理

　局部性驱动的协议层处理的思想是，只要网络协议栈中每一层的代码可以装入 I-cache，就可以有效地使用 I-cache。方法是每层一次处理多个包，分摊装载 I-cache 的开销（P2c）。

　软件工程方面的考虑

　 采取以上两项优化措施的时候，我们都要先评估一下它们对代码的模块化和可维护性的影响。当我们做系统优化的时候，一定要考虑到工程方面的可行性问题，否则理论上再好的东西都没有意义。

　代码的重新组织可以让编译器来做。比如，可以让程序员对处理错误的代码进行标注，表明哪个分支经常使用，然后由一个增广的编译器为 I-cache 重新组织代码。有文献描述了相应的算法。

　局部性驱动的协议层处理需要修改层间通信方法，相邻两层之间通过队列来传递数据包。当一个协议层被调用时，从自己的读队列中取数据包处理，直至队列取空。当每一层可以重用另一层的包缓冲区（就像 UNIX 的 mbufs）时，该策略工作很好。代码修改量不大。

　5.9 9

　小结

　 本章以 web 应用为例介绍了优化内存和总线带宽使用的技术。

　这些技术大部分需要修改内核和应用，但是这些修改都是局部的，并且基本上是保留模块化特性的

　1 P1 原则的运用

　 本章反复应用 P1 原则来消除明显的浪费，这个浪费就是不必要的读和写，它们消耗了宝贵的内存和总线带宽。

　初看起来原则 P1 显得很空洞，但运用这个原则的困难在于如果不把视野尽可能放宽到整个系统，浪费并不是显而易见的。

　在每个子系统内部，比如应用到内核、内核到适配器、文件系统到应用，并没有浪费内存带宽。

　当我们跟随着一个数据包的处理过程时，我们发现了应用到内核、内核到适配器的冗余拷贝。

　当我们进一步拓展视野看到响应 web 请求的过程时，我们注意到文件系统中还存在冗余。

　当我们进一步拓展视野看到处理一个数据包涉及的所有操作时，我们看到还有冗余的读操作。

　最后，当我们剖析指令加载时，我们发现读入的协议代码可能比数据包大很多倍。

　因此，运用 P1 原则要求对整个系统有一个概要的了解。这听起来很复杂，但是第 2 章提到使用简单的模型（硬件、体系结构、操作系统、协议）就可以做到这一点。比如，I-cache 有许多复杂的变体，但是每个代码块包含多条指令的直接映射 I-cache 这样一个简单模型，对于操作系统的设计者来说并不难于理解和记忆。

　和理论技术的优美和复杂性相比，系统技术（如避免拷贝）可能显得乏味和浅显。然而，系统技术的复杂性并不在于深度（组件本身并不复杂），而在于广度（组件之间的复杂关系）。比如，优化 web 服务器中的内存带宽需要理解 HTTP、文件系统、网络代码、指令 cache 实现等。这正是本课程一开始强调的，网络算法学需要跨学科的、系统的思维能力。