3代表性DHT算法 ■Chord 基于分布式Hash表 ■Pastry (DHT:Distributed Hash Table ■CAN 结构化P2P: 直接根据查询内容的关键字定位其索引的存放节点 11
11 3 代表性DHT算法 Chord Pastry CAN 基于分布式Hash表 (DHT： Distributed Hash Table ) 结构化P2P: 直接根据查询内容的关键字定位其索引的存放节点
3.1 Chord:概述 UC Berkeley和MIT共同提出 ■采用环形拓扑(Chord:环) ■其核心思想就是要解决在P2P应用中遇到 的基本问题：如何在P2P网络中找到存有 特定数据的节点 ■Chord使用一致性哈希作为哈希算法，在 Chord协议中将其规定为SHA-1。 12
12 3.1 Chord：概述 UC Berkeley和MIT共同提出 采用环形拓扑(Chord环) 其核心思想就是要解决在P2P应用中遇到 的基本问题：如何在P2P网络中找到存有 特定数据的节点 Chord使用一致性哈希作为哈希算法，在 Chord协议中将其规定为SHA-1
3.1 Chord:概述 应用程序接口 ■Insert(K,V):将<K,V>对存在放到节点D为 Successor(K上 ■Lookup(K):根据K查询相应的V ■Update(K,newV):根据K更新相应的V ■Join(NID):节点加入 ■LeaveO):节点主动退出 13
13 3.1 Chord：概述 应用程序接口 Insert(K, V)：将<K, V>对存在放到节点ID为 Successor(K)上 Lookup(K)：根据K查询相应的V Update(K, new_V)：根据K更新相应的V Join(NID)：节点加入 Leave()：节点主动退出
(1)Chord:Hash表分布规则 Hash算法：SHA-1 Hash节点P地址一>m位节 K=hash(key)=54 N1 ID=hash(IP)=14 点D(表示为NID) N56O N8 ■ Hash内容关键字一>m位 K10 K(表示为KD) N519 9N14 ■ 节点按D从小到大顺序排列 N48 在一个逻辑环上 N42Q N21 <K,V>存储在后继节点上 K38 0 K24 ■ Successor(K):从K开始 N38 N32 K30 顺时针方向距离K最近的 节点 m=6 14
14 (1) Chord：Hash表分布规则 Hash算法：SHA-1 Hash节点IP地址－>m位节 点ID(表示为NID) Hash内容关键字－>m位 K(表示为KID) 节点按ID从小到大顺序排列 在一个逻辑环上 <K, V>存储在后继节点上 Successor(K)：从K开始 顺时针方向距离K最近的 节点 ID=hash(IP)=14 N56 K=hash(key)=54 N1 N8 N14 N21 N32 N38 N42 N48 N51 m=6
(2)Chord:简单查询过程 每个节点仅维护其后 Lookup(K54) 继节点D、P地址等 K54 N1 信息 N560 N8 K10 查询消息通过后继节 N519 N14 点指针在圆环上传递 N48 ■ 直到查询消息中包含 N420 N21 的K落在某节点D和 K24 K38 它的后继节点D之间 N38 N32 K30 速度太慢ON),N为 m=6 网络中节点数 15
15 (2) Chord：简单查询过程 每个节点仅维护其后 继节点ID、IP地址等 信息 查询消息通过后继节 点指针在圆环上传递 直到查询消息中包含 的K落在某节点ID和 它的后继节点ID之间 速度太慢 O(N)，N为 网络中节点数 N56 K54 Lookup(K54) N1 N8 N14 N21 N32 N38 N42 N48 N51 m=6