分布式系统模型ppt课件.ppt

《分布式系统模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《分布式系统模型ppt课件.ppt（93页珍藏版）》请在三一办公上搜索。

1、分布式系统系统模型（System Models）,结构模型（Architectural model）基础模型（Fundamental model）,结构模型（Architectural model）,分布式系统的结构模型是关于其各部分的布局及其相互间关系，它定义了系统的各组件之间相互交互的方式以及它们映射到下面的计算机网络的方式。 Client/server模型 对等进程（peer process）模型,客户/服务器模型的扩展,* 在（多个）协作的服务器上划分 （partition）和复制数据； * 由代理服务器（proxy servers） 和客户进行数据缓存（caching）； * 使用移

2、动代码和移动代理； * 以方便的方式添加和删除移动设备。,基础模型（Fundamental model）,基础模型是对所有结构模型中公共属性的更形式化的描述。交互模型（Interaction model） 交互模型处理分布式系统中性能以及设置时间限制的困难，例如对于消息传递（message delivery）。反映了进程交互的方式。故障模型（failure model） 故障模型试图给出可能由进程和通信通道呈现出来的故障的一个精确的规格说明（specification）。它定义可靠的通信和正确的进程。安全模型（security model） 安全模型讨论对于进程和通信通道可能存在的威胁，它引入

3、了安全通道的概念，以抵御这些威胁。,结构模型,系统的结构是关于其各个独立指定的组件的结构。 建筑物的结构设计有类似的方面：不仅要确定它的外观，而且要确定它的总体结构和结构风格（哥特式，新古典主义，现代的）。 我们围绕着进程和对象的概念构建我们的结构模型。分布式系统的结构模型首先简化和抽象分布式系统各个组件的功能，然后它考虑： 放置组件在一个计算机网络上，寻找定义数据和工作负载分布的有用的模式。 组件之间的相互关系，即它们的功能角色以及它们之间的通信模式。,进程分类,服务器进程 提供服务客户进程 请求服务对等进程 指这样的一类进程，它们以一种对称的方式协作和通信，以执行一个任务。,客户/服务器模

4、型的变种,某些更动态的系统可以构造为客户/服务器模型的变种： * 从一个进程到另一个进程移动代码的可能性允许一个进程委托任务到另一个进程。例如，客户可以从服务器下载代码在本地运行它。对象和存取它们的代码能够被移动以减少访问延迟和最小化通信量。 * 某些分布式系统被设计以使计算机和其它移动设备能无缝地添加或删除，允许它们发现可用的服务并向其它设备提供它们的服务。 在一个计算机网络中实际的放置（布局、分布）组成分布式系统的进程可能受到性能、可靠性、安全性和费用的影响。,软件层(软件结构),原来在单一计算机中，软件结构是指把软件结构化为层或模块;而近来则是用位于相同或不同的计算机里的进程之间提供和请

5、求的服务来定义。分布式系统中软件硬件服务层：,Middleware-based Systems,General structure of a distributed system as middleware. Middleware提供部分Distributed Operating System服务。,1-22,中间件（Middleware）,从中间件提出的初始动因来看，是指网络环境下处于操作系统等系统软件和应用软件之间的一种起连接作用的分布式软件，主要解决异构网络环境下分布式应用软件的互连与互操作问题，它可屏蔽实现细节，提高应用系统的易移植性从广义的角度看，中间件代表了处于系统软件和应用软件之

6、间的中间层次的软件，其主要目的是对应用软件的开发和运行提供更为直接和高效的支撑,中间件(续),中间件是一个软件层，它的目的是屏蔽异构性并向应用程序员提供一个方便的编程模型。中间件通过在一组计算机里的进程或对象来表达，它们相互交互以为分布式应用实现通信和资源共享支持。 中间件技术已成为软件技术的研究热点主要中间件包括：数据访问中间件、远程过程调用中间件、事务中间件、消息中间件和面向对象中间件等；远程过程调用包（例如Sun RPC）和组通信系统（例如Isis）是最早、当前最广泛使用的中间件的实例。The BEA Tuxedo system is a middleware product that

