《第二部分端节点算法学.ppt》由会员分享，可在线阅读，更多相关《第二部分端节点算法学.ppt（72页珍藏版）》请在三一办公上搜索。
1、第二部分 端节点算法学,端节点算法学,端节点算法学：网络算法学在端节点（尤其是服务器）上的运用，是建立高速服务器的一组系统性技术。研究如何减少以下开销：数据拷贝（chapter 5）控制转移（chapter 6）解复用（chapter 7）定时器（chapter 8）其它一般性协议处理任务（chapter 9）,第五章 拷贝数据,消除不必要的拷贝（P1）,计算机中额外的拷贝消耗两个宝贵的资源：内存带宽：如果处理一个消息涉及k次拷贝，系统吞吐量可能降至1/k内存：如果一个消息在内存中存k份，有效内存容量降至1/k一个拷贝如果不是由硬件要求的，该拷贝是不必要的。消除多余的拷贝使得软件接近实现硬件的
2、潜力，是网络算法学的目标之一。,5.1 为什么要拷贝数据,应用场景：用户向web服务器请求一个文件；服务器从磁盘读出文件，发送到网络上。,资源消耗情况,拷贝和TCP检查和计算都要消耗内存总线带宽。不同内存区域之间的拷贝（copy 2，copy 3）：每个字都要通过内存总线读一次和写一次。计算TCP检查和：需对每个字读一次。涉及外设的拷贝（copy 1，copy 4）：如果由CPU做拷贝（PIO）：每个字都要通过内存总线读一次和写一次。如果由设备做拷贝（DMA）：每个字只需通过内存总线读一次或写一次。涉及外设的拷贝还消耗I/O总线带宽。,对服务器吞吐量的影响,在上面的例子中：Web服务器吞吐量不
3、超过T/7，T为内存速度和内存总线速度中的较小值。有效的文件缓冲区大小仅为总容量的1/3。多余的拷贝在两个方面损害了服务器的性能：由于使用了过多的总线和内存带宽，服务器的运行速度低于总线速度。由于使用了过多的内存，服务器不得不大量地从磁盘而不是主存读文件。,请求动态内容,5.2 消除 Copy 4,为什么需要copy 4？适配器内存位于适配器上，而内核存储空间位于存储子系统中。理论上，在一个内存映射的体系结构中，内存可以位于总线上的任何地方，包括在适配器中。利用网络适配器中已有的存储空间（P4，利用系统组件）和内核存储空间放置的自由度（P13，利用自由度），可以将部分内核空间放在网络适配器中。
4、,如何计算检查和？,Witless方法（P2c，共享开销）：CPU读入每个字时，捎带计算检查和。Afterburner适配器（TCP offloading engine）：数据传输由网卡通过DMA完成，网卡使用特殊的硬件在传输数据的同时计算检查和。缺点：网络适配器需要很大的内存空间来支持大量的高速TCP连接，网卡成本很高。在Witless方法中，出错的数据包可能写入应用缓冲区。,5.3 消除 Copy 3,应用和内核之间需要一次拷贝有两个原因：应用程序在write()之后可能修改其缓冲区，而TCP需要缓存数据以备重发，应用和内核之间通过数据拷贝可以解除耦合。应用程序和内核程序使用不同的虚拟地址
5、空间，需要通过拷贝来传递数据。,写时拷贝的原理,写时拷贝（copy-on-write）：当应用程序对内核执行一个写时拷贝时，通过修改一些描述符，将内核缓冲区映射到应用缓冲区的物理内存页上。当应用程序试图修改其缓冲区时，内核进行真正的拷贝（P2b），但这种情况很少发生。这里运用了Lazy Evaluation（P2b）来优化预期情形（P11）。,使用写时拷贝的示意图,写时拷贝的实现,举例：假定进程 P1 的虚拟页 X 映射到物理页 P，现操作系统要复制 X的内容到进程 P2 的虚拟页 Y。当对 X 进行写时拷贝时：内核修改页表，令 Y 指向物理页 P将 X 表项的COW保护位置位当应用试图写页X
6、时：硬件读X的COW位，发现置位，产生一个异常。操作系统将物理页 P 拷贝到物理页 P，清除 X 的COW位，令 X 指向 P，Y 继续指向 P。,写时拷贝的实现（续）,对于不提供写时拷贝功能的操作系统（如UNIX和Windows）：可以通过修改页表避免物理拷贝需要找到一种替代COW位的保护机制（硬件检测、触发操作系统异常）,5.4 优化页面重映射,对页面映射过于简单的看法是，只需修改进程2的页表，使VP 8指向存放包数据的物理页。（X）,页面重映射的开销,修改多级页表：实际映射可能要求修改多级页表，涉及多次写。要求锁操作：修改页表前后要有请求锁和释放锁的开销。刷新TLB：当新的地址映射写入页
7、表时，相关的TLB表项要清除或修正。在目标域中分配虚拟内存：系统要在目标进程中找到一个空闲的页表表项。锁住物理页：为防止页被换出，必须锁住物理页。,Fbufs（fast buffers）,基本观察：如果一个应用正在通过内核向网络发送大量的数据包，那么一个缓冲区可能会被重用多次。方法一：提前分配好包缓冲区并计算好所有的页面映射信息（P2a），避免实际传输时的许多映射开销。方法二：当数据传输开始时计算页面映射（P2b），然后将其缓存起来（P11a），消除后续包的页面映射开销。推迟建立映射比预先映射更适合突发流量。,实现原理,利用共享内存，将一组物理页P1、P2、Pk 同时映射给内核和应用。一般地，
8、将一个有序的安全域序列定义为一条路径，为每一条路径预留不同的一组物理页。,提前解复用（early demultiplexing）,当数据包到达时，底层驱动通过检查数据包的所有头部确定一条完整的路径（提前解复用）。对于每条路径，适配器有一个空闲缓冲区链表：适配器把数据包写入一个空闲缓冲区，将缓冲区描述符传给接收路径上的下一个进程。最后一个进程将用完的缓冲区交还给第一个进程，缓冲区重新回到空闲缓冲区链表。,单向路径的实现,为什么路径是单向的？我们假定每条路径上的第一个进程是writer，其余进程是reader，显然这是不对称的。可以提供一定的保护级别。如何实现单向路径？给第一个进程的页表表项设置写
9、允许位，给其它进程的页表表项设置只读位。,避免不必要的一般性（P7）,在将物理页映射给路径上的进程时，同一个物理页映射到同一个虚拟页上。将所有进程的虚拟内存中一定数量的起始页预留为 fbuf 页。,如何添加包头？,在发送路径上，每一个安全域都要给数据包加上一个包头。然而，为了实现保护，每条路径只允许一个writer，其余为reader。问题：怎么允许其它安全域添加包头呢？,定义数据包为聚合数据结构,将数据包定义为一个带有指针的聚合数据结构，每个指针指向一个fbuf。给数据包添加包头，就是将一个fbuf添加到聚合数据结构中。,修改应用API,大量已有的应用软件是根据拷贝语义的API书写的。然而采
10、用fbufs后，在包缓冲区被其它进程使用完之前，应用不允许写或释放包缓冲区。解决方案：API 不再保持拷贝语义，应用必须判断能不能写缓冲区。安全的实现方法：当一个fbuf从应用传递到内核后，内核翻转写允许比特，归还fbuf时再重新设置该位。,已有的网络应用软件必须重写吗？,方法一：已有的API增加新的系统调用，要求高性能的应用使用新的系统调用进行重写。方法二：用新的扩展实现一个公共的I/O库，链接到该库的应用不需要修改，就可以得到性能提升。实践表明，将应用移植到类fbuf的API，对应用所做的修改不大，且是局部的。,5.5 使用RDMA避免拷贝,通过以太网在两个工作站之间传输1MB的文件：发送
11、端：文件被划分成一系列数据块，封装在以太帧中传输。接收端：CPU处理每一个帧，进行协议处理，将数据拷贝（可能通过像fbufs的零拷贝接口）到应用缓冲区。使用DMA在磁盘和内存之间传输1MB数据：CPU设置DMA，告知磁盘数据的写入地址；数据传输结束后，磁盘通过中断通知CPU。,什么是RDMA,RDMA的愿景：数据在两台计算机的主存之间直接传输，而不需要两端CPU对数据包进行逐个处理。两个网络适配器协作从一个主存读数据，然后写入另一个主存。RDMA需要解决两个问题：接收端适配器如何知道应将数据放在哪儿？如何保证安全？,5.5.1 VAX Cluster 的RDMA,VAX Cluster为可伸缩
12、应用（如数据库应用）提供计算平台：系统核心是一个140Mb/s的网络（称CL），使用一个以太网风格的协议。用户可以将许多VAX计算机和网络硬盘连接到CL。RDMA的需求背景：在远程硬盘和VAX机的内存之间有效传输大量数据。要求包含文件数据的包在进入目的适配器之后，直接到达它的存放位置。,传统网络的接收端,接收端应用将一些页（如页1、2、3）放入一个队列交给适配器，用于接收应用1到来的包。假设数据包的到达顺序为包1、包3、包2，则这些包被依次放入页1、2、3。数据包接收完后，CPU做一个重映射（若文件很大，重映射的开销很大）。,VAX 的 RDMA 解决方案,接收端应用锁住一些物理页，用作文件传
13、输的目的存储区域，将缓冲区名字传送到发送端应用。发送端应用将缓冲区名字及包存放的偏移量随同数据包一起发送。（P10，在包头中传递线索）接收端适配器根据缓冲区名字和偏移量，将数据存放到指定的缓冲区（不需要页重映射）。为实现RDMA，网络适配器必须实现传输层协议。,如何保证安全？,允许一个携带缓冲区ID的网络数据包直接写入内存，是一个明显的安全隐患。为降低安全风险，缓冲区ID中包含一个难以猜测的随机串。VAX Cluster只在本集群内部可信的计算机之间使用RDMA传递数据。,5.5.2 RDMA在SAN中的应用,存储区域网（Storage Area Network，SAN）：一种后端网络，用于将
14、大量的计算机和网络硬盘连接在一起。目前有好几种这样的技术：Fiber Channel（FC）InfinibandInternet Small Computer System Interface（iSCSI）,Fiber Channel,FC的目标之一是将工作站与本地硬盘之间的标准接口SCSI扩展到较长距离。FC使用了现代网络技术，比如用交换机连接点-点光纤链路，使得速度更高，距离跨度更大。FC增加了一些安全措施：允许将网络虚拟化为一些区域，一个区域中的节点不能访问其它区域中节点的内存。增加了认证要求。,5.6 把避免拷贝技术扩展到文件系统,考虑消除copy 2,5.6.1 共享内存方法,类UN
15、IX操作系统提供一个系统调用mmap()，允许应用（如web服务器）将一个文件映射到自己的虚拟地址空间。概念上，当一个文件被映射到一个应用的地址空间，这个应用就好像在自己的内存中缓存了这份文件。如果Web程序将文件映射到自己的地址空间，则它和文件cache访问的是同一组物理页（免除了拷贝）。,Flash Web服务器,Web应用程序将经常用到的文件映射到自己的内存空间，以避免copy 1和copy 2。受到可分配给文件页的物理页数量及页表映射的限制，Flash Web服务器只能将这些映射的文件当成是一个高速缓存（cache）。Flash Web服务器只是缓存了一些文件分片，并使用LRU策略将一
16、段时间未用的文件unmap。,尚未解决的问题,Flash Web 不能避免web服务器与CGI进程之间的拷贝：CGI程序生成的动态内容通过UNIX管道传给web服务器；典型地，管道要在两个地址空间之间拷贝内容。一个被访问多次的文件，不能缓存检查和：传统的缓存方案需要从数据包内容映射到检查和，很低效。,可以结合 fbufs 和 mmap 吗？,可以结合 fbufs 和 mmap 吗？,在mmap中，应用选择缓冲区的地址和格式。在fbufs中，内核选择缓冲区的地址和格式。,可以结合 fbufs 和 mmap 吗？,在mmap中，应用选择缓冲区的地址和格式。在fbufs中，内核选择缓冲区的地址和格式
17、。如果应用使用其虚拟地址空间的一个缓冲区映射了一个文件，这个缓冲区不能用fbuf（内核地址空间）发送，必须要有一次物理拷贝！,可以结合 fbufs 和 mmap 吗？,在mmap中，应用选择缓冲区的地址和格式。在fbufs中，内核选择缓冲区的地址和格式。如果应用使用其虚拟地址空间的一个缓冲区映射了一个文件，这个缓冲区不能用fbuf（内核地址空间）发送，必须要有一次物理拷贝！当消除copy 2时，讨厌的copy 3又出现了！,5.6.2 IO-Lite,IO-Lite推广 fbufs 至包含文件系统，使得不必使用 mmap。IO-Lite 借用了 fbufs 的主要思想：为同一条路径上的进程映射
18、相同的物理页，实现只读共享；推迟创建路径的缓冲区；使用缓冲区聚合以允许添加包头。,IO-Lite 响应 Get 请求,IO-Lite 响应 Get 请求的步骤,当文件第一次从磁盘读入文件系统的高速缓存时，文件页被保存为IO-Lite buffer。当应用通过一个调用读文件时，创建一个缓冲区聚合体，指针指向IO-Lite buffer。当应用发送文件给TCP时，网络系统得到一个指向相同IO-Lite页的指针。应用将常用文件的HTTP响应维护在一个高速缓存中。IO-Lite给每个缓冲区分配一个编号，TCP模块维护一个以缓冲区编号为索引的检查和高速缓存。,实现零拷贝的管道,IO-Lite也可以用来实
19、现一个消除了拷贝的改良型管道程序。将改良后的管道应用到CGI程序和web服务器之间，可以消除冗余的拷贝。,实现IO-Lite,IO-Lite必须处理复杂的共享模式：多个应用、TCP代码和文件服务器均可能有指向IO-Lite buffer的缓冲区。IO-Lite必须实现一个复杂的替换策略：IO-Lite页既可能是虚拟内存页又可能是文件页需将标准的页替换规则和文件缓存替换策略集成在一起。找到一种干净的方法将IO-Lite集成到OS中,5.6.3 使用I/O拼接避免文件系统拷贝,I/O拼接的基本思想：引入一个新的系统调用sendfile()，允许内核将读文件的调用和向网络发送消息的调用合并。文件到s
20、ocket传输的传统方法（4次拷贝）：read(file,tem_buf,len);write(socket,tmp_buf,len);使用sendfile()传输文件到socket：sendfile(socket,file,len);,内核2.1版本的sendfile实现,调用sendfile()时：文件数据先被拷贝到内核中的文件缓冲区；然后从文件缓冲区拷贝到内核中的socket缓冲区；最后从socket缓冲区拷贝到适配器。与read/write方式相比，减少了一次拷贝。,内核版本2.4之后的sendfile实现,调用sendfile()时：文件数据先被拷贝到内核中的文件缓冲区；将记录数据位
21、置和长度的信息保存到socket缓冲区；数据通过DMA通道直接发送到适配器。消除了copy 2 和 copy 3基于sendfile的机制不能推广到与CGI程序通信。,I/O Splicing,5.7 扩展到拷贝之外,利用load和store之间的空周期做累加计算，不需额外开销，拷贝循环可以扩展到包括检查和计算。,Integrated Layer Processing（ILP）,整合层次处理（ILP）的主要思想：对同一个数据包进行多种数据操作时，将这些操作整合在一个循环中，避免对包中的数据进行多次的读和写（P1）。,ILP面临的问题,问题一：不同操作需要的信息一般来自不同的层次，将不同层次的代
22、码整合在一起而不牺牲模块化特性是极其困难的。问题二：不同操作可能需要在不同长度的数据块上以及数据包的不同部位进行。,ILP面临的问题（续）,问题三：有些操作可能是相互依赖的。比如，如果数据包的TCP检查和验证失败，就不应当对包进行解密操作。问题四：过分提高整合度可能降低代码的局部性，增大cache miss率，反而产生不良的后果。,ILP的前景,ILP很难实现，且超过一定数量的操作整合在一起可能会降低性能。特别是，如果包数据被使用几次，它可能驻留在d-cache中，使得整合操作完全没有必要。因此，除了整合拷贝-检查和计算之外，在整合其它操作方面，学术界和工业界一直没有跟进。,5.8 扩展到数据
23、操作之外,消除数据拷贝和整合数据操作，其技术共同点都是避免冗余的读/写操作，以减少对内存总线（以及I/O总线）的压力。还有哪些因素会影响内存总线的使用呢？Cache的使用效率DMA或PIO的选择,5.8.1 有效使用 I-cache,处理器有一个或多个数据cache，以及一个或多个指令cache。包数据几乎不能从 d-cache 获得好处。处理数据包的程序代码可以从 I-cache 获益。处理数据包需要的状态可以从d-cache 获益。代码和状态都可能竞争内存带宽，其中代码对内存带宽的竞争更严重：处理一个包需要的状态一般较小（但减小状态仍是必要的）协议栈处理的代码大得多,（1）代码布局,代码在
24、内存中的布局是一个可以利用的自由度（P13）。代码布局的主要思想：通过安排代码在内存中的位置优化常见情形（P11），使得最常使用的代码驻留在I-cache中,I-Cache的实现特点（1）,大多数处理器使用直接映射的I-cache：内存地址的低位比特用来检索I-cache条目；如果高位比特匹配，直接从I-cache返回内容；若不匹配，进行一个主存访问，用新的数据替换原来的条目。问题：被映射到I-cache同一位置的代码会被轮流替换出去，即使它们都是经常使用的代码。,I-Cache的实现特点（2）,每条I-cache包含多条指令：当取一条指令时，同一个代码块中的全部指令都会被读入。（基于空间局部
25、性假设而优化）问题：不常用的代码会被读入I-cache，如果它与常用代码在一个块中。,举例,许多网络代码包含错误检查，比如：if error E do X,else do Z虽然 Z 几乎从不被执行，但是编译器通常会将 Z 的代码紧跟在 X 的后面。如果 X 和 Z 位于同一个指令块中，取经常使用的代码 X，会把不经常使用的代码 Z 也取进来，浪费了内存带宽和cache空间。,重新组织代码,解决方案：重新组织代码，将经常使用的代码连续放置。比如，将Z的代码放置到远离X的地方。这里运用了两条原则：代码在内存中的位置是一个可以利用的自由度（P13）优化常见情形（P11）,（2）局部性驱动的协议层处
26、理,基本思想：每个协议层一次处理多个包，分摊装载 I-cache的开销每一批处理的包数量越多，I-cache的使用越高效。具体实现时，应能动态调整批处理的大小。,（3）软件工程方面的考虑,代码重新组织可以让编译器来做：程序员对不常使用的代码分支进行标注，由编译器为I-cache重新组织代码。局部性驱动的协议层处理需修改层间通信方法：如果协议代码使用一个过程调用将数据包传递给上（下）一层，则代码修改为将数据包加入上（下）一层的一个包队列中。当一个协议层被调用时，从自己的读队列中取数据包，直至队列取空。,5.8.2 DMA还是PIO,PIO需要CPU参与，但易于整合其它功能。DMA不需要CPU参与
27、，但也不易于整合其它功能。PIO 和 DMA 都存在 d-Cache 的失效问题：当使用 PIO 或 DMA 时，数据都会进入 d-cache。如果数据马上被处理，cache的使用很高效。如果数据到来很久后才被使用，则是对d-cache的一种浪费，并且会降低cache命中率。使用DMA还是PIO没有定论，最好视具体情况而定。,5.9 小结,本章以web应用为例介绍了优化内存和总线带宽使用的技术，主要包括：使用适配器内存消除 copy 4 使用fbufs消除copy 3使用mmap消除copy 2使用IO-Lite、sendfile消除 copy2 和copy 3整合拷贝和检查和计算到一个循环中通过代码布局、局部性驱动的协议层处理优化I-cache的使用,本章使用的技术以及主要的原则,P1原则的运用,本章反复应用P1原则来消除明显的浪费：不必要的读和写消耗了内存和总线带宽。运用这个原则的困难在于，如果不把视野尽可能放宽到整个系统，浪费并不是显而易见的。运用P1原则要求对整个系统有一个概要的了解，使用简单的模型（硬件、体系结构、操作系统、协议）就可以做到这一点。系统技术的复杂性并不在于深度，而在于广度。,
