（计算机软件与理论专业论文）分布式存储平台的路由算法和本地资源管理.pdf

摘要 本课题来源于四川省青年软件创新工程项目：基于广域网的分布式容错存储 平台。研究和开发一种网络容错存储平台软件，主要用于数据的高可靠存储、远 程备份和远程灾难恢复。本文的核心内容是这个存储平台的路由算法和本地资源 的管理。 在本论文中，首先叙述了有关网络协议和服务器模型的基础知识，这些基础 知识是研究p 2 p 分布式存储模型的前提。接下来简单的总结了p 2 p 分布式存储 模型的历史和发展。 接下来第五章描述了基于广域网的分布式容错存储平台的系统结构，从总体 上明确了本论文的核心内容在整个系统中的功能和作用。第六章描述的是文件名 到节点号的映射安全散列算法，作为一个h a s h 算法，它不仅提高了效率，而且 用来在分布式系统中定位节点还达到了一定的负载平衡的作用，这一部分是后面 描述路由算法的基础。第七章分析介绍了传统的路由算法，总结了它们的优点和 不足之处，之后在第八章中提出了我们的一种面向层次结构的路由算法，这种面 向层次结构的路由算法定位节点快，健壮性高，安全性好。第九章描述了本地资 源管理，重点在于文件存储指针表的设计和管理，特别是保持内存和磁盘信息的 同步机制，包括定时同步和补救同步。 最后通过对基于广域网的分布式容错存储平台功能和性能的测试，表明它达 到了设计的目标并具有较高的性能。 关键词： 路由，文件存储指针，同步 a b s t r a c t r e s e a r c h & d e v e l o p m e n t o fd i s t r i b u t e df a u l tt o l e r a n ts t o r a g ef l a tb a s e d o nw a n i sap r o j e c tc o m e sf r o m y o u t hs o f t w a r ec r e a t i v ee n g i n e e r i n g ”f r o mt e c h n o l o g i c a l o m c eo fs i c h u a n i tm a i n l yr e s e a r c h e san e t w o r kf a u l tt o l e r a n ts t o r a g ef i a ts o f t w a r e i tc a nb eu s e di nh i g hr e l i a b l es t o r a g e o f d a m 、t o n g - d i s t a n c ec o p ya n dc a l a m i t yr e m e d y t h em o s ti m p o r t a n tp a r t so ft h i sp a p e ra r et h er o u t ea l g o r i t h m sa n dl o c a lr e s o u r c e s m a n a g e m e n t o ft h i ss t o r a g ef i a t f i r s t l y , w er e c o u n ts o m eb a s a lk n o w l e d g ea b o u tn e t w o r kp r o t o c o la n ds e r v e r m o d e l b e c a u s et h e s ea r et h ep r e c o n d i t i o n s o f r e s e a r c h i n g p 2 ei nt h ee n dw ed r a w a s i m p l e c o n c l u s i o no ft h e h i s t o r ya n dd e v e l o p m e n to ft h ep 2 pd i s t r i b u t e ds t o r a g e m o d e l t h e n ，w ed i s c u s st h es y s t e ms t r u c t u r eo fd i s t r i b u t e df a u l tt o l e r a n ts t o r a g er a t b a s e do nw a n ，s ow ec a nu n d e r s t a n dt h ef u n c t i o na n de f f e c to ft h i sp a p e r sn u c l e a r c o n t e n ti nt h ew h o l es y s t e mf r o mah o l i s t i cv i e w i nc h a p 6w e d e p i c t as e c u r eh a s h i n g a l g o r i t h ma b o u tm a p p i n g f r o mt i l en a m et on o d en u m b e ra sa h a s h i n ga l g o r i t h m ，i t n o t o n l ye n h a n c e st h ee f f i c i e n c yb u ta l s op l a y sa l o a db a l a n c er o l ei np o s i t i o n i n gn o d e i nt h ed i s t r i b u t e ds y s t e m t h el a t t e rp a r ti st h eb a s eo ft h er o u t e a l g o r i t h m i nc h a p7 w ei n t r o d u c eat r a d i t i o n a lr o u t e a l g o r i t h m a n d p o i n t o u ti t s a d v a n t a g e s a n d d i s a d v a n t a g e s i n t h e f o l l o w i n gc h a p ah i b e r a r c h y o r i e n t e d r o u t e a l g o r i t h m i s p r e s e n t e d ，t h ep r o m i n e n t m e r i to f t h i sn e w a l g o r i t h mi si t sf a s tp o s i t i o n i n gn o d e 、h i g h r e l i a b i l i t ya n dw e l ls e c u r i t y i nc h a p10 w ed e s c r i b et h el o c a lr e s o u r c e sm a n a g e m e n t ， t h e e m p h a s e s a r et h ed e s i g na n dm a n a g e m e n to ft h ef i l e s t o r a g ep o i n t e rt a b l e ， e s p e c i a l l yk e e p i n gt h ei n f o r m a t i o ni nm e m o r ya n dd i s ks y n c h r o n o u sw h i c hi n c l u d e t i m e rs y n c h r o n i z a t i o na n dr e m e d ys y n c h r o n i z a t i o n 。 f i n a l l y , w ep r o v e dt h a tt h ei n i t i a lg o a l i sr e a c h e da n dag o o dp e r f o r m a n c ei s a c h i e v e db y t a k i n gt h es y s t e m i ns o m e f f m c t i o n a l i t y t e s t s k e y w o r d s ： r o u t i n g ，f i l es t o r a g ep o i n t e r ，s y n c h r o n i z a t i o n v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 奎垒盍日期：2 。呼年2 月巧日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文， ( 保密的学位论文在解密后应遵守此规定) 签名：奎垒! 壶 导师签名：2 丝之 日期：2 0 。牛年2 月2 7 ，日 分布式存储平台的路由算法和本地资源管理 1 1背景 第一章引言 现在的社会是一个信息的社会，信息以爆炸式的方式迅速增长。我们在利用 和处理这些信息的同时，怎样保存这些信息就成了当务之急。如今网络化存储的 概念已经被提了出来，而且得到了快速的发展。与传统的备份方法r a i d 磁 盘阵列、镜像盘相比较，网络存储不仅是得到了更大的存储能力，而且还具备了 基于网络的数据备份和恢复技术。 目前流行的网络存储系统主要有s a n ，n a s ，网格以及p 2 p 系统等。 s a n ( s t o r a g e a r e an e t w o r k ，存储区域网) 是种类似于普通局域网的 高速存储网络，它通过专用的集线器、交换机和网关建立起与服务器和磁盘阵列 之间的直接连接。s a n 不是一种产品而是配置网络化存储的一种方法。不过s a n 虽然实现了网络存储，但其跨越的距离相当有限，无法满足广域网范围的数据恢 复。 n a s 系统是直接挂在网上的专用文件服务器，具备快速、简单、可靠的性 能，支持u n i x 和w i n d o w sn t 多种网络环境。n a s ( n e t w o r ka t t a c h e d s t o r a g e ，网络附加存储) 系统实现了两个突破：理念上的突破把存储器直 接接到网络上，不再挂在服务器后端，避免了给服务器增加负担：技术上的突破 通过专用软件减少磁头臂机械移动的次数，克服由此造成的延时。但是到目 前为止它还只能局限于局域网的范围。 实现远程数据共享和恢复的技术主要有：i f c p 、f c i p 和i s c s i 等。这三种 都是l p 存储协议，通过它们可以构建基于以太网的s a n ，使得s a n 扩展到广域 网的范围。 网格( g r i d ) ，可以称作是第三代i n t e r n e t ，它的主要特点是不仅仅包括计 算机和网页，而且包括各种信息资源，例如数据库、软件以及各种信息获取设备 等，它们都连接成一个整体。整个网络如同一台巨大无比的计算机，向每个用户 提供一体化的服务。目前网格还处于研究阶段，最著名的网格计算研究是美国的 g l o b u s 项目。 p 2 p 是p e e r - t o p e e r 的缩写，p e e r 在英语里有”( 地位、能力等) 同等者“、 ”同事”和”伙伴”等意义。这样一来，p 2 p 也就可以理解为”伙伴对伙伴“的意思，或 称为对等联网。早期的p 2 p 系统主要是一些文件共享和存储程序，如：n a p s t e r ， g n u t e l l a 和m o j on a t i o n 等。n a p s t e r 使用中心目录服务器去定位文件，而 分布式存储平台的路由算法和本地资源管理 g n u t e l l a 是通过广播请求进行文件查询，m o j on a t i o n 则提供了分片存储和下 载机制，但是这些系统在可靠性和扩展性方面都还做的远远不够。现在的p 2 p 系统都通过在应用层建立一个逻辑网络( o v e r l a yn e t w o r k s ) ，从而可以实现基 于关键字的路由( k b r ) ，在此基础上可以进一步支持分布式哈希表( d h t ) 或分 散式对象定位路由( d o l r ) 。这些系统在可靠性和扩展性方面有了大大提高。其 中有代表性的系统包括：t a p e s t r y ，p a s t r y ，c a n 和c h o r d 。但是由于p 2 p 系统中各个节点主机的不稳定性使得整个系统在可靠性方面有一定的局限性，针 对这种情况人们又提出了s e r v e rt os e r v e r 的模型。 鉴于s a n 和n a s 需要有专用硬件的支持，成本比较高，不适宜普及，而网 格涉及的范围太大，仍处于研究阶段，只有p 2 p 是目前最活跃，最适宜普及的 网络存储技术。但是纯粹的p 2 p 系统中，由于各个节点主机的不稳定性，使得 整个系统在可靠性方面有一定的局限性，因此采用s e r v e rt os e r v e r 的模型是一 个比较好的折衷方案。本实验室申请的四川省青年软件创新工程项目基于广域 网的分布式容错存储平台就是一个s e r v e rt os e r v e r 的分布式存储系统，它可 以充分结合当前普遍应用的f t p 和w w v v 服务，有利于普及推广，并且采用了基 于物理拓扑结构的逻辑网络路由，提供了强大的扩展能力和快速的路由定位能 力。 1 2论文组织结构 第一章是背景知识的介绍。 第二章介绍了网络协议的基础知识。 第三章介绍了服务器模型。 第四章总结了p 2 p 的历史和发展。 第五章描述了系统的结构图。 第六章描述了文件名到节点号的映射安全散列算法。 第七章是对一些传统路由算法的分析。 第八章描述了本系统的路由算法。 第九章描述了本地资源管理。 第十章是测试和总结。 最后是参考资料和致谢。 分布式存储平台的路由算法和本地资源管理 第二章t c p f l p 协议简介 在2o 世纪80 年代早期， iso g p 开始致力于制定一套普遍适用的规范集合， 以使得全球范围的计算机平台可进行开放式通信。iso 创建了一个有助于开发 和理解计算机的通信模型，即开放系统互连0si ( 模型) 。0si 模型将网络结 构划分为七层：即物理层、数据链路层、网络层、传输层、会话层、表示层和应 用层。每一层均有自己的一套功能集，并与紧邻的上层和下层交互作用。在顶层， 应用层与用户使用的软件( 如字处理程序或电子表格程序) 进行交互。 在0si 模型的底端是携带信号的网络电缆和连接器。总的说来，在顶端与底端 之间的每一层均能确保数据以一种可读、无错、排序正确的格式被发送。 2 1o s l 模型 o s i 模型是对发生在网络中两节点之间过程的理论化描述。它并不规定支持 每一层的硬件或软件的模型，但你学习到的有关网络的每件事均能对应于模型中 的一层。因此，不仅应了解各层的名字，而且应了解它们的功能及层之间相互作 用的方法，图2 1 描绘了0si 模型和它的层结构： 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 图2 i0 si 模型 i ) 物理层 物理层是0si 模型的最低层或第一层，该层包括物理连网媒介，如电缆连 线连接器。物理层的协议产生并检测电压以便发送和接收携带数据的信号。在你 分布式存储平台的路由算法和本地资源管理 的桌面pc 上插入网络接口卡，你就建立了计算机连网的基础。换言之，你提供 了一个物理层。尽管物理层不提供纠错服务，但它能够设定数据传输速率并监测 数据出错率。网络物理问题，如电线断开，将影响物理层。同样地，如果你没有 将网络接口卡在计算机的电路板中插得足够深，计算机也将在物理层出现网络问 题。 ieee 已制定了物理层协议的标准，特别i e e e8 0 2 规定了以太网和令牌环 网( 见第3 章) 应如何处理数据。术语“第一层协议”和“物理层协议”，均是 指描述电信号如何被放大及通过电线传输的标准。在第4 章和第6 章将介绍物理层 设备( 如网络接口卡和集线器) 及它们的操作。 2 ) 数据链路层 数据链路层是0si 模型的第二层，它控制网络层与物理层之间的通信。它 的主要功能是将从网络层接收到的数据分割成特定的可被物理层传输的帧。帧是 用来移动数据的结构包，它不仅包括原始( 未加工) 数据，或称“有效荷载”， 还包括发送方和接收方的网络地址以及纠错和控制信息。其中的地址确定了帧将 发送到何处，而纠错和控制信息则确保帧无差错到达。 数据链路层的功能独立于网络和它的节点和所采用的物理层类型，它也不关 心是否正在运行w ordperfect 、exce1 或使用inter net 。有 一些连接设备，如网桥或交换机，由于它们要对帧解码并使用帧信息将数据发送 到正确的接收方，所以它们是工作在数据链路层的。ether n et 是应用数 据链路层技术的个实例。 3 ) 网络层 网络层，即0si 模型的第三层，其主要功能是将网络地址翻译成对应的物 理地址，并决定如何将数据从发送方路由到接收方。例如，。一个计算机有一个网 络地址l0 34 99 12 ( 若它使用的是tcp ip 协议) 和一个物理地 址0060973e97f3 。 网络层通过综合考虑发送优先权、网络拥塞程度、服务质量以及 可选路由的花费来决定从一个网络中节点a 到另一个网络中节点b 的最佳路径。由于网络层处理路由，而路由器因为即连接网络各段， 并智能指导数据传送，属于网络层。在网络中，“路由”是基于编址 方案、使用模式以及可达性来指引数据的发送。网络层协议还能补偿 数据发送、传输以及接收的设备能力的不平衡性。为完成这一任务， 网络层对数据包进行分段和重组。分段即是指当数据从一个能处理较 分布式存储平台的路由算法和本地资源管理 大数据单元的网络段传送到仅能处理较小数据单元的网络段时，网络 层减小数据单元的大小的过程。这个过程就如同将单词分割成若干可 识别的音节，给正学习阅读的儿童使用一样。重组过程即是重构被分 段的数据单元。类似地，当一个孩子理解了分开的音节时，他会将所 有音节组成一个单词，也就是将部分重组成一个整体。 4 ) 传输层 传输层主要负责确保数据可靠、顺序、无错地从a 点到传输到b 点( a 、b 点可能在也可能不在相同的网络段上) 。因为如果没有传输层，数据将不能被接 受方验证或解释，所以，传输层常被认为是0si 模型中最重要的一层。传输协 议同时进行流量控制或是基于接收方可接收数据的快慢程度规定适当的发送速 率。除此之外，传输层按照网络能处理的最大尺寸将较长的数据包进行强制分割。 例如，以太网无法接收大于150o 字节的数据包。发送方节点的传输层将数据 分割成较小的数据片，同时对每一数据片安排一序列号以便数据到达接收方节 点的传输层时，能以正确的顺序重组。该过程即被称为排序。 5 ) 会话层 会话层负责在网络中的两节点之间建立和维持通信。术语“会话”指在两个 实体之间建立数据交换的连接：常用于表示终端与主机之间的通信。所谓终端是 指几乎不具有( 如果有的话) 自己的处理能力或硬盘容量，而只依靠主机提供应 用程序和数据处理服务的一种设备。会话层的功能包括：建立通信链接，保持会 话过程通信链接的畅通，同步两个节点之间的对话，决定通信是否被中断以及通 信中断时决定从何处重新发送。你可能常常听到有人把会话层称作网络通信的 “交通警察”。当通过拨号向你的isp ( 因特网服务提供商) 请求连接到因特 网时，isp 服务器上的会话层向你与你的pc 客户机上的会话层进行协商连接。 若你的电话线偶然从墙上插孔脱落时，你终端机上的会话层将检测到连接中断并 重新发起连接。会话层通过决定节点通信的优先级和通信时间的长短来设置通信 期限。就此而论，会话层如同一场辩论竞赛中的评判员。例如，如果你是一个辩 论队的成员，有2 分钟的时间阐述你公开的观点，在1 分3o 秒后，评判员将通知 你还剩下30 秒钟。假如你试图打断对方辩论成员的发言时，评判员将要求你等 待，直到轮到你为止。最后，会话层监测会话参与者的身份以确保只有授权节点 才可加入会话。 6 ) 表示层 分布式存储平台的路由算法和本地资源管理 表示层如同应用程序和网络之间的翻译官，在表示层，数据将按照网络能理解 的方案进行格式化；这种格式化也因所使用网络的类型不同而不同。表示层管理 数据的解密与加密，如系统口令的处理如果在intern et 上查询你银行账 户，使用的即是一种安全连接。你的账户数据在发送前被加密，在网络的另一端， 表示层将对接收到的数据解密。除此之外，表示层协议还对图片和文件格式信息 进行解码和编码。 7 ) 应用层 osi 模型的顶端也即第七层是应用层。应用层负责对软件提供接口以使程 序能使用网络服务。术语“应用层”并不是指运行在网络上的某个特别应用程序， ! n m i c r o s o f tw ord ，应用层提供的服务包括文件传输、文件管理以及电子邮件 的信息处理。例如，如果在网络上运行m i c r o s o f tw ord 。并选择打开个文件， 你的请求将由应用层传输到网络。 2 2t c p i i p 协议 tcp ip 不是一个简单的协议，而是一组小的、专业化协议，包括tcp 、 ip 、udp 、arp 、icmp 以及其他的一些被称为子协议的协议。大部分网络 管理员将整组协议称为tcp ip ，有时简称为ip 。tcp ip 的前身是由 美国国防部在20 世纪6o 年代末期为其远景研究规划署网络( arp anet ) 而 开发的。由于低成本以及在多个不同平台间通信的可靠性， tcp ip 迅速发 展并开始流行。它实际上是一个关于因特网的标准，迅速成为局域网的首选协议。 一些最近发行的网络操作系统( n0s ) ( 如netw a r e5 o ) 使用tcp ip 为缺省协议。 tcp ip 最大的优势之一是其可路由性，也就意味着它可以携带被路由 器解释的网络编址信息。tcp ip 还具有灵活性，可在多个网络操作系统( n 0s ) 或网络介质的联合系统中运行。然而由于它的灵活性，tcp ip 需要 更多的配置。 t c p i p 与o s i 模型的比较如图2 2 中描述，对应于osi 模型的七层结构： 应用层：大致对应于0si 模型的应用层和表示层，借助于协议立n w i n s o c k a p i 、ftp ( 文件传输协议) 、tftp ( 普通文件传输协议) 、http ( 超文 本传输协议) ，sm tp ( 简单邮件传输协议) 以及dh cp ( 动态主机配鼍协议) ， 应用程序通过该层利用网络。 传输层：大致对应于0si 模型的会话层和传输层，包括tcp ( 传输控制协 议) 以及udp ( 用户数据报协议) ，这些协议负责提供流控制、错误校验和排 分布式存储平台的路由算法和本地资源管理 序服务。所有的服务请求都使用这些协议。 互连网层：对应于0si 模型的网络层，包括ip ( 网际协议) 、icmp ( 网 际控制报文协议) 、igmp ( 网际组报文协议) 以及arp ( 地址解析协议) 。 这些协议处理信息的路由以及主机地址解析。 网络接口层：大致对应于osi 模型的数据链路层和物理层。该层处理数据 的格式化以及将数据传输到网络电缆。 tcp ip 协议群中的子协议或tcp ip 核心协议，被设计成运行在0s i 模型的传输层或网络层的协议。它们为网络中的各主机提供通信服务。它们也 对四层模型的最高层一应用层中的协议提供服务。你可能会猜测到，tcp 和ip 是tcp ip 协议群中最重要的核心协议。 除了下面将讨论的子协议， tcp ip 协议群中还有一组路由协议作为其 应用层 表示层 应用层 会话层 传输层 传输层 网络层 互连网层 数据链路层 物理层 网络接口层 图2 2t c p i p 与0 s i 模型的比较 特色协议，这些协议有助于路由器更有效地管理信息流由于理解路由协议必须 先了解路由器的工作过程，我们将顺延到第6 章对路由协议进行讨论。 1 网际协议 网际协议( ip ) 属于tcp ip 模型和互连网层，提供关于数据应如何 传输以及传输到何处的信息。ip 是一种使tcp ip 可用于网络连接的子协议， o p tcp ip 可跨越多个局域网段或通过路由器跨越多种类型的网络。在一个 网际环境中，被连接在一起的单个网络被称为子网。使用子网是t c p i p 连网的 一个重要部分。 数据帧的ip 部分被称为一个ip 数据报，ip 数据报如同数据的封面，包含 了路由器在子网中传输数据所必需的信息。ip 数据报包括报头和数据，总长度 分布式存储平台的路由算法和本地资源管理 不能超过6 55 3 5 字节。下面描述了ip 数据报头的各部分，并描绘在图2 3 中。 版本号i p 头长度服务类型数据包长度 标识段标志段 生存时间传输协议头校验和 发送地址 目标地址 选项 填充 图2 3ip 数据报头 版本：标识协议的版本号。接收方工作站首先查看该域以决定它是否能够读取 该输入数据。若不能，它将拒绝该数据包。然而，由于大多数tcp ip 网络 使用ip 版本4 ( ipv4 ) ，很少发生拒绝事件。一个更高级的ip 版本，即ip 版本6 ( ipv6 ) 已经开发出来并将在不久使用。ipv6 将具有向后兼容性以 便能够接收ipv4 的数据。 网际报头长度( ihl ) ：用32 位编组形式标识ip 报头的长度。擐常用的ip 报头由四个编组，或2o + 8 位字节组成。该域的重要性在于它向接收点指示了数 据从何处开始( 在报头结束之后立即开始) 服务类型( t os ) ：通过指定数据的速度、优先权或可靠性，通知ip 如何处 理输入的数据报。 总长度：用字节标识数据报的总长度，其包括报头和数据。 标识符：标识一个数据报所属的消息，以使得接收节点可以重组被分断或分段 的消息。该域和下面两个域，即标识符和段偏移量，在数据报的分段和重组过程 中起作用。 标志：无分段( df ) 或多个分段( mf ) ：标识一个消息是否被分段，如果 是，则表示数据报是否是最后一个段。 分段偏移量；标识数据报段属于输入段集的哪一段。 生存期( ttl ) ：标识一个数据报在它被抛弃前在网络中存在的最大时间， 单位为秒。ttl 对应于一个数据报通过路由器的数目；一个数据报每次通过一 分布式存储平台的路由算法和本地资源管理 个路由器， ttl 将减去一秒，不论路由器是否花费一整秒进行数据处理。 协议：标识将接收数据报的传输层协议类型( 如tcp 或udp ) 。 报头校验和：决定ip 报头是否已被破坏。 源地址：标识源节点的完整的ip 地址。 目标地址：标识目标节点的完整的ip 地址。 可选项：可以包含可选的路由和实时信息。 填充位：包含填充信息以确保报头是32 位的倍数，该域的大小可变。 数据：包括了由源节点发送的原始数据，9 - j 2 i tcp 信息ip 协议是种不可靠 的、无连接的协议，即意味着它不保证数据的可靠传输。然而，tcp iw e j , 议 群中更高层协议可使用ip 信息确保数据包接正确的地址进行传输。注意到ip 数据报并不包含一个校验和部件，报头校验和仅仅验证ip 报头中路由信息的完 整性。如果当数据包被接收时伴随信息的校验和值不正确，则数据包将被认为己 破坏并被抛弃，同时，一个新的数据包被发送。 2 传输控制协议 传输控制协议( tcp ) 协议属于tcp ip 协议群中的传输层，提供可 靠的数据传输服务。tcp 是一种面向连接的子协议，意味着在该协议准备发送 数据时，通信节点之间必须建立起一个连接。tcp 协议位于ip 子协议的上层， 通过提供校验和、流控制及序列信息弥补ip 协议可靠性的缺陷。如果一个应用 程序只依靠ip 协议发送数据，ip 协议将杂乱地发送数据，如不检测目标节点是 否脱机，或数据是否在发送过程中已被破坏。另一方面 tcp 包括了可保证数 据可靠性的几个组件。tcp b t j , 议段的各个域描述如下，图2 4 描述了一个tcp 协议段和它的各个域。 图2 4tcp 协议段和它的各个域 分布式存储平台的路由算法和本地资源管理 源端口：指示源节点的端口号。一个端口是位于主机上的一个地址。在端口处， 一个应用程序可以获得输入数据。端口的一个例子如端! z 1 80 ，该端口一般用于 接收w e b 页请求。在第1 l 章将对端口有更多的了解。 目标端口：指示目标节点的端口号。 序列号：标识了数据段在已发送的数据流中的位置。 应答号( ack ) ：发送方通过返回一条消息来验证数据已被接收。 tcp 报头长度：指示了tcp 报头的长度。 代码：包括了标识特殊条件的标识符，例如，一个消息是紧迫的，或源节点希望 请求一个连接或结束一个连接。 滑动窗口尺寸：指示了接收方机器可接收的数据块个数。 校验和：允许接收节点判定tcp 段是否在发送过程中被破坏。 紧迫指示器：能够指示出紧迫数据驻留在数据中的位置。 可选项：用于具体指定一些特殊选项。 填充：包含了确保tcp 报头大小是32 位整数倍的填充信息。 数据：包含了由源节点发送的原始数据。 3 u d p ( 用户数据报协议) 用户数据报协议，如同tcp ，位于tcp ip 模型中互连网层和应用层之 间的传输层中。不同于tcp 的是， udp 是一种无连接的传输服务，它不保证 数据包以正确的序列被接收。事实上，该协议根本不保证数据包的接收，而且， 它不提供错误校验或序列编号。然而通过int ernet 进行实况录音或电视 转播，要求迅速发送数据时， udp 的不精确性使得它比tcp 协议更加有效、 更有用。在这些情况下，具有验证、校验和以及流控制机制的tcp 协议将增加 太多的报头，使得其难以发送。与tcp 协议的lo 各域相对照， udp 报头仅包 含了四个域：源端口、目标端口、长度和校验和。 3 网际控制报文协议 虽然ip 能确保数据包到达正确的目标点，但当发送过程出了某些问题时， 网际控制报文协议( icmp ) 将通知发送方且数据不再被传送。icmp 位于t cp ip 模型互连网层的ip 协议和tcp 协议之间，它不提供错误控制服务， 而是仅仅报告哪一个网络是不可到达的，哪一个数据包因分配的生存时间( 它们 的ttl ) 过期而被抛弃。ic mp 常用于诊断实用程序中。 分布式存储平台的路由算法和本地资源管理 4 地址解析协议 地址解析协议( arp ) 是一个互连网层协议，它获取主机或节点的mac 地址( 物理地址) 并创建一个本地数据库以将mac 地址映射到主机ip ( 逻辑) 地址上。arp 协议与ip 协议紧密协作，因为ip 再指导发送数据到目标主机之 前必须具有目标主机的地址。如果一个主机需要知道在同一子网的另一主机的m ac 地址，第一个主机将向网络发送一条广播消息，“ip 地址为aa bb cc dd 的计算机请发送给我你的mac 地址”。在本地子网中具有ip 地址aa bb cc cc 的主机将广播一条包括目标主机物理地址的arp 响应。为使arp 更 加有效，计算机在一个缓冲区保存已经知道的ip mac 地址映射表，这样就 无需广播冗余请求。 除核心的传输层和互连网层协议之外， tcp ip 协议群还包括几个应用 层协议。这些协议工作于tcp 或udp 及ip 协议之上，将用户的请求翻译成网 络可阅读的格式。下表描述了较通用的应用层协议： t elnet ：一种终端仿真协议。用于通过tcp ip 协议群登录到远程主 机上。t elnet 常用于连接两个不同的系统( 如pc 和unix ) 。通过t eln et ，你可控制处于局域网和广域网，如internet 上的远程主机。例如， 网络管理员使用t e1net 从家中登录到公司的路由器上以修改路由器的配置。 文件传输协议( ftp ) ：一种借助tcp ip 协议进行发送和接收文件的协 议。ftp 是一种客户机n 务器协议，在该协议中运行ftp 协议服务器部分的 主机接收来自于运行ftp 客户机部分的另一主机的命令。它通过一组非常简单 的命令构成它的用户接口。 简单邮件传输协议( smtp ) ：该协议负责将消息从一个邮件服务器上传输 到intern et 上或其他基于tcp ip 协议的网络上的另一个邮件服务器。 s 醛tp 使用简单的请求一响应机制传输信息，并依据更复杂的协议，如邮局协议 ( p0p ) 来跟踪邮件的存储和转发。 。 简单网络管理协议( snmp ) ：一种用于管理tcp ip 网络设备的通信协 议。为使用snmp ，网络中的每个设备将运行一个代理程序以收集关于该设备 的信息。snmp 将收集到的信息传输给一个中央数据库。所有的标准网络管理 程序都使用sn mp 。 网络中的每个节点必须有一个惟一的称之为地址的标识号。网络可以识别两 类地址：逻辑和物理( 或mac ) 地址。mac 地址被嵌入进一个设备的网络接口 卡中，因而是不可变的。但逻辑地址依赖于协议标准所制定的规则。在tcp i p 协议群中， ip 协议是负责逻辑编址的核心。因此，在tcp ip 网络中地址 有时也被称为“ip 地址”，ip 地址依据非常特定的参数进行分配和使用。 分布式存储平台的路由算法和本地资源管理 每个ip i g s t y - - 个惟一的32 位数，被分割成4 组0ctet ， 或8 位字节， 每组用句号分开。一个合法的ip 地址如144 92 43 178 。一个ip 地址包含两类信息；网络和主机。第一个0ctet 标识网络类。存在三种类型 的网络：a 类、b 类、c 类以及c 类。表2 1 总结了tcp ip n 络通用的三种类 型： 表2 1 三种类型的网络 网络类开始8 位字网络数每个网络中主机 al 一1 2 61 2 61 6 7 7 7 2 1 4 b 1 2 8 1 9 l 1 6 0 0 06 5 5 3 4 c1 9 2 2 2 3 2 0 0 0 0 0 2 5 4 注意：虽然8 位有256 种可能的组合，仅仅只有l 254 能被用于标识网络和主 机。数字0 和2 5 5 被保留来用于向网络中所有站进行广播或发送信息。 a 类网络中的所有节点共享ip 号的第一个字节，该号从l 开始n 26 。b 类网 络中的所有节点共享ip 号的最初两个字节，它们的ip 地址从128 开始到19l 。 c 类网络ip 号共享最初三个字节，第一个字节位于l92 与223 之间。例如， 具有下列ip 地址的节点可能属于相同的a 类网络：23 78 1 l0 109 ， 23 164 32 97 ，23 48 1 12 43 ，以及23 108 37 22 。具有下列ip 地址的节点可能属于相同的b 类网络： l68 34 88 2 9 、l68 34 55 4l 、168 34 73 49 以及168 34 2 05 1 l3 。具有下列ip i g 址的节点可能属于相同的c 类网络：204 、139 1 l8 7 、204 。l39 1 l8 54 、204 139 。l l8 14 以及2o 4 139 1 l8 31 。 由于只有在因特网上才能获得a 类网络，大部分a 类网络被保留用于大公司或 政府，此外，一些i p 地址被保留用于网络功能，如广播消息不能被分配给机器 或设备使用。注意到127 对于任何ip 号不是一个合法的开始字节，因而地址从 127 开始的i p 地址被保留用于在网络接口卡内循环传输信息，如地址为127 0 0 1 的ip 地址称为内循环地址。当试图与这个ip 号通信时，你通常与自 己的机器通信。当必须解决工作站的tcp ip 通信问题时，这个地址是非常 分布式存储平台的路由算法和本地资源管理 有用的。如果从内循环测试中接收到一个正确的响应，则证明tcp ip 协议 在工作站上已被安装和使用。 一个公司能从int ernic ( 也被称为n e t w o r ks o l u t i i n s ) ，即当前的 因特网命名机构或isp 处( 因特网服务提供商) 申请一个网络地址类，其中is p 可能代表公司从internic 申请网络地址或其保留的ip 地址给公司。 分布式存储平台的路由算法和本地资源管理 第三章服务器模型 在计算量不大的服务器中，影响服务器性能的最大因素之一就是i 0 的效 率，c p u 速率与外设速率不匹配、以及与网络速率差异所导致的i o 问题是实 现高性能服务器的关键。 i ，o 模型在u n i x 环境中有四种，分别是阻塞i o 、非阻塞i o 、信号驱动1 o 和异步i o 。但是，信号驱动i o 作为复杂的服务器i 0 驱动机制还不是很成熟： 而l i n u x 下( 我们选择的运行平台为l i n u x ) 的异步i 0 实现也还没完成，所以 就暂不考虑这两种机制。 u n i x 中的i 0 都是通过文件( 或文件描述符) 来操作的。我们可以把这些 文件分为两类：快速和慢速。这与文件的读写的速度并没有关系。如果对文件 的读写的请求的结果在可预测的时间内可以返回，那么这类文件就叫快速的。反 之对慢速文件的操作可能导致无限的等待。下表是文件的类型和它的i o 的分 类： 表3 1 文件类型与i o 分类 文件类型分类 常规文件快速 目录快速 块设备快速 字符设备不定 管道慢速 套接字慢速 其中字符设备要根据具体的情况而定，如d e v m e m 是快速文件，而终端 ( 通常s t d i n ，s t d o u t ，s t d e r r 与它相连) 就是谩速文件。 对快速文件进行读写操作总是能完成并迅速返回。对慢速文件的操作，可能 会阻塞，而且在返回时并不一定完全完成了操作( 可能只读写了部分数据) 。在 服务器中要注意的也就是这些慢速文件。 阻塞i o ：调用要一直等到请求的操作完成。当调用i o 请求的系统调用时， 如不能马上完成( 读时缓冲区无数据，或写时缓冲区无空间) ，则进程会睡眠直 到条件满足时，继续有关操作后再返回。 非阻塞i o ：遇到i o 操作不能马上完成时，不会让进程睡眠而是返回一个 分布式存储平音的路由算法椰本地资源管理 错误，程序就可以在此时继续做其它事，到适当的时候再继续未完成的i o 操作。 这里讨论的服务器结构可以应用于逻辑上是服务器客户端模式的网络服务 器。最简单的服务器是单个进程；q 页- f 接受请求，处理完一个请求后再接受下一个 请求。但在实际中这是不可行的，网络服务器会同时接受到大量的请求，顺序处 理会导致客户响应时间过长，所以服务器必须能并发的处理这些请求。 大多数的网络应用都遵循以下几个步骤： 1 接受外部的t c p i p 连接或创建一个与其它机器的连接。 2 连接建立，通过t c p i p 双方交换命令。 3 这些命令引起服务器上的多种行为的发生( 如磁盘读写，调用外部程序 等) 。 通常，这些网络应用的性能体现在几个方面： 1 尽快的完成并发任务 2 有效的处理大量的等待( 由t c p i p 引起，或者等待通信的另一方发下 一条命令) 要实现一个高性能的网络服务器，必须选择一个能够正确处理以上标准的构 架。下面讨论几种典型的服务器构架和它们各自的特点。 3 1多进程服务器模型 1 】为每一个请求立即创建处理进程 多进程的并发服务器可使用f o r k 系统调用。这种服务器有一个主进程，在 主进程使用一个简单的循环不断的接受新的请求连接，然后对每个请求连接f o r k 一个子进程来处理这个请求。当请求处理完成后，进程退出。 此模型有两个主要优点，第一个优点是主程序简单，因此也就很稳定。第二 个优点是子进程不会出现内存泄漏的情况，因为每个进程结束退出时，它所占有 的内存会由操作系统自动清除。而且每一个子进程都是独立的处理不同的网络连 接，子进程之间也就不需要同步机制。 这个模型在负载比较低的时候，可以达到较好的性能。中等负载的时候，如 果进程映象较小，或者用了针对应用的高效措施，或者应用本身不会有太多的并 发任务时，也比较合适。 但是，由于f o r k 系统调用需要相当大的系统开销，而且进程是一个系统中 最大的实体，系统中能同时存在的晟大进程数也是有上限的，而f o r k 服务器处 理一定数量的连接就要有同等数量的进程来服务，这样不仅消耗的资源客观，还 存在上下文切换的较大开销。所以这种结构的处理能力不高，通常每秒能处理几 个至十几个请求。 分布式1 竿帖吼i 台的路由期法和奉地资源崔理 2 ) 预创建进程 这种服务器模型不是在一个请求到来时创建一个新的进程，而是预先创建一 定数量的进程来等待未来需处理的请求。这些预先创建的进程一直驻留在系统中 并行的处理请求。当一个进程处理完一个请求后不必退出，它可以接受下一个请 求。 和上一种情况相比，预创建进程服务器减少了f o r k 系统调用的开销。所以 它的性能是相当高的，每秒中能处理的连接数是简单f o r k 服务器的2 至1 0 倍。 预创建进程服务器有几个关键的地方需要考虑： 任务的分配：在u n i x 环境中有几种方法，第一种方法是主进程接受请求的 连接，将连接成功的文件描述符通过管道或u n i x 域套接字传递给预创建的服务 予进程；第二种方法是在服务进程中直接接受请求，它们之间的互斥可以通过用 文件锁来实现。需要注意的是同样一个方法在不同的操作系统上有时是不可移植 的。同时主进程可以根据负载的轻重情况在一定范围内动态的调整总的进程数。 和每个请求创建一个进程的服务器相比，预创建进程服务器的实现时要注意 不能因为程序错误发生崩溃，不要发生内存泄漏而造成地址空间的混乱。 解决内存泄漏的问题的办法有