（计算机应用技术专业论文）分布式存储系统中的资源定位与数据存储技术研究.pdf

摘要 在计算机网络中存在着大量空闲的存储资源，例如台式机、服务器、工作站等。虽然这 些节点的计算与存储能力各异，但都可以向其他节点提供一定的共享存储空间，并且这些节 点也可能成为共享资源的访问者。分布式存储系统为了有效组织这些：符点，并合理利用节点 的资源，需要考虑节点异构性与连接异构性。 节点异构性是指节点的存储能力各异，存储空间多的节点应当适当分担更多的负载，并 且数据存储策略应当考虑到节点的负载状况，并动态判断和选择合适的节点存储。连接异构 性是指节点之间的连接耗费不同。同一实验室中的两个节点传输数据比起不同城市之间的两 个节点传输数据要更加快速，因此在存储系统中对数据访问时，应尽量避免通过高耗费的连 接进行，优先在本地相近节点中访问数据。 本文针对上述问题，基于结构化p 2 p 系统中d h t 技术所提供的资源定位功能，设计一 个分布式存储系统，向用户提供面向文件的存储与读取服务。该存储系统所基于的d h t 协 议c y c o r d ，利用c c c 图的拓扑特征对节点进行组织，首先将：霄点组成本地圈再将本地圈连 接在一起，以方便区分节点之间低耗费的本地连接与高耗费的远程连接。利用此特性，在 d h t 路由协议、关键字分配的动态负载均衡、文件裂片存储位置选择的动态负载均衡、文 件裂片索引冗余存储等方面都尽量减少通过远程连接的数据传输，提高网络资源的利用效 率。 本文的主要贡献有： ( 1 ) 基于c c c 图和d h t 协议，设计了一个新的资源定位协议c y c o r d 。理论与实验数据的分 析比较说明，在条件2 l 1 ) ，一次请求经过的本地连 接与远程连接的跳数分别为l 和r ，则总的耗费c o s t = l + r 入。 2 3 2 性能理论分析 在系统容量相同，节点数相同的情况下，由于c y c o r d 的本地圈的数目不大于c h o r d 中 的节点数目( 因为每个本地圈至少包含一个节点) ，所以c y c o r d 的远程连接跳数是小于c h o r d 的( 由于c h o r d 中连接无远程与本地的区别，统一看作远程连接) 。另外，当每个本地罔只 含一个节点时，c y c o r d 协议等同予c h o r d 协议。 定理：当每个小圈平均含m 个节点时，c y c o r d 协议的一次查询经历的远程连接数小于c h o r d 1 0 第二章c y c o r d 协议的设计和分析 协议，差值为( i 0 9 2 m ) 2 。 证明： 根据c h o r d 已有的结论，c h o r d 平均查询跳数为( 1 0 9 2 n ) 2 ，其中1 1 为系统节点数量。而 c y e o r d 中小圈的数目为n m ，其平均查询远程跳数奠j ( 1 0 9 2 ( r d m ) ) 2 ，所以差值为( i 0 9 2 m ) 2 。 推论：对于平均每小圈含m 个节点，且连接异构因子为入的c y c o r d 系统，当平均本地跳数 1 满足2 l 入水( 1 0 9 2 m ) 时，其平均请求耗费小于相同节点数的c h o r d 系统。 证明： 假设节点数1 1 ，每个小圈平均含m 个节点，连接异构因子入。 c h o r d 的请求平均耗费： c o s t c h o r d = ( 1 0 9 2 n ) 2 【( 1 一m n ) 入+ m n 】， c y e o r d 请求平均耗费： c o s t c v c o r d = ( 1 0 9 2 ( n m ) ) 2 a + l l ，( 爹 其中l 为平均本地跳数。当m n 时，c h o r d 的平均一跳的耗费约等于入，则由 c o s t c v c o a d m ，( 2 1 0 9 2 m ) 当同时进行第一阶段和第二阶段的优化时，本地跳l = 1 ，带入公式中，可得 入 2 ( 1 0 9 2 m ) 由上结论可以看出，对于连接异构因子入来说，存在这样一个阙值，当入大于这个值 时。c y c o r d 协议比c h o r d 协议具有更低的查询耗费；当入d , - t - 这+ 值时，c y c o r d 协议比c h o r d 协议具有更高的查询耗费。设该值为入o ，由公式和公式可得，对c y c o r d 查询协议第一 阶段进行优化后，入o = m ( 2 l 0 9 2 m ) ；对c y c o r d 查询协议第一阶段和第二阶段都进行优化后， 入o = 2 ( i 0 9 2 m ) ，其中m 表示本地罔中节点数。 图2 6 连接异构因子阈值 图2 6 说明连接异构因子阈值随本地圈中节点数m 的变化趋势。其中，折线以上部分 的区域表示c y c o r d 协议查询耗费优于c h o r d 协议的情况。可以看出： ( 1 ) 只对c y c o r d 查询第一阶段进行优化时，连接异构因子闽值随m 增人而增人：当m 为4 或者更低的值时，c y c o r d 比起c h o r d 更优；但随着m 的增加，需要更人的连接异构因 子，来保证c y c o r d 比c h o r d 具有更低的查询耗费。 ( 2 ) 同时对c y c o r d 查询第一与第二阶段进行优化时，由于连接异构因子大于l ，所以当m = 4 时，c y c o r d 协议将必然比c h o r d 协议拥有更低的查询耗费。 1 4 第二章c y c o r d 协议的设计和分析 2 6c y c o r d 查询的负载均衡 2 6 1 结构化p 2 p 系统的负载均衡 d h t 协议的一个重要特征是，关键字在各个节点间达到自然的均衡，这是由于节点的 标识往往通过哈希获得所以节点比较均匀的分散于关键字空间中。但是这只是在节点同构 ( 即各个节点所拥有资源的量相近) 的假设基础上的，即使在这种情况下，随机选择节点标 识依然会产生一定程度的不均衡( o ( i o g n ) ) 2 2 】【2 3 】。 有研究人员使用虚拟服务器( v i r t u a ls e r v e r ) 【1 7 】【2 6 】【3 5 】的方法