Archive for '分布式体系结构' Category
[zz]从LiveJournal后台发展看大规模网站性能优化方法
15 01月 2008zz from example.net.cn
March 16, 2006
从LiveJournal后台发展看大规模网站性能优化方法
于敦德 2006-3-16
一、LiveJournal发展历程
LiveJournal是99年始于校园中的项目，几个人出于爱好做了这样一个应用，以实现以下功能：
博客，论坛
社会性网络，找到朋友
聚合，把朋友的文章聚合在一起
LiveJournal采用了大量的开源软件，甚至它本身也是一个开源软件。
在上线后，LiveJournal实现了非常快速的增长：
2004年4月份：280万注册用户。
2005年4月份：680万注册用户。
2005年8月份：790万注册用户。
达到了每秒钟上千次的页面请求及处理。
使用了大量MySQL服务器。
使用了大量通用组件。
二、LiveJournal架构现状概况
三、从LiveJournal发展中学习
LiveJournal从1台服务器发展到100台服务器，这其中经历了无数的伤痛，但同时也摸索出了解决这些问题的方法，通过对LiveJournal的学习，可以让我们避免LJ曾经犯过的错误，并且从一开始就对系统进行良好的设计，以避免后期的痛苦。
下面我们一步一步看LJ发展的脚步。
1、一台服务器
一台别人捐助的服务器，LJ最初就跑在上面，就像Google开始时候用的破服务器一样，值得我们尊敬。这个阶段，LJ的人以惊人的速度熟悉的 Unix的操作管理，服务器性能出现过问题，不过还好，可以通过一些小修小改应付过去。在这个阶段里LJ把CGI升级到了FastCGI。
最终问题出现了，网站越来越慢，已经无法通过优过化来解决的地步，需要更多的服务器，这时LJ开始提供付费服务，可能是想通过这些钱来购买新的服务器，以解决当时的困境。
毫无疑问，当时LJ存在巨大的单点问题，所有的东西都在那台服务器的铁皮盒子里装着。
2、两台服务器
用付费服务赚来的钱LJ买了两台服务器：一台叫做Kenny的Dell 6U机器用于提供Web服务，一台叫做Cartman的Dell 6U服务器用于提供数据库服务。
LJ有了更大的磁盘，更多的计算资源。但同时网络结构还是非常简单，每台机器两块网卡，Cartman通过内网为Kenny提供MySQL数据库服务。
暂时解决了负载的问题，新的问题又出现了：
原来的一个单点变成了两个单点。
没有冷备份或热备份。
网站速度慢的问题又开始出现了，没办法，增长太快了。
Web服务器上CPU达到上限，需要更多的Web服务器。
3、四台服务器
又买了两台，Kyle和Stan，这次都是1U的，都用于提供Web服务。目前LJ一共有3台Web服务器和一台数据库服务器。这时需要在3台Web服务器上进行负载均横。
LJ把Kenny用于外部的网关，使用mod_backhand进行负载均横。
然后问题又出现了：
单点故障。数据库和用于做网关的Web服务器都是单点，一旦任何一台机器出现问题将导致所有服务不可用。虽然用于做网关的Web服务器可以通过保持心跳同步迅速切换，但还是无法解决数据库的单点，LJ当时也没做这个。
网站又变慢了，这次是因为IO和数据库的问题，问题是怎么往应用里面添加数据库呢？
4、五台服务器
又买了一台数据库服务器。在两台数据库服务器上使用了数据库同步(Mysql支持的Master-Slave模式)，写操作全部针对主数据库（通过Binlog，主服务器上的写操作可以迅速同步到从服务器上），读操作在两个数据库上同时进行(也算是负载均横的一种吧)。
实现同步时要注意几个事项：
读操作数据库选择算法处理，要选一个当前负载轻一点的数据库。
在从数据库服务器上只能进行读操作
准备好应对同步过程中的延迟，处理不好可能会导致数据库同步的中断。只需要对写操作进行判断即可，读操作不存在同步问题。
5、更多服务器
有钱了，当然要多买些服务器。部署后快了没多久，又开始慢了。这次有更多的Web服务器，更多的数据库服务器，存在 IO与CPU争用。于是采用了BIG-IP作为负载均衡解决方案。
6、现在我们在哪里：
现在服务器基本上够了，但性能还是有问题，原因出在架构上。
数据库的架构是最大的问题。由于增加的数据库都是以Slave模式添加到应用内，这样唯一的好处就是将读操作分布到了多台机器，但这样带来的后果就是写操作被大量分发，每台机器都要执行，服务器越多，浪费就越大，随着写操作的增加，用于服务读操作的资源越来越少。
由一台分布到两台
最终效果
现在我们发现，我们并不需要把这些数据在如此多的服务器上都保留一份。服务器上已经做了RAID，数据库也进行了备份，这么多的备份完全是对资源的浪费，属于冗余极端过度。那为什么不把数据分布存储呢？
问题发现了，开始考虑如何解决。现在要做的就是把不同用户的数据分布到不同的服务器上进行存储，以实现数据的分布式存储，让每台机器只为相对固定的用户服务，以实现平行的架构和良好的可扩展性。
为了实现用户分组，我们需要为每一个用户分配一个组标记，用于标记此用户的数据存放在哪一组数据库服务器中。每组数据库由一个master及几个 slave组成，并且slave的数量在2-3台，以实现系统资源的最合理分配，既保证数据读操作分布，又避免数据过度冗余以及同步操作对系统资源的过度消耗。
由一台（一组）中心服务器提供用户分组控制。所有用户的分组信息都存储在这台机器上，所有针对用户的操作需要先查询这台机器得到用户的组号，然后再到相应的数据库组中获取数据。
这样的用户架构与目前LJ的架构已经很相像了。
在具体的实现时需要注意几个问题：
在数据库组内不要使用自增ID，以便于以后在数据库组之间迁移用户，以实现更合理的I/O，磁盘空间及负载分布。
将userid，postid存储在全局服务器上，可以使用自增，数据库组中的相应值必须以全局服务器上的值为准。全局服务器上使用事务型数据库InnoDB。
在数据库组之间迁移用户时要万分小心，当迁移时用户不能有写操作。
7、现在我们在哪里
问题：
一个全局主服务器，挂掉的话所有用户注册及写操作就挂掉。
每个数据库组一个主服务器，挂掉的话这组用户的写操作就挂掉。
数据库组从服务器挂掉的话会导致其它服务器负载过大。
对于Master-Slave模式的单点问题，LJ采取了Master-Master模式来解决。所谓Master-Master实际上是人工实现的，并不是由MySQL直接提供的，实际上也就是两台机器同时是Master，也同时是Slave，互相同步。
Master-Master实现时需要注意：
一个Master出错后恢复同步，最好由服务器自动完成。
数字分配，由于同时在两台机器上写，有些ID可能会冲突。
解决方案：
奇偶数分配ID，一台机器上写奇数，一台机器上写偶数
通过全局服务器进行分配(LJ采用的做法)。
Master-Master模式还有一种用法，这种方法与前一种相比，仍然保持两台机器的同步，但只有一台机器提供服务（读和写），在每天晚上的时候进行轮换，或者出现问题的时候进行切换。
8、现在我们在哪里
现在插播一条广告，MyISAM VS InnoDB。
使用InnoDB：
支持事务
需要做更多的配置，不过值得，可以更安全的存储数据，以及得到更快的速度。
使用MyISAM：
记录日志（LJ用它来记网络访问日志）
存储只读静态数据，足够快。
并发性很差，无法同时读写数据（添加数据可以）
MySQL非正常关闭或死机时会导致索引错误，需要使用myisamchk修复，而且当访问量大时出现非常频繁。
9、缓存
去年我写过一篇文章介绍memcached，它就是由LJ的团队开发的一款缓存工具，以key-value的方式将数据存储到分布的内存中。LJ缓存的数据：
12台独立服务器（不是捐赠的）
28个实例
30GB总容量
90-93%的命中率（用过squid的人可能知道，squid内存加磁盘的命中率大概在70-80%）
如何建立缓存策略？
想缓存所有的东西？那是不可能的，我们只需要缓存已经或者可能导致系统瓶颈的地方，最大程度的提交系统运行效率。通过对MySQL的日志的分析我们可以找到缓存的对象。
缓存的缺点？
没有完美的事物，缓存也有缺点：
增大开发量，需要针对缓存处理编写特殊的代码。
管理难度增加，需要更多人参与系统维护。
当然大内存也需要钱。
10、Web访问负载均衡
在数据包级别使用BIG-IP，但BIG-IP并不知道我们内部的处理机制，无法判断由哪台服务器对这些请求进行处理。反向代理并不能很好的起到作用，不是已经够快了，就是达不到我们想要的效果。
所以，LJ又开发了Perlbal。特点：
快，小，可管理的http web 服务器/代理
可以在内部进行转发
使用Perl开发
单线程，异步，基于事件，使用epoll , kqueue
支持Console管理与http远程管理，支持动态配置加载
多种模式：web服务器，反向代理，插件
支持插件：GIF/PNG互换？
11、MogileFS
LJ使用开源的MogileFS作为分布式文件存储系统。MogileFS使用非常简单，它的主要设计思想是：
文件属于类（类是最小的复制单位）
跟踪文件存储位置
在不同主机上存储
使用MySQL集群统一存储分布信息
大容易廉价磁盘
到目前为止就这么多了，更多文档可以在http://www.danga.com/words/找到。Danga.com和LiveJournal.com的同学们拿这个文档参加了两次MySQL Con，两次OS Con，以及众多的其它会议，无私的把他们的经验分享出来，值得我们学习。在web2.0时代快速开发得到大家越来越多的重视，但良好的设计仍是每一个应用的基础，希望web2.0们在成长为Top500网站的路上，不要因为架构阻碍了网站的发展。
参考资料：http://www.danga.com/words/2005_oscon/oscon-2005.pdf
感谢向静推荐了这篇文档给我。
google架构的启示
14 01月 2008highscalability.com的一篇文章在介绍了google的一些基础架构后，给出了几条启示，感觉不错，翻译如下：
架构会成为竞争优势。
在多个数据中心扩展是个尚未解决的问题。
看看Hadoop，如果你没有时间从头实现GFS/MapReduce架构的话。
构建一个平台的优势是一个初级开发者也可以快速在上面开发出健壮的应用。
协同(Synergy)并不总是一句废话：让所有的系统协调工作，改进其一都可对整个系统有所提升。如果每个系统各自为政，那么就无法取得持续的整体改进。
构建自管理的系统。你可以更容易平衡资源，动态增加容量，下线机器和优雅的完成软件升级，而这一切都无需停机。
使用优胜劣汰的规则。让多个节点同时处理一个耗时较长的任务，然后取那个最先完成的。
不要忽视学术界。学术界有很多还没有转化到工业应用中的好点子。
考虑压缩。特别是当你有充足的CPU而I/O有瓶颈的时候。
转载请保留出处。http://bluefire.wordpress.com.cn 。thanks.
原文在 http://highscalability.com/google-architecture
[zz]Google 的计算能力仍是独步武林
10 01月 2008本文转载自dbanotes
作者: Fenng | 可以转载, 转载时务必以超链接形式标明文章原始出处和作者信息及版权声明 网址: http://www.dbanotes.net/arch/google_mapreduce_amazing.html
从 Greg Linden 的文章看到的数据：Google 的 MapReduce 平均每天处理 20 Petabytes 的数据。每天能跑完 10 万个工作任务。光是 07 年 9 月，就用掉了 11081 个"机器年" ，跑了 220 万个 Mapreduce 任务。这个计算能力是惊人的。
Yahoo! 也用 Hadoop 实现了 Mapreduce , 我个人感觉和 Google 可能还有一段距离。光有计算环境还不行，还要有应用程序来实现功能，Google 已经实现了超过 1 万个应用程序，Yahoo! 有多少呢?
这方面估计微软更没戏了，要是弄个不包括 "Window" 的 Windows 服务器集群估计还能差不多，否则，光是一个视窗要耗费多少计算资源? 如果服务器规模是几万、几十万台，计算能力的浪费是惊人的。微软的对抗计划是 Dryad.
所以说啊，Google 的计算能力仍是独步武林，虽然有不服气的，但有什么办法? 这方面 Google [...]
[zz]Kademlia: 基于异或运算的P2P信息系统(翻译稿)
5 01月 2008转载自这里。英文原版paper在这里 Kademlia: A Peer-to-peer Information. System Based on the XOR Metric.
Petar Maymounkov and David Mazi`eres
fpetar,dmg@cs.nyu.edu
http://kademlia.scs.cs.nyu.edu
摘要
本文我们将描述一个在容易出错的网络环境中拥有可证实的稳定性和高性能稳定性的点对点(P2P)系统。我们的系统使用一个很新颖的基于异或运算的拓扑来发送查询并且定位节点, 这简化了算法并且使验证更加容易。这种拓扑结构具有以下特性，它能通过交换消息传达和加强节点间的有用联系信息。本系统利用这个信息来发送平行的,异步的查询消息来对付节点的失效而不会给用户带来超时时延。
1 ．介绍
本论文描述Kademlia , 一个点对点（P2P）的<键, 值>元组存储和查询系统。 Kademlia拥有许多的可喜的特点，这些特点是任何以前的P2P系统所无法同时提供的。它减少了节点必须发送的用来相互认识的配置消息的数量。在做键查询的同时, 配置消息将会被自动传播。 节点拥有足够的知识和灵活性来通过低时延路径发送查询请求。 Kademlia使用平行的,异步的查询请求来避免节点失效所带来的超时时延。通过节点记录相互的存在的算法可以抵抗某些基本的拒绝服务（DoS）攻击。最后, 仅仅使用在分布式运行时间上较弱的假设（通过对现有点对点系统的测量而确认的这些假设），我们可以正式的证实Kademlia的许多重要特性。
Kademlia 使用了许多点对点（P2P）系统的基本方法。 键是一个160-bit的隐式数量(例如, 对一些大型数据进行SHA-1哈希的值)。每个参与的机器都拥有一个节点ID, 160位的键。 <键, 值>对将存储在那些ID与键很‘接近’的节点上, 这里‘接近’当然是按照一个接近度的概念来计算的。最后, 一个基于节点ID的路由算法使得任何人可以在一个目的键附近定位到一个服务器。
Kademlia 的许多的优点都是得益于它使用了一个很新颖的方法, 那就是用节点间的键作异或运算的结果来作为节点间的距离。异或运算是对称的, 允许Kademlia的参与者接收来自相同分布的并且包含在其路由表中的节点的查找请求。如果没有这个性质，就像Chord一样，系统无法从它们收到的查询请求中学习到有用的路由信息。更糟的是， 由于Chord中的运算是不对称的， Chord的路由表更加严格。 Chord节点的查找表的每一项都必须存储精确的按ID域的间隔递增的节点。在这个间隔内的任何节点都比这个间隔内的某些键大，因此离键很远。相反， Kademlia 可以在一定的间隔内发送请求给任何节点， 允许基于时延来选择路由，甚至发送平行的，异步的查询。
为了在特定的ID附近定位节点，Kademlia自始至终使用一个单程的路由算法。相反，其它一些系统使用一种算法来接近目标ID,然后在最后的几个跳数使用另外一种算法。在现有系统中，Kademlia与pastry的第一阶段最像，（虽然作者并没有用这种方式来描述），Kademlia 的异或运算可以使当前节点到目标ID的距离粗略的持续减半，以此来寻找节点。在第二阶段，Pastry不再使用距离运算，而是改为比较ID的数字区别。它使用第二种，数字区别运算作为替代。不幸的是，按第二种运算计算的接近比第一种的远得多，这造成特定节点ID值的中断，降低了性能，并且导致在最差行为下的正式分析的尝试失败。
2 ．系统描述
每个Kademlia节点有一个160位的节点ID。在Chord系统中，ID是通过某种规则构造出来的，但在这片文章中，为了简化，我们假设每台机器在加入系统时将选择一个随机的160位值。每条节点发送的消息包含它的节点ID， 同时允许接收者记录下发送者的存在信息，如果有必要的话。
键，同样也是160位的标识符。为了发布和寻找<键，值>对，Kademlia依赖一个概念，那就是两标识符之间的距离的概念。给定两个标识符， x和y， Kademlia定义两者的位异或（XOR）的结果作为两者的距离，d(x，y)＝x⊕y。我们首先注意到异或运算是一个有意义的运算，虽然不是欧几里得运算。很明显具有下面的性质： d(x，x)＝0；如果x≠y, 则d(x, [...]
[zz]eMule中的分布式哈希表技术: Kademlia
5 01月 2008转载自这里。
目前的kad协议实现普遍兼容性还不够，没有一个比较权威的实现标准。你可以参考一下文献[1]，或者是KadC、emule的源码。 http://kadc.sourceforge.net/ http://sourceforge.net/projects/emule
前两天在网上看到世界知名的电骡服务器Razorback 2被查封、4人被拘禁的消息，深感当前做eMule / BitTorrent等P2P文件交换软件的不易。以分布式哈希表方式(DHT，Distributed Hash Table)来代替集中索引服务器可以说是目前可以预见到的为数不多的P2P软件发展趋势之一，比较典型的方案主要包括：CAN、CHORD、 Tapestry、Pastry、Kademlia和Viceroy等，而Kademlia协议则是其中应用最为广泛、原理和实现最为实用、简洁的一种，当前主流的P2P软件无一例外地采用了它作为自己的辅助检索协议，如eMule、Bitcomet、Bitspirit和Azureus等。鉴于 Kademlia日益增长的强大影响力，今天特地在blog里写下这篇小文，算是对其相关知识系统的总结。
1. Kademlia简述
Kademlia(简称Kad)属于一种典型的结构化P2P覆盖网络(Structured P2P Overlay Network)，以分布式的应用层全网方式来进行信息的存储和检索是其尝试解决的主要问题。在Kademlia网络中，所有信息均以<key, value>的哈希表条目形式加以存储，这些条目被分散地存储在各个节点上，从而以全网方式构成一张巨大的分布式哈希表。我们可以形象地把这张哈希大表看成是一本字典：只要知道了信息索引的key，我们便可以通过Kademlia协议来查询其所对应的value信息，而不管这个value信息究竟是存储在哪一个节点之上。在eMule、BitTorrent等P2P文件交换系统中，Kademlia主要充当了文件信息检索协议这一关键角色，但Kad 网络的应用并不仅限于文件交换。下文的描述将主要围绕eMule中Kad网络的设计与实现展开。
2. eMule的Kad网络中究竟存储了哪些信息?
只要是能够表述成为<key, value>字典条目形式的信息Kad网络均能存储，一个Kad网络能够同时存储多张分布式哈希表。以eMule为例，在任一时刻，其Kad网络均存储并维护着两张分布式哈希表，一张我们可以将其命名为关键词字典，而另一张则可以称之为文件索引字典。
a. 关键词字典：主要用于根据给出的关键词查询其所对应的文件名称及相关文件信息，其中key的值等于所给出的关键词字符串的 160比特SHA1散列，而其对应的value则为一个列表，在这个列表当中，给出了所有的文件名称当中拥有对应关键词的文件信息，这些信息我们可以简单地用一个3元组条目表示：(文件名，文件长度，文件的SHA1校验值)，举个例子，假定存在着一个文件 “warcraft_frozen_throne.iso”，当我们分别以“warcraft”、“frozen”、“throne”这三个关键词来查询 Kad时，Kad将有可能分别返回三个不同的文件列表，这三个列表的共同之处则在于它们均包含着一个文件名为 “warcraft_frozen_throne.iso”的信息条目，通过该条目，我们可以获得对应iso文件的名称、长度及其160比特的SHA1校验值。
b. 文件索引字典：用于根据给出的文件信息来查询文件的拥有者(即该文件的下载服务提供者)，其中key的值等于所需下载文件的 SHA1校验值(这主要是因为，从统计学角度而言，160比特的SHA1文件校验值可以唯一地确定一份特定数据内容的文件)；而对应的value也是一个列表，它给出了当前所有拥有该文件的节点的网络信息，其中的列表条目我们也可以用一个3元组表示：(拥有者IP，下载侦听端口，拥有者节点ID)，根据这些信息，eMule便知道该到哪里去下载具备同一SHA1校验值的同一份文件了。
3. 利用Kad网络搜索并下载文件的基本流程是怎样的?
基于我们对eMule的Kad网络中两本字典的理解，利用Kad网络搜索并下载某一特定文件的基本过程便很明白了，仍以 “warcraft_frozen_throne.iso”为例，首先我们可以通过warcraft、frozen、throne等任一关键词查询关键词字典，得到该iso的SHA1校验值，然后再通过该校验值查询Kad文件索引字典，从而获得所有提供 “warcraft_frozen_throne.iso”下载的网络节点，继而以分段下载方式去这些节点下载整个iso文件。
在上述过程中，Kad网络实际上所起的作用就相当于两本字典，但值得再次指出的是，Kad并不是以集中的索引服务器(如华语P2P源动力、 Razorback 2、DonkeyServer 等，骡友们应该很熟悉吧)方式来实现这两本字典的存储和搜索的，因为这两本字典的所有<key, value>条目均分布式地存储在参与Kad网络的各节点中，相关文件信息、下载位置信息的存储和交换均无需集中索引服务器的参与，这不仅提高了查询效率，而且还提高了整个P2P文件交换系统的可靠性，同时具备相当的反拒绝服务攻击能力；更有意思的是，它能帮助我们有效地抵制FBI的追捕，因为俗话说得好：法不治众…看到这里，相信大家都能理解“分布式信息检索”所带来的好处了吧。但是，这些条目究竟是怎样存储的呢?我们又该如何通过Kad网络来找到它们?不着急，慢慢来。
[...]
[zz]对等网络中主流分布式哈希算法比较分析
5 01月 2008转载自这里。2006.3.6
本文首先从P2P的定义出发，介绍了结构化P2P与非结构化P2P的区别以及结构化P2P的核心技术DHT。而后，本文深入介绍了几种主流的DHT算法与协议并对每种协议进行了讨论。文章的最后展望了DHT在未来的发展趋势。
对等网络(Peer -to-Peer，简称P2P)是目前非常热门的应用，自1999年以来，P2P的研究一直是国外知名学府(如美国麻省理工学院，加州大学伯克利分校和莱斯大学等)以及知名企业的研发机构(如微软，诺基亚的研究院)关注的重点。它甚至被美国《财富》杂志称为改变因特网发展的四大新技术之一，被认为是代表无线宽带互联网未来的关键技术。
作为一项新兴的技术，目前学术界对P2P在技术层面上的定义尚未统一。Keith W. Ross (Polytechnic University)和Dan Rubenstein(Columbia University)在[9]中提到了对P2P系统的3个基本定义：
相比中央服务器而言有明显的自治性(Autonomy)。
利用网络边缘的资源，如存储/计算能力和信息资源。
网络边缘的资源处在动态的变化中(新的资源加入，已有的资源消失)。
自治性的要求使得P2P系统不再需要特定的中央管理机制，所有节点之间拥有对等的关系。这一方面为系统带来了自组织、容错性好、可扩展性强等优点；另一方面也提出了新的问题：如何在没有集中管理机制的情况下实现系统的自组织和自管理？
定义2，3中分布性和动态性的特点使得上述问题的实现具有更大的难度。在分布式系统中，过多过快的信息交互可能消耗大量的网络资源；而为了实时反映系统的变化，又要求节点及时获得更新信息，这就需要在节点之间进行通信。
为了解决这一对矛盾，已经有许多P2P的框架和协议被提出来并得到了很好的应用。
结构化与非结构化P2P
依照节点信息存储与搜索方式的不同，诸多P2P协议可以分为2大类：结构化(Structured)的与非结构化(Unstructured)的系统。
非结构化P2P系统
在非结构化的系统中，每个节点存储自身的信息或信息的索引(如指针和IP地址)。当用户需要在P2P系统中获取信息时，他们预先并不知道这些信息(如某个文件)会在那个节点上存储。因此，在非结构化P2P系统中，信息搜索的算法难免带有一定的盲目性，例如最简单的泛洪式查找(类似于广播)和扩展环查找(从最近的n个节点开始，层层转发直到找到目标或超出了跳数的上限为止)。
一些典型的应用采用了一些优化的办法。如在Gnutella中，采用了等级制的组成结构：节点被分成超级节点(Super Node)和普通节点。普通节点必须依附于超级节点，每个超级节点作为一个独立的域管理者，负责处理域内的查询操作。在查找的过程中，查询首先在域内进行，失败后才会扩展到超级节点之间。
非结构化系统的优点在于实现结构简单：无须中央服务器，节点之间完全平等，网络的层次是单一的，而且节点之间无需维护拓扑信息。
结构化P2P系统
在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时，他们必须知道这些信息(或索引)可能存在于那些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找，因此提高了信息搜索的效率。
但是，结构化P2P也引入了新的问题：
首先，既然信息是分布存储的，那么如何将信息分布存储在重叠网中的节点上？
其次，由于节点动态的加入和离开重叠网，如何将拓扑的变更信息通知其它节点？
DHT的引入基本解决了上述问题，因此自从DHT协议出现以后，结构化P2P的应用得到了快速的发展。目前已经有很多较为成熟的DHT协议被提出并且得到了应用。其中比较有代表性的有：缓冲阵列路由协议(CARP)；一致性哈希；Chord；内容寻址网络；Pastry。
DHT简介
DHT使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核心思想是通过将存储对象的特征(关键字)经过哈希运算，得到键值(Hash Key)，对象的分布存储依据键值来进行。具体来讲，大致有以下步骤：
对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映射到了一个具体的数值范围中。
重叠网中的每个节点负责数值范围中的特定段落。例如，节点A负责存储键值从8000到8999的对象；而节点B负责7000~7999的对象。这样就将对象集合分布地存储在所有的节点中。
节点可以直接存储对象本身，如文件中的一个片段；也可以存储对象的索引，如该对象所在节点的IP地址。
结构化的分布式存储问题解决后，剩下的问题就是用户如何才能找到存储着目标信息的节点。在有着大量节点(如100万个)的P2P系统中，任何节点都不可能拥有全部的节点?键值?内容的对应关系；因此用户获得了键值之后，如何找到该键值对应的节点就被称为DHT的路由问题。DHT协议必须定义优化的查找(路由)算法来完成这一搜寻的工作。不同的DHT协议之间区别很大程度上就在于定义了不同的路由算法。
DHT的应用非常简洁—-API简单到只有一项输入和一项输出：
应用层将数据对象(文件、数据块或索引)通过哈希算法获得键值，将该键值提交给DHT后，返回结果就是键值所在节点的IP地址。图1(来自[9])显示了这种应用结构：
图 1 DHT的应用结构
在这样的支持下，可以开发多种P2P的应用程序，如网络存储与文件共享、即时消息、音频/视频等。图2(来自[9])显示了这种应用结构：
图 2 DHT应用的层次
主流DHT协议
缓冲阵列路由协议(CARP，Cache Array Routing Protocol)
协议简介
CARP是由微软公司的Vinod Valloppillil和宾西法尼亚大学的Keith W. Ross在1997年提出的。该协议可以将URL空间映射到一个仅有松散关联关系的Web cache 服务器(在协议中称为“代理”，Proxy)阵列中。支持该协议的HTTP客户端可以根据要访问的URL智能选择目标代理。该协议解决了在代理阵列内分布存储内容的问题，避免了内容的重复存储，提高了客户端访问时Web Cache命中的概率。
哈希算法
哈希使用的关键字有2个，一个是代理的标识符(每个代理均有唯一的标识)，另一个是URL本身。存储内容时，每个代理负责缓冲哈希键值最大的URL。这样，当缓冲代理阵列发生少量变化时(新的代理加入或旧的代理退出)，原有的URL还有可能仍然被映射到原来的代理上，仍可以按照原有的方式访问。
路由算法
客户端(HTTP浏览器)首先加载一个代理配置文件，该文件中存储了代理的标识符和IP地址等用于哈希的关键参数。浏览器在访问网页时，可以根据URL和代理标识获得代理的位置信息(IP地址)，从而可以直接访问缓冲代理中的页面。
讨论
CARP的哈希过程比较简单，路由查找更是简单到至多只有一跳(O(1))。但是CARP在P2P的应用环境中有一些致命的缺陷：
每个节点必须知道其它所有节点的信息。在大规模的重叠网环境中，由于可能存在大量的(数百万)节点，加之节点都是动态加入和退出网络，因此这一条件几乎不可能满足。
在缓冲阵列发生较大变化时(这在P2P网络中非常常见)，原有的URL和代理之间的对应关系可能发生改变，从而使得原有的配置文件失效。
一致性哈希(Consistent [...]
[zz]P2P网络中的DHT分布式哈希结构
5 01月 2008转载自这里
现有的P2P实现可以分为三种类型。它们分别是：基于目录服务器P2P，非结构化P2P和结构化P2P。基于目录服务器这一类系统中设置目录服务器，用于保存用户节点的地址信息和该节点上共享文件的描述信息，文件本身是分散存贮在各个节点上的，实际的文件传输也是在对等节点之间进行，目录服务器仅仅起到中介作用，为节点提供发布和查询文件索引服务。鉴于集中式目录服务器不仅可能成为系统的瓶颈，而且还可能引发法律纠纷，因此出现了以Gnutella为代表的非结构化P2P系统，在这种P2P结构中，文件索引信息不再由集中式的目录服务器存储和管理，而是分散到网络中，由节点自己保存，该类系统采用分布式的索引查找策略，为了查找网络中的文件，节点要随机地维护网络中的其他一些节点作为邻居，以便通过邻居节点广播查询报文。非结构化P2P系统中由于不存在目录服务器，所以没有单点瓶颈问题，不存在单一故障点。然而其缺点也是明显的：在网络中广播查询报文加重了网络通信负担，其查询机制在系统规模扩大时不具有可扩展性。另外，由于查询报文被限制在特定的范围内，所以并不能保证一定可以找到网络中存在的目的数据。上面介绍的两类P2P系统都缺乏有效的、可扩展的索引查找机制。为此，近年来许多研究小组在设计可扩展的查找机制方面做了大量的研究工作，提出了Chord、Pastry、CAN和Tapestry等用于构建结构化P2P的分布式哈希表系统（Distributed Hash Table，DHT）。DHT的主要思想是：首先，每条文件索引被表示成一个(K, V)对，K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的IP地址（或节点的其他描述信息）。所有的文件索引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的(K,V)对）。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也就决定了节点要维护特定的邻居节点，以便路由能顺利进行。这个规则因具体系统的不同而不同，CAN，Chord，Pastry和Tapestry都有自己的规则，也就呈现出不同的特性。基于分布式哈希表（DHT）的分布式检索和路由算法因为具有查找可确定性、简单性和分布性等优点，正成为国际上结构化P2P网络研究和应用的热点。自2002年起，美国国家科学基金会（NSF）提供了1200万美元的资金启动了一个为期5年的研究项目IRIS，该项目集中了MIT和UC Berkeley等5所著名高等院校的强大科研力量，为下一代大规模分布式应用研制基于DHT的新型基础设施。
分布式哈希表在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个P2P应用同时使用。
1 Chord
Chord是UC Berkeley和MIT共同提出的一种分布式查找算法，目的是为了能在P2P网络中查找数据。给定一个关键字，Chord可以有效地把该关键字映射到网络中某个节点上。因而在P2P网络中只要给每个数据V都赋予一个关键字K，就可以利用Chord在该关键字映射的节点上存储或提取相应的(K, V)对。Chord的突出特点是算法简单，而且可扩展 － 查询过程的通信开销和节点维护的状态随着系统总节点数增加成指数关系。Chord的路由性能优于CAN，而节点加入过程和维护开销又优于Tapestry和Pastry。
Chord的设计:Chord中每个关键字和节点都分别拥有一个m比特的标识符。关键字标识符K通过哈希关键字本身得到，而节点标识符N则通过哈希节点的IP地址得到。哈希函数可以选用SHA-1。所有节点按照其节点标识符从小到大（取模2m后）沿着顺时针方向排列在一个逻辑的标识圆环上（称为Chord环）。Chord的映射规则是：关键字标识为K的(K, V)对存储在这样的节点上，该节点的节点标识等于K或者在Chord环上紧跟在K之后，这个节点被称为K的后继节点，表示为successor(K)。因为标识符采用m位二进制数表示，并且从0到2m－1顺序排列成一个圆圈，succesor(K)就是从K开始顺时针方向距离K最近的节点。
上图给出了一个m=6的Chord环，环中分布了10个节点，存储了5个关键字，节点标识前加上N而关键字前加上K以示区别。因为successor(10)=14，所以关键字10存储到节点14上。同理，关键字24和30存储到节点32上，关键字38存储到节点38上，而关键字54则存储到节点56上。当网络中的参与节点发生变动时，上面的映射规则仍然要成立。为此，当某节点n加入网络时，某些原来分配给n的后继节点的关键字将分配给n。当节点n离开网络时，所有分配给它的关键字将重新分配给n的后继节点。除此之外，网络中不会发生其他的变化。以上图为例，当标识为26的节点接入时，原有标识为32的节点负责的标识为24的关键字将转由新节点存储。显然，为了能在系统中转发查询报文，每个节点要了解并维护chord环上相邻节点的标识和IP地址，并用这些信息构成自身的路由表。有了这张表，Chord就可以在环上任意两点间进行寻路。
Chord的路由：Chord中每个节点只要维护它在环上的后继节点的标识和IP地址就可以完成简单的查询过程。对特定关键字的查询报文可以通过后继节点指针在圆环上传递，直到到达这样一个节点：关键字的标识落在该节点标识和它的后继节点标识之间，这里的后继节点就是存储目标(K, V)对的节点。
上图给出了一个示例，节点8发起的查找关键字54的请求，通过后继节点依次传递，最后定位到存储有关键字54的节点56。在这种简单查询方式中，每个节点需要维护的状态信息很少，但查询速度太慢。若网络中有N个节点，查询的代价就为O（N）数量级。因而在网络规模很大时，这样的速度是不能接受的。
为了加快查询的速度，Chord使用扩展的查询算法。为此，每个节点需要维护一个路由表，称为指针表（finger table）。如果关键字和节点标识符用m位二进制位数表示，那么指针表中最多含有m个表项。节点n的指针表中第i项是圆环上标识大于或等于n+2i-1的第一个节点（比较是以2m为模进行的）。例如若s=successor(n+2i-1), 1≤i≤m，则称节点s为节点n的第i个指针，记为n.finger[i]。n.finger[1]就是节点n的后继节点。指针表中每一项既包含相关节点的标识，又包含该节点的IP地址（和端口号）。
上图给出了节点8的指针表，例如节点14是环上紧接在(8+20) mod 26=9之后的第一个节点，所以节点8的第一个指针是节点14；同理因为节点42是环上紧接在(8+25) mod 26=40之后的第一个节点，所以节点8的第6个指针是节点42。维护指针表使得每个节点只需要知道网络中一小部分节点的信息，而且离它越近的节点，它就知道越多的信息。但是，对于任意一个关键字K，节点通常无法根据自身的指针表确定的K的后继节点。例如，下图中的节点8就不能确定关键字34的后继节点，因为环上34的后继节点是38，而节点38并没有出现在节点8的指针表中。
扩展的查询过程是：任何一个节点收到查询关键字K的请求时，首先检查关K是否落在该节点标识和它的后继节点标识之间，如果是的话，这个后继节点就是存储目标(K, V)对的节点。否则，节点将查找它的指针表，找到表中节点标识符最大但不超过K的第一个节点，并将这个查询请求转发给该节点。通过重复这个过程，最终可以定位到K的后继节点，即存储有目标(K, V)对的节点。
节点加入和退出：为了应对系统的变化，每个节点都周期性地运行探测协议来检测新加入节点或失效节点，从而更新自己的指针表和指向后继节点的指针。新节点n加入时，将通过系统中现有的节点来初始化自己的指针表。也就是说，新节点n将要求已知的系统中某节点为它查找指针表中的各个表项。在其他节点运行探测协议后，新节点n将被反映到相关节点的指针表和后继节点指针中。这时，系统中一部分关键字的后继节点也变为新节点n，因而先前的后继节点要将这部分关键字转移到新节点上。当节点n失效时，所有指针表中包括n的节点都必须把它替换成n的后继节点。为了保证节点n的失效不影响系统中正在进行的查询过程，每个Chord节点都维护一张包括r个最近后继节点的后继列表。如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正常节点替换失效节点。
2 Pastry
Microsoft研究院和Rice大学共同提出的Pastry是用于广域P2P应用的分布式查找和路由系统。Pastry系统中的每个节点都有一个唯一的节点号（nodeId），每条消息都有一个关键字。Pastry可以把消息路由到nodeId和关键字在数值上最接近的那个节点。每个Pastry节点维护节点号空间中和它直接相邻的邻居节点信息。当发生新节点加入、已有节点失效或恢复事件时，Pastry节点会通知上层应用。Pastry是完全分布式的、可扩展的和自组织的，它能够自动应对节点加入、离开和失效。
Pastry的设计：Pastry是自组织的重叠网络，每个节点都被分配一个128位的nodeId。nodeId用于在圆形的节点空间中（从0到2128－1）标识节点的位置，它是在节点加入系统时随机分配的，随机分配的结果是使得所有的nodeId在128位的节点号空间中均匀分布。nodeId可以通过计算节点公钥或者IP地址的哈希函数值来获得。
假设网络包含N个节点，Pastry可以把一个给定的关键字路由到nodeId和该关键字最接近的节点。即使同时发生节点失效，Pastry也可以保证关键字送达目标节点，除非nodeId和关键字临近的节点中有|L|/2个同时失效（|L|是配置参数，典型值取16或32）。为了进行路由，Pastry把nodeId和关键字表示为一串以2b为基的数，查询消息被路由到nodeId和关键字在数值上最接近的节点。方法是：每个节点把查询消息转发给下一个节点时，要保证这个节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId和关键字的相同前缀长一个数位（即b个比特）。如果找不到这样的邻居节点，消息将转发给前缀长度相同但是节点号数值更接近关键字的节点。为此，每个Pastry节点都需要维护状态表：一张路由表，一个邻居节点集和一个叶子节点集。
nodeId为10233102的Pastry节点维护的状态示意图
上图给出了一个节点维护的数据示意图，b取值为2，所有的数均是4进制的。其中路由表的最上面一行是第0行。路由表中每行的阴影项表示当前节点号中相应的数位。路由表中每项节点的nodeId表示格式是“相同前缀 ＋ 下一数位 ＋ nodeId的剩余位”。图中没有列出相关节点的IP地址。
路由表每行包括2b-1个表项。第n行的2b-1个表项中，每个节点nodeId的前n个数位和当前节点nodeId的前n个数位相同，而第n＋1个数位和当前节点不同。b的取值是路由表大小和任意两节点间需要的最大路由跳数之间的折衷。例如，当b取4而网络中有106 个节点时，每个节点的路由表平均包括75个表项，预期的路由跳数是5。如果网络中有109个节点，则路由表平均会有105项，而预期的路由步数也将增加到7。
叶子节点集维护的是nodeId和本节点最接近的节点，其中一半是nodeId大于当前节点的，另一半是nodeId小于当前节点的。叶子节点集在路由时需要用到。邻居节点集维护按给定的评测指标距离本节点最近的节点，正常的路由过程并不使用邻居节点集，它的主要作用是维护路由的本地性。通常这两个集合的大小分别为2b或者2×2b。
Pastry的路由过程是：节点收到一条查询消息时，首先检查该消息的关键字是否落在叶子节点集范围内。如果是，则直接把消息转发给对应的节点，也就是叶子节点集中nodeId和关键字最接近的节点。如果关键字没有落在叶子节点集范围内，节点就会把消息转发给路由表中的一个节点，该节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId和关键字的相同前缀长一个数位。如果路由表中相应的表项为空，或者表项中对应的节点不可达，这时候查询消息将被转发给前缀长度相同但是节点号数值更接近关键字的节点。除非消息已经到达目的节点，否则这样的节点一定位于叶子节点集中。而且，只要叶子节点集中一半以上的节点不同时失效，就一定可以找到满足要求的节点。很明显，路由的每一步都比上一步向目标节点前进了一步，因此路由过程总是收敛的。
节点加入和退出
新节点加入时需要初始化自身的状态表，并通知其他节点自己已经加入系统。假定新加入节点的nodeId为X，同时假定X在加入Pastry之前知道系统中和自己距离相近的节点A。新节点X首先请求A路由一条“加入”消息，消息的关键字就是X。这条消息最终会到达nodeId和X最接近的节点Z。作为应答，节点A、节点Z以及从A到Z的路径上所有经过的节点都会把自己的状态表发送给节点X。节点X利用这些信息初始化自己的状态表，然后节点X再通知其他节点它已经加入了系统。从交换的消息数量上说，节点加入操作的复杂度为O（log2bN）。
Pastry中节点很可能失效或者突然离开系统。若nodeId空间中的相邻节点无法和某个节点通信时，就认为该节点失效了。一旦节点检测出其叶子节点集L中的某个节点失效，它就会请求该集合中nodeId最大或最小的节点把其叶子节点集L’发送过来。（如果失效节点的nodeId比当前节点的nodeId大，则用叶子集中nodeId最大的节点，反之则用nodeId最小的节点。）当前节点将从L’中选择一个L中没有的活动节点来替代失效节点。如果节点检测出其路由表中某项对应的节点失效，它将从该项所在的路由表行中选择另一个节点，要求该节点把路由表中对应位置的项发过来。如果当前节点的路由表中对应行已经没有可用节点了，那么当前节点将从路由表的下一行中选择一个节点，这个过程将继续到当前节点能够得到一个替代失效节点的节点号，或者当前节点遍历了路由表为止。节点也会周期性地和邻居节点集中的节点交换信息以检测这些节点是否仍在Pastry系统中，如果节点检测出其邻居节点集中的某个节点失效，它将请求其他邻居节点把其邻居节点集发送过来并从中选择一个新的邻居节点替换失效节点。
3 CAN
UC Berkeley提出的CAN（Content Addressable Network，内容寻址网络）实现了文件索引和存放位置的有效映射，不需要任何形式的中央控制点，节点只需要维护少量的控制状态而且状态数量独立于系统中的节点数量，具有完全自组织和分布式的结构，并且有良好的可扩展性和容错性。
CAN的设计
CAN的设计基于虚拟的d维笛卡儿坐标空间，这个坐标空间完全是逻辑的，和任何物理坐标系统都没有关系。在任何时候，整个坐标空间动态地分配给系统中的所有节点，每个节点负责维护独立的互不相交的一块区域。CAN中的节点自组织成一个代表这个虚拟坐标空间的重叠网络（overlay network）。每个节点要了解并维护相邻区域中节点的IP地址,用这些邻居信息构成自身的坐标路由表。有了这张表，CAN可以在坐标空间中任意两点间进行寻路。
下图给出了一个2维的[0, 1]×[0, 1]的笛卡儿坐标空间划分成五个节点区域的情况。虚拟坐标空间采用下面的方法保存（K, V）对。当保存（K1, V1）时，使用统一的哈希函数把关键字K1映射成坐标空间中的点P。那么这个值将被保存在该点所在区域的节点中。当需要查询关键字K1对应的值时，任何节点都可以使用同样的哈希函数找到K1对应的点P，然后从该点对应的节点取出相应的值V1。如果此节点不是发起查询请求的节点，CAN将负责将此查询请求转发到P所在区域的节点上。因此，有效的路由机制是CAN中的一个关键问题。
五个节点维护的CAN虚平面
CAN的路由
CAN中的路由很简单，沿着坐标空间中从发起请求的点到目的点之间的一条路径转发即可。为此，每个CAN节点都要保存一张坐标路由表，其中包括它的邻居节点的IP地址和其维护的虚拟坐标区域。两个节点互为邻居是指：在d维坐标空间中，两个节点维护的区域在d－1维的坐标上有重叠而在剩下的一维坐标上相互邻接。例如，图2.6中D和E是邻接节点，而D和B就不是邻接节点, 因为D和B在X轴和Y轴上都邻接。每条CAN消息都包括目的点坐标。路由时节点只要朝着目标节点的方向把消息转发给自己的邻居节点即可。下图给出了查找过程的一个简单的例子。
如果一个d维空间划分成n个相等的区域，那么平均路由长度是(d/4)(n1/d)，每个节点只需要维护2d个邻居节点的信息。这个结果表明CAN的可扩展性很好，节点数增加时每个节点维护的状态信息不变，而路由长度只是以O（n1/d）的数量级增长。因为坐标空间中两点之间可以有许多条不同的路径，所以单个节点的失效对CAN基本上没有太大的影响。遇到失效节点时，CAN会自动沿着其他的路径进行路由。
节点加入和退出
因为整个CAN空间要分配给系统中现有的全部节点，当一个新的节点加入网络时必须得到自己的一块坐标空间。CAN通过分割现有的节点区域实现这一过程。它把某个现有节点的区域分裂成同样大小的两块，自己保留其中的一块而另一块分给新加入的节点。整个过程分为以下三步：
1. 新节点首先找到一个已经在CAN中的节点。
2. 新节点使用CAN的路由机制找到一个区域将要被分割的节点。
3. 执行分割操作，然后原有区域的邻接区域必须被告知发生了分割，这样新节点才能被别的节点路由到。
当节点离开CAN时，必须保证它的区域被系统中剩余的节点接管，也即分配给其他仍然在系统中的节点。一般是由某个邻居节点来接管这个区域和所有的索引数据（K，V）对。如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的区域，那么将由这个邻居节点执行合并操作。否则，该区域将交给其邻居节点中区域最小的节点负责。也就是说，这个节点将临时负责两个区域。
正常情况下，每个节点向其所有邻居节点发送周期性的更新消息，消息中包括自身的区域范围、它的邻居列表以及这些邻居节点负责的区域范围。如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了。这时，节点将启动接管机制，并启动一个时钟。失效节点的每个邻居节点相互独立地执行该过程，每个时钟大小都和相应节点负责的区域面积成比例。如果时钟超时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。当某个节点接收到接管消息后，如果它的区域面积比发出消息的节点大，那么它将取消接管操作。否则它将发出自己的取代消息。采用这种机制可以有效地选择面积最小的邻居节点来接管失效节点。在特殊情况下，还有可能出现多个相邻的节点同时失效的情况。例如，节点检测到某个节点失效，但是失效节点地邻居中超过一半可能都不可达。这时，如果让该节点接管失效节点地区域，就有可能导致CAN中状态不一致。所以在这种情况下，CAN在执行修复操作之前，会搜索失效区域附近的节点，搜索逐步扩大直至获得足够的邻居状态，以便安全地开始接管过程。
4 Tapestry
Tapestry是UC Berkeley提出的一种新型的P2P网络定位和路由算法。该算法可以对消息进行与位置无关的路由，把查询消息传递到最近的存储有目标对象拷贝的节点。Tapestry具有自组织、容错和负载平衡等特点。每个Tapestry 节点只需维护O（log N）大小的路由表信息，路由最多在O（log N）跳数内完成。
Tapestry的设计
Tapestry从一个标识符空间中为每个节点随机分配一个节点标识符nodeID，对象也从同一个标识符空间中分配一个全局唯一标识符GUID（globally unique identifier）。Tapestry使用SHA-1来产生标识符，使得nodeID和GUID均匀分布在标识符空间中。为了讨论问题的方便，用Nid来表示节点N的标识符，用OG表示对象O的标识符。Tapestry目前使用160比特的标识符空间，标识符用一个全局统一的进制表示（例如使用16进制，则标识符是一个40位的数字），所有的节点依据标识符自组织成一个重叠网络。
Tapestry动态地把每个标识符G映射到当前系统中一个节点上，该节点称为G的根节点，表示为GR。如果某节点的Nid＝G，则这个节点就是G的根节点。为了转发查询消息，每个节点需要维护一个邻居映射表，每个表项包括一个邻居节点的标识符和IP地址。往GR路由时，消息将沿着邻居指针向节点标识符在标识符空间中更接近G的节点转发（例如，匹配更大的前缀）。
Tapestry中的每个节点都保存有邻居映射表。邻居映射表可以用于把消息按照目的地址一位一位地向前传递，比如从4***=>42**98=>42A*=>目的节点42AD（这里*表示通配符）。这种方式类似于IP分组转发过程中的最长前缀匹配。节点N的邻居映射表分为多个级别，每个级别包含的邻居节点的数量等于标识符表示法的基数，而每个级别中邻居节点标识符和本节点标识符的相同前缀都比前一级别多一个数位。也就是说，第j级邻居表的第i项是标识符以prefix(N, j-1) ＋ “i”为前缀而且离当前节点最近的邻居节点。例如，节点325AE的邻居映射表中第4级第9项是系统中标识符以325 + “9” =3259为前缀的某个节点。
上图给出了一个节点的邻居指针实例，从图中可以看到第一级的邻居节点标识和本节点标识没有共同前缀，而第二级的邻居节点标识都以4开头，即和本节点标识具有相同的一个数位的前缀。
Tapestry采用的基本查找和路由机制：当一条查找消息到达传递过程中的第n个节点时，该节点和目的节点的共同前缀长度至少大于n。为了进行转发，该节点将查找邻居映射表的第n+1级中和目的标识符下一数位相匹配的邻居节点。转发过程将在每个节点中依次进行直到到达目的节点。这种方法可以保证路由至多经过logbN个节点就可以到达目的节点，这里N是节点标识符名字空间的大小，而b是标识符使用的基数。同样，由于每个节点的邻居映射表的每个级别只需要保存b个表项，因此，邻居映射表的空间为blogbN。 [...]
[zz]SMP系统与MPP系统比较
5 01月 2008转载自这里。
SMP (Symmetric Multi Processing),对称多处理系统内有许多紧耦合多处理器，在这样的系统中，所有的CPU共享全部资源，如总线，内存和I/O系统等，操作系统或管理数据库的复本只有一个，这种系统有一个最大的特点就是共享所有资源。
MPP (Massively Parallel Processing)，大规模并行处理系统，这样的系统是由许多松耦合的处理单元组成的，要注意的是这里指的是处理单元而不是处理器。每个单元内的 CPU都有自己私有的资源，如总线，内存，硬盘等。在每个单元内都有操作系统和管理数据库的实例复本。这种结构最大的特点在于不共享资源。
既然有两种结构，那它们各有什么特点呢？采用什么结构比较合适呢？通常情况下，MPP系统因为要在不同处理单元之间传送信息（请注意上图），所以它的效率要比SMP要差一点，但是这也不是绝对的，因为MPP系统不共享资源，因此对它而言，资源比SMP要多，当需要处理的事务达到一定规模时，MPP的效率要比SMP好。这就是看通信时间占用计算时间的比例而定，如果通信时间比较多，那MPP系统就不占优势了，相反，如果通信时间比较少，那MPP系统可以充分发挥资源的优势，达到高效率。当前使用的OTLP程序中，用户访问一个中心数据库，如果采用SMP系统结构，它的效率要比采用MPP结构要快得多。而MPP系统在决策支持和数据挖掘方面显示了优势，可以这样说，如果操作相互之间没有什么关系，处理单元之间需要进行的通信比较少，那采用MPP系统就要好，相反就不合适了。
通过上面两个图我们可以看到，对于SMP来说，制约它速度的一个关键因素就是那个共享的总线，因此对于DSS程序来说，只能选择MPP，而不能选择 SMP，当大型程序的处理要求大于共享总线时，总线就没有能力进行处理了，这时SMP系统就不行了。当然了，两个结构互有优缺点，如果能够将两种结合起来取长补短，当然最好了。
Non-centric p2p computing model的一些设想 2
23 12月 2007知行合一，还是回头看看系统的一些具体设计应该是怎么样的吧。
这个社会拟态计算网络有哪些特点呢？大概发散思考一下：节点独立、自洽，热上线、下线（动态接入），自动网络发现，自组织，等等。
协议：SOA常用技术均可。
接入：如果A已经在network中，B只需要（知道、认识）A就可以接入network。
断开：假设A断开接入，所有认识A的节点都会主动发现（心跳探测）到A的断开。
承担社会责任：接入网络的节点会对每一次心跳探测反馈和声明自己的胜任能力，以期待别人能够把工作分配给他。（劳动成为一种社会需要）
工作优先原则：把自己的工作分配给请求劳动的节点的节点，会评估所有有劳动力的节点谁最适合该工作（例如，该计算需要的数据在节点的本地磁盘上），然后分配给最适合的。
任务发起（工作产生）：第一种是自洽网络中的某节点触发发起；第二种是神迹（来自系统外的信号）发起。
神的检视：提供从外部观察网络的接口
先这么多。。。待续
Non-centric p2p computing model的一些设想
23 12月 2007首先说明的是，此文纯属本人胡思乱想，没有经过什么深思熟虑，更未有文献的支持佐证，只是一个萌芽期的头脑风暴（一个人的，哈哈）而已。
非中心点对点计算模型应该是从tracker-based的p2p计算模型发展而来。当然，tracker-based p2p应该是从master-slave cluster发展来的。
tracker比起来master，已经简化了太多了，随便列一下就能列出不少：
1. 无须维护任务队列；
2. 无须负责任务调度；
3. 无须负责失败处理；
4. ……
似乎tracker简化的还剩下一个功能，就是提供所有（是吗？我不确定）计算节点的状态信息的注册和发现。
再进一步简化的结果就是tracker连注册和发现的功能也不需要了，trackerless。当然，如果这样，一个新的节点如何接入呢？
我想，应该是p2p network里任意一个节点都可以做他的entry point。然后他就应该可以通过这一个节点发现整个network。
如果和人际圈类比，真的是有异曲同工之妙呀！
互联网应用层讲社会化网络，我觉得技术层应该讲社会化计算，或者不妨叫做社会拟态计算。最终整个计算网络的工作原理将完全可以按照人际社会的原理来实作出来，甚至连PRD都可以省了，因为人际社会就是一个范本啦，哈哈。
甚至可以大胆的设想，建立在碳元素基础上的肉体的人类，不久将更主要的生活在一个建立在硅元素之上的环境里，享受着create any, share any的快乐。