Аккорд (одноранговая сеть)

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

Chord — один из четырех оригинальных протоколов распределенных хеш-таблиц , наряду с CAN , Tapestry и Pastry . Он был представлен в 2001 году Ионом Стойкой , Робертом Моррисом , Дэвидом Каргером , Франсом Каашуком и Хари Балакришнаном и был разработан в Массачусетском технологическом институте . ^[1] Документ «Аккорд» 2001 года ^[1] выиграл награду ACM SIGCOMM Test of Time в 2011 году. ^[2]

Последующие исследования Памелы Заве показали, что оригинальный алгоритм Chord (как указано в документе SIGCOMM 2001 г.) ^[1] Технический отчет 2001 г., ^[3] документ PODC 2002 года, ^[4] и документ TON 2003 года ^[5]) может неправильно заказать кольцо, изготовить несколько колец и сломать кольцо. ^[6]

Обзор

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

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

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

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

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

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

Основной запрос

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

Пальчиковый стол

Чтобы избежать описанного выше линейного поиска, Chord реализует более быстрый метод поиска, требуя, чтобы каждый узел хранил таблицу пальцев , содержащую до $m$ записи, напомним, что $m$ — количество битов в хеш-ключе. $i^{th}$ вход узла $n$ будет содержать $successor((n+2^{i-1})\,{\bmod {\,}}2^{m})$ . Первая запись таблицы пальцев фактически является непосредственным преемником узла (и, следовательно, дополнительное поле преемника не требуется). Каждый раз, когда узел хочет найти ключ $k$ , он передаст запрос ближайшему преемнику или предшественнику (в зависимости от таблицы пальцев) $k$ в своей таблице пальцев («самая большая» на круге, идентификатор которой меньше, чем $k$ ), пока узел не обнаружит, что ключ хранится у его непосредственного преемника.

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

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

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

Преемник каждого узла правильно указывает на своего непосредственного преемника.
Каждый ключ хранится в $successor(k)$ .
Таблица пальцев каждого узла должна быть правильной.

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

Инициализировать узел $n$ (предшественник и таблица пальцев).
Уведомите другие узлы об обновлении своих предшественников и таблиц пальцев.
Новый узел перенимает ответственные ключи от своего преемника.

Предшественник $n$ можно легко получить от предшественника $successor(n)$ (в предыдущем круге). Что касается таблицы пальцев, существуют различные методы инициализации. Самый простой — выполнить запросы на поиск преемников для всех $m$ записи, в результате чего $O(M\log N)$ время инициализации. Лучший способ — проверить, $i^{th}$ запись в таблице пальцев по-прежнему верна для $(i+1)^{th}$ вход. Это приведет к $O(\log ^{2}N)$ . Лучший способ — инициализировать таблицу пальцев на основе ее непосредственных соседей и внести некоторые обновления. $O(\log N)$ .

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

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

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

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

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

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

Доказательные эскизы

С большой вероятностью, контакты Корда $O(\log N)$ узлы, чтобы найти преемника в $N$ -узловая сеть.

Предположим, узел $n$ желает найти преемника ключа $k$ . Позволять $p$ быть предшественником $k$ . Мы хотим найти верхнюю границу количества шагов, необходимых для маршрутизации сообщения от $n$ к $p$ . Узел $n$ проверит свою таблицу пальцев и направит запрос ближайшему предшественнику $k$ что оно имеет. Позвоните в этот узел $f$ . Если $f$ это $i^{th}$ вход в $n$ таблица пальцев, затем оба $f$ и $p$ находятся на расстоянии между $2^{i-1}$ и $2^{i}$ от $n$ вдоль идентификационного круга. Следовательно, расстояние между $f$ и $p$ по этому кругу не более $2^{i-1}$ . Таким образом, расстояние от $f$ к $p$ меньше, чем расстояние от $n$ к $f$ : новое расстояние до $p$ составляет не более половины первоначального расстояния.

