入门DHT协议理论篇

入门DHT协议理论篇

背景

想研究下比特币挖矿的技术原理, 了解到其借鉴了p2p( peer-to-peer) 的去中心化网络DHT, 之前对p2p分布式网络就特别感兴趣,但一直不得其解, 正好,借此机会,系统全面的先去学习DHT协议。

p2p2

P2P 就是 peer-to-peer。这种方式的特点是,资源一开始并不集中存储在某些设备上,而是分散地存储在多台设备上,这些设备我们称为 peer, 比如1个文件 100K, 我将其拆分, 分到10台机器上

在下载一个文件时,只要得到那些已经存在了文件的 peer 地址,并和这些 peer 建立点对点的连接,就可以就近下载文件,而不需要到中心服务器上。

一旦下载了文件,你的设备也就称为这个网络的一个 peer,你旁边的那些机器也可能会选择从你这里下载文件

通过这种方式解决上面 C/S 结构单一服务器带宽压力问题。如果使用过 P2P2软件,例如 BitTorrent,你就会看到自己网络不仅有下载流量,还有上传流量,也就是说你加入了这个 P2P 网络,自己可以从这个网络里下载,同时别人也可以从你这里下载。这样就实现了,下载人数越多,下载速度越快的愿望。

种子文件(.torent)

上面整个过程是不是很完美?是的,结果很美好,但为了实现这个美好,我们还是有很多准备工作要做的。比如,我们怎么知道哪些 peer 有某个文件呢?    

这就用到我们常说的种子(.torrent)。 .torrent 文件由[文件信息]和Announce(Tracker URL)两部分组成。

其中,文件信息有以下内容:

  • Info 区 : 指定该种子包含的文件数量、文件大小及目录结构,包括目录名和文件名, 即文件的基本信息
  • Name 字段: 指定顶层目录名字
  • 每个段的大小: BitTorrent(BT)协议把一个文件分成很多个小段,然后分段下载
  • 段哈希值: 将整个种子种,每个段的 SHA-1 哈希值拼在一起。 hash主要验证文件未被篡改。

下载时,BT 客户端首先解析 .torrent 文件,得到 Tracker 地址,然后连接 Tracker 服务器。Tracker 服务器回应下载者的请求,将其他下载者(包括发布者)的 IP 提供给下载者。    

下载者再连接其他下载者,根据 .torrent 文件,两者分别对方自己已经有的块,然后交换对方没有的数据。     可以看到,下载的过程不需要其他服务器参与,并分散了单个线路上的数据流量,减轻了服务器的压力。

下载者每得到一个块,需要算出下载块的 Hash 验证码,并与 .torrent 文件中的进行对比。如果一样,说明块正确,不一样就需要重新下载这个块。这种规定是为了解决下载内容的准确性问题。

从这个过程也可以看出,这种方式特别依赖 Tracker。Tracker 需要收集所有 peer 的信息,并将从信息提供给下载者,使下载者相互连接,传输数据。虽然下载的过程是非中心化的,但是加入这个 P2P 网络时,需要借助 Tracker 中心服务器,这个服务器用来登记有哪些用户在请求哪些资源。

这种方式, 像分布式的hdfs即采用此方案。必须有一个中心节点记录数据节点存储信息

所以,这种工作方式有一个弊端,一旦 Tracker 服务器出现故障或者线路被屏蔽,BT 工具就无法正常工作了。那能不能彻底去中心化呢?答案是可以的

去中心化网络(DHT)

