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

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

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

Однією з реалізацій 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, Pastry і Tapestry[en] - були введені приблизно в 2001 році. З тих пір ця область досліджень була досить активна. Поза науковими колами DHT технологію-прийняли як компонент BitTorrent і Coral Content Distribution Network

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

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


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