java - 使用 DHT 查找内容。SHA-1。和弦协议

Question

我正在尝试实现 Chord 协议，以便在小型网络中快速查找一些节点和密钥。我无法弄清楚的是...... Chord cosideres 节点和键被放置在一个圆圈上。它们的位置由应用 SHA-1 哈希函数获得的哈希值决定。我究竟如何使用这些值？考虑到这一点，我是否将它们作为字符串de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3进行比较"a" < "b" is true？或者怎么做？我如何知道一个键是在另一个之前还是之后？

Answer 1

由于键空间是一个环，因此不能说单个值大于另一个值，因为如果您绕着环走相反的方向，则相反。你可以说一个值是否在一个范围内。在 Chord DHT 中，每个服务器负责在它与其前身之间的值范围内的键。

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

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”是手指编号。

请记住，'n' 将是十六进制，而 'k' 和 'mod(160^2)' 通常是 dec，所以这是需要 BigInt hex 到 BigInt dec 的地方。

即使您的编程框架允许您将这些变量创建为十六进制，160 也是一个 dec（字面意思是 1 位 60 位），此外，如果不将其可视化，将您的大脑包裹在“mod(160^2)”周围已经足够困难了作为十六进制。将 'n' 转换为 dec 而不是将 'k' 等转换为 hex ，然后使用 BigInt 库进行包括比较在内的数学运算。