分布式系统命名部分ppt

上传人:今*** 文档编号:106797827 上传时间:2019-10-16 格式:PPT 页数:42 大小:1.33MB
返回 下载 相关 举报
分布式系统命名部分ppt_第1页
第1页 / 共42页
分布式系统命名部分ppt_第2页
第2页 / 共42页
分布式系统命名部分ppt_第3页
第3页 / 共42页
分布式系统命名部分ppt_第4页
第4页 / 共42页
分布式系统命名部分ppt_第5页
第5页 / 共42页
点击查看更多>>
资源描述

《分布式系统命名部分ppt》由会员分享,可在线阅读,更多相关《分布式系统命名部分ppt(42页珍藏版)》请在金锄头文库上搜索。

1、第5章 命名系统,第5章 命名系统,名称、标识符和地址 无层次命名 结构化命名 基于属性的命名,命名系统,位置无关(location independent) 用户友好(human-friendly name) 高效搜索(effectively search),名称、标识符和地址,名称的实质 在分布式系统中,名称用来指向一个实体。要对实体进行操作,就需要访问实体,因此需要一个访问点。访问点是另一种特殊的实体,它的名称称为地址。 注意 对于实体E,一个与位置无关的名称,是独立于E的访问点的地址。,标识符,纯名称 纯名称是一些没有任何意义的名称;是一些随机的字符串。纯名称只是起区分的作用。 标识符

2、 标识符是具有以下属性的名称: P1:一个标识符最多引用一个实体。 P2:每个实体最多由一个标识符引用。 P3:一个标识符始终引用同一个实体(就是说标识符永远不会重新使用)。,5.2无层次命名,问题提出 当只给出非结构化的名称(比如说一个标识符),我们如何定位它的访问点?,简单方法:广播和多播,转发指针 基于宿主位置的方法 分布式散列表 分层方法,广播和多播,5.2.1简单方法,不能超出局域网 要求所有的进程监听定位请求,广播一个包含实体的标识符,要求拥有该实体的机器返回它当前的地址。,转发指针,当实体移动时,它留下一个指针指向下一个位置。,5.2.2基于宿主位置的方法,利用宿主追踪实体的位置

3、 注册宿主位置。 注册实体所在的远程主机。 宿主与实体所在的远程主机保持联系 客户首先与宿主建立连接,然后与远程主机连接。,5.2.2基于宿主位置的方法,5.2.2基于宿主位置的方法,基于宿主位置的方法的问题 宿主地址必须在实体的生存期内有效。 宿主地址是固定的。 可扩展性差。 问题 我们如何解决永转移的问题?,5.2.3分布式散列表(DHT),Chord 将节点组织成逻辑环 各个节点被赋予一个随机的m位标识符。 每个实体被赋予一个特定的m位键值。 含有键值K的实体位于含有最小标识符ID=K的节点之内(称之为K的后继者)。,DHTs: Finger表,原理 每个节点P维护一个最多M个实体的指状

4、表FTp。 FTpi = succ(p+2i-1) 要查找键k,节点P立即把该请求转发给在P的指状表中索引为J的节点Q。 q = FTpj k FTpj +1 如果p k FTp1,请求也要转发给FTp1。,DHTs: Finger表,利用网络邻近,潜在问题 请求跨因特网进行路由时不稳定:结点k和后继结点(k+1)可能相距很远。,基于拓扑的结点标识符赋值:在标识符赋值时,两个邻近结点所赋给的标识符也是靠近的。很难实现。 邻近路由:每个结点维护多个后继者,转发给最近者。 例:FTqi指向 p+2i-1;p+2i-1区间内的第一个结点。 结点P也能跟踪该区间的其他结点。 邻近邻结点选择:选择最近的

5、结点作为邻结点。,5.2.4分层方法(HLS),基本思想 将底层网络划分为一组域,构建一个大规模的搜索树。每个域都拥有关联的目录节点DIR。,HLS:目录树组织,不变性 实体E的地址存储在叶域或者中间节点。 中间节点含有一个指向更底层子域目录节点的指针。 根节点掌握所有实体的信息。,HLS:查找操作,基本原理 首先在客户所在叶域的目录节点查找实体E。 节点里含有实体E的位置记录=跟随向下查找指针,如果没有E的位置记录继续下一步。 向父节点所在域查找实体E的位置信息,以此类推。,HLS:插入操作,5.3 结构化命名,命名空间本质 名称空间是一个有向图,其中叶节点代表一个实体。目录节点是指向其他叶

