Distribuovaná hashovací tabulka

DHT ( anglicky  d istributed hash table -  „distribuovaná hashovací tabulka “) je třída decentralizovaných systémů distribuovaných vyhledávacích služeb, které fungují jako hashovací tabulka. Jako datová struktura může být hashovací tabulka asociativní pole obsahující páry ( klíč – hodnota ). Termín DHT je také spojen s řadou principů a algoritmů , které vám umožňují zaznamenávat data, distribuovat informace mezi určitou sadu uzlů úložiště a obnovovat je distribuovaným vyhledáváním podle klíče. Rysem distribuované tabulky je schopnost distribuovat informace mezi sadu uzlů úložiště takovým způsobem, že každý zúčastněný uzel může najít hodnotu spojenou s daným klíčem. Odpovědnost za udržování vztahu mezi jménem a hodnotou je rozdělena mezi uzly, přičemž změna sady členů způsobuje minimální počet přerušení. To vám umožní snadno škálovat DHT a také neustále sledovat přidávání a odstraňování uzlů a chyb v jejich práci.

DHT je rámec, který lze použít k vytvoření mnoha komplexních služeb, jako jsou distribuované systémy souborů , distribuce souborů typu peer-to-peer a sítě pro doručování obsahu , kooperativní webová mezipaměť, multicast , anycast , služba názvů domén a rychlé zasílání zpráv . Hlavní distribuované sítě, které používají DHT: I2P síť , BitTorrent , eDonkey síť ( Kad Network ) , YaCy , Tox a Coral Content Distribution Network . Přes síť DHT je možné vytvářet vyhledávače .

Historie

Výzkum DHT byl zpočátku motivován zejména peer-to-peer systémy jako I2P , Napster , Gnutella , Freenet , které využívaly zdroje distribuované přes internet k vytvoření jediné aplikace. Zejména využívali širokopásmový internet a místo na pevném disku k poskytování služby distribuce souborů.

Tyto systémy se liší v tom, jak nalezly data kolegů:

• Napster měl centrální indexový server: každý uzel po připojení musí poslat seznam lokálně uložených souborů na server, který musí prohledávat a dotazovat se na uzly obsahující výsledky. Tato centrální součást učinila systém zranitelným vůči útokům a rizikům.
• Gnutella a podobné sítě se posunuly k modelu záplavových požadavků – v podstatě by každé vyhledávání vedlo k odeslání zprávy všem strojům v síti. I když se tato metoda vyhnula centralizovanému selhání, byla výrazně méně účinná než Napster .
• Konečně, Freenet byl také kompletně distribuován, ale směrování je založeno na heuristickém klíči, ve kterém má každý soubor přiřazený klíč a soubory s podobnými klíči mají tendenci se shlukovat na podobné sadě uzlů. Požadavek byl s největší pravděpodobností odeslán do takových clusterů, aniž by bylo nutné dotazovat všechny peery. Freenet však nemohl zaručit, že data budou nalezena.

DHT používají strukturovanější směrování klíčů k dosažení decentralizace I2P , Gnutella a Freenetu a účinnosti a zaručených výsledků Napsteru . Jednou nevýhodou je, že stejně jako Freenet podporuje DHT pouze vyhledávání v přesné shodě a nikoli vyhledávání podle klíčových slov, i když tyto funkce lze navrstvit na DHT.

První čtyři DHT – CAN , Chord , Pastry a Tapestry – byly představeny kolem roku 2001 .  Od té doby je tato oblast výzkumu poměrně aktivní. Mimo akademickou sféru byla technologie DHT přijata jako součást BitTorrentu a Coral Content Distribution Network .

Vlastnosti

DHT se vyznačuje následujícími vlastnostmi:

• Decentralizace : forma systému kolektivních uzlů bez koordinace;
• Škálovatelnost : systém bude fungovat stejně efektivně s tisíci nebo miliony uzlů;
• Odolnost proti chybám : Systém bude stejně spolehlivý (v určitém smyslu) s uzly, které se neustále připojují, odpojují a vyvolávají chyby.

Klíčovou technikou pro dosažení tohoto cíle je, že každý uzel by se měl koordinovat pouze s několika uzly v systému – typicky O(log n ), kde n  je počet účastníků (viz níže) – takže je potřeba jen omezené množství práce. provedené při každé změně počtu účastníků.

