Розподілена геш-таблиця

Розподілена хеш-таблиця (англ. Distributed hash table, DHT) — розподілена система що реалізує функції хеш таблиці^[1].

Однією з реалізацій DHT є протокол Kademlia.

Опишемо типову організацію децентралізованої мережі, яка використовує розподілену хеш-таблицю. Кожен учасник мережі під час першого підключення до мережі отримує унікальний номер (ID), що вибирається із певної множини, в деяких реалізаціях це 160-бітове число, яке генерується випадковим чином. Для порівняння двох ID вводиться поняття метрики або відстані. У випадку Kademlia воно обчислюється як виключне «або» двох чисел (XOR). Чим менше значення такої відстані — тим два учасники мережі вважаються ближчими один до одного. Метрика введена таким чином не відображає географічної близькості учасників мережі.

Коли учасник хоче розмістити у мережі деякий ресурс (файл), він обробляє його зміст та обчислює значення хеш-функції, яка буде ідентифікувати ресурс у мережі. Хешувальна функція обирається таким чином, щоб унікальні номери учасників та хеш-функція набували значень з однієї множини. Обрахувавши значення Хеш-функції, учасник намагається відшукати іншого учасника мережі, ID якого близький до знайденого хешу. Знайшовши, розміщувач ресурсу передає знайденому учаснику свою IP-адресу та хеш, які той зберігає у себе.

Таким чином, клієнт мережі, який потім хоче завантажити ресурс, знаючи з деяких джерел його геш, намагається дізнатися відомості про знаходження ресурсу в тих учасників мережі, унікальний номер яких близький до хешу.

Пошук ресурсів за назвами файлів може бути організовано у такий спосіб. Ім'я файлу розбивається на ключові слова, які під час розміщення ресурсу гешуються та зберігаються у мережі разом із назвою файлу та його хешем. Номер учасника на якому ці відомості зберігаються знаходиться аналогічним чином — він має бути якомога ближче до значення хешу відповідного ключового слова. Пошук за іменем файлу відбувається так: за ключовими словами обчислюється їх хеш, та в учасників мережі, які мають ID близькі до цього хешу відшуковується повна назва файлу разом зі значенням хеш-функції.

Історія

Дослідження в області DHT спочатку були мотивовані зокрема піринговими системами, такими, як I2P, Napster, Gnutella, Freenet, які використовували розподілені в інтернеті ресурси для створення одного єдиного додатка. Зокрема вони використовували широкосмуговий інтернет і простір на жорстких дисках для надання сервісу розповсюдження файлів. Ці системи різняться тим, як вони знаходили дані пірів:

Napster мав центральний індексний сервер: кожен вузол, після приєднання, повинен відправити список локально збережених файлів на сервер, який повинен провести пошук і направити запит до вузлів, що містить результати. Цей центральний компонент робив систему вразливою для атак і ризиків.
Gnutella і схожі мережі перейшли до моделі лавинних запитів — в основному, кожен пошук привів би до повідомлення, переданому на будь-яку машину в мережі. Уникаючи єдиної точки відмови, цей метод був значно менш ефективним, ніж Napster.
Нарешті, Freenet був також повністю розподіленим, але маршрутизація працює на базі евристичного ключа, в якому кожен файл має асоційований з ним ключ, а файли з схожими ключами мали тенденцію до об'єднання в кластери на схожому наборі вузлів. Запит, швидше за все, прямував таким кластерам без потреби опитувати всі вузли. Однак Freenet не міг гарантувати, що дані будуть знайдені.

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

Перші чотири DHT — CAN, Chord^[en], Pastry^[en] і Tapestry^[en] — були введені приблизно в 2001 році. З тих пір ця область досліджень була досить активна. Поза науковими колами DHT-технологію прийняли як компонент BitTorrent і Coral Content Distribution Network

Властивості

DHT притаманно наголошувати на таких властивостях:

Децентралізовані обчислення^[en]: Вершини спільно утворюють систему без централізованого узгоджування.
Відмовостійкість: Система має бути надійною (в якомусь сенсі) навіть коли вершини постійно долучаються, покидають і збоять.^[2]
Масштабовність: Система має дієво функціонувати навіть з тисячами або мільйонами вершин.

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