概述

在去中心化底层网络中大部分使用P2P网络，特别是运用于区块链技术中。通常为了维护整个网络会用到分布式哈希表DHT（Distributed Hash Table），而Kademlia协议是其中一种DHT技术。

Kademlia协议（简称Kad）是美国纽约大学的PetarP. Maymounkov和David Mazieres. 在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based on the XOR metric》。 Kad 通过独特的以异或算法（XOR）为距离度量基础，建立了一种全新的 DHT 拓扑结构，相比于其他算法，大大提高了路由查询速度。

算法链接:

pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

前置知识点

由于异或运算的特殊性质:

即:

A XOR A=0

A XOR B= B XOR A(无向性)

A XOR B <= A + B

A XOR B != A XOR C (A,B,C均大于0，且两两之间互不相等)

所以在Kademlia算法中，一个节点与另一个节点之间的距离(这里的距离是指ID的差值)是固定的，即，我们可以确保离某个节点距离为Y的节点有且仅有一个

正文

算法中，是以满二叉树来表示这个ID的，这里为了方便，我们直接来模拟第一个节点中的K桶存放，当前网络只有这个这8个节点，k值为4

二叉树如下(有点丑，轻喷)

理想的存入方式是，第0个元素(1在0号桶，2,3在1号桶...以此类推)，直到存到第160个桶

示意图如下:

按照理论上的逻辑应该是:

第0号节点中，该会有160个buket，每个桶里面必须得存k个元素，那么就相当于，在这个网络中，浪费了160-4=156个桶!废弃比例来到了惊人的156/160=97.5%,并且会大大降低命中的概率(比如一个文件要访问距离为1290的桶，由于该桶没有，所以会一直向后查询桶，进行大概150次的无效查询)

如何改进K桶的存储方式?

上述提到的问题，最大的原因是，网络中的节点数量少并且存储的节点树过于稀疏，那么如何在满足Kademlia查找的logN效率基础上再进行优化呢?

我们可以尝试对Kademlia算法桶的存储内容进行改良如下:

当有节点加入时，匹配到当前最符合的桶中，即需要每个桶额外存储几个元素:

startDistanceLogic(理论最近距离)

endDistanceLogic(理论最远距离)

startDistanceReal(实际最近距离)

endDistanceReal(实际最远距离)

加入节点存储在这个(理论)距离中间的即为符合条件的桶，如果该桶的大小没满，即未达到K，则正常加入该桶，如果满了，则将桶进行分裂，再将该节点分别加入分裂(一般是一分为二)后的桶中

分裂逻辑如下:(先讨论加入节点在该桶实际距离范围内的情况)

先计算出分裂后的每个桶的分隔距离(spiltDistance):

$$ \frac{(startDistanceReal+endDistanceReal)}{2} $$

然后两个桶的理论距离分别为:

前一个桶:

startDistanceLogic=min(startDistanceReal,startDistanceReal)
endDistanceLogic=spiltDistance

后一个桶:

startDistanceLogic=spiltDistance+1
endDistanceLogic=max(spiltDistance,startDistanceReal)

将节点加入进桶中

示意图如下:

假设0号节点桶中只存入了4个节点，现在距离为5的节点要加入桶，每个桶中的中间的顺序是没有意义的(应当按照Kademlia算法对于K桶内的排序进行)，这里只是方便查看

const K = 4 // 每个桶最大节点数

type NodeID *[16]byte // 假设NodeID为16字节的byte数组
type Bucket struct {
   Nodes []*Node // 存储节点指针
   Range [2]*big.Int // 存储桶的ID范围，起始和结束
}

type Node struct {
   ID NodeID
}

// calculateBucketIndex 根据节点ID计算所属桶的索引
func calculateBucketIndex(targetID NodeID, ownID NodeID) int {
   xorResult := new(big.Int).Xor(new(big.Int).SetBytes(targetID[:]), new(big.Int).SetBytes(ownID[:]))
   bigK := big.NewInt(int64(K))
   return xorResult.BitLen() - bigK.BitLen()
}

// splitBucket 分裂桶操作
func splitBucket(buckets [][]*Node, targetID NodeID, ownID NodeID, index int) {
   midPoint := big.NewInt(0).Lsh(big.NewInt(1), uint(calculateBucketIndex(targetID, ownID)-K+1)) // 计算中间点
   newBuckets := make([][]*Node, 2)
   for i := range newBuckets {
      newBuckets[i] = make([]*Node, 0, K)
   }

   // 重分配节点到新桶
   for _, node := range buckets[index] {
      nodeIndex := calculateBucketIndex(node.ID, ownID)
      if big.NewInt(0).SetBytes(node.ID[:]).Cmp(midPoint) <= 0 {
         newBuckets[0] = append(newBuckets[0], node)
      } else {
         newBuckets[1] = append(newBuckets[1], node)
      }
   }

   // 替换原有桶为新桶
   buckets[index] = newBuckets[0]
   buckets = append(buckets, newBuckets[1]) // 实际情况下需要调整索引，这里简化处理

   // 添加新节点到正确桶
   addNode(buckets, targetID, ownID)
}

// addNode 向Kademlia网络添加节点
func addNode(buckets [][]*Node, newNodeID NodeID, ownID NodeID) {
   index := calculateBucketIndex(newNodeID, ownID)
   bucket := buckets[index]

   // 检查桶是否已满
   if len(bucket) < K {
      bucket = append(bucket, &Node{ID: newNodeID})
   } else {
      splitBucket(buckets, newNodeID, ownID, index)
   }
}

若加入节点不在该桶实际距离范围内的情况，比如加入的节点为160，则需要重新计算ER，其余分裂步骤和上述一样

推广:

该方法动态拓展了K桶的值域，在Kademlia的基础上做了大幅的优化改良

按照如上的思路，每个桶中都会至多存与该节点最近的K个节点，并且对于空间的利用发挥到了极致 => 将松散的二叉树整合成为了一棵紧密的二叉树，空间利用率接近100%并且查找的时候的速度优于理论中的logN

优缺点:

优点: 提高了查找效率，节约了空桶的地址空间，适合小的分布式P2P网络结构

缺点:由于每次节点的加入/退出都可能涉及到对于桶的重新组合，所以不适合节点下线/上线非常频繁的场景(因为对于桶的读写锁占用会涉及到3个桶对象，而理论上的Kademlia算法节点加入和删除只涉及到1个桶)