Кондитерские изделия (DHT)

Pastry — это оверлейная сеть и сеть маршрутизации для реализации распределенной хеш-таблицы (DHT), аналогичной Chord . Пары ключ -значение хранятся в резервированной одноранговой сети подключенных интернет- хостов. Протокол запускается путем предоставления ему IP-адреса узла, уже находящегося в сети, а затем через таблицу маршрутизации, которая динамически создается и исправляется. Утверждается, что из-за ее избыточного и децентрализованного характера не существует единой точки отказа , и любой отдельный узел может покинуть сеть в любое время без предупреждения и с небольшой или нулевой вероятностью потери данных. Протокол также способен использовать метрику маршрутизации, предоставленную внешней программой, например ping или Traceroute , для определения лучших маршрутов для хранения в своей таблице маршрутизации.

Обзор

Хотя функциональность распределенной хеш-таблицы Pastry практически идентична другим DHT , ее отличает сеть наложения маршрутизации, построенная на основе концепции DHT . Это позволяет Pastry реализовать масштабируемость и отказоустойчивость других сетей, одновременно снижая общую стоимость маршрутизации пакета от одного узла к другому, избегая необходимости лавинной рассылки пакетов. Поскольку метрика маршрутизации предоставляется внешней программой на основе IP-адреса целевого узла, метрику можно легко переключить на кратчайшее количество переходов, минимальную задержку, максимальную пропускную способность или даже общую комбинацию метрик.

Ключевое пространство хеш-таблицы считается циклическим, как пространство ключей в системе Chord , а идентификаторы узлов представляют собой 128-битные целые числа без знака, представляющие положение в циклическом пространстве ключей. Идентификаторы узлов выбираются случайным образом и единообразно, поэтому одноранговые узлы, соседние по идентификатору узла, географически разнообразны. Сеть наложения маршрутизации формируется поверх хеш-таблицы, когда каждый одноранговый узел обнаруживает и обменивается информацией о состоянии, состоящей из списка конечных узлов, списка соседей и таблицы маршрутизации. Список конечных узлов состоит из L /2 ближайших узлов по идентификатору узла в каждом направлении по кругу.

Помимо конечных узлов существует также список окрестностей. Это представляет M ближайших узлов с точки зрения метрики маршрутизации. Хотя он не используется непосредственно в алгоритме маршрутизации, список соседей используется для поддержания принципов локальности в таблице маршрутизации.

Наконец, есть сама таблица маршрутизации. Он содержит одну запись для каждого назначенного ему адресного блока. Для формирования адресных блоков 128-битный ключ делится на цифры, причем каждая цифра имеет длину b бит, что дает систему счисления с основанием 2. ^б. Это разделяет адреса на отдельные уровни с точки зрения клиента: уровень 0 представляет собой общий префикс из нулевой цифры между двумя адресами, уровень 1 — общий префикс из одной цифры и т. д. Таблица маршрутизации содержит адрес ближайшего известного узла для каждой возможной цифры на каждом уровне адреса, за исключением цифры, которая принадлежит самому узлу на этом конкретном уровне. Этот приводит к хранению $2^{b}-1$ контактов на уровень, при этом количество уровней масштабируется как $(\log _{2}{N})/b$ . Ценности $b\approx 4,L\approx 2^{b}$ и $M\approx 2^{b}$ представляют рабочие значения в типичной сети.

Маршрутизация

Пакет может быть направлен на любой адрес в пространстве ключей независимо от того, существует ли узел с этим идентификатором узла или нет. Пакет направляется к своему правильному месту в кольцевом кольце, и узел, идентификатор узла которого находится ближе всего к желаемому месту назначения, получит пакет. Всякий раз, когда партнер получает пакет для маршрутизации или хочет отправить пакет, он сначала проверяет свой набор листьев и направляет его непосредственно к нужному узлу, если он найден. Если это не удается, партнер затем обращается к своей таблице маршрутизации с целью найти адрес узла, который имеет более длинный префикс с адресом назначения, чем сам партнер. Если у узла нет контактов с более длинным префиксом или контакт умер, он выберет узел из своего списка контактов с таким же префиксом длины, чей идентификатор узла численно ближе к пункту назначения, и отправит пакет этому узлу. Поскольку количество правильных цифр в адресе всегда либо увеличивается, либо остается неизменным (а если оно остается неизменным, то расстояние между пакетом и пунктом назначения уменьшается), протокол маршрутизации сходится.

Приложения, созданные на основе Pastry

Сама Pastry определяет, как ключи распределяются между узлами и как можно найти узел, ответственный за хранение ключа. Использование этого в качестве основы для протокола более высокого уровня позволяет Pastry реализовать такие функции, как распределенная файловая система, система подписки и публикации или любая другая система, которую можно свести к хранению значений и их дальнейшему извлечению.

ПРОШЛОЕ

