分布式系统第二章课件

1、第2章 分布式系统体系结构东北大学信息学院于 戈2011年9月第1页，共58页。2011-9-14计算机软件所 于戈22.1 体系结构的样式2.2 系统体系结构2.3 体系结构与中间件2.4 自主管理2.5 客户/服务器模型第二章 主要内容第2页，共58页。2011-9-14计算机软件所 于戈3 软件体系结构（Software Architecture） 软件的组件，以及组件之间的相互关系 软件体系结构的要素 组件(component)：模块单元，能提供良好的接口 连接器（connector）：实现组件间通信的机制 软件体系结构的样式 如何表示一个体系结构 常用的有4种2.1 体系结构的样式第

2、3页，共58页。2009-9-14计算机软件所 于戈4 系统由自上而下的不同层次的组件组成； 只有相邻的层次可以通信； 请求消息自上而下，响应自下而上。层次型体系结构第N层第N-1层第2层第1层第4页，共58页。2011-9-14计算机软件所 于戈5 基于对象模型 每个组件对应一个对象； 组件之间通信通过远程方法调用（RMI）实现；面向对象的体系结构对象对象对象对象对象第5页，共58页。2011-9-14计算机软件所 于戈6 组件间的通信，通过基于一个公用的存储（如共享的分布式文件系统）实现 例如，基于Web的分布式系统，组件使用共享的基于Web的数据服务以数据为中心的体系结构第6页，共58页

3、。2011-9-14计算机软件所 于戈7 组件间的通信，通过事件（可带有数据）的传播实现； 例如，发布/订阅(publish/subscribe)系统以事件为中心的体系结构组件组件传送 发布事件总线组件组件组件共享（持久）的数据空间传送 发布第7页，共58页。2011-9-14计算机软件所 于戈8 系统体系结构（System Architecture ） 软件体系结构的具体实例 集中型体系结构 客户/服务器模型 服务器：实现特定服务的进程 客户：向服务器提出请求、等待答复的进程 请求/答复模式2.2 系统体系结构请求 答复客户服务器等待第8页，共58页。2011-9-14计算机软件所 于戈9层

4、次型C/S体系结构用户接口层、处理层、数据层例：搜索引擎第9页，共58页。2011-9-14计算机软件所 于戈10多层C/S体系结构瘦客户/胖服务器：用户接口简单，但后端负载重胖客户/瘦服务器：能提高性能，但管理困难客户机服务器第10页，共58页。2011-9-14计算机软件所 于戈11三层C/S体系结构举例用户接口应用服务器数据库服务器时间第11页，共58页。2011-9-14计算机软件所 于戈12新型体系结构垂直分布：不同功能的分布水平分布：相同功能的复制对等型（peer-peer）分布水平分布的Web服务器负载平衡、容错等第12页，共58页。2011-9-14计算机软件所 于戈13P2P

5、技术从C/S模式到P2P模式引自：中科院计算所罗杰文 Peer to Peer 综述 /users/luojw/P2P/ch01.html第13页，共58页。2011-9-14计算机软件所 于戈14P2P技术P2P 应用文件内容共享和下载，例如Napster、Gnutella、eDonkey、eMule、Maze、BT等； 计算能力和存储共享，例如SETIhome、Avaki、Popular Power等； 协同与服务共享平台，例如JXTA、Magi、Groove等； 即时通讯工具，包括ICQ、QQ、Yahoo Messenger、MSN Messenger等； P2P通讯与信息共享，例如Sk

6、ype、Crowds、Onion Routing等； 网络电视：沸点、PPStream、 PPLive、 QQLive、 SopCast等。 第14页，共58页。2011-9-14计算机软件所 于戈15P2P技术覆盖网络(overlay network)： 建立在另一个网络上的网络，属于应用层网络，面向应用层的，不考虑或很少考虑网络层，物理层的问题。P2P网络是建立在Internet之上一种覆盖网络。P2P网络的拓扑结构 集中型（Centralized Topology）； 分散型无结构拓扑（Decentralized Unstructured Topology）； 分散型结构化拓扑（Dece

7、ntralized Structured Topology，也称作DHT网络）； 半分散型拓扑（Partially Decentralized Topology）。 第15页，共58页。2011-9-14计算机软件所 于戈16P2P网络的拓扑结构集中型拓扑结构 例， MP3共享软件Napster，通过一个中央索引服务器保存所有Napster用户上传的音乐文件索引和存放位置的信息。存在问题中心节点的单点失效中心节点的维护成本可伸缩性第16页，共58页。2011-9-14计算机软件所 于戈17P2P网络的拓扑结构分散型无结构拓扑结构 例， Gnutella协议。基于完全随机图的Flooding搜索