7、distributes applications across multiple platforms, databases, and operating systems using message-based communications and, if desired, distributed transaction processing.,面向对象中间件,面向对象中间件是对象技术和分布式汁算发展的产物，它提供种通讯机制，透明地在异构的分布计算环境中传递对象请求目前主要的面向对象中间件产品和标准有OMG的CORBA、微软的DCOM和Sun公司的Java RMI/EJB。它们的异构性和开放性各

8、有不同，适用于异构环境、开放的CORBA是Internet与企业应用事实上的工业标准，而特定于Windows平台、专有的COM则是桌面系统的首选EJB则兼具二者之优势 中间件也提供了供应用程序使用的服务，它们被紧密地绑定到由中间件提供的分布式编程模型。例如，CORBA提供了naming, security, transactions, persistent storage和event notification等服务。,Web Services,随着软件产业模式从以产品为中心的制造业转变为以客户为中心的服务业，WWW从两层体系转变为三层体系，分布计算中间件从Intranet扩展到Internet

9、，上述中间件技术已不能适应这些发展需求，因而导致新型中间件技术Web Services的产生。 Web Services以XML、SOAP、WSDL和UDDl为核心，致力于软件在应用层的互操作问题Web Services不仅屏蔽了异构的操作系统、网络和编程语言，还屏蔽了传统中间件之间的异构性，并支持开放、动态的互操作模式，增强了服务动态发布，查找和使用的能力因此，Web Services获得了产业界广泛的支持和学术界的重视。,(发布服务的wsdl信息),(根据wsdl,生成访问服务的SOAP消息),系统结构,Client-server模型 这是分布式系统最经常被引用的体系结构，下图阐述了这种简

10、单的结构：客户进程与各服务器进程（在分离的主计算机上）交互以访问它们所管理的共享资源。,由多个服务器提供的服务, 服务可以被实现为在分离的主计算机上的多个服务器进程，它们按需要交互来向客户进程提供一个服务。这些服务器可以划分（partition）该服务所基于的对象集合，并在它们之间分布它们，或者在若干个主机上维护这些对象的复制副本。,代理服务器和缓存（Proxy servers and caches）,Cache是近期使用了的数据对象的存储，它比对象本身更近。当一个新的对象被接收到，它被添加到cache存储中，如果需要的话，替换某个现有对象。当客户进程需要一个一个对象的时候，caching服务

11、首先检查cache，如果最新的拷贝是可用的，则从那里提供该对象。否则，去获取一个最新的拷贝。Cache可以布置在每一个客户端，或位于代理服务器上，以便能够被多个客户共享。,对等进程（peer processes）,在这种结构中，所有进程扮演类似的角色，作为对等者协同交互，在没有任何客户与服务器差别的情况下执行一个分布式活动或计算。在这种模型中，对等进程中的代码维护应用级（层）资源的一致性并按需要同步应用级的行为（actions）。 通常，n个对等进程可以相互交互，其通信模式取决于应用需求。,协调代码,应用由大量的运行在不同的计算机上的对等进程组成,对等计算技术,P2P系统去掉了客户/服务器的不

12、对称性, 客户机也可以充当服务器。,P2P网络的分类,P2P网络根据节点信息存储和资源查找的方式主要可以分为3种类型: (1)集中式P2P网络,利用中心索引服务器存储数据的元数据信息,例如Napster1。 (2)非结构化P2P网络,借助泛洪广播查询请求,例如Gnutella2。 这两种方案由于设计之初并没有考虑运行在大规模网络环境下,因此扩展能力有限。 (3)结构化P2P网络,利用分布式哈希表(distributed hash table,DHT)技术来进行资源定位,例如Chord3,CAN4, Pastry5和Tapestry6。 结构化P2P网络因其高效快速的资源定位方式成为P2P网络发

13、展的方向。,Napster文件共享系统允许用户在其他Napster用户的硬盘上搜索、下载音乐文件。,（Index）,File location request,6. Index update,peers,File request,File delivered,peers,洪泛：搜索请求被广播到所有的邻居及邻居的邻居上,网格计算技术,网格俗称下一代因特网、国际互联网2、下一代万维网。网格计算系统具有高度的异构性：其硬件、操作系统、网络、管理域和安全策略等都不尽相同。网格是把地理位置上分散的资源集成起来的一种基础设施，它是构筑在互联网上的的一组新兴技术。通过这种基础设施，用户不需要了解这个基础设施

