如何将Kademlia路由表表示为数据结构 [英] How to represent a kademlia routing table as data structure
问题描述
The kademlia paper talks about the the organization of buckets, splitting, merging and finding the correct bucket to insert in abstract, concise and confusing terms.
§2.2讨论了一组固定的160个存储桶，每个存储桶覆盖了键空间的固定子集.但是后面的章节将涉及覆盖键空间不同部分的其他拆分和存储桶.不太适合固定列表
§2.2 talks about a fixed set of 160 buckets with each bucket covering a fixed subset of the keyspace. But later chapters involve additional splitting and buckets covering different parts of the keyspace. That don't fit well into a fixed list
组织存储桶的正确方法是什么?
What is the correct way to organize buckets?
元:由于困惑反映在许多问题中，部分信息分散在许多答案中，因此本问答集旨在提供易于链接的说明
推荐答案
混淆源于纸张的不同版本
这是预印本，主要用于从理论上概述卡德姆里亚的基本特性，但仍反映在完整版的§2.2和§3中.
This is from the pre-print version and mostly used to outline basic properties of kademlia in a theoretical manner and still reflected in §2.2 and §3 of the full version.
许多现实世界中的实现都采用了这种方法，但是并没有实现存储桶拆分，合并或
Many real-world implementations implement this approach but they don't implement bucket splitting, merging or node multihoming.
这涉及将联系人放入与节点共享i前缀位的第i个存储桶中.这意味着布局使用相对于节点自己的ID的距离.
It involves putting contacts into the ith bucket that shares i prefix bits with the node. Which means the layout uses distances relative to the node's own ID.
这在§2.4部分中进行了描述.
This is described in section §2.4.
实施细化，如处理§2.4末尾描述的高度不平衡的树或§4.2中所述的更深层的非本地拆分，则需要将每个存储桶与其覆盖的键空间范围相关联，可以将其表示为类似于CIDR范围，即，起始ID和为掩盖ID的尾部而共享的前缀位数.
To implement refinements such as handling highly unbalanced trees described towards the end of §2.4 or deeper non-local splitting described in §4.2 one needs to associate each bucket with the keyspace range it covers, this can be expressed similar to CIDR ranges, i.e. a start ID and the number of prefix bits shared to mask off the tail of the ID.
拆分存储桶是通过将两个新存储桶的前缀位的数量增加一，并将添加的位分别设置为0和1来完成的.
Splitting a bucket is performed by increasing the number of prefix bits by one and setting the added bit to 0 and 1 respectively for two new buckets.
与平面布局不同，此结构不涉及相对于节点自己的ID的距离，尽管某些决定是基于节点自己的ID是否会落入桶中.
Unlike the flat layout this structure does not involve distances relative to the node's own ID, although some decisions are based on whether the node's own ID would fall into a bucket.
由于此类路由表中存储区的数量随时间的变化而有所变化，因此必须在可调整大小的数据结构中表示，因此在§2.4中进行了提及.由于无法再通过固定索引进行访问，因为直到检查了前缀范围后，才可以知道覆盖任何特定节点ID的确切存储桶，如果要避免扫描以下内容，则需要某种O(log n)搜索.每次都列出整个存储桶列表.
按存储桶将要覆盖的最低ID对存储桶进行排序是实现此目的的一种自然方法. BTree或与二进制搜索结合的排序数组可用于实现此目的.
Since the number of buckets in such a routing table varies over time it has to represented in a resizable data structure, this is mentioned in §2.4. Since access can't be done by a fixed index anymore since the exact bucket that will cover any specific node ID is not known until the prefix-ranges have been examined some kind of O(log n) search is needed if one wants to avoid scanning the whole bucket list each time.
Sorting the buckets by the lowest ID that the bucket would cover is a natural approach to achieve this. BTrees or sorted arrays combined with binary search can be used to achieve this.
无论采用哪种方法，都不会使用与请求目标琐碎，因为任何一个铲斗都可能不足以装满它，因此需要遍历多个铲斗.扫描整个路由表以寻找最佳可用候选者可能更简单.
Regardless which approach you take, populating a response to find_node requests with the correct set of contacts that match the request's target is not trivial since any single bucket may be insufficient to fill it and thus multiple buckets need to be traversed. It may be simpler to scan the whole routing table for the best available candidates for the reply.
这篇关于如何将Kademlia路由表表示为数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
