《分布式系统原理与范型 (第二版)》复习资料.doc

分布式复习资料第1章分布式系统是若干独立计算机的结合，这些计算机对于用户来说就像是单个相关系统。硬件方面：机器本身是独立的。软件方面：对用户来说就像与单个系统打交道。重要特性：1、各种计算机之间的差别以及计算机之间的通信方式的差别对用户是隐藏的。2、用户和应用程序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行交互。中间件：为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个 “软件层”组织起来。该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的低层之间。如图，这样的分布式系统有时又称为中间件。注意层次分布与组件分布式系统的最主要目标是使用户能够方便地访问远程资源，并且以一种受控的方式与其他用户共享这些资源。透明性：如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统，这样的分布式系统就是透明的。透明的类型：1、访问透明性：指对不同数据表示形式以及资源访问方式的隐藏。2、位置透明性：指用户无法判别资源在系统中的物理位置。3、并发透明性：在资源共享时，用户不会感觉到他人也在使用自己正使用的资源。4、故障透明性：用户不会注意到某个资源(也许他从未听说过这个资源)无法正常工作，以及系统随后从故障中恢复的过程。开放性：一个开放式的分布式系统，是根据一系列准则来提供服务，这些准则描述了所提供服务的语法和含义。互操作性：刻画了来自不同厂商的系统或组件的两种实现能够在何种程度上共存并且协同工作，这种共存和协同工作只能依赖于通过双方在公共标准中规定的各自所提供的服务来完成。可移植性：刻画了这样的性能，如果为分布式系统A开发了某个应用程序，并且另一个分布式系统B与A具有相同的接口，该应用程序在不做任何修改的情况下在B上执行的可行程度。可扩展性：当一个系统需要进行扩展时，必须解决多方面的问题。首先考虑规模上的扩展。在需要支持更多的用户或资源时，我们常常收到集中的服务、数据以及算法所造成的限制，如图所示。例如，许多服务是以集中的方式实现的，它们由分布式系统中一台特定的计算机上运行的单个服务来提供。这种方案存在的问题是显而易见的：用户增多时该服务将成为系统的瓶颈。即使它拥有无限的处理能力和存储能力，在系统达到一定规模后与该服务器的通信也将发生困难。从而使得系统规模无法继续增长。扩展技术：1、 隐藏通信等待时间对于地域扩展是比较适用的。基本想法：尽量避免等待远程服务对请求的响应。例如，当对远程计算机的某个服务发出请求时，在发出请求端，除了等待服务器响应之外，还可以利用这段时间做其他工作。本质上，以这种方式构建的 应用程序使用的异步通信。当响应到来时，应用程序产生中断，并且调用专门的处理程序对前面发出的请求进行处理。2、 分布技术分布技术把某个组件分割成多个部分，然后再将它们分散到系统中区。3、 缓存缓存是复制的一种特殊形式。与复制相同，缓存一般是在访问资源的客户附近制作该资源的副本。然而，与复制不同的是，是否进行缓存是由要访问资源的客户决定的，而不是由资源拥有者决定的。缓存和复制都存在严重的缺点，这些缺点可能会对可扩展性造成不良影响。进行缓存或者复制以后，由于资源存在多个副本，修改其中的一个会导致它与其他副本不相同，从而导致一致性方面的问题。集群计算：底层硬件是由类似的工作站或PC集组成，通过高速的局域网紧密连接起来。而且，每个节点运行的都是相同的操作系统。网格计算：组成分布式系统的这种子分组通常构建成一个计算机系统联盟，其中的每个系统归属于不同的管理域，而且在硬件、软件和部署网格技术上也差别很大。光纤层：在特定站点提供对局部资源的接口。这些接口都进行了定制，以允许在某个虚拟组织中实现资源共享。连接层：由通信协议组成，用于支持网格事务处理，延伸多个资源的使用。例如，用于在资源之间传输数据或从远程地点访问资源的协议。另外，连接层还有安全协议，用于进行用户和资源的认证。资源层：负责管理单个资源。它使用由连接层提供的功能，直接调用对光线层可用的接口。汇集层：负责处理对多个资源的访问，通常由资源分派、把任务分配和调度到多资源以及数据复制等服务组成。连接层和资源层由相对较小、较标准的协议集组成，而汇集层由很多用于不同目的的不同协议组成。应用层：由应用程序组成。第2章体系结构样式：1、分层体系结构 2、基于对象的体系结构 3、以数据为中心的体系机构 4、基于事件的体系结构客户服务器模型分为三层：1)用户接口层 2)处理层 3)数据层多层体系结构点对点体系结构：在结构化的点对点体系机构中，覆盖网络是一个确定性的过程来构成的。这个使用最多的进程是通过一个分布式哈希表来组织继承的。超级对等体：能维护一个索引或者充当一个代理程序的结点。控制管理多个常规对等体。边界服务器系统这种系统部署在因特网中，服务器放置在网络的“边界”。这种边界是由企业网络和实际的因特网之间的分界线形成的。协作分布式系统混合结构主要部署在协作式分布式系统中。在很多重要的系统中，主要问题是先启动起来，因为经常会部署一个传递的客户-服务器结构。一旦某个结点要加入系统，就可以使用完全非集中式的组织结构，用于协作。自治计算：以高级反馈控制系统的形式来组织分布式系统，允许自动自适应变换。也叫做自主系统。自适应的多样性：自我管理、自我恢复、自我配置、自我优化等。反馈控制模型反馈控制系统的核心由需要管理的组件形成。这些组件能通过可控输入参数驱动，受干扰或噪声输入的影响。系统本身需要被监视，因此需要对系统各个方面进行测量。但是实际测量很难做到，就需要一个逻辑尺度预测组件。控制循环的核心部分是反馈分析组件，分析上述测量值，并把它们与参考值进行比较。包含了决定自适应的各种算法。第三章 线程为什么要使用线程？虽然进程构成了分布式系统中的基本组成单元，但是实践表明，操作系统提供的用于构建分布式系统的进程在粒度上还是太大了。而就粒度而言，将每个进程细分为若干控制线程的形式则更加合适，可以使构建分布式应用程序变得更加方便，获得更好的性能。进程间通信机制IPC IPC需要内核干预。从用户模式切换到内核模式S1，在内核中进行上下文切换S2，再从内核模式切换到用户模式S3。完成进程之间的切换。多线程客户隐藏通信时间延迟的常规方法是启动通信后立即进行其他工作。例子：Web浏览器。Web浏览器一般在开始获取HTML页面后随即就显示它。为了尽量隐藏通信时间延迟，某些浏览器在接收数据的过程中就开始显示这些数据。首先将文本显示出来，并提供页面滚动之类的功能，同时获取组成页面的其他文件，比如图像等。用户不必等待浏览器取得整个页面的所有组件就能够查看页面。从效果来看，web浏览器好像在同时进行多任务一样。只要取得了主HTML文件，就可以激活多个独立的线程，它们分别负责取得页面的各个部分。每个线程都与服务器建立一个独立连接以获取数据。多线程服务器虚拟化计算机界面1) 由机器指令组成，可由任何程序激起的硬件软件界面。2) 由机器指令组成，只有特权程序(如OS)才可激活的。3) 由操作系统提供的系统调用组成的界面。4) 由库调用组成的界面，通常形成了所谓的应用程序编程结构(API)。很多情况下前述的系统调用由API隐藏。虚拟化的实质是模仿这些界面的行为。虚拟化可采用两种方式。第一种：可以构建一个运行时系统，实质上提供一套抽象指令集来执行程序。指令可以被翻译执行，也可以仿真执行，就像在Unix平台上运行Windows应用程序。第二种：提供一种系统。把它做成一层完全屏蔽硬件但是提供一个同样指令集(或其他硬件)的界面。这个界面可以同时提供给不同的程序。可以有多个不同的操作系统独立并发地运行在同一平台。客户端软件与分布透明性客户端通过将调用请求转发给每一个服务器的副本来达到复制透明性。服务器组织结构：1) 迭代服务器：自己处理请求，并且在必要的情况下将响应返回给发出请求的客户。2) 并发服务器：并不自己处理请求，而是将请求传递给某个独立线程或者其他进程来处理，自身立即返回并等待下一个请求。或者每收到一个输入请求都派生出一个新进程来对其进行处理。多线程服务器就是个特例。3) 状态无关服务器：不保存其客户的状态信息，而且也不将自身的状态变化告知任何客户。如Web服务器，仅仅对输入的HTTP请求做出响应，在处理请求的时候，彻底忽略用户的存在。软状态：有一种特别的状态无关设计是服务器维护软状态的信息。服务器仅维护一小段时间的客户状态。时间到期后就删除相关客户信息，到无状态行为。4) 状态相关服务器：一直保存客户端的信息直到显式地删除。如文件服务器，它让客户保留文本的本地副本，甚至进行更新操作。端口：客户总是向服务器所在机器上的端点发送请求，这种端点就是端口。a) 有许多服务不需要预先分配好端点。比如，一个时间服务器可能会使用由本地操作系统动态分配给它的端点。在这种情况下，客户首先必须查询到该端点号。一种解办法在运行服务器的每一台机器上都运行一个特殊的守护程序，该守护程序负责跟踪位于同一台机器上的服务器实现的每一项服务所使用的当前端点。守护程序还监听一个已知的端口。客户通过这个端口与该守护程序进行联系，请求得到指定服务器的端点号，随后再与该服务器进行联系。b) 与其对这么多被动进程进行跟踪，不如由一个超级服务器来负责监听所有与这些服务关联的端点。当收到请求 时候，派生出一个进程以对该请求进行进一步处理，这个派生出的进程在处理完毕后自动退出运行。中断服务器工作：处理通信中断的更好方法是在开发客户程序和服务器程序的时候考虑到对带外数据发送的支持。带外数据是服务器在处理客户发送的其他所有数据之前必须处理的数据。一种办法是让客户将带外数据发送到一个另外的控制端点，服务器则监听该端点，同时也监听常规数据传输的端点。另一种方法是通过发送原始请求所使用的连接来发送带外数据。TCP转发原理：当交换机接收到一个TCP连接请求时，找到处理这个请求的最佳服务器，把请求包转发给这个服务器。服务器反过来发送一个响应给客户，同时把交换机的IP地址也放入数据段。第四章 通信OSI模型是用来支持开放式系统间通信的。开放式系统通过一系列标准规则来与其他开放式系统通信的系统。每一层都规定了与上一层的接口。接口中包括一组操作，定义向用户提供的服务。面向连接的协议：消息发送方和接收方必须首先显式地确立连接，可能还需要就采用的协议进行协商，然后才能进行数据交换。在通信完毕后，必须终止连接。如电话系统。无连接的协议：交换数据之前不需要有建立连接的过程，消息发送方只需要在准备好的时候传送第一个消息即可。如将信件投入邮箱。如果机器1上的进程A想传消息给机器2上的进程B。那么消息先到机器1上的应用层，依次向下传递，每传递一层，就在消息前增加一个报头。第n层添加的报头中的信息是供第n层协议使用的。某些层还要增加报尾。物理层只负责传输位，而数据链路层是负责检查传输是否出错。数据链路层在每一帧的开头和结尾分别放置特殊的位来对头尾进行标记，并用某种方法将帧中的所有字节相加，计算出校验和。再将校验和放入帧中。当接收到消息后，接收方重新计算校验和，跟原有进行比较。目前应用最广泛的网络协议就是无连接的网际协议(IP)。远程过程调用包括以下步骤：1) 客户过程以正常的方式调用客户存根2) 客户存根生成一个消息，然后调用本地操作系统3) 客户端操作系统将消息发送给远程操作系统4) 远程操作系统将消息交给服务器存根5) 服务器存根提取参数，然后调用服务器6) 服务器执行要求的操作，操作完成后将结果返回给服务器存根7) 服务器存根将结果打包成一个消息，然后调用本地操作系统8) 服务器操作系统将含有结果的消息发送给客户端操作系统9) 客户端操作系统将消息交给客户存根10) 客户存根将结果从消息中提取出来，返回给调用它的客户过程。传递引用参数？异步RPC在异步RPC中，服务器接收到RPC请求后立即向客户端发送应答，再调用客户端请求。应答的作用是向客户确认服务器已准备开始处理该RPC请求。客户收到服务器的确认消息后，将不再阻塞，而是继续向下执行。延迟的同步RPC远程服务器在处理请求时，客户同时做一些其他的事情。当服务器处理好请求时，返回结果去中断客户，服务器一端变成发送端，实现第二个异步RPC。套接字：一种通信端点。如果应用程序要通过底层网络发送某些数据，可以把这些数据写入套接字，然后从套接字读出数据。服务器一般执行前4个原语，一般按照图中顺序执行。调用套接字原语的时候，调用者创建一个新的通信端点，用于某种特定的传输协议的。MPI的先进之处：程序的硬件独立性需要导致MPI的出台。MPI是为并行应用程序设计的，是为瞬时通信量身定做的。它直接使用的是底层网络。消息队列系统：面向消息的中间件服务。为持久异步通信提供多种支持。本质是，提供消息的中介存储能力，这样就不需要消息发送方和接收方在消息传输中都保持激活状态。与套接字和MPI的重要区别在于，它的设计目标一般是支持那些时间要求较为宽松的消息传输，不适合几秒甚至几微秒内要完成的传输。消息进入接收方的消息队列时，接收方不必处于运行状态。发送方和接收方可以彼此完全独立地运行。消息队列系统的队列集合是分布在多台机器上的，因此需要维护一个从队列到其所在网络位置之间的映射关系。一个数据库，存储到网络位置所对应的队列名。发送方A只需要找到最近的路由器，并将队列发送给路由器。路由器负责接下来寻找路径将消息发送给接收方B。采用这种方式，只有在路由器需要添加队列或者删除队列时进行更新，其他队列管理器只需要知道最近的路由器的位置即可。消息转换器：的消息处理，需要消息转换器，是队列网络中负责转换消息的特定结点。对于消息队列系统来说，消息转换器也不过是一个应用程序而已。异步传输模式：流中的数据项是逐个传输的，但是对某一项在何时进行传输并没有进一步的限制。这是采用离散数据流时常见的情况。比如文件的传输。同步传输模式：数据流中每一个单元都定义了一个端到端的最大延迟时间，容许延迟。数据单元的传输时间是否远远小于最大允许延迟并不重要。等时传输模式：数据单元必须按时传输，端到端的延迟时间同时又上限和下限。这个上、下限也称为边界延迟抖动。在视频和音频方面很常用，比如音视频的同步(对口型)。QoS服务质量特性：1) 数据传输所要求的比特率 2) 创建会话的最大延时(比如应用程序何时可以开始发送数据)。 3) 端到端的最大延时 4) 最大延时抖动 5) 最大往返延时。当数据包有不同的延时，接收方先把它们存储在缓冲区，当总是有足够的数据包进入缓冲区时，接收方就可以以固定的速率把数据包传递给应用程序。如在传送音视频时，采用交错传输，丢失的帧分布较广，这样丢失的就不是一大段而是零散的帧，对于音视频的播放影响就较小。但是这样需要更大的缓冲区，因此程序的开始延时更高。流同步同步机制 用应用程序进行同步 多媒体中间件提供接口控制视频和音频流。每个设备和流都有自己的高级接口。中间件层负责处理同步。覆盖网络信息传播模型 anti-entropy结点P随机选取另一结点Q，然后与Q交换信息。更新信息的方法：1) P只是把自己的更新信息发出给Q，基于push的方法2) P只是从Q那里获取更新，基于pull的方法3) P和Q相互发送更新信息给对方，基于push-pull的方法第5章 命名系统名称是用来与实体当前位置无关的方式来定位它们。名称与实体的位置可能毫不相干。访问点：用来实体的一种特殊实体。地址：访问点的名称。所以访问点就是实体的地址。标识符属性：1) 一个标识符最多引用一个实体2) 每个实体最多由一个标识符引用3) 一个标识符始终引用同一个实体（也就是说标识符永远不会重新使用）地址&标识符地址和标识符都是名称类型，但是用于不同目的。地址是用于访问实体的，找到实体的位置，而标识符不一定与实体的位置相关，只是一个使得实体区别于其他实体的标志。广播&多播广播：包含某个实体所用标识符的消息会广播到每台机器上，请求每台机器产看它是否拥有该实体。拥有该实体的机器发送回复消息，消息包含访问点的地址。但是随着网络的扩大，越来越低效。多播：只有符合条件的一组机器才能接收到消息请求。转发指针 链长，断的可能性大，可靠性差当对象从地址空间A移到B时，会留一个客户存根在A中，一个服务器存根在B中。服务器存根要么包含实际对象的本地应用，要么包含该对象远程客户存根的本地引用。对象调用携带一个客户存根的标识，这是调用发起的地方。当调用到达位于当前位置的对象后，会向发起调用的客户存根发送回一个响应。当前位置中包含了对象的当前位置。客户存根会把自己的对应服务器存根调整为对象当前位置中的那个服务器存根。宿主位置：创建实体的位置。分布式散列表分层方法：链接挂载在涉及多个命名空间合并使用的时候，会出现挂载，从这个命名空间挂载到另一空间。访问另一空间的地址。存储结点标识符的目录结点称为挂接点。外部名称空间中的目录结点为挂载点。名称空间的分布全局层：由最高级别的结点组成，由根节点和根节点的子节点组成。涉及到统筹。特点：通常是稳定的，目录表很少改变。可以用来代表组织或组织群。行政层：由那些在单个组织内一起被管理的目录结点组成。特点：代表属于同一组织或行政单位的实体组。虽然会改变，但通常也是稳定的。管理层：由经常改变的结点组成。涉及到个体。在可用性和性能方面，每层的名称服务器都必须满足不同的需求。性能问题：因为全局层结点变化不频繁，所以查找操作的结果一般会长期有效。所以客户可以缓存这些结果。当再次执行同样的操作时，可以直接从缓存中获取结果，而不用再调用名称服务器。所以，全局层的名称服务器不需要快速响应单一的查询请求，需要较大的吞吐能力。迭代名称解析：名称解析程序把完整的名称转发给根名称所在的服务器。服务器每次解析后都将结果返回给客户。递归名称解析：名称服务器会把结果传递给它找到的下一台服务器，解析的结果保存在当前服务器。当最后一台服务器解析结束后，会依次向上取出解析结果，最后汇总到根名称服务器，统一发送回客户。递归名称解析优点：1) 与迭代名称解析相比，缓存结果更为有效2) 减少通信开销目录服务：基于属性的命名系统。实体有一个可以用于查找的相关属性集。如电子邮件系统中，可以用发送者、主题等属性来标记邮件。资源描述框架RDF统一资源描述方法。RDF模型的基础是，资源用由主题、断言和对象组成的三联体来描述。如（Person,name,Alice），主题是Person, 断言是name, 对象是Alice。第六章 同步化物理时钟：计时器。时钟同步算法最大偏移率如果时钟A落后，那么可以在每个中断添加时间来调整。调整的时钟要参考另一个时钟，另一个时钟被称为参考时钟。逻辑时钟：机器的相对时间，不一定与实际时间相同。先发生：ab “a在b之前发生”1) 如果a和b是同一进程中的两个时间，且a在b之前发生，则ab 为真2) 如果a是一个进程发送消息的事件，而b作为另一个进程接收这个消息的事件，则ab也为真。再发送到下一个进程后，如果时钟小于或等于当前进程，那么把后一进程的时钟改为当前进程时钟+1，并且把下一进程以后的时钟都要按照原来的间隔延后。比如P2中56改为61后，那么后面的64也要改成69, 72改为77， 80改为85。向量时钟Lamport时间戳不能捕获因果关系，而向量时钟可以。区别？强制因果有序通信互斥算法1、 集中式算法进程在使用资源时独占资源，当有其他进程发送请求时，放入到请求队列中。2、 非集中式算法每个协作者都被复制了n次。某个进程要访问资源，只需从mn/2个协作者中获取多数投票即可。3、 分布式算法当一个进程要访问资源时，发送一个消息给所有其他进程，包括自己。当一个进程接收到消息时，做出判断1) 若接受者没有访问资源，也不想访问，就返回一个OK消息2) 若接受者已获得访问，就不应答看，并将请求放入队列中3) 若接受者也想访问资源但尚未访问，就比较收到消息的时间戳和自己发送消息的时间戳进行比较，早的获胜。如果发送者获胜，接受者就返回OK。否则接受者将获得访问，不应答，然后将请求消息放到队列中。4、 令牌环算法将进程以环状连接到一起，每个进程只需知道谁在它的下一位上。设置一个令牌，每个进程进行传递。每个进程得到令牌后，看自己要不要访问资源，如果要，就执行。进程执行结束后，把令牌向下传递。如果不要访问资源，就直接把令牌向下传递。四种算法比较欺负算法当任何一个进程发现协作者不再响应请求时，它就发起一次选举1) P向所有编号比它大的进程发送一个ELECTION消息2) 如果无人响应，P获