WikiDer > Распределенная хеш-таблица

Distributed hash table

А распределенная хеш-таблица (DHT) это распределенная система который предоставляет службу поиска, похожую на хеш-таблица: пары ключ-значение хранятся в DHT, и все участвующие узел может эффективно извлекать значение, связанное с данным ключ. Основным преимуществом DHT является то, что узлы можно добавлять или удалять с минимальными усилиями по перераспределению ключей. Ключи уникальные идентификаторы, которые соответствуют конкретным значения, которые, в свою очередь, могут быть любыми, от адресов до документы, произвольным данные.[1] Ответственность за поддержание сопоставления ключей со значениями распределяется между узлами таким образом, что изменение набора участников вызывает минимальные нарушения. Это позволяет DHT шкала к чрезвычайно большому количеству узлов и для обработки постоянных приходов, уходов и отказов узлов.

DHT образуют инфраструктуру, которую можно использовать для создания более сложных сервисов, таких как Anycast, кооператив веб-кеширование, распределенные файловые системы, услуги доменного имени, мгновенное сообщение, многоадресная передача, а также одноранговый обмен файлами и распространение контента системы. Известные распределенные сети, использующие DHT, включают: BitTorrentраспределенный трекер, Сеть распространения контента Coral, то Кад сеть, то Штормовой ботнет, то Мессенджер Tox, Freenet, то YaCy поисковая система, а Межпланетная файловая система.

Распределенные хеш-таблицы

История

Первоначально исследования DHT были частично мотивированы пиринговый (P2P) системы, такие как Freenet, Гнутелла, BitTorrent и Napster, который использовал ресурсы, распределенные через Интернет, для создания единого полезного приложения. В частности, они воспользовались повышенным пропускная способность и жесткий диск способность предоставлять услуги обмена файлами.[2]

Эти системы различались тем, как они находили данные, предлагаемые их коллегами. Napster, первая крупномасштабная система доставки контента P2P, требовала центрального сервера индекса: каждый узел после присоединения отправлял список локально хранимых файлов на сервер, который выполнял поиск и направлял запросы на узлы, которые содержали полученные результаты. Этот центральный компонент сделал систему уязвимой для атак и судебных исков.

Gnutella и аналогичные сети переехали в наводнение запросов модель - по сути, каждый поиск приведет к тому, что сообщение будет транслироваться на все остальные машины в сети. Избегая единая точка отказа, этот метод был значительно менее эффективен, чем Napster. Более поздние версии клиентов Gnutella переехали на динамический запрос модель, которая значительно повысила эффективность.[3]

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

Распределенные хэш-таблицы используют более структурированную маршрутизацию на основе ключей, чтобы добиться как децентрализации Freenet и Gnutella, так и эффективности и гарантированных результатов Napster. Одним из недостатков является то, что, как и Freenet, DHT поддерживают только поиск с точным соответствием, а не поиск по ключевым словам, хотя Freenet алгоритм маршрутизации может быть обобщен на любой тип ключа, где может быть определена операция близости.[5]

В 2001 году четыре системы:МОЖЕТ,[6] Аккорд,[7] Кондитерские изделия, и Гобелен- разожгли DHT как популярную тему для исследований. Проект под названием Infrastructure for Resilient Internet Systems (Iris) был профинансирован грантом в размере 12 миллионов долларов США. Национальный фонд науки в 2002.[8]Включены исследователи Сильвия Ратнасами, Ион Стойка, Хари Балакришнан и Скотт Шенкер.[9]За пределами академических кругов технология DHT была принята как компонент BitTorrent и в Сеть распространения контента Coral.

Характеристики

DHT обычно подчеркивают следующие свойства:

  • Автономия и децентрализация: узлы вместе образуют систему без какой-либо центральной координации.
  • Отказоустойчивость: система должна быть надежной (в некотором смысле) даже с узлами, которые постоянно подключаются, уходят и выходят из строя.
  • Масштабируемость: система должна эффективно работать даже с тысячами или миллионами узлов.

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

Некоторые проекты DHT стремятся быть безопасный против злонамеренных участников[10] и позволить участникам остаться анонимный, хотя это встречается реже, чем во многих других одноранговых сетях (особенно обмен файлами) системы; видеть анонимный P2P.

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

Структура

