第二部分 端节点算法学.ppt

1、第二部分 端节点算法学,端节点算法学,端节点算法学： 网络算法学在端节点（尤其是服务器）上的运用，是建立高速服务器的一组系统性技术 随着网络功能虚拟化的提出，将来数据中心中绝大部分的网络设备都会在通用服务器上实现 端节点算法学研究如何减少以下开销： 数据拷贝（chapter 5） 控制转移（chapter 6） 解复用（chapter 7） 定时器（chapter 8） 其它一般性协议处理任务 （chapter 9）,第五章 拷贝数据,消除不必要的拷贝（P1）,网络报文在收发和处理的过程中，通常会被拷贝多次 计算机中的数据拷贝消耗两个宝贵的资源： 内存带宽：如果处理一个报文涉及k次拷贝，系统吞

2、吐量可能降至1/k 内存：如果一个报文在内存中被保存k份，有效内存容量降至1/k 本章关注如何消除不必要的拷贝： 一个拷贝如果不是由硬件要求的，该拷贝是不必要的 本章还将讨论其它需要对数据包载荷进行的操作,5.1 为什么要拷贝数据,应用场景： 用户向web服务器请求一个静态文件 服务器从磁盘读出文件，发送到网络上 两个子系统： 文件子系统 网络子系统,一个简单的故事,直观上，这是一个简单的故事： web应用程序通过一个系统调用（读文件），将文件从磁盘读入到它的缓冲区中 构造一个HTTP响应头，通过一个系统调用（写套接字），将响应头和缓冲区内容交给网络子系统 网络子系统将数据划分成适当大小的块，

3、加上各层协议头，交给网络驱动程序,一个真实的故事,Copy 1： 硬盘文件缓冲区（内核空间） Copy 2： 文件缓冲区应用缓冲区 （用户空间） Copy 3： 应用缓冲区套接字缓冲区（内核空间） Copy 4： 套接字缓冲区网卡 TCP程序还需要扫描一遍数据，计算TCP检查和,资源消耗情况,拷贝和TCP检查和计算：每个字需要穿过内存总线79次！不同内存区域之间的拷贝（copy 2，copy 3）： 每个字都要通过内存总线读一次和写一次 计算TCP检查和：每个字都要通过内存总线读一次 涉及外设的拷贝（copy 1，copy 4）： 如果由CPU做拷贝（PIO）：每个字都要通过内存总线读一次和写

4、一次 如果由设备做拷贝（DMA）：每个字只需通过内存总线读一次或写一次 涉及外设的拷贝都需要消耗I/O总线带宽,对服务器吞吐量的影响,在上面的例子中： Web服务器吞吐量不超过T/7，T为内存速度和内存总线速度中的较小值 有效的文件缓冲区大小仅为总容量的1/3 多余的拷贝在两个方面损害了服务器的性能： 由于使用了过多的总线和内存带宽，服务器的运行速度远远低于总线速度 由于使用了过多的内存，服务器不得不大量地从磁盘而不是主存读文件 如果请求动态内容，还要增加一次拷贝（CGI程序web服务器）,请求动态内容,Step 6：CGI 程序将构造好的网页文件，通过进程间通信机制传给web服务器程序，涉及

5、一次拷贝,5.2 消除copy 4,为什么需要copy 4？简单的解释： 适配器内存和内核存储空间不在同一个硬件上,消除 Copy 4,在一个内存映射的体系结构中， 设备寄存器被映射到一块内存区域，CPU通过读写这块内存区域与设备通信 理论上，内存可以位于总线上的任何地方，包括在适配器中解决方案： 利用网络适配器中已有的存储空间（P4，利用系统组件），以及内核存储空间放置的自由度（P13，利用自由度），将套接字缓冲区放在网络适配器中 应用缓冲区的内容直接拷贝到网络适配器的内存中,如何计算TCP检查和？,如何计算检查和？,Witless方法（P2c，共享开销）： CPU读入每个字时，捎带计算检查

