分布式系统命名部分PPT.ppt

第5章 命名系统 名称、标识符和地址 无层次命名 结构化命名 基于属性的命名 命名系统 位置无关（location independent） 用户友好（human-friendly name） 高效有哪些信誉好的足球投注网站（effectively search） 5.4.1 目录服务 是指基于属性的命名系统，而支持结构化命名的系统通常称为命名系统 属性设计因人而异 引入资源描述框架（resource description framework RDF） 基于属性的命名系统基本上要求对所有资源描述进行穷举有哪些信誉好的足球投注网站。 5.4.3 非集中式实现 映射到分布式散列表 语义覆盖网络 映射到分布式散列表 将资源描述给出的（属性，值）对转换为DHT的一个键值，键值中的某些位用于表示属性，某些位用于表示值。 语义覆盖网络（semantic overlay network） 语义相近的邻结点及其链接构成语义覆盖网。 END 可扩展性 问题 通过将结点映射到服务器能定位到任何地方，我们引入隐含的位置从属。 地理跨度 必须保证名字解析进程能跨越很大的地理空间。 示例：分布式域名系统 基本思想 将DNS全名哈希成一个键值k，然后在基于DHT的系统中查询k值。缺点：不能再子域中查询所有的结点。 结点信息 DNS on Pastry Pastry 带有前缀的键值构成的基于DHT的系统。考虑一个4位键值的系统。一个ID为3210追踪以下的结点。 注意 结点3210负责处理前缀为321的键。如果获得一个键值为3012的请求，它将转发给结点N30。对于DNS：负责键值k的结点用一个哈希值存储DNS记录。 DNS记录副本 定义 在i层被复制—DNS记录被复制到所有前缀为i的结点。注意：在i层被复制的记录通常需要i个查找步骤。 结论 假设Xi是在i层被复制最多的记录部分。那么： N为网络中的结点数， d = b(1??a)=a and a 1，假设a是ZipF分布的参数。 DNS记录副本 意图 当查找DNS记录是，如果你要达到平均为1跳的要求，令b=4,a=0.9,N=10，000，并且有1000000条记录。 5.4基于属性的命名 概论 在分布式系统中，描述实体最常用的方法是利用属性。 问题 查找操作很耗时，因为它要求匹配请求的属性值而不是实际的值。 解决方案 结合传统的结构化命名，将目录服务作为数据库 5.4.2分层实现：LDAP * 第5章 命名系统 名称、标识符和地址 名称的实质 在分布式系统中，名称用来指向一个实体。要对实体进行操作，就需要访问实体，因此需要一个访问点。访问点是另一种特殊的实体，它的名称称为地址。 注意 对于实体E，一个与位置无关的名称，是独立于E的访问点的地址。 标识符 纯名称 纯名称是一些没有任何意义的名称；是一些随机的字符串。纯名称只是起区分的作用。 标识符 标识符是具有以下属性的名称： P1：一个标识符最多引用一个实体。 P2：每个实体最多由一个标识符引用。 P3：一个标识符始终引用同一个实体（就是说标识符永远不会重新使用）。 5.2无层次命名 问题提出 当只给出非结构化的名称（比如说一个标识符），我们如何定位它的访问点？ 简单方法：广播和多播，转发指针 基于宿主位置的方法 分布式散列表 分层方法 广播和多播 5.2.1简单方法 不能超出局域网 要求所有的进程监听定位请求 广播一个包含实体的标识符，要求拥有该实体的机器返回它当前的地址。 转发指针 当实体移动时，它留下一个指针指向下一个位置。 5.2.2基于宿主位置的方法 利用宿主追踪实体的位置 注册宿主位置。 注册实体所在的远程主机。 宿主与实体所在的远程主机保持联系 客户首先与宿主建立连接，然后与远程主机连接。 5.2.2基于宿主位置的方法 5.2.2基于宿主位置的方法 基于宿主位置的方法的问题 宿主地址必须在实体的生存期内有效。 宿主地址是固定的。 可扩展性差。 问题 我们如何解决永转移的问题？ 5.2.3分布式散列表（DHT） Chord 将节点组织成逻辑环 各个节点被赋予一个随机的m位标识符。 每个实体被赋予一个特定的m位键值。 含有键值K的实体位于含有最小标识符ID=K的节点之内（称之为K的后继者）。 DHTs: Finger表 原理 每个节点P维护一个最多M个实体的指状表FTp[]。 FTp[i] = succ(p+2i-1) 要查找键k，节点P立即把该请求转发给在P的指状表中索引为J的节点Q。 q = FTp[j] k