Аккорд (одноранговый) - Chord (peer-to-peer)

В вычисление, Аккорд это протокол и алгоритм для пиринговый распределенная хеш-таблица. Распределенная хеш-таблица хранит пары ключ-значение назначая ключи разным компьютерам (известные как «узлы»); узел будет хранить значения для всех ключей, за которые он отвечает. Chord определяет, как ключи назначаются узлам, и как узел может обнаружить значение для данного ключа, сначала обнаружив узел, ответственный за этот ключ.

Аккорд - один из четырех оригинальных распределенная хеш-таблица протоколы, а также МОЖЕТ, Гобелен, и Кондитерские изделия. Он был представлен в 2001 году Ион Стойка, Роберт Моррис, Дэвид Каргер, Франс Каашук, и Хари Балакришнан, и был разработан в Массачусетский технологический институт.[1]

Обзор

Аккорд project.svg

Узлам и ключам присваивается -кусочек идентификатор с помощью последовательное хеширование. В SHA-1 алгоритм - основа функция хеширования для последовательного хеширования. Согласованное хеширование является неотъемлемой частью надежности и производительности Chord, потому что и ключи, и узлы (фактически, их IP-адреса ) равномерно распределены в одном и том же пространстве идентификаторов с пренебрежимо малой вероятностью коллизии. Таким образом, это также позволяет узлам присоединяться и выходить из сети без прерывания работы. В протоколе термин узел используется для обозначения как самого узла, так и его идентификатора (ID) без двусмысленности. Так это термин ключ.

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

Каждый узел имеет преемник и предшественник. Преемником узла является следующий узел в окружности идентификатора по часовой стрелке. Предшественник - против часовой стрелки. Если существует узел для каждого возможного идентификатора, преемником узла 0 является узел 1, а предшественником узла 0 является узел ; однако обычно в последовательности есть «дыры». Например, преемником узла 153 может быть узел 167 (а узлы с 154 по 166 не существуют); в этом случае предшественником узла 167 будет узел 153.

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

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

Детали протокола

В сети Chord с 16 узлами узлы расположены по кругу. Каждый узел связан с другими узлами на расстоянии 1, 2, 4 и 8 от них.
Сеть Chord с 16 узлами. Выделены «пальцы» для одного из узлов.

Базовый запрос

Основное использование протокола Chord - запрос ключа у клиента (обычно также у узла), то есть для поиска . Основной подход - передать запрос наследнику узла, если он не может найти ключ локально. Это приведет к время запроса, где количество машин в кольце.

Палец стол

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

С такой таблицей пальцев количество узлов, с которыми необходимо связаться, чтобы найти преемника в N-узловая сеть . (См. Доказательство ниже.)

Присоединение к узлу

Каждый раз, когда присоединяется новый узел, следует поддерживать три инварианта (первые два обеспечивают корректность, а последний продолжает быстро запрашивать):

  1. Преемник каждого узла правильно указывает на своего непосредственного преемника.
  2. Каждый ключ хранится в .
  3. Таблица пальцев каждого узла должна быть правильной.

Чтобы удовлетворить этим инвариантам, a предшественник поле поддерживается для каждого узла. Поскольку преемником является первая запись в таблице finger, нам больше не нужно поддерживать это поле отдельно. Следующие задачи должны быть выполнены для вновь присоединенного узла :

  1. Инициализировать узел (предшественник и таблица пальцев).
  2. Сообщите другим узлам об обновлении своих предшественников и таблиц пальцев.
  3. Новый узел принимает свои ответственные ключи от своего преемника.

Предшественник можно легко получить от предшественника (в предыдущем круге). Что касается его таблицы пальцев, существуют различные методы инициализации. Самый простой - выполнить запросы на поиск преемников для всех записи, в результате чего время инициализации. Лучший метод - проверить, запись в таблице пальцев все еще верна для Вход. Это приведет к . Наилучший метод - инициализировать таблицу пальцев из ее ближайших соседей и внести некоторые обновления, то есть .

Стабилизация

Чтобы обеспечить правильный поиск, все указатели-преемники должны быть актуальными. Следовательно, протокол стабилизации периодически выполняется в фоновом режиме, который обновляет таблицы пальцев и указатели-преемники.

Протокол стабилизации работает следующим образом:

  • Stabilize (): n запрашивает у своего преемника своего предшественника p и решает, должен ли p быть преемником n (это тот случай, если p недавно присоединился к системе).
  • Notify (): уведомляет наследника n о своем существовании, поэтому он может изменить своего предшественника на n
  • Fix_fingers (): обновляет таблицы пальцев

