Jaettu hash-taulukko

DHT ( eng. d istributed h ash t table - "distributed hash table ") on luokka hajautettuja hajautettuja hakupalvelujärjestelmiä, jotka toimivat hash-taulukon tavoin. Tietorakenteena hash-taulukko voi olla assosiatiivinen taulukko, joka sisältää ( avain-arvo ) -pareja. Termi DHT liittyy myös useisiin periaatteisiin ja algoritmeihin , joiden avulla voit tallentaa tietoja, jakaa tietoa tietyn tallennussolmujoukon kesken ja palauttaa ne hajautetulla haulla avaimella. Hajautetun taulukon ominaisuus on kyky jakaa tietoa tallennussolmujoukon kesken siten, että jokainen osallistuva solmu voisi löytää tiettyyn avaimeen liittyvän arvon. Vastuu nimen ja arvon välisen suhteen ylläpitämisestä on jaettu solmujen kesken, jolloin jäsenjoukon muuttaminen aiheuttaa minimimäärän katkoksia. Tämän avulla voit helposti skaalata DHT:ta sekä seurata jatkuvasti solmujen ja virheiden lisäämistä ja poistamista työssään.

DHT on kehys, jolla voidaan rakentaa monia monimutkaisia palveluita, kuten hajautettuja tiedostojärjestelmiä , peer-to-peer-tiedostojen jakelu- ja sisällönjakeluverkkoja , yhteistoiminnallista verkkovälimuistia, ryhmälähetystä , anycastia , verkkotunnuspalvelua ja pikaviestintää . Tärkeimmät hajautetut verkot, jotka käyttävät DHT: ta: I2P -verkko , BitTorrent , eDonkey-verkko ( Kad-verkko ) , YaCy , Tox ja Coral Content Distribution Network . DHT-verkon kautta on mahdollista luoda hakukoneita .

Historia

DHT-tutkimusta motivoivat alun perin erityisesti peer-to-peer-järjestelmät , kuten I2P , Napster , Gnutella ja Freenet , jotka käyttivät Internetin kautta hajautettuja resursseja yhden sovelluksen luomiseen. Erityisesti he käyttivät laajakaistainternetiä ja kiintolevytilaa tiedostojen jakelupalvelun tarjoamiseen.

Nämä järjestelmät eroavat toisistaan siinä, miten ne löysivät vertaistiedot:

Napsterilla oli keskushakemistopalvelin: jokaisen solmun on liittymisen jälkeen lähetettävä luettelo paikallisesti tallennetuista tiedostoista palvelimelle, joka etsii ja kyselee tulokset sisältävät solmut. Tämä keskeinen komponentti teki järjestelmän alttiiksi hyökkäyksille ja riskeille.
Gnutella ja vastaavat verkot ovat siirtyneet kohti tulvapyyntömallia - periaatteessa jokainen haku johtaisi viestin lähettämiseen kaikille verkon koneille. Vaikka tämä menetelmä vältyttiin keskitetyltä epäonnistumiselta, se oli huomattavasti vähemmän tehokas kuin Napster .
Lopuksi Freenet oli myös täysin hajautettu, mutta reititys perustuu heuristiseen avaimeen, jossa jokaiseen tiedostoon liittyy avain, ja tiedostoilla, joilla on samanlaiset avaimet, on taipumus klusteroitua samanlaisiin solmuihin. Pyyntö lähetettiin todennäköisimmin tällaisille klustereille ilman, että kaikkia vertaiskyselyitä tarvittiin. Freenet ei kuitenkaan voinut taata, että tiedot löydettäisiin.

DHT:t käyttävät järjestelmällisempää avainten reititystä I2P :n , Gnutellan ja Freenetin hajauttamiseksi sekä Napsterin tehokkuuden ja taattujen tulosten saavuttamiseksi . Yksi haittapuoli on, että Freenetin tapaan DHT tukee vain tarkan haun hakuja, ei avainsanahakuja, vaikka nämä ominaisuudet voidaan kerrostaa DHT:n päälle.

Ensimmäiset neljä DHT :ta – CAN , Chord , Pastry ja Tapestry – esiteltiin vuoden 2001 tienoilla . Siitä lähtien tämä tutkimusalue on ollut varsin aktiivista. Akateemisen maailman ulkopuolella DHT-tekniikka on hyväksytty BitTorrentin ja Coral Content Distribution Networkin osaksi .

Ominaisuudet

DHT:lle on tunnusomaista seuraavat ominaisuudet:

