基于DHT分布式云存储系统综述

《基于DHT分布式云存储系统综述》由会员分享，可在线阅读，更多相关《基于DHT分布式云存储系统综述（7页珍藏版）》请在金锄头文库上搜索。

1、基于 DHT 的分布式云存储系统综述题目： 基于云计算的知识管理综述专业：计算机应用技术年级： 2014 级学号： 2014303100 姓名：静水流云上海大学信息工程学院2014 年 12 月 28 日基于 DHT 的分布式云存储系统的综述摘要： 随着信息爆炸式的增长，集中式的存储方式的瓶颈效应愈发明显的遏制了数据存储的扩展性和并 发访问的效率等，SAN 和 NAS 等传统集中式存储系统越来越难以满足海量数据存储的需要。为了解决诸 如此类的传统存储的瓶颈问题，分布式存储系统和云存储系统相继被提出，并成为学术研究和商用的热点 内容。分布式存储系统实现涉及并使用的技术有很多，本文主要介绍基于DH

2、T的分布式存储系统，重点在 搜索技术方面。1 引言把用户的文件分片后均衡存储在不同的分布式存储节点上，并利用虚拟目录服务器和基于P2P DHT 的目录服务器把文件元数据与文件数据片高效地对应起来，以提供高效目录服务，分布式存储节点以P2P 方式工作以快速完成用户对文件数据的请求任务。分布式网络存储系统DNSS 充分利用了DHT原理和 P2P 的搜索技术优势 3 ，有较高的可用性、可靠性和可扩展性。P2P技术突破了传统的CS架构的模式，具 有非常好的扩展性，但存在安全性、可控性问题2 。利用 DHT的资源管理优势和P2P的高扩展性，可以 构建一个在全互联网范围内使用的可靠高效的海量分布式存储系统

3、。而对于海量数据的分布式存储，主要 涉及的技术问题是如何处理好数据的添加、删除以及最为重要的查找效率，本文结合分布式hash 表的一 致特性，重点讲述一下如何构造一个基于DHT的分布式存储系统，当然主要内容是DHT原理部分 1 。2 p2p网络和 hash函数概述2.1 p2p 网络简介p2p 网络又称工作组，网上各台计算机有相同的功能，无主从之分，一台计算机都是既可作为服务器， 设定共享资源供网络中其他计算机所使用，又可以作为工作站，没有专用的服务器，也没有专用的工作站。 在 P2P网络环境中，成千上万台彼此连接的计算机都处于对等的地位，整个网络一般来说不依赖专用的集 中服务器。网络中的每一

4、台计算机既能充当网络服务的请求者，又对其它计算机的请求作出响应，提供资 源和服务。其主要分为两种：非结构化p2p 网络和结构化p2p 网络 4 。前者有网络拓扑是任意的、内容 的存储位置与网络拓扑无关的特点；后者网络拓扑结构是有规律的，每个节点都随机生成一个标识(ID) ， 内容的存储位置与网络拓扑相关，内容的存储位置与节点标识之间存在着映射关系。2.2 hash 函数简介Hash 函数可以根据给定的一段任意长的消息计算出一个固定长度的比特串，通常称为消息摘要（MD ： Message Digest ），一般用于消息的完整性检验。Hash函数有以下特性：给定 P ，易于计算出 MD （P）只给

5、出 MD（P），几乎无法找出 P 无法找到两条具有同样消息摘要的不同消息Hash 函数 MD5 ：消息摘要 长度固定为 128 比特； SHA-1：消息摘要长度固定为160 比特。 Hash 函数应用于 P2P的特性唯一性：不同 的输入明文，对应着不同的输出摘要将节点IP 地址的摘要作为节点ID，保证了节点ID 在 P2P环境下的 唯一性 SHA-1(“202.38.64.1 ”) =24b92cb1d2b81a47472a93d06af3d85a42e463ea。3 DHT原理3.1 DHT 简述DHT(Distributed Hash Table，分布式哈希表)算法就是使用分布式哈希函数来

