Использование DHT для поиска материала. SHA-1. Chord protocol

Question

Я пытаюсь реализовать протокол Chord, чтобы быстро найти некоторые узлы и ключи в небольшой сети. То, что я не могу понять, это ... Аккорд выделяет узлы и ключи как находящиеся на цирке. И их размещение диктуется хэш-значениями, полученными с помощью хэш-функции SHA-1. Как именно я могу работать с этими значениями? Я могу сделать их как строку de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3, а затем сравнить их как таковые, учитывая, что "a" < "b" is true? Или как? Как узнать, есть ли ключ до или после другого?

Answer 1

Поскольку пространство ключей является кольцом, нельзя сказать, что одно значение больше другого, потому что, если вы идете в другую сторону по кругу, противоположное имеет значение true. Вы, , можете указать, значение находится в пределах диапазона или нет. В Chord DHT каждый сервер отвечает за клавиши в диапазоне значений между ним и его предшественником.

Я бы посоветовал использовать строки для хэш-значений. Вы shouldn't use the hashCode function for distributed systems, но при добавлении новых узлов вам нужна математика на хэш-ключах. Вы можете попробовать преобразовать хеши в BigIntegers.

Answer 2

хэши sha1 не являются строками, а очень длинными шестнадцатеричными числами - они часто хранятся в виде строк, поскольку в противном случае они требовали бы родной 160-битный тип номера. Они построены как 5 32-битных шестнадцатеричных чисел, а затем часто «нанизаны» вместе.

Использование строк sha1 в качестве чисел, которые они представляют, не является трудным, но требует библиотеки, которая может обрабатывать такие большие числа (например, BigInt или bcmath). эти библиотеки работают, вычисляя числа внутри строки один столбец за раз справа налево, подобно человеку, когда вы используете перо и бумагу для добавления, умножения, деления и т. д., они обычно будут иметь функции для выполнения общей математики как сравнение скважин и т. д., и часто принимают строки в качестве аргументов. Кроме того, убедитесь, что вы используете функцию для преобразования больших чисел в любое время, когда вам нужно перейти от hex к dec, иначе ваш 160-битный шестнадцатеричный номер, скорее всего, будет округлен до 64-битного dec float или аналогичного и потеряет большую часть его точности.

больше/меньше, чем сравнения : используются в аккордах до диапазонов фигур, но делают это, используя modulo, чтобы они «обертывались», делая диапазоны, такие как [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 (буквально означает один преследуемый и шестьдесят бит), и, кроме того, обертывание вашего мозга вокруг «mod (160^2)» уже тяжело достаточно, не визуализируя его как шестую. конвертировать 'n' в dec вместо преобразования 'k' и т. д. в hex, а затем использовать библиотеку BigInt для выполнения математики, включая сравнения.