www.wikidata.uk-ua.nina.az

Розподілена геш таблиця Ця стаття не містить посилань на джерела Ви можете допомогти поліпшити цю статтю додавши посилан

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

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (січень 2023)

Розподілена геш-таблиця (англ. 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

Властивості Редагувати

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

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

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

Див. також Редагувати

Посилання Редагувати


Це незавершена стаття про Інтернет.
Ви можете допомогти проєкту, виправивши або дописавши її.
  1. R Mokadem, A Hameurlain and AM Tjoa. Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems. Proc. iiWas, 2010
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno sichen 2023 Rozpodilena gesh tablicya angl Distributed hash table DHT protokol peredachi danih ta mehanizm zberezhennya informaciyi pro resursi decentralizovano bez vidilenogo servera bezposeredno na kliyentah uchasnikiv fajloobminnoyi merezhi tipu peer to peer 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 Zmist 1 Istoriya 2 Vlastivosti 3 Div takozh 4 PosilannyaIstoriya RedaguvatiDoslidzhennya 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 Chord Pastry i Tapestry 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 NetworkVlastivosti RedaguvatiDHT pritamanno nagoloshuvati na takih vlastivostyah Decentralizovani obchislennya en Vershini spilno utvoryuyut sistemu bez centralizovanogo uzgodzhuvannya Vidmovostijkist Sistema maye buti nadijnoyu v yakomus sensi navit koli vershini postijno doluchayutsya pokidayut i zboyat 1 Masshtabovnist Sistema maye diyevo funkcionuvati navit z tisyachma oba 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 takozh RedaguvatiSpisok struktur danih YaCy vidkritodzherelna poshukova mashina na osnovi DHTPosilannya RedaguvatiDHT Protocol Arhivovano 13 lyutogo 2010 u Wayback Machine nbsp Ce nezavershena stattya pro Internet Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi R Mokadem A Hameurlain and AM Tjoa Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems Proc iiWas 2010 Otrimano z https uk wikipedia org w index php title Rozpodilena gesh tablicya amp oldid 38071701