P2P 与分布式存储 / 系统课时

K 桶怎样保存远近不同的节点

K 桶怎样保存远近不同的节点

节点发现的新邻居越来越多时,路由表不能无限增长。本课用 8 位节点 ID 和每桶 2 个位置,亲手计算 XOR 距离、观察 K 桶的远近分布,并模拟新节点加入、旧节点应答和离线淘汰后的表项变化。

学习目标

  • 按 XOR 距离将节点放入对应 K 桶,理解桶号与共同前缀的关系。
  • 模拟桶满时的活跃性探测、节点保留和失效替换。
  • 根据模拟输出检查各桶占用,并辨别路由表与地址缓存的职责。

XOR 距离怎样划分远近

Kademlia 把节点标识映射到固定长度的键空间,距离定义为 selfId XOR peerId,不是 IP 延迟或物理距离。对于非零距离 d,教学模型中的桶号为 d.bit_length() - 1:最高不同位越靠左,距离越远;d=0 表示自身,不加入路由表。

设本地 8 位 ID 为 0x50(二进制 01010000),每个桶覆盖一个不重叠的距离区间:

桶号 XOR 距离范围 示例节点 XOR 结果
0 1 0x51 1
1 2~3 0x53 3
2 4~7 0x54 4
3 8~15 0x58 8
4 16~31 0x40 16
5 32~63 0x70 32
6 64~127 0x10 64
7 128~255 0xD0 128

例如 0x50 XOR 0x40 = 0x10,最高置位在第 4 位,所以 0x40 进入桶 4;0xD0 与本地最高位不同,进入桶 7。相反,桶 0 仅包含一个可能的 8 位 ID,远处的桶 7 对应 128 个可能的 ID,桶数相同不等于节点数相同。

本地节点与八个 XOR 距离区间对应的 K 桶

真实 libp2p Kad-DHT 使用更长的哈希路由键,通常按共同前缀长度管理邻居;某些实现采用可分裂的前缀树。这里的 8 位桶号只是把相同的 XOR 分组原理缩小,不能当作某个 SDK 的内部数组下标。

桶满后怎样决定留谁

经典 Kademlia 的每个桶最多保存 K 个联系人,顺序从最久未见到最近确认活跃。已有节点再次被有效通信确认后移到队尾;新节点进入未满的桶时直接排在队尾。

当桶已经装满,不是直接踢掉最老的节点,而是先探测队首联系人:

  1. 如果队首能响应 PING,就把它移到队尾,原候选暂不写入这个桶。
  2. 如果探测判定队首失效,就删除该联系人,把候选追加到队尾。
  3. 如果候选已在桶中,只更新其最近活跃位置,不重复占用名额。

K 桶加入、活跃探测和失效替换流程

用 Python 重放节点加入与离线

以下代码在 Python 3.10 及以上版本可直接运行,不依赖第三方库。K=2 是便于观察的教学值;online 是预设的探测结果,不执行真实 libp2p PING。先让桶 4 收录 0x40、0x41,再用新候选 0x42 检查两种分支。

python
from collections import defaultdict

SELF_ID = 0x50
K = 2
buckets = defaultdict(list)
online = {0x40: True, 0x41: True}

def bucket_index(peer_id):
    distance = SELF_ID ^ peer_id
    if distance == 0:
        return None
    return distance.bit_length() - 1

def show(peers):
    return "[" + ", ".join(f"0x{peer:02X}" for peer in peers) + "]"

def observe(peer_id):
    index = bucket_index(peer_id)
    if index is None:
        return "跳过自身"
    bucket = buckets[index]
    # 桶内按最久未见到最近活跃排列。
    if peer_id in bucket:
        bucket.remove(peer_id)
        bucket.append(peer_id)
        return f"刷新 0x{peer_id:02X}"
    if len(bucket) == K:
        oldest = bucket.pop(0)
        # 以测试状态模拟 PING 响应;这里不发网络请求。
        if online.get(oldest, True):
            bucket.append(oldest)
            return f"保留 0x{oldest:02X},拒绝 0x{peer_id:02X}"
        bucket.append(peer_id)
        return f"淘汰 0x{oldest:02X},加入 0x{peer_id:02X}"
    bucket.append(peer_id)
    return f"加入 0x{peer_id:02X},桶{index}"

# 先让各距离段有节点,并使桶 4 装满。
for peer in (0x51, 0x53, 0x54, 0x58, 0x40, 0x41, 0x70, 0x10, 0xD0):
    observe(peer)

print("非空桶号:", sorted(buckets))
print("桶4初始:", show(buckets[4]))
print("在线检测:", observe(0x42))
print("桶4更新:", show(buckets[4]))
online[0x41] = False
print("离线检测:", observe(0x42))
print("桶4更新:", show(buckets[4]))
print("重复发现:", observe(0x40))
print("桶4最终:", show(buckets[4]))

预期输出:

text
非空桶号: [0, 1, 2, 3, 4, 5, 6, 7]
桶4初始: [0x40, 0x41]
在线检测: 保留 0x40,拒绝 0x42
桶4更新: [0x41, 0x40]
离线检测: 淘汰 0x41,加入 0x42
桶4更新: [0x40, 0x42]
重复发现: 刷新 0x40
桶4最终: [0x42, 0x40]

第一次桶满时,探测 0x40 成功,所以它留在表中并移到队尾,队首变成 0x41。之后将 0x41 的模拟状态改为离线,再次提交 0x42,才会发生替换。最后重新观察 0x40,只改变顺序,不增加桶内节点数。

用桶占用检查分布和边界

执行完代码后,桶 0、1、2、3、5、6、7 各有 1 个节点,桶 4 有 2 个,总计 9 个;所有桶都没有超出 K=2。这说明容量限制是按桶执行的,不是整张表最多只能放 2 个节点。即使桶 7 的距离范围比桶 0 大 128 倍,也不代表它能存放更多条目。

真实部署时还要区分三类状态:Peerstore 中保存的地址未必可拨通;传输层连接成功未必意味着节点已进入 DHT 路由表;路由表中曾经活跃的联系人也可能随后离线。路由表应根据 DHT 的验证和探测结果更新,而不是仅凭发现事件或缓存地址批量写入。

可以把示例中的 0x42 改为 0x43 再运行:它与 0x50 的 XOR 距离为 19,仍进入桶 4,替换逻辑不变。工程中的 K 常取 20,例如 libp2p Kad-DHT 规范 推荐此值;具体桶结构、候补缓存和失效判断仍以所用实现为准。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

K 桶怎样保存远近不同的节点

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通