В Kademlia все пары (ключ, значение), хранящиеся в узле, за исключением тех, которые были изначально опубликованы самим текущим узлом, имеют срок действия, основанный на том, где текущий узел расположен по отношению к ключу. Если текущий узел относится к k ближайшим к ключу узлам, срок действия пары (ключ, значение) истекает по истечении 24 часов с момента первоначальной публикации. Если это не k-ближайший узел, срок действия равен
обратно пропорционально количеству узлов между текущим узлом и узлом, идентификатор которого ближе всего к идентификатору ключа
согласно статье Кадемля. В документе также говорится, что
это число может быть выведено из структуры корзины текущего узла.
Кажется, есть два очень разных способа подсчета узлов между текущим узлом и данным узлом, и я не уверен, какой из них правильный. Далее мы предполагаем реализацию таблицы маршрутизации с плоским массивом, массив со 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 ведрах (с частичным подсчетом последнего).
Используя второй метод, мы подсчитываем все узлы в сегментах 1, 2, 4, 5 и 7. Мы не учитываем сегменты 0, 3, 6. Это работает, потому что расстояния между данным идентификатором и сегментами: 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 к данному ключу.
exp(k /C)в своем вычислении. - person the8472 schedule 20.06.2019