S/Kademlia sibling list运行机制及高不平衡树问题解决咨询

1. sibling list 具体工作原理 #

S/Kademlia在原生Kademlia的k桶路由表基础上，新增了独立的sibling list结构，核心工作逻辑如下：

S/Kademlia论文中定义sibling list的容量与k桶参数k保持一致，优先存储与当前节点ID异或距离最小的节点集合。

• 每个节点启动后，会在节点发现过程中同步收集与自身ID异或距离最近的节点，按照距离从小到大排序存入sibling list，列表满后新的更近节点会替换掉列表中距离最远的节点
• sibling list的更新优先级高于普通k桶：每次节点收到其他节点的请求、响应等通信报文时，会优先校验该节点是否符合进入sibling list的条件，更新完成后会主动向列表内所有节点同步自身状态
• 执行数据存储、路由查询等核心操作时，节点除了遵循原生Kademlia的逐跳路由规则，还会向自身sibling list内的所有节点广播操作请求，确保近距离节点全部收到通知

2. sibling list 解决高不平衡树问题的逻辑 #

首先明确S/Kademlia的高不平衡树问题成因：原生Kademlia的k桶按ID前缀分层存储，当网络中大量节点ID集中在某一个前缀区间时（比如女巫攻击批量生成同前缀节点、或网络节点自然分布不均），路由树的对应前缀分支会异常冗长，其他分支节点极少，常规逐跳路由很容易跳过该长前缀分支的节点，导致内容查询失败、数据孤立。
sibling list通过以下特性解决该问题：

• 不依赖路由树的分层k桶存储规则，直接保留和当前节点ID最近的一批节点，哪怕这些节点全部属于同一个极深的长前缀分支，也不会被k桶的分层容量限制遗漏
• 同前缀区间的节点通过sibling broadcast机制同步所有操作请求，哪怕常规路由没有触达该不平衡分支，列表广播也能覆盖到分支内所有节点，避免数据孤立
• 当路由查询进入长前缀不平衡分支时，sibling list可以直接返回分支内所有可用节点信息，不需要按照常规k桶规则逐跳查询，大幅降低了不平衡场景下的查询跳数和失败率

内容的提问来源于stack exchange，提问作者RedAFD