Některé projekty DHT se snaží poskytovat ochranu před uživateli se zlými úmysly a umožňují účastníkům zůstat v anonymitě, i když je to méně běžné než v mnoha jiných systémech P2P (zejména při sdílení souborů); viz Anonymní sítě .

A konečně, DHT se musí vypořádat s tradičnějšími problémy distribuovaného systému, jako je vyvažování zátěže, integrita dat a výkon (zejména zajištění rychlého dokončení operací, jako je směrování a ukládání dat nebo vyhledávání).

Struktura

Strukturu DHT lze rozdělit na několik hlavních složek. Je založen na abstraktním klíčovém prostoru, jako je sada 160bitových řetězců (počet bitů se může lišit). Schéma rozdělení prostoru klíčů rozděluje vlastnictví klíče mezi zúčastněné uzly. Překryvná síť pak propojí uzly a pomůže najít vlastníka jakéhokoli klíče v prostoru klíčů.

Se všemi komponentami na místě je typické použití DHT pro ukládání a zobrazování informací následovně: předpokládejme, že klíčový prostor je 160bitové řetězce. Pro uložení souboru s daným jménem a informacemi do DHT je z názvu souboru nalezen hash SHA1 (160bitová hodnota) , ze kterého se vytvoří 160bitový klíč k (hash), po kterém se vytvoří zpráva. put(k, data), где data - содержание самого файлаa odeslány do kteréhokoli zúčastněného uzlu v DHT. Zpráva prochází z jednoho uzlu do druhého přes překryvnou síť, dokud nedosáhne jediného uzlu zodpovědného za klíč k, v souladu se schématem rozdělení prostoru klíčů, kde bude pár (k, data) uložen. Jakýkoli jiný klient může získat obsah souboru vytvořením klíče (k), tj. získáním hash názvu souboru , aby našel data spojená s klíčem odesláním zprávy get(k). Zpráva opět projde přes překrytí do uzlu odpovědného za klíč, který odpoví, že požadovaná data jsou k dispozici.

Komponenty dělení klíčového prostoru a překryvné síťové komponenty jsou popsány níže, aby představily základní myšlenky společné pro většinu systémů DHT. Mnoho vývojů se v detailech liší.

Rozdělení klíčového prostoru

Většina DHT používá různé varianty konzistentního hashování k mapování klíčů na uzly. Srdcem této metody rozdělení je funkce , která definuje abstraktní pojem vzdálenosti mezi klávesami a , která nemá nic společného s geografickou vzdáleností nebo zpožděním sítě. Každému uzlu je přiřazen jeden klíč, nazývaný jeho identifikátor (ID). Uzel s ID vlastní všechny klíče , pro které  je nejbližší ID vypočteno pomocí .

Příklad. Chord DHT zachází s klávesami jako s body na kruhu a  je to vzdálenost ujetá ve směru hodinových ručiček kolem kruhu od klávesy k . Kruh klíčového prostoru je tedy rozdělen na souvislé segmenty, jejichž konce jsou identifikátory uzlů. Pokud a jsou sousední ID, pak uzel s ID obsahuje všechny klíče mezi a .

Konzistentní hašování má hlavní vlastnost, že odstranění nebo přidání pouze jedné sady klíčů patřících uzlům sousedních ID neovlivní ostatní uzly.

DHT a BitTorrent

DHT i PEX ve skutečnosti plní hlavní funkci BitTorrent trackeru  – pomáhají účastníkům sdílení souborů dozvědět se o sobě navzájem. Oni mohou:

• Pomozte účastníkům najít se rychleji
  V distribuci je například partner X s nedostupným portem. Peer Z se připojí k distribuci, která sama nedokáže navázat spojení s X a musí čekat, až se o tom X dozví. X právě přistoupil k trackeru a udělá tak za hodinu.
  Ale partner Y se znovu obrátí na sledovač a dozví se o novém peer Z. Pokud je zároveň Y sám již dlouho připojen a je zapojen do sdílení souborů s X, pak sdělí X adresu tohoto nového peer Z prostřednictvím PEX Těchto vrstevníků Y může být v distribuci hodně. Nyní může X zahájit spojení se Z bez čekání na další požadavek na tracker, což je zvláště důležité, pokud je Z do té doby odpojeno. S velkým podílem příchozích a odchozích distributorů se tak zkracuje čekání, než začnou stahovat.

