进程物理内存使用率高

模型的重要性网络算法学的一个中心难题是,它要求跨领域的知识,包括协议、硬件、体系架构、操作系统、算法等.
但是一个人不可能对所有这些领域都非常了解,因此需要不同领域的专家协作才能设计出高效的网络系统.

不同领域的专家之间如何进行有效的对话呢这时模型就很有用了,模型既可以把问题讲清楚,又不涉及不必要的细节.

最低程度,模型应能定义所需要的术语,这样不同领域的专家就能交流了(能听懂对方的话了).
最好情况:领域外的专家可以根据模型进行设计,并可由领域内的专家对设计进行检验.
比如,算法设计者虽然不懂得硬件,但能够根据硬件专家给出的模型设计出与硬件相匹配的算法,并在硬件上进行验证.
这正是本章的目的.

下面给出几个与网络计算机系统性能有关的抽象模型.
2.
1协议抽象模型协议是网络的核心,各种网络功能都是通过执行协议来实现的.
协议定义了对等实体之间通信的规则,对等实体之间通过交换报文来实现通信.
网络协议定义了报文的格式和交换次序,……,协议还定义了调用接口.

因此,可将协议看成是一个加上了接口和报文格式的状态机.
所有协议都可以抽象为图中的状态机模型:…….

常见而耗时的功能这门课关注的是系统性能,而TCP/IP协议是因特网的核心,所以我们把基于TCP/IP的协议状态机需要经常执行而又非常耗时的功能抽象出来,这些功能正是我们优化实现的重点.
图示的模型将贯穿于整个课程中.

图的中部是协议处理部分(传输层、网络层);图的下部是与网络的接口部分,涉及数据包的收发;图的上部是应用程序部分,涉及应用数据的交付.

在图的下部(DataManipulation):协议状态机必须从网络接收和发送数据包.
这涉及到数据操作,即必须读或写数据包中的每一个字节(当操作时间与数据长度成正比时,通常认为这是一个高开销的操作).
在此过程中需要分配资源,如分配缓冲区、CPU时间等(缓冲区分配、任务调度都需要操作系统参与).

图的中部(Protocolprocessing)描述了许多协议都需要的一些功能,协议处理开销随着包数量的增加而增大:(1)很多协议允许将大块数据分成小段传输,因而需要重组功能.
(2)协议都需要查找或者修改一些状态.
例如,每个TCP包到来都会导致TCP去查找TCP连接表并修改连接状态,每个IP包到来都会导致IP去查找转发表等.

(3)协议都需要设置定时器.
(4)如果协议模块需要处理多个不同的客户程序,它需要有效地调度这些客户,例如TCP必须调度对不同连接的处理.

在图的上部:协议状态机必须将数据包交付(Demultiplex)给某个客户程序.
在某些情况下,客户程序程序需被激活,产生开销较大的控制切换(controltransfer).
比如,当TCP收到一个web页时,根据端口号将数据包交给web浏览器程序,并可能需要唤醒运行浏览器的进程.
当目标程序很多的时候,解复用和控制切换都会产生很大的开销.

本课程的主要内容就是仔细研究这些功能的实现.
我们会看到,尽管这些常见功能一般来说开销很大,但是通过正确的技术是可以降低它们的开销的.

重要的性能度量网络中两个最重要的性能指标:吞吐量,延迟.
我们比较熟悉比特速率这个指标,但在某些情况下我们更关注包速率这个指标.
比如,对于路由器来说,每个包的处理开销是差不多的,包括包头检查、IP地址表查找等.
包的长度越短,单位时间内包的数量就越多,路由器的负担就越重,因此包速率是更能够反映路由器处理能力的指标.
因此在做路由器压力测试时,输入的都是最小长度的包.
当然,如果我们关注与数据处理有关的功能,比如内容扫描、加密/解密等,那么长包的处理压力大,这时我们会采用比特速率这个指标.

线速处理是网络系统优化的重要目标之一.
为满足线速处理要求(当前数据包必须在下一个包到来前处理完),必须限制最坏情况下数据包的处理时间.
所以,往往我们对最坏情况延迟更感兴趣.

性能测量分为全局性能测量(如端到端延迟和带宽)和本地性能测量(如路由器查找速度).
尽管全局性能测量对于整个网络的性能很重要,但本课程只关注本地性能测量.

