（计算机应用技术专业论文）基于改进的wordnet云计算存储资源搜索方法研究.pdf

天津师范大学硕士学位论文 摘要 随着网络技术的飞速发展，人们对于分布式计算的需求不断提高，新的计算 模式不断出现，“云计算 作为一种新兴的分布式计算模式，受到了人们的普遍 关注，但相关技术尚不成熟，无统一的标准，云计算存储资源中对象信息搜索关 键技术还没有具体的实现方案。 本文在分析了云计算存储结构组织方式的基础上，借助w o r d n e t 同义词集 进行语义上的聚类，并根据这种聚类的结果，实现根据关键字在存储资源中的快 速搜索。 本文提出了适于云计算环境的w o r d n e t 结构，将该结构分数据中心和用户 两级建立在云计算的存储结构上。应用w o r d n e t 对词语进行同义词聚类，利用 聚类结果，对云计算用户发出的搜索进行分析，查找语义上属于同义的存储对象 标签，达到获取存储对象资源信息的目的。 本文主要包括了以下几部分内容，第一章和第二章阐述了研究背景和涉及到 的相关技术；第三章提出了适于云计算的w o r d n e t 结构及实现方法；第四章给 出了利用w o r d n c t 结构按照语义的方法搜索云计算存储对象资源的具体实现。 本文对所提出的方法进行了仿真试验，测试了不同参数对于本搜索方法的影 响；与其他的分布式搜索方法在模拟环境下进行了比较，实验结果表明本文提出 的方法对于多用户、大数据量的分布式存储结构具有较好的效果。 关键字：云计算分布式存储w o r d n e t 结构同义词集 天津师范大学硕士学位论文 a b s t r a c t b yt h er a p i dd e v e l o p m e n to ft e c h n o l o g yo fn e t w o r k ，t h er e q u i r e m e n ta n di n t e r e s t o fp e o p l ef o c u so nd i s t r i b u t e dc o m p u t i n ga r eb l o o m i n g ，a n dm a n yn e w a p p r o a c h e so n t h i sk e e ps p r i n g i n gu p w i t ht h i st r e n d e n e y , c l o u dc o m p u t i n ge m e r g e su n d e rt h e c o m m o nc o n c e r no fp e o p l e t h e r ei sl a c ko fs o l m i o nr e l a t e dt o t e c h n o l o g yo f s e a r c h i n gs t o r a g eo b j e c ti n f o r m a t i o ni nc l o u d ，h o w e v e r , a n dn ou n i f i e ds t a n d a r dw a s b u i l d e du pa ts a m et i m e o nt h eb a s eo fa n a l y s i so fc l o u dc o m p u t i n gs t o r a g e ，i nt h i s p a p e r , u s i n g w o r d n e t ss y n o n y ms e tc l u s t e rt h es e m a n t i cs i m i l a r i t ya n da c h i e v ef a s t m a t c h i n g s e a r c hk e yr e t r i e v ei nc l o u ds t o r a g e w ep u r p o s ean e ww o r d n e ts t r u c t u r es u i tt oc l o u d c o m p u t i n ge n v i r o n m e n t ，i n t h i sp a p e r , b u l i du pt h i ss t r u c t u r eo nb o t hu s e rl e v e la n dd a t ac e n t e rl e v e li nc l o u d s t r o a g e w ea n a l y s i st h es e a r c hk e ya n dm a t c h i n gi tt h r o u g h ts y n o n y ms e t 谢ms e a r c h t a g sr e l a t e dt oo b j e c t , t h e na c h i e v ei n f o r m a t i o no fo b j e c ti nc l o u ds t o r a g e t h e r ea r ef o u rc h a p t e r si n t h i s p a p e r ：c h a p t e r 1a n d2r e v i e w e dt h es e a r c h b a c k g r o u n da n dr e l a t e dt e c h n o l o g i e s ，c h a p t e r3w ep u r p o s e dan e ww o r d n e t s t r u c t u r es u i tt oc l o u dc o m p u t i n ge n v i r o n m e n ta n dm e t h o dt oi m p l e t e di t ，c h a p t e r4 w es h o wh o wt ou s et h en e ww o r d n e ts t r u c t u r es e a r c h i n gc l o u dc o m p u t i n go 巧e c t b a s e do ns e m a n t i cs i m i l a r i t y w ed os o m ee x p e r i m e n to nt e s t i n gi n f l u e n c eo fm o d e lp a r a m e t e ri nd i f f e r e n t s c e n a r i oa n dc o m p a r et h i s a p p r o a c ht o o t h e rd i s t r i b u t e ds e a r c h i n gm e t h o do n s i m u l a t e dc l o u ds t o r a g e w ec a ng e tc o n c l u s i o nl i k e ：t h ea p p r o a c hw ed e s i g n e di s a v a i l a b l ew i t he x i s t e n c eo f h u g em o u n to fu s e ra n dd a t ai nd i s t r i b u t e ds t o r a g e s e a r c hk e y s ：c l o u dc o m p u t i n g , d i s t r i b u t e ds t o r a g e ，w o r d n e ts t m e t u r e ，s y n o n y ms e t 天津师范大学硕士学位论文 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得苤鲞竖芷盘堂或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 学位论文版权使用授权书 本入完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名： 。； 料| l 日期： 天津师范大学硕士学位论文 第一章云计算概述 1 1 云计算研究现状和概念 1 1 1 云计算研究现状 从2 0 0 3 年开始，m m 、s u n 、h p 等就陆续提供了像买电买水一样通过一个 网络购买计算力和存储空间的服务，这种潮流在2 0 0 6 - 2 0 0 7 年之间发生了质变， 随着最著名的畅销书销售网站a m a z o n 和i b m 、g o o g l e 先后推出了云计算服务， 云计算作为网格的升级实现产品已经在商业化的进程中阔步前行。 在目前各大公司各自为战的情况下，云计算尚无统一的标准，参考m m 提 出的云计算架构眩。表明云计算的目标在于使用互联网内看似无限的计算资源去 为使用者提供服务。这一点上，云计算得到了a m a z o n 、g o o o e 云计算产品的认 同。有了云计算的存在，使用者不再需要购买物理计算设备，并且陷于繁杂的配 置和维护计算设备的工作中，而是只需要为使用期间的费用支出。待使用结束后， 使用者归还或者租用期限到达之时，云计算系统收回计算资源待下一次分配使 用。 以i b m 蓝云为例，如图1 1 和1 2 所示。其中，x e n 是被选定的专门负责按 照用户要求动态配置服务器的虚拟化模型。当用户需要某种计算资源处理一些工 作的时候，只需要通过w e b 界面通过填写申请表的方式，声明自己计划什么时 候开始需要哪种类型的计算资源，并告知系统在什么期限结束使用即可。接下来 待申请得到批准后，用户就可以如期获得计算资源的使用权了。利用x e n 所创 建的虚拟机可以被用户删除和动态的添加，并且用户还被允许在虚拟机上运行自 己的程序。对于云计算中大量的虚拟机，i b m 使用t r v o l im o n i t o r i n g 程序来负 责监督收集云环境中的各种数据并定期对这些数据加以分析，以便了解云环境的 运行情况，实现对云环境的管理。被定期收集来的数据存放在d b 2 中，而d b 2 作为存放云环境监控数据的数据仓库。 天津师范大学硕士学位论文 圈圈困 p r o j e c tn a m e ： s t a t e ： s t a t u s ： r e q u e s td a t e ： s t a nd a t e ： e n dd a t e ： 工仳麻磔机和x c nv m 曰囡囡 1 1 2 云计算概念 围 囤囤回囤 l带x e n 的开放式源代码l i n u xl 供应管j ! j ! 堆拽 图1 1i b m 蓝云体系结构图 x ls o f t w a r e a c t i v e s e r v i c ep r o v i s i o nc o m p l e t e d 0 9 - - 1 0 2 0 0 7 0 6 1 3 2 0 0 7 0 2 - 0 5 - 2 0 0 8e ) ( t e n d t 0 ：严叫“ 回喇e n dc o n t r a c td a 协 图1 2 用户申请租赁i b m 蓝云资源的界面 li b m 给出了云计算的概念阴 “云”是一个虚拟化的计算机资源池，它可以：托管多种不同的工作负载， 包括成批的后端作业和面向用户的交互式应用程序；通过快速提供虚拟机器或物 理机器，迅速部署和增加工作负载：支持冗余、自我恢复且具有高可扩展性的编 程模型，以使工作负载能够从多种不可避免的硬件软件故障中进行恢复；实时 监控资源使用情况，在需要时重新平衡资源分配。 2w i k i p e d i a 的解释3 1 ： 云计算是一种随着计算机技术的发展和应用而成的互联网络。它是一种可 以动态伸缩，并且经常可以提供虚拟资源作为服务以供使用的互联网。使用者不 需要精通相关知识和能够驾驭基础结构。其中的架构、平台、软件都是作为服务 提供给用户。 3 归结结论 文献h 在研究了大量的关于云计算的定义之后，做出了这样的结论：虽然关 2 m 习匿 天津师范大学硕士学位论文 于云计算的很多定义各有特点，但是最终都归结于了两点：第一是定义了云计算 的可自由扩展性，第二是指出了云计算资源的虚拟化，即根据用户的需求自行配 制。文献侉1 在佐证了这一看法的同时，提出了商用化是云计算的一大主要特点， 可自由扩展并且按照用户的需求进行自由配置的资源包括：计算力、存储、平台 和服务。 1 2 网格与云计算的结构比较 作为网格计算阍阴的商用型产品，云计算产品的出现仿佛在一夜之间使还在 试验室中讨论的网格计算变得黯然失色。其实，云计算的基础是网格计算，只不 过在商用化的推动下，由于投资的大大增加，而提升了云计算的易用性和高集成 化。i a nf o s t e r 和他的研究小组在文献佑。全方面的比较了网格与云计算的各自特 点。他分别用图描述了网格计算和云计算的结构，如图1 3 和1 4 。 i a nf o s t e r 的研究中将在云计算出现以前已经有1 3 年之久的网格计算分为基 础设施( f a b r i c ) 、连接( c o n n e c t i v i t y ) 、资源( r e s o u r c e ) 、收集( c o l l e c t i v e ) 、 应用( a p p l i c a t i o n ) 五层。其中，基础设施层负责构建和维护网格计算赖以存在 的物理设备，由于网格计算出现的初衷是为了利用各个研究机构大量闲置的资源 以构成超级计算机去解决大量需要计算的科研数据，因此网格的基础设施主要是 分布在网格中各处的客户机、服务器等小型存储和计算设备。网格的连接层负责 制定协议使得在不同操作系统下并且呈分散状态的计算设备实现连接和通信。资 源层负责寻找和发现网格中的资源，以及对资源进行监督。收集层负责监督网格 内用户对于资源的取得和使用过程。应用层上建立了大量的应用程序用以实现不 同地理位置、操作系统、硬件配置的用户加入和使用网格资源。 比较网格计算的五层结构，i a nf o s t e r 同样将云计算的结构划分为四层，它 们自下而上是：基础设施( f a b r i c ) 、统一的资源( u n i f i e dr e s o u r c e ) 、平台 ( p l a n t f o r m ) 、应用( a p p l i c a t i o n ) 。云计算的基础设施层同样是负责构建和维护 网格计算赖以存在的物理设备基础，这其中既包括计算设备，也包括存储设备。 但稍有不同的是云计算的基础设施具有大量投资、统一购置的特点，因此在配制 和使用的操作系统上大致相仿。统一的资源层是为用户提供经过抽象化的统一格 式的计算资源和存储资源，比如：像虚拟机、逻辑文件系统等。平台层建立在统 3 天津师范大学硕士学位论文 一的资源层之上，目的提供一个开发和应用云资源的平台。应用程序层顾名思义 是所有可用的云计算应用程序的集合。 利用文献瞪中的比较，不难发现云计算首先在基础上更为一致。其次因为基 础设施的一致，减轻了开发协调不同平台、系统间通讯协议的负担。再有，云计 算可以为用户提供实时的计算资源，而不需要像网格那样需要在超级计算机使用 等待队列中，等待超级计算机的空闲。最后，云计算在应用程序上是建立在许多 已有的网络协议之上的，包括w s d l ，s o a p ，以及w e b 2 0 中像r e s t , r s s ，a j a x 等协议。而不需要像网格那样根据网格的a p i 去开发基于虚拟组织( v o ) 的应 用程序噶i 。 网 格 结 构 石 计 算 结 构 图1 3i a nf o s t e r 网格计算5 层结构图 图1 4i a nf o s t e r 云计算4 层结构图 4 天津师范大学硕士学位论文 1 3 云计算的存储 云计算中的存储结构同样没有统一的方式，但是既然云计算来自于网格嘲， 云计算的存储自然也就具备了分布式的特点，但同时许多云计算项目，包括： a m a z o n ，i b m ，g o o g l e 都为存储建立了多个数据中心，更是有商家投入了上百 万台的服务器，数据相比较p 2 p 分布在每个客户端的情况又稍有不同。因此， 云计算的存储具有分布式和集中式两者的特点。 1 3 1g o o g l ef i l es y s t e m 结构分析 g o o g l ef i l es y s t e m n 们文件系统g f s 以集群的概念出现，集群在形式上等同 于小型的数据中心。一个g f s 集群包含一个主服务器和多个块服务器，被多个 客户端访问，如图1 5 。文件被分割成固定尺寸的块。在每个块创建的时候，服 务器分配给它一个不变的、全球唯一的“位的块句柄对它进行标识。块服务器 把块作为l i n u x 文件保存在f i l es y s t e m 硬盘上，并根据指定的块句柄和字节范围 来读写块数据。为了保证可靠性，每个块都会复制到多个块服务器上。l i n u x 文 件系统( l i n u xf i l es y s t e m 也属于集群中的固定设备，而不是用户端的存储设备) ， 作为存储具体的块的物理介质。 数据信息 控制信息 图1 5g o o g l e 用于云计算服务的文件系统g f s 结构图 主服务器管理文件系统所有的元数据。这包括命名空间( n a r n e s p a c e ) ，访问 控制信息，文件到块的映射信息，以及块当前所在位置信息。它还管理系统范围 的活动，例如块租用管理，孤块的垃圾回收，以及块在块服务器间的移动。主服 务器用心跳信息周期地跟每个块服务器通讯，给他们以指示并收集他们的状态。 5 天津师范大学硕士学位论文 客户端跟主服务器交互进行元数据操作，但是所有的数据操作的通讯都是直 接针对块服务器进行的。 g f s 把文件切割成块存储在不同服务器上的做法，具有分布式的特点；同时， 由块服务器和集群主服务器分别管理块信息，对内对外提供文件元数据的做法具 有集中式的特点，这类似服务器客户端的结构中，客户端向服务器读取文件信 息。 1 3 2a m a z o ns 3 结构分析 a m a z o n ( 亚马逊) 的s 3 ( 简单存储服务) 1 1 j 是配合e c 2 ( 弹性计算云) 相应而生的文件存储服务，也是一个超大规模的存储系统，如图1 6 。s 3 中最基 本的存储单位为o b j e c t m ( 对象) ，o b j e c t 按照n a m e v a l u e 对的方式存在，逻辑上 放置在相关联的b u c k e t ( 桶) 中。对象的名，类似于文件系统中的文件名，对象 的值类似于文件系统的文件内容或文件数据。每个对象被分布存储在桶所在的数 据中心下的服务器中，通过具有高可靠性的d h t ( 分布式哈希表) 进行存储控 制n 2 1 。对象的大小范围在0 5 g b 之间，另外还可包括用于描述对象的0 - 4 k b 的 元数据。元数据又分为默认元数据和扩展元数据两部分。a i t l a t o n 没有规定用户 上传文件到s 3 的数量上限，但是对于桶的数目有小于等于1 0 0 的规定。对象名 需要按照a m a z o n 的全球命名空间( g l o b a ln a m e s p a c e ) 的要求，进行设定；命名 空间包括“桶名( b u c k e tn a m e ) ”和“对象名( o b j e c tn a m e ) 两部分 ，两部分结 合起来形成了文件名，如“s o m e b u c k e t f i l e d a t 。s 3 给每个桶和桶中每个文件分 配一个u r i 地址，因此a m a z o n 的用户可以通过h u p 或者h t t p s 协议进行访问。 目前尚无资料显示a m a z o n 是否像g o o g l ef i l es y s t e m 的主服务器和块服务器那 样，用专门的服务器去管理桶。桶的名字和文件名有从松散到严格的三级命名约 束，可参见阿。a m a z o n 的用户可以通过列表方式，看到自己建立的桶名，但其 余用户的桶和对象是对外保密的，除非该用户有公开它的愿望n 3 1 。 a m a z o n 的简单存储服务从管理对象以及对象的组织存放形式上类似于 g o o g l ef i l es y s t e m 的方式，即：对象数据上按照分布式的存储方式存放和读取， 对象的描述信息，包括：桶名、对象名、元数据、甚至是各对象的d h t 和起始 地址。这样有利于集中的管理对象，并且在数据存放上做到冗余适度、分布均匀。 6 天津师范大学硕士学位论文 篮 西 晶慨r 图1 6a m a z o ns 3 存储结构图 7 一少磊 天津师范大学硕士学位论文 第二章典型的分布式存储搜索算法和w o r d n e t 2 1 典型的分布式存储搜索算法 一个存储节点应该是分散在整个互联网上的存储系统，叫做分布式存储系统 ( d i s t r i b u t e ds t o r a g es y s t e m ：an e t w o r kf i l e s y s t e mw h o s es t o r a g en o d e sa le d i s p e r s e do v e rt h ei n t e r a c t ) 1 4 1 。 根据节点的拓扑方式不同也就是分散着的节点组成存储网络的方式不同和 资源在节点上的分布方式不同，在分布式搜索算法中有像泛洪式( f l o o d i n g ) 1 5 1 搜索、中心式搜索算法n 6 1 、p a s t r y 唧结构的搜索算法、c h o r d n 8 1 结构的搜索算法、 基于兴趣的聚类搜索算法等。其中，泛洪式搜索主要针对无结构化的分布式存储 系统使用，集中式搜索算法主要应用于存在一台或多台中央索引服务器的分布式 存储系统，p a s t r y 、c h o r d 主要针对高度结构化的分布式存储系统使用，而基于 兴趣的聚类搜索算法则不针对任何物理上的分布存储拓扑结构而言，它是针对存 储内容的某些概念进行分类的搜索算法。 2 1 1 中心式算法 使用集中式搜索的系统为集中式分布存储系统，其中存一个或者多个中央服 务器，存放其他节点共享资源的索引。这类似服务器一客户端( s e r v e r - c l i e n t ) 结 构中存储资源的服务器，负责存储、管理资源信息，但不同的是资源数据分布存 储在其他节点中。更不同的是，存放资源数据的节点可以自由的加入或者离开整 个分布式系统，并且不像服务器客户端结构那样，当服务器瘫痪的时候，造成 共享资源访问的中断。 集中式搜索的算法是这样执行搜索：当一个新的节点加入集中式分布存储系 统时，首先要向中央服务器传送自己所共享资源的一个索引。一个节点想要搜索 资源时，将带有所搜索资源的标识的搜索请求发送到中央服务器，中央服务器负 责检索资源索引，告知资源请求者拥存放信息的节点及路径。目前，典型的系统 有n a p s t e r l l 6 1 0 8 天津师范大学硕士学位论文 n a p s t c r 获取文件的三个步骤如图2 1 所示。首先，所有与中央服务器相连 的节点在想要获取文件的时候，要向中央服务器查询信息列表以确定位置，具体 的做法是向中央服务起发出p u s h 请求；此后，待请求得到满足后，中央服务器 向节点回发响应信息，将搜索信息所在的节点位置告知给搜索节点；最后，搜索 节点按照获得的信息，前往目标节点取得文件。 雕并器 厂气 p us f f lp o s x l o lo 节点l n 节点n u 节点2 ( a ) 用户使用p u s h 消息上载文件列表给服务器图 oo 节点1 o 节点n o 节点l 服务器 。 节点2 o 节点n 节点2 ( b ) 结点进行查询及请求响应( c ) 节点进行文件下载 图2 1n a p s t e r 获取文件流程图 中心式搜索算法优点是在存在中央服务器的分布式存储结构下，对系统内分 布资源的维护简单，发现效率高，速度快。由于资源的发现依赖中心化的目录系 统，发现算法灵活高效并能够实现复杂查询。缺点是与传统客户机朋艮务器结构 类似，容易出现因中央服务器瘫痪而造成的网络搜索的中断。 9 天津师范大学硕士学位论文 2 1 2 泛洪式算法 使用泛洪式( f l o o d i n g ) 搜索的分布式存储网络中，每个节点都不知道其他 节点的资源，彼此除了物理上的相连，不存在任何逻辑上的关系。因此，当某个 用户发出一个搜索之后，只能通过于与之相连的节点之间互相转发，来实现搜索。 泛洪式搜索的算法是这样执行搜索：搜索首先遍历发出查询节点的邻接点， 如果相邻节点含有这个资源，就返回一个查询命中( q u c r y h i t ) 信息给查询发出 者。如果它相邻的节点都没有包含这个被查询资源，然后再向下传播，在传播的 过程中采用宽度优先搜索方法( b f s ) 。泛洪式搜索典型的系统是g n u t e l l a n 9 1 。 g n u t e l l a 如图2 2 所示。为了限制泛洪式搜索在有限的时间内完成，因此按 照其它g n u t e l l a 中节点与搜索发出节点的跳数经过几次路由到达查询发出 节点，设定了t t l 变量，以约束查找的范围。设开始时t t l = 3 ，在离查询发出 节点跳数最近的n 个节点中进行查找，如果不能命中，则到跳数第二近的m 个 节点中进行查询，当每次不能命中查询资源的时候，传播一次1 几减1 ，如果 ”阻= o 时还没有搜索到资源，则停止。 搜索 i d = 1 兰玉 t ti = 3 - 匕 。 厂= 、 i i 匿f f d j u o 一 图2 2c m u t e l l a 采用的带兀l 控制的泛洪式搜索 泛洪式( f l o o d i n g ) 搜索的优点在于对于分布式存储网络的拓扑结构要求很 低，几乎任何分布式存储网络都可以使用该算法作为资源查询算法。其缺点是可 靠性差，对网络资源的消耗较大。 1 0 天津师范大学硕士学位论文 2 1 3c h o r d 算法 d h t 2 0 是分布式哈希表( d i s t r i b u t c dh a s ht a b l e s ) 的缩写。在n 个节点的 分布式网络中，假如想要做到让当每个节点都知道与它相邻的节点的所有情况的 时候，搜索的路由复杂度为o ( n ) ，这显然不符合搜索者想要快速得到信息的目 的。因此为了减少搜索时所需要的路由复杂度，利用h a s h 函数对节点标识关键 字进行h a s h 计算得到的n 位数值，能被按照数值的范围定位到与关键字对应的 资源存储节点中。以实现由每个节点只维护一小段路由表，整个网络的信息搜索 通过哈希计算和路由表交换来完成。 p u 困互 匦 图2 3d h t 在分布式存储中所处的位置 d h t 中每一条存储的表项由s t o r e ( k e y , v a l u e ) 组成，当查询和提取程序搜索 k e y 的时候，通过v a l u e = r e t r i v e ( k e y ) 取得。如图2 3 ，d h t 是分布式存储系统各 个节点存储信息和路由信息的抽象，分布式应用程序通过计算哈希值，与查询 d h t 表获得搜索目标的位置。 c h o r d 网络提供了应用d h t 实现通过计算便可存放和定位信息的分布式存 储范例。作为m i t ( 美国麻省理工学院) 的研究成果，c h o r d 以环状的结构将所 有该分布式存储系统中的节点编制进来。环上的每个节点赋予0 2n 。1 之间的一个 n 位地址，无论地址为2k ( 0 9 ) 的节点是否真实地存在，该地址都已经真实 的分配给了该真实虚拟节点。 按照d h t 的思想，c h o r d 中每个节点所负责维护的d h t 表( f i n g e r 表n 8 佗1 1 ) 的长度不超过n 个，查找每个信息所付出的路由代价为o ( 1 0 9 n ) 。c h o r d 为了解 决地址为2k ( 0g 固) 的节点实际上并不存在的问题，设置了s u c c e s s o r ( k ) 的概 念，表示离k 最近的一个地址在k 之后的真实存的节点，称为k 的后继节点 s u c c e s s o “k ) = ( n + 2 詹_ 1 ) m o d2 m ，1 冬k m 。 天津师范大学硕士学位论文 c h o r d 的搜索算法：c h o r d 中节点收到查找关键字k 的请求之后，首先检查 查询关键字k e y 是否落位于该节点标识和它的后继节点标识之间，如果是，则这 个后继节点就是存储 要查找的节点；否则，节点将查找它的f i n g e r 表，找到表中节点标识符最大但不超过k 的第一个节点，并将这个查询请求转 发给该节点。如图2 3 通过重复这个过程，找到k e y 的后继节点，即存储有 的节点，由该节点返回查询结果。 c hor d 实例 fing ert ab1ef orn o de10 start i1 1ter val s uc c l l 1 l ，l2 ) l2 1 2 12 ，l4 )12 1 4 r 1 4 ，2 ) 1 4 2 2 ，1 0 ) 2 图2 4 c h o r d 实例 c h o r d 的优点在考虑网络波动的最差情况下的设计与实现。由于每个结点的 度数尽量保持最小，这样需要响应的成员关系变化的维护可以比较小，从而可以 快速恢复网络波动造成的影响，仅需要o ( 1 0 9 2 n ) 的信息移动位置。缺点是由于 每个结点仅有少量路由状态造成发现算法的高延时，因为每一次查找需要联系多 个结点，在稳定的网络中这种思路是不必要的。并且，由于d h t 本身的精确性， 造成对于需要模糊查询的内容搜索效率大大下降。 2 1 4 基于兴趣的聚类算法 这种算法的出发点是从语义相近的角度对分布式存储网络中的节点进行聚 类，而非以往的按照哈希地址相近或者干脆就不对这些节点进行聚类。这种算法 的一个前提是认为相近兴趣的节点保存的内容和提交的查询也相近。因此，通过 聚类的方法，将兴趣度相近的节点组织起来，使得兴趣相近的节点相互联系，彼 此能都直接到达醐。这种兴趣网跟底层的实际网络无关，它只是在实际网络之 1 2 天津师范大学硕士学位论文 上的覆盖网，或成为重叠网( o v e r l a y n e t w o r k ) 。 基于兴趣的聚类搜索算法：设整个网络中包含的所有文档的集合为d ，d 包 含m 个不同的文档，即d = d 1 ，d 2 ，d m 。d 中所有文档的特征构成了特征集合f ， f 包含k 个特征，即f = f 1 ，最，氩 。文档d i d ，可以用向量表示为 d i = ( w i i ，w l i ，, w i k ) ，其中w i i ( 1 匀曼k ) 为文档d i 的第j 个特征的数值表示。假设 文档集合d 中的文档由k 维向量表示，通过比较这些向量在k 维笛卡儿空间中 夹角的余弦值，可以衡量这两个向量对应的文档向量的接近程度，即两个文档在 语义上的相似度。夹角越小，文档相似度越高；夹角越大，文档相似度越低。图 - - 1 ) 斗 4 5 为一个两维向量空间的示例。文档d l 和d 2 对应的文档向量分别为d l j f l d 2 ，其 ， ， 斗 中d l = ( w 1 1 ，w 1 工) ，d 2 = ( w 2 1 ，w 2 2 ) ，d l t ：1 d 2 之间的夹角为a 。 w i 2 属 蒜 w 1 工 l w 2 1 w i 1 f 7 ) 图2 5 两维向量空同夹角不例图 文档的相似程度通过计算两个文档向量之间夹角的余弦值得出倥3 1 洲。如图 - - i i , 2 5 ：假设两个文档d i 和d j ，对应的文档向量分别为d i 和d j ，d i = ( w i 1 ，w i 厶，w i 0 ， 斗斗斗 d j 气w i 1 ，w i 如，w i j , ) ，则d i 和d j 之间夹角的余弦值计算公式如公式2 1 所示。为一 个两维向量空间的示例。文档d 1 和d 2 对应的文档向量分别为d i 和d 2 ，其中d i = ( w 1 1 ， w l 工) ，d 2 = ( w 2 1 ，w 2 上) ，d l 和d 2 之间的夹角为a 。 ( w ，w ) c o s ( 口孑，孑，) 2 ( 2 1 ) 天津师范大学硕士学位论文 基于兴趣的聚类搜索算法的优点在于能够通过将“有共同兴趣”的节点聚集 在一起而对与该兴趣有关的关键字进行搜索的时候获得更高的准确性和效率。缺 点是，两个对象间兴趣的计算很大程度上依赖关键字空间，也就是文档特征集合 f = f i ，最，& 中每一个丘( 0s 殴) 的选择；此外对于大量的关键字存在的时候， 计算文档兴趣的工作量会大大增大，从而影响资源的搜索用时。 2 2w o r d n e t 概述 由g e o r g ea m i l l e r 以及他领导的普林斯顿实验室从1 9 8 5 年开始提出了基于 认知语言学原理按照英文中词语的语义相似关系，利用树形结构将同语义英文词 语组织在一起，并使其形成结构化的英文词典w o r d n e t l 2 5 1 。w o r d n e t 发展到现在 已经网罗了包含名词 2 6 1 、动词、形容词、副词在内的超过1 2 万组同义词( 夥n o n y m y n e t s ，简称s y n s e t s ) 的英文词语集合。 w b r d n e t 研究的最小对象是词语，组成词典的最小单位是同义词集。比如在 w o r d n e t 词典中，b a r g e 和f l a t b o a t 表示同一个意思“驳船、用于货运的平底船”， 那么他们就是同义词，用集合 b a r g e ，f l a t b o a t 表示。 w o r d n e t 的设计者将英语的词语源文件( l e x i c a ls o u r c ef i l e s ) 编制成了由索 引和数据文件组成，并且包含同义词集间相互关系的w o r d n e td a t a b a s e ，以供开 发者作为库文件的形式使用，如图2 6 。结构化的w o r d n e t 库文件是w o r d n e t 的 核心部分，任何基于w o r d n e t 对词语的归类、建立词语之间的相互关系、以及 开发应用，都是建立在p o s i d x 和p o s d a t 文件的基础上。这两个文件中每条记录 的格式如下： 索引文件p o s i d x 中每条记录的格式： 文件格式( f o r m a t ) l e m m a p o ss y n s e t _ c n tpe n t p 仃s y m b o l 】s e n s e c n tt a g s e n s ee n ts y n s e t _ o f f s e t 【s y r m e to f f s e t 】 文件格式实例( f o r m a te x a m p l e ) t r e en35 一拌m s p311 1 0 3 7 9 0 01 1 7 3 8 3 1 00 9 3 2 1 1 4 8 数据文件p o s d a t 中每条记录的格式： 文件格式( f o r m a t ) 1 4 天津师范大学硕士学位论文 s y l l s e t _ o f f s e tl e x f i l e n u ms s _ t y p ew _ c n tw o r dl e x _ i d 【w o r dl 饮_ i d 】p _ c n tp t r 】【f l a m e s 】 文件格式实例( f o r m a t _ e x a m p l e ) 0 2 6 3 4 9 0 10 61 10 1c h r i s t m a s t r e e00 0 1 0 2 7 5 9 6 9 9n0 0 0 0ia no r n a m e n t e d e v e r g r e e nu s e d 嬲ac h r i s t m a sd e c o r a t i o n 图2 6w o r d n e t 生成及应用示意图 单就英文中的名词面言，同意词集之间存在同义关系( s y n o n y m y ) 、反义关 系( a n t o n y m y ) 、上位关系( h y p e m y m ) 、下位关系( h y p o n y m y ) 、整体关系 ( h o l o n y m ) 、部分关系( m e r o n y m ) 旺5 1 鲫。w o r d n e t 将名词划分为2 5 个基本类 别( 2 5u n i q u eb e g i n n e r s ) ，如表2 1 所示。 表2 1w o r d n e t 名词基本类别 a c t , a c t i o n , n a t u r a l a c t i v i t y n a t u r a lo b j e c t a n i m a l ，f a u n a a r t i f a c t p h e n o m e n o n p e r s o n , h u m a n b e i n g a t t r i b u t e ，p r o p e r t yp l a n t , f l o r ab o d y , c o r p u sp o s s e s s i o n c o g n i t i o n , k n o w l e d g e p r o c e s s c o m m u p 3 c a t i o n q u a n t i t y , a m o u n te v e n t , h a p p e n i n g r e l a t i o n f c c l m g ，e m o t i o ns h a p e f o o d s t a t e ，c o n d i t i o n g r o u p , c o l l e c t i o n s u b s t a n c e l o c a t i o n , p l a c e t i m em o t i v e 1 5 天津师范大学硕士学位论文 w o r d n e t 将这2 5 个基本类别，用1 1 棵名词分类树组织起来，如图2 7 。 自然现象 n a n u r a lp h e n o m a n o n p r o c e s s 状态s t o l e 行动a c t i v i t y 事件e v e n f 团体g r o u p 处所l o c a t i o n 所有物p o s s e s s i o n 外型s h o p e a b s t r a c t i o n 抽象物 7 心、 a t t r i b u t eq u a n t i t yr e l a t i o nt i m e c o m m u n i c a t i o n p s y c h o lf e a t u r e 心理特征 c o g n i t i o n f e e l i n g m o t i c a t i o n e n n t y 买体 0 r g a n i c m f 刀 a n i m a lp e r s o np l a n ta r t i f a c ts u b s t a n c e n a t u r a lo b j e c t 图2 7w o r d n e t 分类名词示意图 f o o d b o d y 天津师范大学硕士学位论文 第三章w o r d n e t 概述 3 1 对云计算存储的搜索定位 本文中所设计的基于改进的w o r d n e t 结构对云计算存储对象资源得搜索方 法严格遵从了云计算只提供给付费用户的思想，将搜索的范围定位在有权使用云 计算的用户对于云存储资源的搜索，搜索的范围不包含自己所拥有的对象文件， 因为以a m a z o ns 3 为例，用户可以列出自己的所有桶内的文件。搜索结果的返 回是命中对象的描述信息，这也是为了保护云计算用户对于自己上传文件的私 有。本文所研究搜索方法时，以a m a z o ns 3 的存储结构和标准为主要参照。 在a m a z o n8 3 中，描述云存储资源特征的数据包含对象名和元数据。尽管 对象名类似于文件名，但由于对象名只能存在一个并且有可能是包含多重信息的 短语，而从包含不同信息的词组当中抽取关键字又存在误差。文献陉引提出按照 o n t o l o g i e s 规则集使用元数据在解决g i s 中存在词语语义多样性的一系列方法， 显示了不同类型的元数据在于描述数据本身的强大作用。同样，文献陀9 1 中作者 提到，当搜索的目标是文件的描述或者索引信息，元数据比其它的信息更有用。 因此，元数据中留给用户的空间更为广阔，这不仅是因为最多可以使用4 k b 的 数据去描述一个对象，而且对于元数据在完成存储系统所必需的信息收集默 认元数据写入( 如对象创建的时间、用户名等) 之外，还有留给用户没有限制范 围的扩展元数据去描述s 3 对象各种各样的特点。利用这部分空间为存储对象添 加搜索标签，之后形成的云计算存储对象正是本文所研究的对象。 凡是使用过r a p i d s h a r e 或是r a y f i l e 的用户都有这样的印象，在上传文件到 该网络存储系统的时候，都会被允许添加搜索标签( s e a r c ht a g s )