• Snížení zátěže trackeru
  Získáním peer adres přes DHT nebo PEX klienti přistupují k trackeru méně často, čímž se sníží zatížení.

• Podpora distribuce během období nedostupnosti trackeru
  Pokud je tracker jediným zdrojem informací o peerech, pak se distribuce postupně zastaví, pokud je nefunkční. Pomocí PEX si klienti mohou mezi sebou vyměňovat informace o peerech, se kterými měli komunikační relace, čímž zpomalují proces zastavení distribuce. DHT umožňuje zcela nahradit sledovač.

• DHT umožňuje distribuci bez trackeru
  Taková distribuce se nazývá trackerless ( trackerless ). Torrent pro něj je vytvořen bez adresy trackeru a klienti se navzájem najdou přes DHT. Pravda, zároveň ten, kdo distribuci spustil, musí mít skutečnou IP adresu, která je přístupná zvenčí. Při účasti na distribucích bez sledování mají klienti BitTorrent určitou podobnost s eMule pomocí sítě Kad .

Soukromý klíč

Ve veřejných (otevřených) trackerech, kde si kdokoli může stáhnout torrent a podílet se na distribuci, slouží DHT a PEX ve prospěch všech účastníků.

U soukromých (uzavřených) trackerů je především důležité, aby se distribuce mohli účastnit pouze registrovaní uživatelé a dodržovali určitá pravidla. Na první žádost klienta má soukromý tracker možnost zabránit jeho distribuci, aniž by mu sdělil adresy ostatních zúčastněných klientů. Proto je pro soukromý tracker důležité, aby klienti tyto adresy nedostávali přes DHT/PEX.

DHT a PEX se objevily v klientech Azureus a BitComet kolem léta 2005. Správci mnoha soukromých trackerů nebyli s touto novou funkcí spokojeni, a proto začali tyto nové klientské verze na trackeru zakazovat.

Poté vývojáři klientů navrhli nový klíč uvnitř souboru torrent: private . Pokud se rovná 1, pak je klient povinen automaticky zakázat DHT / PEX pro tento torrent, bez ohledu na přání uživatele. Takový torrent se nazývá Secure Torrent.

Téměř všechny moderní soukromé trackery samy o sobě prosazují private:1 ve všech torrentech zveřejněných na trackeru a také zakazují několik zastaralých verzí klientů, kteří podporují DHT nebo PEX, ale ještě nevědí o soukromém klíči . Předpokládá se, že uživatelé sledovačů jednoduše nemohou používat DHT / PEX na distribucích a není problém. Ve skutečnosti, aby nebylo zohledněno hodnocení, stačí nahradit váš přístupový klíč jakýmkoli jiným. A ani ho nemusíte krást. Stačí si zaregistrovat jiný účet, abyste si z něj vzali přístupový klíč.

DHT a statistika

Tato část se vztahuje pouze na soukromé trackery, kde soukromý klíč není vnucován do torrentů , a na některých distribucích (v závislosti na tom, zda distributor sám vložil soukromý klíč do torrentu ) lze použít DHT a PEX.

Často existuje názor, že DHT povolené v klientovi ovlivňuje sledování klientských statistik trackerem, například „distribuováno přes DHT, takže statistiky prošly kolem trackeru“. To není pravda.

Za prvé, DHT/PEX se používá pouze k získání partnerských adres. Sdílení souborů ani jejich statistiky nejsou vedeny. Klient hlásí statistiky stažených a nahraných dat pouze do trackeru.

To znamená, že „distribuováno prostřednictvím DHT“ ve skutečnosti znamená „Dostal jsem informace o některých (nebo všech) peerech prostřednictvím DHT a pravděpodobně mě někteří kolegové také našli prostřednictvím DHT.

Zadruhé, ačkoli klienti obvykle vědí, odkud získali své partnerské adresy, žádný klient nerozděluje provoz na „přijato/odesláno účastníkům DHT“ a „přijato/odesláno kolegům přijatým ze sledovače“. I v případě potřeby by to pro klienta bylo obtížné - některé peery mohou být přijímány jak z trackeru, tak přes DHT nebo PEX a klient často neví, jak peer, který s ním zahajuje spojení, získal svou adresu.

