|
|
|
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有帐号？FreeOZ用户注册
x
FROM：Wikipedia分散式杂凑表（英语：Distributed Hash Table，简称DHT）是分散式计算系统中的一类，用来将一个关键值（key）的集合分散到所有在分散式系统中的节点，并且可以有效地将讯息转送到唯一一个拥有查询者提供的关键值的节点（Peers）。这里的节点类似杂凑表中的储存位置。分散式杂凑表通常是为了拥有极大节点数量的系统，而且在系统的节点常常会加入或离开（例如网路断线）而设计的。在一个结构性的延展网路（overlay network）中，参加的节点需要与系统中一小部份的节点沟通，这也需要使用分散式杂凑表。分散式杂凑表可以用以建立更复杂的服务，例如分散式档案系统、点对点技术档案分享系统、合作的网页快取、多播、任播（anycast）、网域名称系统以及即时通讯等。
发展背景研究分散式杂凑表的主要动机是为了开发点对点系统，像是Napster、Gnutella及Freenet。这些系统得益于使用分散在网际网路上的各项资源以提供实用的应用，特别在频宽及硬碟储存空间上，他们所提供的档案分享功能因此得到最大的好处。
这些系统使用不同的方法来解决如何找到拥有某资料的节点的问题。Napster 使用中央的索引伺服器：每个节点加入网路的同时，会将他们所拥有的档案列表传送给伺服器，这使得伺服器可以进行搜寻并将结果回传给进行查询的节点。但中央索引伺服器让整个系统易受攻击，且可能造成法律问题。于是，Gnutella 和相似的网路改用大量查询模式（flooding query model）：每次搜寻都会把查询讯息广播给网路上的所有节点。虽然这个方式能够防止单点故障（single point of failure），但比起 Napster 来说却极没效率。
最后，Freenet 使用了完全分散式的系统，但它建置了一套使用经验法则的基于关键值的转送方法（key based routing）。在这个方法中，每个档案与一个关键值相结合，而拥有相似关键值的档案会倾向被相似的节点构成的集合所保管。于是查询讯息就可以根据它所提供的关键值被转送到该集合，而不需要经过所有的节点。然而，Freenet 并不保证存在网路上的资料在查询时一定会被找到。
分散式杂凑表为了达到 Gnutella 与 Freenet 的分散性（decentralization）以及 Napster 的效率与正确结果，使用了较为结构化的基于关键值的转送方法。不过分散式杂凑表也有个 Freenet 有的缺点，就是只能作精确搜寻，而不能只提供部份的关键字；但这个功能可以在分散式杂凑表的上层实做。
最初的四项分散式杂凑表技术——内容可定址网路（Content addressable network，CAN）、Chord（Chord project）[1]、Pastry（Pastry (DHT)），以及 Tapestry (DHT)（Tapestry (DHT)）皆同时于2001年发表。从那时开始，相关的研究便一直十分活跃。在学术领域以外，分散式杂凑表技术已经被应用在BitTorrent及CoralCDN（Coral Content Distribution Network）等。
性质分散式杂凑表本质上强调以下特性：
- 分散性：构成系统的节点并没有任何中央式的协调机制。
- 规模性：即使有成千上万个节点，系统仍然应该十分有效率。
- 容错：即使节点不断地加入、离开或是停止工作，系统仍然必须达到一定的可靠度。
要达到以上的目标，有一个关键的技术：任一个节点只需要与系统中的部份节点沟通。一般来说，若系统有n 个节点，那么只有 Θ(logn) 个节点是必须的（见后述）。因此，当成员改变的时候，只有一部分的工作（例如资料或关键值的传送，杂凑表的改变等）必须要完成。
有些分散式杂凑表的设计寻求能对抗网路中恶意的节点的安全性，但仍然保留参加节点的匿名性。在其他的点对点系统（特别是档案分享）中较为少见。参见匿名点对点技术。
最后，分散式杂凑表必须处理传统分散式系统可能遇到的问题，例如负载平衡、资料完整性，以及效能问题（特别是确认转送讯息、资料储存及读取等动作能快速完成）。
结构分散式杂凑表的结构可以分成几个主要的元件[2][3]。其基础是一个抽象的关键值空间（keyspace），例如说所有160位元长的字元串集合。关键值空间分割（keyspace partitioning）将关键值空间分割成数个，并指定到在此系统的节点中。而延展网路则连接这些节点，并让他们能够借由在关键值空间内的任一值找到拥有该值的节点。
当这些元件都准备好后，一般使用分散式杂凑表来储存与读取的方式如下所述。假设关键值空间是一个160位元长的字元串集合。为了在分散式杂凑表中储存一个档案，名称为 filename 且内容为 data，我们计算出 filename 的 SHA1 杂凑值——一个160位元的关键值 k——并将讯息 put(k,data) 送给分散式杂凑表中的任意参与节点。此讯息在延展网路中被转送，直到抵达在关键值空间分割中被指定负责储存关键值 k 的节点。而 (k,data) 即储存在该节点。其他的节点只需要重新计算 filename的杂凑值 k，然后送出讯息 get(k) 给分散式杂凑表中的任意参与节点，以此来找与 k 相关的资料。此讯息也会在延展网路中被转送到负责储存 k 的节点。而此节点则会负责传回储存的资料 data。
以下分别描述关键值空间分割及延展网路的基本概念。这些概念在大多数的分散式杂凑表实作中是相同的，但设计的细节部份则大多不同。
关键值空间分割大多数的分散式杂凑表使用某些稳定杂凑（consistent hashing）方法来将关键值对应到节点。此方法使用了一个函数 δ(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 (graph theory)））必须尽量少，因此维护的花费不会过多。当然，转送长度越短，则最大节点度越大。以下列出常见的最大节点度及转送长度（n 为分散式杂凑表中的节点数）
- 最大节点度 O(1)，转送长度 O(logn)
- 最大节点度 O(logn)，转送长度 O(logn / loglogn)
- 最大节点度 O(logn)，转送长度 O(logn)
- 最大节点度 O(n1 / 2)，转送长度 O(1)
第三个选择最为常见。虽然他在最大节点度与转送长度的取舍中并不是最佳的选择，但这样的拓朴允许较为有弹性地选择邻近节点。许多分散式杂凑表实作利用这种弹性来选择延迟较低的邻近节点。
最大的转送长度与直径有关：最远的两节点之间的最短距离。无疑地，网路的最大转送长度至少要与它的直径一样长，因而拓朴也被最大节点度与直径的取舍限制住[4]，而这在图论中是基本的性质。因为贪婪演算法(Greedy Method)可能找不到最短路径，因此转送长度可能比直径长[5]。
范例[编辑]分散式杂凑表实作与协定分散式杂凑表的应用参见[编辑]参考资料 Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris 与 Ion Stoica, Looking up data in P2P systems. 于 Communications of the ACM, 2003年1月^ [size=0.8em]（英文） Moni Naor 与 Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003年^ [size=0.8em]（英文） Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table. 博士论文 （史丹佛大学），2004年8月^ [size=0.8em]（英文） http://maite71.upc.es/grup_de_grafs/table_g.html^ [size=0.8em]（英文） Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks. Proc. STOC, 2004.^ http://www.bamboo-dht.org/^ http://planet.urv.es/bunshin/^ http://dks.sics.se^ http://mace.ucsd.edu
[编辑]外部链接
|
|
发表于 10-12-2009 22:19:10
收藏
赞
踩
楼主
发表于 11-12-2009 14:55:14
发表于 12-12-2009 12:11:58
