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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Розподілена хеш-таблиця (англ. Distributed hash table, DHT) — протокол передачі даних та механізм збереження інформації про ресурси та учасників файлообмінної мережі типу peer-to-peer децентралізовано (без виділеного сервера), безпосередньо на клієнтах мережі.

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

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

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

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

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]


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

Вставляйте сюди невідформатований текст.