P2P技术科普(二)—- 非结构化P2P及其搜索方法

上集回顾,传统的‘客户端/服务器’模式有一些问题,比如,单一故障点,低资源利用率,高带宽要求。我说P2P客服了这些问题,因为没有中央服务器了。这里,我要强调一下,并不是说只要有中央的东西就是失败,只要这个中央的东西不是那个实际掌握资源的人就可以接受。下面,简要介绍一下P2P技术的发展。

 

第一代,Napster

这一代的p2p只是把资源从服务器上拿掉了。中央服务器上只有一个目录。这个目录记录着哪个用户有哪些资源。要建立这样的一个目录,要求网络中的每个人都要告诉这个服务器:他有什么资源。

1,  Kaka发一个资源请求向中央服务器。

2,  这个服务器然后检索目录,并告诉Kaka,日天有他要的东西。

3,  Kaka直接去找日天下东西。

这样做,解决了高带宽需求(服务器只需要转发一些消息,而不用真格的提供资源),低资源利用率的问题(网络里谁都可以发挥作用了)。但是,他仍然面临严重的‘单一故障点’风险。同时,napster的出现严重挑战了知识产权法,并最终导致其在2001年被勒令关闭。

 

第二代,非结构化P2P

Napster帝国的坍塌,导致了江湖上群雄并起,老的规矩也就法不责众了,其中Gnutella等非结构的P2P脱颖而出。非结构化说白了就是,用户之间瞎连,没有规定谁必须和谁有连接,基本随机。其基本搜索方法是地毯式的,如果这样的搜索能够遍及整个网络。那么,只要资源存在就一定能一网打尽。

但是上天要求每一个用户都要给自己资源请求加一个限制,于是每个资源请求都只能走几步就必须停了,即使什么都还没找到。因为地毯式的搜索要消耗大量的网络资源,比如,平均一个人有4个邻居,如果资源请求的限制为5. 那么一共需要4+42+43+44+45=1364个信息,每个信息多大呢?大概k到几十k,也就是说一个信息就至少几m。一个人一个信息就这么大了,想想一个大网络,每人十几个邻居,限制提高到78. 这就是为什么中国很多地方,尤其是网吧限制p2p. 因为他们可怜的带宽都被p2p的请求信息占用了。

 

当然,p2p的设计者们都看到了问题,于是提出了很多新的搜索方法。这些方法可以分成两种:一种根据以前的搜索信息对以后的搜索进行预测。一种就是瞎找,碰运气

1,根据经验的搜索准确率可能会高一点,但是这种方法要求每个用户都要建一些表来记录以前的数据,而且每次发送或接到请求都要经过一系列的计算才能决定发给哪个邻居。而且程序上难以实现,更重要的是平均准确率并不比瞎找好很多。这里就不多做介绍了。

2,瞎B找的,还基本上以地毯式为基础。我介绍两种最常见的:

l  K-walkers: 第一个人先把消息发给k邻居,具体多少都自己定。 然后从第一轮邻居开始都只把消息转发给他们的一个邻居。

l  水纹式(涟漪式):先定一个限制。第一个人先发给第一层的邻居。如果第一层不灵,他们再发给他们的邻居。一旦找到资源就不再继续了。这样的话最坏的情况就是原始的地毯式。好点的情况就是,消息没到限制就找到了相应的资源,就停了。

 

这种非结构的p2p的优点在于,操作简单,完全不需要中央控制,所以又称为‘存(纯)p2p’。其缺点同样明显,要么牺牲搜索成功率,要么牺牲带宽占有量。

 

于是又有人提出了结构化的P2P。数学的东西我就不说了,基本的思想就是:

1,  每个用户,资源都得有个名字。

2,  有一种数学加密方法,对这些名字加密。且保证如果名字不同,那么得到的结果就不同。

3,  如一资源和一用户加密后结果接近,就把该资源的地址放到相应的用户身上。

 

举个例子:

有三个人,日天,kaka,威哥。三个资源:“一剪梅.mp3,“八荣八耻歌歌词.txt,xxx.avi

对这留个东西加密后分别得到: 1002003000 3002 23398

‘xxx.avi’的下载地址就会被分配到‘日天’的机子上,于是当你想搜索“xxx.avi”,你的消息就会通过某种方法被传到到日天那。

 

这样,结构化的P2P就可以保证,只要网络里有相应的资源,就一定能找到。但是由于其程序实现的难度,加之维护网络所需的投入太大,并不被经常使用。尽管他有很漂亮的数据。

 

当然还有第三代的,以后再做专题。

 

下集预告:BT基本原理

(为什么只有BitTorrent才是人越多就越快? 有何缺陷?)