Структура DHT может быть разбита на несколько основных компонентов.[11][12] Фундамент - это абстрактный пространство клавиш, например набор 160-битных струны. Пространство клавиш разделение Схема разделяет владение этим пространством ключей между участвующими узлами. An оверлейная сеть затем соединяет узлы, позволяя им найти владельца любого заданного ключа в пространстве ключей.

После того, как эти компоненты будут установлены, типичное использование DHT для хранения и извлечения может происходить следующим образом. Предположим, что пространство ключей - это набор 160-битных строк. Чтобы проиндексировать файл с заданным имя файла и данные в DHT SHA-1 хеш из имя файла генерируется 160-битный ключ k, и сообщение положил(k, данные) отправляется на любой узел, участвующий в DHT. Сообщение пересылается от узла к узлу через оверлейную сеть, пока не достигнет единственного узла, ответственного за ключ. k как указано разделением пространства ключей. Затем этот узел хранит ключ и данные. Затем любой другой клиент может получить содержимое файла, снова хешируя имя файла производить k и запрашивая любой узел DHT найти данные, связанные с k с сообщением получать(k). Сообщение снова будет перенаправлено через оверлей на узел, ответственный за k, который ответит сохраненным данные.

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

Разбиение ключевого пространства

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

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

Последовательное хеширование

Последовательное хеширование использует функцию который определяет абстрактное понятие расстояния между клавишами и , который не зависит от географического расстояния или сети задержка. Каждому узлу назначается единственный ключ, называемый его идентификатор (Я БЫ). Узел с ID владеет всеми ключами для которого ближайший идентификатор, измеренный в соответствии с .

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

Рандеву хеширование

При рандеву-хешировании, также называемом хешированием наивысшего случайного веса (HRW), все клиенты используют одну и ту же хеш-функцию. (выбирается заранее), чтобы связать ключ с одним из п доступные серверы - у каждого клиента одинаковый список идентификаторов {S1, S2, ..., Sп }, по одному на каждый сервер. k, клиент вычисляет п хеш-веса ш1 = час(S1, k), ш2 = час(S2, k), ..., шп = час(Sп, k).Клиент связывает этот ключ с сервером, соответствующим наивысшему весу хэша для этого ключа. Сервер с идентификатором владеет всеми ключами для которого хеш-вес выше, чем хэш-вес любого другого узла для этого ключа.

Хеширование с сохранением местоположения

Хеширование с сохранением местоположения гарантирует, что одинаковые ключи назначаются аналогичным объектам. Это может обеспечить более эффективное выполнение запросов диапазона, однако, в отличие от использования согласованного хеширования, больше нет гарантии, что ключи (и, следовательно, нагрузка) равномерно случайным образом распределены по пространству ключей и участвующим одноранговым узлам. Протоколы DHT, такие как Self-Chord и Oscar[13] решает такие вопросы. Self-Chord отделяет ключи объектов от одноранговых идентификаторов и сортирует ключи по кольцу с помощью статистического подхода, основанного на рой интеллект парадигма.[14] Сортировка гарантирует, что похожие ключи хранятся соседними узлами и что процедуры обнаружения, включая диапазон запросов, может выполняться за логарифмическое время. Оскар создает судоходный сеть малого мира на основе случайная прогулка выборка также обеспечивает логарифмическое время поиска.

Оверлейная сеть

Каждый узел поддерживает набор ссылки к другим узлам (его соседи или таблица маршрутизации). Вместе эти ссылки образуют оверлейную сеть.[15] Узел выбирает своих соседей в соответствии с определенной структурой, называемой топология сети.

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

Помимо базовой правильности маршрутизации, два важных ограничения топологии должны гарантировать, что максимальное количество хмель на любом маршруте (длина маршрута) мала, поэтому запросы выполняются быстро; и что максимальное количество соседей любого узла (максимальный узел степень) низкий, поэтому накладные расходы на обслуживание не являются чрезмерными. Конечно, короткие маршруты требуют большего максимальная степень. Ниже приведены некоторые общие варианты максимальной степени и длины маршрута, где п это количество узлов в DHT, используя Обозначение Big O:

