P2P网络的拓扑结构
拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，结点之间的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集中式、层次式等拓扑结构。Internet本身是世界上最大的非集中式的互联网络，但是九十年代所建立的一些网络应用系统却是完全的集中式的系统，许多Web应用都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临着过量存储负载、DOS（Denial of Service，拒绝服务）攻击，网络带宽限制等一些难以解决的问题。Peer-to-Peer (简称P2P) 系统主要采用非集中式的拓扑结构，一般来说不存在上述这些难题。根据结构关系可以将P2P系统细分为四种拓扑形式：
-
中心化拓扑（Centralized Topology）；
-
全分布式非结构化拓扑（Decentralized Unstructured Topology）；
-
全分布式结构化拓扑（Decentralized Structured Topology，也称作DHT网络）；
-
半分布式拓扑（Partially Decentralized Topology）。
其中，中心化拓扑最大的优点是维护简单，资源发现效率高。由于资源的发现依赖中心化的目录系统，发现算法灵活高效并能够实现复杂查询。最大的问题与传统客户机/服务器结构类似，容易造成单点故障，访问的“热点”现象和版权纠纷等相关问题，这是第一代P2P网络采用的结构模式，经典案例就是著名的MP3共享软件Napster[1].
Napster是最早出现的P2P系统之一，并在短期内迅速成长起来。它实质上并非是纯粹的P2P系统，而是通过一个中央索引服务器保存所有Napster用户上传的音乐文件索引和存放位置的信息。它的工作原理如图1所示。当某个用户需要某个音乐文件时，首先连接到Napster中央索引服务器，在服务器上进行检索，服务器返回存有该文件的用户信息，再由请求者直接连到文件的所有者传输文件。Napster首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统的文件传输延时。
图1 Napster的拓扑结构
然而，这种对等网络模型存在以下这些问题：
- 中央索引服务器的瘫痪容易导致整个网络的崩溃，因此可靠性和安全性较低。
- 随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本较高。
- 中央索引服务器的存在常引起版权问题上的纠纷，服务提供商容易被追究法律责任。
综合上述优缺点，对小型网络而言，中心化拓扑模型在管理和控制方面占一定优势。但鉴于其存在的上述缺陷，该模型并不适合大型网络应用。
全分布式非结构化拓扑的P2P网络是在重叠网络（Overlay Network）(见标注1)采用了随机图的组织方式，结点度数服从Power-law规律（幂次法则）[2]，从而能够较快发现目的结点，面对网络的动态变化体现了较好的容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带有规则表达式的多关键词查询，模糊查询等，采用这种拓扑结构最典型的案例便是Gnutella（音译：纽特拉）。准确地说，Gnutella不是特指某一款软件，而是指遵守Gnutella协议[3]的网络以及客户端软件的统称。目前基于Gnutella网络的客户端软件非常多，著名的有Shareaza、LimeWire和BearShare等。
图2Gnutella的拓扑结构和文件检索方法
Gnutella和Napster最大的区别在于Gnutella是更加纯粹的P2P系统，因为它没有中央索引服务器，每台机器在Gnutella网络中是真正的对等关系，既是客户机同时又是服务器，所以被称为对等机(Servent，Server+Client的组合)。在文件检索方面，它与Napster也不相同。在Gnutella网络的发展初期，它主要采用基于完全随机图的Flooding搜索算法。图2 显示了Flooding的工作流程：当一台计算机要下载一个文件，它首先以文件名或者关键字生成一个查询，并把这个查询发送给与它相连的所有计算机，这些计算机如果存在这个文件，则与查询的机器建立连接，如果不存在这个文件，则继续在自己相邻的计算机之间转发这个查询，直到找到文件为止。为了控制搜索消息不至于永远这样传递下去，一般通过TTL (Time To Live)的减值来控制查询的深度。
但是，随着联网节点的不断增多，网络规模不断扩大，通过这种Flooding方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。所以在初期的Gnutella网络中，存在比较严重的分区，断链现象。也就是说，一个查询访问只能在网络的很小一部分进行，因此网络的可扩展性不好。所以，后来许多研究人员在Flooding的基础上作了许多改进，例如采用Random work [4]、Dynamic Query[5]等方法。
由于非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没有遵循某些预先定义的拓扑来构建。这些系统一般不提供性能保证，但容错性好，支持复杂的查询，并受结点频繁加入和退出系统的影响小。但是查询的结果可能不完全，查询速度较慢，采用Flooding查询的系统对网络带宽的消耗非常大，并由此带来可扩展性差等问题。
全分布式结构化拓扑的P2P网络主要是采用分布式散列表（Distributed Hash Table, 简写成DHT）技术来组织网络中的结点。DHT是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。通过加密散列函数，一个对象的名字或关键词被映射为128位或160位的散列值。分布式散列表起源于SDDS（Scalable Distribute Data Structures）[6]研究，Gribble等实现了一个高度可扩展，容错的SDDS集群。DHT类结构能够自适应结点的动态加入/退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。只要目的结点存在于网络中DHT总能发现它，发现的准确性得到了保证，最经典的案例是Tapestry，Pastry，Chord和CAN。
Tapestry [7]提供了一个分布式容错查找和路由基础平台，在此平台基础之上，可以开发各种P2P应用(OceanStore[8]即是此平台上的一个应用)。Tapestry的思想来源于Plaxton。在Plaxton中，结点使用自己所知道的邻近结点表，按照目的ID来逐步传递消息。Tapestry基于Plaxton的思想，加入了容错机制，从而可适应P2P的动态变化的特点。OceanStore是以Tapestry为路由和查找基础设施的P2P平台。它是一个适合于全球数据存储的P2P应用系统。任何用户均可以加入OceanStore系统，或者共享自己的存储空间，或者使用该系统中的资源。通过使用复制和缓存技术，OceanStore可提高查找的效率。最近，Tapestry为适应P2P网络的动态特性，作了很多改进，增加了额外的机制实现了网络的软状态（soft state），并提供了自组织、鲁棒性、可扩展性和动态适应性，当网络高负载且有失效结点时候性能有限降低，消除了对全局信息的依赖、根结点易失效和弹性差的问题。
Pastry 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构建大规模的P2P系统。如图3 所示，在Pastry中，每个结点分配一个128位的结点标识符号(nodeID) ，所有的结点标识符形成了一个环形的nodeID空间，范围从0到2128 - 1 ，结点加入系统时通过散列结点IP地址在128位nodeID空间中随机分配。网络结点的加入与退出，资源查询的过程可以参考文献[9]。
图3Pastry的消息路由
Chord [10]项目诞生于美国的麻省理工学院。它的目标是提供一个适合于P2P环境的分布式资源发现服务，它通过使用DHT技术使得发现指定对象只需要维护O(logN)长度的路由表。在DHT技术中，网络结点按照一定的方式分配一个唯一结点标识符(Node ID) ，资源对象通过散列运算产生一个唯一的资源标识符(Object ID) ，且该资源将存储在结点ID与之相等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，Chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字(Key) 映射到对应的结点(Node) 。从算法来看，Chord是相容散列算法的变体。
图4 Chord的拓扑形状
CAN(Content Addressable Networks)[11] 项目采用多维的标识符空间来实现分布式散列算法。CAN将所有结点映射到一个n维的笛卡尔空间中，并为每个结点尽可能均匀的分配一块区域。CAN采用的散列函数通过对(key, value) 对中的key进行散列运算，得到笛卡尔空间中的一个点，并将(key, value) 对存储在拥有该点所在区域的结点内。CAN采用的路由算法相当直接和简单，知道目标点的坐标后，就将请求传给当前结点四邻中坐标最接近目标点的结点。CAN是一个具有良好可扩展性的系统，给定N个结点，系统维数为d，则路由路径长度为O(n1/d) ，每结点维护的路由表信息和网络规模无关为O(d) 。
上述四种基于DHT的P2P系统的性能比较可以参照[12]。DHT这类结构最大的问题是DHT的维护机制较为复杂，尤其是结点频繁加入退出造成的网络波动（Churn）会极大增加DHT的维护代价。DHT所面临的另外一个问题是DHT仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。
半分布式拓扑结构（有的文献亦称作混杂模式，英文表达为Hybrid Structure）吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能较高（处理、存储、带宽等方面性能）的结点作为超级结点（英文表达为SuperNodes或者Hubs），在各个超级结点上存储了系统中其他部分结点的信息，发现算法仅在超级结点之间转发，超级结点再将查询请求转发给适当的叶子结点。半分布式结构也是一个层次式结构，超级结点之间构成一个高速转发层，超级结点和所负责的普通结点构成若干层次。采用这种结构的最典型的案例就是KaZaa。
图5 半分布式拓扑结构（网络中包含Super Node）
KaZaa是当前世界最流行的几款P2P文件共享软件之一。根据CA公司统计，全球KaZaa的下载量超过2.5亿次。使用KaZaa软件进行文件传输消耗了互联网40%的带宽。之所以它如此的成功，是因为它结合了Napster和Gnutella共同的优点。从结构上来说，它使用了Gnutella的全分布式的结构，这样可以是系统更好的扩展，因为它无需中央索引服务器存储文件名，它是自动的把性能好的机器成为SuperNode，它存储着离它最近的叶子节点的文件信息，这些SuperNode,再连通起来形成一个Overlay Network. 由于SuperNode的索引功能，使搜索效率大大提高。
图6 KaZaa的软件界面
半分布式结构的优点是性能、可扩展性较好，较容易管理，但对超级点依赖性大，易于受到攻击，容错性也受到影响。
在实际应用中，每种拓扑结构的P2P网络都有其优缺点，下表从可扩展性、可靠性、可维护性、发现算法的效率、复杂查询等方面比较了这四种拓扑结构的综合性能。
|
比较标准／拓扑结构
|
中心化拓扑
|
全分布式非结构化拓扑
|
全分布式结构化拓扑
|
半分布式拓扑
|
|
可扩展性
|
差
|
差
|
好
|
中
|
|
可靠性
|
差
|
好
|
好
|
中
|
|
可维护性
|
最好
|
最好
|
好
|
中
|
|
发现算法效率
|
最高
|
中
|
高
|
中
|
|
复杂查询
|
支持
|
支持
|
不支持
|
支持
|
我还是比较看好chord...虽然目前还有不少问题没有解决....
顺便附上一篇经典的chord论文: Chord: A Scalable Peertopeer Lookup Service for Internet Applications
http://www.blogjava.net/Files/heiyuchuanxia/chord_sigcomm.rar
posted @
2006-11-15 15:28 Stefanie 阅读(3427) |
评论 (0) |
编辑 收藏
最近的程序中总是出现写奇怪的问题....于是乎就查了一点相关的资料....找到了这样一片相关的文章....感觉收获挺多了..... 分享分享.......
关于Java 初始化，有多文章都用了很大篇幅的介绍。经典的<<Thinking in java>>更是用了专门的一章来介绍Java初始化。但在大量有代码实例后面，感觉上仍然没有真正深入到初始化的本质。
本文以作者对JVM的理解和自己的经验，对Java的初始化做一个比深入的说明，由于作者有水平限制，以及JDK各实现版本的变化，可能仍然有不少错误和缺点。欢迎行家高手赐教。
要深入了解Java初始化，我们无法知道从程序流程上知道JVM是按什么顺序来执行的。了解JVM的执行机制和堆栈跟踪是有效的手段。可惜的是，到目前为止。JDK1。4和JDK1。5在javap功能上却仍然存在着BUG。所以有些过程我无法用实际的结果向你证明两种相反的情况。
<<Thinking in java>>(第三版)在第四章一开始的时候,这样来描述Java的初始化工作:
以下译文原文:
可以这样认为,每个类都有一个名为Initialize()的方法,这个名字就暗示了它得在使用之前调用,不幸的是,这么做的话,用户就得记住要调用这个方法,java类库的设计者们可以通过一种被称为构造函数的特殊方法,来保证每个对象都能得到被始化.如果类有构造函数,那么java就会在对象刚刚创建,用户还来不及得到的时候,自动调用那个构造函数,这样初始化就有保障了。
我不知道原作者的描述和译者的理解之间有多大的差异,结合全章,我没有发现两个最关键的字"<clinit>"和"<init>"。至少说明原作者和译者并没有真正说明JVM在初始化时做了什么,或者说并不了解JVM的初始化内幕,要不然明明有这两个方法,却为什么要认为有一个事实上并不存在的"Initialize()"方法呢?
"<clinit>"和"<init>"方法在哪里？这两个方法是实际存在而你又找不到的方法，也许正是这样才使得一些大师都犯晕。加上jdk实现上的一些BUG，如果没有深入了解，真的让人摸不着北。
现在科学体系有一个奇怪的现象，那么庞大的体系最初都是建立在一个假设的基础是，假设1是正确的，由此推导出2，再继续推导出10000000000。可惜的是太多的人根本不在乎2-100000000000这样的体系都是建立在假设1是正确的基础上的。我并不会用“可以这样认为”这样的假设，我要确实证明"<clinit>"和"<init>"方法是真真实实的存在的：
package debug;
public class MyTest{
static int i = 100/0;
public static void main(String[] args){
Ssytem.out.println("Hello,World!");
}
}
执行一下看看,这是jdk1.5的输出：
java.lang.ExceptionInInitializerError
Caused by: java.lang.ArithmeticException: / by zero
at debug.MyTest.(Test.java:3)
Exception in thread "main"
请注意，和其它方法调用时产生的异常一样，异常被定位于debug.MyTest的<clinit>.
再来看：
package debug;
public class Test {
Test(){
int i = 100 / 0;
}
public static void main(String[] args) {
new Test();
}
}
jdk1.5输入：
Exception in thread "main" java.lang.ArithmeticException: / by zero
at debug.Test.<init>(Test.java:4)
at debug.Test.main(Test.java:7)
JVM并没有把异常定位在Test()构造方法中，而是在debug.Test.<init>。 当我们看到了这两个方法以后，我们再来详细讨论这两个“内置初始化方法”（我并不喜欢生造一些
非标准的术语，但我确实不知道如何规范地称呼他们）。
内置初始化方法是JVM在内部专门用于初始化的特有方法，而不是提供给程序员调用的方法，事实上“<>”这样的语法在源程序中你连编译都无法通过。这就说明，初始化是由JVM控制而不是让程序员来控制的。
类初始化方法：<clinit>
我没有从任何地方了解到<clinit>的cl是不是class的简写，但这个方法确实是用来对“类”进行初
始化的。换句话说它是用来初始化static上下文的。
在类装载（load）时，JVM会调用内置的<clinit>方法对类成员和静态初始化块进行初始化调用。它们的顺序按照源文件的原文顺序。
我们稍微增加两行static语句：
package debug;
public class Test {
static int x = 0;
static String s = "123";
static {
String s1 = "456";
if(1==1)
throw new RuntimeException();
}
public static void main(String[] args) {
new Test();
}
}
然后进行反编译：
javap -c debug.Test
Compiled from "Test.java"
public class debug.Test extends java.lang.Object{
static int x;
static java.lang.String s;
public debug.Test();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."":()V
4: return
public static void main(java.lang.String[]);
Code:
0: new #2; //class debug/Test
3: dup
4: invokespecial #3; //Method "":()V
7: pop
8: return
static {};
Code:
0: iconst_0
1: putstatic #4; //Field x:I
4: ldc #5; //String 123
6: putstatic #6; //Field s:Ljava/lang/String;
9: ldc #7; //String 456
11: astore_0
12: new #8; //class java/lang/RuntimeException
15: dup
16: invokespecial #9; //Method java/lang/RuntimeException."":()V
19: athrow
我们可以看到,类初始化正是按照源文件中定义的原文顺序进行。先是声明 static int x;
static java.lang.String s;
然后对int x和String s进行赋值：
0: iconst_0
1: putstatic #4; //Field x:I
4: ldc #5; //String 123
6: putstatic #6; //Field s:Ljava/lang/String;
执行初始化块的String s1 = "456";生成一个RuntimeException抛
9: ldc #7; //String 456
11: astore_0
12: new #8; //class java/lang/RuntimeException
15: dup
16: invokespecial #9; //Method java/lang/RuntimeException."":()V
19: athrow
要明白的是，"<clinit>"方法不仅是类初始化方法，而且也是接口初始化方法。并不是所以接口
的属性都是内联的，只有直接赋常量值的接口常量才会内联。而
[public static final] double d = Math.random()*100;
这样的表达式是需要计算的，在接口中就要由"<clinit>"方法来初始化。
下面我们再来看看实例初始化方法"<init>"
"<init>"用于对象创建时对对象进行初始化，当在HEAP中创建对象时，一旦在HEAP分配了空间。最先就会调用"<init>"方法。这个方法包括实例变量的赋值（声明不在其中）和初始化块，以及构造方法调用。如果有多个重载的构造方法，每个构造方法都会有一个对应的"<init>"方法。构造方法隐式或显示调用父类的构造方法前,总是先执行实例变量初始化和初始化块.同样，实例变量和初始化块的顺序也是按源文件的原文顺序执行，构造方法中的代码在最后执行：
package debug;
public class Test {
int x = 0;
String s = "123";
{
String s1 = "456";
//if(1==1)
//throw new RuntimeException();
}
public Test(){
String ss = "789";
}
public static void main(String[] args) {
new Test();
}
}
javap -c debug.Test的结果：
Compiled from "Test.java"
public class debug.Test extends java.lang.Object{
int x;
java.lang.String s;
public debug.Test();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."":()V
4: aload_0
5: iconst_0
6: putfield #2; //Field x:I
9: aload_0
10: ldc #3; //String 123
12: putfield #4; //Field s:Ljava/lang/String;
15: ldc #5; //String 456
17: astore_1
18: ldc #6; //String 789
20: astore_1
21: return
public static void main(java.lang.String[]);
Code:
0: new #7; //class debug/Test
3: dup
4: invokespecial #8; //Method "":()V
7: pop
8: return
}
如果在同一个类中，一个构造方法调用了另一个构造方法，那么对应的"<init>"方法就会调用另一
个"<init>"，但是实例变量和初始化块会被忽略，否则它们就会被多次执行。
package debug;
public class Test {
String s1 = rt("s1");
String s2 = "s2";
public Test(){
s1 = "s1";
}
public Test(String s){
this();
if(1==1) throw new Runtime();
}
String rt(String s){
return s;
}
public static void main(String[] args) {
new Test("");
}
}
反编译的结果：
Compiled from "Test.java"
public class debug.Test extends java.lang.Object{
java.lang.String s1;
java.lang.String s2;
public debug.Test();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."":()V
4: aload_0
5: aload_0
6: ldc #2; //String s1
8: invokevirtual #3; //Method rt:(Ljava/lang/String;)Ljava/lang/String;
11: putfield #4; //Field s1:Ljava/lang/String;
14: aload_0
15: ldc #5; //String s2
17: putfield #6; //Field s2:Ljava/lang/String;
20: aload_0
21: ldc #2; //String s1
23: putfield #4; //Field s1:Ljava/lang/String;
26: return
public debug.Test(java.lang.String);
Code:
0: aload_0
1: invokespecial #7; //Method "":()V
4: new #8; //class java/lang/RuntimeException
7: dup
8: invokespecial #9; //Method java/lang/RuntimeException."":()V
11: athrow
java.lang.String rt(java.lang.String);
Code:
0: aload_1
1: areturn
public static void main(java.lang.String[]);
Code:
0: new #10; //class debug/Test
3: dup
4: ldc #11; //String
6: invokespecial #12; //Method "":(Ljava/lang/String;)V
9: pop
10: return
}
我们看到，由于Test(String s)调用了Test();所以"<init>":(Ljava/lang/String;)V不再对
实例变量和初始化块进次初始化：
public debug.Test(java.lang.String);
Code:
0: aload_0
1: invokespecial #7; //Method "":()V
4: new #8; //class java/lang/RuntimeException
7: dup
8: invokespecial #9; //Method java/lang/RuntimeException."":()V
11: athrow
而如果两个构造方法是相互独立的，则每个构造方法调用前都会执行实例变量和初始化块的调用：
package debug;
public class Test {
String s1 = rt("s1");
String s2 = "s2";
{
String s3 = "s3";
}
public Test() {
s1 = "s1";
}
public Test(String s) {
if (1 == 1)
throw new RuntimeException();
}
String rt(String s) {
return s;
}
public static void main(String[] args) {
new Test("");
}
}
反编译的结果：
Compiled from "Test.java"
public class debug.Test extends java.lang.Object{
java.lang.String s1;
java.lang.String s2;
public debug.Test();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."":()V
4: aload_0
5: aload_0
6: ldc #2; //String s1
8: invokevirtual #3; //Method rt:(Ljava/lang/String;)Ljava/lang/String;
11: putfield #4; //Field s1:Ljava/lang/String;
14: aload_0
15: ldc #5; //String s2
17: putfield #6; //Field s2:Ljava/lang/String;
20: ldc #7; //String s3
22: astore_1
23: aload_0
24: ldc #2; //String s1
26: putfield #4; //Field s1:Ljava/lang/String;
29: return
public debug.Test(java.lang.String);
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."":()V
4: aload_0
5: aload_0
6: ldc #2; //String s1
8: invokevirtual #3; //Method rt:(Ljava/lang/String;)Ljava/lang/String;
11: putfield #4; //Field s1:Ljava/lang/String;
14: aload_0
15: ldc #5; //String s2
17: putfield #6; //Field s2:Ljava/lang/String;
20: ldc #7; //String s3
22: astore_2
23: new #8; //class java/lang/RuntimeException
26: dup
27: invokespecial #9; //Method java/lang/RuntimeException."":()V
30: athrow
java.lang.String rt(java.lang.String);
Code:
0: aload_1
1: areturn
public static void main(java.lang.String[]);
Code:
0: new #10; //class debug/Test
3: dup
4: ldc #11; //String
6: invokespecial #12; //Method "":(Ljava/lang/String;)V
9: pop
10: return
}
明白了上面这些知识,我们来做一个小测试吧:
public class Test2 extends Test1{
{
System.out.print("1");
}
Test2(){
System.out.print("2");
}
static{
System.out.print("3");
}
{
System.out.print("4");
}
public static void main(String[] args) {
new Test2();
}
}
class Test1 {
Test1(){
System.out.print("5");
}
static{
System.out.print("6");
}
}
试试看能清楚打印的顺序吗?如果没有new Test2()将打印什么?
作者:axman 专栏:http://blog.csdn.net/axman/
posted @
2006-11-05 14:43 Stefanie 阅读(372) |
评论 (0) |
编辑 收藏
最近几年真是blog盛行,各式各样的blog,就我的blog也有不少,讲音乐的,平时的生活,还有就是写写看电影的感受,总的来说,有了blog,似乎生活也充实了不少......
blogjava的blog,我是打算专门写一些关于我专业方向的学习心得,也算是一个交流的平台吧.....
上了研,选择了web services这个方向,对于我应该也算是一个不小的挑战,这个领域涉及方方面面的东西,对于一个刚刚起步的我,也真是有很多地方需要好好学习.....
打算在此记录下我在web services之路上的点点滴滴......
posted @
2006-10-13 20:22 Stefanie 阅读(329) |
评论 (1) |
编辑 收藏