DHT(Distributed Hash Table ,这个网络中,每个加入 DHT 网络的人,都要负责存储这个网络里的资源信息和其他成员的联系信息,相当于所有人一起构成了一个庞大的分布式存储数据库。

Kedemlia 协议 就是一种著名的 DHT 协议。我们来基于这个协议来认识下这个神奇的 DHT 网络。

当一个客户端启动 BitTorrent 准备下载资源时,这个客户端充当两个角色:

  1. peer角色: 监听一个 TCP 端口,用来上传和下载文件。对外表明我这里有某个文件, 上传使用
  2. DHT Node 角色:监听一个 UDP 端口,通过这个角色,表明这个节点加入了一个 DHT 网络


在 DHT 网络里面,每一个 DHT Node 都有一个 ID。这个 ID 是一个长字符串。每个 DHT Node 都有责任掌握一些“知识”,也就是文件索引。也就是说,每个节点要知道哪些文件是保存哪些节点上的。注意,这里它只需要有这些“知识”就可以了,而它本身不一定就是保存这个文件的节点。 因为任意节点都可能会下载文件, 即任意节点可能都会保存这个文件。

当然,每个 DHT Node 不会有全局的“知识”,也就是说它不知道所有的文件保存位置,只需要知道一部分。这里的一部分,就是通过哈希算法计算出来的

每个 DHT Node 不会有全局的“知识”,也就是说它不知道所有的文件保存位置,只需要知道一部分。这里的一部分,就是通过哈希算法计算出来的。

Node ID 和文件哈希值

每个文件可以计算出一个哈希值,而 DHT Node 的 ID 是和哈希值相同长度的串

这里成功将节点id 和文件hash值关联起来了

对于文件下载,DHT 算法是这样规定的:

如果一个文件计算出一个哈希值,则和这个哈希值一样的那个 DHT Node,就有责任知道从哪里下载这个文件,即便它自己没保存这个文件

当然不一定总这么巧,都能找到和哈希值一模一样的,有可能文件对应的 DHT Node 下线了,所以 DHT 算法还规定:

除了一模一样的那个 DHT Node 应该知道文件的保存位置,ID 和这个哈希值非常接近的 N 个 DHT Node 也应该知道。

文件 1 通过哈希运算,得到匹配 ID 的 DHT Node 为 Node C(当然还会有其他的,为了便于理解,咱们就先关注 Node C),所以,Node C 就有责任知道文件 1 的存放地址,虽然 Node C 本身没有存放文件 1

同理,文件 2 通过哈希计算,得到匹配 ID 的 DHT Node 为 Node E,但是 Node D 和 E 的值很近,所以 Node D 也知道。当然,文件 2 本身不一定在 Node D 和 E 这里,但是我们假设 E 就有一份。

接下来,一个新节点 Node new 上线了,如果要下载文件 1,它首先要加入 DHT 网络。如何加入呢?

在这种模式下,种子 .torrent 文件里面就不再是 Tracker 的地址了,而是一个 list 的 Node 地址,所有这些 Node 都是已经在 DHT 网络里面的。当然,随着时间的推移,很有可能有退出的,有下线的,这里我们假设,不会所有的都联系不上,总有一个能联系上

那么,Node new 只要在种子里面找到一个 DHT Node,通过其介绍,就加入了网络

Node new 不知道怎么联系上 Node C,因为种子里面的 Node 列表里面很可能没有 Node C,但是没关系,它可以问。DHT 网络特别像一个社交网络,Node new 会去它能联系上的 Node 问,你们知道 Node C 的联系方式吗?

在 DHT 网络中,每个 Node 都保存了一定的联系方式,但是肯定没有所有 Node 的联系方式。节点之间通过相互通信,会交流联系方式,也会删除联系方式。这和人们的沟通方式一样,你有你的朋友圈,他有他的朋友圈,你们互相加微信,就互相认识了,但是过一段时间不联系,就可能会删除朋友关系一样。

在社交网络中,还有个著名的六度理论,就是说社交网络中的任何两个人的直接距离不超过六度,也就是即使你想联系比尔盖茨,最多通过六个人就能够联系上

所以,Node New 想联系 Node C,就去万能的朋友圈去问,并且求转发,朋友再问朋友,直到找到 C。如果最后找不到 C,但是能找到离 C 很近的节点,也可以通过 C 的相邻节点下载文件 1。
这里,一般实际情况是, 问朋友A, A告知你B离C近, 然后我再去问B….

在 Node C上,告诉 Node new,要下载文件 1,可以去 B、D、F,这里我们假设 Node new 选择了 Node B,那么新节点就和 B 进行 peer 连接,开始下载。它一旦开始下载,自己本地也有文件 1 了,于是,Node new 就告诉 C 以及 C 的相邻节点,我也有文件 1 了,可以将我加入文件 1 的拥有者列表了

你可能会发现,上面的过程中漏掉了 Node new 的文件索引,但是根据哈希算法,一定会有某些文件的哈希值是和 Node new 的 ID 匹配的。在 DHT 网络中,会有节点告诉它,你既然加入了咱们这个网络,也就有责任知道某些文件的下载地址了

好了,完成分布式下载了。但是我们上面的过程中遗留了两个细节性的问题。

1)DHT Node ID 以及文件哈希值是什么?

其实,我们可以将节点 ID 理解为一个 160bits(20字节)的字符串,文件的哈希也使用这样的字符串。

2)所谓 ID 相似,具体到什么程度算相似?

这里就要说到两个节点距离的定义和计算了。

在 Kademlia 网络中,两个节点的距离采用的是逻辑上的距离,假设节点 A 和 节点 B 的距离为 d,则:

1
 d = A XOR B

如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

上面说过,每个节点都有一个哈希 ID,这个 ID 由 20 个字符,160 bits 位组成。这里,我们就用一个 5 bits ID 来举例。

我们假设,节点 A 的 ID 是 01010,节点 B 的 ID 是 01001,则:

1
 距离 d = A XOR B = 01010 XOR 00011 = 01001 = 9

所以,我们说节点 A 和节点 B 的逻辑距离为 9。

回到我们上面的问题,哈希值接近,可以理解为距离接近,也即,和这个节点距离近的 N 个节点要知道文件的保存位置。

