Я пытаюсь реализовать распределенную хэш-таблицу для выпечки, но некоторые вещи ускользают от моего понимания. Я надеялся, что кто-то сможет уточнить.
Отказ от ответственности : я не студент информатики. Я прошел ровно два курса по информатике в моей жизни, и ни один не занимался чем-то отдаленно сложным. Я работал с программным обеспечением в течение многих лет, поэтому я чувствую, что могу выполнить задачу по реализации, если бы я мог просто обдумать идеи. Так что я могу просто упустить что-то очевидное.
Я прочитал статью, которую опубликовали авторы [1], и добился некоторого прогресса, но я продолжаю зацикливаться на этом конкретном моменте в работе таблицы маршрутизации:
Газета утверждает, что
A узла маршрутизации таблицы, , организована в ⌈ войти 2 б N ⌉ строки с 2 б - 1 записей в каждой. 2 б - 1 записи в строке п таблицы маршрутизации каждый относятся к узлу , чье NodeId акций NodeId нынешнего узла в первом п цифры, но чьи п + - - го цифра имеет один из 2 б - 1 возможных значений, кроме п + 1 - го цифра идентификатора нынешнего узла.
выступает за конкретного приложения, как правило , переменной 4 . Давайте для простоты используем b = 4 . Так что выше
Таблица маршрутизации A узла, , организована в ⌈ войти 16 Н ⌉ строк с 15 записей в каждой. В 15 записей в строке п таблицы маршрутизации каждые относятся к узлу , чье NodeId акций NodeId нынешнего узла в первом п цифры, но чьи п + - - го цифра имеет один из 2 б - 1 возможных значений, кроме п + 1- я цифра в идентификаторе текущего узла.
Я так много понимаю. Кроме того, - это количество серверов в кластере. Я тоже это понимаю.
У меня вопрос: если строка, в которую помещается запись, зависит от общей длины ключа, почему на первый взгляд случайное ограничение на число строк? Каждый идентификатор узла имеет 32 цифры, когда (128-битные идентификаторы узла делятся на цифры по b битам). Так что же происходит, когда N становится достаточно высоким, чтобы ⌈ log 16 N ⌉ > 32 ? Я понимаю, что для достижения этого сценария потребуется 340 282 366 920 938 463 463 374 607 431 768 211 457 (если моя математика верна), но это выглядит как странное включение, а корреляция никогда не объясняется.
Кроме того, что произойдет, если у вас есть небольшое количество серверов? Если у меня меньше 16 серверов, у меня только одна строка в таблице. Кроме того, ни при каких обстоятельствах каждая запись в строке не будет иметь соответствующий сервер. Должны ли записи быть пустыми? Я понимаю, что смогу найти сервер в наборе листов, несмотря ни на что, учитывая, что несколько серверов, но тот же вопрос возникает для второй строки - что, если у меня нет сервера, который имеет идентификатор узла такой, что я могу заполнить каждую возможную перестановку n-й цифры? Наконец, если у меня есть, скажем, четыре сервера, и у меня есть два узла, которые, скажем, делят, скажем, 20 из их 32 цифр, на какую-то случайную случайность ... я должен заполнить 20 строк таблицы для этого узла, даже если это гораздо больше строк, чем я мог бы даже близко к заполнению?
Вот то, что я придумал, пытаясь объяснить это:
- Записи должны быть установлены в нулевое значение, если нет узла, который точно соответствует этому префиксу.
- Пустые строки должны добавляться до тех пор, пока не будет достаточно строк, соответствующих общей длине nodeIds.
- Если и только если нет соответствующей записи для желаемого идентификатора сообщения, воспользуйтесь поиском в таблице маршрутизации для ID узла, общая длина которого больше или равна текущему идентификатору узла, и чья запись математически ближе, чем текущая ID узла по желаемому идентификатору.
- Если в # 3 не найдено подходящего узла, предположим, что это пункт назначения, и доставьте сообщение.
Все четыре из этих предположений верны? Где-то еще я должен искать информацию об этом?
- Кондитерские изделия: Масштабируемое, децентрализованное расположение и маршрутизация объектов для крупномасштабных одноранговых систем. Автор А. Роудронг и П. Друшел (2001) - скачать здесь
Ответы:
Идея таблицы маршрутизации в Pastry (и во всех структурированных P2P-сетях) состоит в том, чтобы минимизировать ее размер, гарантируя при этом более быструю маршрутизацию.
Алгоритм маршрутизации Pastry выглядит следующим образом:
Практические сценарии обычно не типичны. Могут быть ситуации, когда в сети не так много узлов. Вот почему мы следуем шагу C выше. - Тем не менее, чтобы гарантировать корректность этого алгоритма, необходимо, чтобы каждый узел был подключен к двум ближайшим к нему узлам (с точки зрения идентификаторов). Это сформирует кольцо упорядоченных узлов [например, 1-> 3-> 4-> 9-> 10-> 11-> 1]
источник