命名与资源统一定位

1、1 实体命名2 移动实体的定位3 无引用实体的删除为什么要命名？名称的形式？命名的方式有哪些？对实体进行操作就需要一个访问点.访问点的名称称为地址。一个实体的访问点的地址也简称为实体的地址。这种命名方式的缺点： 访问点随时会发生改变或者重新分配给另一实体，我们就得到一个无效的查询结果。 一个实体可能有多个访问点，哪个地址用来作为引用是不清楚的。标识符是用来唯一标识实体的名称。标识符具有以下属性：一个标识符最多指向一个实体；每个实体最多由一个标识符指向；一个标识符始终指向同一个实体（即不会重新使用）。例如：图书ISBN编号、硬盘序列号等由自然语言定义的名称，即用户自己定义的名称。例如：Windo

2、ws系统中的文件名定义：一个系统中的所有实体的名称的集合以及其相互的关系表示方式：带有标注的具有两种类型节点的有向图l叶节点：表示一个命名的实体，其性质是不具有分支边l目录节点：具有一定数量的分支边，每条边用一个名称标注。用于存储一个表，其中每条分支边用一个（边标签，节点标识符）对来表示。l特殊的节点根节点：只具有分支边，不具有进入边n0：home,steen,mbox这样的序列称为路径名。 绝对路径路径名 相对路径在图中通常不使用路径名n0：home,steen,mbox而是使用其字符串表示法/home/steen/mbox来表示。全局与局部名称n全局名称：绝对名称，无论在何处使用，都标识同

3、一实体n局部名称：相对名称，其所标识的实体依赖于使用上下文根节点：根目录目录节点：文件目录（文件夹）叶节点：文件 在逻辑磁盘的连续磁盘块上实现的文件系统的一般组织结构如图所示：n名称解析：查询名称的过程 考虑路径名N: 解析过程：1.解析从命名图的节点N开始2.在N的目录表查询名称label-1，并返回label-1所指向的节点的标识符3.解析过程在标示出的节点目录表中查询名称label-2，4.以此类推5.直到解析会在由label-n所指向的最后一个节点上停止，并返回该节点的内容n问题一：从哪里开始解析名称？n问题二：怎么开始解析名称？知道如何启动以及在何处启动名称解析通常称为终止机制。从本

4、质上讲，终止机制处理从名称空间中选择初始节点，名称解析从初始节点开始。解析文件名需要事先实现一些机制，通过他们解析程序才可以启动。例如：一个字符串“12345678901”，很多人都不知道如何处理这些数字，除非告诉他们这个数列是电话号码。该信息足够启动解析程序。别名：是同一个实体的另一个名称别名的实现方式：（1）硬连接：允许多个绝对路径名来指向命名图中的同一个节点（2）符号连接：用叶节点来表示实体，而不是存储实体的地址或位置，该节点存储绝对路径名。 由于在分布式系统中名称空间分布在不同的机器上，因此在进行名称解析之前需要想办法将不同机器上的名称空间“合并”。方法：（1）挂载； （2）全局名称服

5、务。定义：用一个目录节点来存储一个外部名称空间的一个目录节点的标识符。存储节点标识符的目录节点称为挂接点；外部名称空间的目录节点称为挂载点。 在分布式系统中挂载外部名称空间需要的信息：（1）访问协议的名称；（2）服务器的名称；（3）外部名称空间中挂载点的名称。存在的问题：现有名称都发生变化；如果合并的名称空间太多将导致性能问题。n名称空间的分类（分层）：1. 全局层：由最高级的节点组成。特点：稳定，很少变化。2. 行政层：由在单个组织内一起被管理的目录节点组成。特点：相对稳定3. 管理层：由经常改变的节点组成。http:/ （2）不使用客户端缓存； （3）可以联系根服务器的地址是众所周知的。方

6、法一：迭代名称解析root:方法二：递归名称解析递归名称解析直接将结果发送给它找到的下一个名称服务器。内容内容迭代名称解析迭代名称解析递归名称解析递归名称解析通信开销大小缓存结果较有效非常有效 进行长距离通信时，迭代名称解析需要和服务器进行3次远程通信，而递归名称解析只需要进行一次远程通信和两次本地或近程通信，总开销大约是迭代名称解析的通信开销的1/3. 通信开销： 缓存结果： 由于全局层和行政层节点不会经常改变，所以名称服务器可以有效地缓存返回的地址。此外，由于地址也被递归返回负责实现vu节点以及nl节点的名称服务器，所以可以同时缓存地址。还可以缓存中间名称查询结果。 例如例如另一个用户后来

