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

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

Эти системы различаются тем, как они находили данные пиров:

• Napster имел центральный индексный сервер: каждый узел, после присоединения, должен отправить список локально хранящихся файлов на сервер, который должен произвести поиск и направить запрос к узлам, содержащим результаты. Этот центральный компонент делал систему уязвимой для атак и рисков.
• Gnutella и похожие сети двинулись к модели лавинных запросов — в основном, каждый поиск привёл бы к сообщению, передаваемому на все машины сети. Избегая централизованного отказа, этот метод был значительно менее эффективным, чем Napster.
• Наконец, Freenet был также полностью распределённым, но маршрутизация работает на базе эвристического ключа, в котором каждый файл имеет ассоциированный с ним ключ, а файлы с похожими ключами имели тенденцию к объединению в кластеры на похожем наборе узлов. Запрос, скорее всего, направлялся таким кластерам без надобности опрашивать всех пиров. Однако Freenet не мог гарантировать, что данные будут найдены.

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

Первые четыре DHT — CAN, Chord, Pastry и Tapestry (англ. Tapestry) — были введены приблизительно в 2001 году. С тех пор эта область изысканий была достаточно активна. Вне научных кругов DHT-технологию приняли как компонент BitTorrent и Coral Content Distribution Network.

DHT характеризуется следующими свойствами:

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

Ключевая методика достижения цели заключается в том, что любой узел должен координировать работу только с несколькими узлами в системе — как правило, О(logn), где n — количество участников (смотри ниже) — так, чтобы только ограниченный объём работы был сделан для каждого изменения количества участников.

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

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

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

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

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

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

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

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

Карта сети BitTorrent DHT

И DHT, и PEX фактически выполняют основную функцию BitTorrent-трекера — помогают участникам файлообмена узнать друг о друге. Они могут:

• Помочь участникам быстрее найти друг друга
  Например, на раздаче есть пир X с недоступным портом. К раздаче подключается пир Z, который не может сам начать соединение с X и вынужден ждать, пока Х о нём узнает. Х только что обращался к трекеру и в следующий раз собирается это сделать через час.
  Но вот пир Y в очередной раз обращается к трекеру и узнаёт про нового пира Z. Если при этом Y сам давно уже соединён и занимается файлообменом с X, то он через PEX сообщает X адрес этого нового пира Z. Таких пиров Y на раздаче может быть много. Теперь X может начать соединение с Z, не ожидая очередного запроса к трекеру, что особенно важно, если к тому времени Z отключится. При большой доле приходящих и уходящих раздающих это сокращает ожидание начала загрузки с них.

• Снизить нагрузку на трекер
  Получая адреса пиров через DHT или PEX, клиенты реже обращаются к трекеру, тем самым снижая нагрузку.

• Поддержать раздачу в периоды недоступности трекера
  Если трекер является единственным источником информации о пирах, то при его неработоспособности раздача постепенно остановится. Используя PEX, клиенты могут обмениваться друг с другом информацией о пирах, с которыми у них были сеансы связи, тем самым замедляя процесс остановки раздачи. DHT же позволяет полностью заменить трекер.

• DHT позволяет раздавать без трекера
  Такая раздача называется бестрекерной (trackerless). Торрент для неё создаётся без адреса трекера и клиенты находят друг друга через DHT. Правда, при этом начавший раздачу должен иметь реальный IP-адрес, доступный извне. При участии в trackerless-раздачах BitTorrent-клиенты приобретают определённое сходство с eMule, использующим сеть Kad.

1. Существует несколько несовместимых между собой протоколов, которые обслуживают различные сети.
2. Работа клиента, как DHT-узла, создаёт большую нагрузку на маршрутизатор (роутер).
3. Хеши публикуются открыто, что позволяет интерактивно отслеживать раздачи (чем и пользуются правообладатели).[1][2][3]

• Magnet-ссылка
• Kademlia

• Описание протокола DHT (Перевод) (рус.)
• Описание протокола DHT на сайте BitTorrent.org (англ.)
• в Azureus Wiki (англ.)
• на сайте BitComet (англ.)