6、和 出错的数据包可能被写入应用缓冲区，与TCP语义不符（所以该方法从未被实施）Afterburner适配器（TCP offloading engine）： 数据传输由网卡通过DMA完成，网卡使用特殊的硬件在传输数据的同时计算检查和 网络适配器的成本 vs 性能：网络适配器需要很大的内存空间和较强的处理器来支持大量的TCP连接，网卡成本可能较高,5.3 消除 Copy 3,为什么需要copy 3？ 应用和内核使用不同的虚拟地址空间（不是必要的） 应用和内核之间需要通过数据拷贝解除耦合（必要的）如果拷贝不能避免，那么能够减小拷贝的开销吗？,写时拷贝（copy-on-write）,当应用程序对内核执

7、行一个写时拷贝时，OS将内核缓冲区映射到应用缓冲区的物理内存页上当应用程序试图修改其缓冲区时，内核进行真正的拷贝，但这种情况很少发生,写时拷贝的实现,举例： 假定进程 P1 的虚拟页 X 映射到物理页 L上，需要复制 X的内容到进程 P2 的虚拟页 Y 当P1对 X 进行写时拷贝时： 内核修改页表，令 Y 指向物理页 L 将 X 表项的COW保护位置位 当P1试图写页X时： 硬件读X的COW位，发现置位，产生一个异常 操作系统将物理页 L拷贝到物理页 L，清除 X 的COW位，令 X 指向 L，Y 继续指向 L,写时拷贝的实现（续）,对于不提供写时拷贝功能的操作系统（如UNIX和Windows

8、），也可以基于虚拟内存实现类似的功能： 可以通过修改页表避免物理拷贝 需要找到一种替代COW位的保护机制,5.4 优化页面重映射,对页面重映射过于简单的看法： 只需修改P2的页表（一次写操作），令VP 8指向存放包的物理页,（X）,页面重映射的开销,修改多级页表： 实际映射可能要求修改多级页表，涉及多次写 要求锁操作： 修改页表前后要有请求锁和释放锁的开销 刷新TLB： 新的地址映射写入页表时，相关的TLB表项要清除或修正,在目标域中分配虚拟内存： 系统要在目标进程中找到一个空闲的页表表项 锁住物理页： 为防止页被换出，必须锁住物理页以上开销在多处理器系统中会被放大！,如果只是简单地使用页表重

9、映射来避免拷贝，结果可能不像预期的那么好。,Fbufs（fast buffers）,基本观察： 如果一个应用正在发送大量的数据包，那么一个包缓冲区可能会被重用多次 方法一： 提前分配好需要的包缓冲区，并计算好所有的页面映射信息（P2a），发送时重复使用这些包缓冲区 方法二： 数据传输开始时分配包缓冲区并计算页面映射，然后将其缓存起来（P11a），消除后续包的页面映射开销 基本思想：映射一次，重复使用,为应用分配一组固定的物理页,为避免内核空间和用户空间之间的拷贝，将一组物理页P1、P2、Pk 同时映射给内核和应用。 数据包经过的一系列处理程序构成一个有序的安全域序列，定义为一条路径 为每一条路

10、径预留固定的一组物理页，数据包到达时立即确定其所属的路径（提前解复用）,在路径上传递包缓冲区描述符,对于每条路径，适配器有一个空闲缓冲区链表： 适配器把数据包写入一个空闲缓冲区，将缓冲区描述符传给接收路径上的下一个进程 最后一个进程将用完的缓冲区交还给第一个进程，缓冲区重新回到空闲缓冲区链表,实现单向路径,有序的安全域序列是一条单向路径： 规定第一个进程是writer，其余进程是reader（为了提供一定的保护级别） 给第一个进程的页表表项设置写允许位，给其它进程的页表表项设置只读位,映射到同一个物理页的虚拟页号相同,在将物理页映射给路径上的进程时，应将物理页映射到相同页号的虚拟页上 为此，将

11、所有进程的虚拟内存中一定数量的起始页预留为 fbuf 页,收包处理过程,P1从free fbufs队列取一个空闲缓冲区，写入数据包，将缓冲区的描述符写入written fbufs队列 P2从written fbufs队列取包缓冲区描述符，读相应的包缓冲区 P2将释放的包缓冲区描述符写回free fbufs队列,如何添加包头？,在发送路径上，每一个安全域都要给数据包加上一个包头。 然而，为了实现保护，每条路径只允许一个writer，其余为reader。问题：怎么允许其它安全域添加包头呢？,定义数据包为聚合数据结构,将数据包定义为一个带有指针的聚合数据结构，每个指针指向一个fbuf。 给数据包添加

