Vyhledávání P2P

Co je to P2P?

Zkratka P2P (peer to peer) je označení pro architekturu počítačových sítí, ve kterém mezi sebou komunikují uživatelé přímo mezi sebou. Hlavní rozdíl je právě v této komunikaci, kde (v ideálním případě) neexistuje centrální server, ale mnoho „serverů“ tzv. uzlů, které jsou současně i klienti. Decentralizace má výhodu vyšší stability, pokud odejde jeden uzel, na celou síť to bude mít minimální následek. V praxi se ale používá částečná centralizace, kdy existují speciální servery sdílející určité informace pro vyhledávání a další činnosti.

V dnešní době se architektura P2P používá ve velké většině na výměnné sítě, díky kterým si uživatelé mezi sebou vyměňují data. Mezi daty se nejčastěji nalézají různá multimedia chráněná autorským zákonem.

Historie P2P

První známky používání P2P přichází ke konci roku 1999. Dříve se pro sdílení dat používaly nejvíce anonymní FTP servery. P2P se do světa rozšířila díky službě Napster, která byla první P2P sítí. Službu Napster používalo 25miliónů uživatelů na světě. Byl to současně triumf i důvod pádu služby Napster. Společnosti si začaly všímat protipirátské organizace a v červenci roku 2001 Napster zaplatil obrovskou pokutu a zanikl. P2P sítě ovšem od té doby znaly miliony uživatelů. Od té doby se začaly vyvíjet další technologie pracující v P2P architekturách. Stěžejní byla dobrá technologie sdílení informací mezi sebou, což úzce souviselo i s vyhledáváním těchto informací.

Úschova metainformace v souborech

Schopnost správného vyhledávání souborů je v P2P sdílení velmi podstatná. Způsoby vyhledávání se mohou značně lišit. Pro centralizované servery s vyhledáváním, které používal Napster, je to jednoduchá úloha. Veškeré informace o souborech jsou uloženy na jednom centrálním serveru, potom účastník přesně ví, komu má poslat seznam souborů určených ke sdílení.

Dalším způsobem distribuce metainformací jsou tzv. magnet linky. Jejich hlavní rozdíl je ve zveřejnění libovolnou cestou, nejčastěji na webu jako odkaz. Tento princip úplně odstraňuje problém s vyhledáváním mezi uzly, poněvadž se informace o sdílených souborech získávají mimo režii této sítě zvenku. Například soubory typu torrent jsou obdobou magnet linků. V torrentu jsou uloženy veškeré metainformace, které účastník potřebuje k tomu, aby kýžený soubor mohl stáhnout.

Jiný způsob hledání je tzv. floodsearch, účastník pošle svůj dotaz několika uzlům. Tyto uzly odpoví, nebo pošlou požadavek dalším uzlům. Tento princip používala síť Gnutella, ovšem brzy zjistili, že je tento princip obtížně aplikovatelný na velký počet klientů. Proto byla vyvinuta Gnutella 2, která už používala lepší protokol. Mezi obyčejnými uzly se nalézaly tzv. superuzly shromažďující informace o souborech. Superuzly přijímaly dotazy o hledaných souborech a následně je zpracovávaly. Protokol byl chráněn proti napadení zahlcením velkého množství paketů tím, že vyhledávací dotazy zabezpečoval pomocí query keys. Query key je 32-bitové číslo, které je náhodně vygenerováno, uloženo a posláno od superuzlu k běžnému uzlu jakmile od něj superuzel získá query key request. Dokud uzel nemá přiřazen query key, nemůže posílat požadavky na vyhledávání.

Centralizované vyhledávací servery mají výhodu, že disponují absolutním seznamem všech souborů na síti, ovšem nevýhody nižší stability serveru. Pokud server spadne, celou síť to naprosto paralyzuje. Naopak použití floodsearch sebou nese přesně opačné příznaky. Jistým kompromisem je použití superuzlů, jak je používá Gnutella 2. Další vývoj P2P služeb se inspiroval právě těmito problémy a snažil se je nějakým způsobem vyřešit.

Nový směr?

Jednou z odpovědí na problémy kompromisů mezi kvalitou vyhledávání a odolnosti vůči výpadku centrálních uzlů byl algoritmus Kademlia, který je založen na naprosto odlišné koncepci tzv. distribuované hašové tabulky. Kademlia splňuje původní koncepci P2P sítí, poněvadž je úplně decentralizovaná, všechny uzly jsou si rovny (žádné superuzly). Díky tomu je odolná proti vypadávání, ale stále zaručuje přesné výsledky vyhledávání a velký možný počet (až miliardy) uživatelů.