Hajauttaminen : kollektiivisen solmujärjestelmän muoto ilman koordinointia;
Skaalautuvuus : järjestelmä toimii yhtä tehokkaasti tuhansien tai miljoonien solmujen kanssa;
Vikasietoisuus : Järjestelmä on yhtä luotettava (jossain mielessä) solmujen ollessa jatkuvasti yhteydessä, katkaisevia ja aiheuttavia virheitä.

Keskeinen tekniikka tämän tavoitteen saavuttamiseksi on, että minkä tahansa solmun tulisi koordinoida vain muutaman järjestelmän solmun kanssa – tyypillisesti O(log n ), missä n on osallistujien määrä (katso alla) – niin että vain rajoitettu määrä työtä tehdään. jokaiseen osallistujamäärän muutokseen.

Jotkut DHT-projektit pyrkivät tarjoamaan suojaa haitallisilta käyttäjiltä ja sallivat osallistujien pysyä nimettöminä, vaikka tämä on harvinaisempaa kuin monissa muissa P2P - järjestelmissä (etenkin tiedostojen jakamisen yhteydessä); katso Nimettömät verkot .

Lopuksi DHT:n on käsiteltävä perinteisempiä hajautetun järjestelmän ongelmia, kuten kuormituksen tasapainotusta, tietojen eheyttä ja suorituskykyä (erityisesti varmistamalla, että toiminnot, kuten reititys ja tietojen tallennus tai haut, valmistuvat nopeasti).

Rakenne

DHT:n rakenne voidaan jakaa useisiin pääkomponentteihin. Se perustuu abstraktiin avainavaruuteen, kuten 160-bittisten merkkijonojen joukkoon (bittien määrä voi vaihdella). Avaintilan osiointimalli jakaa avainten omistajuuden osallistuvien solmujen kesken. Peittoverkko yhdistää sitten solmut ja auttaa löytämään minkä tahansa avaimen omistajan avaintilassa.

Kun kaikki komponentit ovat paikoillaan, DHT:n tyypillinen käyttö tietojen tallentamiseen ja näyttämiseen on seuraava: oletetaan, että avaintila on 160-bittisiä merkkijonoja. Annetun tiedoston ja tiedon tallentamiseksi DHT:hen etsitään SHA1-hash (160-bittinen arvo) tiedoston nimestä , josta muodostetaan 160-bittinen avain k (hash), jonka jälkeen muodostetaan viesti. put(k, data), где data - содержание самого файлаja lähetetään mihin tahansa DHT:n osallistuvaan solmuun. Viesti kulkee solmusta toiseen overlay-verkon kautta, kunnes se saavuttaa avaintilan osiointimenetelmän mukaisesti ainoan avaimesta k vastaavan solmun, johon pari (k, data) tallennetaan. Mikä tahansa muu asiakas voi saada tiedoston sisällön tekemällä avaimen (k), eli hankkimalla tiedostonimen tiivisteen löytääkseen avaimeen liittyvät tiedot lähettämällä viestin get(k). Viesti kulkee jälleen peittokuvan läpi avaimesta vastaavalle solmulle, joka vastaa, että vaaditut tiedot ovat saatavilla.

Avaintilan osiointi ja peittoverkkokomponentit on kuvattu alla esittämään perusideat, jotka ovat yhteisiä useimmille DHT-järjestelmille. Monet kehityssuunnat eroavat yksityiskohdista.

Avaintilan osiointi

Useimmat DHT:t käyttävät erilaisia johdonmukaisen hajautusjärjestelmän muunnelmia avainten yhdistämiseen solmuihin. Tämän osiointimenetelmän ytimessä on funktio , joka määrittää abstraktin käsitteen näppäinten ja avainten välisestä etäisyydestä , jolla ei ole mitään tekemistä maantieteellisen etäisyyden tai verkon viiveen kanssa. Jokaiselle solmulle on määritetty yksi avain, jota kutsutaan sen tunnisteeksi (ID). Tunnuksella varustettu solmu omistaa kaikki avaimet , joille lähin tunnus on laskettu käyttämällä . $\delta(k_1, k_2)$ $k_{1}$ $k_{2}$ $sisään$ $k_m$ $sisään$ $\delta(k_m, i_n)$

Esimerkki. Chord DHT käsittelee näppäimiä ympyrän pisteinä, ja se on ympyrän ympäri myötäpäivään kuljettu etäisyys avaimesta kohtaan . Siten avaintilan ympyrä on jaettu vierekkäisiin segmentteihin, joiden päät ovat solmutunnisteita. Jos ja ovat vierekkäisiä tunnuksia, niin tunnuksella varustettu solmu sisältää kaikki avaimet välillä ja . $\delta(k_1, k_2)$ $k_{1}$ $k_{2}$ $i_1$ $i_2$ $i_2$ $i_1$ $i_2$

