结构化的p2p网络是基于DHT（分布式哈希表）实现的。kad算法是DHT的一种实现。kad算法给每个节点分配了一个节点id，根据节点id之间的异或距离建立路由表。给资源设置了一个key，根据key与节点id的异或距离查找资源。
kad相关概念
-
1.两个关键的id：
- nodeid，节点id。节点包含了网络ip地址和端口号，由唯一的节点id指向这一个节点。节点id为160位的二进制表示。
- key。网络中的资源名索引和资源名以key-value键值对的形式表示，资源名经过哈希函数计算，转为160位的key。
-
2.异或距离：
由上述的两个id，把资源放置在nodeid与key的距离相近的节点上，就能实现资源的定位。也就是我们可以根据key去匹配距离相近的nodeid，然后找到在该节点上与key对应的资源value。
其中的距离指的是异或距离。也就是对两个id进行异或运算，可以是nodeid与nodeid，定位节点。或者nodeid与key，定位资源。举个例子：00110 与 00011 的异或距离为 00101，也就是5。（0⊕0=0，1⊕0=1，1⊕1=0）
-
3.异或特性:
x ⊕ x = 0，节点与它本身的异或距离为0。
x ⊕ y > 0 , if x != y，不同节点异或距离一定大于0。
x ⊕ y = y ⊕ x，异或距离是对称的。
x ⊕ y + y ⊕ z >= x ⊕ z，类似于三角形不等式，第三边的距离小于等于另外两边的距离之和。
x ⊕ y ⊕ y ⊕ z = x ⊕ z
x + y >= x ⊕ y -
4.路由表，与k-bucket:
由于节点id是一串二进制数，每一位的取值只有0或1，因此我们可以把节点id表示为二叉树的形式。以100为例，第一位是1，（从上到下）往右子树，第二位是0，往左子树，第三位是0，再往左子树。最终的叶子节点即为100。
k-buckst树形结构
我们把同一个灰色部分的节点放置在同一个列表，这个列表称为k-bucket，k桶。k桶中的k指的是每一个列表所能容纳的节点的最大个数。划分k桶是有规律的。k桶的个数跟节点id的位数有关，假设节点id的位数为n，则最多有n个k桶。第1个k桶中的节点与本地节点前n-1位id是相同，第2个k桶中的节点与本地节点前n-2位id是相同，以此类推，最后第n个k桶中的节点与本地节点第1位id就不一样了。
所有的k桶合起来也就是一个节点的路由表。
这里以nodeid为110的节点为例，共有3个k桶。第i个k桶中异或距离的范围为
。(i从0开始。）应用了上面说的规律，第1个k桶中的111与110的前2位是相同的，第2个k桶种的100、101与110的前1位是相同的。
节点id为110的路由表
-
5.协议消息:
- PING — 验证远程节点是否在线。
- STORE — 在某个节点上存储 key-value 键值对。在节点上存储资源。
- FIND_NODE — 查找节点，给定一个nodeid，被请求的节点返回与nodeid相近的k个节点。
- FIND_VALUE — 查找资源，给定一个key，被请求的节点的nodeis与key相近，并且具有该key，返回与key对应的value。
kad实现的功能
-
1.查找节点
需要用到的参数：，每次同时向
查找过程：
- 1.请求节点，向自己的k桶中的
- 2.接收节点收到请求后，查看自己的k桶，返回k个与nodeid相近的节点。
- 3.请求节点在这些返回的节点里，取出k个距离最近的节点，更新结果列表。
- 4.请求节点向结果列表里的k个节点发起 FIND_NODE 请求。
- 回到步骤2。
循环上述过程，迭代结束后，结果列表中的k个节点便是整个网络中最接近nodeid的节点。
- 1.请求节点，向自己的k桶中的
-
2.查找资源
类似于查找节点的过程。资源为value，有唯一的key对应value，key与nodeid相似，所以查找到离key最接近的nodeid，在节点处匹配到key，返回key对应的value。 -
3.维护k桶
（查找节点，是主动的更新路由表，维护k桶，是被动的更新路由表。）
当节点收到另一个节点（设为节点A）发来的任何消息（请求或是响应）时，都会更新该节点id对应的k桶。k桶中最新的节点置于最底部。- 1.如果节点A已经存在于k桶中，将节点A移到k桶的底部。
- 2.如果节点A不存在于k桶中，k桶中节点的数量少于k个，将节点A添加到k桶的底部。
- 3.如果k桶已经满了，向k桶最上面的节点B发送ping
- 节点B无响应，移除节点B，将节点A加入到k桶底部。
- 节点B有响应，将节点B移到k桶底部。丢弃节点A。
网友评论