/kad-java

kad-java

Primary LanguageJava

kad-java

kad关键问题流程

算法的三个参数：keyspace，k和α

  • keyspace 即ID有多少位,决定每个节点的通讯录有几层
  • k 每个一层k-bucket里装k个node的信息，即<node ID, IP Adress, port> 每次查找node时，返回k个node的信息,对于某个特定的data，离其key最近的k个节点被会要求存储这个data
  • α 每次向其他node请求查找某个node时，会向α个node发出请求

节点的指令

Kademlia算法中，每个节点只有4个指令

  • PING 测试一个节点是否在线
  • STORE 要求一个节点存储一份数据
  • FIND_NODE 根据节点ID查找一个节点
  • FIND_VALUE 根据KEY查找一个数据，实则上跟FIND_NODE非常类似

节点的关键数据结构

  • nodeId 节点ID
  • ip,port ip地址和端口
  • data 数据
  • k桶 路由表

1.k桶如何排布,以及如何更新

k桶的排布
根据nodeId间的异或距离排布，比如

节点1111的k桶排布
k1 1110 最后一位不同
k2 1101 1100 最后第二位不同
k3 1011 1010 1001 1000 最后第三位不同
k4 0111 0011 0001 0000 0101 0100 0110  0010

k桶的更新

  • 主动收集节点:任何节点都可以发起四个命令，从而从返回值刷新K-桶中的节点信息
  • 被动收集节点:当收到其他节点发送过来的请求（如：FIND_NODE、FIND_VALUE），会把对方的节点ID加入到某个K-桶中
  • 检测失效节点:通过发起PING请求，判断K-桶中某个节点是否在线，然后清理K-桶中那些下线的节点

当一个节点ID要被用来更新对应的K-桶，其具体步骤如下:

  • 计算自己和目标节点ID的距离d
  • 通过距离d选择路由表中对应的K-桶，如果目标节点ID已经在K-桶中，则把对应项移到该K-桶的尾部
  • 如果目标节点ID不在K-桶中，则有两种情况：
    • 如果该K-桶存储的节点小于K个，则直接把目标节点插入到K-桶尾部；
    • 如果该K-桶存储节点大于等于K个，则选择K-桶中的头部节点进行PING操作，检测节点是否存活。如果头部节点没有响应，则移除该头部节点，并将目标节点插入到队列尾部；如果头部节点有响应，则把头部节点移到队列尾部，同时忽略目标节点。

2.节点如何加入，删除

当一个节点要加入网络
前提:必须知道一个存在于网络中的有效节点
具体步骤:假设节点A是待加入节点，节点B是节点A知道的网络中的有效节点，有如下流程

  1. 节点A把节点B加入到自己的k桶
  2. 节点A生成一个随机的ID值，知道离开网络，节点A一直用这个ID作为自己的nodeId
  3. 计算与节点B的距离，并向距离最近的α个节点(开始只有B节点)发起FIND_NODE请求，请求定位的节点是自己的节点ID
  4. 其他节点在收到节点A的FIND_NODE请求后，会根据FIND_NODE请求的约定，找到K个距离A最近的节点，并返回给A节点,并把A节点加入自己的k桶
  5. A收到这些节点以后，就把它们加入到自己的K-桶中，并再进行步骤3,直到距离没有更新

3.节点如何点位

具体步骤

  1. 首先由发起者确定目标ID对应路由表中的K-桶位置，然后从自己的K-桶中筛选出K个距离目标ID最近的节点，并同时向这些节点发起FIND_NODE的查询请求
  2. 被查询节点收到FIND_NODE请求后，从对应的K-桶中找出自己所知道的最近的K个节点，并返回给发起者。
  3. 发起者在收到这些节点后，更新自己的结果列表，并再次从其中K个距离目标节点ID最近的节点，挑选未发送请求的节点重复Step1步骤
  4. 上述步骤不断重复，直到无法获取比发起者当前已知的K个节点更接近目标节点ID的活动节点为止。 在查询过程中，没有及时响应的节点应该立即排除，同时查询者必须保证最终获得的K个节点都是在线的。

4.数据如何定位

当节点要查询<key, value>数据对时，和定位节点的过程类似

  1. 首先发起者会查找自己是否存储了<key, value>数据对，如果存在则直接返回，否则就返回K个距离key值最近的节点，并向这K个节点ID发起FIND_VALUE请求
  2. 收到FIND_VALUE请求的节点，首先也是检查自己是否存储了<key, value>数据对，如果有直接返回value，如果没有，则在自己的对应的K-桶中返回K-个距离key值最近的节点
  3. 发起者如果收到value则结束查询过程，否则发起者在收到这些节点后，更新自己的结果列表，并再次从其中K个距离key值最近的节点，挑选未发送请求的节点再次发起FIND_VALUE请求
  4. 上述步骤不断重复，直到获取到value或者无法获取比发起者当前已知的K个节点更接近key值的活动节点为止，这时就表示未找到value值。

如果上述FIND_VALUE最终找到value值，则<key, value>数据对会缓存在没有返回value值的最近节点上，这样下次再查询相同的key值时就可以加快查询速度。 所以，越热门的资源，其缓存的<key, value>数据对范围就越广。这也是为什么我们以前用P2P下载工具，下载的某个资源的人越多时，下载速度越快的原因。

5.数据如何保存

当节点收到一个<key, value>的数据时，它的存储过程如下：

  1. 发起者首先定位K个距离目标key值最近的节点
  2. 然后发起者对这K个节点发起STORE请求
  3. 接收到STORE请求的节点将保存<key, value>数据
  4. 同时，执行STORE操作的K个节点每小时重发布自己所有的<key, value>对数据
  5. 最后，为了限制失效信息，所有<key, value>对数据在发布24小时后过期。 ##未完待续