14、上资源的具体细节就可以使用自己需要的资源。网格上的资源包括计算机、集群、计算机池、仪器、设备、传感器、存储设施、数据、软件等。,网格计算技术,网格把用通信手段连接起来的资源无缝集成为一个有机的整体。他给用户提供一种基于国际互联网的新型计算平台，在这个平台上对来自客户的请求和提供资源的能力之间进行合理的匹配，为用户的请求选择合适的资源服务，可实现广域范围的资源共享。网格把分布的资源集成为一台能力巨大的超级计算机，提供计算资源、存储资源、数据资源、信息资源、知识资源、专家资源、设备资源的全面共享。资源共享是网格的根本特征，消除资源孤岛是网格的奋斗目标。,网格分层体系结构,应用层,汇聚层,构造层,资

15、源层,连接层,网格分层体系结构,构造层：面对具体的物理资源，其基本功能是控制局部的资源，并向上提供访问这些资源的接口。连接层：其基本功能是实现资源的相互通信，为下层的物理资源提供安全的数据通信能力。该层定义了核心的通信和认证协议，用于网格中的事务处理。,网格分层体系结构,资源层：负责管理单个资源，实现对单个资源的共享。它使用由连接层提供的功能，直接调用对构造层可用的接口。汇聚层：该层负责处理对多个资源的访问，通常由资源分派、把任务分配和调度到多个资源以及数据复制等服务组成。应用层：由应用程序组成，这些应用程序在虚拟组织中运行，它们可以充分利用网格计算环境。,开放网格服务体系结构OGSA,OGS

16、A是新一代的网格体系结构以服务为中心如果说分层体系结构是以协议为中心的“协议结构”，则OGSA就是以服务为中心的“服务结构”。在OGSA中，服务的概念更广，包括各种计算资源、存储资源、网络、程序、数据库等，一切都是服务。分层体系结构强调资源共享，而OGSA强调服务共享。OGSA定义了“网格服务”（Grid Service）的概念，网格服务是一种Web Service，该服务提供了一组定义明确的接口，且遵守特定的惯例，解决服务发现，动态服务创建，生命周期管理和通知等问题。由于在OGSA中，一切都是网格服务，因此网格就是可扩展的网格服务的集合。,开放网格服务体系结构OGSA,采用统一的Web Se

17、rvice框架一个Web Service就是一个可以被URL识别的软件应用，它的接口和绑定可以被XML（eXtensible Markup Language）描述与发现，并且可以通过基于Internet的协议支持直接与其他的基于XML消息的软件应用进行交互。Web Services定义了一种用来描述所访问的软件组件、访问方法以及识别相关服务提供者的发现方法。OGSA完全符合标准的Web Services框架，后者解决了发现和启动永久服务的问题。由于在网格中大量存在的是临时服务，因此OGSA对Web Services进行了扩展，提出网格服务的概念。该技术支持临时服务，并能实现其动态创建和删除。网

18、格服务包含许多接口，其中Grid Service接口是不可少的，而其他的接口可根据需要进行增减。,Globus Toolkit,Globus Toolkit是一种基于社团的、开放结构、开放源代码的服务的集合，也是支持网格及其应用的软件库，他解决了安全、信息发现、资源管理、数据管理、通信、故障检测和可移植性等问题。该软件包被世界上的的许多网格项目，包括几百个地点所采用。GT3是OGSA的第一个实现。GT3工具集建立在SOAP、WSDL和WS-Inspection等万维网服务技术的基础上。SOAP是基于XML的RPC协议；WSDL用于描述服务，是Web Service的接口定义语言；WS-Insp

19、ection用于定位服务提供者发布的服务；UDDI定义了Web Service的目录结构。GT3是采用Java语言开发的，因此可以在不同环境下运行。GT3软件分为浏览器和服务器两个部分。用户通过浏览器和具体的服务器相连，可以查询有关的信息，也可以访问该服务器上的服务和服务实例。,普适计算技术,普适计算（Pervasive Computing）是指无处不在的，渗透到各个方面的计算。主要针对移动设备，如汽车、手机、BP机、笔记本电脑、手表、智能卡和销售机等新一代智能设备与国际互联网连接，使用户能够随时随地获取相关的信息。普适计算是一种新型的计算模式，在该模式下，计算以人为中心，人机交互类似于人与人

20、之间的自然交流方式（如语言、姿势、书写等），用于计算的设备无处不在，弥漫在人们生活的环境中，并能够随时随地为人们提供所需要的服务，而使用计算设备的人则感知不到计算机的存在。分布式普适系统中的设备，往往具有体积小、由电池供电、可移动以及只有一个无线连接等特征。,客户/服务器模型的变种,通过考虑下面的一些因素我们可以导出客户/服务器模型的几个变种： 使用移动代码和移动代理； 用户对于低价格（low-cost）计算机 的需要；(有限的硬件资源, 管理简单) 以方便的方式添加和删除移动设备的需 求。,移动代码（Mobile code）,Applets是一种众所周知和广泛使用移动代码：用户运行浏览器选择

21、一个到Applet的链接（link），Applet的代码存储在Web服务器上，代码被下载到浏览器并在那儿运行。下图是其示例：,移动代码 (续),局部（本地）运行下载的代码的好处是，由于不会遭遇跟网络通信相关的延迟或带宽的变化（可变性），因此会得到好的交互式响应。 例子：一个股票代理（stockbroker）可以提供一个定制服务来通知客户股票价格的变化。为了使用这个服务，每个客户必须下载一个特别的Applet，它从代理服务器那里接收更新，显示给用户，也许还要执行自动的买和卖操作（根据客户设置的条件）。 移动代码对于目的计算机里的本地资源有潜在的安全威胁，因此浏览器会限制Applet对本地资源的访

22、问。,移动代理（Mobile agents）,移动代理是一个包含代码和数据的运行程序（自治的软件组件，能与其他代理通信），它在网络中从一台计算机移动（travels）到另一台计算机，代表某人（someone）完成（执行）一个任务，例如收集信息，最终返回结果。移动代码在它访问的每一个场点可能作许多对本地资源（local resources）的调用请求，例如访问各个数据库项。我们将这种结构与静态客户(static client)做一个比较：静态客户要作对某些资源的远程调用，这样可能会传送大量的数据，移动代理结构通过用本地调用代替远程调用减少（降低）了通信的费用和时间。,移动代理（续）,与移动代码一

23、样，移动代理对它们所访问到计算机上的资源也有潜在的安全威胁。接收移动代理的环境基于用户的身份（移动代理代表谁）应该决定允许它使用哪些局部资源，其身份（identity）必须以一种安全的方式与移动代理的代码和数据包含在一起。此外，移动代理本身可能是脆弱的，即如果它们被拒绝访问它们需要的信息，它们可能不能完成它们的任务。由移动代理执行的任务可以通过其它方式执行。例如，需要访问Internet上Web服务器上资源的Web爬行者（crawlers）通过做对服务器进程的远程调用（remote invocations），能够相当成功地工作。由于这些原因，移动代理的应用（适用性）可能是有限的。,移动代理（续

24、）,一个移动代理系统应该向代理程序员（the agent programmer）提供尽可能多的灵活性，来尽可能多地隐藏下面的网络体系结构。移动代理系统的例子有：IBM 的Aglet以及Voyager，AgentTCL等。 移动代理与移动代码的区别?,移动代理与移动代码的区别,代理通常是“multi-hop”可移动的，而Java applets是“single-hop”。即代理通常是要从网络上的一个主机漫游到另一个主机，在每一个访问点积聚状态，然后主动地决定什么时候移动，以及应该移动到哪里。代理主动地控制他们的移动，而Java applets则是被动的。代理典型的应用包括网络管理，compara

25、tive service shopping等。代理在它们的旅行中是有状态的，而Java applets通常是无状态的。随着代理访问经过各个结点，典型地它在每个结点上都要执行一些工作，这会引起其内部的状态变换，并在其移动过程中携带它们。,网络计算机（Network computers）, 在桌面计算机环境中，操作系统和应用软件典型地需要大量的活动代码和数据，它们位于在本地磁盘上。但是应用文件的管理和本地软件库的维护都需要相当的技术工作，这对于大多数的用户是不能胜任的。 网络计算机是对这个问题的一个反应。它按用户的需要从远程文件服务器下载操作系统和任何应用软件。应用在本地运行，但文件由远程文件服务