Этот процесс сокращения оставшегося расстояния вдвое повторяется, поэтому после $t$ шагов, расстояние, оставшееся до $p$ самое большее $2^{m}/2^{t}$ ; в частности, после $\log N$ шагов, оставшееся расстояние не более $2^{m}/N$ . Поскольку узлы распределены равномерно и случайным образом вдоль круга идентификатора, ожидаемое количество узлов, попадающих в интервал этой длины, равно 1, и с высокой вероятностью их будет меньше, чем $\log N$ такие узлы. Поскольку сообщение всегда продвигается хотя бы на один узел, оно занимает не более $\log N$ шаги, необходимые сообщению для прохождения оставшегося расстояния. Таким образом, общее ожидаемое время маршрутизации равно $O(\log N)$ .

Если Корд отслеживает $r=O(\log N)$ предшественники/преемники, то с высокой вероятностью, если каждый узел имеет вероятность сбоя 1/4, find_successor (см. ниже) и find_predecessor (см. ниже) вернут правильные узлы

Проще говоря, вероятность того, что все $r$ сбой узлов это $\left({{1} \over {4}}\right)^{r}=O\left({{1} \over {N}}\right)$ , что является малой вероятностью; поэтому с высокой вероятностью хотя бы один из них жив и узел будет иметь правильный указатель.

Псевдокод

Определения псевдокода

палец [к]: первый узел, который удался $(n+2^{k-1}){\mbox{ mod }}2^{m},1\leq k\leq m$
преемник: следующий узел от рассматриваемого узла на кольце идентификатора
предшественник: предыдущий узел из рассматриваемого узла на кольце идентификатора

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

// ask node n to find the successor of id
n.find_successor(id)
    // Yes, that should be a closing square bracket to match the opening parenthesis.
    // It is a half closed interval.
    if id ∈ (n, successor] then
        return successor
    else
        // forward the query around the circle
        n0 := closest_preceding_node(id)
        return n0.find_successor(id)

// search the local table for the highest predecessor of id
n.closest_preceding_node(id)
    for i = m downto 1 do
        if (finger[i] ∈ (n, id)) then
            return finger[i]
    return n

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

// create a new Chord ring.
n.create()
    predecessor := nil
    successor := n