Johdonmukaisella hajautustoiminnolla on pääominaisuus, että vain yhden viereisten tunnusten solmuihin kuuluvien avainjoukon poistaminen tai lisääminen ei vaikuta muihin solmuihin.

DHT ja BitTorrent

Sekä DHT että PEX suorittavat itse asiassa BitTorrent-seurannan päätehtävän - ne auttavat tiedostojen jakamisen osallistujia oppimaan toisistaan. He voivat:

Auta osallistujia löytämään toisensa nopeammin
Esimerkiksi jakelussa on vertais X, jonka portti ei ole käytettävissä. Peer Z kytkeytyy jakeluun, joka ei voi itse muodostaa yhteyttä X:n kanssa ja joutuu odottamaan, kunnes X saa tiedon siitä. X on juuri käyttänyt seurantalaitetta ja tekee sen seuraavan tunnin kuluttua.
Mutta vertaisy Y kääntyy jälleen jäljittäjän puoleen ja saa tietää uudesta vertaisversiosta Z. Jos Y itse on samaan aikaan ollut pitkään yhteydessä ja on mukana tiedostojen jakamisessa X:n kanssa, se kertoo X:lle tämän uuden vertaisryhmän Z osoitteen PEX :n kautta. Tällaisia vertaisia Y voi olla jakelussa paljon. Nyt X voi aloittaa yhteyden Z:n kanssa odottamatta seuraavaa pyyntöä jäljittimelle, mikä on erityisen tärkeää, jos Z katkaistaan siihen mennessä. Suurin osa saapuvista ja lähtevistä jakelijoista vähentää lataamisen alkamista.

Vähennä seurantalaitteen kuormitusta
Kun asiakkaat hankkivat vertaisosoitteita DHT:n tai PEX:n kautta, asiakkaat käyttävät seurantaohjelmaa harvemmin, mikä vähentää kuormitusta.

Tukea jakelua jaksojen aikana, jolloin seuranta ei ole käytettävissä.
Jos seurantalaite on ainoa tietolähde vertaisista, jakelu pysähtyy vähitellen, jos se ei toimi. PEX :n avulla asiakkaat voivat vaihtaa keskenään tietoja vertaisryhmistä, joiden kanssa heillä oli kommunikaatioistuntoja, mikä hidastaa jakelun pysäytysprosessia. DHT:n avulla voit vaihtaa seurantalaitteen kokonaan.

DHT:n avulla voit jakaa ilman seurantaohjelmaa
Tällaista jakelua kutsutaan trackerttömäksi ( trackerless ). Sitä varten luodaan torrent ilman seurantaosoitetta ja asiakkaat löytävät toisensa DHT:n kautta. Totta, samaan aikaan jakelun aloittaneella henkilöllä on oltava todellinen IP-osoite, joka on saatavilla ulkopuolelta. Osallistuessaan seurantattomiin jakeluihin BitTorrent-asiakkaat muistuttavat eMulea Kad-verkkoa käyttämällä .

Yksityinen avain

Julkisissa (avoimissa) seurantajärjestelmissä, joissa kuka tahansa voi ladata torrentin ja osallistua jakeluun, DHT ja PEX palvelevat kaikkia osallistujia.

Yksityisille (suljetuille) jäljittäjille on ennen kaikkea tärkeää, että vain rekisteröityneet käyttäjät voivat osallistua jakeluihin ja että he noudattavat tiettyjä sääntöjä. Asiakkaan ensimmäisestä pyynnöstä yksityisellä jäljittäjällä on mahdollisuus estää häntä levittämästä yksinkertaisesti kertomatta hänelle muiden osallistuvien asiakkaiden osoitteita. Siksi on tärkeää yksityiselle jäljittäjille, etteivät asiakkaat saa näitä osoitteita DHT/PEX:n kautta.

DHT ja PEX ilmestyivät Azureus- ja BitComet-asiakkaille kesällä 2005. Monien yksityisten seurantaohjelmien järjestelmänvalvojat eivät olleet tyytyväisiä tähän uuteen toimintoon ja alkoivat siksi kieltää nämä uudet asiakasversiot seurannasta.

