Open TianEx opened 5 years ago
Kademlia是分布式哈希表DHT的一种，在DHT中，每个节点分布维护一部分存储内容以及其他节点的路由信息，使得网络中任何节点的增删对整个系统的影响尽可能小。
在分布式存储下必然需要处理两个问题： 1.存储负载如何均匀分配到各个节点 2.查询尽可能高效简单
首先，对于每个节点本身包含两个属性——节点id以及socket，同时每个节点需要维护分配存储的内容以及部分其他节点的路由信息（之所以每个节点不维护全量路由信息，一方面是由于分布式环境下节点赠删频繁，而每次变动都需要全网广播所有节点的路由表更新导致成本高昂，另一方面涉及路由安全）。 其次，为了尽量减少节点的up/down对系统的影响，在DHT中往往通过hash计算得到的值映射到对应节点上，这也就要求hash算法的值域和节点id的值域保持一致，同时存储在最接近hash值的n个节点上。
那么一个节点如何查找指定内容的节点？在Kademlia中为了高效查询，每个节点的路由表都是按照距离分层——所谓距离是指节点间的异或XOR的值，即节点记录的路由信息实际按相同位来分层。 比如，对于hash得到id为0110的节点，如果有另一个节点id只有最后1位不同，那么它的id只能是0111，此时两者距离位1；而如果节点id从倒数第二位开始就不同，那么此节点有两个，与其的距离分别2和3——即如果节点id从倒数第n位开始不同，那么这样的节点有2^n-1个，与base节点的距离范围【2^n-1~2^n）。 换个话说，如果将整个网络中所有节点看作一个按节点id排列的二叉树，树中每个叶子就是一个节点，同一子树即为一层。 这样每个节点只需维护一部分路由，并按距离分层，这样虽然对于某一个节点来说，每层中实际存在的节点逐渐增多，但每个节点在自己的路由表中只记录n个节点socket——如果节点id有128位，那么每个节点中分为128层（即128个bucket），同时整个网络中最多可以容纳2^128个节点。
Kademlia的查询机制保证对于任意n个节点，最多只需要查询log2(n)次即可找到目标节点。
基本原理
Kademlia是分布式哈希表DHT的一种，在DHT中，每个节点分布维护一部分存储内容以及其他节点的路由信息，使得网络中任何节点的增删对整个系统的影响尽可能小。
在分布式存储下必然需要处理两个问题： 1.存储负载如何均匀分配到各个节点 2.查询尽可能高效简单
首先，对于每个节点本身包含两个属性——节点id以及socket，同时每个节点需要维护分配存储的内容以及部分其他节点的路由信息（之所以每个节点不维护全量路由信息，一方面是由于分布式环境下节点赠删频繁，而每次变动都需要全网广播所有节点的路由表更新导致成本高昂，另一方面涉及路由安全）。 其次，为了尽量减少节点的up/down对系统的影响，在DHT中往往通过hash计算得到的值映射到对应节点上，这也就要求hash算法的值域和节点id的值域保持一致，同时存储在最接近hash值的n个节点上。
那么一个节点如何查找指定内容的节点？在Kademlia中为了高效查询，每个节点的路由表都是按照距离分层——所谓距离是指节点间的异或XOR的值，即节点记录的路由信息实际按相同位来分层。 比如，对于hash得到id为0110的节点，如果有另一个节点id只有最后1位不同，那么它的id只能是0111，此时两者距离位1；而如果节点id从倒数第二位开始就不同，那么此节点有两个，与其的距离分别2和3——即如果节点id从倒数第n位开始不同，那么这样的节点有2^n-1个，与base节点的距离范围【2^n-1~2^n）。 换个话说，如果将整个网络中所有节点看作一个按节点id排列的二叉树，树中每个叶子就是一个节点，同一子树即为一层。 这样每个节点只需维护一部分路由，并按距离分层，这样虽然对于某一个节点来说，每层中实际存在的节点逐渐增多，但每个节点在自己的路由表中只记录n个节点socket——如果节点id有128位，那么每个节点中分为128层（即128个bucket），同时整个网络中最多可以容纳2^128个节点。
Kademlia的查询机制保证对于任意n个节点，最多只需要查询log2(n)次即可找到目标节点。
工程实现