大多数网络管理工具(如HP的OpenView)用于全局测量,本地测量需要的工具是在计算机内部测量性能的工具,比如英特尔的VTune.

因特网环境的特点当我们优化任何一个系统时,都要考虑它的运行环境.
不要试图做出一个在各种情况下都最优的系统,因为通用和最优也是一对矛盾.
就像我们前面介绍过的DIR24-8算法,它充分利用了因特网中绝大多数路由表项的前缀不超过24位、24位索引表消耗内存空间不大这个特点设计的,对于长度为128位的IPv6地址就不适用.
(将来你们做研究时也要注意这个问题)因此,我们要设计因特网中的高效网络系统,那么一定要了解因特网环境的特点.

链路速度:链路速度高意味着包的最大处理时间在缩短.
TCP占主导:传统应用主要使用TCP,P2P文件共享等也使用TCP(要求可靠传输),因此TCP优化很重要.

小包:研究表明,路由器收到的包中大约一半为最小长度(40字节)的TCP响应包.
在移动互联网应用中,大量的都是小包.

延迟很长:网络中的实际来回延迟远远超过光的传输延迟.
测量发现,数据包穿过美国的延迟时间平均为241ms,而光的传输延迟不超过30ms.
延迟增大可能是由追求高吞吐量造成的,比如在调制解调器上的批量压缩和在路由器中的流水处理,也可能因为拥塞造成.

局部性很差:骨干网上的流量研究表明,在一个非常短的时间内大约有一百万个并发流(具有不同的对)经过一个路由器,因此局部性很小.
也就是说,在一个包上执行的计算在未来短时间内重用到另一个包上的可能性很小,因此路由缓存不奏效.
正因为如此,路由缓存在现在的高速路由器中已经不用了,转而使用高速的IP地址查找技术,如硬件实现的DIR24-8算法.

从因特网环境的特点,我们可以看到网络系统面临的挑战:高速+小包=包速率很快;高速+大规模并发流量=局部性差,cache用不上;TCP很重要,但TCP开销大、处理复杂.

存储器在现代计算机系统结构中,访存是最大的性能瓶颈,因为访存延迟比指令执行时间长很多,而且处理器速度和访存速度之间的鸿沟越来越宽,使得访存瓶项问题更加突出.

在端节点和路由器中,数据包、状态信息、指令等都是保存在内存中,处理一个数据包需要访存多次,因此,访存构成了端节点和路由器的主要性能瓶颈.
许多的系统优化工作都是围绕该问题的解决而展开的.

为了优化访存性能,必须了解不同类型存储器的特性.
存储器的种类(1)寄存器寄存器由一组有序的触发器构成.
大多数现代处理器中都有一组片上寄存器.
一个电路逻辑访问同一个片上的寄存器是很快的,大约为0.
5-1ns.

(2)SRAM静态随机访问存储器(SRAM)由一组寄存器组成.
如果有N个寄存器,则使用log2N个地址位进行寻址.
由于地址解码延迟,访问片上SRAM只比访问片上寄存器慢一点点.
一般情况下,片上SRAM的访问时间为1-2ns,片外SRAM的访问时间为5-10ns.
现在的高端多核处理器的cache可以达到三级,每个核拥有独立的L1和L2cache,一个芯片内的所有核共用一个L3cache,它们的访存延迟要看产品手册.
(3)DRAMDRAM内部将存储单元组成成行、列二维结构,先提供行地址,再提供列地址,因此,DRAM的访问速度比SRAM低.
另外,由于预充电的需要,DRAM连续读之间需要一点延迟,所以连续读的延迟要大一些.

以上三种存储器,容量依次增大,但访存速度依次降低.
现在又出现了许多新型的存储器,如非易失性存储器,即当电源关闭后所存储的数据不会消失.
ROM/EPROM也是非易失型存储器,但它们一旦写入数据后不可更改,新型非易失性存储器是允许动态读写的.
这类存储器中有的只能顺序读写、有的可以随机读写,有的读快写慢等,在使用时需要了解这些存储器的新特性.

在这里我们大致有个量级的概念就可以了,即片外SRAM比寄存器至少慢5倍,片外DRAM又比片外SRAM慢5-10倍.

(4)快页内存(page-modeDRAM)页模式DRAM(快页内存)使用DRAM的结构特点来优化对相邻存储单元的连续访问.

