分布式系统第二章PPT课件.ppt

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

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

3、/subscribe)系统以事件为中心的体系结构组件组件传送 发布事件总线组件组件组件共享（持久）的数据空间传送发布2011-9-14计算机软件所 于戈8系统体系结构（SystemArchitecture）软件体系结构的具体实例集中型体系结构客户/服务器模型服务器：实现特定服务的进程客户：向服务器提出请求、等待答复的进程请求/答复模式2.2系统体系结构请求答复客户服务器等待2011-9-14计算机软件所 于戈9层次型C/S体系结构n用户接口层、处理层、数据层n例：搜索引擎2011-9-14计算机软件所 于戈10多层C/S体系结构n瘦客户/胖服务器：用户接口简单，但后端负载重n胖客户/瘦服务器：

4、能提高性能，但管理困难客户机服务器2011-9-14计算机软件所 于戈11三层C/S体系结构举例用户用户接口接口应用应用服务器服务器数据库数据库服务器服务器时间时间2011-9-14计算机软件所 于戈12新型体系结构n垂直分布：不同功能的分布n水平分布：相同功能的复制n对等型（peer-peer）分布水平分布的Web服务器负载平衡、容错等2011-9-14计算机软件所 于戈13P2P技术n从C/S模式到P2P模式引自：中科院计算所罗杰文PeertoPeer综述http:/ 于戈14P2P技术nP2P 应用n文件内容共享和下载，例如Napster、Gnutella、eDonkey、eMule、M

5、aze、BT等；n计算能力和存储共享，例如SETIhome、Avaki、Popular Power等；n协同与服务共享平台，例如JXTA、Magi、Groove等；n即时通讯工具，包括ICQ、QQ、Yahoo Messenger、MSN Messenger等；nP2P通讯与信息共享，例如Skype、Crowds、Onion Routing等；n网络电视：沸点、PPStream、PPLive、QQLive、SopCast等。2011-9-14计算机软件所 于戈15P2P技术n覆盖网络覆盖网络(overlay network)：建立在另一个网络上的网络，属于应用层网络，面向应用层的，不考虑或很少考

6、虑网络层，物理层的问题。nP2P网络是建立在Internet之上一种覆盖网络。nP2P网络的拓扑结构 n集中型集中型（Centralized Topology）；n分散型无结构拓扑分散型无结构拓扑（Decentralized Unstructured Topology）；n分散型结构化拓扑分散型结构化拓扑（Decentralized Structured Topology，也称作DHT网络）；n半分散型拓扑半分散型拓扑（Partially Decentralized Topology）。2011-9-14计算机软件所 于戈16P2P网络的拓扑结构n集中型拓扑结构集中型拓扑结构 n例，MP3共享

7、软件Napster，通过一个中央索引中央索引服务器服务器保存所有Napster用户上传的音乐文件索引和存放位置的信息。n存在问题n中心节点的单点失效n中心节点的维护成本n可伸缩性2011-9-14计算机软件所 于戈17P2P网络的拓扑结构n分散型无结构拓扑结构分散型无结构拓扑结构 n例，Gnutella协议。基于完全随机图的Flooding搜索算法。n存在问题n不能保证性能n网络带宽的消耗 非常大n可伸缩性差2011-9-14计算机软件所 于戈18P2P网络的拓扑结构n覆盖网络构造算法（覆盖网络构造算法（Gossip-based protocols）n关于所有节点的表，称为全局视图（total

8、 view）。每个节点维护一个部分视图（partial view），含有c个邻接点的列表。n表项：=n节点之间定期交换表项。由主动线程（可主动发起通信）和被动线程完成。n节点的加入n与任意一个已知的节点进行视图交换n节点的删除n可自行离开，无需通知其他节点。n当其他节点发现某节点P不再响应时，将其从表中删除2011-9-14计算机软件所 于戈19P2P网络的拓扑结构n主动线程和被动线程的执行步骤主动线程和被动线程的执行步骤do forever receive bufferp from p if pull then /0 is the initial age buffer(MyAddress,0

9、)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.selectPeer()if push then /0 is the initial age buffer(MyAddress,0)view.permute()move oldest H items to end of view buffer.ap

