标签: dht

在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，我们将找到我们要寻找的东西，并且没有必要遍历路由中的所有节点表。

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

有谁知道utorrent如何通过DHT实现“投票”系统？

我在网上看，但几乎没有关于它的信息。

一些信息：http : //lists.ibiblio.org/pipermail/bittorrent/2011-January/002413.html

http://arxiv.org/ftp/arxiv/papers/1305/1305.0711.pdf

你会收到一条类似这样的消息： { a: { id: '907050177fb05376db71ce066663819503eb0a9a', target: '546d6d0e5aacfae66299f26a300a428c497b23b5', token: '5b3f3de3d4f5ba42721dac14b2076dc64bc829da', vote: 0 }, q: 'vote', t: '+=\u0000\u0000', v: 'UT??', y: 'q' }

我唯一不明白的是target他们说它sha1(info-hash + "rating")但我不知道。所以评级 1-5 和 0 是投票的查询。所以如果一个 infohash 有 5 票，范围从 1 到 5，你会收到 5 个回复吗？

有没有人玩过这个？

我想确认我对 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| +==================+ …

我需要一个纯.Net持久散列表/二进制树,功能类似于berkeley-db Java版.

在功能上它应该与DHT类似,如memcached和速度等,但它不必分发.本质上,我正在寻找一个持久的哈希表.

有没有人有任何想法或建议？

类似的问题也在这里:在C#中寻找一个简单的独立持久字典实现

保罗

我熟悉分布式哈希表 (DHT) 的工作原理。是否可以编写一个将数据存储到现有 DHT（例如 Kademlia 或 Mainline DHT）的程序？是否有一个简单的“Hello World”类型的程序可以显示最简单的方法来执行此操作？

自从2001年全部问世以来,四大P2P分布式哈希表(DHT)覆盖网络(Pastry,CAN,Chord和Tapestry)发生了什么？

我知道学术项目持续了几年,其中一些仍然出现零星的维护版本,但有没有最终大规模,非学术用途？围绕其中任何一个还有一个活跃的开发社区吗？

我已经通过谷歌和维基百科进行了几次旅行,但是没有关于最近发生的事情的真实信息,他们的网站都奄奄一息.

更新:我看到Chimera(Tapestry的继任者)仍在积极开发中,最近的研究出版物:http://current.cs.ucsb.edu/projects/chimera/index.html

更新#2:如果问题是某人为-1,我应该更清楚一下编程方面 - 我对通用P2P覆盖网络库和相关标准感兴趣,这些标准将为P2P社交网络奠定坚实的基础应用程序.我所看到的所有现有的,包括Chimera,似乎都太弱了,没有开发和支持和/或过时,无法形成一个坚实的基础设施层.我想知道我还有其他选择.

更新#3:主线DHT似乎在这里产生了一些问题.它基于Kademlia,就我而言,它主要用作Bittorrent的分布式搜索协议.

问题取自这里： https: //groups.google.com/forum/#!topic /byu-cs-460-computer-networking/hpESI0NapmY

“我在考虑分布式哈希表如何存储数据。我知道每个节点都有一个标识符，然后数据存储在标识符与其（数据）哈希值最接近的后继节点上。我也明白当节点加入或离开网络时，数据将被传输以反映网络中存在的新节点集。

我不明白的是，当节点在移交数据之前死亡时会发生什么。那数据丢失了吗？也许我真正的问题是：如何保证数据在 DHT 中不会丢失？”