Возможное использование

  • Совместное зеркалирование: A Балансировка нагрузки механизм размещения информации в локальной сети для компьютеров вне локальной сети. Эта схема могла бы позволить разработчикам балансировать нагрузку между множеством компьютеров вместо центрального сервера, чтобы гарантировать доступность их продукта.
  • Хранилище с разделением по времени: в сети, как только компьютер подключается к сети, его доступные данные распределяются по сети для извлечения, когда этот компьютер отключается от сети. Данные с других компьютеров отправляются на рассматриваемый компьютер для автономного извлечения, когда они больше не подключены к сети. В основном для узлов без возможности постоянного подключения к сети.
  • Распределенные индексы: поиск файлов по сети в базе данных с возможностью поиска. например Клиенты передачи файлов P2P.
  • Крупномасштабные комбинаторные поиски: ключи - это возможные решения проблемы, и каждый ключ отображается на узел или компьютер, который отвечает за их оценку как решение или нет. например Взлом кода
  • Также используется в беспроводных сенсорных сетях для обеспечения надежности[2]

Контрольные эскизы

Если два узла находятся на расстоянии 11 друг от друга по кольцу (то есть между ними 10 узлов), для отправки сообщения от одного к другому требуется три перехода. Первый переход охватывает расстояние в 8 единиц, второй - 2 единицы и последний переход - 1 единицу.
Путь маршрутизации между узлами A и B. Каждый переход сокращает оставшееся расстояние вдвое (или лучше).

С большой долей вероятности, Аккорд контактирует узлов, чтобы найти преемника в -узловая сеть.

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

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

Если Аккорд отслеживает предшественники / преемники, то с высокой вероятностью, если каждый узел имеет вероятность сбоя 1/4, find_successor (см. ниже) и find_predecessor (см. ниже) вернут правильные узлы

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

Псевдокод

Определения псевдокода
палец [k]
первый успешный узел
преемник
следующий узел из рассматриваемого узла в кольце идентификаторов
предшественник
предыдущий узел из рассматриваемого узла в кольце идентификаторов

Псевдокод для поиска преемник узел идентификатора приведен ниже:

// просим узел n найти преемника idn.find_successor (id) // Да, это должна быть закрывающая квадратная скобка, чтобы соответствовать открывающей скобке. // Половина закрытого интервала. если id ∈ (n, преемник] тогда        возвращаться преемник еще        // перенаправляем запрос по кругу n0: = closest_preceding_node (id) возвращаться n0.find_successor (id) // поиск в локальной таблице самого высокого предшественника idn.closest_preceding_node (id) за я = м вниз до 1 делать        если (палец [i] ∈ (n, id)) тогда            возвратный палец [i] возвращаться п

Псевдокод для стабилизации хордового кольца / окружности после присоединения и удаления узлов выглядит следующим образом:

// создаем новое кольцо Chord. n.create () предшественник: = nil successor: = n // присоединяемся к кольцу Chord, содержащему узел n'.n.join (n ') предшественник: = nil successor: = n'.find_successor (n) // вызывается периодически. n спрашивает наследника // о его предшественнике, проверяет, является ли непосредственный // наследник n последовательным, и сообщает наследнику о nn.stabilize () x = successor.predecessor если x ∈ (n, преемник) тогда        successor: = x successor.notify (n) // n 'думает, что это может быть наш предшественник. n.notify (n') если предшественник равен нулю или же n'∈ (предшественник, n) тогда        предшественник: = n '// вызывается периодически. обновляет записи в таблице пальцев. // далее сохраняет указатель пальца в fixn.fix_fingers () next: = next + 1 если следующий> м тогда        следующий: = 1 finger [следующий]: = find_successor (n +);// вызывается периодически. проверяет, не сработал ли предшественник. n.check_predecessor () если предшественник потерпел неудачу тогда        предшественник: = ноль

Смотрите также

  • Кадемлия
  • Koorde
  • OverSim - фреймворк моделирования наложения
  • SimGrid - инструментарий для моделирования распределенных приложений -

Рекомендации

  1. ^ Стойка, И.; Morris, R .; Kaashoek, M. F .; Балакришнан, Х. (2001). «Chord: масштабируемая одноранговая служба поиска для интернет-приложений» (PDF). Обзор компьютерных коммуникаций ACM SIGCOMM. 31 (4): 149. Дои:10.1145/964723.383071.
  2. ^ Лаббай, Пир Мира (осень 2016 г.). "T2WSN: ТИТИВИРОВАННАЯ НАДЕЖНОСТЬ ДВУХСТОРОННИХ АККОРДОВ, ПОДДЕРЖИВАЮЩАЯ НАДЕЖНОСТЬ И ДОСТАВКА ДЛЯ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ" (PDF). Журнал теоретических и прикладных информационных технологий. 91: 168–176.

внешняя ссылка