Elosztott hash táblázat

A DHT ( eng.  d istributed h ash t table  – „distributed hash table ”) a decentralizált elosztott keresőszolgáltatási rendszerek egy osztálya, amelyek hash-táblázatként működnek. Adatstruktúraként a hash tábla lehet egy ( kulcs-érték ) párokat tartalmazó asszociatív tömb . Ezenkívül a DHT kifejezés számos alapelvhez és algoritmushoz kapcsolódik , amelyek lehetővé teszik az adatok rögzítését, az információk elosztását a tárolócsomópontok bizonyos készletei között, és visszaállítását kulcsonkénti elosztott kereséssel. Az elosztott tábla egyik jellemzője, hogy képes információkat osztani a tárolási csomópontok között oly módon, hogy minden résztvevő csomópont megtalálja az adott kulcshoz tartozó értéket. A név és az érték közötti kapcsolat fenntartásának felelőssége megoszlik a csomópontok között, így a tagkészlet megváltoztatása minimális számú törést okoz. Ez lehetővé teszi a DHT könnyű méretezését, valamint a csomópontok hozzáadásának és eltávolításának, valamint a munkájuk során felmerülő hibák folyamatos figyelését.

A DHT egy olyan keretrendszer, amely számos összetett szolgáltatás, például elosztott fájlrendszerek , peer-to-peer fájlelosztó és tartalomszolgáltató hálózatok , kooperatív web-gyorsítótár, multicast , anycast , tartománynév-szolgáltatás és azonnali üzenetküldés létrehozására használható . Főbb elosztott hálózatok, amelyek DHT-t használnak: I2P hálózat , BitTorrent , eDonkey hálózat ( Kad Network ) , YaCy , Tox és Coral tartalomelosztó hálózat . Lehetőség van keresőmotorok létrehozására a DHT hálózaton keresztül.

Történelem

A DHT-kutatást kezdetben különösen az olyan peer-to-peer rendszerek motiválták, mint az I2P , Napster , Gnutella , Freenet , amelyek az interneten elosztott erőforrásokat használták fel egyetlen alkalmazás létrehozására. Különösen a szélessávú internetet és a merevlemez-területet használták fel fájlterjesztési szolgáltatás biztosítására.

Ezek a rendszerek abban különböznek egymástól, hogy hogyan találták meg a társadatokat:

• A Napster központi indexszerverrel rendelkezett: minden csomópontnak a csatlakozás után el kell küldenie a helyileg tárolt fájlok listáját a szervernek, amelynek meg kell keresnie és le kell kérdeznie az eredményeket tartalmazó csomópontokat. Ez a központi komponens sebezhetővé tette a rendszert támadásokkal és kockázatokkal szemben.
• A Gnutella és a hasonló hálózatok elmozdultak az elárasztási kérés modelljére – alapvetően minden keresés azt eredményezné, hogy üzenetet küldenek a hálózat összes gépére. A központosított meghibásodás elkerülése mellett ez a módszer lényegesen kevésbé volt hatékony, mint a Napster .
• Végül a Freenet is teljesen terjesztett, de az útválasztás egy heurisztikus kulcson alapul, amelyben minden fájlhoz tartozik egy kulcs, és a hasonló kulcsokkal rendelkező fájlok hasonló csomópontokba csoportosulnak. A kérést nagy valószínűséggel az ilyen fürtökhöz küldték el anélkül, hogy le kellett volna kérni az összes társat. A Freenet azonban nem tudta garantálni, hogy az adatokat megtalálják.

A DHT-k strukturáltabb kulcsútválasztást használnak az I2P , a Gnutella és a Freenet decentralizálása , valamint a Napster hatékonyságának és garantált eredményeinek elérése érdekében . Az egyik hátránya az, hogy a Freenethez hasonlóan a DHT is csak a pontos egyezésű keresést támogatja, a kulcsszavas keresést nem, bár ezek a funkciók a DHT tetejére rétegezhetők.