7、请求解析路径名另一个用户后来请求解析路径名root:root: 。该。该名称被传递名称被传递给根服给根服务器后，会被直接转发给用于务器后，会被直接转发给用于cscs节点的名称服务器，节点的名称服务器，并请求他解析剩下的名称。并请求他解析剩下的名称。1.DNS名称空间标识符：区分大小写的字符串，字符串由字母和数字组成。字符串的最大长度63个字符，完整的路径名最大长度255个字符。例：路径名root:DNS表示：flits.cs.vu.nl.（最后一个点通常省略）概念：域：子树域名：指向根节点的路径名（有绝对和相对之分）记录类型记录类型相关实体相关实体内容内容SOA（授权起点）区域文件的信息A（地

8、址）主机允许通信的主机所用的IP地址MX（邮件交换）域指向邮件服务器，该服务器处理发往该节点的邮件SRV域包含处理特定服务的服务器名称NS（名称服务器）区域包含一个服务器名称CNAME（规范名称）节点包含主机的规范名称或者说主名PTR（指针）主机维护IP地址到主机名称之间的反向映射HINFO（主机信息）主机存储所代表主机的信息TXT任意类型容纳任何被认为有用的、特定于实体的信息 节点的内容由一组资源记录组成。各种不同类型的资节点的内容由一组资源记录组成。各种不同类型的资源记录如下表所示：源记录如下表所示：2.DNS的实现DNS名称空间划分为：全局层和行政层。为了更好的理解实现方式，下图显示了一

9、个文件的部分内容：n命名命名/ /定位实体定位实体n简单方法简单方法n基于起始位置的方法基于起始位置的方法n层次方法层次方法创建分布式系统的目的是让人使用，同时实体也必须有地址，因而命名系统实质上都要维护易于理解的名称与地址之间的映射。为什么大型名称系统实现方式能够高效运行？例：更新ftp.cs.vu.nl的地址，假设名称不发生改变 （1）如果FTP服务器被转移到另一台机器上，且这台机器和cs.vu.nl同域。 那么更新地址只需要修改DNS数据库。由此看出，如果全局层和行政层节点不经常变化，更新限于一个服务器，就可以高效地实现DNS这样的命名系统。 （2）如果转移到名为ftp.cs.unisa

10、.edu.au的机器(不同域)上。假设ftp.cs.vu.nl不变，因为这个名称可能被作为标识符了。在ftp.cs.vu.nl的DNS数据库中记录新机器的地址；记录新机器的名称而不是它的地址，同时有效地把ftp.cs.vu.nl转化成一个符号连接。记录新机器的地址的缺点： 查询操作时不受影响，当再次把ftp.cs.vu.nl转移到另一台机器上时，必须同时更新它在cs.vu.nl所用DNS数据库中的项，但这种更新不再是本地操作，完成更新操作可能需要几百ms。违背了对管理层节点进行的操作是高效的假设。新机器的名称的缺点： 查询操作变得比较低效，每次查询都会被分成两步：（1）找到机器的名称；（2）查

11、找与该名称相关联的地址。另一个严重问题：名称不能改变出现问题的原因：命名服务维护着易于理解的名称与实体地址之间的直接映射。每当名称或地址发生变化时，映射也同样需要修改。解决方法：引入标识符来把命名实体与查找实体分开 在通过命名服务查找实体时，命名服务会返回一个标识符。 实体的定位由独立的定位服务处理。定位服务实际上是以标识符为输入，然后返回被表示实体的地址。假设这样一个分布式系统：它创建于一个能够提供高效广播功能的计算机网络之中。这种功能由局域网提供，在这种网络中所有的机器都链接在一根电缆上。原理：将包含该实体所用标识符的信息广播到每台机器上，并要求每台机器查看它是否拥有该实体。只有能够为该实