要注意的是,这个距离不是地理位置,因为在 Kademlia 网络中,位置近不算近,ID 近才算近。我们可以将这个距离理解为社交距离

DHT 网络节点关系的维护

就像人一样,虽然我们常联系的只有少数,但是朋友圈肯定是远近都有。DHT 网络的朋友圈也一样,远近都有,并且按距离分层

假设某个节点的 ID 为 01010,如果一个节点的 ID,前面所有位数都与它相同,只有最后 1 位不停,这样的节点只有 1 个,为 01011。与基础节点的异或值为 00001,也就是距离为 1。那么对于 01010 而言,这样的节点归为第一层节点,也就是k-buket 1

类似的,如果一个节点的 ID,前面所有位数和基础节点都相同,从倒数第 2 位开始不同,这样的节点只有 2 个,即 01000 和 01001,与基础节点的亦或值为 00010 和 00011,也就是距离为 2 和 3。这样的节点归为第二层节点,也就是k-bucket 2

所以我们发现, 我们从左到右, 逐位比较, 找到第一个位置不同的节点,然后再从右到左,计数这是第一个节点, 即所谓的第几个 **k-bucket **

所以,我们可以总结出以下规律:

如果一个节点的 ID,前面所有位数相同,从倒数第 i 位开始不同,这样的节点只有 2^(i-1) 个,与基础节点的距离范围为 [2^(i-1), 2^i],对于原始节点而言,这样的节点归为k-bucket i。

你会发现,差距越大,陌生人就越多。但是朋友圈不能把所有的都放下,所以每一层都只放 K 个,这个 K 是可以通过参数配置的。

可以更深入的思考, 每一层存储固定的朋友, 但外层朋友很多, 应该多存才对。 是这样吗? 我们可以留一个疑问。

**DHT 网络中查找好友 **

假设,Node A 的 ID 为 00110,要找 B(10000),异或距离为 10110,距离范围在 [2^4, 2^5),这就说明 B 的 ID 和 A 的从第 5 位开始不同,所以 B 可能在 k-bucket 5 中

然后,A 看看自己的 k-bucket 5 有没有 B,如果有,结束查找。如果没有,就在 k-bucket 5 里随便找一个 C。因为是二进制,C、B 都和 A 的第 5 位不停,那么 C 的 ID 第5 位肯定与 B 相同,C和B从第四位开始不同, 即它与 B 的距离小于 2^4,相当于 A、B 之间的距离缩短了一半以上。

接着,再请求 C,在 C 的通讯里里,按同样的查找方式找 B,因为从第四位不同, 则进入c的 k-bucket 4桶中找B,如果 C 找到了 B,就告诉 A。如果 C 也没有找到 B,就按同样的搜索方法,在自己的通讯里里找到一个离 B 更近一步的 D(D、B 之间距离小于 2^3),把 D 推荐给 A,A 请求 D 进行下一步查找。

接着, 再请求D, 在D的 k-bueckt3中…

接着,再请求E, 在E的 k-bucket2 中…

你可能已经发现了,Kademlia 这种查询机制,是通过折半查找的方式来收缩范围,对于总的节点数目为 N 的网络,最多只需要 log2(N) 次查询,就能够找到目标

节点之间的通信方式

在 Kademlia 算法中,每个节点互相通信, 会接收到下面四种请求,也会发出以下四种请求:

  • PING:测试一个节点是否在线。相当于打个电话,看还能打通不;不能打通就把这个节点记录删除掉
  • find_node:查询某个节点
  • get_peers: 根据文件hash,问下哪个节点知道文件放哪了
  • announce_peer: 告知应该知道文件该存储哪些节点

加入节点

首先通过种子中的节点 介绍, 加入到节点中, 这样才能扩充自己的朋友圈。 朋友圈人越多,越能方便找到其他节点

节点的更新

整个 DHT 网络,会通过相互通信,维护自己朋友圈好友的状态。

  • 每个 bucket 里的节点,都按最后一次接触时间倒序排列。相当于,朋友圈里最近联系的人往往是最熟的;

  • 每次执行四个请求中的任意一个都会触发更新
  • 当一个节点与自己接触时,检查它是否已经在 k-bucket 中。就是说是否已经在朋友圈。如果在,那么就将它移到 k-bucket 列表的最底,也就是最新的位置(刚联系过,就置顶下,方便以后多联系)。如果不在,就要考虑新的联系人要不要加到通讯录里面。假设通讯录已满,就 PING 一下列表最上面的节点(最旧的),如果 PING 通了,将旧节点移动到列表最底,并丢弃新节点(老朋友还是要留点情面的,老朋友更稳定,不会捣乱)。如 PING 不同,就删除旧节点,并将新节点加入列表(联系不上的老朋友还是删掉吧)。

总结

主要参考: https://www.zhihu.com/people/l1905