Максимум. степеньМаксимальная длина маршрутаИспользуется вПримечание
Худшая длина поиска, вероятно, гораздо более медленное время поиска
Koorde (с постоянной степенью)Более сложный в реализации, но приемлемое время поиска можно найти при фиксированном количестве подключений.
Аккорд
Кадемлия
Кондитерские изделия
Гобелен
Чаще всего, но не оптимально (градус / длина маршрута). Chord - это самая базовая версия, а Kademlia кажется наиболее популярным оптимизированным вариантом (должен быть улучшен средний поиск)
Koorde (с оптимальным поиском)Сложнее реализовать, но поиск может быть быстрее (имеет нижнюю границу наихудшего случая)
Наихудшие потребности в локальном хранилище с интенсивным обменом данными после подключения или отключения любого узла

Самый распространенный выбор, Степень / длина маршрута не является оптимальным с точки зрения компромисса между степенью и длиной маршрута, но такие топологии обычно допускают большую гибкость в выборе соседей. Многие DHT используют эту гибкость для выбора соседей, близких по времени задержки в физической базовой сети. В общем, все DHT строят навигационные сетевые топологии малого мира, в которых выбирается компромисс между длиной маршрута и степенью сети.[16]

Максимальная длина маршрута тесно связана с диаметр: максимальное количество переходов на любом кратчайшем пути между узлами. Очевидно, что длина маршрута в наихудшем случае по крайней мере равна ее диаметру, поэтому DHT ограничены соотношением градус / диаметр.[17] это фундаментально в теория графов. Длина маршрута может быть больше диаметра, так как жадный алгоритм маршрутизации может не находить кратчайшие пути.[18]

Алгоритмы наложения сетей

Помимо маршрутизации, существует множество алгоритмов, которые используют структуру оверлейной сети для отправки сообщения всем узлам или подмножеству узлов в DHT.[19] Эти алгоритмы используются приложениями для наложение многоадресной рассылки, диапазон запросов или сбор статистики. Две системы, основанные на этом подходе: Structella,[20] который реализует лавинную рассылку и случайные блуждания на наложении Pastry, и DQ-DHT, который реализует алгоритм поиска с динамическими запросами по сети Chord.[21]

Безопасность

Благодаря децентрализации, отказоустойчивости и масштабируемости DHT по своей природе более устойчивы к враждебному злоумышленнику, чем централизованная система.[нечеткий]

Открытые системы для распределенное хранилище данных которые устойчивы к массированным враждебным атакам, возможны.[22]

Система DHT, которая тщательно разработана, чтобы иметь Византийская отказоустойчивость может защитить от уязвимости в системе безопасности, известной как Атака Сибиллы, который влияет на все текущие проекты DHT.[23][24]

Петар Маймунков, один из первых авторов Кадемлия, предложил способ обойти слабые места атаки Сибиллы путем включения отношений социального доверия в структуру системы.[25] Новая система под кодовым названием Tonika или также известная под своим доменным именем 5ttt, основана на алгоритме, известном как «электрическая маршрутизация», и написана в соавторстве с математиком Джонатаном Кельнером.[26] Маймунков сейчас предпринял комплексные усилия по внедрению этой новой системы. Однако исследование эффективных средств защиты от атак Sybil обычно считается открытым вопросом, и каждый год на ведущих конференциях по исследованию безопасности предлагается широкий спектр потенциальных средств защиты.[нужна цитата]

Реализации