Sitten asiakaskehittäjät ehdottivat uutta avainta torrent-tiedoston sisällä: yksityinen . Jos se on yhtä suuri kuin 1, asiakkaan on automaattisesti poistettava DHT / PEX käytöstä tästä torrentista riippumatta käyttäjän halusta. Tällaista torrentia kutsutaan suojatuksi torrentiksi.

Melkein kaikki nykyaikaiset yksityiset seurantalaitteet itse pakottavat yksityisen:1 :n kaikissa seurantaan lähetetyissä torrenteissa ja kieltävät myös useita vanhentuneita asiakasversioita, jotka tukevat DHT:ta tai PEX:ää, mutta eivät vielä tiedä yksityisestä avaimesta . Uskotaan, että tracker-käyttäjät eivät yksinkertaisesti voi käyttää DHT / PEX-jakeluissa, eikä ongelmaa ole. Itse asiassa, jotta luokitusta ei oteta huomioon, riittää, että korvaat salasanasi millä tahansa muulla. Eikä sinun tarvitse edes varastaa sitä. Riittää, kun rekisteröit toisen tilin salasanan ottamiseksi siltä.

DHT ja tilastot

Tämä osio koskee vain yksityisiä seurantalaitteita, joissa yksityistä avainta ei pakoteta torrenteihin , ja joissakin jakeluissa (riippuen siitä, lisäsikö jakelija itse yksityisen avaimen torrentiin ) voidaan käyttää DHT:ta ja PEX:ää.

Usein ollaan sitä mieltä, että asiakkaassa käytössä oleva DHT vaikuttaa seurantalaitteen asiakastilastojen seurantaan, esimerkiksi "jaetaan DHT:n kautta, joten tilastot menivät seurannan ohi". Tämä ei ole totta.

Ensinnäkin DHT/PEX:ää käytetään vain vertaisosoitteiden hankkimiseen. Tiedostojen jakamista tai niiden tilastointia ei pidetä. Asiakas raportoi ladattujen ja ladattujen tietojen tilastot vain seurantalaitteeseen.

Toisin sanoen "jaettu DHT:n kautta" tarkoittaa itse asiassa "sain tietoja joistakin (tai kaikista) vertaisista DHT:n kautta, ja luultavasti jotkut vertaiskumppanit löysivät minut myös DHT:n kautta."

Toiseksi, vaikka asiakkaat yleensä tietävät, mistä he ovat saaneet vertaisosoitteensa, mikään asiakas ei erota liikennettä "vastaanotettuun/lähetettyyn DHT-vertaisille" ja "vastaanotettuun/lähetettyyn kumppanille, joka vastaanotettiin jäljittäjältä". Haluttaessa asiakkaalle tämä olisi vaikeaa - jotkut vertaiset voidaan vastaanottaa sekä jäljittimestä että DHT:n tai PEX:n kautta, ja usein asiakas ei tiedä, miten siihen yhteyden aloittava vertaishenkilö sai osoitteensa.

Asiakas raportoi jäljittäjälle kokonaistiedot ladatuista volyymeistä ja annetuista kaikille ystäville, joiden kanssa hän kommunikoi , riippumatta siitä, saiko asiakas tietää yksittäisistä vertaisista trackerin, DHT:n tai PEX:n kautta vai onko kyseinen vertaisyritys edes aloittanut yhteyden itse. . Eli vaikka "vasemmanpuoleiset" käyttäjät (jotka eivät käytä seurantaa) ilmestyisivät jakeluun DHT/PEX:n takia, asiakas raportoi silti jäljittimelle kaikesta, mitä he ovat ladanneet ja lahjoittaneet.

Tilastojen oikea kirjaaminen riippuu vain seurannan tilasta: seurantalaite toimii - tilastot otetaan huomioon, jos se ei toimi - sitä ei oteta huomioon. Vain pitkäaikaisen toimimattoman seurantalaitteen tapauksessa DHT / PEX voi olla epäsuorassa roolissa, mikä estää tiedostojen jakamista vähitellen kuolemasta tällaisessa "jakelussa ottamatta huomioon tilastoja".

Miten DHT toimii

Hajautetun verkon toteutus BitTorrent-asiakkaissa perustuu DHT:n muunnelmaan nimeltä Kademlia . Yleisesti ottaen DHT (Distributed hash table) tarkoittaa hajautettua hajautettua järjestelmää, joka yhdistää suuren määrän jatkuvasti katoavia ja ilmestyviä solmuja ja siirtää tehokkaasti viestejä niiden välillä. DHT-rakenteiden pohjalta rakennetaan erilaisia monimutkaisempia järjestelmiä, kuten P2P -tiedostojen jakaminen , yhteistoiminnallinen verkkovälimuisti, DNS-palvelut jne.

