Технологии / Распределённые хэш-таблицы

DHT (distributed hash table) — класс децентрализованных распределённых систем для реализации поисковой службы, работающей подобно хэш-таблице. Как структура данных, хэш-таблица может представлять собой ассоциативный массив, содержащий пары (ключ-значение). C термином DHT связан ряд принципов и алгоритмов, позволяющих записывать данные, распределяя информацию среди некоторого набора узлов-хранителей, и восстанавливать их, путём распределённого поиска по ключу. Особенностью распределённой таблицы является возможность распределить информацию среди некоторого набора узлов-хранителей таким образом, что каждый участвующий узел может найти значение, ассоциированное с данным ключом. Ответственность за поддержание связи между именем и значением распределяется между узлами, в силу чего изменение набора участников является причиной минимального количества разрывов. Это позволяет легко масштабировать DHT, а также постоянно отслеживать добавление и удаление узлов и ошибки в их работе.DHT — это инфраструктура, которая может быть использована для построения многих сложных служб, таких как распределённые файловые системы, пиринговое распространение файлов и сети доставки содержимого, кооперативный web-кэш, многоадресное вещание (multicast), anycast, служба доменных имен и система мгновенных сообщений. Существует возможность создания поисковых машин по сети DHT.

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

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

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

Некоторые алгоритмы реализующие DHT:

CAN
Chord
Pastry
Tapestry

Применение:

I2P
BitTorrent
eDonkey network (Kad Network)
YaCy
Tox
Coral Content Distribution Network