DRAM控制器先提供行地址,再提供列地址.
当提供行地址时,选中的那一行数据(4字节)进入到rowbuffer中;再提供列地址,选中要读取的字节.
(DRAM的做法)快页内存的做法:如果要访问的4个字节刚好位于同一行(页)中,则提供行地址后这些数据就全部进入了rowbuffer中,不需要再给出列地址,因此可以加快对局部性好的数据的连续访问(不需要读4次).

知道快页内存具有这个特性后,我们就可以有意识地组织数据,让那些要被读取的数据保存在连续位置,这样可以显著加快访问速度.

(5)交织内存(InterleavedDRAM)假定DRAM的读写周期为100ns,即在地址线上输出地址后,将在100ns后得到要访问的数据.
假定输出一个地址只需要10ns,那么在等待数据到来的过程中,可以在地址线上输出其它bank中的地址.
当输出了10个bank中的地址后,在数据线上将依次出现这10个bank中要访问的数据.

如果一个DRAM的字长为32位,读写周期为100ns,则单个DRAMbank的最大吞吐量约为40MB.
采用以上的交织内存,如果能够合理安排读操作,则内存吞吐量可以达到400MB.

基于这些核心思想的内存技术有很多,不同在于容量大小、读写协议、bank数等,典型的例子包括具有2个bank的SDRAM和具有16个bank的RDRAM.

举例:流ID的流水化查找下面举一个例子,说明如何利用存储器的特点设计高效的算法.
设计方案考虑由于有线速处理的要求,我们必须限制最坏情况下的查找时间(查找流ID的最长时间不能超过128ns),考虑使用一个平衡二叉树.

遍历一棵树的逻辑是很简单的,关键是把树保存在什么地方为了获得高速度,理想情况下流ID和计数器应保存在SRAM中.
然而,当前的核心路由器中大约有100万条并发的网络流,在SRAM中保持100万条流的状态是很昂贵的.
(假设计数器为16比特,则100万条流至少需求(96+16)*1M=14MB)如果使用普通的DARM实现分支因子为2的二叉树,查找一个流ID需要log21000000=20次访存.
即使按照最乐观的DRAM访存周期50ns来计算,整个的查找时间为1微秒.

使用RDRAM实现二分查找为了缩短查找时间,可以考虑使用交织内存,多个包一起查.
RDRAM集成了16个bank,可以使用RDRAM实现一棵高度为16的二叉树.

讲课时画一个图.
RDRAM一次读操作的时间约为60ns.
尽管一个流ID的查找需要16*60ns的时间,但查找芯片可以同时查找16个包,使得总的查找性能为每个数据包60ns,可以满足查找时间的要求.

但是,层次为16的二叉树只能有216=64K个流ID,不能满足规模的要求!
需要增加每个节点保存的流ID.

网络存储子系统设计技术流ID查找使用了在网络芯片的存储子系统设计中经常使用的一些技术(前2项).

交错内存和流水线:类似的技术也可用于IP查找、包分类和包调度等.
多个bank可以用多个外部存储来实现.

宽字并行:为了一次读入更多的数据,使用可并行处理的宽内存字.
这可以使用DRAM,并利用其快页模式;或者使用SRAM,并使得每个内存字更宽.

组合DRAM和SRAM:由于SRAM快而贵,而DRAM便宜却慢,因此将这两种技术组合起来可以得到一个最佳的平衡.
将SRAM作为DRAM数据库的缓存是很经典的做法.

2.
3端节点架构本课程关注端节点,因此我们看一下端节点的架构.
端节点就是通用计算机,由处理器、存储器、总线、I/O设备组成.

如果处理器的状态只保存在DRAM中,则一条指令将花费60ns去读或写一次内存,这会非常慢.
事实上,处理器使用cache来提高速度.

Cache的使用效果与局部性由于每个包最多只经过I/O总线两次(收和发),而包处理过程中需要访存很多次,所以我们关注访存瓶颈.

为了填补处理速度和访存速度的鸿沟,现代计算机系统充分利用cache来提高性能.
但是,cache的使用效果与应用的时空局部性有关.

时间局部性:一个存储位置在短时间内被再次访问.
由于数据被访问时会进入cache,当短时间内再次访问该数据时,该数据很大可能仍在cache中,从而可以显著减少访存时间.