Наиболее заметные различия, встречающиеся в практических примерах реализации DHT, включают как минимум следующее:

  • Адресное пространство - это параметр DHT. Некоторые реальные DHT используют 128-битное или 160-битное пространство ключей.
  • Некоторые реальные DHT используют хеш-функции, отличные от SHA-1.
  • В реальном мире ключ k может быть хешем файла содержание а не хеш файла имя предоставлять хранилище с адресацией по содержимому, чтобы переименование файла не мешало пользователям его найти.
  • Некоторые DHT могут также публиковать объекты разных типов. Например, ключ k может быть узлом Я БЫ и связанные данные могут описывать, как связаться с этим узлом. Это позволяет публиковать информацию о присутствии и часто используется в приложениях для обмена мгновенными сообщениями и т. Д. В простейшем случае Я БЫ это просто случайное число, которое напрямую используется как ключ k (так что в 160-битном DHT Я БЫ будет 160-битным числом, обычно выбираемым случайным образом). В некоторых DHT публикация идентификаторов узлов также используется для оптимизации операций DHT.
  • Для повышения надежности можно добавить избыточность. В (k, данные) пара ключей может храниться более чем в одном узле, соответствующем ключу. Обычно вместо выбора только одного узла алгоритмы реального мира DHT выбирают я подходящие узлы, с я является параметром DHT, зависящим от реализации. В некоторых проектах DHT узлы соглашаются обрабатывать определенный диапазон пространства ключей, размер которого может выбираться динамически, а не жестко запрограммированным.
  • Некоторые продвинутые DHT, такие как Кадемлия сначала выполнить итеративный поиск через DHT, чтобы выбрать набор подходящих узлов и отправить положить (k, данные) сообщения только этим узлам, что резко снижает бесполезный трафик, поскольку опубликованные сообщения отправляются только узлам, которые кажутся подходящими для хранения ключа k; а итеративный поиск охватывает только небольшой набор узлов, а не весь DHT, что сокращает бесполезную пересылку. В таких DHT пересылка положить (k, данные) сообщения могут появляться только как часть алгоритма самовосстановления: если целевой узел получает положить (k, данные) сообщение, но считает, что k находится за пределами обрабатываемого диапазона и известен более близкий узел (с точки зрения пространства ключей DHT), сообщение пересылается на этот узел. В противном случае данные индексируются локально. Это приводит к некоторому самобалансирующемуся поведению DHT. Конечно, такой алгоритм требует, чтобы узлы публиковали данные о своем присутствии в DHT, чтобы можно было выполнять итеративный поиск.
  • Поскольку на большинстве машин отправка сообщений намного дороже, чем доступ к локальной хеш-таблице, имеет смысл объединить множество сообщений, касающихся конкретного узла, в один пакет. Предполагая, что каждый узел имеет локальный пакет, состоящий не более чем из б операций, процедура комплектации следующая. Каждый узел сначала сортирует свой локальный пакет по идентификатору узла, ответственного за операцию. С помощью ведро сортировка, это можно сделать в O (b + n), где п - количество узлов в DHT. Когда в одном пакете выполняется несколько операций, обращающихся к одному и тому же ключу, пакет уплотняется перед отправкой. Например, несколько поисков одного и того же ключа могут быть сокращены до одного или несколько приращений могут быть сокращены до одной операции добавления. Это сокращение может быть реализовано с помощью временной локальной хеш-таблицы. Наконец, операции отправляются в соответствующие узлы.[27]

Примеры

Протоколы и реализации DHT

