A распределенная хеш-таблица (DHT ) - это распределенная система, которая предоставляет службу поиска, аналогичную хэш-таблице : пары ключ-значение хранятся в DHT, и любой участвующий узел узел может эффективно извлекать значение, связанное с данный ключ. Основным преимуществом DHT является то, что узлы можно добавлять или удалять с минимальными усилиями по перераспределению ключей. Ключи - это уникальные идентификаторы, которые сопоставляются с определенными значениями, которые, в свою очередь, могут быть любыми: от адресов до документов и произвольных данных. Ответственность за поддержание сопоставления ключей и значений распределяется между узлами таким образом, что изменение набора участников вызывает минимальные нарушения. Это позволяет DHT масштабировать до очень большого количества узлов и обрабатывать постоянные прибытия, отправления и отказы узлов.
DHT образуют инфраструктуру, которую можно использовать для создания более сложных сервисов, таких как anycast, совместное веб-кэширование, распределенные файловые системы, службы доменных имен, обмен мгновенными сообщениями, многоадресная передача, а также одноранговый обмен файлами и распространение контента системы. Известные распределенные сети, использующие DHT, включают распределенный трекер BitTorrent, Coral Content Distribution Network, сеть Kad, ботнет Storm, программа обмена мгновенными сообщениями Tox, Freenet, поисковая система YaCy и Межпланетная файловая система.
Распределенные хэш-таблицыПервоначально исследования DHT были частично мотивированы одноранговыми (P2P) системами, такими как Freenet, Gnutella, BitTorrent и Napster, которые использовали ресурс ces распределены по Интернету для создания единого полезного приложения. В частности, они воспользовались преимуществами увеличенной полосы пропускания и емкости жесткого диска для предоставления услуги обмена файлами.
Эти системы различались тем, как они размещали данные, предлагаемые их ровесники. Napster, первая крупномасштабная система доставки контента P2P, требовала центрального сервера индекса: каждый узел после присоединения отправлял список локально хранимых файлов на сервер, который выполнял поиск и направлял запросы на узлы, которые содержали полученные результаты. Этот центральный компонент сделал систему уязвимой для атак и судебных исков.
Gnutella и аналогичные сети перешли на модель лавинной рассылки запросов - по сути, каждый поиск будет приводить к трансляции сообщения на все остальные машины в сети. Избегая единой точки отказа , этот метод был значительно менее эффективным, чем Napster. Более поздние версии клиентов Gnutella перешли на модель, которая значительно повысила эффективность.
Freenet полностью распределен, но использует эвристическую маршрутизацию на основе ключей, в которой каждый файл связаны с ключом, а файлы с аналогичными ключами имеют тенденцию к кластеризации на аналогичном наборе узлов. Скорее всего, запросы будут направляться через сеть в такой кластер без необходимости посещения множества одноранговых узлов. Однако Freenet не гарантирует, что данные будут найдены.
Распределенные хэш-таблицы используют более структурированную маршрутизацию на основе ключей для достижения как децентрализации Freenet и Gnutella, так и эффективности и гарантированных результатов Napster. Одним из недостатков является то, что, как и Freenet, DHT напрямую поддерживают только поиск с точным соответствием, а не поиск по ключевым словам, хотя алгоритм маршрутизации Freenet может быть обобщен для любого типа ключа, в котором может быть определена операция близости.
В 2001 году четыре системы - CAN, Chord, Pastry и Tapestry - сделали DHT популярной темой исследований. Проект под названием Infrastructure for Resilient Internet Systems (Iris) был профинансирован грантом в размере 12 миллионов долларов США Национального научного фонда в 2002 году. Среди исследователей были Сильвия Ратнасами, Ион Стойка, Хари Балакришнан и Скотт Шенкер. За пределами академических кругов технология DHT была принята как компонент BitTorrent, а в Coral Content Distribution Network.
DHT обычно подчеркивают следующие свойства:
Ключевой метод, используемый для достижения этих целей, заключается в том, что любой узел должен координироваться только с несколькими другими узлами в системе - чаще всего, O (log n) из n участников (см. ниже) - так что для каждого изменения членства необходимо выполнять лишь ограниченный объем работы.
Некоторые проекты DHT стремятся быть безопасными против злонамеренных участников и позволяют участникам оставаться анонимными, хотя это встречается реже, чем во многих других одноранговых сетях. (особенно файлообменник ) системы; см. анонимный P2P.
Наконец, DHT должны иметь дело с более традиционными проблемами распределенных систем, такими как балансировка нагрузки, целостность данных и производительность (в частности, обеспечение таких операций поскольку маршрутизация и хранение или извлечение данных завершаются быстро).
Структура DHT может быть разделена на несколько основных компонентов. В основе лежит абстрактное пространство ключей, такое как набор 160-битных строк. Схема разделения пространства ключей разделяет владение этим пространством ключей между участвующими узлами. Затем сеть наложения соединяет узлы, позволяя им найти владельца любого заданного ключа в пространстве ключей.
После того, как эти компоненты будут установлены, обычное использование DHT для хранения и извлечения может происходить следующим образом. Предположим, что пространство ключей - это набор 160-битных строк. Чтобы проиндексировать файл с заданным filenameи данными в DHT, создается хэш SHA-1 имени файла, в результате чего создается 160-битный ключ k, и помещается сообщение (k, data) отправляется на любой узел, участвующий в DHT. Сообщение пересылается от узла к узлу через оверлейную сеть, пока не достигнет единственного узла, ответственного за ключ k, как определено разделением пространства ключей. Затем этот узел хранит ключ и данные. Затем любой другой клиент может получить содержимое файла, снова хешируя имя файла для получения k и запрашивая любой узел DHT найти данные, связанные с k, с сообщением get (k). Сообщение снова будет перенаправлено через оверлей на узел, ответственный за k, который ответит сохраненными данными.
Сетевые компоненты разделения пространства ключей и перекрытия описаны ниже с целью уловить основные идеи, общие для большинства DHT; многие конструкции отличаются деталями.
Большинство DHT используют какой-либо вариант согласованного хеширования или рандеву-хеширования для сопоставления ключей с узлами. Эти два алгоритма, по-видимому, были разработаны независимо и одновременно для решения проблемы распределенной хеш-таблицы.
Как согласованное хеширование, так и рандеву-хеширование имеют важное свойство, заключающееся в том, что удаление или добавление одного узла изменяет только набор ключей, принадлежащих узлам со смежными идентификаторами, и не затрагивает все остальные узлы. Сравните это с традиционной хэш-таблицей , в которой добавление или удаление одной корзины приводит к переназначению почти всего пространства ключей. Поскольку любая смена владельца обычно соответствует перемещению объектов, хранящихся в DHT, с интенсивным использованием полосы пропускания, от одного узла к другому требуется минимизация такой реорганизации, чтобы эффективно поддерживать высокие скорости оттока (приход и сбой узла).
Согласованное хеширование использует функцию , который определяет абстрактное понятие расстояния между клавишами и , что не связано с географическим расстоянием или сетью задержкой. Каждому узлу назначается единственный ключ, называемый его идентификатором (ID). Узлу с идентификатором принадлежат все ключи , для которых - это ближайший идентификатор, измеренный согласно .
Например, Chord DHT использует согласованное хеширование, при котором узлы рассматриваются как точки на окружности, а - это расстояние, которое проходит по часовой стрелке по окружности от до . Таким образом, круговое пространство ключей разбивается на непрерывные сегменты, конечными точками которых являются идентификаторы узлов. Если и - два соседних идентификатора с меньшим расстоянием по часовой стрелке от до , затем узел с идентификатором владеет всеми ключами, находящимися между и .
При рандеву-хешировании, также называемом хешированием наивысшего случайного веса (HRW), все клиенты используют одну и ту же хеш-функцию (выбирается заранее), чтобы связать ключ с одним из n доступных серверов. Каждый клиент имеет одинаковый список идентификаторов {S 1, S 2,..., S n }, по одному для каждого сервера. Учитывая некоторый ключ k, клиент вычисляет n хеш-весов w 1 = h (S 1, k), w 2 = h (S 2, k),..., w n = h (S n, k). Клиент связывает этот ключ с сервером, соответствующим наивысшему весу хэша для этого ключа. Серверу с идентификатором принадлежат все ключи , для которых хэш-вес выше, чем хеш-вес любого другого узла для этого ключа.
Хеширование с сохранением местоположения гарантирует, что аналогичные ключи назначаются аналогичным объектам. Это может обеспечить более эффективное выполнение запросов диапазона, однако, в отличие от использования согласованного хеширования, больше нет гарантии, что ключи (и, следовательно, нагрузка) равномерно случайным образом распределены по пространству ключей и участвующим одноранговым узлам. Протоколы DHT, такие как Self-Chord и Oscar, решают такие проблемы. Self-Chord отделяет ключи объектов от одноранговых идентификаторов и сортирует ключи по кольцу с помощью статистического подхода, основанного на парадигме интеллекта роя. Сортировка гарантирует, что аналогичные ключи хранятся соседними узлами и что процедуры обнаружения, включая запросы диапазона, могут выполняться за логарифмическое время. Оскар создает навигационную сеть малого мира на основе выборки случайного блуждания, также обеспечивая логарифмическое время поиска.
Каждый узел поддерживает набор связей с другими узлами (своими соседями или таблицей маршрутизации ). Вместе эти ссылки образуют оверлейную сеть. Узел выбирает своих соседей в соответствии с определенной структурой, называемой топологией сети .
Все топологии DHT имеют один вариант наиболее важного свойства: для любого ключа k каждый узел либо имеет идентификатор узла, который владеет k, либо имеет ссылка на узел, идентификатор узла которого ближе к k, с точки зрения расстояния между ключами, определенного выше. Затем легко направить сообщение владельцу любого ключа k, используя следующий жадный алгоритм (который не обязательно является оптимальным в глобальном масштабе): на каждом шаге пересылать сообщение соседу, чей идентификатор наиболее близок к k. Если такого соседа нет, значит, мы должны достичь ближайшего узла, который является владельцем k, как определено выше. Этот стиль маршрутизации иногда называют маршрутизацией на основе ключей.
Помимо базовой правильности маршрутизации, два важных ограничения топологии должны гарантировать, что максимальное количество переходов на любом маршруте (длина маршрута) низкий, поэтому запросы выполняются быстро; и что максимальное количество соседей любого узла (максимальный узел степень ) низкое, так что накладные расходы на обслуживание не являются чрезмерными. Конечно, для более коротких маршрутов требуется более высокая максимальная степень. Ниже приведены некоторые распространенные варианты максимальной степени и длины маршрута, где n - количество узлов в DHT с использованием нотации Big O :
Макс. степень | Максимальная длина маршрута | Используется в | Примечание |
---|---|---|---|
Наихудшая длина поиска, вероятно, гораздо более медленное время поиска | |||
Коорде (с постоянной степенью) | Более сложный в реализации, но приемлемое время поиска можно найти при фиксированном количестве соединений | ||
Аккорд. Kademlia. Кондитерские изделия. Гобелен | Наиболее распространены, но не оптимальный (градус / длина маршрута). Chord является самой базовой версией, а Kademlia кажется наиболее популярным оптимизированным вариантом (должен иметь улучшенный средний поиск) | ||
Коорде (с оптимальным поиском) | Более сложный в реализации, но поиск может быть быстрее (иметь нижнюю границу наихудшего случая) | ||
Наихудшие потребности в локальном хранилище с интенсивным обменом данными после подключения или отключения любого узла |
Наиболее распространенный выбор, градусов / длина маршрута не является оптимальной с точки зрения компромисса между степенью и длиной маршрута, но такие топологии обычно допускают большую гибкость в выборе соседей. Многие DHT используют эту гибкость для выбора соседей, близких по задержке в физической базовой сети. В общем, все DHT строят навигационные сетевые топологии малого мира, в которых длина маршрута зависит от степени сети.
Максимальная длина маршрута тесно связана с диаметром : максимальное количество переходов на любом кратчайшем пути между узлами. Очевидно, что длина маршрута сети в наихудшем случае по крайней мере равна ее диаметру, поэтому DHT ограничиваются соотношением степень / диаметр, которое является фундаментальным в теории графов. Длина маршрута может быть больше диаметра, так как жадный алгоритм маршрутизации может не находить кратчайшие пути.
Помимо маршрутизации, существует множество алгоритмов, которые используют структуру наложения сеть для отправки сообщения всем узлам или подмножеству узлов в DHT. Эти алгоритмы используются приложениями для выполнения наложения многоадресной передачи, запросов диапазона или для сбора статистики. Две системы, основанные на этом подходе: Structella, которая реализует лавинную рассылку и случайные обходы в наложении Pastry, и DQ-DHT, которая реализует алгоритм поиска с динамическими запросами по сети Chord.
Благодаря децентрализации, отказоустойчивости и масштабируемости DHT по своей сути более устойчивы к злоумышленникам, чем централизованная система.
Открытые системы для распределенного хранилища данных, которые являются надежными против массивных враждебных злоумышленников возможны.
Система DHT, тщательно разработанная для обеспечения византийской отказоустойчивости, может защитить от уязвимости системы безопасности, известной как атака Сибиллы, который затрагивает все текущие разработки DHT.
Петар Маймунков, один из первых авторов Kademlia, предложил способ обойти слабость атаки Сибиллы путем включения в систему отношений социального доверия дизайн. Новая система под кодовым названием Tonika или также известная под своим доменным именем 5ttt, основана на алгоритме, известном как «электрическая маршрутизация», и написана в соавторстве с математиком Джонатаном Кельнером. Маймунков сейчас предпринял комплексные усилия по внедрению этой новой системы. Тем не менее, исследование эффективных средств защиты от атак Сибиллы обычно считается открытым вопросом, и на ведущих конференциях по исследованию безопасности ежегодно предлагается широкий спектр потенциальных средств защиты.
Наиболее заметные различия, встречающиеся в Практические примеры реализации DHT включают, по крайней мере, следующее:
| journal =
(), охватывающий неструктурированные и структурированные децентрализованные оверлейные сети, включая DHT (Chord, Pastry, Tapestry и другие).