6、解决结构化的分布式存储问题 1 。分布式哈希表实际上是一张散列表，每个节点被分配给一个属于自己的散列块，并成为这 个散列块的管理者。目前，典型的DHT协议包括美国MIT 的 Chord、UC Berkeley 的 pastry和 CAN 、纽约 大学的 Kademlia 2。本文主要介绍chord 和 pastry 。将内容索引抽象为 对 K是内容关键字的 Hash 摘要 K = Hash(key)V是存放内容的实际位置，例如节点IP 地址等所有的 对组成一张大的 Hash 表，因此该表存储了所有内容的信息每个节点都随机生成一个标识(ID) ，把 Hash 表分割成许多小块， 按特定规则 (

7、即 K和节点 ID 之间的映射关系 ) 分布到网络中去，节点按这个规则在应用层上形成一个结构 化的重叠网络给定查询内容的K 值，可以根据K 和节点 ID 之间的映射关系在重叠网络上找到相应的V 值，从而获得存储文件的节点IP 地址，如图 1 所示。将分割的hash 表按一定的规则分配到p2p 网络的个节点 上，如图 2 所示。图 1 hash 表图 2 hash 表分布图3.2DHT 搜索原理DHT搜索技术主要涉及定位和路由两部分：定位(Locating)节点 ID 和其存放的 对中的 K 存在 着映射关系，因此可以由K 获得存放该 对的节点 ID 路由 (Routing)在重叠网上根据节点I

8、D 进行路 由，将查询消息最终发送到目的节点。每个节点需要有到其邻近节点的路由信息，包括节点ID、IP 等网 络拓扑拓扑结构由节点ID 和其存放的 对中的 K之间的映射关系决定拓扑动态变化，需要处理节点 加入 / 退出 / 失效的情况，如图2 所示。4 Chord和 Pastry分布式存储系统4.1Chord环原理4.1.1Hash表分布规则Hash节点 ( 例如 IP 地址 ) m位节点 ID( 表示为 NID)，Hash内容关键字 m位 K(表示为 KID) 节点按 ID 从小到大顺序排列在一个逻辑环上，由 对组成的hash 表存储在该节点后继节点上。Lookup(K) ： 从 K 开始顺

9、时针方向距离K 最近的节点，如图3 Chord 环结构图所示。图 3 Chord 环结构图4.1.2 Chord环简单查询过程每个节点仅维护其后继节点ID、IP 地址等信息查询消息通过后继节点指针在圆环上传递直到查询消 息中包含的 K 落在某节点 ID 和它的后继节点ID 之间速度太慢 O(N) ，N为网络中节点数 5 。如果建立查 询指针表，将该节点临近节点的hash 值作为指针存储在节点上，则可大大降低查询时间，如图4 Chord 环查询图所示。图 4 Chord 环查询过程图节点加入：新节点N 事先知道某个或者某些结点，并且通过这些节点初始化自己的指针表，也就是 说，新节点 N 将要求已

10、知的系统中某节点为它查找指针表中的各个表项在其它节点运行探测协议后，新 节点 N将被反映到相关节点的指针表和后继节点指针中新结点N的第一个后继结点将其维护的小于N节点 的 ID 的所有 K 交给该节点维护。节点退出 / 失效：当 Chord 中某个结点 M退出 / 失效时，所有在指针表中包含该结点的结点将相应指 针指向大于 M结点 ID 的第一个有效结点即节点M的后继节点为了保证节点M的退出 / 失效不影响系统中正 在进行的查询过程，每个Chord 节点都维护一张包括r 个最近后继节点的后继列表。如果某个节点注意到 它的后继节点失效了，它就用其后继列表中第一个正常节点替换失效节点4.2Past

11、ry原理英国剑桥 Microsoft研究院和 Rice 大学共同提出考虑网络的本地性, 解决物理网络和逻辑网络的拓扑失配的问题基于应用层定义的邻近性度量,例如 IP 路由跳数、地理距离、往返延时等节点ID 分布采用环 形结构 5 。4.2.1节点维护状态表路由表 R：路由表包括 log2b N (m/b)行，每行包括2b -1个表项路由表第 n 行与节点 ID 的前 n 个 数位相同，但是第n+1 个数位不同，也称为n 数位前缀相同路由表中的每项包含节点ID，IP 地址等根据邻近性度量选择距离本节点近的节点 邻居节点集 M ：邻居节点集包含|M| 个在邻近性度量上最接近于本节点的节点，|M|