10、pend(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）（b）2011-9-14计算机软件所 于戈20P2P网络的拓扑结构n分散式结构化拓扑结构分散式结构化拓扑结构 n采用分布式散列表（Distributed Hash Table,简写成DHT）技术来组织网络中的结点。n加密散列函数，将一个对象的名字或关键词映

11、射为128位或160位的散列值nDHT是一个由广域范围大量结点共同维护的巨大散列表。n散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。nTapestry，Pastry，Chord和CAN2011-9-14计算机软件所 于戈21P2P网络的拓扑结构n分散式结构化拓扑结构分散式结构化拓扑结构 n例：MIT的Chord 系统n网络结点按照一定的方式分配一个唯一结点标识符(Node ID)n通过散列运算为对象产生一个唯一的对象标识符(Object ID）n分布式查找协议，将指定的关键字(Key)映射到对应的结点(Node)n时间复杂性O(log(N)2011-

12、9-14计算机软件所 于戈22P2P网络的拓扑结构n分散式结构化拓扑结构分散式结构化拓扑结构 n例：CAN 系统n将(key,value)对存储在拥有该点所在区域的结点内n路由算法：将请求传给当前结点四邻中坐标最接近目标点的结点n时间复杂性O(n/d)，d为系统维数2011-9-14计算机软件所 于戈23P2P网络的拓扑管理n使用无结构P2P技术构造特定的结构化P2P覆盖网络的两层结构2009-9-14计算机软件所 于戈24P2P网络的拓扑管理n使用两层的无结构P2P系统，最终生成的特定的覆盖网络2011-9-14计算机软件所 于戈25超级节点（Superpeer）n超级节点：能够维护索引或充

13、当代理的节点2011-9-14计算机软件所 于戈26混合型体系结构n将客户/服务器结构与非集中式结构相结合n边界服务器系统（edge server）C/SP2P2011-9-14计算机软件所 于戈27混合型体系结构n协作分布式系统n例1：文件共享系统BitTorrentn强制每个参与者，即可下载文件，也负责上载文件n全局目录：在Web站点中保存，指向下载文件的tracker。n跟踪器（tracker）:记录活动节点的服务器2011-9-14计算机软件所 于戈28混合型体系结构n协作分布式系统n例2：Globule系统 协作式CDN（collaborative content distribut

14、ion network）n没有边界服务器n用户提供增强型Web服务器，包含如下3种组件n可重定位客户请求到其他服务器n可分析访问模式n可管理Web页复制2011-9-14计算机软件所 于戈292.3 体系结构与中间件n中间件在体系结构中的位置n中间件如何适应于应用需要n中间件的多种版本n中间件可重新配置和定制2011-9-14计算机软件所 于戈30拦截器（Interceptor）n拦截器（Interceptor）n软件结构n可中断正常执行的控制流，插入执行其他代码n例：远程对象调用n请求级拦截器n消息级拦截器2011-9-14计算机软件所 于戈31自适应软件n自适应软件n可以地自动适应环境变化

15、如移动、QoS、故障、能耗n随着环境变化而变化n三种方案1.分离关注点（Separation of concerns）n把主要功能与附加功能分离开n面向方面的软件开发（aspect-oriented software development）2011-9-14计算机软件所 于戈32自适应软件n三种方案2.计算反射（Computational reflection）n自我检查，并调整自身行为3.基于组件的设计n运行时，进行动态配置n迟后绑定（late binding）2011-9-14计算机软件所 于戈33自治计算（autonomiccomputing）可自动地自适应变化自主系统（self-s

16、tarsystem）自主管理自主恢复自主配置自主优化2.4 分布式系统的自主管理分布式系统的自主管理2011-9-14计算机软件所 于戈34反馈控制模型三要素：测量；分析；调整；自主控制自主控制2011-9-14计算机软件所 于戈35例：Astrolabe监视系统观察系统行为。区域信息：数据收集和信息聚集自主监视自主监视2011-9-14计算机软件所 于戈36例：Globule差分复制策略What-if分析：复制的位置、一致性维护策略自主复制管理自主复制管理2011-9-14计算机软件所 于戈37例：Globule差分复制策略轨迹驱动模拟方法：根据预测误差与跟踪轨迹长度的关系，确定复制策略自主

17、复制管理自主复制管理2011-9-14计算机软件所 于戈38例：Jade系统自动组件修复管理修复过程的执行步骤:终止非故障组件和故障组件之间的所有绑定请求节点管理器去在域中启动和增加一个新节点将新节点配置成与崩溃节点相同的组件重新建立所有在前面已终止的所有绑定自主修复自主修复2011-9-14计算机软件所 于戈392.5 客户-服务器模型n服务器（Server）：服务方，实现特定服务的进程n客户(Client)：委托方，请求服务的进程n交互方式：请求-回答(request-reply)时间2011-9-14计算机软件所 于戈40客户和服务器举例n头文件2009-9-14计算机软件所 于戈41客

18、户和服务器举例nServer程序2009-9-14计算机软件所 于戈42客户和服务器举例nClient程序2011-9-14计算机软件所 于戈43消息格式举例struct message long source;/*发送者标识发送者标识*/long dest;/*接受者标识接受者标识*/long opcode;/*操作码：读、写、创建、删除操作码：读、写、创建、删除*/long result;/*返回结果代码返回结果代码：成功、失败：成功、失败*/long offset;/*读写位置读写位置*/long count;/*读写计数读写计数*/char filenameMAX_PATH;/*文件名

19、文件名*/char dataBUF_SIZE;/*数据区数据区*/2011-9-14计算机软件所 于戈44服务器程序举例void 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

20、source,&m2);/*返回结果返回结果*/2009-9-14计算机软件所 于戈45客户程序举例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(CLIE

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

22、9-14计算机软件所 于戈48寻址方式(Addressing)1、计算机+进程n计算机号/进程号n机号+进程号n机号+本地标识号例：UNIXn机器IP地址n端口号(port)/*Socketaddress,internetstyle.*/structsockaddr_inshortsin_family;/*AF_INET*/u_shortsin_port;structin_addrsin_addr;charsin_zero8;2011-9-14计算机软件所 于戈49寻址方式(Addressing)2、全局进程标识符n广播定位进程3、ASCII码进程名n名字服务器2011-9-14计算机软件所

23、于戈50（1）阻塞发送原语同步式（2）非阻塞发送原语异步式内核缓冲区copy（3）阻塞接受原语等待（4）非阻塞接受原语Test轮询接收（5）超时（timeout)时间时间时间时间阻塞与非阻塞型发送/接收2011-9-14计算机软件所 于戈51有缓冲与无缓冲型接收n无缓冲区n服务器等待客户n直接丢弃消息n暂存“意外”消息n有缓冲区n邮箱（mailbox)：n缓存所有的输入消息n“溢出”问题2011-9-14计算机软件所 于戈52可靠的和非可靠的发送/接收n非可靠的收发n可能丢失消息n由用户负责确认n可靠的收发n由系统确认（acknowledge）a)内核-内核确认b)应答(reply)作为确认n

