长沙大型网站建设,网页设计作业成品代码啊,阿里云clouder网站建设,品牌商城网站建设公司转自#xff1a;http://blog.csdn.net/wangxiaoqin00007/article/details/7374833 虽然网上搜索CHord#xff0c;一搜一大堆#xff0c;但大多讲得不太清楚明白。今天发现一篇blog#xff0c;图文并茂#xff0c;逻辑清楚且易懂#xff0c;特意转载收藏。 P2P的一个常见问…转自http://blog.csdn.net/wangxiaoqin00007/article/details/7374833 虽然网上搜索CHord一搜一大堆但大多讲得不太清楚明白。今天发现一篇blog图文并茂逻辑清楚且易懂特意转载收藏。 P2P的一个常见问题是如何高效的定位节点也就是说一个节点怎样高效的知道在网络中的哪个节点包含它所寻找的数据如下图 对此有三种比较典型的来解决这个问题。 Napster使用一个中心服务器接收所有的查询服务器告知去哪下载其所需要的数据。存在的问题是中心服务器单点失效导致整个网络瘫痪。 Gnutella使用消息洪泛message flooding来定位数据。一个消息被发到系统内每一个节点直到找到其需要的数据为止。当然使用生存时间TTL来限制网络内转发消息的数量。存在的问题是消息数与节点数成线性关系导致网络负载较重。 SN型现在大多数采用所谓超级节点Super NodeSN保存网络中节点的索引信息这一点和中心服务器类型一样但是网内有多个SN其索引信息会在这些SN中进行传播所以整个系统的崩溃几率就会小很多。尽管如此网络还是有崩溃的可能。 现在的研究结果中Chord、Pastry、CAN和Tapestry等常用于构建结构化P2P的分布式哈希表系统Distributed Hash TableDHT。 DHT的主要思想是首先每条文件索引被表示成一个(K, V)对K称为关键字可以是文件名或文件的其他描述信息的哈希值V是实际存储文件的节点的IP地址或节点的其他描述信息。所有的文件索引条目(即所有的K, V对)组成一张大的文件索引哈希表只要输入目标文件的K值就可以从这张表中查出所有存储该文件的节点地址。然后再将上面的大文件哈希表分割成很多局部小块按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上使得每个节点负责维护其中的一块。这样节点查询文件时只要把查询报文路由到相应的节点即可该节点维护的哈希表分块中含有要查找的(K,V)对。 这里介绍的Chord算法就是解决网络内节点定位问题的一种P2P协议。它通过多个节点跳转找到我们所查找的资源 我们先看看它是如何进行的随后再总结其特点和操作特征以及一些实现。 1.Chord里面的基本要素 节点IDNIDnode identifier表示一个物理机器m位的一个数字m要足够大以保证不同节点的NID相同的几率小的可以忽略不计由节点机器的IP地址通过哈希操作得到。 资源IDKIDkey identifiers原为键ID其实际表示一个资源因为Key与一个资源value哈希绑定故在本文中统称资源ID这样比较直观m位的一个数字m要足够大以保证不同资源的KID相同的几率小的可以忽略不计由Key通过哈希操作得到。 常哈希函数较之一般哈希函数节点的加入和离开对整个系统影响最小另外还有一些优势在此不赘述。在Chord中使用SHA-1来进行常哈希计算。 Chord环Chord RingNID和KID被分配到一个大小为2^m的环上用于资源分配给某一个节点和节点分布以及资源定位注在这个环上的ID为0--2^m-1。首先我们说资源分配资源被分配到NIDKID的节点上这个节点成为k的后继节点是环上从k起顺时针方向的第一个节点记为successor(k)。而节点分布则顺时针将节点N由大到小放在这个环上。例如下边这幅图 这是一个m6的环其中有10个节点5个资源K10的后继节点为N14也就是说K10被分配给了N14。 2.Chord资源定位Key Location 资源定位是Chord协议的核心功能为了便于理解我们先介绍一个简单的资源定位方法然后再介绍这个可伸缩的资源定位方法。 简单方法 考虑如下场景节点n寻找KID为id的资源此时节点n首先问询是否在下一个节点上find_successor这要看资源k的KID是否在该节点NID和下一个节点的NID之间若在则说明资源k被分配给了下一个节点若不在则在下一个节点上发起同样的查询问询下下一个点是否有该资源。如此迭代下去用伪代码定义这个操作 n.find_successor(id) if (id є (n; successor]) return successor; else // 将查询沿着环进行下去 return successor.find_successor(id); 例如下图 节点N8寻找K54这个资源N8.find_successor(K54)发现下一个节点N14不合符54є (8; 14]于是N14发起同样的搜索然后一跳一跳后直到节点N56满足54є (51; 56]于是得知资源K54在N56这个节点上。 在一个有N个节点的环上这样的查找方法显然在最坏的时候要查找N次才能得到所需资源的位置查找次数与节点个数成线性关系。显然这样的效率不给力所以Chord使用了可伸缩资源定位的方式来提高效率。 可伸缩方法 在每个节点N上都维护了最多有m项m为ID的位数的路由表称为finger table用来定位资源。这个表的第i项是该节点的后继节位置至少包含到2^(i-1)后的位置。还是延续上边的例子 节点N8的路由表中左边那一栏包含了N81到N8322^5-1的位置右边那一栏每个位置对应的实际存在的节点。比如N81-N14表示在N8后的第一个位置上的资源由N14来负责。这样记录有以下优势 每个节点只包含全网中一小部分节点的信息。 每个节点对于临近节点负责的位置知道的更多比如N8节点对于N14负责的位置知道3处而对N21负责的位置只知道1处。 路由表通常不包含直接找到后继节点的信息往往需要询问其他节点来完成。 当在某个节点上查找资源时首先判断其后继节点是不是就持有该资源若没有则直接从该节点的路由表从最远处开始查找看哪一项离持有资源的节点最近发现后跳转若没有则说明本节点自身就有要寻找的资源。如此迭代下去。 例如节点N8寻找K54这个资源 首先在N8上查找后继节点为N14发现K54并不符合54є (8; 14]的要求那么直接在N8的路由表上查找符合这个要求的表项由远及近查找此时N8的路由表为 我们发现路由表中最远的一项N832--N42满足42є (8; 54]则说明N42这个点离持有K54这个资源的节点最近因为N42在该路由表中离N8这个节点最远那么此时跳到N42这个节点上继续查找。N42的后继节点为N48不符合54є (42; 48]的要求说明N48不持有资源54此时开始在N42的路由表上查找 N42节点的路由表为 我们由远及近开始查找发现N428--N51满足51є (42; 54]则说明N51这个点离持有K54这个资源的节点最近那么此时跳到N51这个节点上继续查找。N51节点的后继节点为N56符合54є (51; 56]此时定位完成N56持有资源节点K54。 用伪代码表示 // 查询节点n后继节点。 n.find_successor(id) if (id є (n; successor]) return successor; else n0 closest_preceding_node(id); return n0.find successor(id); // search the local table for the highest // predecessor of id n.closest_preceding_node(id) for i m downto 1 if (finger[i] є (n; id)) return finger[i]; return n; 经证明最多经过O(log N)次查找就能找到一个资源。 3.Chord的节点加入 Chord通过在每个节点的后台周期性的进行stabilization询问后继节点的前序节点是不是自己来更新后继节点以及路由表中的项。 有三个操作 join(n0) n加入一个Chord环已知其中有一个节点n0. Stabilize(): n查询其后继节点的前序节点P来决定P是否应该是n的后续节点也就是说当p不是n本身时说明p是新加入的此时将n的后继节点设置为p。 Notify(n0): n0通知n它的存在若此时n没有前序节点或n0比n现有的前序节点更加靠近n则n将其设置为前序节点。 Fix_fingers(): 修改路由表。 具体的例如 这是原先的结构 现在N26节点要加入系统首先它指向其后继N32然后通知N32N32接到通知后将N26标记为它的前序节点predecessor。如下图 然后N26修改路由表如下图 下一次N21运行stabilize()询问其后继节点N32的前序节点是不是还是自己此时发现N32的前序节点已经是N26 于是N21就将后继节点修改为N26并通知N26自己已经将其设置为后继节点N26接到通知后将N21设置为自己的前序节点。 这个加入操作会带来两方面的影响 1)正确性方面当一个节点加入系统而一个查找发生在stabilization结束前那么此时系统会有三个状态 A.所有后继指针和路由表项都正确时对正确性没有影响。 B.后继指针正确但表项不正确查找结果正确但速度稍慢在目标节点和目标节点的后继处加入非常多个节点时。如下图 C.后继指针和路由表项都不正确此时查找失败Chord上层的软件会发现数据查找失败在一段时间后会进行重试。 总结一下节点加入对数据查找没有影响。 2)效率方面当stabilization完成时对查找效率的影响不会超过O(log N) 的时间。当stabilization未完成时在目标节点和目标节点的后继处加入非常多个节点时才会有性能影响。可以证明只要路由表调整速度快于网络节点数量加倍的速度性能就不受影响。 4.Chord节点失败的处理 我们可以看出Chord依赖后继指针的正确性以保证整个网络的正确性。但如图若N14, N21, N32同时失效那么N8是不会知道N38是它新的后继节点。为了防止这样的情况每个节点都包含一个大小为r的后继节点列表一个后续节点失效了就依次尝试列表中的其他后继节点。可以证明在失效几率为1/2的网络中寻找后继的时间为O(log N) 。 5.Chord的特征和应用 特征去中心化高可用度高伸缩性负载平衡命名灵活。 应用全球文件系统、命名服务、数据库请求处理、互联网级别的数据结构、通信服务、事件通知、文件共享。 参考文献 Chord项目网址http://pdos.csail.mit.edu/chord/ http://net.chinaunix.net/8/2008/07/28/1231438.shtml转载于:https://www.cnblogs.com/z-sm/p/5058176.html