26、器管理。像Web browser这样的网络应用也能够运行。由于所有的应用数据和代码都由文件服务器存储，用户可以从一台网络计算机迁移到另一台。网络计算机的处理器和存储器能力可以被限制以降低它的成本（cost）。 如果包含一个磁盘，它仅仅保持最少的软件，磁盘的其余部分被用做cache存储，以保持近期从服务器载入的软件和数据文件的copies。,瘦客户（Thin clients）, 瘦客户是指一个软件层，它支持用户端的计算机上基于窗口的用户界面，而在远程的计算机上执行应用程序。 这种结构与网络计算机模式有同样低的管理和硬件费用。但它不是下载应用代码到用户的计算机，而是在计算服务器上运行它们。,移动设

27、备和自组网络（Mobile devices and spontaneous networking）,现在各种小的、便携的计算设备越来越多，包括笔记本电脑、个人数字助理（PDAs）类的手持设备，移动电话和数字照相机、可穿戴的计算机（如smart watch）、以及嵌入在日常装置（如洗衣机）里的设备。许多的这些设备能够无线联网，范围从大城市或更大的范围（GSM, CDPD），到数百米（WaveLAN），或几米（BlueTooth, infra-red and HomeRF）。更短范围的网络有直到10Mbps级的带宽，GSM有望达到数百Kbps级。,移动设备和自组网络（续）,适当地集成到我们的分布式

28、系统，这些设备提供了对移动计算（mobile computing）的支持，从而用户能够在网络环境之间携带它们的移动设备，并利用本地和远程的服务。集成移动设备和其它设备到一个给定的网络的分布形式也许可以最好地用自组网络（spontaneous networking）来描述。这个术语用于指这样的应用：它涉及到以一种比现在可能的更加不正式的方式把移动和非移动设备连接成网络。那些嵌入式设备向用户和其它的相邻设备提供服务。像PDAs这样的便携式设备让用户可以访问在他们当前位置的服务，也可以访问像Web这样的全球服务。,上图给出了自组网络的一个图示，覆盖一个酒店套房的无线网络。套房的高保真系统提供音乐服务

29、，闹钟系统通过音乐服务提供叫醒服务。TV/PC（带机顶盒的电视）既可用作电视也可用作计算机，它（通过酒店的因特网网关）提供对Web的访问。它还可以为用户提供查看服务，使用户可以浏览存储在相机或便携式摄像机中的图像。,自组网络的关键特征是： 易于连接到本地网络（local network） 无线连接避免了预安装电缆的需要 易于跟本地服务（local services）集成 设备插入到（和移动到）已有的设备网络，将自 动发现那里提供什么服务 当它们旅行（travel）的时候，移动用户可能 遭遇受限的连接（limited connectivity）， 其连接的自主特性又引起了安全问题： 有限的连接

30、用户在移动时并不总是保持连接 安全和私秘（Security and privacy） 如果酒店 客人或雇员以不受监管的方式进行无线连接, 酒 店及其客人应对安全攻击的能力是脆弱的。,发现服务（Discovery services） 我们需要的是客户发现所连接的网络上有什么服务可用以及查明它们属性的方法。发现服务的目的是接受并存储网上可用的服务细节，对客户关于这些的查询给出回应。 注册服务（registration service） 接受服务器注册请求，记录到发现服务的数据库中 查找服务（lookup service） 查找数据库中注册的可用服务,接口和对象（Interfaces and obj

31、ects）,进程中（无论是服务器或是对等进程）可用于调用的功能函数的集合通过一个或多个接口定义来说明。在基本的客户/服务器结构中，每一个服务器进程被看作一个具有固定接口（定义了它里面能够被调用的函数）的单一的实体（entity）。 在面向对象语言（例如C+和Java）中，通过适当的附加支持，分布式进程能够以更加面向对象的方式进行构造。许多对象能够被封装在服务器或对等进程中，对它们的引用（references）被传递到其它进程以便它们的方法能够通过远程调用（remote invocation）进行（被）访问。这是CORBA和Java所采用的方法（采用远程方法调用RMI机制）。,分布式结构的设计需

