Пропустить график

Графы пропуска — это своего рода распределенная структура данных, основанная на списках пропуска . Их изобрели в 2003 году Джеймс Аспнес и Гаури Шах. Почти идентичная структура данных под названием SkipNet была независимо изобретена Николасом Харви, Майклом Джонсом, Стефаном Саройу, Марвином Теймером и Алеком Вулманом также в 2003 году.

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

Описание

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

Детали реализации

Как и в списках пропуска , узлы располагаются в порядке возрастания на нескольких уровнях; каждый узел на уровне i содержится на уровне i +1 с некоторой вероятностью p (регулируемый параметр). Уровень 0 состоит из одного двусвязного списка, содержащего все узлы набора. На более высоких уровнях списки становятся все более разреженными, пока список не будет состоять всего из одного узла. Графы пропуска отличаются от списков пропуска тем, что каждый уровень i ≥1 будет содержать несколько списков; членство ключа x в списке определяется вектором принадлежности ⁠ $m(x)$⁠ . Вектор принадлежности определяется как бесконечное случайное слово в фиксированном алфавите, каждый список в графе пропуска идентифицируется конечным словом w из того же алфавита, если это слово является префиксом ⁠ $m(x)$⁠ тогда узел x является членом списка.

Операции

Графики пропуска поддерживают основные операции поиска , вставки и удаления . Пропуск графиков также будет поддерживать более сложную операцию поиска диапазона .

Поиск

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

Каждый узел в списке имеет следующие поля:

key

Значение узла.

neighbor[R/L][level]

Массив, содержащий указатели на правого и левого соседа узла, дважды связанного на уровне i.

search(searchOp, startNode, searchKey, level)
    if (v.key = searchKey) then
        send(foundOp, v) to startNode
    if (v.key < searchKey) then
        while level ≥ 0
            if (v.neighbor[R][level].key ≤ searchKey) then
                send(searchOp, startNode, searchKey, level) to v.neighbor[R][level]
                break
            else
                level = level - 1
    else
        while level ≥ 0
            if ((v.neighbor[L][level]).key ≥ searchKey) then
                send(searchOp, startNode, searchKey, level) to v.neighbor[L][level]
                break
            else
                level = level - 1
    if (level < 0) then
        send(notFoundOp, v) to startNode

Анализ, проведенный Уильямом Пью, показывает, что в среднем список пропуска и, как следствие, граф пропуска содержат $O\left({\frac {\log n}{\log(1/p)}}\right)$ уровни для фиксированного значения p . Учитывая, что максимум ${\frac {1}{1-p}}$ узлы ищутся в среднем за уровень, общее ожидаемое количество отправленных сообщений равно $O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)$ и ожидаемое время поиска равно $O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)$. Следовательно, для фиксированного значения p ожидается, что операция поиска займет O (log n ) время с использованием сообщений O (log n ) .

Вставлять

Вставка выполняется в два этапа и требует, чтобы новый узел u знал некоторый вводящий узел v ; вводящим узлом может быть любой другой узел, находящийся в данный момент в графе пропуска. На первом этапе новый узел u использует вводящий узел v для поиска своего собственного ключа; Ожидается, что этот поиск завершится неудачей и вернет узел s с наибольшим ключом, меньшим, чем u . На втором этапе u вставляет себя на каждый уровень, пока не станет единственным элементом в списке на верхнем уровне. Вставка на каждом уровне осуществляется с помощью стандартных операций с двусвязным списком; следующий указатель левого соседа изменяется, чтобы указывать на новый узел, а предыдущий указатель правого соседа изменяется, чтобы указывать на узел.

insert()
search for s
L = 0
while true
    insert u into level L from s
    Scan through level L to find s' such which has membership vector matching membership vector of u for first L+1 characters
    if no s' exists
        exit
    else
        s = s'
        L = L + 1

Подобно поиску, операция вставки занимает ожидаемое количество сообщений O (log n ) и время O (log n ). При фиксированном значении р; Ожидается, что операция поиска на этапе 1 займет O (log n ) времени и сообщений. На этапе 2 на каждом уровне L ≥ 0 u взаимодействует со средним числом 1/ p других узлов, чтобы найти s ', для этого потребуется время O (1/ p ) и сообщения, ведущие к времени O (1) и сообщениям для каждого шага в фаза 2.

Удалить

Узлы могут быть удалены параллельно на каждом уровне за O (1) раз и O (log n ) сообщений. Когда узел желает покинуть граф, он должен отправить сообщения своим непосредственным соседям, чтобы переставить их указатели следующего и предыдущего узла.

delete()
for L = 1 to max level, in parallel
    delete u from each level.
delete u from level 0

График пропуска содержит среднее значение O (log n ) уровней; на каждом уровне вы должны отправить 2 сообщения для завершения операции удаления в двусвязном списке. Поскольку операции на каждом уровне могут выполняться параллельно, операция удаления может быть завершена с использованием времени O (1) и ожидаемых сообщений O (log n ).

Отказоустойчивость

В графах пропуска отказоустойчивость описывает количество узлов, которые могут быть отключены от графа пропуска из-за сбоев других узлов. Были рассмотрены две модели отказа; случайные сбои и состязательные сбои. В модели случайного отказа любой узел с некоторой вероятностью может выйти из строя независимо от любого другого узла. Состязательная модель предполагает, что отказы узлов планируются таким образом, что на каждом этапе достигается наихудший возможный отказ, известна вся структура графа пропусков и выбираются отказы для максимального увеличения отключения узла. Недостатком пропуска графов является отсутствие механизма восстановления ; в настоящее время единственный способ удалить и восстановить граф пропуска — это построить новый граф пропуска с уцелевшими узлами.

Случайный сбой

Графики пропуска обладают высокой устойчивостью к случайным сбоям. Благодаря сохранению информации о состоянии соседей и использованию резервных каналов во избежание отказа соседей нормальная работа может продолжаться даже при большом количестве сбоев узлов. Пока количество вышедших из строя узлов меньше $O\left({\frac {1}{\log n}}\right)$ график пропуска может продолжать нормально функционировать. Моделирование, выполненное Джеймсом Аспнесом, показывает, что граф пропусков с 131072 узлами способен выдерживать до 60% сбоев своих узлов до того, как выжившие узлы будут изолированы. Хотя другие распределенные структуры данных могут достичь более высокого уровня отказоустойчивости, они, как правило, гораздо более сложны.

Состязательный провал

Состязательный отказ сложно смоделировать в большой сети, поскольку становится трудно найти модели сбоя в худшем случае. Теоретический анализ показывает, что устойчивость зависит от коэффициента расширения вершин графа, определяемого следующим образом. Для набора узлов A в графе G коэффициент расширения равен количеству узлов не в A, но смежных с узлом в A, делённому на количество узлов в A. Если графы пропуска имеют достаточно большой коэффициент расширения $\Omega \left({\frac {1}{\log n}}\right)$ тогда самое большее ⁠ $O(f\log n)$⁠ узлы могут быть разделены, даже если конкретно запланировано до f отказов.