Vyhľadávanie v peer-to-peer sieťach

Spôsoby distribúcie metainformácií o súboroch a vyhľadávanie

Schopnosť nájsť určitý súbor je vo file-sharing p2p sieti dosť podstatná. V prípade centralizovaných serverov (Napster) a hybridných sietí s vyhľadávacími servermi (napr. ed2k, DirectConnect) je to jednoduchá úloha, pretože účastník vie, komu má poslať zoznam svojich súborov a koho sa dotazovať. Iná možnosť je „zaplaviť“ (floodsearch) sieť dotazmi – účastník pošle dotaz niekoľkým (rádovo menej než 10) uzlom, tie buď odpovedia, alebo pošlú dotaz ďalej do siete iným uzlom, tie ďalej, až kým sa nedosiahne maximálny počet hopov. Tento princíp bol používaný sieťou Gnutella, ale čoskoro zistili, že sa veľmi zle škáluje na veľký počet účastníkov (veľké množstvo správ). Naviac má nevýhodu, že je ťažké (alebo nemožné) nájsť zriedkavé súbory.

Gnutella 2 už používa vylepšený protokol, kde superuzly zhromažďujú informácie o zdieľaných súboroch a dotazy idú len cez ne. Aby sa floodsearch nedal použiť ako generátor veľkého množstva paketov (na DOS), Gnutella 2 zabezpečuje vyhľadávacie dotazy cez query keys. Query key je náhodné 32-bitové číslo, ktoré uzol potrebuje získať od superuzlu pred poslaním prvého požiadavku na vyhľadávanie. Na jeho získanie pošle uzol správu query key request, superuzol vygeneruje query key a vráti ho uzlu (správa query key acknowledgement). Superuzol si zapamätá, ktorému uzlu priradil ktorý query key. Keby niekto chcel využiť floodsearch na DOS počítača s určitou IP adresou (cieľ), musel by byť schopný odpočuť paket s query key poslaný na adresu cieľa.

Úplne iný spôsob distribúcie metainformácií je používanie už spomenutých magnet linkov, ktoré môžu byť zverejnené ľubovolnou cestou (web, irc, …). Umožňuje to vyhľadávanie mimo réžiu pôvodnej p2p siete. Súbory .torrent siete BitTorrent sú v podstate obdobou magnet linkov: hovoria, kde je tracker, ktorý má o danom súbore informácie, plus ďalšie metainformácie ako dĺžka súboru a haše častí súboru.

Niektoré siete (napr. ANts) podporujú nielen vyhľadávanie podľa názvu súboru, ale aj full-textové vyhľadávanie v dokumentoch s operátormi AND, OR, plus, mínus, úvodzovky, atď. Implementácia je jednoduchá – každý dokument sa rozparsuje na slová a superuzlu pošle páry (slovo, identifikácia súboru). Vyhľadávanie je realizované floodsearchom. Superuzol, ktorý obrží požiadavok na full-textové vyhľadávanie vyhodnotí hľadaný výraz oproti slovám, ktoré má v databáze a vráti odpovedajúce identifikátory súborov. Rovnakým spôsobom Gnutella 2 implementuje vyhľadávanie v metainformáciách o súbore (akurát syntax povoľuje plus, mínus, úvodzovky a rozsahy).

Voľba medzi centralizovaným vyhľadávacím serverom, distribuovaním po superuzloch a floodsearchom je kompromis medzi presnosťou odpovede a odolnosťou proti zlyhaniu serveru(-ov). Práve tieto otázky boli inšpiráciou k hľadaniu nového riešenia.

Kademlia

Kademlia bola jednou z odpovedí na problém kompromisu medzi presnosťou výsledkov hľadania, centralizáciou verzus decentralizova­nosťou a odolnosťou voči výpadku centrálnych uzlov. Je založená na úplne novom koncepte, je to tzv. distribuovaná hašová tabuľka (distributed hash table, DHT). Kademlia nie je konkrétna p2p sieť, ale algoritmus distribuovania dát a ich vyhľadávania. Siete postavené na Kademlii (napr. Kad, Overnet, trackerless BitTorrent) používajú vždy vlastnú implementáciu. Má niekoľko veľmi zaujímavých vlastností – je úplne decentralizovaná, všetky uzly sú rovnaké (žiadne superuzly), je dosť odolná proti vypadávaniu uzlov a stále zaručuje do veľkej miery presné výsledky vyhľadávania. Je škálovateľná do veľkého počtu uzlov (milióny, miliardy). Cena komunikácie (tj. počet prenesených správ medzi uzlami) je napriek veľkosti siete veľmi nízka. Pozrieme sa, ako je to docielené.

Základný popis, identifikácia uzlov a dát