Kademlia se skládá z hašových tabulek, kde jednotlivé položky mají dvě složky. Každá položka se skládá z hodnoty a klíče, hodnota reprezentuje soubor a klíč jeho identifikaci v síti. Jak z názvu vypovídá, klíč není přímo název souboru, ale kontrolní součet, k němuž se používá 160bitové SHA-1 hašování. Každý účastník, resp. uzel, který je připojený do sítě a sdílí nějaké soubory, je reprezentován 160bitovým identifikátorem, IP adresou a UDP portem (viz obr. 1). Identifikátor si volí klientský program při startu. Jak je patrno, identifikační klíč i identifikátor uzlu mají stejnou velikost, resp. počet bitů. Je to proto, že se informace o souborech (hodnota a klíč) ukládají do samotného uzlu.

Binární strom algoritmu Kademlia

Obrázek 1 – Binární strom algoritmu Kademlia. Černá tečka ukazuje lokaci uzlu 0011.... ve stromě. Šedé ovály ukazují množiny podstromů, ke kterým se uzel 0011... musí nějakým způsobem dostat.

Do uzlů se ukládají pouze informace o párech, které jsou „blíž“ uzlu. Aby algoritmus zjistil, který soubor je blíže a který dále od uzlu, zavádí určitou metriku definující vzdálenost mezi dvěma uzly x,y, resp. klíče x od uzlu y. Definuje ji takto:

d(x,y) = x xor y

Funkce d(x,y) je vzdálenost mezi x a y. Vzdálenost může nabývat hodnot 0 až 2160. Tato „vzdálenost“ nemá s fyzickou vzdáleností nic společného, poněvadž je metrika definována exkluzivním logickým součtem identifikátorů uzlu a souboru. Uzel v Číně může mít menší vzdálenost k uzlu v České republice, než uzel ve Slovensku. Závisí to pouze na jejich identifikátorech. Každý uzel má na jiných uzlech uloženou vlastní tabulku o 160 položkách. Každá položka tabulky obsahuje seznam k uzlů (tzv. k-bucket). Hodnota k je konstanta společná pro celou síť, např. 20 a reprezentuje počet uzlů uložených na jedné pozici v tabulce. Uzly uložené na určité pozici tabulky mají společnou jednu věc. Tou je vzdálenost. Každý uzel seznamu je ve vzdálenosti alespoň 2i a současně méně než 2i+1, při splnění podmínky 0<=i<160.

Pro každý zapamatovaný uzel má uloženou trojici hodnot (IP adresu, UDP port a identifikátor). Pro krátké vzdálenosti bude určitá pozice v tabulce (resp. k-bucket) často prázdná. V každém k-bucketě jsou položky souborů setříděné podle času, kdy je uzel viděl naposledy online. Nejkratší časy se ukládají na konec k-bucketu. V případě že naším uzlem prochází nějaká zpráva, náš uzel si spočítá vzdálenost od uzlu, který zprávu posílá, následně se podívá do k-bucketu vypočítané vzdálenosti, jestli je v něm tento uzel uložen. Pokud uzel existuje, posune jej na konec k-bucketu. Jestliže v něm uzel není a k-bucket není plný, uloží se na jeho konec. Jestli je k-bucket plný, nejdříve ověří dostupnost uzlu s nejdelší prodlevou, resp. uzel na začátku k-bucketu pingnem. Když bude pingnutý uzel dostupný, nový uzel zahodí, pokud nebude dostupný, zahodí starý uzel a uloží na začátek nový uzel.

Díky tomuto principu výměny informací mezi uzly, není možné zahltit určitý uzel falešnými požadavky a následně způsobit jeho pád (útoky typu DoS). Pokud by útočník vytvořil spoustu nových uzlů v určité vzdálenosti a snažil by se vyprázdnit k-buckety ostatních uzlů těmi svými, přidali by se pouze uzly, které by se do k-bucketu vešly, ostatní by byly zahozeny. Ze statistických údajů je navíc patrné, že čím déle je uzel online, tím vyšší je pravděpodobnost, že bude online další hodinu (viz obr 2).

Graf ukazující pravděpodobnost, že uzel zůstane online dalších 60minut

Obrázek 2 – Pravděpodobnost, že uzel zůstane v síti další hodinu je jako funkce uptime. Na ose x jsou minuty, na ose y je zlomek uzlů, které zůstaly alespoň další jednu hodinu online.

Vyhledávání souborů v Kademlii

Na vyhledávání souborů používá algoritmus Kademlia několik druhů zpráv: ping, store, find_node a find_value.