12、包头，就是将一个fbuf添加到聚合数据结构中。,Fbufs总结,Fbufs运用了虚拟内存映射的思想，但通过在大量数据包之间分摊页面映射开销而做得更高效： 包缓冲区映射一次，重复使用很多次 消除了一般情形中的页表更新有人扩展了Fbufs思想，并实现在Sun Solaris操作系统中 DPDK也运用了“一次映射，重复使用”的思想,应用如何使用Fbufs？,大量已有的应用软件是根据拷贝语义的API书写的 然而采用fbufs后，在包缓冲区被其它进程使用完之前，应用不允许写或释放包缓冲区,修改应用API,大量已有的应用软件是根据拷贝语义的API书写的 然而采用fbufs后，在包缓冲区被其它进程使用完之前

13、，应用不允许写或释放包缓冲区解决方案：API 不再保持拷贝语义，应用在写缓冲区之前必须进行判断 安全的实现方法： 当一个fbuf从应用传递到内核后，内核翻转写允许比特，归还fbuf时再重新设置该位。,已有的网络应用软件必须重写吗？,方法一： 给已有的API增加新的系统调用，要求高性能的应用使用新的系统调用进行重写。 方法二： 用新的扩展实现一个公共的I/O库，链接到该库的应用不需要修改，就可以得到性能提升。实践表明，将应用移植到类fbuf的API，对应用所做的修改不大，且是局部的。,5.5 使用RDMA避免拷贝,考虑在两个计算机之间传输一个大文件： 采用fbufs 采用TOE网卡,采用fbuf

14、s接收文件,包到达网卡后，被拷贝到一个包缓冲区中 包缓冲区描述符在路径上传递，各安全域处理包 应用程序将包数据拷贝到文件缓冲区，释放包缓冲区,采用TOE网卡接收文件,包到达网卡后，被送入套接字缓冲区进行协议处理和重组 DMA控制器将数据送入应用缓冲区，向CPU发出中断 驱动程序通知内核模块接收数据，交给应用 应用拷贝数据到文件缓冲区，应用缓冲区重新交给网卡使用,直接内存访问（DMA）,在上述两种方法中，都要求CPU参与数据拷贝 ，占用了CPU的时间使用DMA在外设和内存之间传输数据，不需要CPU的参与： CPU设置DMA（给出数据的存放地址、长度等） DMA控制器完成数据传输 DMA控制器通过

15、中断通知CPU传输完成能否在两台计算机的内存之间直接传输数据，而不需要CPU参与？,远程直接内存访问（RDMA）,RDMA的愿景： 数据在两台计算机的主存之间直接传输，不需要CPU参与到数据传输的过程中 两个网络适配器协作地从一个主存读数据，然后写入另一个主存,RDMA需要解决的问题,除了需要网卡执行TCP/IP协议外，RDMA还需解决两个问题： 接收端适配器如何知道应将数据放在哪儿？（不能求助CPU） 如何保证安全？（发送进程不能随意写目标终端的内存）,VAX集群 的RDMA,RDMA在VAX集群中已经被使用，VAX集群为可伸缩应用（如数据库应用）提供计算平台： 系统核心是一个140Mb/s

16、的网络（称Computer Interconnect，CL），使用一个以太网风格的协议 用户可以将许多VAX计算机和网络硬盘连接到CLRDMA的需求背景： 在远程硬盘和VAX机的内存之间有效传输大量数据 要求包含文件数据的包在进入目的适配器之后，直接到达它的存放位置,传统网络的接收端,接收端应用提前将一些映射好的页放入一个队列，交给网络适配器使用到达网卡的数据包被依次放入这些页中（数据包可能乱序到达）接收完数据包后，CPU做一个重映射（使得在应用看来，数据按顺序存放在一个地址连续的缓冲区中）。若文件很大，重映射的开销很大。,VAX 的 RDMA 解决方案,接收端应用锁住一些物理页，用作文件传输

17、的目的存储区域（其呈现出来的逻辑视图是由地址连续的虚拟页组成的一个缓冲区），缓冲区名字被发送给发送端应用发送端应用将缓冲区名字及包存放的偏移量，随同数据包一起发送到接收端接收端适配器根据缓冲区名字和偏移量，将数据存放到指定的缓冲区（不需要页重映射）,如何保证安全？,允许将一个携带缓冲区ID的网络包直接写入内存，是一个明显的安全隐患。为降低安全风险， 缓冲区ID中包含一个难以猜测的随机串（防止伪造） VAX集群只在本集群内部可信的计算机之间使用RDMA传递数据,RDMA在SAN中的应用,存储区域网（Storage Area Network，SAN）： 一种后端网络，将大量计算机和网络硬盘连接在一

18、起目前有好几种这样的技术，都使用了RDMA的思想： Fiber Channel（FC） Infiniband iSCSI,5.6 把避免拷贝技术扩展到文件系统,Copy 1是必要的考虑消除copy 2,5.6.1 共享内存方法,类UNIX操作系统提供一个系统调用mmap()，允许应用（如web服务器）将一个文件映射到自己的虚拟地址空间。概念上，当一个文件被映射到一个应用的地址空间，这个应用就好像在自己的内存中缓存了这份文件。当然，这个缓存的文件只是一组映射。如果Web程序将文件映射到自己的地址空间，则它和文件cache访问的是同一组物理页（免除了拷贝）。,Flash Web服务器,Web应用程

19、序将经常用到的文件映射到自己的内存空间，以避免copy 1和copy 2。受到可分配给文件页的物理页数量及页表映射的限制，Flash Web服务器只能缓存和映射最近常用的文件。由于同样的限制，Flash Web服务器只是缓存了一些文件分片（通常是文件的头几个分片），并使用LRU策略将一段时间未用的文件unmap。,尚未解决的问题,Flash Web 不能避免web服务器与CGI进程之间的拷贝： CGI程序生成的动态内容通过UNIX管道传给web服务器； 典型地，管道要在两个地址空间之间拷贝内容。一个被访问多次的文件，不能缓存检查和,由 fbufs 和 mmap() 想到的问题,fbufs可以消

20、除copy 3 mmap()可以消除copy 2Q：能否将 fbufs 和 mmap() 结合起来使用，同时消除 copy2和copy3 ？,可以结合 fbufs 和 mmap 吗？,在mmap中，应用选择缓冲区的地址和格式 在fbufs中，内核选择缓冲区的地址和格式如果应用将文件映射到其虚拟地址空间的一个缓冲区，这个缓冲区不能用fbuf（内核地址空间）发送，必须要有一次物理拷贝！当消除copy 2时，copy 3不能避免！,5.6.2 IO-Lite,IO-Lite推广 fbufs 至包含文件系统，从而不必使用 mmap。IO-Lite可以一揽子解决前面所有的问题： 同时消除copy 2和c

21、opy 3 消除CGI程序和web服务器之间的拷贝 缓存传送过的数据包的检查和,IO-Lite 的主要思想,IO-Lite 借用了 fbufs 的主要思想： 为同一条路径上的进程映射相同的物理页，实现只读共享 推迟创建路径的缓冲区 使用缓冲区聚合以允许添加包头,IO-Lite 响应 Get 请求,IO-Lite 响应 Get 请求的步骤,当文件第一次从磁盘读入文件系统的高速缓存时，文件页被保存为IO-Lite buffer。 当应用通过一个系统调用读文件时，创建一个缓冲区聚合体，指针指向IO-Lite buffer。 当应用发送文件给TCP时，网络子系统得到一个指向相同IO-Lite页的指针。

22、 应用将常用文件的HTTP响应头维护在一个高速缓存中。 IO-Lite给每个缓冲区分配一个编号，TCP模块维护一个以缓冲区编号为索引的检查和高速缓存。,实现零拷贝的管道,IO-Lite也可以用来实现一个消除了拷贝的改良型管道程序（传递IO-Lite buffer的指针而不是拷贝）将改良后的管道应用到CGI程序和web服务器之间，可以消除冗余的拷贝,实现IO-Lite,IO-Lite必须处理复杂的共享模式： 应用程序、TCP程序和文件服务器等均可能有指向IO-Lite buffer的缓冲区。 IO-Lite必须实现一个复杂的替换策略： IO-Lite页既可能是虚拟内存页又可能是文件页 需将标准的

23、页替换规则和文件缓存替换策略集成在一起。 找到一种干净的方法将IO-Lite集成到OS中 IO-Lite已经在UNIX中实现了,5.6.3 使用I/O拼接避免文件系统拷贝,I/O拼接的基本思想： 引入一个新的系统调用sendfile()，允许内核将读文件的调用和向网络发送消息的调用合并 文件到socket传输的传统方法需两次系统调用：read (file, tem_buf, len); write (socket, tmp_buf, len); 使用sendfile()传输文件到socket：sendfile (socket, file, len);,内核2.1版本的sendfile实现,调用

24、sendfile()时： 文件数据先被拷贝到内核中的文件缓冲区 然后从文件缓冲区拷贝到内核中的socket缓冲区 最后从socket缓冲区拷贝到适配器 与read/write方式相比，减少了一次拷贝,内核版本2.4之后的sendfile实现,调用sendfile()时： 文件数据先被拷贝到内核中的文件缓冲区 将记录数据位置和长度的信息保存到socket缓冲区 数据通过DMA通道直接发送到适配器 消除了copy 2 和 copy 3基于sendfile的机制不能推广到与CGI程序通信 Sendfile() 已用于apache、nginx、lighttpd等web服务器中,5.7 扩展到拷贝之外,

25、除数据拷贝外，其它涉及包中所有数据的操作也是高开销操作，如检查和计算、格式转换等： 需要CPU参与 需要使用内存总线将拷贝循环扩展到包括检查和计算： 利用load和store之间的空周期做累加计算 不增加任何额外的开销,Integrated Layer Processing（ILP）,除检查和之外，其它数据密集的操作能否都集成到拷贝循环中？ 整合层次处理（ILP）的主要思想： 对同一个数据包进行多种数据操作时，将这些操作整合在一个循环中，避免对包中的数据进行多次的读和写（P1）。整合层次处理会有什么问题？,ILP面临的问题,问题一： 不同操作需要的信息一般来自不同的层次，将不同层次的代码整合在

26、一起而不牺牲模块化特性极其困难 问题二： 不同操作可能需要在不同长度的数据块上以及数据包的不同部位进行 问题三： 有些操作可能是相互依赖的。比如，如果数据包的TCP检查和验证失败，就不应当对包进行解密操作,ILP面临的问题（续）,问题四： 过分提高整合度可能降低代码的局部性，增大指令cache的miss率，反而产生不良的后果 结论： ILP很难实现（问题1问题3） ILP可能性能不佳（问题4） ILP可能完全没有必要（若包数据需要被处理几次，则数据很可能驻留在cache中）目前只有检查和计算被整合在数据拷贝过程中,5.8 扩展到数据操作之外,消除数据拷贝和整合数据操作，其技术共同点都是避免冗余

27、的读/写操作，以减少对内存总线的压力。还有哪些因素会影响内存总线的使用呢？ Cache的使用效率 DMA或PIO的选择,5.8.1 有效使用 I-cache,处理器包含一个或多个数据cache，以及一个或多个指令cache： 一般而言，包数据几乎不能从 d-cache 获得好处 处理数据包需要的状态可以从d-cache 获益 处理数据包的程序代码可以从 I-cache 获益代码和状态都可能竞争内存带宽，相比而言，代码对内存带宽的竞争更严重： 处理一个包需要的状态一般较小，比如一个连接表项 协议栈处理的代码大得多，而I-cache的容量一般很小 高效地利用I-cache是提高性能的一个关键,I-

28、Cache的实现特点（1）,大多数处理器使用直接映射的I-cache： 内存地址的低位比特用来检索I-cache条目 如果高位比特匹配，直接从I-cache返回内容 若不匹配，进行一个主存访问，用新的内容替换原来的条目 问题： 被映射到I-cache同一位置的代码会被轮流替换出去，即使它们都是经常使用的代码。,I-Cache的实现特点（2）,每一条I-cache包含多条指令： 当取一条指令时，同一个代码块中的全部指令都会被读入。（基于空间局部性假设而优化）问题： 不常用的代码会被读入I-cache，如果它与常用代码在一个块中。,举例,许多网络代码包含错误检查，比如：if error E do

