Введение

Децентрализованная распределенная система с поисковой службой

Распределенная хеш-таблица (DHT) — это распределенная система, предоставляющая поисковую службу, аналогичную хеш-таблице. В DHT хранятся пары «ключ-значение», и любой участвующий узел может эффективно извлекать значение, соответствующее заданному ключу. Основное преимущество DHT заключается в том, что узлы можно добавлять или удалять с минимальными усилиями по перераспределению ключей. Ключи — это уникальные идентификаторы, которые сопоставляются с определенными значениями, которые, в свою очередь, могут быть чем угодно: от адресов и документов до произвольных данных. Ответственность за поддержание соответствия между ключами и значениями распределяется между узлами таким образом, что изменение состава участников вызывает минимальные сбои. Это позволяет DHT масштабироваться до чрезвычайно большого числа узлов и обрабатывать постоянные подключения, отключения и отказы узлов. DHT формируют инфраструктуру, которую можно использовать для создания более сложных сервисов, таких как anycast, совместное веб-кэширование, распределенные файловые системы, службы доменных имен, мгновенный обмен сообщениями, многоадресная рассылка, а также одноранговый обмен файлами и системы распространения контента. К известным распределенным сетям, использующим DHT, относятся распределенный трекер BitTorrent, сеть Kad, ботнет Storm, мессенджер Tox, Freenet, поисковая система YaCy и Межпланетная файловая система.

История

Исследования DHT были изначально мотивированы, отчасти, одноранговыми (P2P) системами, такими как Freenet, Gnutella, BitTorrent и Napster, которые использовали распределенные по Интернету ресурсы для предоставления единого полезного приложения. В частности, они воспользовались увеличением пропускной способности и объема жестких дисков для обеспечения сервиса обмена файлами. Эти системы различались способом поиска данных, предлагаемых их участниками. Napster, первая крупномасштабная система доставки P2P-контента, требовала центральный индексный сервер: каждый узел, при подключении, отправлял список локально хранимых файлов на сервер, который выполнял поиск и перенаправлял запросы на узлы, содержащие результаты. Этот центральный компонент делал систему уязвимой для атак и судебных разбирательств. Gnutella и подобные сети перешли к модели широковещательного поиска: каждый запрос приводил к отправке сообщения на каждую машину в сети. Хотя этот метод избегал единой точки отказа, он был значительно менее эффективным, чем Napster. Более поздние версии клиентов Gnutella перешли к динамической модели запросов, что значительно повысило эффективность. Freenet полностью распределена, но использует эвристическую маршрутизацию на основе ключей, в которой каждому файлу сопоставляется ключ, а файлы с похожими ключами, как правило, группируются на одном и том же наборе узлов. Запросы, скорее всего, будут маршрутизироваться через сеть к такому кластеру без необходимости посещения множества узлов. Однако Freenet не гарантирует нахождение данных. Распределенные хэш-таблицы используют более структурированную маршрутизацию на основе ключей, чтобы достичь как децентрализации Freenet и Gnutella, так и эффективности и гарантированных результатов Napster. Одним из недостатков является то, что, как и Freenet, DHT напрямую поддерживают только поиск точного соответствия, а не поиск по ключевым словам, хотя алгоритм маршрутизации Freenet может быть обобщен для любого типа ключей, где определена операция близости. В 2001 году четыре системы — CAN, Chord, Pastry и Tapestry — стимулировали исследования DHT как популярной темы. Проект под названием «Инфраструктура устойчивых интернет-систем» (Iris) был профинансирован грантом в размере 12 миллионов долларов от Национального научного фонда США в 2002 году. Среди исследователей были Сильвия Ратнасами, Ион Стойка, Хари Балакришнан и Скотт Шенкер. За пределами академической среды технология DHT была принята в качестве компонента BitTorrent и в проектах PlanetLab, таких как Coral Content Distribution Network.

Структура

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

Разделение клавишных пространств

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

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

В последовательном хешировании используется функция, которая определяет абстрактное понятие расстояния между ключами и , не связанное с географическим расстоянием или задержкой сети. Каждому узлу присваивается один ключ, называемый его идентификатором (ID). Узел с ID владеет всеми ключами , для которых этот ID является ближайшим, измеренным в соответствии с . Например, DHT Chord использует последовательное хеширование, рассматривая узлы как точки на окружности, а – это расстояние по часовой стрелке от до . Таким образом, круговое пространство ключей разделяется на смежные сегменты, конечными точками которых являются идентификаторы узлов. Если и – два соседних ID, при этом расстояние по часовой стрелке от до меньше, то узел с ID владеет всеми ключами, попадающими между и .

Хэширование встреч

В хэшировании rendezvous, также называемом хэшированием с наивысшим случайным весом (HRW), все клиенты используют одну и ту же хэш-функцию (выбранную заранее) для сопоставления ключа одному из n доступных серверов. У каждого клиента есть один и тот же список идентификаторов, по одному для каждого сервера. Для данного ключа k клиент вычисляет n хэш-весов: w1 = h(S1, k), w2 = h(S2, k), ..., wn = h(Sn, k). Клиент сопоставляет этот ключ с сервером, соответствующим наибольшему хэш-весу для этого ключа. Сервер с идентификатором владеет всеми ключами, для которых хэш-вес выше, чем хэш-вес любого другого узла для данного ключа.

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

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

Накладная сеть

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

Макс. степень Макс. длина маршрута Применяется в Примечание Наихудшая длина поиска, с вероятностью значительно более длительного времени поиска Koorde (с постоянной степенью) Сложнее в реализации, но приемлемое время поиска можно достичь с фиксированным числом соединений Chord Kademlia Pastry Tapestry Наиболее распространенный, но не оптимальный (соотношение степени/длины маршрута). Chord — самая простая версия, а Kademlia — наиболее популярный оптимизированный вариант (должен обеспечивать улучшенный средний поиск) Koorde (с оптимальным поиском) Сложнее в реализации, но поиск может быть быстрее (имеет более низкую границу в худшем случае) Наихудшие требования к локальному хранилищу, с большим объемом коммуникаций после подключения или отключения любого узла

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

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

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

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

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