12、体提供访问点的机器才会发送回复信息，回复信息中包含访问点的地址。缺点：随着网络的扩大，广播变得低效。通过使用多播，只有符合条件的一组主机才能接受到请求。l多播组：符合条件的一组主机系统负责将信息发送给所有的组成员l多播地址的使用方式（1）用作对多播实体的通用定位服务（2）可以将多播地址与多个复制的实体相关联，并使用多播查找一个最近的副本（选择最先回复的复制实体）。原理：当实体从A移动到B时，它将在后面留下一个指针，这个指针指向它在B中的新位置。优点：简单，一旦找到实体以后，客户就可以顺着转发指针形成的链查找实体的当前地址。缺点：l 如果不采取特殊措施，那么链可能会特别长，以致定位实体的开销会很

13、变得很大。l 链中的所有中间位置必须维护转发指针链l 链很脆弱，容易断开按照SSP链的方法，每个转发指针都以（代理，骨架）对的形式实现。骨架要么包含实际对象的本地引用，要么包含该对象所用代理的本地引用。 为了简化（代理，骨架）值对组成的链，即缩短链，调用会携带一个代理的标识符，这个代理是调用开始的地方。当调用到达位于当前位置的对象以后，会向发起调用的代理反馈一个答复。答复包含了对象的当前位置信息，然后代理会把自己的对应骨架调整为对象当前位置中的那一个骨架.由于使用广播、多播和转发指针带来了可扩展性问题。且在大型网络中很难实现广播和多播，而过长的转发指针链会带来性能问题，并且容易受到链断开的影响

14、。为了解决这些问题，引入了起始位置的方法。这种方法持续跟踪实体的当前位置，可以使用特殊的技术来预防网络故障或进程失效。起始位置的选择：在实践中，通常选择创建实体的位置作为起始位置。 每个移动主机都是用固定的IP地址，所有与该IP地址通信一开始都被转发到移动主机的起始位置代理中。 缺点:(1)增加了通信延迟，因为需要先与起始位置进行联系； 保证起始位置始终存在，否则无法联系(2)使用了固定的起始位置 实体永久移动到一个其他网络，每次联系都经过起始位置在分层设计中，网络被划分为一组域。最底层的域称为叶域。每个域都拥有关联的目录节点，用来持续跟踪域的实体。顶级域的目录节点称为根节点，它包括全部实体。

15、为了持续跟踪实体的位置，每个目前位于域D中的实体都由一条在目录节点N内的位置记录来代表。位置记录包含该实体当前在域中的位置。根节点拥有每个实体的位置记录，其中每条位置记录都存储一个指向更低一层子域目录节点的指针。实体可以有多个地址，如果实体分别在域D1和D2中拥有地址，那么同时包含D1和D2的最小域的目录节点将包含两个指针，每个 指针都指向 一个包含地 址的子域。查询操作的实现查询操作是在局部进行的，查询区域可能逐步扩大，最坏的情况是搜索到达根节点。更新操作：插入和删除插入方式：高级域指向低级域、颠倒的顺序只有缓存数据很少发生变化时，采用缓存会变得很有效。假设移动实体E经常在域D中移动，那么E

16、的当前地址是经常改变的，但是有关E的信息不变的位置就是目录节点D。在D中而不是其他任何节点中查找E的当前位置有是有意义的，这种方法被称为指针缓存。原则上，从发起查询的叶节点开始，一路上经过的所有节点都可以缓存指向目录节点D的引用。目录节点D存储E的实际地址而不是E所在的子域的指针。查找步骤：（1）查询本地指针缓存,找到正确的目录节点.（2）要求这个节点返回E的当前地址。案例：用户在旧金山和洛杉矶之间移动如何找到最适合的目录节点来存储移动实体的当前地址？什么时候让缓存项失效？分层定位服务存在的一个主要问题是根节点需要存储所有实体的位置记录并为每个实体处理请求。如果不采取特殊技术，根节点需要处理太

17、多的查找和更新请求，以至于它会成为瓶颈。解决方案：把根节点以及其他高层目录节点划分成多个子节点，每个子节点负责处理与定位服务支持的所有实体的特定子集相关的请求。出现的问题：在定位服务覆盖的网络中，在物理上如何放置每个子节点？ 方案一：集中放置子节点，各个节点相互保持近距离，这就可以用一台并行计算机有效的实现根节点。 处理能力已经足够，但与根节点之间的网络连接可能没有足够的能力来处理全部请求。 方案二：把子节点均匀的扩散到网络中。 如果处理不当，这种方法有可能产生可扩展性问题。根节点已经被划分成多个子节点，现在需要解决的是如何分配合适的子节点负责该用户？一种可能的解决方案是使用创建实体一种可能的