8、算法。存在问题不能保证性能网络带宽的消耗 非常大可伸缩性差第17页，共58页。2011-9-14计算机软件所 于戈18P2P网络的拓扑结构覆盖网络构造算法（Gossip-based protocols） 关于所有节点的表，称为全局视图（total view）。每个节点维护一个部分视图（partial view），含有c个邻接点的列表。表项：=节点之间定期交换表项。由主动线程（可主动发起通信）和被动线程完成。节点的加入与任意一个已知的节点进行视图交换节点的删除可自行离开，无需通知其他节点。当其他节点发现某节点P不再响应时，将其从表中删除第18页，共58页。2011-9-14计算机软件所 于戈19

9、P2P网络的拓扑结构主动线程和被动线程的执行步骤do forever receive bufferp from p if pull then / 0 is the initial age buffer (MyAddress,0) view.permute() move oldest H items to end of view buffer.append(view.head(c/2-1) send buffer to p view.select(c,H,S,bufferp) view.increaseAge()do forever wait(T time units) pview.select

10、Peer() if push then / 0 is the initial age buffer (MyAddress,0) view.permute() move oldest H items to end of view buffer.append(view.head(c/2-1) send buffer to p else / empty view to trigger response send (null) to p if pull then receive bufferp from p view.select(c,H,S,bufferp) view.increaseAge()（a

11、）（b）第19页，共58页。2011-9-14计算机软件所 于戈20P2P网络的拓扑结构分散式结构化拓扑结构 采用分布式散列表（Distributed Hash Table, 简写成DHT）技术来组织网络中的结点 。加密散列函数，将一个对象的名字或关键词映射为128位或160位的散列值DHT是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。Tapestry，Pastry，Chord和CAN第20页，共58页。2011-9-14计算机软件所 于戈21P2P网络的拓扑结构分散式结构化拓扑结构 例：MIT的Chor

12、d 系统网络结点按照一定的方式分配一个唯一结点标识符(Node ID)通过散列运算为对象产生一个唯一的对象标识符(Object ID）分布式查找协议，将指定的关键字(Key) 映射到对应的结点(Node) 时间复杂性O(log(N)第21页，共58页。2011-9-14计算机软件所 于戈22P2P网络的拓扑结构分散式结构化拓扑结构 例：CAN 系统将(key, value) 对存储在拥有该点所在区域的结点内路由算法：将请求传给当前结点四邻中坐标最接近目标点的结点时间复杂性O(n/d)，d为系统维数第22页，共58页。2011-9-14计算机软件所 于戈23P2P网络的拓扑管理使用无结构P2P技

13、术构造特定的结构化P2P覆盖网络的两层结构第23页，共58页。2009-9-14计算机软件所 于戈24P2P网络的拓扑管理使用两层的无结构P2P系统，最终生成的特定的覆盖网络第24页，共58页。2011-9-14计算机软件所 于戈25超级节点（Superpeer）超级节点：能够维护索引或充当代理的节点第25页，共58页。2011-9-14计算机软件所 于戈26混合型体系结构将客户/服务器结构与非集中式结构相结合边界服务器系统（edge server）C/SP2P第26页，共58页。2011-9-14计算机软件所 于戈27混合型体系结构协作分布式系统例1：文件共享系统BitTorrent强制每个

14、参与者，即可下载文件，也负责上载文件全局目录：在Web站点中保存，指向下载文件的tracker。跟踪器（tracker）:记录活动节点的服务器第27页，共58页。2011-9-14计算机软件所 于戈28混合型体系结构协作分布式系统例2：Globule系统 协作式CDN（collaborative content distribution network）没有边界服务器用户提供增强型Web服务器，包含如下3种组件可重定位客户请求到其他服务器可分析访问模式可管理Web页复制第28页，共58页。2011-9-14计算机软件所 于戈292.3 体系结构与中间件中间件在体系结构中的位置中间件如何适应于应

15、用需要中间件的多种版本中间件可重新配置和定制第29页，共58页。2011-9-14计算机软件所 于戈30拦截器（Interceptor）拦截器（Interceptor）软件结构可中断正常执行的控制流，插入执行其他代码例：远程对象调用请求级拦截器消息级拦截器第30页，共58页。2011-9-14计算机软件所 于戈31自适应软件自适应软件可以地自动适应环境变化，如移动、QoS、故障、能耗随着环境变化而变化三种方案分离关注点（Separation of concerns）把主要功能与附加功能分离开面向方面的软件开发（aspect-oriented software development）第31页，

16、共58页。2011-9-14计算机软件所 于戈32自适应软件三种方案计算反射（Computational reflection）自我检查，并调整自身行为基于组件的设计运行时，进行动态配置迟后绑定（late binding）第32页，共58页。2011-9-14计算机软件所 于戈33自治计算（autonomic computing）可自动地自适应变化自主系统（self-star system）自主管理自主恢复自主配置自主优化2.4 分布式系统的自主管理第33页，共58页。2011-9-14计算机软件所 于戈34反馈控制模型三要素：测量；分析；调整；自主控制第34页，共58页。2011-9-14计

17、算机软件所 于戈35例：Astrolabe监视系统观察系统行为。区域信息：数据收集和信息聚集自主监视第35页，共58页。2011-9-14计算机软件所 于戈36例：Globule差分复制策略What-if分析：复制的位置、一致性维护策略自主复制管理第36页，共58页。2011-9-14计算机软件所 于戈37例：Globule差分复制策略轨迹驱动模拟方法：根据预测误差与跟踪轨迹长度的关系，确定复制策略自主复制管理第37页，共58页。2011-9-14计算机软件所 于戈38例：Jade系统自动组件修复管理修复过程的执行步骤:终止非故障组件和故障组件之间的所有绑定请求节点管理器去在域中启动和增加一个

18、新节点将新节点配置成与崩溃节点相同的组件重新建立所有在前面已终止的所有绑定自主修复第38页，共58页。2011-9-14计算机软件所 于戈392.5 客户-服务器模型服务器（Server）：服务方，实现特定服务的进程客户(Client)：委托方，请求服务的进程交互方式：请求-回答(request-reply)时间第39页，共58页。2011-9-14计算机软件所 于戈40客户和服务器举例头文件第40页，共58页。2009-9-14计算机软件所 于戈41客户和服务器举例Server程序第41页，共58页。2009-9-14计算机软件所 于戈42客户和服务器举例Client程序第42页，共58页。

19、2011-9-14计算机软件所 于戈43消息格式举例struct message long source; /* 发送者标识*/ long dest; /* 接受者标识 */ long opcode; /* 操作码：读、写、创建、删除 */ long result; /* 返回结果代码 ：成功、失败*/ long offset; /* 读写位置 */ long count; /* 读写计数 */ char filenameMAX_PATH; /* 文件名*/ char dataBUF_SIZE; /* 数据区*/第43页，共58页。2011-9-14计算机软件所 于戈44服务器程序举例void

20、 main(void) struct message m1,m2; /* 输入、输出的消息 */ int r; /* 返回的执行结果 */ while (1） receive(FILE_SERVER,&m1); /* 等待客户请求 */ case(m1.opcode) /* 执行请求的操作 */ case READ: r = do_read(&m1,&m2); break; : default: r = E_BAD_OPCODE; m2.result = r; send(m1.source,&m2); /* 返回结果 */ 第44页，共58页。2009-9-14计算机软件所 于戈45客户程序举

21、例int read(char *file, int position , int nbytes, char *buf) struct message m1; /* 消息缓冲区 */ m1.opcode = READ; /* 设置参数 */ m1.offset = position; /* 读位置 */ m1.count = nbytes; /* 读长度 */ strcpy(&m1.filename,file) /* 文件名 */ send(FILE_SERVER, &m1); /* 发送请求 */ receive(CLIENT,&m1); /* 等待服务器应答 */ if(m1.result

22、= OK) strcpy(buf, &m1.data); /* 置缓冲区 */ return(m1.result); /* 返回结果 */ 第45页，共58页。2011-9-14计算机软件所 于戈46客户-服务器模型的实现客户：用户进程（程序）服务器：能够提供服务的进程 12OS内核客户OS内核服务器请求应答第46页，共58页。2011-9-14计算机软件所 于戈47通信协议简化的请求/应答协议 无路由、无连接两个基本操作send(dest, &mptr)receive(addr,&mptr)765请求/应答432链路层1物理层第47页，共58页。2011-9-14计算机软件所 于戈48寻址方

23、式(Addressing)1、计算机+进程计算机号/进程号机号+进程号机号+本地标识号例：UNIX机器IP地址端口号(port)/* Socket address, internet style. */struct sockaddr_in short sin_family; /*AF_INET*/ u_short sin_port; struct in_addr sin_addr; char sin_zero8;第48页，共58页。2011-9-14计算机软件所 于戈49寻址方式(Addressing)2、全局进程标识符广播定位进程3、ASCII码进程名名字服务器第49页，共58页。2011-

24、9-14计算机软件所 于戈50 （1）阻塞发送原语 同步式（2）非阻塞发送原语 异步式 内核缓冲区copy（3）阻塞接受原语 等待（4）非阻塞接受原语 Test轮询接收（5）超时（timeout)时间时间阻塞与非阻塞型发送/接收第50页，共58页。2011-9-14计算机软件所 于戈51有缓冲与无缓冲型接收无缓冲区服务器等待客户直接丢弃消息暂存“意外”消息有缓冲区邮箱（mailbox)：缓存所有的输入消息“溢出”问题第51页，共58页。2011-9-14计算机软件所 于戈52可靠的和非可靠的发送/接收非可靠的收发可能丢失消息由用户负责确认可靠的收发由系统确认（acknowledge）内核-内核确认应答(reply)作为确认客户内核确认折衷方法服务器端设置计时器，超时后，发确认消息第52页，共58页。2011-9-14计算机软件所 于戈53实现技术小结项目方案1方案2方案3寻址机器号稀疏的全局进程号ASCII名（NS）阻塞？阻塞copy-to