Аккорд (одноранговый) - Chord (peer-to-peer)
В вычисление, Аккорд это протокол и алгоритм для пиринговый распределенная хеш-таблица. Распределенная хеш-таблица хранит пары ключ-значение назначая ключи разным компьютерам (известные как «узлы»); узел будет хранить значения для всех ключей, за которые он отвечает. Chord определяет, как ключи назначаются узлам, и как узел может обнаружить значение для данного ключа, сначала обнаружив узел, ответственный за этот ключ.
Аккорд - один из четырех оригинальных распределенная хеш-таблица протоколы, а также МОЖЕТ, Гобелен, и Кондитерские изделия. Он был представлен в 2001 году Ион Стойка, Роберт Моррис, Дэвид Каргер, Франс Каашук, и Хари Балакришнан, и был разработан в Массачусетский технологический институт.[1]
Обзор
Узлам и ключам присваивается -кусочек идентификатор с помощью последовательное хеширование. В SHA-1 алгоритм - основа функция хеширования для последовательного хеширования. Согласованное хеширование является неотъемлемой частью надежности и производительности Chord, потому что и ключи, и узлы (фактически, их IP-адреса ) равномерно распределены в одном и том же пространстве идентификаторов с пренебрежимо малой вероятностью коллизии. Таким образом, это также позволяет узлам присоединяться и выходить из сети без прерывания работы. В протоколе термин узел используется для обозначения как самого узла, так и его идентификатора (ID) без двусмысленности. Так это термин ключ.
Используя протокол поиска Chord, узлы и ключи расположены в кружке идентификатора, который имеет не более узлов, начиная от к . ( должен быть достаточно большим, чтобы избежать столкновения.) Некоторые из этих узлов будут отображаться на машины или ключи, в то время как другие (большинство) будут пустыми.
Каждый узел имеет преемник и предшественник. Преемником узла является следующий узел в окружности идентификатора по часовой стрелке. Предшественник - против часовой стрелки. Если существует узел для каждого возможного идентификатора, преемником узла 0 является узел 1, а предшественником узла 0 является узел ; однако обычно в последовательности есть «дыры». Например, преемником узла 153 может быть узел 167 (а узлы с 154 по 166 не существуют); в этом случае предшественником узла 167 будет узел 153.
Понятие преемника также может использоваться для ключей. В узел-преемник ключа это первый узел, идентификатор которого равен или следует в кружке идентификатора, обозначенном . Каждый ключ назначается (хранится в) своему узлу-преемнику, поэтому поиск ключа это запросить .
Поскольку преемник (или предшественник) узла может исчезнуть из сети (из-за сбоя или ухода), каждый узел записывает целый сегмент окружности, примыкающей к нему, т. Е. узлы, предшествующие ему, и узлы, следующие за ним. Этот список приводит к высокой вероятности того, что узел сможет правильно определить местонахождение своего преемника или предшественника, даже если рассматриваемая сеть страдает от высокой частоты отказов.
Детали протокола
Базовый запрос
Основное использование протокола Chord - запрос ключа у клиента (обычно также у узла), то есть для поиска . Основной подход - передать запрос наследнику узла, если он не может найти ключ локально. Это приведет к время запроса, где количество машин в кольце.
Палец стол
Чтобы избежать линейного поиска, описанного выше, Chord реализует более быстрый метод поиска, требуя, чтобы каждый узел сохранял стол для пальцев содержащий до записи, напомним, что - количество бит в хеш-ключе. В вход узла будет содержать . Первая запись в таблице finger фактически является непосредственным преемником узла (и поэтому дополнительное поле-преемник не требуется). Каждый раз, когда узел хочет найти ключ , он передаст запрос ближайшему преемнику или предшественнику (в зависимости от таблицы пальцев) в его таблице пальцев ("самый большой" в круге, ID которого меньше, чем ), пока узел не узнает, что ключ хранится в его непосредственном преемнике.
С такой таблицей пальцев количество узлов, с которыми необходимо связаться, чтобы найти преемника в N-узловая сеть . (См. Доказательство ниже.)
Присоединение к узлу
Каждый раз, когда присоединяется новый узел, следует поддерживать три инварианта (первые два обеспечивают корректность, а последний продолжает быстро запрашивать):
- Преемник каждого узла правильно указывает на своего непосредственного преемника.
- Каждый ключ хранится в .
- Таблица пальцев каждого узла должна быть правильной.
Чтобы удовлетворить этим инвариантам, a предшественник поле поддерживается для каждого узла. Поскольку преемником является первая запись в таблице finger, нам больше не нужно поддерживать это поле отдельно. Следующие задачи должны быть выполнены для вновь присоединенного узла :
- Инициализировать узел (предшественник и таблица пальцев).
- Сообщите другим узлам об обновлении своих предшественников и таблиц пальцев.
- Новый узел принимает свои ответственные ключи от своего преемника.
Предшественник можно легко получить от предшественника (в предыдущем круге). Что касается его таблицы пальцев, существуют различные методы инициализации. Самый простой - выполнить запросы на поиск преемников для всех записи, в результате чего время инициализации. Лучший метод - проверить, запись в таблице пальцев все еще верна для Вход. Это приведет к . Наилучший метод - инициализировать таблицу пальцев из ее ближайших соседей и внести некоторые обновления, то есть .
Стабилизация
Чтобы обеспечить правильный поиск, все указатели-преемники должны быть актуальными. Следовательно, протокол стабилизации периодически выполняется в фоновом режиме, который обновляет таблицы пальцев и указатели-преемники.
Протокол стабилизации работает следующим образом:
- Stabilize (): n запрашивает у своего преемника своего предшественника p и решает, должен ли p быть преемником n (это тот случай, если p недавно присоединился к системе).
- Notify (): уведомляет наследника n о своем существовании, поэтому он может изменить своего предшественника на n
- Fix_fingers (): обновляет таблицы пальцев
Возможное использование
- Совместное зеркалирование: A Балансировка нагрузки механизм размещения информации в локальной сети для компьютеров вне локальной сети. Эта схема могла бы позволить разработчикам балансировать нагрузку между множеством компьютеров вместо центрального сервера, чтобы гарантировать доступность их продукта.
- Хранилище с разделением по времени: в сети, как только компьютер подключается к сети, его доступные данные распределяются по сети для извлечения, когда этот компьютер отключается от сети. Данные с других компьютеров отправляются на рассматриваемый компьютер для автономного извлечения, когда они больше не подключены к сети. В основном для узлов без возможности постоянного подключения к сети.
- Распределенные индексы: поиск файлов по сети в базе данных с возможностью поиска. например Клиенты передачи файлов P2P.
- Крупномасштабные комбинаторные поиски: ключи - это возможные решения проблемы, и каждый ключ отображается на узел или компьютер, который отвечает за их оценку как решение или нет. например Взлом кода
- Также используется в беспроводных сенсорных сетях для обеспечения надежности[2]
Контрольные эскизы
С большой долей вероятности, Аккорд контактирует узлов, чтобы найти преемника в -узловая сеть.
Предположим, узел желает найти преемника ключа . Позволять быть предшественником . Мы хотим найти верхнюю границу количества шагов, необходимых для маршрутизации сообщения от к . Узел проверит свою таблицу пальцев и направит запрос ближайшему предшественнику что у него есть. Назовите этот узел . Если это вход в стол для пальцев, затем оба и находятся на расстоянии между и из по кружку идентификатора. Следовательно, расстояние между и по этому кругу самое большее . Таким образом, расстояние от к меньше, чем расстояние от к : новое расстояние до составляет не более половины начального расстояния.
Этот процесс уменьшения вдвое оставшегося расстояния повторяется, поэтому после шагов, оставшееся расстояние до самое большее ; в частности, после шагов, оставшееся расстояние не более . Поскольку узлы случайным образом распределены равномерно по окружности идентификатора, ожидаемое количество узлов, попадающих в интервал этой длины, равно 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 - инструментарий для моделирования распределенных приложений -
Рекомендации
- ^ Стойка, И.; Morris, R .; Kaashoek, M. F .; Балакришнан, Х. (2001). «Chord: масштабируемая одноранговая служба поиска для интернет-приложений» (PDF). Обзор компьютерных коммуникаций ACM SIGCOMM. 31 (4): 149. Дои:10.1145/964723.383071.
- ^ Лаббай, Пир Мира (осень 2016 г.). "T2WSN: ТИТИВИРОВАННАЯ НАДЕЖНОСТЬ ДВУХСТОРОННИХ АККОРДОВ, ПОДДЕРЖИВАЮЩАЯ НАДЕЖНОСТЬ И ДОСТАВКА ДЛЯ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ" (PDF). Журнал теоретических и прикладных информационных технологий. 91: 168–176.
внешняя ссылка
- Аккордовый проект (перенаправление с: http://pdos.lcs.mit.edu/chord/ )
- Open Chord - реализация Java с открытым исходным кодом
- Chordless - еще одна реализация Java с открытым исходным кодом
- jDHTUQ - реализация Java с открытым исходным кодом. API для обобщения реализации одноранговых систем DHT. Содержит графический интерфейс в структуре данных режима