基于P2P的分布式网络存储服务

1

名词解释：

P2P: 对等网络 Peer to Peer，每个节点，既是服务端，也是客户端

peer: n.同辈，同龄人

传统C/S架构有哪些问题？

资源存储在服务端，对服务器存储空间、服务器IO性能要求高，客户端的网络资源没有得到充分利用

2

3

Napster文件分享过程

? 用户向Napster服务器上传文件列表

? 服务器记录文件信息及其所在的网络位置IP地址

Napster文件下载过程

? 用户向服务器查询文件

? 服务器返回文件所在机器的IP地址

? 文件被直接从所在机器传送给用户

Napster缺点

? 服务器的单点失败问题

什么是单点失效？

举个简单例子就是：网站就一台服务器，当这台服务器挂了，网站就没办法访问了

如何避免单点失效？

打造高可用（不易宕机），高性能（支持大规模并发），可以伸缩（压力大时增加服务分摊压力，压力小时关闭部分服务，节约资源）的服务器集群

? 服务器容易受到拒绝服务攻击DoS

DoS是Denial of Service的简称，即拒绝服务，其目的是使计算机或网络无法提供正常的服务。最常见的DoS攻击有计算机网络带宽攻击和连通性攻击

带宽攻击指以极大的通信量冲击网络，使得所有可用网络资源都被消耗殆尽，最后导致合法的用户请求就无法通过

连通性攻击指用大量的连接请求冲击计算机，使得所有可用的操作系统资源都被消耗殆尽，最终计算机无法再处理合法用户的请求

4

基于洪泛查询的定位机制 Gnutella

名词解释：

洪泛：洪水泛滥之意

特点：

? 没有集中式服务器

? 没有索引

? 文件存储在各个节点上

定位过程

? 用户将文件请求发送给邻居

? 如果邻居可以响应该请求，那么邻居就响应；否则邻居将该请求转发给自己的邻居

? 一旦定位用户请求的文件后，相关的节点直接将文件传输给用户

洪泛查询问题

洪泛过渡：请求在网络中无法找到目的地址，像死循环一样消耗网络资源

如何解决洪泛过度？

? 向查询请求中在网络层首部设置 Time To Live(TTL)

TTL是 Time To Live的缩写，该字段指定IP包被路由器丢弃之前允许通过的最大网段数量。TTL是IPv4报头的一个8bit字段

TTL的作用是限制IP数据包在计算机网络中的存在的时间。TTL的最大值是255，TTL的一个推荐值是64

如何设置合理的TTL？

? TTL设置过大，没有解决洪泛问题

? TTL设置过小，找不到文件

Gnutella优点

没有中心点，不容易出现单点失败导致的系统瘫痪故障，不容易受到DoS攻击

Gnutella缺点

洪泛查询方式，消耗网络资源

基于哈希的分布式映射定位机制

 Chord 2001年由MIT提出

什么是Chord？

Chord是一个算法，也是一个协议。作为一个算法，Chord可以从数学的角度严格证明其正确性和收敛性；作为一个协议，Chord详细定义了每个环节的消息类型。当然，Chord之所以受追捧，还有一个主要原因就是Chord足够简单，3000行的代码就足以实现一个完整的Chord

一致性hash算法原理

Chord的文件映射机制

? 把每个节点的网络地址映射在Hash环上

1.计算每个节点网络地址的Hash值

2.把地址Hash值映射在Hash环上

? 把文件信息映射在Hash环的节点上

1.计算每个文件信息的Hash值

2.把文件hash值映射在上面同一个Hash环上

3.把文件Hash值映射在具体节点上

Chord例子

10个节点，5个文件

? 计算每个节点网络地址的Hash值

每个节点按照自己网络地址（e.g.IP地址+端口号），计算各自Hash值

· 节点1的网络地址的Hash值为1, 表示为N1

· 节点2的网络地址的Hash值为8，表示为N8

· ….

· 节点10的网络地址的Hash值为8，表示为N56

? 把地址Hash值映射在Hash环上

? 计算每个文件信息的Hash值

文件1的Hash值为10，表示为 K10

文件2的Hash值为24，表示为 K24

文件3的Hash值为30，表示为 K30

文件4的Hash值为38，表示为 K38

文件5的Hash值为54，表示为 K54

? 把文件hash值映射在上面同一个Hash环上

? 写出节点和文件的映射表

(K10,N14)

(K24,N32)

(K30,N32)

(K38,N38)

(K54,N56)

Hash环文件查找定位

? 顺序方案

如果每个节点记录保持自己与空间环上紧邻的前驱peer和后继peer的两个网络连接，如此就可以形成一个网络环，采用的数据结构：循环双向链表

优点：插入、删除维护方便

缺点：查询慢

任何节点的查找请求，如果沿Chord环一圈，肯定能够找到相关的文件，时间复杂度是O(N)，N为网络节点数

Chord : Finger table方案

? 基本出发点

让每个节点有规律地多存储一些Chord环中的信息，这样可以加快查找文件的速度

? 方案

每个节点都存储O(log(n)）条记录，各自形成一个自己的Finger table

? 例如

m=6 ，节点 N8 存储 空间8+1, 8+2, 8+4,8+8,…,8+32 的实体网络地址信息

? 查找过程

节点N8查找文件K54

? 时间复杂度

O(logN)，N为网络节点数，以空间换时间（每个节点多维护了Finger Table）

联想

? 看完了Chord设计思路，笔者联想到redis中实现zset这种数据类型采用的数据结构—跳表，同样采取的是空间换时间的思路加速查询

? redis集群如何保证key均匀地分布在不同的节点，且能够适应增加、删除节点？

通过一致性hash算法，可以点击下方链接查看更多：

https://www.zsythink.net/archives/1182

本文从分布式网络存储系统的定位问题，引出3种解决方案，分别是基于目录/索引的定位机制、 基于洪泛查询的定位机制、基于哈希的分布式映射定位机制，以及3种方案对应的实现方法。