Az első négy DHT -t – CAN , Chord , Pastry és Tapestry – 2001 körül mutatták be .  Azóta ez a kutatási terület meglehetősen aktív. A tudományos körökön kívül a DHT technológiát a BitTorrent és a Coral Content Distribution Network összetevőjeként fogadták el .

Tulajdonságok

A DHT-t a következő tulajdonságok jellemzik:

• Decentralizáció : a kollektív csomópontrendszer koordináció nélküli formája;
• Skálázhatóság : a rendszer egyformán hatékonyan működik több ezer vagy millió csomóponttal;
• Hibatűrés : A rendszer ugyanolyan megbízható lesz (bizonyos értelemben), ha a csomópontok folyamatosan kapcsolódnak, lekapcsolnak és hibákat dobnak.

A cél elérésének egyik kulcsfontosságú technikája az, hogy bármely csomópont csak néhány csomóponttal koordináljon a rendszerben – jellemzően O(log n ), ahol n  a résztvevők száma (lásd alább) –, így csak korlátozott mennyiségű munka szükséges. a résztvevők számának minden változásához.

Egyes DHT-projektek védelmet kívánnak nyújtani a rosszindulatú felhasználókkal szemben, és lehetővé teszik a résztvevők névtelenségének megőrzését, bár ez kevésbé gyakori, mint sok más P2P rendszerben (különösen fájlok megosztása esetén); lásd: Névtelen hálózatok .

Végül a DHT-nak meg kell küzdenie a hagyományos elosztott rendszerekkel kapcsolatos problémákkal, mint például a terheléselosztás, az adatok integritása és a teljesítmény (különösen annak biztosítása, hogy az olyan műveletek, mint az útválasztás és az adattárolás vagy a keresések gyorsan befejeződjenek).

Szerkezet

A DHT szerkezete több fő összetevőre bontható. Absztrakt kulcstéren, például 160 bites karakterláncokon alapul (a bitek száma változhat). A kulcstér-particionálási séma elosztja a kulcstulajdonjogot a részt vevő csomópontok között. Az átfedő hálózat ezután összeköti a csomópontokat, és segít megtalálni a kulcstérben lévő bármely kulcs tulajdonosát.

Ha az összes összetevő a helyén van, a DHT tipikus felhasználása információk tárolására és megjelenítésére a következő: tegyük fel, hogy a kulcstér 160 bites karakterlánc. A megadott névvel és információval rendelkező fájl DHT-ban való tárolásához a fájlnévből egy SHA1 hash (160 bites érték) található , amelyből egy 160 bites k kulcs (hash) keletkezik, amely után üzenet jön létre. put(k, data), где data - содержание самого файлаés elküldjük a DHT bármely résztvevő csomópontjához. Az üzenet az átfedő hálózaton keresztül megy egyik csomóponttól a másikig, amíg el nem éri az egyetlen, a k kulcsért felelős csomópontot a kulcstér-particionálási séma szerint, ahol a (k, adatok) pár tárolódik. Bármely más kliens hozzáférhet a fájl tartalmához egy kulcs (k) létrehozásával, azaz a fájlnév hash-jének lekérésével , hogy üzenet küldésével megtalálja a kulcshoz tartozó adatokat get(k). Az üzenet ismét átmegy a fedvényen a kulcsért felelős csomóponthoz, amely azt válaszolja, hogy a szükséges adatok rendelkezésre állnak.

Az alábbiakban ismertetjük a kulcstér-particionálást és az átfedő hálózati összetevőket, hogy bemutassuk a legtöbb DHT-rendszerre jellemző alapötleteket. Sok fejlesztés részleteiben különbözik.

Keyspace particionálás

A legtöbb DHT a konzisztens kivonatolás különféle változatait használja a kulcsok csomópontokhoz való leképezésére. Ennek a particionálási módszernek a középpontjában a függvény áll , amely meghatározza a és a kulcsok közötti távolság elvont fogalmát , amelynek semmi köze a földrajzi távolsághoz vagy a hálózati késleltetéshez. Minden csomóponthoz egyetlen kulcs van hozzárendelve, amelyet azonosítójának (ID) neveznek. Az azonosítóval rendelkező csomópont birtokolja az összes olyan kulcsot , amelyhez  a legközelebbi azonosító tartozik a segítségével .

