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

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

DHT образуют инфраструктуру, которую можно использовать для создания более сложных сервисов, таких как Anycast , совместное веб-кэширование , распределенные файловые системы , службы доменных имен , обмен мгновенными сообщениями , многоадресная рассылка , а также одноранговые системы обмена файлами и распространения контента . Известные распределенные сети, использующие DHT, включают сеть распределенный трекер BitTorrent, Kad , ботнет Storm , мессенджер Tox , Freenet , поисковую систему YaCy и InterPlanetary File System .

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

История

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

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

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

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

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

В 2001 году четыре системы — CAN , Аккорд , Кондитерские изделия и гобелены сделали ДГТ популярной темой исследований. США Проект под названием «Инфраструктура для устойчивых интернет-систем» (Iris) был профинансирован за счет гранта в размере 12 миллионов долларов США от Национального научного фонда в 2002 году. Среди исследователей были Сильвия Ратнасами , Ион Стойка , Хари Балакришнан и Скотт Шенкер . За пределами академических кругов технология DHT была принята в качестве компонента BitTorrent и в проектах PlanetLab, таких как Coral Content Distribution Network.

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

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

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

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

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

Структура

Структуру DHT можно разложить на несколько основных компонентов. Основой является абстрактное пространство ключей , такое как набор 160-битных строк . пространства ключей Схема разделения разделяет владение этим пространством ключей между участвующими узлами. Затем оверлейная сеть соединяет узлы, позволяя им найти владельца любого ключа в пространстве ключей.

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

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

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

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

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

Согласованное хеширование

Дополнительная информация: Согласованное хеширование.

Согласованное хеширование использует функцию $\delta (k_{1},k_{2})$ который определяет абстрактное понятие расстояния между клавишами $k_{1}$ и $k_{2}$, что не связано с географическим расстоянием или задержкой сети . Каждому узлу назначается один ключ, называемый его идентификатором (ID). Узел с идентификатором $i_{x}$ владеет всеми ключами $k_{m}$ для чего $i_{x}$ — ближайший идентификатор, измеренный в соответствии с $\delta (k_{m},i_{x})$.

Например, Chord DHT использует последовательное хеширование, при котором узлы рассматриваются как точки на круге. $\delta (k_{1},k_{2})$ это расстояние, проходимое по кругу по часовой стрелке от $k_{1}$ к $k_{2}$. Таким образом, круговое пространство ключей разбивается на смежные сегменты, конечными точками которых являются идентификаторы узлов. Если $i_{1}$ и $i_{2}$ — это два соседних идентификатора, находящихся на меньшем расстоянии по часовой стрелке от $i_{1}$ к $i_{2}$, то узел с идентификатором $i_{2}$ владеет всеми ключами, которые попадают между $i_{1}$ и $i_{2}$.

Хэширование рандеву

Дополнительная информация: Хэширование рандеву.

При хешировании рандеву, также называемом хешированием с наибольшим случайным весом (HRW), все клиенты используют одну и ту же хэш-функцию. $h()$ (выбран заранее), чтобы связать ключ с одним из n доступных серверов. одинаковый список идентификаторов { S1 _. , S2 _{Каждый клиент имеет} ,..., Sn _} сервера , по одному для каждого По некоторому ключу k клиент вычисляет n хеш-весов w ₁ = h ( S ₁ , k ), w ₂ = h ( S ₂ , k ), ..., w _n = h ( S _n , k ) . Клиент связывает этот ключ с сервером, соответствующим наибольшему весу хеш-функции для этого ключа. Сервер с идентификатором $S_{x}$ владеет всеми ключами $k_{m}$ для которого хеш-вес $h(S_{x},k_{m})$ выше, чем хеш-вес любого другого узла для этого ключа.

Хеширование с сохранением локальности

Дополнительная информация: Хеширование с сохранением локальности.

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

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

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

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

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