12、为 2b 或者 2X2b , 邻近性度量指的是物理上相邻节点邻居节点集通常不用于路由查询消息，而是用来维护本地性 叶子节点集 L：叶子节点集包含|L| 个节点 ID 最接近本节点的节点，也就是逻辑地址上的相邻节点, 其中 |L|/2个节点的 ID 大于本节点， |L|/2个 ID 小于本节点， |L| 为 2b 或者 2X2b，如图 5 Pastry环节 点路由表所示。图 5 Pastry环节点路由表4.2.2 Pastry查询过程当一个 K 为 D 的查询消息到达节点A, 节点 A 首先看 D 是否在当前节点的叶子节点集中，如果是，则 查询消息直接被转发到目的节点，也就是叶子节点集中节点ID

13、 与 D数值最接近的那个节点( 有可能就是当 前节点 ) ，否则进行下一步在路由表中查找与D具有更长相同前缀的表项，如果该表项不为空，则将查询 消息直接转发到该节点，否则进行下一步.例如路由D= 0629 的查询消息 :5324 0748 0605 0620 0629 。如果不存在这样的节点, 当前节点将会从其维护的所有邻居节点集合中选择一个距离该键 值最接近的节点作为转发目标，如图6 Pastry查询过程图所示。图 6 Pastry 查询过程图所示节点路由表 R 中的每行与本节点具有相同的n 数位长度前缀，但是下一个数位不同例如，对于节点N0201： N-: N1?, N2?, N3? N0

14、: N00?, N01?, N03? N02: N021?, N022?, N023? N020: N0200, N0202, N0203当有多个节点时，根据邻近性度量选择最近的节点，此过程维持了较好的本地性。 节点加入：初始化状态表新节点开始时知道一个根据邻近性度量接近自己的节点A节点 A可以通过 使用扩展环 IP 组播等机制自动定位，或者由系统管理员通过其它手段获得新节点通过运行SHA-1 算法计 算自己的 IP 地址的摘要得到节点ID 为 X节点 X向节点 A发送 join消息， Pastry 将该消息路由到节点ID 在数值上最接近X 的节点 Z 接收到 join消息的节点，包括A、Z，

15、以及 A到 Z 路径上所有的节点将发送它 们的状态表给X，X 检查这些信息，然后节点根据下面的过程初始化状态表；由于A 与 X 在邻近性度量上 接近 , 所以使用 A的邻居节点集来初始化X 的邻居节点集由于Z的节点 ID 与 X最相近 , 因此使用 Z 的叶子 节点集来初始化X 的叶子节点集X将 join消息经过的第i 个节点的路由表的第i 行作为自己路由表的第 i 行 Join 消息经过的第i 个节点与 X的前 i 个数位相同向其它相关节点通告自己的到来新节点向邻居节 点集、叶子节点集和路由表中的每个节点发送自己的状态，以更新这些节点的状态表。此过程如图7 Pastry节点加入图所示。图 7

16、 Pastry 节点加入图节点退出 / 失效：叶子节点集L 中的节点退出机制，本地节点要求当前叶子节点集合L 中的 ID 最大的节点或 ID 最小的节点把它的叶子节点集合L1 发送过来 , 如果 L1 中存在 L 中没有的节点 , 则从中选择一 个替代失效节点 . 除非 |L|/2个节点同时失效，否恢复过程始终是有效的失效检测，和叶子节点集中的节 点周期性交互存活消息路由表R 中的节点退出机制：如果失效节点对应的表项为Rdl ( 第 l 行第 d 列) ， 则联系同一行中的所指向的存活节点并且获取该节点的Rdl 表项，如果l 行中没有存活节点， 则从下一行选择一个节点失效检测，和路由表中的节点联系(例如发送查询消息) 如果无反应则检测到节点 失效5 Chord和 Pastry比较Chord 和 Pastry 都是以 DHT为原理，构建的不同形式的环状结构，两者差别较大，具体比较如下表1 所示 6 。表 1 Chord 和 Past