Ping ověřuje, zda je uzel dostupný.

Zpráva store obsahuje klíč souboru a adresu uzlu, který tento soubor fyzicky skladuje. Příjemce si tuto informaci uloží, její životnost je 24h, poté se záznam vymaže.

Find_node, jak již z názvu vypovídá, hledá určitý uzel. Jako vstupní parametr se dodává 160bitový identifikátor uzlu. Příjemci tohoto požadavku vrátí tázanému uzlu adresy k nejbližším uzlům uloženým v jejich k-bucketech. Pokud k-bucket neobsahuje k uzlů, pošle uzel adresy dalších uzlů z nejbližších k-bucketů, aby splnil k počet uzlů. Pokud nenajde ani v nejbližších k-bucketech dostatečný počet uzlů, odešle pouze maximální počet uzlů, které vyhledal.

Find_value je velmi podobný zprávě find_node. Pouze místo identifikátoru uzlu je parametrem klíč hledaného souboru. Uzly vrací přímo uloženou informaci o uzlech, které soubor fyzicky vlastní.

Vyhledávání probíhá rekurzivně. Pokud účastník hledá uzel nebo klíč, vybere ze svých k-bucketů nejbližších n uzlů, kterým pošle požadavek na vyhledávání. Hodnota n je malé číslo, které lze nastavit v klientovi, např. 3. Těmto uzlům pošle zprávu, od nich dostane odpověď se seznamem nejbližších uzlů. Z těchto uzlů si vybere zase n nejbližších uzlů a pošle jim znovu tento požadavek, dokud nezíská přímo hledaný klíč/uzel. Pro lepší pochopení viz obr.2 .

Umístění uzlů pomocí jejich identifikátorů

Obrázek 3 – Umístění uzlů pomocí jejich identifikátorů. Zde uzel označený černou tečkou s prefixem 0011 hledá uzel s prefixem 1110 pomocí postupného učení bližších řad a bližších uzlů. Úsečka nahoře reprezentuje 160bitový prostor identifikátorů a ukazuje, jak se vyhledávání přibližuje cílovému uzlu. Uzel 0011 vyšle zprávu uzlu 101 (ten je uložen v jeho k-bucketu), s požadavkem na najití uzlu 1110. Uzel 101 vrátí adresu nejbližšího uzlu, který je uzlu 1110 nejblíže, tím je uzel 1101. Tento uzel vrátí uzlu 0011 adresu nejbližšího uzlu, tím je uzel 11110. Konečně tento uzel má uloženou přímo adresu uzlu 1110, kterou vrátí uzlu 0011 a vyhledávání je dokončeno.

Publikování o existenci souborů se dělá pouze na k uzlech nejbližších k publikovanému klíči, o kterých uzel ví. Tyto uzly obdrží zprávu store. Na zaručení aktuálních dat každou hodinu uzel dělá replikaci všech k-bucketů. Tyto informace replikuje vždy na k nejbližších uzlech k danému klíči. Vlastníci souborů musí replikovat informace o svých souborech každých 24 hodin, jinak životnost této informace na ostatních uzlech skončí a informace se ztratí.

Literatura

  1. Root.cz - Vyhľadávanie v peer-to-peer sieťach [online]
    http://www.root.cz/clanky/vyhladavanie-v-peer-to-peer-sietach/,
    Ondrej Mikle [cit. 2009-21-11].
  2. Lupa.cz - Peer to peer sítě od A do Z: Gnutella a Ares [online]
    http://www.lupa.cz/clanky/peer-to-peer-site-od-a-do-z-gnutella-a-ares,
    Jáchym Krasek [cit. 2009-21-11].
  3. Zacatecnik.com - Co je to P2P [online]
    http://zacatecnik.com/index.php?text=44-co-je-to-p2p Wampi
  4. ETH Zurich - P2P Systems as Attack Platform for Distributed Denial-of-Service [online]
    http://www.infsec.ethz.ch/education/ss03/SPA/talks/intro/ges.pdf,
    Arno Wagner [cit. 2009-21-11].
  5. New York University - Kademlia: A Peer-to-peer Information System Based on the XOR Metric [online]
    http://web.archive.org/web/20030917013432/kademlia.scs.cs.nyu.edu/kpos.pdf,
    Petar Maymounkov, David Mazieres [cit. 2009-21-11].
Jakub Holík
Družstevní
Tišnov Česká republika

This hCard created with the hCard creator.

Valid XHTML 1.0 Strict

Valid CSS!

© 2009 Vyhledávání P2P, Jakub Holík