Példa. A Chord DHT a billentyűket kör pontjaiként kezeli, és  az óramutató járásával megegyező irányban megtett távolság a körön a kulcstól a -ig . Így a kulcstér kör összefüggő szegmensekre oszlik, amelyek végei csomópontazonosítók. Ha a és szomszédos azonosítók, akkor az azonosítóval rendelkező csomópont tartalmazza az és közötti összes kulcsot .

A konzisztens kivonatolás fő tulajdonsága, hogy a szomszédos azonosítók csomópontjaihoz tartozó kulcsok egyetlen készletének törlése vagy hozzáadása nincs hatással a többi csomópontra.

DHT és BitTorrent

Mind a DHT, mind a PEX valójában a BitTorrent nyomkövető fő funkcióját tölti  be – segítenek a fájlmegosztó résztvevőknek egymás megismerésében. Ők tudnak:

• Segítsen a résztvevőknek, hogy gyorsabban megtalálják egymást . Például van egy peer
  X a disztribúción , amelynek portja nem elérhető. Z peer csatlakozik a disztribúcióhoz, amely maga nem tud kapcsolatot létesíteni X-szel, és meg kell várnia, amíg X megtudja ezt. X éppen elérte a nyomkövetőt, és legközelebb egy óra múlva fogja megtenni. De Y partner ismét a nyomkövetőhöz fordul, és megismeri az új Z peer-t. Ha ugyanakkor Y maga is régóta kapcsolatban van, és fájlmegosztást folytat X-szel, akkor a PEX -en keresztül közli X-vel ennek az új Z társnak a címét. Sok ilyen Y társ lehet a terjesztésben. Mostantól X tud kapcsolatot létesíteni Z-vel anélkül, hogy megvárná a következő kérést a nyomkövetőnek, ami különösen fontos, ha Z addigra megszakad. A bejövő és kimenő terjesztők nagy aránya miatt ez csökkenti a várakozási időt a letöltés megkezdésére.
  

• Csökkentse a nyomkövető terhelését
  A DHT-n vagy PEX-en keresztüli társcímek megszerzésével a kliensek ritkábban érik el a nyomkövetőt, ezáltal csökkentve a terhelést.

• Támogassa a terjesztést a nyomkövető nem elérhető időszakaiban
  Ha a nyomkövető az egyetlen információforrás a társakról, akkor a terjesztés fokozatosan leáll, ha nem működik. A PEX segítségével az ügyfelek információkat cserélhetnek egymással azokról a partnerekről, amelyekkel kommunikációs munkameneteket folytattak, ezáltal lelassíthatják a terjesztés leállításának folyamatát. A DHT lehetővé teszi a nyomkövető teljes cseréjét.

• A DHT lehetővé teszi a nyomkövető nélküli
  terjesztést. Az ilyen terjesztést trackerlessnek ( trackerless ) hívják. Torrent jön létre hozzá tracker cím nélkül, és a kliensek DHT-n keresztül találják meg egymást. Igaz, ugyanakkor a terjesztést elindító személynek valódi, kívülről elérhető IP-címmel kell rendelkeznie. A nyomkövető nélküli disztribúciókban való részvétel során a BitTorrent kliensek bizonyos mértékben hasonlítanak az eMule -hoz a Kad hálózatot használva .

Privát kulcs

A nyilvános (nyílt) trackerekben, ahol bárki letölthet egy torrentet és részt vehet a terjesztésben, a DHT és a PEX minden résztvevő javát szolgálja.

A privát (zárt) trackereknél mindenekelőtt fontos, hogy csak regisztrált felhasználók vegyenek részt a disztribúciókban, és bizonyos szabályokat betartsanak. Egy ügyfél első kérésére egy privát nyomkövetőnek lehetősége van megakadályozni a terjesztését anélkül, hogy megmondaná neki a többi résztvevő kliens címét. Ezért egy privát nyomkövető számára fontos, hogy az ügyfelek ne DHT/PEX-en keresztül kapják meg ezeket a címeket.

