Kademlia算法与分布式哈希表(DHT)

分布式哈希表常用在P2P网络中,如常见的BitTorrent。而Kademlia算法是要解决在网络中的寻找节点问题。

分布式哈希表(Distributed Hash Table)

在介绍Kademlia之前有必要熟悉一下DHT。

分布式哈希表就是将文件的哈希表存储在多个节点中,每个节点存储一部分文件的同时维护一个路由表,即每个节点包含:

  • Hash key(文件哈希值)
  • Hash Value(文件的一部分)
  • 路由表(在kademlia算法中称为k-bucket)

这些节点相互连接组成网络:

具体到P2P的文件共享中,假如要分享1G的电影,可以将1G的文件分割为128KB的小块,并生成小块的哈希值。

分布式哈希表实际上是P2P共享发展史上的第三种技术路线,前两代都存在一定的问题,简单介绍一下:

  1. 第一代 Tracker服务器
    • 这种模式下,文件块是分发到各个节点上的,但是每个节点在获取其他节点的位置时需要连接中央服务器。
    • 这种情况下中央服务器就成为了单点故障,一旦中央服务器出现故障或者被不可抗力ban掉后整个网络就无法运行
  2. 第二代
    • 在看到第一代的不足后,第二代P2P在查找节点时会询问与自身相连的所有节点,如果周边节点不知道目标节点的位置,又回广播一遍查询信息,直到找到目标节点。
    • 显然这种情况很容易催生广播风暴,严重占用网络带宽。即使通过设定TTL、限制查询递归次数也无法解决这个问题。

Kademlia算法

首先声明算法的三个参数:

  1. keyspace
    • 节点ID的位数,默认是160位
    • 决定每个节点的路由表(k-bucket)有几层
  2. k *重要*
    • 路由表里的每层存储k个信息
    • 每次查询时返回k个信息
    • 存储文件时,将文件存储到k个节点
    • 默认值为8
  3. α
    • 向其他节点查询目标节点时,每次向α个节点发送请求

一、节点

1.节点包含的信息

前面介绍了网络中的一个节点包含三个信息:

  • 文件的哈希值
  • 文件
  • 路由表

实际上节点还包含自身的ID和IP地址信息,所以共五个信息:

  • 节点ID(哈希值,二进制,默认160位[keyspace])
  • 节点IP地址和端口
  • 文件的哈希值(二进制,默认160位)
  • 文件
  • 路由表(术语k-bucket,存储了当前节点到其他节点的距离)

其中,算法用到的只有节点ID、哈希值和路由表。

为了方便理解,以下二进制都缩短至8位。

2.文件如何分配到节点

文件会被分配给ID与其哈希值相同的节点,但在实际情况中文件数是远大于节点数的,基本找不到相同的节点ID,此时将文件分配给ID与其哈希值异或距离最短的节点。

例如,文件哈希值为00000100,在网络中如果存在ID为00000100的节点,则该节点存储此文件;如果没有00000100,但有00000101节点,则交给这个节点存储。

考虑到节点可能不在线或者退出网络的情况,同一个文件会存储在ID相近的k个节点中。

例如,哈希值为00000100的文件会被存储到ID为00000101、00000100、00000110等k个节点中(如果节点存在)。

二、异或距离

异或距离即节点间的逻辑距离,因为计算距离的方式为二进制异或,所以称“异或距离”。

1.计算方式

异或距离的计算方式为按位异或(异或:相同为0,不同为1)。

例如,节点00000011和节点00010001之间的异或距离为

00000011

00010001

———-

00010010B = 18D

他们之间的异或距离为18。

2.k-bucket(路由表)分层

k-bucket是每个节点必须维护的表,节点在查询时会向k-bucket中记录的已分层的节点发送请求。

k-bucket按照异或距离来分层。

例如,有一基础节点的ID为00010001,它与另外一个节点00010000的异或距离为1,则在基础节点的k-bucket中,节点00010000被分到k-bucket 1层。

有另外两个节点00010011和00010010,从倒数第2位开始不同,它们与基础节点的异或距离为分别为2(00000010)和3(00000011),则在基础节点的k-bucket中,它们被分到k-bucket 2层。

… …

如果节点的ID前面所有位数相同,在倒数第i位不同,这样的节点只有2(i-1)个,与基础节点的距离范围为[2(i-1), 2i),在基础节点的k-bucket中,它们被分到k-bucket i层。

将节点作为叶子节点,以ID(人为约定左0右1)排列为二叉树(图中k-bucket 2的异或距离右区间错了,应为4):

则其k-bucket层次就是按照父节点、爷爷节点、曾爷爷节点的子树来划分的。

三、查找目标节点

真正的算法步骤:

  • 在本节点的k-bucket中查找文件哈希值
    • 如果找到对应哈希值的节点ID,或者找到对应哈希值相邻范围的节点,则直接得到对应节点的地址
    • 如果没有找到,则在距文件哈希值最近的k-bucket层中选择节点,令其在它的k-bucket中查找目标节点,如果该节点还没有,则该节点再返回一个更接近的节点,直到找到目标节点。

例如,基本节点为00000001,要查找的文件哈希为00010001。

首先,该文件是存储在相邻k个节点上的,假设正好有节点的ID为00010001,则该文件存储在00010001和其他相邻k-1个节点上。

该文件的哈希与基本节点从倒数第5位开始不同,而且其异或距离为16。

基本节点开始在它的k-bucket 5中查找该哈希值,如果恰好其k个记录中存在该节点,则直接获取节点地址。

如果其k-bucket 5中没有该哈希记录,则选择其中的一个节点(一条记录),请求这个节点在它的k-bucket中寻找哈希00010001,返回结果。

如果该节点还没有记录,则再返回一个经过它计算后得到的更近一步的节点,再从这个节点查找。

 

如图,B节点再次查找时k-bucket ii必定小于基本节点查找时的5,因为B节点与目标节点的ID从开始到倒数第5位一定是相同的(它们都与基本节点比较过,都在基本节点的k-bucket 5中),最坏的情况也只是倒数第4位不同,那么B节点最多也只在k-bucket 4中查询,这样就会逐步缩小目标节点所在范围,以确定节点的位置。

可以看出,也可以根据二叉树的性质推断,如果在N个节点中查找某个节点,最多只需查询log2(N)次。

参考链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据