Макс. степень	Максимальная длина маршрута	Используется в	Примечание
$O(1)$	$O(n)$		Наихудшая длина поиска, вероятно, с гораздо более медленным временем поиска.
$O(1)$	$O(\log n)$	Хорда (с постоянной степенью)	Более сложна в реализации, но приемлемое время поиска можно найти при фиксированном количестве соединений.
$O(\log n)$	$O(\log n)$	Аккорд Кадемлия Кондитерские изделия Гобелен	Самый распространенный, но не оптимальный (градус/длина маршрута). Chord — самая базовая версия, а Kademlia — самый популярный оптимизированный вариант (должен быть улучшен средний поиск).
$O(\log n)$	$O(\log n/\log(\log n))$	Шнуры (с оптимальным поиском)	Сложнее реализовать, но поиск может быть быстрее (имеет нижнюю границу наихудшего случая)
$O({\sqrt {n}})$	$O(1)$		Наихудшие потребности в локальном хранилище, с большим объемом обмена данными после подключения или отключения любого узла.

Самый распространенный выбор, $O(\log n)$ степень/длина маршрута не является оптимальным с точки зрения соотношения степени/длины маршрута, но такие топологии обычно обеспечивают большую гибкость в выборе соседей. Многие DHT используют эту гибкость для выбора соседей, близких по задержке в физической базовой сети. В общем, все DHT создают навигационные топологии сетей маленького мира, в которых длина маршрута находится в компромиссе с уровнем сети.

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

Алгоритмы для оверлейных сетей

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

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

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

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

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

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

Реализации

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

• Адресное пространство является параметром DHT. Некоторые реальные DHT используют 128-битное или 160-битное пространство ключей.
• Некоторые реальные DHT используют хеш-функции, отличные от SHA-1 .
• В реальном мире ключ k файла, может быть хешем содержимого файла а не хешем имени , чтобы обеспечить хранилище с адресацией по содержимому , чтобы переименование файла не мешало пользователям его найти.
• Некоторые DHT также могут публиковать объекты разных типов. Например, ключ k может быть узлом Идентификатор и связанные с ним данные могут описывать, как связаться с этим узлом. Это позволяет публиковать информацию о присутствии и часто используется в приложениях обмена мгновенными сообщениями и т. д. В простейшем случае ID — это просто случайное число, которое напрямую используется в качестве ключа. k (то есть в 160-битном DHT ID будет 160-битным числом, обычно выбираемым случайным образом). В некоторых DHT публикация идентификаторов узлов также используется для оптимизации операций DHT.
• Для повышения надежности можно добавить резервирование. (k, data) пара ключей может храниться более чем в одном узле, соответствующем ключу. Обычно вместо того, чтобы выбирать только один узел, реальные алгоритмы DHT выбирают мне подходят узлы, с i — параметр DHT, специфичный для реализации. В некоторых конструкциях DHT узлы соглашаются обрабатывать определенный диапазон пространства ключей, размер которого можно выбирать динамически, а не жестко запрограммировать.
• Некоторые продвинутые DHT, такие как Kademlia, сначала выполняют итеративный поиск через DHT, чтобы выбрать набор подходящих узлов и отправить сообщения put(k, data) только на эти узлы, что радикально снижает бесполезный трафик, поскольку опубликованные сообщения отправляются только на узлы, которые кажутся подходящими для хранения ключа. к ; а итеративные поиски охватывают лишь небольшой набор узлов, а не весь DHT, что сокращает бесполезную пересылку. В таких DHT пересылка Сообщения put(k, data) могут возникать только как часть алгоритма самовосстановления: если целевой узел получает сообщение put(k, data) сообщение, но считает, что k находится вне обрабатываемого диапазона и известен ближайший узел (с точки зрения пространства ключей DHT), сообщение пересылается на этот узел. В противном случае данные индексируются локально. Это приводит к некоторому самобалансирующемуся поведению DHT. Конечно, такой алгоритм требует, чтобы узлы публиковали данные о своем присутствии в DHT, чтобы можно было выполнять итеративный поиск.
• Поскольку на большинстве машин отправка сообщений обходится намного дороже, чем доступ к локальной хэш-таблице, имеет смысл объединить множество сообщений, касающихся конкретного узла, в один пакет. Предполагая, что каждый узел имеет локальный пакет, состоящий не более чем из b операций, процедура объединения заключается в следующем. Каждый узел сначала сортирует свой локальный пакет по идентификатору узла, ответственного за операцию. Используя сегментную сортировку , это можно сделать в O(b + n) , где n — количество узлов в DHT. Если в одном пакете выполняется несколько операций, обращающихся к одному и тому же ключу, перед отправкой пакет сжимается. Например, несколько поисков одного и того же ключа можно свести к одному, а несколько приращений можно свести к одной операции добавления. Такое сокращение можно реализовать с помощью временной локальной хеш-таблицы. Наконец, операции отправляются на соответствующие узлы.