Приложения, использующие DHT

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

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

  1. ^ Стойка, И.; Morris, R .; Каргер, Д.; Kaashoek, M. F .; Балакришнан, Х. (2001). «Chord: масштабируемая одноранговая служба поиска для интернет-приложений» (PDF). Обзор компьютерных коммуникаций ACM SIGCOMM. 31 (4): 149. Дои:10.1145/964723.383071. Значение может быть адресом, документом или произвольным элементом данных.
  2. ^ Лиз, Кроукрофт; и другие. (2005). «Обзор и сравнение схем одноранговых оверлейных сетей» (PDF). Обзоры и учебные пособия по коммуникациям IEEE. 7 (2): 72–93. CiteSeerX 10.1.1.109.6124. Дои:10.1109 / COMST.2005.1610546.
  3. ^ Рихтер, Стивенсон; и другие. (2009). «Анализ влияния моделей динамических запросов на отношения клиент-сервер». Тенденции в современных вычислениях: 682–701.
  4. ^ Поиск в маленьком мире, главы 1 и 2 (PDF), получено 2012-01-10
  5. ^ «Раздел 5.2.2» (PDF), Распределенная децентрализованная система хранения и поиска информации, получено 2012-01-10
  6. ^ Ратнасами; и другие. (2001). «Масштабируемая сеть с адресацией к контенту» (PDF). В материалах ACM SIGCOMM 2001. Получено 2013-05-20. Цитировать журнал требует | журнал = (Помогите)
  7. ^ Хари Балакришнан, М. Франс Каашук, Дэвид Каргер, Роберт Моррис, Ион Стойка. Поиск данных в P2P-системах. В Коммуникации ACM, Февраль 2003 г.
  8. ^ Дэвид Коэн (1 октября 2002 г.). «Новая P2P-сеть, финансируемая правительством США». Новый ученый. Получено 10 ноября, 2013.
  9. ^ «Массачусетский технологический институт, Беркли, ICSI, Нью-Йоркский университет и Райс запускают проект IRIS». пресс-релиз. Массачусетский технологический институт. 25 сентября 2002 г. Архивировано с оригинал 26 сентября 2015 г.. Получено 10 ноября, 2013.
  10. ^ Гвидо Урданета, Гийом Пьер и Мартен ван Стин. Обзор методов безопасности DHT. ACM Computing Surveys 43 (2), январь 2011 г.
  11. ^ Мони Наор и Уди Видер. Новые архитектуры для P2P-приложений: непрерывно-дискретный подход. Proc. СПА, 2003.
  12. ^ Гурмит Сингх Манку. Dipsea: модульная распределенная хеш-таблица В архиве 2004-09-10 на Wayback Machine. Докторская диссертация (Стэнфордский университет), август 2004 г.
  13. ^ Гирдзияускас, Шарунас; Датта, Анвитаман; Аберер, Карл (01.02.2010). «Структурированное наложение для гетерогенных сред». Транзакции ACM в автономных и адаптивных системах. 5 (1): 1–25. Дои:10.1145/1671948.1671950. ISSN 1556-4665.
  14. ^ Форестьеро, Агостино; Леонарди, Эмилио; Мастроянни, Карло; Мео, Микела (октябрь 2010 г.). «Self-Chord: основанная на биологических принципах P2P-платформа для самоорганизующихся распределенных систем». Транзакции IEEE / ACM в сети. 18 (5): 1651–1664. Дои:10.1109 / TNET.2010.2046745.
  15. ^ Галуба, Войцех; Гирдзияускас, Шарунас (2009 г.), «Одноранговые оверлейные сети: структура, маршрутизация и обслуживание», в LIU, LING; ОЗСУ, М. ТАМЕР (ред.), Энциклопедия систем баз данных, Springer США, стр. 2056–2061, Дои:10.1007/978-0-387-39940-9_1215, ISBN 9780387399409
  16. ^ Гирдзияускас, Шарунас (2009). Проектирование одноранговых сетей с учетом перспективы малого мира. epfl.ch. EPFL.
  17. ^ Задача (градус, диаметр) для графов, Maite71.upc.es, архивировано с оригинал на 2012-02-17, получено 2012-01-10
  18. ^ Гурмит Сингх Манку, Мони Наор и Уди Видер. "Знай своего соседа: сила предвидения в случайных P2P-сетях". Proc. СТОК, 2004.
  19. ^ Али Годси. «Распределенная k-арная система: алгоритмы для распределенных хеш-таблиц», В архиве 22 мая 2007 г. Wayback Machine. KTH-Королевский технологический институт, 2006 г.
  20. ^ Кастро, Мигель; Коста, Мануэль; Роустрон, Энтони (1 января 2004 г.). «Должны ли мы строить Gnutella на структурированном оверлее?» (PDF). Обзор компьютерных коммуникаций ACM SIGCOMM. 34 (1): 131. CiteSeerX 10.1.1.221.7892. Дои:10.1145/972374.972397.
  21. ^ Талия, Доменико; Трунфио, Паоло (декабрь 2010 г.). «Включение динамических запросов по распределенным хеш-таблицам». Журнал параллельных и распределенных вычислений. 70 (12): 1254–1265. Дои:10.1016 / j.jpdc.2010.08.012.
  22. ^ Барух Авербух, Кристиан Шайделер. «На пути к масштабируемому и надежному DHT» .2006.Дои:10.1145/1148109.1148163
  23. ^ Максвелл Янг; Аникет Кейт; Ян Голдберг; Мартин Карстен.«Практическая надежная коммуникация в DHT, противостоящая византийскому противнику».
  24. ^ Наталья Федотова; Джордано Орцетти; Лука Велтри; Алессандро Закканнини. «Византийское соглашение об управлении репутацией в одноранговых сетях на основе DHT».Дои:10.1109 / ICTEL.2008.4652638
  25. ^ Крис Лесневски-Лаас. "Защищенный от Сибиллы однократный DHT" (PDF): 20. Цитировать журнал требует | журнал = (Помогите)
  26. ^ Джонатан Келнер, Петар Маймунков (2009). «Электрическая трассировка и параллельная резка». arXiv:0909.2859. Bibcode:2009arXiv0909.2859K. Цитировать журнал требует | журнал = (Помогите)
  27. ^ Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов. Издательство Springer International. ISBN 978-3-030-25208-3.
  28. ^ Вики Сообщества В архиве 4 декабря 2010 г. Wayback Machine получено в январе 2010 года.
  29. ^ Retroshare FAQ получено декабрь 2011 г.

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