Kademlia je hašová tabuľka – ukladá páry (kľúč, hodnota), ktoré sú rozdistribuované medzi jej uzlami. Obecne môžu byť kľúče a hodnoty hocičo, ale pre potreby zdieľania súborov hodnota=súbor (jeho obsah), kľúč=identifikácia súboru. Ako identifikácia súboru sa používa jeho SHA-1 haš (160-bitová hodnota). Každý uzol (účastník) je identifikovaný trojicou (160-bit ID, IP adresa, UDP port). ID je náhodná hodnota, ktorú si klientský program zvolí pri štarte. Všimnite si, že kľúče a uzly zdieľajú ten istý 160-bitový priestor. Je to kvôli tomu, že informácie o pároch (kľúč, hodnota) budú uložené v uzle, ktorý je „blízko“ ku kľúču. Aby sme vedeli, čo je „blízko“, „bližšie“, potrebujeme nejakým spôsobom merať vzdialenosť (potrebujeme nejakú metriku). Vzdialenosť dvoch uzlov x, y (resp. kľúča x od uzlu y) definujeme takto:

d(x,y) = x xor y

Vzdialenosť predstavuje číslo od 0 do 2¹⁶⁰-1, čím je menšie, tým „bližšie“ sú dva objekty. Z definície metriky d je vidieť, že nemá nič spoločné s fyzickou vzdialenosťou dvoch uzlov, tj. uzol v Austrálii môže byť blízko uzlu vo Švédsku, závisí to len od ich zvoleného ID. Každý uzol si udržuje tabuľku iných uzlov v rôznych vzdialenostiach. Tabuľka má 160 položiek a pre každé i, 0<=i<160 si na danej pozícii v tabuľke udržuje zoznam niekoľkých k uzlov (tzv. k-bucket), ktoré sú vo vzdialenosti aspoň 2ⁱ, ale menej než 2ⁱ⁺¹. Hodnota k je nejaká konštanta určená pre celú sieť, napr. 20.

Letní fotosoutěž o ceny

Čas dovolených, prázdnin a digitálních foťáků je tady. Připravili jsme pro vás na prázdniny velkou fotosoutěž o zajímavé ceny. Máte šanci vyhrát PDA s operačním systémem Palm OS, set-top-box pro příjem digitální televize a další skvělé ceny! Pošlete nám své fotky a vyhrajte.

Pre každý zapamätaný uzol si drží trojicu (IP adresa, UDP port, ID). Pre malé hodnoty i budú položky v tabuľke často prázdne, pretože žiadny uzol tak blízko pravdepodobne nebude existovať. V každom k-buckete sú uzly zotriedené podľa času, kedy sme ich naposledy videli online (na začiatku sú tie, čo sme videli najdávnejšie). Keď cez náš uzol prechádza nejaká správa, vypočítame vzdialenosť od uzlu, ktorý ju posiela, pozrieme sa do daného k-bucketu, či tam taký uzol je. Ak ho už poznáme, posuneme ho v k-buckete na koniec. Ak ho ešte nepoznáme a je miesto v danom k-buckete, pridáme ho na koniec. Ak je k-bucket plný, pingneme ten uzol z k-bucketu, čo sme videli najdávnejšie. Ak odpovie, informáciu o novom uzle zahodíme. Ak neodpovie, zahodíme neodpovedajúci uzol z k-bucketu a dáme tam nový.

Takto nie je možné spôsobiť DOS na určitý uzol tak, že by útočník vytvoril veľa uzlov a snažil sa vyprázdniť iným uzlom určité k-buckety. Zároveň si tak maximalizujeme šancu, že najviac uzlov z k-bucketu bude online ďalšiu hodinu. Zo štatistických meraní je vidieť, že čím dlhšie je už uzol online, tým väčšia pravdepodobnosť, že zostane online ďalšiu hodinu (viď obrázok 1).

Obrázok 1: Pravdepodobnosť, že uzol ostane v sieti ďalšiu hodinu ako funkcia závislá od uptime. Na x ose sú minúty, na y ose je zlomok uzlov, ktoré po x minútach online ostali aspoň ďalších 60 minút online.

Protokol – vyhľadávanie súborov, oznamovanie o ich existencii

Kademlia používa iba niekoľko typov správ – ping, store, find_node, find_value. Ping overuje, či je uzol online, store hovorí, že uzol má uložiť u seba určitý pár (kľúč, ID vlastníka). Find_node a find_value sú určené na nájdenie uzlu, resp. hodnoty (súboru).

Správa store obsahuje kľúč súboru a klasickú trojicu (IP adresa, UDP port, ID uzlu) toho, kto súbor fyzicky skladuje. Jej príjemca si u seba túto informáciu uloží, jej životnosť je 24 hodín.