A DHT és a PEX 2005 nyarán jelent meg az Azureus és BitComet kliensekben. Sok privát nyomkövető rendszergazdája elégedetlen volt ezzel az új funkcióval, ezért elkezdték tiltani ezeket az új kliensverziókat a nyomkövetőn.

Ezután a kliens fejlesztői egy új kulcsot javasoltak a torrent fájlon belül: private . Ha egyenlő 1-gyel, akkor a kliens köteles automatikusan letiltani a DHT / PEX-et ennél a torrentnél, függetlenül a felhasználó kívánságától. Az ilyen torrentet Secure Torrentnek hívják.

Szinte az összes modern privát nyomkövető maga érvényesíti a privát:1 -et a trackeren közzétett összes torrentben, és tiltja a kliensek több elavult verzióját is, amelyek támogatják a DHT-t vagy a PEX-et, de még nem ismerik a privát kulcsot . Úgy gondolják, hogy a tracker felhasználók egyszerűen nem használhatják a DHT / PEX-et a disztribúciókon, és nincs probléma. Valójában ahhoz, hogy ne vegyük figyelembe a minősítést, elegendő a jelszavát bármilyen másra cserélni. És még csak el sem kell lopnod. Elég egy másik fiókot regisztrálni, hogy kivegye belőle a jelszót.

DHT és statisztika

Ez a rész csak azokra a privát nyomkövetőkre vonatkozik, ahol a magánkulcs nincs kényszerítve a torrentekbe , és egyes disztribúcióknál (attól függően, hogy a terjesztő maga illesztette-e be a privát kulcsot a torrentbe ) használható a DHT és a PEX.

Gyakran van olyan vélemény, hogy a kliensben engedélyezett DHT befolyásolja az ügyfélstatisztikák nyomkövető általi követését, például „DHT-n keresztül terjesztve, tehát a statisztika túlhaladt a nyomkövetőn”. Ez nem igaz.

Először is, a DHT/PEX csak társcímek lekérésére szolgál. Sem a fájlmegosztást, sem a róluk szóló statisztikákat nem vezetik. A kliens a letöltött és feltöltött adatok statisztikáit csak a trackernek jelenti.

Vagyis a „DHT-n keresztül terjesztve” valójában azt jelenti, hogy „DHT-n keresztül kaptam információkat néhány (vagy az összes) társról, és valószínűleg néhány társ is megtalált a DHT-n keresztül”.

Másodszor, bár az ügyfelek általában tudják, honnan kapták a társcímeiket, egyetlen ügyfél sem választja szét a forgalmat „fogadott/DHT-társaknak küldött” és „a nyomkövetőtől kapott partnereknek érkezett/küldött” forgalomra. Még ha kívánja is, ezt nehéz lenne megtennie a kliensnek - egyes társak mind a nyomkövetőből, mind DHT-n vagy PEX-en keresztül fogadhatók, és gyakran az ügyfél nem tudja, hogyan kapta meg a címét az a peer, amelyik elindítja a kapcsolatot.

A kliens jelenti a trackernek a letöltött kötetek összesített adatait, amelyeket az összes partnernek adott, akivel kommunikált , függetlenül attól, hogy a kliens a trackeren, DHT-n vagy PEX-en keresztül értesült-e az egyes társakról, vagy akár maga indította-e el a kapcsolatot. . Vagyis még ha „baloldali” felhasználók (akik nem érik el a nyomkövetőt) megjelennek a disztribúcióban a DHT / PEX miatt, a kliens akkor is jelentést tesz a trackernek mindenről, amit letöltött és elajándékozott.

A statisztikák helyes elszámolása csak a nyomkövető állapotától függ: a nyomkövető működik - a statisztikákat figyelembe veszik, ha nem, akkor nem. Csak egy hosszú ideig nem működő nyomkövető esetén játszhat közvetett szerepet a DHT / PEX, megakadályozva, hogy a fájlmegosztás fokozatosan kihaljon egy ilyen „statisztika figyelembevétele nélküli elosztásnál”.

