在分布式系统中，资源的查找是个很重要也很棘手的问题，一般的说来主要有两种方式
- 一种采用集中式的查找，有一个索引服务器，p2p的开山鼻祖Napster就是这种这种方式，还有诸如LDAP，都是这种方式的代表。这种方式虽然查找起来方便，但是容易受攻击，目录服务器垮了这个系统也就不行了。这显然不能满足p2p的技术要求（但是在其他的distributed系统中，如grid中却可以应用的很好），p2p是针对于一般用户的，它的准入策略不能太严格，在开始的情况下，只能假定所有人都是善意的。
- 另一种查找方式就是分散式的查找。在Napster因法律问题而受到打压以后，研究人员开始明白仅仅文件时分散是不够的，p2p就是要完全的decentrlized/去中心化，但是怎么解决查找的问题，很自然的一个思路就是采取一种“洪泛”的策略，我把我要查找的信息告诉所有我知道的邻居，他们告诉他们知道的下一家，这样递归的查找下去，最终肯定可以找到所需要的资源。采用这种方式最主要的有Gnutella和Freenet，为了采用目录服务器p2p system(Napster)相区分开，一般把以Gnutella/Freenet为代表的p2p system称之为第二代p2p system，而把Napster等称为第一代p2p system。
这种分散式的查找方式虽然更加符合p2p的初始精神，Decentrlized，Anonymity，Robustness。但是采用“洪泛”的一个显然的弱点是网络里的流量会以指数级的方式迅速增长，这样这种p2p system的参与peer不能太多，否则网络将会因为拥赛而垮掉。但是很不幸，p2p面对可以说就是草根，如果得不到用户，那么它还有什么意义呢？
行文至此，p2p系统3年前面临的困境要怎样解决呢？Napster方式肯定不适合，首先就不符合p2p的精神，甚至不能真正称之为一个p2p system。
那么对第二代的p2p system能做什么，自然是改造。控制拥塞是网络里面的老课题，也有很多经验和成熟的技术可用，只是应用环境变了。事实上，现在这种结构p2p system研究者的热点也是集中在这里：怎么样在保证通讯质量的同时，尽量减少通讯量。
好了，终于轮到DHT和Chord出场了。Creativity！在对原有系统修修补补的同时，另外一些研究者确在思考全新的解决方案。既然集中式和分散式各有优缺点，而且看起来它们之间还是互不的，那么能不能把它们结合起来呢 ？既不完全分散也不完全集中。把所有索引信息，分别存放在很多节点之上，但是这又不能和那种多级索引一样，虽然分散了索引，但是仍然有顶级节点，一旦最上面的索引服务器垮掉，整个系统还是垮了。所以最好还是平面结构，而不要是层次式结构。在一个平面上，能购查找的算法，大家能想到什么？哈希表，也许你已经想到了。而这也正是Chord研究者们所想到的，DHT的全称Distributed Hashing Table，分布式哈希表。从这个名称似乎已经隐约可见端倪了，它的思想正是上面所提到的那样。不过为了哈希表放到不同的节点之上，还是做了很精心的设计的，Chord的设计也是非常巧妙的。
p2p的研究到此似乎也就走出了困境，而各种DHT算法也在Chord之后如雨后春笋般的发展起来了。由于基于DHT的p2p system和以前的p2p system之间的一个显著的区别是为了保证各个节点能够hash到另外的节点。所有节点的ID必须是预先规定的。因此被称为structured p2p system,有结构的p2p系统。把以前洪泛的p2p 系统称为unstructured p2p system，无结构的p2p系统。
毫无疑问，DHT是killer级的算法/技术。而使DHT深入人心的正是Chord，看Chord的文章，似乎在他们之前还有类似的想法（Plaxton，CAN），但是也许Plaxton的作者自己都没有太清楚的认识到他们想法的意义。Chord却明确了DHT作为p2p system的基础的地位。
我自己以为，p2p研究正是在此以后，才获得了非凡的理论意义和基础。以前的p2p思想要么不成熟，要么依附于其他的CS分支。p2p研究正式成为CS科学家和应用者都认可的分布式系统。
博文
没有评论:
发表评论