搜索
第1页共17页P2P－CAN（Content-AddressableNetwork）CAN是由AT&T所提出点对点搜寻算法，CAN是利用多维坐标空间概念来建构的点对点架构。下图即为一个包含五个节点二维坐标系统的CAN架构概念图。如节点A所拥有的坐标空间为（0-0.5,0-0.5），节点B所用有的坐标空间为（0.5-1.0,0-0.5）。接下来，我们利用下图来说明CAN点对点建立的算法。当一个新的节点欲加入CAN系统时，新加入的节点会透过一个起始点（Bootstrap）随机的选择系统中的节点，并送出加入（JOIN）系统的讯息给随机选择的节点。当被选择到的节点收到加入的讯息时，则均分其所拥有的坐标空间。如下图所示，当节点E加入节点D的区域时，则D将其所拥有坐标空间均分给E。而在CAN的系统中档案的储存方式是当节点欲分享新的档案加入CAN系统时，CAN系统会将其文件名称依照杂凑函数计算出一个坐标，并将档案信息储存在此坐标空间的节点。当节点欲搜寻档案时，CAN也是利用每个节点所拥有的路由表（coordinateroutingtable）来搜寻档案。路由表内所储存的数据为记录在坐标空间中相邻节点的IP地址及所拥有的空间信息。因此，当起始点收到系统中节点要求搜寻档案的讯息时，起始点会先利用杂凑函数计算出此档案所代表的坐标，起始点会从系统中任意选择一个节点，并将搜寻档案的坐标送给被起始点所选择的节点。被选择到的节点收到档案数据讯息时，会先查询档案数据是否存在节点中，如果存在则回报档案讯息给提出搜寻档案的节点。如果不存在，则节点会依照节点中的路由表，依据贪婪算法（greedyalgorithm）找出一个与档案坐标最接近的节点，并转送此查询讯息，依照此搜寻方式直到找到档案为止第2页共17页T&TACIRI中心的CAN(ContentAddressableNetworks)项目独特之处在于采用多维的标识符空间来实现分布式散列算法。CAN将所有结点映射到一个n维的笛卡尔空间中，并为每个结点尽可能均匀的分配一块区域。CAN采用的散列函数通过对(key,value)对中的key进行散列运算，得到笛卡尔空间中的一个点，并将(key,value)对存储在拥有该点所在区域的结点内。CAN采用的路由算法相当直接和简单，知道目标点的坐标后，就将请求传给当前结点四邻中坐标最接近目标点的结点。CAN是一个具有良好可扩展性的系统，给定N个结点，系统维数为d，则路由路径长度为O(n1/d)，每结点维护的路由表信息和网络规模无关为O(d)。存在问题：key为文件的关键字（例如，文件名))，Value为与存储文件的主机相关的值(例如，IP地址)。插入(Key，Value)对的方法如下：先把Key用散列函数(hashfunchion)映射到空间中的某一点P，(Key,Value)对就被存储在拥有P所在区域的节点上。一个IP可以共享多个文件。那么一个IP对应多个虚拟空间地址。那么查询的时候是根据那个虚拟空间地址开始查找呢？分布式散列表分布式散列表示意图分布式散列表（英语：DistributedHashTable，简称DHT）是分布式计算系统中的一类，用来将一个关键值（key）的集合分散到所有在分布式系统中的节点，并且可以有效地将讯息转送到唯一一个拥有查询者提供的关键值的节点（Peers）。这里的节点类似散列表中的储存位置。分布式散列表通常是为了拥有极大节点数量的系统，而且在系统的节点常常会加入或离开（例如网络断线）而设计的。在一个结构性的延展网络（overlaynetwork）中，参加的节点需要第3页共17页与系统中一小部份的节点沟通，这也需要使用分布式散列表。分布式散列表可以用以建立更复杂的服务，例如分布式档案系统、点对点技术档案分享系统、合作的网页快取、多播、任播（anycast）、网域名称系统以及即时通讯等。目录[隐藏]1发展背景2性质3结构o3.1关键值空间分割o3.2延展网络4范例o4.1分布式散列表实作与协定o4.2分布式散列表的应用5参见6参考资料7外部链接[编辑]发展背景研究分布式散列表的主要动机是为了开发点对点系统，像是Napster、Gnutella及Freenet。这些系统得益于使用分散在互联网上的各项资源以提供实用的应用，特别在带宽及硬盘储存空间上，他们所提供的档案分享功能因此得到最大的好处。这些系统使用不同的方法来解决如何找到拥有某资料的节点的问题。Napster使用中央的索引服务器：每个节点加入网络的同时，会将他们所拥有的档案列表传送给服务器，这使得服务器可以进行搜寻并将结果回传给进行查询的节点。但中央索引服务器让整个系统易受攻击，且可能造成法律问题。于是，Gnutella和相似的网络改用大量查询模式（floodingquerymodel）：每次搜寻都会把查询讯息广播给网络上的所有节点。虽然这个方式能够防止单点故障（singlepointoffailure），但比起Napster来说却极没效率。最后，Freenet使用了完全分布式的系统，但它建置了一套使用经验法则的基于关键值的转送方法（keybasedrouting）。在这个方法中，每个档案与一个关键值相结合，而拥有相似关键值的档案会倾向被相似的节点构成的集合所保管。于是查询讯息就可以根据它所提供的关键值被转送到该集合，而不需要经过所有的节点。然而，Freenet并不保证存在网络上的资料在查询时一定会被找到。第4页共17页分布式散列表为了达到Gnutella与Freenet的分散性（decentralization）以及Napster的效率与正确结果，使用了较为结构化的基于关键值的转送方法。不过分布式散列表也有个Freenet有的缺点，就是只能作精确搜寻，而不能只提供部份的关键字；但这个功能可以在分布式散列表的上层实做。最初的四项分布式散列表技术——内容可寻址网络（Contentaddressablenetwork，CAN）、Chord（Chordproject）[1]、Pastry（Pastry(DHT)），以及Tapestry(DHT)（Tapestry(DHT)）皆同时于2001年发表。从那时开始，相关的研究便一直十分活跃。在学术领域以外，分布式散列表技术已经被应用在BitTorrent及CoralCDN（CoralContentDistributionNetwork）等。[编辑]性质分布式散列表本质上强调以下特性：分散性：构成系统的节点并没有任何中央式的协调机制。规模性：即使有成千上万个节点，系统仍然应该十分有效率。容错：即使节点不断地加入、离开或是停止工作，系统仍然必须达到一定的可靠度。要达到以上的目标，有一个关键的技术：任一个节点只需要与系统中的部份节点沟通。一般来说，若系统有n个节点，那么只有Θ(logn)个节点是必须的（见后述）。因此，当成员改变的时候，只有一部分的工作（例如资料或关键值的传送，散列表的改变等）必须要完成。有些分布式散列表的设计寻求能对抗网络中恶意的节点的安全性，但仍然保留参加节点的匿名性。在其他的点对点系统（特别是档案分享）中较为少见。参见匿名点对点技术。最后，分布式散列表必须处理传统分布式系统可能遇到的问题，例如负载平衡、资料完整性，以及效能问题（特别是确认转送讯息、资料储存及读取等动作能快速完成）。[编辑]结构分布式散列表的结构可以分成几个主要的元件[2][3]。其基础是一个抽象的关键值空间（keyspace），例如说所有160位元长的字符串集合。关键值空间分割（keyspacepartitioning）将关键值空间分割成数个，并指定到在此系统的节点中。而延展网络则连接这些节点，并让他们能够借由在关键值空间内的任一值找到拥有该值的节点。当这些元件都准备好后，一般使用分布式散列表来储存与读取的方式如下所述。假设关键值空间是一个160位元长的字符串集合。为了在分布式散列表中储存一个档案，名称为filename且内容为data，我们计算出filename的SHA1散第5页共17页列值——一个160位元的关键值k——并将讯息put(k,data)送给分布式散列表中的任意参与节点。此讯息在延展网络中被转送，直到抵达在关键值空间分割中被指定负责储存关键值k的节点。而(k,data)即储存在该节点。其他的节点只需要重新计算filename的散列值k，然后送出讯息get(k)给分布式散列表中的任意参与节点，以此来找与k相关的资料。此讯息也会在延展网络中被转送到负责储存k的节点。而此节点则会负责传回储存的资料data。以下分别描述关键值空间分割及延展网络的基本概念。这些概念在大多数的分布式散列表实作中是相同的，但设计的细节部份则大多不同。[编辑]关键值空间分割大多数的分布式散列表使用某些稳定散列（consistenthashing）方法来将关键值对应到节点。此方法使用了一个函数δ(k1,k2)来定义一个抽象的概念：从关键值k1到k2的距离。每个节点被指定了一个关键值，称为ID。ID为i的节点拥有根据函数δ计算，最接近i的所有关键值。例：Chord分布式散列表实作将关键值视为一个圆上的点，而δ(k1,k2)则是沿着圆顺时钟地从k1走到k2的距离。结果，圆形的关键值空间就被切成连续的圆弧段，而每段的端点都是节点的ID。如果i1与i2是邻近的ID，则ID为i2的节点拥有落在i1及i2之间的所有关键值。稳定散列拥有一个基本的性质：增加或移除节点只改变邻近ID的节点所拥有的关键值集合，而其他节点的则不会被改变。对比于传统的散列表，若增加或移除一个位置，则整个关键值空间就必须重新对应。由于拥有资料的改变通常会导致资料从分布式散列表中的一个节点被搬到另一个节点，而这是非常浪费带宽的，因此若要有效率地支援大量密集的节点增加或离开的动作，这种重新配置的行为必须尽量减少。[编辑]延展网络每个节点保有一些到其他节点（它的邻居）的连结。将这些连结总合起来就形成延展网络。而这些连结是使用一个结构性的方式来挑选的，称为网络拓扑。所有的分布式散列表实作拓扑有某些基本的性质：对于任一关键值k，某个节点要不就拥有k，要不就拥有一个连结能连结到距离较接近k的节点。因此使用以下的贪心算法即可容易地将讯息转送到拥有关键值k的节点：在每次执行时，将讯息转送到ID较接近k的邻近节点。若没有这样的节点，那我们一定抵达了最接近k的节点，也就是拥有k的节点。这样的转送方法有时被称为“基于关键值的转送方法”。除了基本的转送正确性之外，拓扑中另有两个关键的限制：其一为保证任何的转送路径长度必须尽量短，因而请求能快速地被完成；其二为任一节点的邻近节点数目（又称最大节点度（Degree(graphtheory)））必须尽量少，因此维护的第6页共17页花费不会过多。当然，转送长度越短，则最大节点度越大。以下列出常见的最大节点度及转送长度（n为分布式散列表中的节点数）最大节点度O(1)，转送长度O(logn)最大节点度O(logn)，转送长度O(logn/loglogn)最大节点度O(logn)，转送长度O(logn)最大节点度O(n1/2)，转送长度O(1)第三个选择最为常见。虽然他在最大节点度与转送长度的取舍中并不是最佳的选择，但这样的拓扑允许较为有弹性地选择邻近节点。许多分布式散列表实作利用这种弹性来选择延迟较低的邻近节点。最大的转送长度与直径有关：最远的两节点之间的最短距离。无疑地，网络的最大转送长度至少要与它的直径一样长，因而拓扑也被最大节点度与直径的取舍限制住[4]，而这在图论中是基本的性质。因为贪婪算法(GreedyMethod)可能找不到最短路径，因此转送长度可能比直径长[5]。对等网络(P2P)中主流分布式哈希算法比较分析本文首先从P2P的定义出发，介绍了结构化P2P与非结构化P2P的区别以及结构化P2P的核心技术DHT。而后，本文深入介绍了几种主流的DHT算法与协议并对每种协议进行了讨论。文章的最后展望了DHT在未来的发展趋势。对等网络(Peer-to-Peer，简称P2P)