32、求（所有模型共享design requirements）, 性能问题（Performance issues） 服务质量（Quality of Service） 使用caching和复制（Use of caching and replication） 可靠性问题（dependability issues）,基础模型,所有前面介绍的不同的系统模型共享某些基 础特性。通常，一个模型仅仅包含我们需要考虑的基本要素，以便理解和推理关于系统行为的某些方面。一个系统模型必须表述这些问题： 系统中主要的实体是什么？ 它们怎样交互？ 影响其个体和集体行为的特征是什么？,基础模型 (续), 在基础模型中我们希望捕

33、捉的分布式系统的特性是想要帮助我们讨论和理解： 交互（Interaction） 计算发生在进程中。进程通过传递信件（pass messages）交互，导致进程之间的通信（即信息流）和协调（coordination，即同步和活动定序ordering）。交互模型必须反映这样的事实：通信的发生是有延迟的（这经常具有相当的持续时间），并且协调独立的进程的准确性（正确度）受限于这些延迟以及在分布式系统的所有计算机上维护相同的时间概念（notion）的困难性。, 故障（Failure） 无论什么时候当任何的计算机里面或连接它们的网络发生故障(包括软件故障) 时，分布式系统的正确操作都会受到威胁。故障模型定

34、义和分类了故障，这提供了一个基础，使我们能够分析其潜在的影响，并使得系统的设计能够容忍每一种类型的故障，以继续正确地运行。, 安全性（security） 分布式系统模块化的特性及其开放性暴露出它们容易遭到外部和内部代理的攻击。安全模型定义和分类了那样的攻击可能采取的形式，这提供了一个基础，使得我们能够分析对系统的威胁，以及设计出能够抵御它们的系统。,交互模型,分布式系统由许多进程组成，他们以复杂的方式交互。例如 ：多个服务器进程相互协作以提供一个服务；前面提到的一个例子是Domain Name Service系统, 他划分和复制他的数据在整个Internet的服务器(servers)上。一组对

35、等进程可以相互协作以获得一个共同的目标：例如，一个以类似的方式（但是具有严格的实时限制）分发音频数据流的音频会议系统。,交互模型（续）,每一个进程进行的速度以及他们之间消息传送的定时同步（timing）通常不能预知。由于必须处理涉及到的一个或多个进程的故障或消息传送的故障，要描述分布式算法所有的状态也是困难的。在分布式系统中，每个进程有他自己的状态（由他可以访问和更新的数据集组成），属于每个进程的状态是完全私有的。在这一节，我们讨论影响分布式系统中交互进程的两个重要因素： 通信性能通常是一个限制特性（limiting characteristic） 不可能维护一个单一的全局时间概念,计算机时钟

36、和定时事件（timing events）,分布式系统中每一台计算机有其自己的内部时钟，可以被本地进程用于获得当前时间的值，因此运行在不同计算机上的两个进程能够给他们的事件关联一个时间戳（timestamps）。然而，即使两个进程在同一个时间读取他们的时钟，其局部时钟也可能提供不同的时间值，这是因为计算机时钟与标准时间的偏移，更重要的是，不同计算机相互间的偏移率是不一样的。即使分布式系统中所有计算机的时钟在初始化的时候被设置成相同的时间，其时钟最终也会变化得很大（除非采用校正措施）。,计算机时钟和定时事件（续）,有几种方法来校正计算机时钟的时间。例如，计算机可以使用无线电接收器来从GPS那里得到

37、时间（具有大约一微秒的精度）。但是GPS接收器不能在建筑物内操作，每台计算机都配备在费用上也是不合理的。一种替代的方法是，一台具有精确时间源（例如GPS）的计算机向网络中其他计算机发送定时消息，结果各局部时钟时间之间的一致性当然受变化的消息延迟的影响。,交互模型的两个变种,在分布式系统中很难对进程执行、消息传递或时钟偏移的时间设置时间限制。有两种简单的、相反的、极端的模型：第一种有非常强的时间假定，另一种没有作任何关于时间的假定。,同步分布式系统,在Hadzilacos和Toueg的定义中，同步分布式系统具有下面的限制：进程每一步执行的时间有已知的下和上界；通道上传送的每一封信在一个已知的有限