Примеры

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

• Апач Кассандра
• Наложение дубинки
• Mainline DHT – стандартный DHT, используемый BitTorrent (на основе Kademlia , предоставленный Khashmir)
• Сеть с адресацией контента (CAN)
• Аккорд
• Шнуры
• Кадемлия
• Кондитерские изделия
• P-сетка
• Пульсация
• СциллаБД
• Гобелен
• ТомP2P
• Волдеморт

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

• BTDigg : поисковая система BitTorrent DHT.
• Codeen : веб-кэширование
• Freenet : анонимная сеть, устойчивая к цензуре.
• GlusterFS : распределенная файловая система, используемая для виртуализации хранения.
• GNUnet : распределительная сеть, подобная Freenet, включая реализацию DHT.
• I2P : анонимная одноранговая сеть с открытым исходным кодом.
• I2P-Bote : бессерверная безопасная анонимная электронная почта
• IPFS : одноранговый протокол распространения гипермедиа с адресацией по контенту.
• JXTA : P2P-платформа с открытым исходным кодом.
• LBRY : протокол обмена контентом на основе блокчейна, который использует систему DHT под влиянием Kademlia для распространения контента.
• Oracle Coherence : сетка данных в памяти, построенная на основе реализации Java DHT.
• Perfect Dark : одноранговое приложение для обмена файлами из Японии.
• Retroshare : друзей-другов сеть
• Jami : сохраняющая конфиденциальность платформа голосовой, видео и чат-связи, основанная на Kademlia-подобном DHT.
• Tox : система обмена мгновенными сообщениями, предназначенная для Skype. замены
• Twister : микроблогов. одноранговая платформа
• YaCy : распределенная поисковая система.

См. также

• Couchbase Server : постоянная, реплицируемая, кластеризованная система хранения распределенных объектов, совместимая с протоколом memcached.
• Memcached : высокопроизводительная система кэширования объектов с распределенной памятью.
• Префиксное хеш-дерево : сложные запросы по DHT.
• Дерево Меркла : дерево, в котором каждый нелистовой узел помечен хешем меток его дочерних узлов.
• Большинство распределенных хранилищ данных используют для поиска ту или иную форму DHT.
• Графы пропуска — это эффективная структура данных для реализации DHT.

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

• Распределенные хэш-таблицы, часть 1 , Брэндон Уайли.
• Распределенные хэш-таблицы связывают страницу Карлеса Паиро, посвященную исследованиям DHT и P2P.
• kademlia.scs.cs.nyu.edu Архив.org снимки kademlia.scs.cs.nyu.edu
• Энг-Кеонг Луа; Кроукрофт, Джон; Пиас, Марсело; Шарма, Рави; Лим, Стив (2005). «Опрос IEEE по схемам наложенной сети». CiteSeerX   10.1.1.111.4197 : охватывает неструктурированные и структурированные децентрализованные оверлейные сети, включая DHT (Chord, Pastry, Tapestry и другие).
• Магистральное измерение DHT на факультете компьютерных наук Хельсинкского университета, Финляндия.