Kademlia算法 理解 总结
Kademlia 分布式存储路由算法了，DHT的一种，P2P广泛使用的一种节点发现查找算法
1. 要素
节点ID：即NodeID，160bit
信息：<key, value> key是存储信息的hash值，
2. 距离
Kad算法定义了一种逻辑距离的计算方法，两个NodeID 进行XOR异或操作，结果作为距离值，例如节点a的ID 0010001，节点b的ID 0010010，则ab距离为 0010001 XOR 0010010 == 3， 节点c的ID 0001001，则ac距离为 24。
信息存储在与key相等的NodeID，或者与key距离最近的节点上
3. 目的
查找节点，查找vlaue
4. 路由表
每个节点维护一份路由表，每个路由表，有多个list组成，list个数由NodeID bits数组成，NodeID 160bits，与其他节点ID相比，拥有不同比特数的个数有0~159种，即list有160个，又规定每个list中最多有k个信息，所以也叫k-桶
所以由下表：
从高位向低位看160bit，
list 0: 前面159bit相同，第160bit不同 原始NodeID 为xxxxxxxxx...xxxx0
xxxxxxxxx...xxxx0
xxxxxxxxx...xxxx1 ----> 只有1个，距离为1，即 [1,2)
list 1: 前面158bit相同，第159bit不同 原始NodeID 为xxxxxxxxx...xxx00
xxxxxxxxx...xxx00
xxxxxxxxx...xxx10
xxxxxxxxx...xxx11 ----> 有2个，距离为2,3， 即[2,4)
list 2: 前面157bit相同，第158bit不同 原始NodeID 为xxxxxxxxx...xx000
xxxxxxxxx...xx000
xxxxxxxxx...xx100
xxxxxxxxx...xx101
xxxxxxxxx...xx110
xxxxxxxxx...xx111 ----->有4个，距离为4,5,6,7 即[4,8)
。
。
。
list159: 前面第1bit不同
000000000...00000
1yyyyyyyyy...yyyyyy ---- y的组合有2的159次方个，距离从2的159次方~2的160次方个， 最多取k个。
5. K-桶更新
list里面节点，根据访问时间尽心排位，最新访问的放在尾部，最久访问的放在头部
收到节点的NodeID, 计算本节点与新节点的距离，找到对应的list
如果list里面有该节点，则把该节点移到尾部
如果list里面没有该节点
list里面不足k个，添加新节点到尾部
list里面超过k个，对list 头部节点进行访问，
如果头部节点没有回应，则移除，把新节点加到尾部
如果头部节点回应，移到尾部，忽略新节点
6. Kad 4种RPC：PING STORE FIND_VALUE FIND_NODE
PING: 探测一个Node是否在线
STORE: 以<key,value>为参数，通知另一个node保存，以供以后取用
FIND_NODE: 以ID或key为参数，接收者返回它所知道的距离该ID最近的k个Node的信息，k个node不一定来自一个k-桶list，除非它所有的k-桶中node总数不足k个，否则要凑足k个
FIND_VALUE: 以ID或者key为参数，如果接收者前面收到过STORE，key正好是前面收到的<key value>, 则返回这个value，如果没有，就按照FIND_NODE流程，返回k个距离最近的Node的信息
另外所有的RPC消息中都有随机数，返回时要保持不变，用来做验证
7. 节点查找(node lookup): 找到距离给定的ID最近的k个node
定义并发数a,
从最近的k-桶中取出a个最近的node，然后向a个node并行发送，异步FIND_NODE消息
从上一步收到回复后，就可以再发送FIND_NODE给返回的Node，
查询结束，发送者已经向K个最近的node发了消息并收到回应
8. 存储<key value>:
先用node lookup查找到k个最近的node
然后向他们发送STORE命令
9. 查找<key value>
使用FIND_VALUE代替FIND_NODE 进行 node lookup, 一旦有其他node返回了要的value，就结束
10. node加入网络：
首先获得一个已经在网络中的node
把它加入到k-桶
然后对自己的ID进行lookup
刷新所有的k-桶