以太坊—P2P网络

1256 0 0

作者:failymao

Chord算法

1.Chord 概念

Chrod算法是P2P中的四大算法之一，是有MIT（麻省理工学院）于2001年提出。
Chord的目的是提供一种能在P2P网络快速定位资源的的算法，Chord并不关心资源是如何存储的，只是从算法层面研究资源的取得，因此Chord的API只有两个set、get。

Chord是什么

- Chord是一个算法，也是一个协议。作为一个算法，Chord可以从数学的角度严格证明其正确性和收敛性；作为一个协议，Chord详细定义了每个环节的消息类型。
Chord还可以被作为一个一致性哈希、分布式哈希（DHT）的实现。

覆盖网络（overlaynetwork）

- 构建在其他网络之上、网络节点之间通过虚拟或逻辑连接在一起，比如云计算、分布式系统都是覆盖网络，因为其都构建于TCP/IP之上，且节点之间有联系。Chord也是构建于覆盖网络

分布式哈希表（DHT）

DHT的主要想法是把网络上资源的存取像Hashtable一样，可以简单而快速地进行put、get 。与一致性哈希相比，DHT更强调的是资源的存取，而不管资源是否是一致性的。 [^ 哈希一致性是指任何一条相同的字段，无论在何时，何地用何种设备进行hash计算后得到的hash值不变]

Chord实现原理

Chord通过把Node和Key映射到相同的空间而保证一致性哈希 ;
为了保证哈希的非重复性，Chord选择SHA-1作为哈希函数，SHA-1会产生一个2^160的空间;每项为一个16字节（160bit）的大整数
整数首尾相连形成一个环，称之为Chord环,整数在Chord环上按大小顺时针排列
Node（机器的IP地址和Port）与Key（资源标识）都被哈希到Chord环上
整个P2P网络的状态为一个虚拟的环，因此我们说Chord是结构化的P2P网络

2.Chord里面的基本要素

节点ID：NID（node identifier），表示一个物理机器，m位的一个数字（m要足够大以保证不同节点的NID相同的几率小的可以忽略不计），由节点机器的IP地址通过哈希操作得到。
资源ID: KID（key identifiers），原为键ID，其实际表示一个资源（因为Key与一个资源value哈希绑定），故在本文中统称资源ID（这样比较直观），m位的一个数字（m要足够大以保证不同资源的KID相同的几率小的可以忽略不计），由Key通过哈希操作得到。
Chord环：Chord Ring，NID和KID被分配到一个大小为2^m的环上，用于资源分配（给某一个节点）和节点分布 ,以及资源定位
什么是资源分配：资源（k）被分配到NID（节点ID）上，这个节点成为k的后继节点 , 是环上从k(假如同样存在一个NID，n=k)起顺时针方向的第一个节点，记为successor(k)。
- 例如下边这幅图：红色表示（N1, N18, N25,N26, N45,N53 ）就是节点ID，蓝色为标志符。
- 而节点分布则顺时针将节点N由小到到放在这个环上。下图是一个m=6的环，其中有10个节点，5个资源，K10的后继节点为N14，也就是说K10被分配给了N14。

3. Chord资源定位（Key Location)

循环查找 :

过程：节点N8寻找K54这个资源，N8.find_successor(K54)发现下一个节点N14不合符54є (8; 14]，于是N14发起同样的搜索，然后一跳一跳后直到节点N56满足54є (51; 56]，于是得知资源K54在N56这个节点上。

缺点 : 效率不给力

可伸缩方法：

原理：每个节点N上都维护了最多有m项（m为ID的位数）的路由表，称为finger table, 用来定位资源 (KID).

路由表是如何生成：

a . 已知chord环的大小为 2^6 = 64(标识符)，已知NID (节点) N1,N8, N14, N21,N32,N38,N42,N48,N51

b. 图展示的N8节点的是finger table的过程

1.  m =6 , 所以每个节点最多维护了6个的资源ID (kID)；

2.  K=8为起始位置， KID(8+2^0) = KID9 —->NID14

3.  KID(8+2^1) =KID11 —–> NID14

4.  KID(8+2^2) =KID12 —–> NID14

5.  KID(8+2^3) =KID16 —–> NID21

…

好处：