kademlia：定位节点.ppt

P2P网络体系(3) 大纲 第一代P2P网络：混合式P2P体系 第二代P2P网络：无结构P2P体系 第三代P2P网络：结构化P2P体系（＊） 第三代P2P网络：结构化P2P体系 ChordCFS CAN TapestryOceanStore PastryPast Kademlia SkipNet Viceroy Koorde Cycloid 其他著名结构化P2P网络 实践系统：，提出更加容错、实用的P2P系统，如Kademlia(2002)，路由方式类似Chord，但采用异或的距离量度，并将网络结构配置信息融合到每条消息中；SkipNet(2003)模型，类似Chord，但采用跳表SkipList数据结构，提供结点路由、对象语义两方面的局部性，以前的结构化P2P网络都没有做到 理论模型：具有特殊性质的新型结构化P2P模型——常数度P2P网络，其路由、定位、自组织方式与过去的模型区别不大，但每个结点的“度”（即连接数）是固定的，不随网络规模改变，保持路由效率的同时减小了自适应开销，常见模型有Viceroy(2002)、Koorde(2003)、Cycloid(2004) 实践系统 一、Kademlia 二、SkipNet 一、Kademlia：基于异或度量的P2P信息系统 由于“异或”是对称的，因此Kademlia结点能从路由消息中获得有用的网络配置信息，这种“捎带更新”方法使得Kademlia以很小的开销获得了很大的自适应性 Kademlia不像Chord需要严格的路由表，可以发送消息给其路由表任意一段(interval)中的每一个结点，让基于时延选择路由下一跳，甚至让它们发送并行的异步消息 Kademlia的应用 Kademlia的异或度量、结点状态和自组织 Kademlia结点、对象ID分配、以及索引负责方式同经典的P2P网络 设Kad网络中有两个结点，ID分别为x,y，其距离d(x,y)=x⊕y，d(x,y)=d(y,x)，具有对称性和三角属性，类似CAN、Tapestry和Pastry，不同于Chord 与Chord的顺时针环形度量一样具有单向性，保证了所有对相同数据对象的定位最终将会聚于相同的路径，且越往后走会聚的可能性越高 Kademlia的结点状态和自组织 每个Kad结点维护一个称为k-buckets的路由表，以采用160位ID为例，对每位i，结点都保存一个链表，称为一个k-bucket，其中记录到自己的异或距离在2i与2i+1之间的一些结点，并按照最近访问时间从尾到头排列 每个链表项是形如(IP, UDP port, nodeID)的三元组 i越大，其链表项越多，并呈指数增长，因此Kad网络给出链表长度上限k Kademlia特点 1、当Kad结点收到消息，用消息发送者的nodeID来更新相应的k-bucket，称为“捎带确认”piggy-backing，或捎带更新。 它还能有效地防止DoS攻击，攻击者无法用特定的nodeID填满其它结点的路由表，因为Kad网络只有检测到旧结点失效才会用新结点 2、路由主动更新：为保持路由表k-buckets的更新，如果某个路由表的所有结点在一个小时中未被查询，则从中任选一个ID对该结点做结点查询以刷新路由表 3、K个ID邻近复制：保证k个结点存储value，并且此k个结点每过一个小时就重新发布key, value对，以保证数据可用；同时还要求最初的发布者S结点每过24小时重新发布key, value，否则过期 4、为保持存储、查询的一致性，当任何一个结点A发现存在另一个结点B离保留在A上的键值对更近时，A会复制键值对到B，但不删除自己数据库中的键值对 Kademlia Binary Tree Subtrees of interest for a node 0011…… Kademlia Binary Tree Every node keeps touch with at least one node from each of its subtrees. (if there is a node in that subtree.) Corresponding to each subtree, there is a k-bucket. Kademlia Search 二、SkipNet：基于跳表、提供显式局部性的P2P模型 SkipNet通过“跳表”(SkipList)数据结构提供显式局部性，体现在两个方面 内容局部性，即语义上可控的对象放置，能够显式地指定数据对象的放置位置或放置范围 路由局部性，同一个组织中结点间消息路由的路径一定位于该组织内部 显式局部性是SkipNet的最大亮点，但也弱化了一致性散列函数的影响，不能提供很好的负载均衡；SkipNet通过折