分布式系统之6、命名2.ppt

命名（2）,内容,实体的命名移动实体的定位无引用实体的删除,二、移动实体的定位,1、实体的移动与定位,问题：如果实体发生了移动，该如何用名称重新定位它呢（管理层的节点经常变化）？传统的名称服务系统：维护着人性化的名称与实体地址之间的直接映射。每当名称或者地址发生改变时，映射也就需要修改。,实体的移动与定位,两种解决方式：在名称数据库中记录新机器的地址。记录新机器的名称，并把原名称转化为一个符号链接。问题：第一种方式：整个名称系统中有多台不同层次的服务器存储映射，更新效率低。第二种方式：查询操作低效。对于高移动性实体，问题尤其严重。,实体的移动与定位,解决传统方式的问题所在：名称与地址直接映射，实体位置变化时，映射必须变化。解决方法：通过标识符来把命名实体和查找实体分开来。标识符表达方式不便于人记忆与理解将实体名称与实体位置彻底分离,名称与地址间的映射（a）名称与地址之间的直接（一级）映射（b）使用标识符的两级映射,实体的移动与定位,引入标识符的二级映射后，实体定位需要两种服务：命名服务：返回标识符定位服务：以标识符为输入，返回实体位置（地址）与一级映射的区别如何定位移动实体？,2、实体定位广播,最简单的方式广播广播实体ID（标识符），所有接受者检查自己是否是该实体，若是，则响应一个带其地址的消息。无法跨越广播域需要所有进程监听,实体定位指针转发,指针转发：每次实体移动时，留下一个指针告知其去向。实现简单方便移动细节对客户透明：顺指针链即可找到实体链有可能会特别长所有中间位置都必须额外维持一个转发链的脆弱性,使用代理、骨架值对的转发指针,实体定位基于起始位置的方法,广播和指针转发的共同问题：可扩展问题基于起始位置的方法：由起始位置（一般是实体创建位置）持续跟踪实体的当前地址。实体的起始位置需要在命名服务中注册。起始位置需要包含实体移动的外部地址的注册。客户先与起始位置联系，然后与实体所在外部位置通信。,实体定位基于起始位置的方法,基本过程：当一台主机移动到另一个网络时，它在当地请求一个称为转交地址的临时通信地址，转交地址在起始位置代理中注册。当起始位置代理收到发给移动主机的数据包时，如果发现主机在本地，则简单转发，如果不在，则根据注册的转交地址建立一个到主机的当前位置的信道，把数据发给转交地址。,移动IP原理,实体定位基于起始位置的方法,缺点：通信延迟：客户为了与移动实体通信，必须首先与起始位置建立联系，而起始位置与移动实体本身处于完全不同的位置。必须保证起始位置始终存在。地理上的可扩展性和伸缩性太差。客户有可能与移动实体地理相邻，但需要访问起始位置定位实体。,实体定位分层方法,基本思想：建立一棵大规模的搜索树，基于这棵树，底层网络被划分为层次化的域。每个域在搜索树中都表示为一个目录节点。它记录所有它包含的实体位置。每个叶子域关联到一个局域网或者一个通信小区。根节点（根域或顶级域）包含所有实体。每个实体在其当前所在域中有一条位置记录，该记录即为其当前地址或指针。,分层方法组织原理图,实体定位分层方法,实体的地址存储于叶节点或临时节点中。如果一个实体被复制了，则有可能有多个地址。基本定位原理：首先在本地叶节点中查找目标实体如果找到，则直接定位如果未找到，则返回到父节点如果父节点包含目标，则可定位，否则返回再上一层父节点向上可回溯到根节点,分层方法存储原理图,分层方法中实体的查找,指针缓存：实体在一个最小域D中规律移动，则缓存D的引用。,实体定位分层方法,分层方法的缺点？思考,三、无引用实体的删除,1、分布式垃圾的问题,实体不再被访问引用，资源不再可用，需要删除分布式系统中，垃圾回收困难分布式存储分布式引用。如果实体删除，而引用没有删除，则引起访问错误。分布式系统基于网络，系统的扩展性和有效性，以及网络通信的失败都会引发回收故障。,2、无引用对象问题,远程对象：通过（代理，骨架）对引用。客户端的代理关联到服务器端的骨架。当没有客户端引用一个远程对象时，即在系统中不再存在客户端代理，该对象就失去了存在的意义。,无引用对象问题,删除无引用的对象，需要知道什么时候一个对象不再被引用。环形引用的问题。谁负责删除。由（代理，骨架）对回收，对客户与对象透明。使用引用图表示远程对象引用关系，每个节点代表一个对象。,对象引用图,3、引用计数,思想：每次客户端创建（移除）一个对象的引用，对一个对象本地（即骨架端）的一个计数增一（减一）。,引用计数,问题一：消息丢失增一消息丢失，对象被提前移除，导致客户无法使用对象重复增一消息减一消息丢失，导致对象无法删除确认消息丢失，增/减一消息重发,不可靠通信引起引用计数消息丢失问题,引用计数,问题二：引用复制进程P1向P2传递了一个引用，对象不知道。P1此时删除其自己对对象的引用，将可能导致对象的删除。如果对象被删除，则P2的引用将无效。解决方法：P1通知对象，告知将向P2复制引用，未收到确认前，P1不允许删除引用。对象向P2确认引用并注册。P1可以删除引用。,a：简单向其他进程复制引用b：解决方法,4、引用列表,引用列表：对象骨架维持一张明确的列表，列出引用它的代理。特征：如果一个代理已经列出，再添加不会产生任何影响。删除列表中不存在的代理也不会产生任何影响。添加和删除都称为幂等操作。,引用列表,引用列表优点：添加新引用的时候，创建进程可以重复向服务器发送添加请求。引用删除的消息同样允许重复。不再需要可靠通信。缺点：引用列表的规模JavaRMI使用引用列表,5、标识不可达实体,不可达实体：相互引用从根集不可到达与单纯无引用实体区别需要跟踪机制简单跟踪机制检查所有能从根集到达的实体，把其他的移除。标记清除收集器,标识不可达实体,标记清除收集器标记阶段：从根集开始，顺着引用链，将链上所有实体都做标记。清除阶段：对系统存储检查，将未标记的实体清除。,标识不可达实体,标记清除收集器的分布式实现每个进程P启动一个本地垃圾收集器，所有收集器并行工作。对骨架、代理和实际对象都着色。三种颜色：白、灰、黑。初始颜色是白色。P进程所能到达的对象标记为灰色。当一个对象标记为灰色时，对其包含的所有代理也标记为灰色。与代理关联的骨架也标记灰色。进而把骨架对应的被引用对象标记为灰色。当所有的代理为灰色时，对