38、的时间内被接收到；每一个进程有一个局部时钟，其相对于标准时间的偏移率有一个已知的界限。,同步分布式系统（续）,能够建议分布式系统中进程执行时间、消息延迟和时钟偏移率很可能的上和下界，但难于达到现实可行的值并提供这些选择值的保证。除非这些界限值能够被保证，否则任何基于这些选择值的设计都不会是可靠的。然而，把一个算法建模为一个同步系统对于弄清楚它在真实的分布式系统中是如何工作的可能是有用的。在同步系统中，可以使用超时（timeouts），例如检测进程的故障。 同步分布式系统可以构建。所需要的是进程在已知的资源需求下执行任务，以便他们能够保证（有）足够的处理器周期和网络容量，同时提供给进程具有有限偏

39、移率的时钟。,异步分布式系统,许多分布式系统（例如Internet），是非常有用的，不能算是合格的同步系统，因此我们需要另一个模型。异步分布式系统没有任何下面的限制：进程执行速度例如，一个进程步(step)可能只花1 微微秒（picosecond），而另一个则要花一个世纪；总之，每一步可能花任意长的时间；消息传送延迟例如，一封从进程A到进程B的信可能在零时间里被传递，而另一封信可能要花几年。换句话说，一封信可以在任意长的时间后被接受到；时钟偏移率时钟的偏移率是任意的。,异步分布式系统（续）,异步模型对在任意执行中涉及到的时间间隔不允许有任何假设，这准确地建模了Internet，在那里对服务器或

40、网络的负载没有任何固有的限制，因此对于（例如，使用ftp传送一个文件）要花多长的时间也就没有限制。有时一封Email信可能要花数天的时间才能到达。Web不能总是在一个合理的时间限制之内提供一个特定的响应。,异步分布式系统（续）,任何对于异步分布式系统有效的解决方案对于同步分布式系统来说也是有效的。实际的分布式系统常常是异步的，因为需要进程共享处理器以及通信通道共享网络。例如，如果太多具有未知特性的进程在共享一台处理器，那么它们任何一个结果的性能都不能得到保证。但是，有许多对于一个异步系统不能解决的设计问题，当使用某些方面的时间时就能够被解决。对于要在一个最终期限前传递的多媒体数据流的每一个元素

41、就是那样的一个问题。,事件定序,在许多情况下，我们想知道一个进程中的一个事件（发送或接收一个消息）是发生在另一个进程中的另一个事件之前、之后或是并发地发生。一个系统的执行可以用事件及其顺序（ordering）来描述，尽管缺乏精确的时钟。,Example,我们考虑在一组email用户X、Y、Z和A之间的一组如下的交换：用户X发送一封具有主题Meeting的信；用户Y和Z通过发送一封具有主题Re:Meeting的信进行回答； 首先X的信被发送，Y读取它并回答；Z读取X的信和Y的回答，然后 发送另一封回答信（它引用了X和Y的信）。但是由于消息传递独 立的延迟，这些信可能按下图的方式被传递：,Exam

42、ple (cont.),这样某些用户可能以错误的顺序看到这些信，例如用户A可能看见：,如果X、Y、Z的计算机的时钟能够同步，那么每一封信在它被发送的时候，就能够携带其局部计算机时钟的时间。例如，信件m1,m2和m3将携带时间t1,t2和t3（t1t2t3）。接收到的信件将按照其时间顺序显示给用户。如果这些时钟是大致同步的，那么这些时间戳（timestamps）经常具有正确的顺序。,逻辑时钟,因为在分布式系统中这些时钟不能完全地被同步，Lamport提出了一种逻辑时间模型，可以用来对运行在分布式系统不同的计算机上的进程中的事件提供一种定序（ordering）。逻辑时间不需要求助于时钟而推断出消息

43、（信件）出现的次序。,逻辑时钟（续）,逻辑上，我们知道一封信在其被发送之后才被接收，因此我们可以声明一些事件对的逻辑顺序，例如我们仅仅考虑跟X、Y相关的事件： X sends m1 before Y receives m1; Y sends m2 before X receives m2.我们也知道在接受信件之后才发送回答，因此我们有下面的逻辑顺序（对于Y）： Y receives m1 before sending m2.逻辑时间进一步采用这个思想，给每一个事件分配一个数值（相应于其逻辑顺序），以便后面的事件比早先的事件有更高的数值。例如，前面的图中在X和Y的事件上显示数值14。,故障模型,

