Кондитерские изделия (DHT) - Pastry (DHT)
- В этой статье описывается распределенная хеш-таблица кондитерских изделий. Для еды см. Кондитерские изделия.
Кондитерские изделия является оверлейная сеть и сеть маршрутизации для реализации распределенная хеш-таблица (DHT) аналогично Аккорд. В пары ключ-значение хранятся в резервном пиринговый сеть подключенных Интернет хосты. Протокол загруженный снабдив его айпи адрес однорангового узла уже в сети и с этого момента через таблицу маршрутизации, которая динамически строится и восстанавливается. Утверждается, что из-за его избыточности и децентрализации нет единая точка отказа и любой отдельный узел может покинуть сеть в любое время без предупреждения и с небольшой вероятностью потери данных или вообще без нее. Протокол также может использовать метрику маршрутизации, предоставленную внешней программой, например пинг или же трассировка, чтобы определить лучшие маршруты для хранения в своей таблице маршрутизации.
Обзор
Хотя функциональность распределенной хеш-таблицы в Pastry практически идентична другим функциям DHTs, то, что отличает его от других, - это сеть с наложением маршрутизации, построенная поверх DHT концепция. Это позволяет кондитерским изделиям реализовать масштабируемость и Отказоустойчивость других сетей, снижая при этом общую стоимость маршрутизации пакета от одного узла к другому, избегая необходимости лавинной рассылки пакетов. Поскольку метрика маршрутизации предоставляется внешней программой на основе IP-адреса целевого узла, метрику можно легко переключить на минимальное количество переходов, минимальную задержку, максимальную пропускную способность или даже общую комбинацию показателей.
Ключевое пространство хеш-таблицы принято круглым, как и ключевое пространство в Аккорд system, а идентификаторы узлов - это 128-битные целые числа без знака, представляющие позицию в круговом пространстве ключей. Идентификаторы узлов выбираются случайным образом и единообразно, поэтому одноранговые узлы, находящиеся рядом по идентификатору узла, географически разнесены. Наложенная сеть маршрутизации формируется поверх хеш-таблицы, когда каждый одноранговый узел обнаруживает и обменивается информацией о состоянии, состоящей из списка конечных узлов, списка соседей и таблицы маршрутизации. Список конечных узлов состоит из L/ 2 ближайших узла по идентификатору узла в каждом направлении по кругу.
В дополнение к листовым узлам есть еще список окрестностей. Это представляет собой M ближайшие одноранговые узлы по метрике маршрутизации. Хотя он не используется непосредственно в алгоритме маршрутизации, список окрестностей используется для поддержания принципов локальности в таблице маршрутизации.
Наконец, есть сама таблица маршрутизации. Он содержит по одной записи для каждого назначенного ему адресного блока. Для формирования адресных блоков 128-битный ключ делится на цифры, каждая цифра б бит, давая систему нумерации с основанием 2б. Это разделяет адреса на отдельные уровни с точки зрения клиента, причем уровень 0 представляет собой общий префикс с нулевой цифрой между двумя адресами, уровень 1 - общий префикс с одной цифрой и т. Д. Таблица маршрутизации содержит адрес ближайшего известного однорангового узла для каждой возможной цифры на каждом уровне адреса, за исключением цифры, которая принадлежит самому одноранговому узлу на этом конкретном уровне. Это приводит к хранению контактов на уровень, количество уровней масштабируется как . Ценности и представляют рабочие значения в типичной сети.
Маршрутизация
Пакет может быть направлен на любой адрес в пространстве ключей, независимо от того, существует ли одноранговый узел с этим идентификатором узла или нет. Пакет направляется в надлежащее место в кольцевом кольце, и одноранговый узел, идентификатор узла которого ближе всего к желаемому месту назначения, получит пакет. Каждый раз, когда одноранговый узел получает пакет для маршрутизации или хочет отправить пакет, он сначала проверяет свой листовой набор и направляет его непосредственно к правильному узлу, если он обнаружен. Если это не удается, одноранговый узел затем обращается к своей таблице маршрутизации с целью найти адрес узла, который имеет более длинный префикс с адресом назначения, чем сам одноранговый узел. Если у однорангового узла нет контактов с более длинным префиксом или контакт умер, он выберет однорангового узла из своего списка контактов с таким же префиксом длины, чей идентификатор узла численно ближе к месту назначения, и отправит пакет этому одноранговому узлу. Поскольку количество правильных цифр в адресе всегда либо увеличивается, либо остается неизменным - а если оно остается неизменным, расстояние между пакетом и его местом назначения уменьшается - протокол маршрутизации сходится.
Приложения на основе кондитерских изделий
Само Pastry определяет, как ключи распределяются между узлами и как можно найти узел, ответственный за хранение ключа. Используя это как основу для более высокого протокол позволяет Pastry реализовывать такие функции, как распределенная файловая система, система подписки и публикации или любая другая система, которая может быть сведена к хранению значений и их последующему извлечению.
ПРОШЛЫЙ
PAST - это распределенная файловая система, расположенная поверх Pastry. Файл сохраняется в системе путем вычисления хеш-значения его имени файла. Затем Pastry направляет содержимое файла в узел в круговом пространстве ключей, ближайший к хешу, полученному из имени файла. Затем этот узел отправит копии файла в k узлы, ближайшие к фактическому ключу, большинство из которых, вероятно, будут конечными узлами этого узла и, следовательно, доступны напрямую. Извлечение данных осуществляется путем перехеширования имени файла и маршрутизации запроса данных через Pastry в нужное место в пространстве ключей. Запрос может быть выполнен любым из k узлы, у которых есть копии данных. Это обеспечивает как избыточность данных, так и распределение нагрузки. Поскольку соседние узлы в пространстве ключей географически разнесены, вероятность того, что все k из них будет отключено при этом очень мало. Что еще более важно, поскольку протокол маршрутизации Pastry стремится минимизировать пройденное расстояние, ближайший узел к машине, сделавшей запрос (согласно метрике), скорее всего, будет тем, что ответит данными.
SCRIBE
SCRIBE - это децентрализованная система публикации / подписки, которая использует Pastry для управления маршрутами и поиска хостов. Пользователи создают темы, на которые могут подписаться другие пользователи. После создания темы владелец темы может публиковать в ней новые записи, которые будут распространяться в многоадресная передача дерево для всех узлов SCRIBE, которые подписались на тему. Система работает, вычисляя хэш имени темы, объединенный с именем пользователя, которому эта тема принадлежит. Этот хэш затем используется как ключ Pastry, и издатель затем направляет пакеты на узел, ближайший к ключу, используя протокол маршрутизации Pastry, чтобы создать корневой узел темы на этом узле. Затем люди подписываются на тему, вычисляя ключ из темы и имени издателя, а затем используя Pastry для маршрутизации сообщения подписки на тему к корневому узлу. Когда корневой узел получает сообщение о подписке от другого узла, он добавляет идентификатор узла в свой список дочерних узлов и начинает действовать как сервер пересылки темы.
Децентрализация достигается за счет того, что все узлы в сети отслеживают сообщения подписки, проходящие мимо них на пути к корневому узлу тем. Если это тема, на которую подписан текущий узел, он перестанет пересылать пакет к корневому узлу и добавит узел, пытающийся подписаться, в качестве одного из своих дочерних узлов. Таким образом формируется древовидная структура с корневым узлом наверху, отправляющим первые несколько узлов-подписчиков, а затем каждый из этих узлов пересылает сообщения своим дочерним узлам и так далее. Поскольку пакеты от случайных узлов в сети Pastry, предназначенные для одного и того же узла, очень скоро в конечном итоге проходят по одному и тому же пути, они в конечном итоге присоединяются к любой части дерева, ближайшей к ним в сети Pastry. Поскольку каждый переход по маршруту кондитерских изделий представляет собой локально лучший маршрут в соответствии с используемой метрикой маршрутизации, сообщение о подписке ищет ближайшую часть дерева и прикрепляется к ней.
Наконец, отказоустойчивость среди членов дерева распределения достигается за счет использования тайм-аутов и пакетов поддержки активности, при этом фактические передачи данных дублируются в качестве пакетов поддержки активности для минимизации трафика. Если дочерний узел какое-то время не получает известий от своего родителя, он направляет новое сообщение о подписке к корневому узлу дерева, повторно присоединяясь к тому месту, где он сталкивается с деревом этой темы. Если родитель не получает известие от ребенка в течение периода ожидания, он удаляет ребенка из своего списка дочерних элементов. (Если это действие приводит к тому, что его дочерний список становится пустым, родительский элемент вообще перестает действовать как сервер пересылки.) Единственная оставшаяся точка отказа - это точка отказа корневого узла, и сама Pastry автоматически преодолевает это. Поскольку Pastry дублирует ключи среди нескольких узлов, ближайших к фактическому значению ключа, на корневом узле уже настроены зеркала, которые находятся в бездействии. Если корневой узел переходит в автономный режим, что снова обнаруживается через тайм-ауты, следующий ближайший узел Pastry начинает действовать как корневой узел. Когда создатель темы пытается опубликовать новый материал, старый корневой узел будет недоступен. Затем издатель вернется к сети Pastry и использует ее для маршрутизации своего сообщения публикации на новый корневой узел. Как только это будет сделано, издатель кэширует копию IP-адреса нового корневого узла, чтобы уменьшить использование сети Pastry для будущих передач.
Смотрите также
Рекомендации
- А. Роустрон и П. Друшель (ноябрь 2001 г.). «Кондитерские изделия: масштабируемое, децентрализованное расположение и маршрутизация объектов для крупномасштабных одноранговых систем» (PDF). Международная конференция IFIP / ACM по платформам распределенных систем (промежуточное программное обеспечение), Гейдельберг, Германия: 329–350.
- А. Роустрон; ЯВЛЯЮСЬ. Кермаррек; М. Кастро и П. Друшель (ноябрь 2001 г.). «SCRIBE: Дизайн крупномасштабной инфраструктуры уведомления о событиях» (PDF). NGC2001 UCL Лондон.