В Kademlia все пары (ключ, значение), сохраненные узлом, кроме тех, которые были первоначально опубликованы самим текущим узлом, имеют срок действия, основанный на том, где текущий узел расположен относительно ключа. Если текущий узел состоит из k-ближайших узлов к ключу, пара (ключ, значение) истекает, когда он переживает 24 часа с момента его первоначальной публикации. Если это не k-ближайший узел, срок действия
обратно пропорционально количеству узлов между текущим узлом и узлом, идентификатор которого наиболее близок к идентификатору ключа
согласно документу Kademlia. В документе также говорится, что
это число может быть выведено из структуры сегмента текущего узла.
Кажется, есть два совершенно разных способа подсчета узлов между текущим узлом и данным узлом, и я не уверен, какой из них правильный. Далее мы предполагаем реализацию таблицы маршрутизации плоского массива, предварительно выделенный массив из 160 блоков.
Страница спецификации проектирования Xlattice Kademlia говорит, что вы должны найти индекс сегмента j, в который попал бы данный узел, и считать узлы в сегментах 0..j, считая все узлы в 0 ..j-1 и считая только узлы, которые ближе к текущему узлу, чем ключ в последнем сегменте j.
Тезис семестра Бруно Спори "Реализация распределенной хэш-таблицы Kademlia" (раздел "Расчет количества промежуточных узлов") вычисляет расстояние между текущим узлом и данным узлом, и считает узлы только в сегментах, которые имеют расстояние, меньшее или равное расстоянию между текущим узлом и данным узлом.
Оба эти метода кажутся мне правильными, но они совершенно разные и дают разные результаты. Первый метод подсчитывает узлы между текущим узлом и данным узлом на основе расстояния между текущим узлом и другими узлами в наших сегментах. Второй метод подсчитывает узлы между текущим узлом и данным узлом на основе расстояния между данным узлом и другими узлами в наших сегментах.
Например, если текущий узел имеет идентификатор 0001_0100 (для примера предположим 8-битные идентификаторы), то есть только 8 сегментов, которые содержат узлы со следующими префиксами:
0001_0101, 0001_011x, 0001_00xx, 0001_1xxx, 0000_xxxx, 001x_xxxx, 01xx_xxxx, 1xxx_xxxx.
Допустим, мы хотим рассчитать срок действия ключа 1010_0010.
Расстояние между текущим узлом и данным узлом составляет 182 (0001_0100 xor 1010_0010 = 182).
Используя первый метод, мы будем считать все узлы в сегментах 0..6 плюс узлы в сегменте 7, которые ближе к текущему узлу, чем заданный идентификатор.
Это работает, потому что расстояния между текущим узлом и всеми сегментами: 1, 2, 4, 12, 20, 52, 84, 148.
Вы можете найти их, сохранив наш идентификатор с диапазоном, который охватывает сегмент (я заменил x на 0, чтобы получить наименьший, но не обязательно самый близкий идентификатор, который попадет в этот сегмент), например, 0001_0100 xor 0001_0101 = 1 и 0001_0100 xor 1000_0000 = 148.
Все узлы до последнего будут иметь узлы, которые находятся на расстоянии <= 182 (расстояние между текущим узлом и данным идентификатором) от текущего узла. Последнее ведро может иметь узлы, которые находятся дальше.
Таким образом, мы подсчитываем количество узлов во всех 8 сегментах (с частичным подсчетом последнего). </p>
Используя второй метод, мы считаем все узлы в сегментах 1, 2, 4, 5 и 7. Мы не учитываем сегменты 0, 3, 6.
Это работает, потому что расстояния между данным ID и сегментами: 183, 180, 178, 186, 162, 130, 226, 34.
Вы можете найти их, сохранив данный идентификатор с диапазоном, который охватывает сегмент (я заменил x на 0, чтобы получить наименьший, но не обязательно самый близкий идентификатор, который попадет в этот сегмент), например, 1010_0010 xor 0001_0101 = 183 и 1010_0010 xor 1000_0000 = 34.
Только сегменты 1, 2, 4, 5 и 7 имеют узлы с расстоянием менее 182 (расстояние между текущим узлом и заданным идентификатором) относительно заданного идентификатора.
Таким образом, мы считаем узлы только в 5 сегментах из 8.
Подсчет узлов в 8/8 и 5/8 - большая разница. Какой метод является правильным? Кажется, что оба подсчитывают количество узлов между текущим узлом и заданным ключом, но результат такой разный.
Обратите внимание, что метрика xor здесь имеет место, здесь, похоже, нет ошибки. Например, расстояние между текущим узлом и узлом, находящимся в последнем сегменте, составляет 0001_0100 xor 1000_0000 = 148. Расстояние между данным узлом и тем же узлом в последнем сегменте составляет 1010_0010 xor 1000_0000 = 34. 148 xor 34 = 182, поэтому d(a, b) = d(a, c) xor d(c, b) имеет место.
Первый метод, кажется, подсчитывает все узлы, о которых знает текущий узел, которые находятся ближе, чем 182 от текущего узла. Второй метод, кажется, подсчитывает все узлы, о которых знает текущий узел, которые находятся ближе чем 182 от данного узла.
Я думаю, что второй метод более корректен, поскольку мы хотим выяснить, являемся ли мы k-ближайшим узлом к данному ключу. Когда вы находите узлы, близкие к заданному идентификатору, то есть FIND_NODE RPC, вы используете процесс, аналогичный второму способу, чтобы определить, какие сегменты содержат узлы, наиболее близкие к данному идентификатору, например, в данном примере это будут сегменты 7, 5, 4, 2, 1, 0, 3, 6 - именно в этом порядке, с ближайшим первым.
Но опять же, первый метод также имеет смысл, так как мы лучше знаем свое окружение. Мы знаем все 8 блоков узлов ближе, чем 182 к текущему узлу, в то время как мы знаем только около 5 блоков узлов ближе, чем 182 к данному ключу.