18、解决方案是使用创建实体E E的位置，如果根节点的一个的位置，如果根节点的一个子节点与创建子节点与创建E E的位置很近，那么它就负责处理根一级的、与的位置很近，那么它就负责处理根一级的、与E E相关相关的请求。但仅适用于实体停留在离创建它的位置的请求。但仅适用于实体停留在离创建它的位置很近很近的情况，若的情况，若实实体体移动到很远的位置，那么问题还未得到解决。移动到很远的位置，那么问题还未得到解决。n无引用对象的问题无引用对象的问题n引用计数引用计数n引用列表引用列表n标识不可到达标识不可到达实体实体1.无引用对象的问题原因：如果一个实体不再被引用，若不删除就会浪费系统的资源。 在分布式系统中，

19、不能确定一个实体的引用是否存在，也不知道以后是否还会通过这个引用来访问这个实体。分布式提供了一种自动删除实体的功能：分布式垃圾收集器假设只要不存在远程引用的对象就应该在系统中删除；对象之间相互引用，导致对象循环引用，应该检测到这种现象并删除它们。可以用下图来表示这种情况：2.引用计数原理：创立对象引用时，用于该对象的引用计数就递增；在删除引用时，引用计数就递减，当计数为0就删除该对象。2.1简单的引用计数 在分布式系统中，这种方法产生的问题大多是由于通信的可靠性引起的。（假设对象把它的引用计数存储在关联的骨架中） 在创建引用和删除引用时可能产生的问题：确认信息丢失，代理会重新发送信息，导致计数

20、多加或减。 解决方案：检测重复信息，使用可靠的通信复制引用时产生的问题如图（a）解决方案如图（b），此外，在骨架确认它已经知道引用的存在之前禁止进程删除引用。传递引用现在需要三条信息，在大型分布式系统中很容易产生性能问题。2.2高级引用计数 简单的分布式引用在递增和递减引用计数之间造成了一种竞争状态。 改进：只采用递减操作 加权引用计数 原理：每个对象拥有一个固定的总权数，在创建对象时，总权数连同一个部分权数一起存储在与它关联的骨架中，部分权数被初始化成总权数。（假设信息不回丢失或多次发送）创建新的远程引用如图（b），复制远程引用如图（c）在删除引用时，一条递减消息被发送给对象的骨架，然后对象

21、的骨架会从总权数中减去被删除引用的部分权数。一旦总权数为0，就可以安全的删除对象。加权引用计数存在的问题：只能创建有限的引用数量。解决方案：使用间接权数使用间接权数的缺点：如果骨架S的总权数为1，那么这种方法与创建从进程P2到进程P1的转发指针相同。以此类推，如果需要传递它的引用，那么它必须创建另一个转发指针。当指针连链过长时会严重地降低性能，同时，指针链容易受到故障的影响。使用世代引用计数假定每个远程引用都由（代理，骨架）值对构成，骨架和对象位于相同的地址空间中。每个代理还存储着一个复制计数器和一个世代标志，复制计数器用来记录代理被复制的次数，世代标志代表的是世代数。3.引用列表原理：让骨架

22、持续跟踪引用它的代理，骨架不是对引用计进行数，而是维护一张明确的列表，列表中列出了所有指向它的代理。特征：如果一个代理被列出，那么把它添加到引用表中不会产生任何影响。删除列表中不存在的代理也不会产生任何影响。添加或删除代理都是幂等操作。幂等操作的特征是它们在不影响最终结果的情况下重复进行。优点：（1）不再需要可靠的通讯，也不需要检测和丢弃重复消息。（只需要对插入和删除操作进行确认）。 （2）进程发生故障时，更容易保持引用表的一致性。缺点：如果骨架需要跟踪很多引用的话，引用列表的规模可能会严重的扩张。4.标识不可到达实体 分布式系统中存在循环引用的情况，实体相互引用，但是它们无法从根集中的一个实体到达，这样的实体也要删除。基于跟踪的垃圾收集：通过查看哪些实体能够从根集实体到达并删除无法到达的实体。4.1简单跟踪跟踪方式：标记-清除收集器 标记阶段：使用源于根集实体的引用链对实体进行跟踪，能够到达的实体被作上标记。 清除