29、X, else do Z虽然 Z 几乎从不被执行，但是编译器通常会将 Z 的代码紧跟在 X 的后面。如果 X 和 Z 位于同一个指令块中，取经常使用的代码 X，会把不经常使用的代码 Z 也取进来，浪费了内存带宽和cache空间。,问题与解决方案,指令cache没有很好地反映时间局部性： 经常使用的代码不一定在cache中：由一个不完美的映射函数引起 不常使用的代码可能被经常调入cache：由cache对空间局部性的优化引起如何解决以上问题？ 重新组织代码，将经常使用的代码连续放置,重新组织代码,如果工作集超过了I-cache的大小，第一个问题仍会出现，但会减少，而第二个问题能够得到很大程度的缓

30、解 代码布局的基本思想：通过优化代码在内存中的位置，使得经常使用的代码驻留在I-cache中,新的问题,处理包的协议代码肯定无法全部装入指令cache： I-cache的容量非常有限 计算机上的所有程序都要竞争I-cache 问题： 如果每处理一个包，就要将全部的协议代码装入I-cache一次，效率太低！ 拷贝数据包的开销和将代码装入I-cache的开销比起来，简直就是微不足道！,局部性驱动的协议层处理,基本思想（若每一层协议代码可以装入I-cache）： 每个协议层一次处理多个包，分摊装载 I-cache的开销 每一批处理的包数量越多，I-cache的使用越高效 具体实现时，应能动态调整批处

31、理的大小,软件工程方面的考虑,代码重新组织可以让编译器来做： 程序员对不常使用的代码分支进行标注，由编译器为I-cache重新组织代码。局部性驱动的协议层处理需修改层间通信方法： 如果协议代码使用一个过程调用将数据包传递给上（下）一层，则代码修改为将数据包加入上（下）一层的一个包队列中。 当一个协议层被调用时，从自己的读队列中取数据包，直至队列取空。,5.8.2 DMA还是PIO？,PIO： 需要CPU参与，完成内存-外设之间的数据传输需要使用内存总线两次 DMA: 不需要CPU参与，且内存-外设之间的数据传输只需要使用内存总线一次DMA一定好于PIO 吗？,DMA or PIO？,如果将数据

32、传输和数据处理结合起来看，DMA的优势并不是那么明显！ PIO需要CPU参与，内存-外设的数据传输需要使用两次内存总线，但易于整合其它功能（如检查和计算） DMA不需要CPU参与，内存-外设的数据传输仅使用内存总线一次，但不易于整合其它功能（如CPU需要读入数据计算检查和）,DMA和PIO都要关注d-cache,PIO 和 DMA 都存在 d-Cache 失效的问题： 当使用 PIO 或 DMA 时，数据都会进入 d-cache 如果数据马上被处理，d-cache的使用很高效 如果数据到来很久后才被使用，则是对d-cache的一种浪费，并且会降低cache命中率使用DMA还是PIO，应视具体情

33、况而定,5.9 小结,本章以web应用为例介绍了优化内存和总线带宽使用的技术，主要包括： 使用适配器内存消除 copy 4 使用fbufs消除copy 3 使用mmap消除copy 2 使用IO-Lite、sendfile消除 copy2 和copy 3 整合拷贝和检查和计算到一个循环中 通过代码重新布局、局部性驱动的协议层处理优化I-cache的使用,本章使用的技术以及主要的原则,P1原则的运用,本章反复运用原则P1（避免显而易见的浪费）来消除不必要的读、写操作 运用这个原则的困难在于，如果不把视野尽可能放宽到整个系统，浪费并不是显而易见的 运用P1原则要求对整个系统有一个概要的了解，使用简单的模型（硬件、体系结构、操作系统、协议）就可以做到这一点 系统技术的复杂性并不在于深度，而在于广度 （涉及多领域的知识）,作业,阅读论文“Network Stack Specialization for Performance”，介绍其中Sandstorm web server的要点。包括以下内容： 该论文做了什么 为什么做：背景，现状 怎么做：主要思路，关键措施 评估方法与效果：实验怎么做，与谁比，效果怎样 你的思考：启发，评论，作业提交：10月16日,