44、分布式系统中，进程和通信通道都可能失效，故障模型定义了故障可能发生的方式，以便理解故障的影响。遗漏故障（Omission failures） 指一个进程或通信通道不能执行它被假定要做的活动。,遗漏故障进程遗漏故障,主要的进程遗漏故障是崩溃（crash）。指进程它停止了，并且不会再执行其程序步骤。其他进程当发现这个进程反复的不能响应调用消息的时候，可以检测到那样的崩溃。然而，这种崩溃检测方法依赖于timeouts的使用，在异步系统中，一个timeout仅能指示出进程不响应他可能崩溃了也可能是很慢，或者消息可能还没有到达。如果其他进程能确切地检测到进程已经崩溃，这样的进程崩溃称为“fail-sto

45、p”。如果进程使用timeouts来检测什么时候其他进程不能响应并且保证信件被传递，那么在同步系统中可以产生Fail-stop行为。,遗漏故障通信遗漏故障,考虑通信原语send和receive。进程p通过在其outgoing消息缓冲区中插入消息m执行一个send，通信通道传送m到q的incoming消息缓冲区，进程q通过从其incoming消息缓冲区取m并传递它来执行一个receive。Outgoing和incoming消息缓冲区典型地由操作系统提供。,通信遗漏故障（续）,通信通道如果它不能把信件从p的outgoing 消息缓冲区传送到q的incoming消息缓冲区，则产生了一个遗漏故障。这就

46、是我们所知道的“dropping messages”，并且这通常是由于在接收端或在介入的网关上缺乏缓冲空间，或者是由于网络传送错误（通过信件数据所携带的checksum进行检测）引起的。Hadzilacos和Toueg把发送进程与outgoing消息缓冲区之间的信件丢失称为send-omission failures；把incoming消息缓冲区与接收进程之间的信件丢失称为receive-omission failures；把两者之间的信件丢失称为channel omission failures。,任意故障（Arbitrary failures）,任意故障是用来描述最坏可能的故障语义，这里任

47、何类型的错误都可能发生。例如，一个进程可以对它的数据项设置错误的值，或者它也可以对一个调用返回一个错误的值。进程的任意故障是指，它任意地省略需要的处理步骤或者采取一些不需要的处理步骤。因此，进程中的任意故障不能通过看是否进程响应调用来进行检测，因为它可以任意地省略回答。,任意故障（续）,通信通道可能遭遇任意故障，例如，信件内容可能被破坏了或者不存在的信件可能被传递或者真实的信件被传递多于一次。通信通道的任意故障是稀少的，因为通信软件能够识别它们并拒绝这些错误的信件。例如，检查和被用于检测被破坏了的信件，而信件顺序号（sequence numbers）可以用来检测不存在的和复制的信件。,Omis

48、sion and arbitrary failures,定时故障（Timing failures）,定时故障应用于同步分布式系统，那里时间限制被设置在进程执行时间、信件传递时间和时钟偏移率。,屏蔽故障（Masking failures）,在分布式系统中，每一个组件通常是从其它一组组件进行构造，可以从有故障的组件（components）来构造可靠的服务。例如，保持数据复本的多个服务器在其中一个崩溃时可以继续提供服务。一个service屏蔽一个故障，或者通过隐藏它或者通过把它转换成一个更可接受的故障类型。,端到端通信的可靠性（Reliability of one-to-one communicat

49、ion）,虽然基本的通信通道可能会呈现出上面描述的省略故障，但是可以使用它构建一个屏蔽了某些那些故障的通信服务。可靠的通信按照有效性和完整性定义如下： 有效性：在outgoing消息缓冲区中的任何 信件最终要被传递到incoming消息缓冲区； 完整性：接收到的信件与发送的信件是相 同的，并且没有信件被传递两次。,端到端通信的可靠性（续）,对完整性的威胁来自于两个独立的源：任何重传消息但是不拒绝到达两次的消息的协议，协议可以通过给信件附加顺序号来 检测那些传递了两次的信件。恶意的用户可能插入伪造的（欺骗的）的信件，重放老的信件或篡改信件。在面对那样的攻击时，可以采取安全性措施来维护完整性。,S

50、ecurity model,we described their system architecture in terms of processes encapsulating objects and providing access to them through interactions with other processes. Protection is described in terms of objects, although the concepts apply equally well to resources of all types. The security of a