空间局部性:一个存储位置被访问后,其邻近位置在短时间内被访问.
X86处理器基于空间局部性假设实现了预取:每当读取一个32比特的字时,处理器预取连续的128比特(一个cache行)到cache中,这样访问其余的96比特将不会产生cachemiss.
高速数据包流基本不呈现时间局部性:一方面,数据包本身不会被反复处理;另一方面,同一个流的数据包往往被大量其它的流隔开,前一个包的查找结果(如下一跳、分类ID等)很快被踢出cache,无法重用.

提高算法及数据结构的空间局部性端节点网络功能的高效实现通常将重点放在提高算法及数据结构的空间局部性上.
比如,1)设计紧凑的数据结构,使其能够常驻cache不被换出;2)将随机访问(链表、树)变为顺序访问(数组),如DHash的工作;3)对相同/相近位置的数据操作尽可能放在一起;4)将经常要被一起访问的数据放在连续位置,且与cache行对齐,如数据结构中成员的长度及存放位置.

这些措施很简单,但是往往会有显著的效果.
举别体伟(相同位置的操作放在一起)和王燕飞(用户态驱动中包缓冲区长度定义,1518Bvs2KB,跨页)的例子.
有经验的程序员会非常注意这些问题,他们通常不会使用复杂的算法,但写出的程序非常高效.
我们的学生一遇到性能问题,往往就会从算法上找原因,但其实是不得要领.

顺便说一下学生在优化checksum时遇到的问题:用了较多的if-else语句,代码行数少,但运行慢.
原因:增加了指令cachemiss.
因此,以代码行数(指令数)来衡量代码效率是不准确的,关键是访存是否高效.

以上例子说明,体系结构知识对于编写高质量的软件是非常有用的.
没有体系结构背景的人,根本不知道这里面有这么多的陷阱.

2.
4操作系统对端节点上的应用性能进行优化,一定要了解操作系统对应用性能的影响,因为它是很大一部分开销的来源.

为什么要设计操作系统呢操作系统是为了解决在裸机上编程困难而设计的.

好的抽象提高了程序员的生产效率,但却带来了两个代价.
(1)实现抽象的机制是有代价的,比如,调度进程会产生开销,管理虚拟内存会产生开销.
(2)抽象阻碍程序员对资源的充分利用,比如,操作系统不允许程序员将查找数据结构一直保持在cache中.

下面我们给出这三种抽象的底层机制与代价的模型.
(1)依靠进程实现不间断计算的抽象由于外部中断的频繁到来,处理器上的程序运行不了多久就会被打断.
但是,操作系统通过进程提供给程序员不间断、顺序计算的抽象.

进程抽象是通过三个机制实现的:上下文切换,调度,保护.
图2.
11给出了上下文切换和调度的示意图.
在进程P1的运行过程中遇到一个中断;P1的状态(上下文)被保存到内存中,运行中断程序;然后调度器程序运行,选择进程P2运行;P2的状态被恢复,P2运行,……;最后,调度器又调度P1运行.
在此过程中,P1觉得自己一直独占CPU在运行.

但是我们看到,处理器的时间线包含了进程之间的上下文切换(状态保存及恢复)以及调度器的运行,这些就是进程抽象带来的开销.

另外,操作系统的保护机制确保应用进程不会对操作系统内核产生影响,以及确保进程隔离.
比如,操作系统使用保护环来规定不同进程的最高权限,对于应用进程无权访问的资源,可以向操作系统发送一个请求,请求通过调用系统服务来处理.
这种保护机制也会引入开销.

进程的三种类型作为计算代理,进程有三种常见的类型:(1)中断处理程序是非常短小的程序,只用于处理紧急请求,比如数据包的到来.
中断处理程序只使用少量的状态,典型地只使用几个寄存器,因此开销最小(上下文最小).

(2)用户进程使用计算机的全部状态,比如内存和寄存器,因此,在用户进程之间切换的代价是很高的.
(上下文最大)(3)线程是轻量级的进程,只需要较少的状态.
另外,由于同一个进程内的线程是共享内存的(即相同的变量),因此,线程切换不需要重新映射.

以上三种类型的进程,其开销依次增大.
举例:接收端活锁下面我们用一个例子说明进程优先级不同产生的问题.
图示为数据包在BSDUNIX中的处理过程.
数据包的到来产生一个硬件中断,CPU响应中断,保存当前正在运行的进程的状态,例如一个java程序,然后CPU执行中断处理程序(为快速响应绕过了调度器).

中断处理程序将数据包描述符拷贝到一个内核IP队列(数据包已通过DMA传输到内存),调用一个软中断(请求一个操作系统线程)后返回.
中断处理程序一般只做最少的、必需的事情.