6、节点的实体。,注意 目录节点用于存储一个表,其中每条分支边用一个 对来表示。,5.3.1名称空间,结点通过名称存储各种属性,描述实体的各方面信息。 实体类型 实体标识符 实体的位置信息 别名 目录结点除了存储目录表外还能存储其他属性。,5.3.2名称解析,问题 解析名称需要目录结点的信息,如何找到该结点。 终止机制 终止机制如何处理从名称空间中选择初始结点。 www.cs.vu.nl:从域名服务器开始 /home/steen.mbox:从命名图的根结点的目录表开始。 0031204447784:通过拨号 130.37.24.8:路由到VU的web服务器 提问:为什么终止机制必须是隐式的?,名称

7、链接,硬链接 路径名:命名图中每个路径可以通过路径中的边的标签序列来指向,这样的序列称为路径名。,名称链接,注意 结点N5只有一个名称。,5.3.3名称空间的实现,基础问题 通过将命名图结点分布存储实现分布式名称解析。 命名空间分层 全局层:由最高级别的结点组成。 行政层:由那些在单个组织内一起被管理的目录结点组成。 管理层:由那些经常改变的结点组成。,5.3.3名称空间的实现,5.3.3名称空间的实现,迭代名称解析,解析程序将完整名称(dir,name1,namek)发给server0。 Server0将(dir,name)解析为dir1,返回sever1(存储dir1)的地址。 Clien

8、t发送解析(dir,name1,namek)请求给sever1。,递归名称解析,解析程序将完整名称(dir,name1,namek)发给server0。 Server0将(dir,name)解析为dir1,发送解析(dir,name1,namek)请求给sever1返回sever1(存储dir1)的地址。 Server0等待server1的响应,然后发送给client.,递归名称解析服务器缓存,可扩展性,规模的可扩展性 必须保证服务器在每个时间单元能处理大量的请求,特别对于高层的服务器。,解决方案 假设结点的信息稳定。就可以通过将结点映射到多个服务器来增加副本数量,以至于可以从最近的服务器进行

9、名字解析。,可扩展性,问题 通过将结点映射到服务器能定位到任何地方,我们引入隐含的位置从属。,地理跨度 必须保证名字解析进程能跨越很大的地理空间。,示例:分布式域名系统,基本思想 将DNS全名哈希成一个键值k,然后在基于DHT的系统中查询k值。缺点:不能再子域中查询所有的结点。,结点信息,DNS on Pastry,Pastry 带有前缀的键值构成的基于DHT的系统。考虑一个4位键值的系统。一个ID为3210追踪以下的结点。,注意 结点3210负责处理前缀为321的键。如果获得一个键值为3012的请求,它将转发给结点N30。对于DNS:负责键值k的结点用一个哈希值存储DNS记录。,DNS记录副

10、本,定义 在i层被复制DNS记录被复制到所有前缀为i的结点。注意:在i层被复制的记录通常需要i个查找步骤。,结论 假设Xi是在i层被复制最多的记录部分。那么:,N为网络中的结点数, d = b(1a)=a and a 1,假设a是ZipF分布的参数。,DNS记录副本,意图 当查找DNS记录是,如果你要达到平均为1跳的要求,令b=4,a=0.9,N=10,000,并且有1000000条记录。,5.4基于属性的命名,概论 在分布式系统中,描述实体最常用的方法是利用属性。 问题 查找操作很耗时,因为它要求匹配请求的属性值而不是实际的值。 解决方案 结合传统的结构化命名,将目录服务作为数据库,5.4.1 目录服务,是指基于属性的命名系统,而支持结构化命名的系统通常称为命名系统 属性设计因人而异 引入资源描述框架(resource description framework RDF) 基于属性的命名系统基本上要求对所有资源描述进行穷举搜索。,5.4.2分层实现:LDAP,5.4.3 非集中式实现,映射到分布式散列表 语义覆盖网络,映射到分布式散列表,将资源描述给出的(属性,值)对转换为DHT的一个键值,键值中的某些位用于表示属性,某些位用于表示值。,语义覆盖网络(semantic overlay network),语义相近的邻结点及其链接构成语义覆盖网。,END,

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 高等教育 > 大学课件

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号