PAST — это распределенная файловая система, расположенная поверх Pastry. Файл сохраняется в системе путем вычисления хеша его имени. Затем Pastry направляет содержимое файла в узел в круговом пространстве ключей, ближайший к хешу, полученному из имени файла. Затем этот узел отправит копии файла на k узлов, ближайших к фактическому ключу, большинство из которых, вероятно, будут конечными узлами этого узла и, следовательно, доступны напрямую. Получение данных осуществляется путем перефразирования имени файла и маршрутизации запроса данных через Pastry в нужное место в пространстве ключей. Запрос может быть выполнен любым из k узлов, имеющих копии данных. Это обеспечивает как избыточность данных, так и распределение нагрузки. Поскольку соседние узлы в пространстве ключей географически разбросаны, вероятность того, что все k из них одновременно перейдут в автономный режим, очень мала. Что еще более важно, поскольку протокол маршрутизации Pastry стремится минимизировать пройденное расстояние, ближайший к машине, отправившей запрос (согласно метрике), скорее всего, будет тот узел, который ответит данными.

ПИСЬЦ

SCRIBE — это децентрализованная система публикации/подписки, которая использует Pastry для управления маршрутами и поиска хостов. Пользователи создают темы, на которые могут подписаться другие пользователи. После создания темы владелец темы может публиковать новые записи в рамках этой темы, которые будут распространяться в дереве многоадресной рассылки всем узлам SCRIBE, подписавшимся на эту тему. Система работает путем вычисления хеша имени темы, объединенного с именем пользователя, которому принадлежит эта тема. Этот хэш затем используется в качестве ключа Pastry, а затем издатель направляет пакеты на узел. ближайший к ключу, используя протокол маршрутизации Pastry для создания корневого узла темы на этом узле. Затем люди подписываются на тему, вычисляя ключ на основе темы и имени издателя, а затем используя Pastry, перенаправляют сообщение о подписке на тему к корневому узлу. Когда корневой узел получает сообщение о подписке от другого узла, он добавляет идентификатор узла в свой список дочерних узлов и начинает действовать как пересылка темы.

Децентрализация достигается за счет того, что все узлы в сети отслеживают сообщения о подписке, проходящие мимо них на пути к корневому узлу темы. Если тема является темой, на которую подписывается текущий узел, он прекратит пересылку пакета к корневому узлу и добавит узел, пытающийся подписаться, в качестве одного из своих дочерних узлов. Таким образом формируется древовидная структура, в которой корневой узел наверху отправляет сообщения первым нескольким узлам-подписчикам, а затем каждый из этих узлов пересылает сообщения своим дочерним узлам и так далее. Поскольку пакеты от случайных узлов сети Pastry, предназначенные для одного и того же узла, часто очень скоро проходят по одному и тому же пути, они в конечном итоге прикрепляются к любой части дерева, ближайшей к ним в сети Pastry. Поскольку каждый переход по маршруту кондитерского изделия представляет собой локально лучший маршрут в соответствии с используемой метрикой маршрутизации, сообщение подписки ищет ближайшую часть дерева и прикрепляется к ней.

Наконец, отказоустойчивость среди членов дерева распределения достигается за счет использования таймаутов и сообщений активности, при этом фактическая передача данных дублируется в качестве сообщений активности для минимизации трафика. Если дочерний узел какое-то время не получает ответа от своего родителя, он направляет новое сообщение о подписке к корневому узлу дерева, повторно подключаясь везде, где он сталкивается с деревом по этой теме. Если родитель не получает известия от ребенка в течение периода ожидания, он удаляет ребенка из своего списка детей. (Если это действие приводит к тому, что его дочерний список становится пустым, родительский узел вообще перестает действовать как пересылающий узел.) Единственной оставшейся точкой отказа является точка корневого узла, и Pastry сам автоматически преодолевает это. Поскольку Pastry дублирует ключи среди нескольких узлов, ближайших к фактическому значению ключа, на корневом узле уже настроены зеркала, которые находятся в режиме ожидания. Если корневой узел отключается от сети, что снова обнаруживается по тайм-ауту, следующий ближайший узел Pastry начнет действовать как корневой узел. Когда создатель темы попытается опубликовать новый материал, старый корневой узел будет недоступен. Затем издатель обратится к сети Pastry и будет использовать ее для маршрутизации сообщения публикации на новый корневой узел. Как только это будет сделано, издатель кэширует копию IP-адреса нового корневого узла, чтобы уменьшить использование сети Pastry для будущих передач.

См. также

Ссылки

А. Роустрон и П. Друшель (ноябрь 2001 г.). «Pastry: масштабируемое, децентрализованное расположение объектов и маршрутизация для крупномасштабных одноранговых систем» (PDF) . Международная конференция IFIP/ACM по платформам распределенных систем (промежуточное программное обеспечение), Гейдельберг, Германия : 329–350.
А. Роустрон; ЯВЛЯЮСЬ. Кермаррек; М. Кастро и П. Друшель (ноябрь 2001 г.). «SCRIBE: Проектирование крупномасштабной инфраструктуры уведомлений о событиях» (PDF) . NGC2001 UCL Лондон .

Внешние ссылки