使用DHT查找信息。SHA-1。Chord协议。

Question

我正在尝试实现Chord协议，以便在小型网络中快速查找一些节点和密钥。我无法理解的是... Chord将节点和密钥视为位于环上，并且它们的位置由应用SHA-1哈希函数获得的哈希值所决定。我该如何操作这些值呢？我需要将它们作为字符串de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3，然后像这样进行比较，考虑到"a" < "b"是真的吗？还是怎么样？我怎样知道一个密钥是在另一个密钥之前还是之后？

- AndreiBogdan

Answer 1

由于键空间是一个环，单个值不能说比另一个大，因为如果你绕着环走，相反的情况就成立了。您可以说一个值是否在范围内。在Chord DHT中，每个服务器负责其前任和后继之间的值范围内的键。

我建议不要使用字符串作为哈希值。您不应该为分布式系统使用hashCode函数，但在添加新节点时需要对哈希键进行数学计算。您可以尝试将哈希转换为BigIntegers。

- kjw0188

Answer 2

SHA1哈希不是字符串，而是非常长的十六进制数字 - 它们通常被存储为字符串，因为否则需要本地160位数字类型。它们由5个32位十六进制数字构建，然后经常“串”在一起。

使用SHA1字符串作为它们所代表的数字并不难，但需要一个可以处理这样大数字的库（如BigInt或bcmath）。这些库通过从右到左逐列计算字符串中的数字来工作，就像人们使用笔和纸进行加法、乘法、除法等运算时一样。它们通常具有执行常见数学运算以及比较等操作的函数，并经常将字符串作为参数。此外，请确保在需要从十六进制转换为十进制时使用转换大数字的函数，否则您的160位十六进制数字很可能会被舍入为64位十进制浮点数或类似物，并且失去大部分精度。

更多/少于比较在和弦中用于确定范围，但是使用模数进行比较，使得诸如[64, 2]之类的范围成为可能。实际公式为

find_successor(fingers[k] = n + 2^(k-1) mod(2^160))

其中'n'是节点的sha1，'k'是finger number。

请记住，'n'通常是十六进制，而'k'和'mod(160^2)'通常是十进制，因此您需要使用BigInt hex to BigInt dec。即使您的编程框架允许您将这些变量创建为十六进制，160仍然是一个十进制（字面意思是一百六十位），此外，理解'mod(160^2)'已经足够困难了，不要再将其视为十六进制。将'n'转换为十进制，而不是将'k'等转换为十六进制，然后使用BigInt库进行数学计算，包括比较。

- JSON