Find_node má za argument 160-bitové ID uzlu, ktorý chceme nájsť. Príjemca tejto správy vráti trojice (IP adresa, UDP port, ID uzlu) pre k najbližších uzlov ku hľadanému uzlu (o ktorých vie). Tieto trojice môže zobrať z rovnakého k-bucketu, alebo viacerých k-bucketov (ak jeho k-bucket najbližších nie je plný). V každom prípade musí vrátiť informácie o k najbližších uzloch. Keď nevie ani o k uzloch, jednoducho vráti zoznam všetkých uzlov, o ktorých vie.

Find_value sa správa podobne ako find_node. Jej operand je kľúč súboru, ktorý chceme nájsť. Príjemca správy vracia trojice (IP adresa, UDP port, ID uzlu), len s tým rozdielom, že ak predtým dostal správu store na daný kľúč, vráti priamo uloženú informáciu o tom, kto hľadaný súbor má.

Všetky vyhľadávania prebiehajú rekurzívne – ak chce účastník nájsť daný uzol/kľúč, vyberie zo svojich k-bucketov n najbližších uzlov (n je malé číslo natvrdo nastavené v klientovi, napr. 3). Týmto uzlom pošle správu (find_node alebo find_value). Dostane odpoveď s niekoľkými najbližšími uzlami, z nich si vyberie zase n najbližších. Týmto uzlom pošle rovnakú správu, atď. Posielanie správ je realizované paralelne, nečaká sa na celú rundu find_node/fin­d_value, kým skončí. Keby dotaz nevrátil žiadny bližší uzol než čo zatiaľ videl, pošle dotaz ďalším najbližším k uzlom, ktorých sa ešte nepýtal. Algoritmus končí buď úspešným nájdením alebo po obdržaní odpovede od najbližších k uzlov, ktoré videl (neúspech).

Publikovanie o existencii súboru sa robí na k uzloch najbližších ku publikovanému kľúču, o ktorých uzol vie. Tým sa pošle správa store. Na zaručenie perzistenie robí uzol každú hodinu replikáciu: všetky páry (kľúč, hodnota), ktoré sú uňho uložené, znova publikuje na k najbližších uzlov k danému kľúču. Naviac samotný vlastník súboru musí replikovať každých 24 hodín, inak sa informácia o súbore stratí (životnosť je práve 24 hodín).

Pripojenie do siete – bootstrap

Keď sa uzol chce pripojiť do siete, stačí mu vedieť IP adresa a port jedného účastníka v sieti. Väčšinou sú adresy niektorých uzlov distribuované priamo so softwarom a klientský program ich pravidelne obnovuje (napr. sťahovaním z webu). Po pripojení k uzlu nový uzol spustí vyhľadanie samého seba (svojho ID). Tým pádom si naplní svoje k-buckety uzlov v rozličných vzdialenostiach a zároveň sa jeho ID propaguje v sieti (aby ho bolo možné nájsť).

Výhody Kademlie

Kademlia sa veľmi dobre škáluje na veľký počet užívateľov (rádovo milióny a viac), pretože dvojnásobné zväčšenie siete znamená len o jedno kolo pri hľadaní naviac. Hĺbka rekurzie pri hľadaní je teda najviac log₂ N plus nejaká malá konštanta, kde N je počet uzlov siete. V závislosti na naplnení k-bucketov môže byť hĺbka rekurzie veľmi nízka. Sieť je veľmi odolná proti výpadku uzlov (kým nenastane nejaký skutočne masívny výpadok) a napriek úplnej decentralizácii je možné nájsť zriedkavé súbory.

Nevýhody Kademlie

Hlavnou nevýhodou sú staré záznamy o súboroch, ktorých vlastník už sieť opustil. Táto nevýhoda sa dá minimalizovať zvolením vhodnej životnosti záznamu. Kademlia (pôvodný návrh) funguje len pre verejné IP, ale tento problém sa dá vyriešiť rošírením o UDP hole punching a connection reversal, ktoré boli spomenuté v minulom dieli.

Ďalšie vlastnosti

Niektoré techniky, ako cachovanie často hľadaných súborov na určitých uzloch, som vynechal, môžete si o nich prečítať v pôvodnom návrhu Kademlia algoritmu (odtiaľ pochádza aj obrázok 1). Obsahuje tiež náčrt dôkazu, že sieť sa bude „správať dobre“ za určitých podmienok, napr. že bude dodržaná spomínaná logaritmická hĺbka rekurzie pri hľadaní, že pravdepodobnosť „odrezania“ uzlu od zvyšku siete v dôsledku iných uzlov opúšťajúcich sieť je zanedbateľná.

Nabudúce

V ďalšom dieli si ukážeme spôsob distribúcie dát súborov odlišný od bežného „rozdeľ súbor a pošli časti“ – network coding. Uvidíme, že tento spôsob má vlastnosti optimalizujúce tok dát v sieti a umožňuje, aby distribuované kusy súborov boli „navzájom zameniteľné“, takže nebude de facto existovať „najzriedkavejšia časť“, čo značne pomáha hlavne distribúcii zriedkavých súborov.