假定随后没有硬件中断产生,则控制权会交给调度器.
调度器一般会调度CPU执行软中断,因为软中断的优先级高于用户进程.

内核线程对数据包进行TCP和IP处理,然后将数据包放入相应的应用队列,称socket队列.
假定该应用程序是一个浏览器,浏览器正在等待数据包的到来.
软中断退出后,控制权重新交给调度器.
调度器可能决定运行浏览器,而不是早先的java程序.

现在假设网络负载很高,一系列的包连续到来,这时只有最高优先级的中断处理程序能够运行,很可能没有多少时间留给软中断,当然更没有时间留给浏览器程序.
这样,最终IP包队列或socket队列会填满,导致这些数据包在消耗了资源之后被丢弃,我们称这时计算机进入接收端活锁:即计算机将所有的时间都用来处理中断、协议处理等较高优先级的任务,却因为没有时间运行较低优先级的应用程序,导致这些已被处理的数据包被丢弃.
这个现象在高速网络环境下很常见.

(2)通过虚拟内存实现无限存储的抽象在虚拟内存系统中,程序员使用的内存抽象是一个线性的存储空间,存储空间的大小只受指令地址长度的限制,而不受物理内存大小的限制.

任何一个对虚拟地址的访问必须映射到一个物理地址上.
现代计算机系统使用基于页的映射方法.
…….
.

页表映射可以避免分配很大的连续内存空间,请求调页可以使程序员可以使用的虚拟内存空间不受物理内存大小的限制,只受磁盘大小以及指令地址长度的限制.

虚拟内存抽象带来的开销采用虚拟内存后,到虚拟地址的访问可能涉及到两次内存访问:…….
为降低访问延迟,现代处理器将最近使用过的虚拟地址到物理地址的映射缓存在处理器的一个片上cache(称TLB)中,实际的地址转换由称为MMU的硬件完成.

TLBmiss和调页是最影响内存访问速度的两个因素.
页表映射也提供了进程之间的一种保护机制.
当进程发出读虚拟地址X的请求时,若页表中没有相应的表项,硬件将产生一个缺页异常,由操作系统调入相应的页.
通过确保只有操作系统能够改变页表表项,就能保证一个进程不会在非授权的情况下读或写另一个进程的存储空间.

路由器转发直接工作在物理内存上,而端节点的网络代码工作在虚拟内存上,因此访存瓶颈在端节点中表现最为突出.

尽管虚拟内存是一个潜在的开销(如TLBmiss),它也是一个可能的机会.
比如,操作系统和应用程序之间的数据包拷贝可以通过操作页表来高效地实现,比如OS将页表映射给应用程序.

(3)通过系统调用实现简单I/O的抽象要让程序员直接与每一个I/O设备打交道是不可接受的,操作系统提供给程序员的设备抽象是可以进行读写的内存.
不管是磁盘还是网卡,在程序员看来都是读写一个文件描述符.

设备访问和系统调用将一个简单的I/O接口调用映射到对设备进行实际操作的代码是设备驱动程序.

设备(如磁盘)必须被所有应用程序共享,如果允许应用程序直接控制设备,一个出错的进程可能会使设备崩溃.
将设备驱动程序放置在操作系统中不会被错误进程影响到的地方是一个合理的要求,这个地方就是内核.

设备驱动程序提供不能被应用程序直接执行的一组基本服务,包括I/O操作和页表更新.
这样当应用程序想访问设备时,它必须通过应用程序和操作系统的边界发出一个系统调用.

系统调用是函数调用的一种保护形式,它使处理器进入内核模式,从而可以执行I/O操作.
当I/O结束后,处理器返回用户模式,执行应用程序代码.

系统调用比函数调用的开销大,因为它涉及用户代码到内核代码、内核代码到用户代码的切换运行,并且要对不正确的参数值进行额外的安全检查.
在现代计算机上,一个简单的系统调用可能需要几个微秒.

2.
5小结本章介绍了影响网络系统性能的四个抽象等级:硬件,体系结构,操作系统和协议.
包处理速度可能受到硬件的影响,如使用的存储器;可能受到体系结构的影响,如总线速度;可能受到操作系统的影响,如控制开销;还可能受到协议机制的影响,如表查找.
理解这些抽象等级,对于我们改进网络系统的性能有非常大的帮助.