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

Розподілена геш-таблиця (англ. 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 учасників — таким чином, для кожної зміни в членстві, потрібно виконати лише обмежений обсяг роботи.

• Список структур даних
• YaCy — відкритоджерельна пошукова машина на основі DHT

1. ↑ Distributed Hash Tables, Part I. Linux Journal. Процитовано 27 березня 2024.
2. ↑ R Mokadem, A Hameurlain and AM Tjoa. Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems. Proc. iiWas, 2010

• DHT Protocol [Архівовано 13 лютого 2010 у Wayback Machine.]

Це незавершена стаття про Інтернет. Ви можете допомогти проєкту, виправивши або дописавши її.