标签: kademlia

我一直试图了解洪流磁铁技术,但我似乎无法弄清楚在打开磁铁链接时你是如何与第一个同伴联系的.

当你得到如下所示的磁力链接时,它不包含初始对等 - 只有BitTorrent信息哈希(btih)和文件名.

magnet:?xt=urn:btih:bbb6db69965af769f664b6636e7914f8735141b3&dn=ubuntu-12.04-desktop-i386.iso

根据BitTorrent和Magnets:他们如何运作？(MakeUseOf)

如果单击未指定跟踪器(tr)的磁力链接,将使用DHT找到第一个对等方.一旦你有了同伴,同伴交换也会开始.

维基百科上的DHT文章没有具体说明如何找到同伴,但在Kademlia文章中(BitTorrent DHT所基于的),它说

想要加入网络的节点必须首先完成引导过程.在此阶段,加入节点需要知道另一个节点的IP地址和端口 - 一个已经参与Kademlia网络的引导节点(从用户或从存储的列表中获得).

但它从哪里知道该节点？我没有在磁铁链接中看到地址或任何内容.由于它是分散的(无跟踪),我不希望它提前知道节点.或者DHT实际上不是分散的？

在Petar Maymounkov和DavidMazières 的Kademlia论文中,据说XOR距离是一个有效的非欧几里德度量,对于为什么有效度量的每个属性都是必要或有趣的解释有限,即:

• d(x,x)= 0
• d(x,y)> 0,如果x!= y
• forall x,y:d(x,y)= d(y,x) - 对称性
• d(x,z)<= d(x,y)+ d(y,z) - 三角不等式

为什么一个指标通常具有这些属性很重要？为什么在Kademlia Distributed Hash Table实现中路由查询的上下文中,每个属性都是必需的？

此外,本文提到,单向性(对于给定的x和距离L,仅存在单一的y表示,其d(X,Y)= 1)保证所有查询将沿着相同的路径收敛.为什么会这样？

最近,我已经阅读了Kademlia协议的文档,我试图理解协议,但我仍然有一些问题:为什么一个节点在知道它的ID而不是ip或端口时必须找到另一个节点？为什么他不知道ip或端口时有ID,他在哪里获得ID？我认为两个不同节点之间的"距离"不是路由距离或实际距离,它只是一个虚拟距离,可以用算法快速找到节点,就是这样吗？

也许我的英语不是很清楚,因为英语不是我的母语,但如果你需要,我会尽力表达自己.非常感谢!

我的理解是 IPFS 和 Bittorrent Mainline DHT 建立在分布式哈希表 (Kademlia) 之上。他们使用文件哈希作为 Kademlia 密钥来查找可能拥有此文件的对等点列表。

1- 我不明白的是，这是否都是分散的，谁从不再托管文件内容的 DHT 对等方中删除？

2- 什么阻止某人在 DHT 中免费存储大量数据？

3- 什么防止某人通过为流行文件添加大量无效对等点来破坏网络。

4- 什么阻止坏人加入 DHT 环而不遵循路由协议，从而阻止发现消息到达正确的节点。

我正在为内部集群实现自己的dht.由于它将用于像bittorrent这样的文件共享程序,"Mainline DHT"是我第一眼看到的.之后我发现"纠结"(python,dht使用扭曲矩阵),国会(python,dht使用pyev + libev),当然还有原始的"kademlia".

他们在组织k-buckets时有不同的方法:

1)congress,kademlia使用固定的160个桶,范围为2*i <=(每个id与我们的差值)<2*(i + 1),0 <= i <160.

2)主线DHT和纠缠使用动态桶.一开始他们只有一个铲斗覆盖整个空间.在它将填充8个活动节点后,桶将被拆分为2个新节点.但只有我们自己的id在那个桶里面.如果不是 - 桶将永远不会分裂.所以,很快我们将有160个最接近我们的桶和其他一些.

两种变体都足够好.但是我发现逻辑上存在巨大差异,它检测到属于某个桶的某个ID.这是我的问题.

国会和kademlia将桶子对待为"离我们最近的距离"和"离我们最远的距离".因此,我们自己的ID将始终在bucket0中.bucket1中最多2个其他ID(因为它覆盖2*1 <= x <2*2距离)将始终最接近我们.所以我的大脑没有休息,因为一切都好.

但是,如果您查看Mainline DHT或纠缠,您将看到哪些存储桶包被视为绝对节点ID包,而不是xor距离!所以在理论上全表id 0,1,2,3,4,5,6,7将在1个桶中.

所以.为什么有些实现将桶边界视为"与我们的最大/最小距离",而其他实现则将"最大/最小160位整数值"？

在Kademlia论文中,第2.4节的最后一段说明为了妥善处理高度不平衡的树木......

Kademlia节点将所有有效联系人保留在大小至少为k个节点的子树中,即使这需要拆分节点自己的ID不驻留的桶.

然而,本文的前一部分似乎表明,如果一个k-bucket已经有k个元素,那么对该k-bucket的任何进一步添加都需要删除最旧的节点(首先ping它以查看它是否存活)或以其他方式缓存添加直到该k-bucket中的插槽可用.

这篇论文似乎与这两点相矛盾.