DHT käyttää UDP - protokollaa . BitTorrent-asiakkaat "kuuntelevat" samaa UDP-porttinumeroa, jota he käyttävät saapuviin TCP - yhteyksiin. Jos käytät aktiivisesti DHT:ta, tämän UDP-portin avaaminen ulkopuolelta on toivottavaa, mutta ei välttämätöntä - DHT toimii näin.

Jokainen yhdistetty asiakas on erillinen solmu DHT-verkossa. Sillä on oma yksilöllinen tunnus (tunniste), joka valitaan satunnaisesti samasta 160-bittisestä tilasta kuin infohash'ja torrentit.

Jokainen solmu ylläpitää reititystaulukkoa, joka sisältää yhteystiedot monille sitä "lähimmille" solmuille ja muutamille kauempana oleville solmuille. Kahden solmun "läheisyys" lasketaan niiden tunnusten "samankaltaisuudesta", eikä sillä ole mitään tekemistä niiden maantieteellisen läheisyyden kanssa.

Kun solmu haluaa löytää vertaisia jakelulle, se vertaa kyseisen jakelun infohash-tietoa tuntemiensa solmujen tunnuksiin ja lähettää sitten pyynnön solmulle, jonka tunnus on eniten samankaltainen kuin tämä tietohaja. Tämä solmu palauttaa sille sen solmun osoitteen, jonka tunnus on vielä lähempänä torrentin infohashia.

Sitten solmumme lähettää pyynnön tälle uudelle solmulle ja vastaanottaa siitä seuraavan solmun osoitteen, jonka tunnus on vieläkin samanlainen kuin torrentin infohash.

Näin ollen tietyn infohash-torrentin jakeluun osallistuvien asiakkaiden pyynnöt virtaavat vähitellen solmuihin, joiden tunnukset ovat eniten samankaltaisia kuin tämä infohash. Nämä solmut muistavat aiemmat pyynnöt, ja kaikille myöhemmille pyyntöjä tehneille solmuille palautetaan saman jakelun aikaisempien vertaiskäyttäjien osoitteet.

Haitat

On olemassa useita yhteensopimattomia protokollia, jotka palvelevat eri verkkoja.
Asiakkaan toiminta DHT-solmuna aiheuttaa suuren kuormituksen reitittimelle (reitittimelle).
Hashit julkaistaan avoimesti, mikä mahdollistaa jakelujen interaktiivisen seurannan (jota tekijänoikeuksien haltijat käyttävät). [1] [2] [3]

Aiheeseen liittyvät artikkelit

Muistiinpanot

↑ Tutkijat vakoilevat BitTorrent-käyttäjiä reaaliajassa . Haettu 30. syyskuuta 2017. Arkistoitu alkuperäisestä 21. elokuuta 2017. (määrätön)
↑ DHT-protokolla . Haettu 29. toukokuuta 2010. Arkistoitu alkuperäisestä 20. toukokuuta 2015. (määrätön)
↑ Laajennus vertaisille metatietotiedostojen lähettämistä varten . Käyttöpäivä: 29. toukokuuta 2010. Arkistoitu alkuperäisestä 10. toukokuuta 2016. (määrätön)

Linkit

Kuvaus DHT-protokollasta (käännös) (venäjä)
Kuvaus DHT-protokollasta osoitteessa BitTorrent.org
Azureus Wikissä
BitCometin verkkosivuilla

BitTorrent tiedostonvaihtoprotokolla ( asiakasohjelmat )
Kirjailijat	Henkilöt Eric Klinker Bram Cohen Navin Yritykset BitTorrent Inc. Vuse, Inc.
Tekniikka	supersiemen Vertaisvaihto (PEX) Jaettu hajautustaulukko (DHT) Yleisradio Protokollan salaus DNA Multitracker Retracker ilmoittaa raaputtaa Siemenlaatikko
Jäljittäjät	Pirate Bay isoHunt Mininova RuTracker.org pornolab.net free-torrents.org Demonoidi 1337x
Moottorit	IPB IPBTT phpBB 2 Torrent-laituri Torrent Pier II phpBB3 ppkBB3cker xbtBB3cker_ SMF SMF Simple Tracker TBDev muu xbtit BTTeam Tracker TorrentTrader Torrent-palvelin Tracker
Aiheeseen liittyvät artikkelit	TorrentFreak