24、客户内核确认c)折衷方法n服务器端设置计时器，超时后，发确认消息2011-9-14计算机软件所 于戈53实现技术小结项目方案1方案2方案3寻址机器号稀疏的全局进程号ASCII名（NS）阻塞？阻塞copy-to-kernel式非阻塞，中断式非阻塞缓冲？无缓冲，丢弃意外的消息无缓冲，暂存意外的消息缓存，邮箱方式可靠？不可靠Request-Ack-Reply-AckRequest-Reply-Ack2011-9-14计算机软件所 于戈54包类型代码类型发方 收方意义REQ请求CS客户需要服务REP应答SC服务器的回答ACK确认一方另一方已收到包AYA活着吗？CS检查服务器是否崩溃IAA还活着SC服务

25、器在线TA重试SC服务器无空间AU未知地址SC无效地址2011-9-14计算机软件所 于戈55包交换举例CREQ REPSCREQ ACK REP ACKS (a)(b)CREQ REPACKSCREQ ACKAYA IAA REP ACKS(c)(d)2011-9-14计算机软件所 于戈56小节n软件体系结构的四种样式n分层、OO、事件为中心、数据为中心n体系分布式系统的三种典型体系结构n集中式、非集中式、混合式n自主管理分布式系统n闭环反馈控制n客户/服务器模型2011-9-14计算机软件所 于戈571.举出一个分布式系统实例，该系统采用以数据为中心的软件体系结构。2.再举出一个分布式系统实例，该系统采用基于事件的软件体系结构。3.什么是三层客户-服务器体系结构，举出一个实际应用案例。4.在结构化覆盖网络中，如果消息是根据覆盖的拓扑结构来路由的，讨论其优缺点。习题2011-9-14计算机软件所 于戈585.在非结构化覆盖网络中，每个节点可随机地选择c个邻接点。要查找一个文件，节点将洪泛一个请求给他的邻接点，这些请求又将被再次洪泛下去。该请求将到达多少个节点。6.请从技术角度来解释为什么BitTorrent中的tit-for-tat策略比因特网中的文件共享好的多？7.请给出自主管理系统的一个实例，其中的分析部件为分布的或隐藏的。习题（续）