【毕业学位论文】（Word原稿）一种支持动态可配置的高效组通信系统的设计与实现-计算机系网络与分布式系统

北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 1 - 摘 要 快速有效地搜集 的网页，使搜索引擎索引更多的网页，是其提供高质量服务的基础。采用分布式搜集策略可以很好完成这一任务。但由于网上信息分布的不规律性和广域性。要应用可靠的组播通讯（ 术来实现搜集系统的负载平衡和动态调度性，即运行过程中添加和删除主控于分布式的 集系统中。 本文基于“天网”搜索引擎系统 构建了一个可靠的组播通讯系统平台。它借鉴了 学的 统，实现了分布式 集系统的组视图维护和可靠的组播通讯。本文论述的系统 结构和方法，将用于“天网” 的开发，达到提高系统能力，改善系统的可扩展性的目的。 关键词 可靠的组播 传送、组视图、分布式、动态可配置、搜索引擎、万维网 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 2 - 第一章 引言 景简介 介 万维网 (简称 一种特殊的结构框架，它的目的是为了访问遍布在因特网上数以万计的机器上的链接文件。在短短的五年之内，它从一种发布高能物理数据的方式演变为如今数百万人脑中的“因特网”。它之所以如此流行是由于它有一个丰富多彩的界面，初学者很容易使用，并且还提供了大量 的信息资源，几乎涉及人们所能想象的所有主题，如从土著人到动物学。 989年 瑞士日内瓦欧洲粒子物理实验室 先开发的一个分布式超媒体信息查询系统。 在 物理学家 1989 年 3 月 倡导下开发出来的， 牛津大学的毕业生，从事过文字处理及实时通信方面的研究。他开发 动机是建立一个信息系统，在此系统中许多科学家可以相互合作，交流信息。 用超文本 (术将许多信息资源连接成一个信息网，信息网由结点和超链接组成。 结构不同于文件系统的线性结构， 的结点的连接关系是相互交叉的，一个结点可以以各种方式与另外的结点相连接。超文本的优点是用户可以通过传递一个超链接得到与当前结点相关的其它结点的信息。超媒体是一个与超文本类似的概念，在超媒体中，超链接的两端可以是文本结点，也可以是图像，语音等各种媒体的数据。 第一个原型（基于文本）于 18 个月后运行。 1991 年 12 月在德克萨斯州的 1 超文本会议上进行了一次演示，并于 1993 年 2 月，随着第一个图形界面 发布而达到了其发展的高峰。 在 1993 年下半年， 不到三个月的时间里翻了一翻。在 1995 年 4月， 网上的流量超过了其它 其它服务的流量，成为 1997 年 12 月，根据 究院在科学杂志上发布的数据，网上大约有 3 亿 2000 万网页。 在最近两年里， 得到了长足的发展，不仅成为企业必不可少的组成部分，并且开始走进千家万户。根据 究院截止到 2000 年 2 月， 务的有效网站 4,217,324 个；共有不重复 页超过 10 亿。 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 3 - 索引擎简介 发展给人们带来了巨大的方便，使得人们可以跨越时间和空间的界限来共享大量的信息。但是，面对如此大量的信息，我们同时也开始感到无所适从。太多的信息使我们很难迅速定位到我们真正需要的部分；由于 有统一的组织和规划，仅靠超链 (无目的地漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发现工具来为他们在 进 行导航。 目前，一个有效的途径是建立搜索引擎。搜索引擎系统通过程序自动地从网上搜集和分析网页，建立索引，为用户服务。这类系统的优点是涵盖的网页数量巨大，但搜索的准确率相对比较低，其典型代表是 搜索引擎出现于 1994 年，在短短的 7 年时间里，经历了天翻覆地的变化。1994 年， 作为最早出现的搜索引擎之一，可以索引 110,000 网页。 1994 年 3 月、 4 月， 均每天收到 1500 个查询。 1997年 12 月，当时的顶级搜索引擎 称可以索引 1 亿网页， 千万条查询。进入 2000 年搜索引擎开始以尝试索引“整个标志。几个主流的搜索引擎，如 都不断扩展自己的搜集能力，企图将整个 的数据都搜集到，建立索引并为用户提供服务。 2000 年 12 月， 索引擎可以索引 1,326,920,000 网页， 储超过 10 亿的网页，每天可以收到亿万计的查询。 随着搜索引擎的发展，逐渐出现了自动分类技术代替人工分类。 2000 年 3 月， 布研 制出先进的目录搜索技术，准备与 讯公司合作推出更加快捷、全面的目录搜索引擎服务。 在一定程度上使用了该技术。 搜索引擎面世后，虽然抱怨不断，但它迅速成为人们网上搜索的有效工具。根据统计，大约 85%的用户使用搜索引擎去定位他们需要的信息 5；并且，几个著名的搜索引擎一直都稳定的处于全球访问量最大的 10 个网站之列。 网搜索引擎简介 国外搜索引擎虽然起步较早，功能全面，性能良好，但是它们的共同缺点是都 不能很好地支持中文信息的发现和查询。虽然 搜索引擎在 1998 年上半年宣布支持中文，但在对中文信息的处理上还存在很多不足，如不能准确切词，不能在上下文环境中理解语义等等。 天网 (英文搜索引擎是北京大学计算机系网络与分布式系统研究室在“九五”科技攻关项目基金的资助下研制开发的，它是主要针对中国丰富的信息资源而开发的具有中文特色的搜索引擎。自 1997 年 10 月正式在 提供查询服务以来，“天网” (总访问量已突北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 4 - 破 800 万次，目前日访问量约为 3、 4 万次，得到了广大用户的好评。 网搜索引擎的系统结构 图 索引擎的系统结构 图 出了 系统结构。可以看出，从功能模块上划分，统 集子系统）、 引子系统）、 索子系统）和 志挖掘子系统）四个子系统构成。 括制器 )、 集器 )和 始数据库 )； 括 引器）和 引数据库）； 括 索器）和户接口）； 括 户行为日志数据库）和 志分析器）。 了按照启发式算法优先选择重要的 完成站点过滤、实现 议及域名解析 功能。 照 议负责从网上抓取网页，为提高网页搜集速度，通常可以同时启动上百个 时工作。 时对搜集回来的网页内容进行分析处理，包括调用切词软件以提取关键词和摘要，提取 链，记录网页的元信息（如作者、修改日期、长度等），并将这些内容存入 内容重新组织，建立 提高检索效率。 它转发给 据查询项和内容，找到匹配的网页后，进行相关度计算并排序，然后通过回给用户。另外， 序还将用户行为信息（包括用户查询项、用户点击的 户翻页情况等）记录到 于跟踪用户行为，以提高搜索引擎的服务质量，如可以学习新词来动态更新词典控制器 搜集器 原始 数据库据库 索引器 索引 数据库 检索器 用户接口 户 用户行为日志数据库 日志分析器 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 5 - 内容。 网的技术特色 天网的搜索范围除中国 丰富的信息资源外，还包括 务器的 网属于机器人搜索引擎范畴，主要采取了基于服务器模式具有导 向功能的搜索和提供文本摘要的方式。在实现中，天网使用了中文自动识别和中文编码自动转换技术、根据中文的语言特点和表达习惯对中文信息进行词语切分和词类标注技术以及基于词的大型、高效的信息索引数据库和快速准确的检索技术等先进的中文信息处理和索引技术，从而大大提高了中文信息的理解程度和发现、检索效率，同时也提高了汉语的查准率。 目前，天网还不支持中文分类目录，只提供关键词（或关键字）查询。 系统的前端提供了 种接口，后台则由若干 主控的导向控制下，使用具有高度智能性和适应性的信息发现 算法搜索网页及 取关键词及摘要，形成原始数据库，然后在此基础上建立索引数据库。 来自前端的用户信息，传给检索服务器，经过查询优化，产生结果回送用户。 天网搜索引擎的检索是基于词汇的，克服了中文分词的困难，同时具有中英文词汇自动学习的能力。 它侧重于中文信息的发现，向全世界的中文用户提供准确、有效的网络中文信息。 于采用了可伸缩的分布式结构、查询 引数据库和检索数据库分开等先进、有效的技术，使得系统占用资源少、信息收集速度快、用户查询响应时间快（系统对 上的查询可在 1秒钟之内作出响应）、查准率和查全率较高，基本达到了实用化程度。 系统在设计和实现过程中，充分考虑到了用户和管理员的使用习惯，提供了浏览器、电子邮件、中英文用户接口和方便使用、功能丰富的管理工具，因而有很好的可用性和易用性。 综上，天网搜索引擎具有以下技术特色： 信息收集符合 相关协议和标准。 实用、高效的信息分析方法 高度智能性和适应性的信息发现方法 中文信息处理技术 可伸缩的分布式结构 基于词的大型、高效的信息索引数据库和快速、准确的检索方法。 智能化、多功能的 用户检索接口 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 6 - 网的搜集系统中引入分布策略及组通讯技术的意义 要在搜索引擎中尽可能地找到用户所需信息，就要求搜索引擎索引尽可能多的网页。因此索引网页数量是评价一个搜索引擎好坏的关键因素之一。要索引更多的网页就要获取更多的网页，因此高效 地获取网页是一个好的搜索引擎的基础。 提到“高效”执行某些大数据量的工作，人们容易想到“分布式”、“并行处理”这样的字眼。事实也是如此。目前，日访问量已突破 3 万的北大“天网”中英文搜索引擎系统（ 采用集中式搜集网页的处理方式（一个 主控控制多个搜集程序并行工作），索引网页达到 100 万量级。全部网页更新周期为 10 天，即 每天大约要搜集 10 万网页，达到 100 万量级。 出自斯坦福大学的 索引擎在 2000 年 7 月可以索引 560,000,000 网页，要达到这个量级，网页的更新是集中式系统在短时间内所不能胜任的。如果以 达到 1000 万量级需要 100 天， 100 天中由于网页的更新，将使搜集到的部分网页失去意义。因此，采用分布式技术在尽可能短的时间内搜集尽可能多的网页，是研制高效搜索引擎的关键技术。 与传统的集中式系 统相比，分布式系统具有下述优点： 优点 说明 经济性 微处理器能提供比大型机更好的性能价格比 速度 分布式系统能提供比大型机更强的计算能力 固有的分布性 有一些应用包含物理上分散的机器 可靠性 当某台机器崩溃时，整个系统仍能正常工作 可扩展性 计算能力逐步增加 表 布式系统的优点 尽管分布式系统有自己的优势，它也有自身的缺点。首先是软件问题。即便使到今天，我们依然没有多少设计、实现和使用分布式软件的经验。第二个问题与通信网络有关。网络可能丢失数据，需要有特殊 的软件处理。它也有可能过载，当网络饱和时，要么被替换掉，要么增加一个新的网络。这两种选择都需要全部或部分地重新布线，更换网卡。当系统依赖于网络时，网络中的数据丢失或过载会抵消分布式系统的优点。第三，数据共享导致安全性问题。 尽管有上述潜在的问题，总的说来分布式的优点超过了它的缺点，并且分布式系统将越来越重要。就搜索引擎系统而言，采用分布式系统更是利大于弊。身就是分布式的，适合于采用分布式方案搜集索引。搜索引擎系统采用分布式，可以继承分布式系统本身的优点，同时，通过精心设计，可以避免分布式 系统本身的缺点。我们首先面临的就是分布系统中软件问题，为使我们的分布式系统具有高可用性、动态可配置性，负载平衡，需要解决分布式系统中进程之间的组通信问题。 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 7 - 程组通讯技术简介 在分布式系统结构中，互相协作的进程需要通信和同步。例如，分布在不同计算机上一到多个进程，通过互相之间的通信实现一个服务，也许还要提供容错功能以增加可用性，采用简单的点到点的信息交换方式并不是最好的方法。组通信（ 适合这种方式。组通信是一个进程发送消息给一组进程。在分布式应用中，能够提供容错功 能的组通信是一种非常有用的方法。引入组概念的目的是想将进程的集合作为一个抽象的整体来处理。这样一个进程可以发送一个消息给一组服务器，而不需知道该组的成员数目，它们的位置等等。 根据对可靠性的要求组通信协议主要分两大类 5。一类是保证组通信具有很强的可靠性。这一类组通信通常包含原子性性。原子性保证一个发送给某个组的消息，它要么被该组所有成员接收，要么就不被任何成员接收。原子性同时可以提供消息传递的顺序性，虚拟同步，安全性，时时性，网络断开等要求。但是要保证很高的可靠性，必须采用昂贵的协议，从而带了了系统在 大负荷运行条件下的不稳定和性能不可预测，以及有限的可伸缩性。短暂的系统性能问题可以导致这些协议处理能力的大幅下降。即使在很稳定的网络条件下，也很难将这类协议扩展到有几百个参与者的情况。 另一类协议努力保证大规模条件下的最大可能的可靠性。如 用于网络新闻的分发） 25， 26， 12， 27。这些系统包含了可伸缩的多播协议来克服消息的丢失和失败，但是不能保证端到端的可靠性。没有核心系统跟踪组中的成员，因此可能不清楚哪些进程属于多播的目的进程，也不清楚多播组是大还是小。典型的情况是，进程匿名加入多播发送树。同样的，一个进程组的成员可以退出或者失败而不用事先通知它的临近进程。 组通信的实现很大程度上取决于硬件。在一些网络里，可以创建一些特殊的特殊网络（例如，将地址高位置 1），来通知监听的多台机器。当消息包被送往这些地址中的一个时，它会自动被传递到所有在该 地址上监听的机器。这种方法称为多播（ 用多播实现组通信很容易，只要为每一组指定一个不同的多播地址就可以了。第二种实现组通信的方法是采用广播 ,即目的地址为某个特定地址（比如说， 0）的包被发送到所有的机器。但是效率低，每台机器都将收到广播包，都需要特殊的软件来检测这一个包是不是自己应该接受的。如果不是，包被丢弃。但是，处理中断浪费了大量时间。第三种方法，在上述两种方法均不存在时，组通信可以通过发送者分别发送消息给组中每一个成员来实现。尽管效率低，这种方法确实是可以使用的，特别是在大多数 组都很小的情况下。 组通信设计方案上需要考虑如下问题：闭合组和开放组；对等组和层次组；组成员；组编址；发送和接收原语；原子性；消息序列；组重叠；可扩展性。 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 8 - 1. 闭合组和开放组：闭合组指只有该组的成员才可以发送消息给该组。开放组指系统里任何进程都可以发送消息给任意组。 2. 对等组和层次组：对等组中所有进程都是处于同等地位的。所有决策都由组中所有进程共同决定。层次组中协调者进程进行决策，当有一个来自外部客户或组内成员的请求时，它被首先送给协调进程，由协调进程来决定那个参与者进程适合完成这项请求。 3. 组成员问题涉及 到组的创建和删除，进程加入或离开某个组。 4. 组编址：为了向一个组发送消息，进程必须要能够指定它的目的组地址。 5. 发送和接收原语：理想情况下，点到点和组通信应该采用用一组原语。但是，若采用 不是原始的 为通常的用户通信机制，会很难将 6. 原子性：大多数组通信系统里，一个被发送给某个组的消息，它要么被该组所有成员正确接收，要么就不被任何成员接收。不允许组内一些成员接收了该消息，而另一些成员却没有。这种整体传递的性质称为原子性。 7. 消息序列：来自于不同进程的 多播消息包可能以不同的顺序到达多播的目的进程，从而产生数据的不一致。组通讯需要保证存在因果关系的消息以同样的顺序到达各组成员。 8. 组重叠：一个进程可以同时是多个组的成员。这样会导致同时属于两个组以上的进程接收到不同顺序的消息。在不同组之间实现时间排序通常很难办到，因此需要考虑这样做是否值得。 9. 可扩展性：许多算法在组内只有少数几个成员时工作得很好，但如果每个组内有几十个，几百个，或是几千个成员呢？或者，有几千个组呢？同样的，如果系统大到单个局域网已不能满足要求，而需要多个局域网和网关时，该怎么办呢？如果组被 分散到几个大洲，又该如何处理呢？ 最早包含组通信系统的是 V28系统。其后有了在第二章中要重点介绍的学的组通信以及 统的组通信等支持组通信的系统。 们采用的方案 由于我们开发的组播通讯系统是面向“天网 ”的分布式搜集系统的一个工具包，它所采用的设计方案以保证“天网”的高效准确运行为主，同时考虑到软件的复用性及以后系统的升级，兼顾效率和功能的完备性。 目标是搜集中国所有的网页。 根据计算， 要搜集9,520,000 左右的网页。以 10 天为周期，仍然按照 有的速度进行搜北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 9 - 集，则需要 10 台机器分布式协作，并且在单台性能没有降低的条件下才能够完成。达到上述目标的同时，希望分布式系统具有如下特点： 1. 负载平衡 2. 主控通讯量少 3. 具有可扩展性，即随着主控的增加性能应有所提高 4. 具有动态调度性，即运行过程中添加和删除主控 因此，我们的组播通讯系统面向的是一个规模较小，组视图变化不频繁，要求通讯量尽量小，运行速度尽量快，而且要求提供消息传播的高可靠性和完备的组视图维护功能的进程组。 基于目前的设备，这个组播通讯系统以 议为通信基础 。它是一个闭合组，任何一个搜集主控要想和组中的进程互发消息，都要首先加入组。它是一个层次组，存在着一个协调者，组中所有成员的 址按照顺序存储在一个组地址数组中，每个组成员在自己的内存中维护这样一个组地址数组，它的一致性由协调者发送特殊的组播消息来维护；规定组地址数组中的第一个成员为协调者，因此当组视图发生变化时，协调者有可能改变。其中的组播消息必须有严格的可靠性，原子性， 组通讯系统还需要保证存在因果关系的消息以同样的顺序到达各组成员。 章的组织和结构 本文的实践工作主要包括参与了北大“天网 ”中英文搜索引擎的分布式搜集系统中的进程组通信系统的设计和实现。本文主要介绍了进程组通信技术的一些基本概念，目前比较有代表性的几个进程组通信系统，以及如何在“天网”的分布式搜集系统中应用相关技术实现我们的进程组通信系统。其中重点是应用于“天网 ”的进程组通信系统的设计和实现。 文章余下各章的内容大致如下： 第二章（进程组通信相关研究）主要介绍目前比较有代表性的进程组通讯系统： 学的组通信以及 统的组通信等支持组通信的系统。 第三章（进程组通信系统的设计）主要介绍“天网”的进程组通 信系统设计方案。首先介绍了设计的目标和整体结构；其后，详细介绍了在进程组通信系统中是如何确保消息的可靠性，有序性和当组视图变化时组播消息的一致性。 第四章（进程组通信系统的实现）主要介绍了“天网”的进程组通信系统的实现。首先介绍了用户接口，接着介绍了几个工作线程和主要的数据结构，然后详细介绍了消息接收和处理过程及消息发送过程的实现。 第五章（总结与展望）总结了目前的“天网”进程组通信系统的现状和不足，为以后的进一步工作进行了展望和设想。 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 10 - 第二章 进程组通讯相关研究 目前比较有代表性的进程组通讯系统是 下面要重点介绍的 学的组通信以及 统的组通信等支持组通信的系统。 学的组通信系统 a) b) c) 图 2.1 a)同步系统 b)弱同步系统 c)虚拟同步系统 学已经开发了三代可靠性组通信技术以及正在开发的第四代可靠性组通信技术。 具集 : 1987 统 : 1990 统 : 1994 统 : 1999- 统的结构目标是基于进程组的可靠性分布式计算。 一个建立分布式应用的工具包，类似的应用如，协调纽约、瑞士证券公司各个代理的股票交易，法国航空交通管制系统，西南贝尔电话网络等。 是一个完全的操A B C D 2 时间 A B C D 2 A B C D 2 达 达 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 11 - 作系统，而是一组程序的集合，这些程序可以在 其他现存的操作系统上运行。 主要思想是“同步”，它的主要通信原语是形式各异的原子广播。在讨论 何实现原子广播之前，有必要首先来看一下几种同步类型。一个同步的系统是这样的，它 的事件按照严格的顺序发生，每个事件理论上都只是在 0时间内完成。例如，如果进程 、 ，如图 2消息将瞬间到达所有的目的地。同样，接着一个从 D 发送的消息也只需要 0时间被传送到各个目的地。从外部观察者的角度看来，系统由离散的事件构成，彼此之间互不重叠。 同步系统是不可能创建的，所以需要考察其它在时间上要求较低的系统。如图 2个“弱同步系统”可以满足要求，它的每个事件需要一个有限的时间，但是任何一方看来，所有时间顺序都是一样的。特别是，所有的进程按照同样的顺序接收消息。 这样的系统是有可能实现的，但对于一些应用来说，甚至更弱的语义也可以接收，因此就可以减弱语义，换取性能。图 2一个“虚拟同步系统”，它放宽了包的顺序限制。 在一个分布式系统中，两个事件被称为“因果相关”，如果第二个事件的行为可能受到第一个事件的影响。所以如果 A 发送一个消息给 B， B 接收了，然后发送一个新的消息给 C，那么第二个消息就和第一个消息因果相关，因为它的内容可能包含了第一个消息的一部分，而是实际上是否如此并没有关系。只要可能存在影响，这种相关就成立。 两个不相关的事件称为“并发事件”。如果 A 发送了一个消息给 B，同时 ，这两个事件就是并发的，因为互相没有影响。虚拟同步的真正含义就是，如果两个消息是因果相关的，那么所有的进程必须以相同的顺序接收它们。但是，若它们是并发的，就没有什么限制，系统可以随意的按不同的顺序将它们发送给不同的进程。 现在讨论 用的广播原语。其中有包括三个： 它们具有不同的语义。 供弱同步通信，用于传送数据到一个组的成员。 供虚拟同步通信，用于发送数据。 些类似于和 它用于管理组成员，而不是发送普通数据。 送者 常是一个序列号），把它发送给所有的组成员（显示的指出所有组成员的名字）。每个成员检查该消息的时间辍，域它所发送和接收过的时间辍比较，从选出最大的，北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 12 - 把它发送回 A。 A 收到所有返回的时间戳以后，选择其中最大的，在一次发送一个含有 该时间戳的“提交”消息给所有的成员。提交的消息被按时间戳的顺序传递给应用程序。这样的协议保证了所有的消息可以以相同的顺序被接收。 这种协议很复杂，而且代价太昂贵。因此， 设计者们又提出了 只保证有因果相关的消息被顺序接收。（ 议现在已经更新过了，但即使如此，也比 慢。） 议工作如下：如果一个组有 么每个进程就维护一个 个元素对应于一个成员。第 始时，该向量设为 0，如图 图 息只能在所有与它有因果关系的“原因”消息被传送后，才能被传送 当一个进程有消息要发送时，它在自己保留的向量里，将相应于自己的元素加 1，然后将该向量作为消息的一部分发送出去。当图 1到达 将检查该消息是否依赖于某些 向量的第一个元素应该比B 自己保留的值多 1，其他都一样，因此该消息被接收，然后被传递给在 B 上运行的组成员。 现在 B 发送了一个消息 ，它将在 该向量里， C 发现在 发送的消息，而因为它还没收到任何来自A 发送的消息， 到 A 的消息到来。无论如何， 的消息之前被传递出去。 下面介绍一个通用算法，它决定将进来的消息缓存还是传递给用户进程。设 i 分量， i 个分量。假设消息是从 接收的首要条件是 。它表明，这是从2 A B C (0,0,0) (0,0,0) (1,0,0) (1,1,0) (1,0,0) (0,0,0) 初始 向量 消息 达但不能发出 在 达并发给应用程序后， 被发给它 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 13 - 就是说，没有消息被漏掉。（来自同一发送者的消息总是因果相关的。）其次，必须对所有的 i j， 表明发送者还没有发现任何接收者错过的消息。如果一个进来的消息符合这两项检验，系统就可以将它传递给用户进程，而不用延迟。否则，它必须等待。 图 示了一个有关向量机制的更详细的例子。进程 0 发送一个包含向量（ 4,6,8,2,1,5）的消息给其他 5 个组成员。进程 1 已经看见了和进程 0 一样的消息，因此该消息通过检验，被接收，并被传递给用户进程。进程 2错过了进程 1发送的消息 6，所以进来的消息必须等待。进程 3看见了和进程 0所看见的所有消息，此外还有来自进程 1的消息 7，它显然还没有被进程 0得到，因此 该消息被接收。进程 4错过了来自进程 0的签一个消息，所以新的消息必须等待。最后，进程 5也比进程 0稍微超前，因此该消息被进程 5接收。 在 最重要的是 达了弱化的基于因果关联的通信语义，它的实现是在消息里加上了一个序列号向量，这样允许接收者检查该消息是应该被立即传递，还是延迟到在它之前的消息到来之后。 持重叠分组得消息排序，但算法比较复杂。 图 供了基于组通信的分布式应用框架，这些应用包括容错系统、可管理的分布式系统，以及使用数据复制、缓存一致和群件的应用。总的说来，的是以最小的代价为应用程序的需求提供通讯模块。 案原先是为重新设计 出的，结果发展成为一种通用意义上的组通信体系机构，为开发健壮的分布式系统提供更高级的支持。如当应用程序对安全性或者时时性有特别的要求时， 能支持，但 够支持。 由进程 0 送出的 消息 中的向量 在其他机器中向量状态 0 4 6 8 2 1 5 1 3 6 8 2 1 5 2 3 5 8 2 1 5 4 2 6 8 2 1 5 5 3 7 8 3 1 5 3 3 7 8 2 1 5 接收 延迟 接收 延迟 接收 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 14 - 行的更快，消耗资源更少。 建 立组通信中虚拟同步（ 准做出了巨大的贡献。 通信系统是由 学联合完成的。允许进程创建进程组，支持进程组的具有可伸缩的可靠的多播和点到点通信，同时支持因果序，全序，流控等属性。 似于 堆叠式结构，可以运行的象样快速。 展了 性能，增加支持多重分裂，有效的密钥重发，应用程序定义安全策略。 用现成的认证系统，如 不是象 计了自己的安全机制，采用了非标准的密钥分发系统和定时服务。为了便于系统验证， 程语言完成。 创了基于 虚拟同步的组通信先河。但是为了解决虚拟同步本身具有的很大限制，例如，当参加虚拟同步的进程在 3 到 100 个时，工作的很好，但是当组成员继续增加时，系统变得很脆弱。尤其是当组逐渐变大，数据吞吐量变得不稳定。因此 开始了 统研制。 于全 新的方法。其核心协议支持多点数据传送，并能保证相当高的可靠性。这种模型采用可伸缩性协议，即使在不同形式的攻击下，或者在每组包含成千上万成员的多组通讯情况下，也能保证稳定的吞吐量。 统的目标是嵌入重要的软件结构和网络操作系统中。 通信 一个分布式操作系统，它使许多 I/O 设备象一台独立的计算机一样工作，它还为并行程序设计提供条件。 1981 年诞生于荷兰阿姆斯特丹的 学，主要由 . 他的 3 个博士生. 计的。在 1983 年，第一个版本 入使用。 持组通信。 的组由一个或多个协同执行某个任务或提供某个服务的进程组成，这些进程可以同时是几个组的成员。组是封闭的，客户存取一个由某个组提供的服务的典型方法是用 组中的一个成员通信，那个成员通过组通信决定组内哪个成员应该做什么（如果必要的话）。 选择这种设计是为了提供比开放组结构更大的透明度。这种思 想的深层是客户通过 单独的服务器通信，所以它也可以通过 整个组通信。开北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 15 - 放组利用 单独的服务器通信（而不是利用组通信和组服务器通信），透明度不高。一旦可以使组外的客户用 组通信（实际上是和组中的一个进程通信），就用不着开放组了，采用封闭组就足够了。 组通信原语 组通信可使用的操作如表 示。 立一个新组同时返回一个别的调用能够识别的组标识符，参数指定组的大小和需要的容错度（组能够容忍且同时能够正常工作的死成员个数）。 许进程进入和离开一存在的组。 一个参数是送给组中所有成员申明新来者存在的一条短消息。相似的，一个参数是一条短消息和组中所有成员道别并祝它们好运。段消息的要点是使所有的成员明白它们的通知是谁（如果他们感兴趣）。然而，保持跟踪对他们并不是必要的。但组中最后一个成员调用 ，组便删除了。 动广播一条消息给该组的所有成员，即使是信息丢失，缓冲区优先或者进程崩溃。 持全局时间顺序，所以，如果两个进程近乎同时的调用 统保证组中成员与原来同样的顺序接收信息。这时系统保证的，程序员可以依赖这一点，如果两个调用几乎同时进行，先被发送到 的保认为先发。 图从一个特定的组接收信息。如果没有可用信息，调用浙江一致阻塞到有可用信息。如果信息已经到来，调用立即返回。协议保证任何情况下信息不会不可挽回的丢失。 来恢复一个崩溃的组，它指明一个新组中成员的最小个树。如国内核能和必要数目的进程建立连接且能重建的话， 回心组的大小，否则，调用失败。 调用 描述 立新组并且设置参数 入组 开组 消息可靠传送给组中成员 塞直到组中有消息送到 程崩溃后的初始恢复 表 通信原语 可靠广播协议 支持组播和广播（如以太网）的 工作得最好。用组播实现组间通信能够避免打扰那些对送来的消息不感兴趣的机器。 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 16 - 靠 广播协议需要的软硬件配置如图 示。所有机器的配置通常是一样的，同时它们运行相同的内核。然而当应用程序启动时，一台机器将被选作 序器，就象一个委员会选举一个主席一样）。如果 下的成员重新选举一个。许多选举算法可以使用，如选择拥有最高网络地址的进程。 实现可靠广播的一系列步骤总结如下： 1). 用户进程陷入内核并传入消息。 2). 内核接收消息并阻塞用户进程。 3). 内核将消息通过一般的点到点通信方式送给 4). 当 到消息，它分派下一个可用的序列号，将序列号存入为其保存的域中，同时广播此消息和序列。 5). 当发送内核发现广播消息头中的消息，它激活被阻塞的调用进程，使其继续执行。 图 组通信的系统结构 组通信的容错功能 组通信协议提供容错功能，可以承受通信组内任意 K 个处理器（含 然崩溃的意外情况。恢复系数 K 是在通信组创建时指定的，K 的值越大，就容易产生越多的冗余，在正常情况下操作也会越慢。 许多分布式算法中都要由一个进 程充当协调者（发起者、序列生成器或担任其他特殊角色）。下面介绍选举这种协调者 的算法。 如果所有进程都完全相同，没有可以区分的特征，就无法选出其中一个作为特殊进程，因此假定每个进程都由一个唯一的进程号，如它的网络地址（为简单起见，假设每个进程占用一台机器）。通常选举算法都指定具有最高进程号的进程作为协调者。但具体做法各有不通。 二期还要假定所有进程都知道其他进程的进程号。它所不知道的是当前哪内核 内核 A S 内核 内核 A S 内核 内核 A S 应用 程序 能 能北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 17 - 个进程是活动的，哪个进程已经终止。选举算法的目的就是：保证在选举执行后，所有进程都认可某个进程成为新的协调者。 法 当某个进程 注意到协调者无法响应进程的请求时，该进程就初始启动一个选举过程。进程 P，执行的选举过程如下： 1)P 向所有进程号比它高的进程发 息。 2)如果得不到其他进程的响应，进程 P 获胜，成为协调者。 3)如果有一个进程号更高的进程响应，该进程就接管选举过程。进程 任何时刻进程都有可能收到进程号比她小的进程发送的 息。该消息到达时，消息的接收者就向消息发送者发送一个 息，说明它仍是活动进程，如果接收者没有掌管选举过程，它将接管选举过程。最后，其他进程都放弃只剩一个进程是，该进程成为新的协调者。然后它向所有进程发送消息，通知这些进程从此刻起它已是新的协调者了，从而宣布它的胜利。 一个以前被终止的进程重新恢复后，也有选举权。如果它碰巧是目前运行的所有进程中进程号最大的一个，就赢得选举，并接管协调者的工作。由于在小镇上总是最厉害的家伙获胜，因此有了“ 法”的名称。 算法 假定对所有进程进行了物理或逻辑排序，因此每个进程都知道它的后继进程是哪个进程。任何一个进程发现协调者不再起作用时，就创建一条包含该进程进程号的 息，并将该消息发送给其他后继进程。如果后继进程已经中止，就跳过它发送给下一个进程，以此类推，直到找到一个正在运行的进程为止。每个进程接收到 息后，就将自己的进程号加入消息中的进程表。 最后 息会回到创建它的那个进程。进程接收到的 息中已经包含该进程的进程号 时，就可以断定这条消息是由它自己创建的。这时，将消息类型该为 次在环上循环发送。这次是将新的协调者（进程表中进程号最大的进程）和环上现有的成员通知给其他进程。 息在环上循环一周后，从环上移去该消息，各进程恢复其原有操作。 章小结 本章高度概括了当前进程组通讯领域所采用的系统结构和方法，具体分析了几种具有代表性的系统，并分析比较了它们的核心技术。 就搜索引擎系统而言，采用分布式系统利大于弊。 身就是分布式的，适合于采用分布式方案搜集索引 。搜索引擎系统采用分布式，尤其需要解决进程之间的组通信问题。分布式系统中需要一个协调者，因此介绍了两种协调者北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 18 - 的算法： 法和环算法。 北京大学学士学位论文 一种支持动态可配置的高效组通信系统的设计与实现 - 19 - 第三章 进程组通信系统的设计 计