在什么条件下应该拆分k-bucket以及为什么？将"所有有效联系人"保留在路由表中似乎不切实际,因为路由表会非常快速地变得非常大.该示例讨论了一个树,其中有许多以001开头的节点和一个以000开头的节点.以000开头的节点必须不断地将其k-bucket拆分为001以保存从001开始的每个有效节点？在一个160位的地址空间中,最终是否可能在000的路由表中存储2 ^ 157个节点？

引用块中的措辞也很混乱......

"在子树中" - 路由表的子树？

"大小为至少k个节点" - 我们使用什么度量来确定子树的大小？在这种情况下,节点是指kademlia节点还是k-buckets或其他？

这是我今天第一次读到关于Kademlia的内容,有些观点我不认为我说得对.

节点和键之间的距离是它们的值的xor.

所以,如果我有关键x和节点y,它们之间的距离是x x或y.

但是为什么要重点说出我所知道的节点并按前缀长度排序呢？这似乎没有直接与节点ID的xor连接,以找到最近的节点？

当我收到一个值的请求时,我在最近的桶中的节点中搜索我,那就是与我有最大共享前缀的节点,即160个桶的前几个桶？

或者我检查所有桶中我知道的所有节点,并计算我正在寻找的密钥和那些节点ID之间的xor,然后根据带有密钥ID的xoring结果将我的请求发送到前k个匹配？

对不起,我对DHT有点新鲜,发现网上的解释有点不清楚.

我不能完全围绕Kademlia DHT的加入过程.我在网上看过一些教程和演示文稿,但它们似乎都以相同的方式说出来,并且所有psedo代码等在大多数情况下都是相同的(实际复制/粘贴).

有人可以高度重视这个吗？

我已经阅读了有关此主题的许多文档，但是有些内容并不清楚。例如，比特种子文档（http://www.bittorrent.org/beps/bep_0005.html）指出

路由表被细分为“存储桶”，每个存储桶覆盖一部分空间。一个空表有一个存储桶，其ID空间范围为min = 0，max = 2 ^ 160。当将ID为“ N”的节点插入表中时，该节点将被放置在最小<= N <最大的存储桶中。空表只有一个存储桶，因此任何节点都必须位于其中。每个存储桶只能容纳K个节点（当前为8个），然后再变为“满”。当存储桶中充满了已知良好的节点时，除非我们自己的节点ID落入存储桶的范围内，否则无法再添加更多节点。在这种情况下，该存储桶将被两个新存储桶替换，每个新存储桶的范围均为旧存储桶的一半，并且旧存储桶中的节点将分布在两个新存储桶中。对于只有一个存储桶的新表，

关于kademlia路由表，它与其他文档有些不同，在kademlia路由表中，根据节点id的位前缀来排列存储桶，但还有另一件令人困惑的事情。当我们回复“查找节点”请求时，我们必须使用XOR操作找到8个最接近所请求节点的节点。我看到一些实现只是通过路由表中的每个项目执行XOR操作，从而找到8个最接近的项目。在我看来，CPU也在浪费。

一切都已经在桶中了。即使我们使用bit torrent文档系统建议的内容，我们也可以更快地找到可能包含所请求节点ID的存储桶，只需枚举存储桶并检查其上的最小和最大数目即可。然后，该存储桶可能应包含关闭节点，但它们是值最接近的节点，而不是异或最相似的XOR最接近的节点（据我所知）。

我使用0到99的数字进行了一个简单的测试，我想找到8个XOR最接近的数字，它们在所寻找的数字附近，但不在附近。现在，考虑一下我们的存储桶，我猜可能存储桶中的所有节点ID都是最接近的，仅是次要异常。因此，例如，如果我们拿这个存储桶，从左边取一个，从右边取一个，并搜索XOR最近的节点ID，我们将找到我们要寻找的东西，并且没有必要遍历路由中的所有节点表。

我是对的还是我错过了什么？

我想确认我对 Kademlia DHT 中的存储桶的理解。\nKademlia 有m 个 k 存储桶，其中m是网络的大小（以位为单位），k是每个存储桶存储的键值对的数量。\nm=4例如，让我们说我们可以有2^4节点，即从 0 到 15。

+========+\n| NodeId |\n+========+\n|   0000 |\n+--------+\n|   0001 |\n+--------+\n|   0010 |\n+--------+\n|   0011 |\n+--------+\n|   0100 |\n+--------+\n|   0101 |\n+--------+\n|   0110 |\n+--------+\n|   0111 |\n+--------+\n|   1000 |\n+--------+\n|   1001 |\n+--------+\n|   1010 |\n+--------+\n|   1011 |\n+--------+\n|   1100 |\n+--------+\n|   1101 |\n+--------+\n|   1110 |\n+--------+\n|   1111 |\n+--------+\n

每个节点都有0位匹配、1位匹配、2位匹配等的路由表，这就是m桶。此外，对于每个桶，它将存储k代表而不是单个 NodeId。\n因此，如果我们说 k=2，则节点 0101 的路由表将类似于：

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82         0101         \xe2\x94\x82\n\xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xa4\n|                      |\n| +==================+ |\n| |       xxxx       | |\n| +==================+ …