// join a Chord ring containing node n'.
n.join(n')
    predecessor := nil
    successor := n'.find_successor(n)

// called periodically. n asks the successor
// about its predecessor, verifies if n's immediate
// successor is consistent, and tells the successor about n
n.stabilize()
    x = successor.predecessor
    if x ∈ (n, successor) then
        successor := x
    successor.notify(n)

// n' thinks it might be our predecessor.
n.notify(n')
    if predecessor is nil or n'∈(predecessor, n) then
        predecessor := n'

// called periodically. refreshes finger table entries.
// next stores the index of the finger to fix
n.fix_fingers()
    next := next + 1
    if next > m then
        next := 1
    finger[next] := find_successor(n+2^next-1);

// called periodically. checks whether predecessor has failed.
n.check_predecessor()
    if predecessor has failed then
        predecessor := nil

См. также

Кадемлия
Шнуры
OverSim - среда моделирования наложений
SimGrid – набор инструментов для моделирования распределенных приложений.

Ссылки

^ Перейти обратно: ^а ^б ^с Стойка, И .; Моррис, Р.; Каашук, МФ; Балакришнан, Х. (2001). «Chord: масштабируемая одноранговая служба поиска интернет-приложений» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 31 (4): 149. дои : 10.1145/964723.383071 .
^ «Награда ACM SIGCOMM Test of Time Paper» . Проверено 16 января 2022 г.
^ Стойка, И .; Моррис, Р.; Либен-Ноуэлл, Д.; Каргер, Д.; Каашук, МФ; Дабек, Ф.; Балакришнан, Х. (2001). Chord: масштабируемая одноранговая служба поиска интернет-приложений (PDF) (технический отчет). MIT LCS. Массачусетский технологический институт. 819. Архивировано из оригинала (PDF) 22 июля 2012 года.
^ Либен-Ноуэлл, Дэвид; Балакришнан, Хари; Каргер, Дэвид (июль 2002 г.). Анализ эволюции одноранговых систем (PDF) . PODC '02: Материалы двадцать первого ежегодного симпозиума по принципам распределенных вычислений. стр. 233–242. дои : 10.1145/571825.571863 .
^ Стойка, И .; Моррис, Р.; Либен-Ноуэлл, Д.; Каргер, Д.; Каашук, МФ; Дабек, Ф.; Балакришнан, Х. (25 февраля 2003 г.). «Chord: масштабируемый протокол однорангового поиска для интернет-приложений». Транзакции IEEE/ACM в сети . 11 (1): 17–32. дои : 10.1109/TNET.2002.808407 . S2CID 221276912 .
^ Заве, Памела (2012). «Использование упрощенного моделирования для понимания аккорда» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 42 (2): 49–57. дои : 10.1145/2185376.2185383 . S2CID 11727788 .
^ Лаббай, Пер Мира (осень 2016 г.). «T2WSN: НАКЛАДКА С ДВУМЯ ХОРДАМИ, ПОВЫШАЮЩАЯ НАДЕЖНОСТЬ И СООТНОШЕНИЕ ПЕРЕДАЧИ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ» (PDF) . Журнал теоретических и прикладных информационных технологий . 91 : 168–176.

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

[StoicaEtAl2001-1] Перейти обратно: ^а ^б ^с Стойка, И .; Моррис, Р.; Каашук, МФ; Балакришнан, Х. (2001). «Chord: масштабируемая одноранговая служба поиска интернет-приложений» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 31 (4): 149. дои : 10.1145/964723.383071 .

[2] «Награда ACM SIGCOMM Test of Time Paper» . Проверено 16 января 2022 г.

[StoicaEtAl2001TechReport-3] Стойка, И .; Моррис, Р.; Либен-Ноуэлл, Д.; Каргер, Д.; Каашук, МФ; Дабек, Ф.; Балакришнан, Х. (2001). Chord: масштабируемая одноранговая служба поиска интернет-приложений (PDF) (технический отчет). MIT LCS. Массачусетский технологический институт. 819. Архивировано из оригинала (PDF) 22 июля 2012 года.

[PODC2002-4] Либен-Ноуэлл, Дэвид; Балакришнан, Хари; Каргер, Дэвид (июль 2002 г.). Анализ эволюции одноранговых систем (PDF) . PODC '02: Материалы двадцать первого ежегодного симпозиума по принципам распределенных вычислений. стр. 233–242. дои : 10.1145/571825.571863 .

[ChordTON2003-5] Стойка, И .; Моррис, Р.; Либен-Ноуэлл, Д.; Каргер, Д.; Каашук, МФ; Дабек, Ф.; Балакришнан, Х. (25 февраля 2003 г.). «Chord: масштабируемый протокол однорангового поиска для интернет-приложений». Транзакции IEEE/ACM в сети . 11 (1): 17–32. дои : 10.1109/TNET.2002.808407 . S2CID 221276912 .

[Zave2012-6] Заве, Памела (2012). «Использование упрощенного моделирования для понимания аккорда» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 42 (2): 49–57. дои : 10.1145/2185376.2185383 . S2CID 11727788 .

[7] Лаббай, Пер Мира (осень 2016 г.). «T2WSN: НАКЛАДКА С ДВУМЯ ХОРДАМИ, ПОВЫШАЮЩАЯ НАДЕЖНОСТЬ И СООТНОШЕНИЕ ПЕРЕДАЧИ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ» (PDF) . Журнал теоретических и прикладных информационных технологий . 91 : 168–176.

[1]

[2]

[3]

[4]

[5]

[6]

[7]