Hogyan működik a DHT

Az elosztott hálózati megvalósítás a BitTorrent kliensekben a DHT Kademlia nevű változatán alapul . Általánosságban elmondható, hogy a DHT (Distributed hash table) egy olyan decentralizált elosztott rendszert jelent, amely nagyszámú, folyamatosan eltűnő és megjelenő csomópontot kombinál, és ezek között hatékonyan továbbítja az üzeneteket. Különféle összetettebb rendszerek épülnek DHT-struktúrákra, mint például a P2P fájlmegosztás , a kooperatív web-gyorsítótár, a DNS-szolgáltatások stb.

A DHT az UDP protokollt használja . A BitTorrent kliensek ugyanazon az UDP portszámon „hallgatnak”, amelyet a bejövő TCP - kapcsolatokhoz használnak. Ha aktívan használja a DHT-t, akkor ennek az UDP-portnak a megnyitása a kívülről történő eléréshez kívánatos, de nem szükséges – a DHT így fog működni.

Minden csatlakoztatott kliens külön csomópont a DHT-hálózatban. Saját egyedi azonosítóval (azonosítóval) rendelkezik, amelyet véletlenszerűen ugyanabból a 160 bites területből választanak ki, mint az infohash' és a torrentek.

Minden csomópont fenntart egy útválasztási táblát, amely tartalmazza a hozzájuk "legközelebbi" csomópontok és néhány távolabbi csomópont elérhetőségi adatait. Két csomópont "közelségét" az azonosítóik "hasonlóságából" számítják ki, és semmi köze a földrajzi közelségükhöz.

Amikor egy csomópont partnereket akar találni egy disztribúcióhoz, összehasonlítja az adott disztribúció infohash-ét az általa ismert csomópontok azonosítóival, majd kérést küld annak a csomópontnak, amelynek azonosítója leginkább hasonlít az infohash-hez. Ez a csomópont visszaadja annak a csomópontnak a címét, amelynek azonosítója még közelebb van a torrent infohash-jához.

Ezután a csomópontunk kérést küld az új csomópontnak, és megkapja tőle a következő csomópont címét, amelynek azonosítója még jobban hasonlít a torrent infohash-jához.

Így egy adott infohash-t tartalmazó torrent terjesztésében részt vevő kliensek kérései fokozatosan eljutnak azokhoz a csomópontokhoz, amelyek azonosítói leginkább hasonlítanak ehhez az infohashhoz. Ezek a csomópontok emlékeznek a korábbi kérésekre, és az összes későbbi kérelmező csomópont az ugyanabból a terjesztésből származó korábbi társak címét adja vissza.

Hátrányok

1. Számos inkompatibilis protokoll szolgál különböző hálózatokat.
2. A kliens DHT-csomópontként történő működése nagy terhelést ró a routerre (routerre).
3. A hasheket nyíltan teszik közzé, ami lehetővé teszi a terjesztések interaktív nyomon követését (ezt használják a szerzői jogok tulajdonosai). [1] [2] [3]

Kapcsolódó cikkek

• Mágneses kapcsolat
• Kademlia

Jegyzetek

1. ↑ A kutatók valós időben kémkednek a BitTorrent felhasználók után . Letöltve: 2017. szeptember 30. Az eredetiből archiválva : 2017. augusztus 21.. (határozatlan)
2. ↑ DHT protokoll . Letöltve: 2010. május 29. Az eredetiből archiválva : 2015. május 20.. (határozatlan)
3. ↑ Kiterjesztés a partnerek számára metaadatfájlok küldéséhez . Hozzáférés dátuma: 2010. május 29. Az eredetiből archiválva : 2016. május 10. (határozatlan)

Linkek

• A DHT protokoll leírása (fordítás)  (orosz)
• A DHT protokoll leírása a BitTorrent.org webhelyen 
•  az Azureus Wikin
• a BitComet  honlapján