分布式系统 - P2P 系统设计研究

P2P 系统即 Peer to Peer 系统，在一个有多个节点的集群中，不存在一个中央节点，而是每个节点互相进行交互，构成整个系统。

P2P 系统是首个开始关注集群中节点的可扩展性的分布式系统，是云计算之先驱。

Napster

使用一个中央服务器存储所有的文件信息。中央服务器可能有多个。

中央服务器不存储文件本身，文件都存储在节点。

客户端查找一个文件中，先向中央服务器发送文件名查询，中央服务器返回存储改文件的节点地址信息。

客户端通过联系 napster.com 获取可能变动的中央服务器地址。

Gnutella

无中央服务器，所有文件存储在节点本身。

当查找一个文件时，节点将消息 flood 到所有相邻节点。

每个消息会自带 TTL(Time to Live) 计数，防止消息无止境的传递。

FastTrack

Napster 和 Gnutella 的混合体。

拓扑结构和 Gnutella 类似，但是在集群中选区部分“健康”的超级节点，扮演 Napster 中的中央服务器的角色。

节点通过“声望”来成为超级节点，声望由节点的参与度决定。

BitTorrent

每个文件对应一个 Tracker，新节点通过网址联系到 tracker。

Tacker 通过接收 peer 的心跳的方式，记录了当前的所有 peer 信息。

Peer 分为 Seed Peer 和 Leecher Peer，前者拥有整个文件的内容，后者只拥有一部分。

文件被切分为多个块，每个块 32 KB ~ 256 KB。

采用“附近稀缺文件优先”原则，节点首先获取附近副本数最少的块。

采用“Tit for Tat”（以牙还牙）策略，优先传输块给附近提供给自己的下载速度最高的节点。

采用“Chocking”策略，只同时上传文件给有限数量的节点。

Chord

Chord 开始严肃的从更高一级的层次考虑怎样实现 Distributed Hash Table(DHT) 。

Consistent Hashing 一致性哈希

一致性哈希的特性使得具有多个节点随时加入退出的集群的维护变得容易：

  1. 一致性哈希算法是 deterministic 的，在不同的机器上使用同样的输入都会算出同样的结果，这样一个集群中的所有机器都会保持一致。
  2. 当哈希表大小变化时（节点增删），只有 K/n 的键需要移动，其中 K 代表键数量，n 代表桶数量。

一致性哈希在 DHT 上的使用

将节点 IP 地址以及数据 Key 进行哈希运算（如 SHA-1算法）映射到 2^m 个数值-称为 Identifier -上，这些Identifier 组成如下图（此处 m=3）的圆环。其中 m 应该大到使得哈希碰撞的概率很低。

将 Key 赋予节点的规则是：

Identifier 为 k 的 Key 赋予 Identifier 为在圆环上等于或大于 k 的节点，该节点称为这个 Key 的后继节点（successor node），可以理解为将 Key 赋予在圆环上顺时针遇到的第一个节点，表示为 successor(k)。

可以看出这里的节点就是传统哈希表的桶，但是与传统哈希表 Key 对应固定的桶不同，一致性哈希的 Key 是滑动到某个节点的，这也是其具有特性 2 的原因。

Consistent Hashing

寻址方法 Routing

successor pointer：

在圆环的拓扑结构下，每个节点维护一个下一个节点的地址信息（successor pointer）即可实现在整个系统中的寻址。但最坏情况的开销是 O(n)。

finger table：

为了加快寻址速度，每个节点还维护了一个额外的寻址表称为 finger table，finger table 具有 m 项（2^m 个 Identifier），假定该节点的 Identifier 为 n，

则第 i 项存入 :

successor(n + 2^i)(mod2^m)

节点的地址，形象的理解就是每次以 2 的倍数远离原节点，如下图：

1535651420203

在 finger table 下寻址时，每次在当前节点的 finger table 中找到顺时针距离目标节点最近的节点发送消息，若没有，则直接发到下一个节点。

finger table 寻址的时间复杂度是 O(log(N))。

故障

  1. 为防止节点故障造成消息无法继续传递，在每个节点维护一张表，记录 2log(N) 个最近的节点地址，
  2. 为防止文件无法访问，某个节点的文件在前驱节点和后继节点保存副本，同时可以辅助负载平衡。

节点加入/退出 Churn

节点加入退出时，需要更新 successor-list 和 finger table。

节点加入的过程：

  1. 新节点 N 联系一个知名服务器，知名服务器会将其“介绍”给要加入的前驱节点 P 和后继节点 S；
  2. 前驱节点 P 将新节点 N 更新其后继节点为 N；
  3. 新节点 N 将其后继节点设定为后继节点 S，并根据 S 构建自身的 finger table；
  4. 新节点 N 定时地询问附近节点更新其 finger table，该过程称为 stabilization protocol，每个节点都定时进行。
  5. 新节点 N 需要从后继节点 S 拷贝一些因哈希重分布后属于它的数据。

节点退出的过程类似。

Pastry

和 Chord 同样使用一致性哈希形成一个虚拟圆环。

和 Chord 同样使用 Stabilization Protocol。

寻址方法 Routing

每个节点知道它们的前驱和后继节点地址。

和 Chord 的 Finger Table 不同的是，以如下形式保存寻址表，假设当前节点号是 01110100101，保存下列节点的地址，其中 * 表示和当前节点号相反的数字：

*
0 *
0 1 *
0 1 1 *
... 0 1 1 1 0 1 0 0 1 0 *

寻址时，将信息发送给最长匹配到的节点。

寻址时间复杂度为 O(log(N))。

Chord 和 Pastry 的对比

Chord 的 Finger Table 是在圆环上按 2 的倍数选点保存。

Pastry 则是将所有节点号放在一个 N 维空间中，并在这个空间中选取特定的点保存。

都具有 O(log(N)) 的查找时间复杂度。内存复杂度为 O(log(N))。

Kelips

不使用虚拟圆环，而是使用 Affinity Group。

将节点哈希到 K 个（K = sqrt(N)）Affinity Group 中，每个节点维护当前 Affinity Group 所有节点的地址，以及其他 Affinity Group 中任一一个节点的地址。

文件本身不按照哈希存储，而是存储到上传地，但将文件的路由信息保存到该文件节点所属 Affinity Group 的所有节点中。

1535821134333

寻址方式 Routing

从文件名获知该文件所属 Affinity Group，联系所知的该 Affinity Group 中的节点获得文件路由地址，若该节点失效，联系任一本 Affinity Group 的节点作为中介，最后获取文件。

寻址时间复杂度为 O(1)。内存复杂度为 O(sqrt(N))。

节点加入/退出 Churn

使用 Gossip-based Membership-list 实现。