Klient hlásí trackeru celková data o stažených objemech a poskytnutých všem peerům, se kterými komunikoval , bez ohledu na to, zda se klient o jednotlivých peerech dozvěděl přes tracker, DHT nebo PEX, nebo zda tento peer dokonce sám zahájil připojení. . To znamená, že i když se na distribuci objeví „leví“ uživatelé (kteří nemají přístup k trackeru) kvůli DHT / PEX, klient bude stále hlásit trackeru vše, co si stáhli a rozdali.

Správné účtování statistik závisí pouze na stavu trackeru: tracker funguje - statistiky se berou v úvahu, pokud nefunguje - nebere se v úvahu. Pouze v případě dlouhodobě nefunkčního trackeru může hrát DHT / PEX nepřímou roli, která zabraňuje postupnému vymírání sdílení souborů na takové „distribuci bez zohlednění statistik“.

Jak DHT funguje

Implementace distribuované sítě v klientech BitTorrent je založena na variantě DHT nazvané Kademlia . Obecně lze říci, že DHT (Distributed hash table) znamená decentralizovaný distribuovaný systém pro kombinování velkého množství neustále mizejících a objevujících se uzlů a efektivní přenos zpráv mezi nimi. Na základě struktur DHT jsou postaveny různé složitější systémy, jako je sdílení souborů P2P , kooperativní ukládání do mezipaměti webu, služby DNS atd.

DHT používá protokol UDP . Klienti BitTorrent „poslouchají“ na stejném čísle portu UDP, které používají pro příchozí TCP spojení. Pokud aktivně používáte DHT, pak je otevření tohoto UDP portu pro přístup zvenčí žádoucí, ale není nutné - DHT tak bude fungovat.

Každý připojený klient je samostatným uzlem v síti DHT. Má své vlastní jedinečné ID (identifikátor), náhodně vybrané ze stejného 160bitového prostoru jako infohash'a torrenty.

Každý uzel udržuje směrovací tabulku obsahující kontaktní informace pro mnoho „nejbližších“ uzlů a pro několik vzdálenějších. „Blízkost“ dvou uzlů se vypočítává z „podobnosti“ jejich ID a nemá nic společného s jejich geografickou blízkostí.

Když chce uzel najít partnery pro distribuci, porovnává infohash této distribuce s ID uzlů, které zná, a pak odešle požadavek na uzel, jehož ID je tomuto infohash nejpodobnější. Tento uzel mu vrátí adresu uzlu, jehož ID je ještě blíže infohash torrentu.

Poté náš uzel odešle požadavek tomuto novému uzlu a obdrží od něj adresu dalšího uzlu, jehož ID je ještě více podobné infohash torrentu.

Požadavky od klientů podílejících se na distribuci torrentu s konkrétním infohash tak postupně proudí do uzlů, jejichž ID jsou tomuto infohashe nejpodobnější. Tyto uzly si pamatují předchozí požadavky a všem následujícím žádajícím uzlům budou vráceny adresy předchozích kolegů ze stejné distribuce.

Nevýhody

1. Existuje několik nekompatibilních protokolů, které obsluhují různé sítě.
2. Provoz klienta jako DHT uzlu vytváří velké zatížení routeru (routeru).
3. Hashe jsou zveřejňovány otevřeně, což umožňuje interaktivní sledování distribucí (což používají držitelé autorských práv). [1] [2] [3]

Související články

• Magnetický odkaz
• Kademlia

Poznámky

1. ↑ Výzkumníci špehují uživatele BitTorrentu v reálném čase . Získáno 30. září 2017. Archivováno z originálu 21. srpna 2017. (neurčitý)
2. ↑ Protokol DHT . Získáno 29. května 2010. Archivováno z originálu 20. května 2015. (neurčitý)
3. ↑ Rozšíření pro Peers pro odesílání souborů metadat . Datum přístupu: 29. května 2010. Archivováno z originálu 10. května 2016. (neurčitý)

Odkazy

• Popis protokolu DHT (překlad)  (ruština)
• Popis protokolu DHT na BitTorrent.org 
•  na Azureus Wiki
• na  webu BitComet