Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Розподілена геш-таблиця (англ. Distributed hash table, DHT) — розподілена система що реалізує функції геш таблиці.
Однією з реалізацій 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, [en], [en] і [en] — були введені приблизно в 2001 році. З тих пір ця область досліджень була досить активна. Поза науковими колами DHT-технологію прийняли як компонент BitTorrent і Coral Content Distribution Network
Властивості
DHT притаманно наголошувати на таких властивостях:
- [en]: Вершини спільно утворюють систему без централізованого узгоджування.
- Відмовостійкість: Система має бути надійною (в якомусь сенсі) навіть коли вершини постійно долучаються, покидають і збоять.
- Масштабовність: Система має дієво функціонувати навіть з тисячами або мільйонами вершин.
Ключовий підхід використовуваний для цього полягає в тому, що кожна вершина потребує координування лише з кількома іншими вершинами — зазвичай, O(log n) з n учасників — таким чином, для кожної зміни в членстві, потрібно виконати лише обмежений обсяг роботи.
Див. також
- Список структур даних
- YaCy — відкритоджерельна пошукова машина на основі DHT
Зноски
- Distributed Hash Tables, Part I. Linux Journal. Процитовано 27 березня 2024.
- 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.]
 | Це незавершена стаття про Інтернет. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Rozpodilena gesh tablicya angl Distributed hash table DHT rozpodilena sistema sho realizuye funkciyi gesh tablici Odniyeyu z realizacij DHT ye protokol Kademlia Opishemo tipovu organizaciyu decentralizovanoyi merezhi yaka vikoristovuye rozpodilenu gesh tablicyu Kozhen uchasnik merezhi pid chas pershogo pidklyuchennya do merezhi otrimuye unikalnij nomer ID sho vibirayetsya iz pevnoyi mnozhini v deyakih realizaciyah ce 160 bitove chislo yake generuyetsya vipadkovim chinom Dlya porivnyannya dvoh ID vvoditsya ponyattya metriki abo vidstani U vipadku Kademlia vono obchislyuyetsya yak viklyuchne abo dvoh chisel XOR Chim menshe znachennya takoyi vidstani tim dva uchasniki merezhi vvazhayutsya blizhchimi odin do odnogo Metrika vvedena takim chinom ne vidobrazhaye geografichnoyi blizkosti uchasnikiv merezhi Koli uchasnik hoche rozmistiti u merezhi deyakij resurs fajl vin obroblyaye jogo zmist ta obchislyuye znachennya gesh funkciyi yaka bude identifikuvati resurs u merezhi Geshuvalna funkciya obirayetsya takim chinom shob unikalni nomeri uchasnikiv ta gesh funkciya nabuvali znachen z odniyeyi mnozhini Obrahuvavshi znachennya gesh funkciyi uchasnik namagayetsya vidshukati inshogo uchasnika merezhi ID yakogo blizkij do znajdenogo geshu Znajshovshi rozmishuvach resursu peredaye znajdenomu uchasniku svoyu IP adresu ta gesh yaki toj zberigaye u sebe Takim chinom kliyent merezhi yakij potim hoche zavantazhiti resurs znayuchi z deyakih dzherel jogo gesh namagayetsya diznatisya vidomosti pro znahodzhennya resursu v tih uchasnikiv merezhi unikalnij nomer yakih blizkij do geshu Poshuk resursiv za nazvami fajliv mozhe buti organizovano u takij sposib Im ya fajlu rozbivayetsya na klyuchovi slova yaki pid chas rozmishennya resursu geshuyutsya ta zberigayutsya u merezhi razom iz nazvoyu fajlu ta jogo geshem Nomer uchasnika na yakomu ci vidomosti zberigayutsya znahoditsya analogichnim chinom vin maye buti yakomoga blizhche do znachennya geshu vidpovidnogo klyuchovogo slova Poshuk za imenem fajlu vidbuvayetsya tak za klyuchovimi slovami obchislyuyetsya yih gesh ta v uchasnikiv merezhi yaki mayut ID blizki do cogo heshu vidshukovuyetsya povna nazva fajlu razom zi znachennyam gesh funkciyi IstoriyaDoslidzhennya v oblasti DHT spochatku buli motivovani zokrema piringovimi sistemami takimi yak I2P Napster Gnutella Freenet yaki vikoristovuvali rozpodileni v interneti resursi dlya stvorennya odnogo yedinogo dodatka Zokrema voni vikoristovuvali shirokosmugovij internet i prostir na zhorstkih diskah dlya nadannya servisu rozpovsyudzhennya fajliv Ci sistemi riznyatsya tim yak voni znahodili dani piriv Napster mav centralnij indeksnij server kozhen vuzol pislya priyednannya povinen vidpraviti spisok lokalno zberezhenih fajliv na server yakij povinen provesti poshuk i napraviti zapit do vuzliv sho mistit rezultati Cej centralnij komponent robiv sistemu vrazlivoyu dlya atak i rizikiv Gnutella i shozhi merezhi perejshli do modeli lavinnih zapitiv v osnovnomu kozhen poshuk priviv bi do povidomlennya peredanomu na bud yaku mashinu v merezhi Unikayuchi yedinoyi tochki vidmovi cej metod buv znachno mensh efektivnim nizh Napster Nareshti Freenet buv takozh povnistyu rozpodilenim ale marshrutizaciya pracyuye na bazi evristichnogo klyucha v yakomu kozhen fajl maye asocijovanij z nim klyuch a fajli z shozhimi klyuchami mali tendenciyu do ob yednannya v klasteri na shozhomu nabori vuzliv Zapit shvidshe za vse pryamuvav takim klasteram bez potrebi opituvati vsi vuzli Odnak Freenet ne mig garantuvati sho dani budut znajdeni DHT vikoristovuyut marshrutizaciyu na bazi bilsh strukturovanogo klyucha shob dosyagti decentralizaciyi I2P Gnutella i Freenet a takozh efektivnosti i garantovanih rezultativ Napster Odin z nedolikiv v tomu sho yak Freenet DHT pidtrimuye tilki poshuk po tochnomu zbigu a ne za klyuchovimi slovami hocha ci mozhlivosti mozhut nasharovuvatisya poverh DHT Pershi chotiri DHT CAN en en i en buli vvedeni priblizno v 2001 roci Z tih pir cya oblast doslidzhen bula dosit aktivna Poza naukovimi kolami DHT tehnologiyu prijnyali yak komponent BitTorrent i Coral Content Distribution NetworkVlastivostiDHT pritamanno nagoloshuvati na takih vlastivostyah en Vershini spilno utvoryuyut sistemu bez centralizovanogo uzgodzhuvannya Vidmovostijkist Sistema maye buti nadijnoyu v yakomus sensi navit koli vershini postijno doluchayutsya pokidayut i zboyat Masshtabovnist Sistema maye diyevo funkcionuvati navit z tisyachami abo miljonami vershin Klyuchovij pidhid vikoristovuvanij dlya cogo polyagaye v tomu sho kozhna vershina potrebuye koordinuvannya lishe z kilkoma inshimi vershinami zazvichaj O log n z n uchasnikiv takim chinom dlya kozhnoyi zmini v chlenstvi potribno vikonati lishe obmezhenij obsyag roboti Div takozhSpisok struktur danih YaCy vidkritodzherelna poshukova mashina na osnovi DHTZnoskiDistributed Hash Tables Part I Linux Journal Procitovano 27 bereznya 2024 R Mokadem A Hameurlain and AM Tjoa Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems Proc iiWas 2010PosilannyaDHT Protocol 13 lyutogo 2010 u Wayback Machine Ce nezavershena stattya pro Internet Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi