eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra po£íta£·
Bakalá°ská práce
Systém pro distribuci statických zdroj· urychlující na£ítání webových aplikací
Lubo² Mátl
Vedoucí práce:
Ing. Tomá² erný
Studijní program: Softwarové technologie a management, Bakalá°ský
Obor: Softwarové inºenýrství
25. kv¥tna 2011
iv
v
Pod¥kování Rád bych pod¥koval Ing. Tomá²i ernému za odborné vedení mé bakalá°ské práce a také za jeho hodnotné rady, inspiraci a diskuze nejen p°i vypracovávání této bakalá°ské práce. Dále bych cht¥l pod¥kovat Petru Prausovi a Slávce Jarom¥°ské za £etné p°ipomínky, zvlá²t¥ Slávce Jarom¥°ské za nalezení velkého mnoºství chyb programu b¥hem fáze testování. Nakonec bych cht¥l pod¥kovat své rodin¥ za podporu p°i studiu a tvorbu pot°ebného zázemí.
vi
vii
Prohlá²ení Prohla²uji, ºe jsem práci vypracoval samostatn¥ a pouºil jsem pouze podklady uvedené v p°iloºeném seznamu. Nemám závaºný d·vod proti uºití tohoto ²kolního díla ve smyslu 60 Zákona £. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zm¥n¥ n¥kterých zákon· (autorský zákon).
V Praze dne 20. 5. 2011
.............................................................
viii
Abstract The number of users of web services grows every year. Web content providers must purchase powerful hardware or use the services of third parties in response to this growth in users. Both these solutions are very expensive for web site providers. The work deals with designing a system which uses peer-to-peer network. This peer-topeer network allows users to participate with a small portion of their hardware and network resources in web page distribution. The load is low enough as not to interfere with normal usage, but it can partially replace the powerful hardware of the web content provider. This system is tested and compared with conventional web site transmission technologies of Internet, which uses a client-server architecture.
Abstrakt Mnoºství uºivatel· webových sluºeb mnohonásobn¥ roste kaºdým rokem. Na tento nár·st uºivatel· musí poskytovatelé webového obsahu reagovat nákupem výkonného hardwaru nebo vyuºitím sluºeb t°etích stran. Ob¥ tato °e²ení jsou pro poskytovatele zna£n¥ nákladná. Práce se zabývá vytvo°ením systému vyuºívajícím peer-to-peer sí´, který umoºní uºivatel·m podílet se malou £ástí svého hardwaru a sí´ovými prost°edky na distribuci webových stránek. Tato zát¥º, kladená na uºivatele, bude dostate£n¥ malá tak, aby uºivatele významn¥ neomezovala, ale dokáºe £áste£n¥ nahradit výkonný hardware poskytovatele webových stránek. Systém je otestován a porovnán s b¥ºnou technologií p°enosu internetových stránek od webového serveru k uºivateli, stojícím na architektu°e client-server.
ix
x
Obsah 1 Úvod
1
2 Pouºité techonologie
3
2.1 2.2
2.3
Peer-to-Peer sí´ . . . . . . . . . . . . . Pastry . . . . . . . . . . . . . . . . . . 2.2.1 Ozna£ování uzl· . . . . . . . . 2.2.2 Stav uzlu . . . . . . . . . . . . 2.2.2.1 Sm¥rovací tabulka . . 2.2.2.2 Seznam soused· . . . 2.2.2.3 Seznam list· . . . . . 2.2.3 Sm¥rování . . . . . . . . . . . . 2.2.4 Vytvá°ení sm¥rovacích tabulek 2.2.4.1 P°ipojení uzlu . . . . 2.2.4.2 Odpojení uzlu . . . . 2.2.5 Chyby v síti . . . . . . . . . . . Scribe . . . . . . . . . . . . . . . . . . 2.3.1 Skupiny . . . . . . . . . . . . . 2.3.1.1 P°ipojení do skupiny . 2.3.1.2 Odpojení od skupiny . 2.3.2 Anycast . . . . . . . . . . . . . 2.3.3 Manycast . . . . . . . . . . . . 2.3.4 Multicast . . . . . . . . . . . .
3 Popis problému, speci kace cíle 3.1 3.2
3.3
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
Popis problému . . . . . . . . . . . . . . . . . Cíle . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Rychlost . . . . . . . . . . . . . . . . . 3.2.2 Decentralizovatelnost . . . . . . . . . . 3.2.3 Sníºení zatíºení webového serveru . . . Re²er²ní zpracování existujících implementací 3.3.1 Akamai . . . . . . . . . . . . . . . . . 3.3.2 Squirrel . . . . . . . . . . . . . . . . . 3.3.2.1 Home-store . . . . . . . . . . 3.3.2.2 Directory . . . . . . . . . . . xi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 3 4 4 5 5 5 5 5 6 6 7 7 7 7 8 8 8
9
9 10 10 11 11 11 11 12 12 12
xii
OBSAH
4 Analýza a návrh °e²ení 4.1
4.2 4.3
Struktura . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Proxy . . . . . . . . . . . . . . . . . . . . 4.1.2 Service . . . . . . . . . . . . . . . . . . . . 4.1.3 Pluginy . . . . . . . . . . . . . . . . . . . 4.1.3.1 Lokální cache . . . . . . . . . . . 4.1.3.2 Distribuovaná cache . . . . . . . ivotní cyklus poºadavku . . . . . . . . . . . . . 4.2.1 Poºadavek na dynamický soubor . . . . . 4.2.2 Poºadavek na statický soubor . . . . . . . Peer-to-peer sí´ . . . . . . . . . . . . . . . . . . . 4.3.1 P°ipojování . . . . . . . . . . . . . . . . . 4.3.2 Zdroj souboru . . . . . . . . . . . . . . . . 4.3.3 Zp·soby vyhledání soubor· v peer-to-peer 4.3.3.1 Jednoduché stahování . . . . . . 4.3.3.2 P°edstahování . . . . . . . . . . 4.3.4 Po£et najednou vyslaných anycast· . . . .
. . . . . . . . . . . . . . . . . . . . . . . . síti . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
5 Realizace 5.1 5.2 5.3 5.4
FreePastry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vrstva proxy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vrstva service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vrstva Plugins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Lokální cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Distribuovaná cache . . . . . . . . . . . . . . . . . . . . . . . . 5.4.3 Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.3.1 P°ipojování do sít¥ peer· . . . . . . . . . . . . . . . . 5.4.3.2 Posílání anycast· . . . . . . . . . . . . . . . . . . . . . 5.4.3.3 P°ijímání anycast· . . . . . . . . . . . . . . . . . . . . 5.4.3.4 P°ijímání chyb . . . . . . . . . . . . . . . . . . . . . . 5.4.3.5 Posílání chyb . . . . . . . . . . . . . . . . . . . . . . . 5.4.4 Plugins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.5 Handlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.5.1 Peer-request-handler . . . . . . . . . . . . . . . . . . . 5.4.5.2 Service-request-handler . . . . . . . . . . . . . . . . . 5.4.6 Kontext . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.7 Odesílání anycast· . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.8 Zp·soby vyhledávání soubor· . . . . . . . . . . . . . . . . . . . 5.4.8.1 Jednoduchá metoda stahování - File url storage engine 5.4.8.2 Metoda p°edstahování - Source url storage engine . .
6 Testování 6.1
Popis 6.1.1 6.1.2 6.1.3
testování Tester . Shaper . Manager
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
15 15 16 16 16 16 17 17 17 18 18 18 18 19 19 22
23
23 23 24 25 25 26 26 26 26 26 27 27 27 27 27 27 28 28 29 29 29
31
31 32 32 32
xiii
OBSAH
6.2
6.3 6.4 6.5
6.6 6.7
Nastavení testovacího prost°edí . . . . 6.2.1 Testovací stránky . . . . . . . . 6.2.2 P°enosové rychlosti . . . . . . . 6.2.3 Zpoºd¥ní (RTT) . . . . . . . . Srovnání webového prohlíºe£e a testeru Zatíºení webového serveru . . . . . . . Porovnání jednotlivých strategií . . . . 6.5.1 P°edstahování . . . . . . . . . . 6.5.2 Jednoduchá metoda stahování . 6.5.3 Rozd¥lování soubor· . . . . . . Porovnání CWC a proxy . . . . . . . . 6.6.1 RTT webového serveru . . . . . 6.6.2 Po£et uºivatel· . . . . . . . . . Srovnání s existujícími °e²eními . . . . 6.7.1 Akamai . . . . . . . . . . . . . 6.7.2 Squirel . . . . . . . . . . . . . .
7 Záv¥r 7.1
Dal²í 7.1.1 7.1.2 7.1.3 7.1.4 7.1.5
pokra£ování práce . . . . . . . . Sociální sí´ . . . . . . . . . . . Bezpe£nost . . . . . . . . . . . Plugin do webového prohlíºe£e Vyuºití serveru . . . . . . . . . Manycast . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
33 33 33 33 34 34 34 36 37 38 38 38 40 40 40 41
43
43 43 44 44 44 44
A Pouºité zkratky
49
B Úºivatelská p°íru£ka
51
C Obsah p°iloºeného CD
53
B.1 Spu²t¥ní . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 B.2 Parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
xiv
OBSAH
Seznam obrázk· 2.1
Stav uzlu pro uzel s nodeId 10233102, b=2 a l=8 . . . . . . . . . . . . . . . .
3.1
Architektura client/server versus architektura peer-to-peer . . . . . . . . . . . 10
4.1 4.2
Cooperative Web Cache - základní struktura . . . . . . . . . . . . . . . . . . . 15 Cooperative Web Cache - ºivodní cyklus poºadavku . . . . . . . . . . . . . . . 17
5.1 5.2 5.3
Class diagram vrstvy Service . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Distribuovaná cache - základní struktura . . . . . . . . . . . . . . . . . . . . . 25 Class diagram CWCTopic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12
Testování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zatíºení serveru - po£et poºadavk· . . . . . . . . . . . . . . . . . . . . . . . . Zatíºení serveru - mnoºství p°ená²ených dat . . . . . . . . . . . . . . . . . . . as stahování testovací stránky Cenrum pro jednotlivé strategie . . . . . . . . as stahování testovací stránky Google pro jednotlivé strategie . . . . . . . . Mnoºství stahovaných dat 25 uzlu - Centrum . . . . . . . . . . . . . . . . . . Mnoºství stahovaných dat 25 uzlu - Google . . . . . . . . . . . . . . . . . . . Mnoºství stahovaných dat 25 uzlu - Centrum . . . . . . . . . . . . . . . . . . as staºení testovací stránky p°i r·zném RTT serveru - Centrum . . . . . . . as staºení testovací stránky p°i r·zném zpoºd¥ní serveru - Google . . . . . . RTT Alexa TOP 500 webových stránek . . . . . . . . . . . . . . . . . . . . . as stahování stránky metodou p°edstahování a samotnou Proxy, pro r·zný po£et uºivatel· . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xv
4
31 35 35 36 36 37 37 38 39 39 40 41
xvi
SEZNAM OBRÁZK
Seznam tabulek 3.1
Pr·m¥rné velikosti soubor· webové stránky . . . . . . . . . . . . . . . . . . . 11
4.1
Pr·m¥rné velikosti soubor· . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.1 6.2
í°ka pásma serveru a uzl· sít¥ pouºité p°i testování . . . . . . . . . . . . . . 32 Porovnání webového prohlíºe£e a Testeru . . . . . . . . . . . . . . . . . . . . . 33
xvii
xviii
SEZNAM TABULEK
Kapitola 1
Úvod Obvyklým cílem poskytovatel· webových stránek je, krom¥ p°edávání informací uºivateli, co nejvy²²í náv²t¥vnost t¥chto stránek. ím je v²ak po£et uºivatel· webové stránky v¥t²í, tím výkonn¥j²í webový server poskytovatel pot°ebuje, aby byla rychlost na£ítání webové stránky na stran¥ clienta p°ijatelná. Dal²ím problémem poskytovatel· je umíst¥ní serveru. Webový server by m¥l být vºdy umíst¥n tak, aby byl svým uºivatel·m co nejblíºe. ím v¥t²í je vzdálenost serveru od uºivatele, tím je zpravidla sí´ové zpoºd¥ní mezi uºivatelským po£íta£em a serverem vy²²í. Jedním z °e²ení t¥chto problém· je pouºití více server·, kdy pomocí DNS [9] je uºivatel p°esm¥rován vºdy na nejbliº²í nebo nejmén¥ zatíºený webový server. Jiným °e²ením je vyuºít sluºby t°etích stran (nap°. Akamai [10]), které s pomocí svého hardwaru zrychlují distribuci webové stránky. Ob¥ tyto °e²ení mají pro poskytovatele webových stránek obrovskou nevýhodu v tom, ºe stojí nemalé nan£ní prost°edky. Cílem této práce je vytvo°it systém vyuºívající peer-to-peer sí´, pro sdílení statických zdroj· webové aplikace, sniºující zatíºení webových server·. Díky tomuto °e²ení se £ást zát¥ºe, která je nyní kladena na webové servery nebo sluºby t°etích stran, rozd¥lí mezi velký po£et uºivatel·. Kaºdý z uºivatel· se tedy stane poskytovatelem webového obsahu a díky velkému mnoºství uºivatel· by tato zát¥º pro jednotlivé uºivatele m¥la být minimální. Velkou výhodou tohoto °e²ení je skute£nost, ºe £ím více uºivatel· vyuºívá jednu webovou sluºbu, tím také roste mnoºství poskytovatel· této webové sluºby. Distribuovaná Webová Cache je pam¥´ tvo°ená pam¥´ovým prostorem v²ech uºivatel· peer-to-peer sít¥. Webový prohlíºe£ kaºdého uºivatele tak m·ºe, krom¥ získávání dat uloºených ve své lokální pam¥ti, £íst data i z Distribuované Webové Cache, tedy z lokální pam¥ti ostatních uºivatel·. Výb¥r uºivatele (uzlu v peer-to-peer síti), od kterého se stahují statická data, není úpln¥ náhodný. Vºdy se vybere z hlediska ºadatele výhodný uºivatel ze v²ech uºivatel·, kte°í mají hledaná data uloºená ve své lokání pam¥ti. Kritériem pro výb¥r tohoto poskytovatele m·ºe být nap°íklad sí´ové zpoºd¥ní od ºadatele k poskytovateli dat nebo rychlost p°ipojení poskytovatele dat. Protoºe data webové stránky lze získat od nejvýhodn¥j²ích uzl· peer-to-peer sít¥, je vy°e²en i problém vzdálenosti webového serveru od svých uºivatel·. Pro vytvo°ení Distribuované Cache je nutné pouºít decentralizovaný systém vyhledávání soubor· v síti uzl·. Tomuto ú£elu slouºí systém Scribe [3], který vyuºívá Pastry [16]. Pastry popisuje zp·sob, jak vytvo°it peer-to-peer sí´ a p°ená²et zprávy mezi jednotlivými uzly. Scribe umoº¬uje vytvá°et skupiny uzl· a pomocí Pastry posílat anycasty na jednotlivé uzly této skupiny. Tento anycast vºdy dorazí náhodn¥ nebo podle ur£itých vylep²ujících 1
2
KAPITOLA 1.
ÚVOD
kritérií jednomu ze £len· skupiny. Tím, ºe kaºdý statický soubor uloºený v Distribuované Cache bude p°edstavovat jednou Scribe skupinu, lze tyto soubory v peer-to-peer síti jednodu²e vyhledávat. Ve chvíli, kdy uºivatel bude mít soubor uloºený ve své lokální pam¥ti, systém se automaticky p°ipojí do Scribe skupiny nebo, pokud je²t¥ neexistuje, ji zaloºí. Jako identi kátor této skupiny se vyuºije URL souboru, a protoºe neexistují dva r·zné soubory se stejným URL, je tento identi kátor jedine£ný. Kaºdý dal²í uºivatel, který bude mít zájem o soubor, vy²le anycast na skupinu, a pokud tato skupina existuje, jeden ze £len· skupiny mu soubor za²le. Práce je strukturována takto: V kapitole 2 jsou popsány technologie Pastry a Scribe, které jsou nutné k pochopení dal²ích £ástí bakalá°ské práce. Kapitola 3 obsahuje popis cíle, kterého chce práce dosáhnout, a popis jiných jiº existujících °e²ení. Návrh °e²ení a vysv¥tlení funkcí systému je v kapitole 4, následovaný popisem implementace 5. P°edposlední kapitola 6 se zabývá testovaním, a kone£n¥ poslední kapitolou 7 je záv¥r a rozbor moºností pokra£ování dal²ího vývoje systému.
Kapitola 2
Pouºité techonologie V této kapitole bakalá°ské práce, jsou popsány technologie, které jsou nezbytn¥ nutné pro pochopení kapitol následujících. Technologie Pastry a Scribe jsou zásadní pro vytvo°ení Distribuované Webové Cache a pro ú£ely vyhledávání soubor· v této cache. 2.1
Peer-to-Peer sí´
Základním prvkem celého systému Cooperative Web Cache (dále jen CWC) je peer-to-peer sí´ [2]. Peer-to-peer sí´ lze charakterizovat jako distribuované systémy, ve kterých v²echny uzly mají stejné schopnosti a odpov¥dnosti a ve²kerá komunikace je symetrická. Jedním z klí£ových problém· ve velkém m¥°ítku peer-to-peer aplikace, je zajistit efektivní algoritmy pro umís´ování objekt· a sm¥rování v rámci sít¥. 2.2
Pastry
Pastry [16] popisuje základní koncept pro vytvo°ení decentralizované peer-to-peer sít¥. Udává zp·sob, jak ozna£ovat jednotlivé sí´ové uzly a jak sm¥rovat zprávy v této síti. Pastry je zcela decentralizovaná, ²kálovatelná a sebeorganizující. Automaticky se p°izp·sobuje vzniku nového uzlu, odpojení uzlu a chybám p°i p°enosu zpráv. Bere také v úvahu lokalitu sít¥ a snaºí se p°i p°enosu zprávy minimalizovat vzdálenost pomocí veli£in, tuto vzdálenost de nujících, jako je nap°íklad po£et skok· p°es uzly. 2.2.1
Ozna£ování uzl·
Kaºdému uzlu je p°id¥len jednozna£ný klí£ nazvaný nodeId. NodeId je 128 bitový identi kátor a je tedy v rozsahu od 0 do 2128 − 1. P°edpokládá se, ºe kaºdý uzel identi kuje nodeId, který je generován náhodn¥ tak, aby byly tyto klí£e rozloºeny rovnom¥rn¥ po celé síti. P°íkladem vytvo°ení nodeId m·ºe být nap°íklad hashovaní ve°ejného klí£e uzlu (pokud n¥jaký má), jeho IP adresy nebo MAC adresy. D·sledkem tohoto náhodného p°id¥lování nodeId je skute£nost, ºe s vysokou pravd¥podobností budou uzly s p°ilehlým klí£em v r·zném geogra ckém umíst¥ní. 3
4
KAPITOLA 2.
POUITÉ TECHONOLOGIE
Obrázek 2.1: Stav uzlu pro uzel s nodeId 10233102, b=2 a l=8 2.2.2
Stav uzlu
Pro ú£ely sm¥rování musí kaºdý uzel udrºovat sm¥rovací tabulku, seznam soused· a seznam list·. Kaºdá z t¥chto datových struktur obsahuje identi kátory ostatních uzl· peer-to-peer sít¥. Uchovávání identi kátor· tvo°í základ k decentralizovanému p°enosu zpráv v peer-topeer síti. Pro vysv¥tlení sm¥rování zavedu dva parametry l a b. Hodnota l udává po£et °ád· klí£e (nodeId kaºdého uzlu) a hodnota 2b udává po£et moºných hodnot, které m·ºe kaºdá £íslice nabývat. Obrázek 2.1 ukazuje p°íklad sm¥rovací tabulku, seznamu soused· a seznamu list· pro uzel s nodeId 10233102. Po£et °ád· kaºdého identi kátoru uzlu je l = 8 a po£et hodnot, které m·ºe kaºdá z £íslic nabývat je 2b = 4, tedy £íslice m·ºe nabývat hodnot 0 − 3. Typické nastavení pro Pastry sí´ je b = 4 a l = 16 nebo l = 32. Kaºdý z identi kátor· uzl·, uloºených ve sm¥rovací tabulce, seznamu soused· nebo v seznamu list·, obsahuje krom¥ nodeId i IP adresu a port uzlu, na kterém tento uzel naslouchá.
2.2.2.1 Sm¥rovací tabulka V p°ípad¥, kdy N udává po£et v²ech uzl· v síti, je sm¥rovací tabulka organizována do dlog2b N e °ádk·. V kaºdém °ádku je 2b − 1 záznam·. ádek s indexem n (indexujeme od 0) obsahuje odkazy na uzly, jejichº nodeId má n po£áte£ních £íslic shodných s nodeId uzlu, který vlastní danou tabulku, ale jejíº n+1 £íslice má jednu z 2b −1 moºných r·zných hodnot. Volba b, ve vzorci pro výpo£et °ádk· a po£tu záznam· na °ádek, udává kompromis mezi velikostí zapln¥ní sm¥rovací tabulky (p°ibliºn¥ dlog2b N e ∗ (2b − 1) záznam·) a maximálním po£tem skok· pot°ebných k cest¥ pro jakoukoli dvojici uzl· (dlog2b N e). S hodnotou b = 4 a 106-ti uzly sm¥rovací tabulka obsahuje v pr·m¥ru 75 poloºek a p°edpokládaný po£et skok· p°i p°enosu zprávy je 5, p°i£emº se 109-ti uzly sm¥rovací tabulka obsahuje v pr·m¥ru 105 poloºek a o£ekávaný po£et skok· je 7.
2.2.
PASTRY
5
2.2.2.2 Seznam soused· Seznam soused· obsahuje uzly, které jsou podle metrické vzdálenosti nejblíºe danému uzlu. Tento seznam se nepouºívá pro sm¥rování zpráv, ale slouºí pro úpravu sm¥rovací tabulky z hlediska vzdálenosti uzl· od sebe, a tím optimalizuje p°enos zprávy tak, aby byl co nejkrat²í (nap°íklad podle sí´ového zpoºd¥ní mezi uzly). Z d·vodu rozsáhlosti tohoto tématu zde nebudu popisovat, jak probíhá úprava sm¥rovací tabulky pomocí seznamu soused·. Ve²keré tyto informace lze nalézt v £lánku Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems [16].
2.2.2.3 Seznam list· Seznam list· obsahuje uzly, jejichº nodeId jsou nejpodobn¥j²í k nodeId uzlu, který tento seznam vlastní. Seznam je rozd¥len na dv¥ £ásti. Na £ást, která obsahuje identi kátory uzl· s numericky men²ími nodeId, neº je nodeId daného uzlu, a na £ást, s identi kátory numericky v¥t²ími. Toto rozd¥lení slouºí pro správnou funkci sm¥rování, které je popsáno níºe. 2.2.3
Sm¥rování
Kaºdá zpráva, která je odeslána, obsahuje krom¥ obsahu zprávy cílový klí£. Podle tohoto klí£e se v peer-to-peer síti vyhledává uzel, jehoº nodeId je numericky nejpodobn¥j²í klí£i zprávy. V nejlep²ím p°ípad¥ má tedy cílový uzel identickou nodeId ke klí£i zprávy. Algoritmus sm¥rování s pouºitím sm¥rovacích tabulek je proveden takto: P°i p°ijetí zprávy uzel nejprve zkontroluje zda klí£ zprávy pat°í do seznamu list·, coº znamená, ºe klí£ zprávy je v¥t²í neº nejmen²í nodeId v seznamu a zárove¬ men²í neº nejv¥t²í nodeId v seznamu. Pokud ano, je zpráva p°edána p°ímo na cílový uzel, tedy uzel seznamu list·, jehoº nodeId je nejblíºe klí£i zprávy. Pokud uzel nespadá pod seznam list·, pouºije se sm¥rovací tabulka a zpráva je p°edána uzlu, který má stejný pre x s klí£em zprávy. Velikost tohoto pre xu je minimáln¥ o 1 del²í neº je spole£ný pre x zprávy a nodeId uzlu, ve kterém se zpráva práv¥ nachází. V n¥kterých p°ípadech takovýto uzel nelze ve sm¥rovací tabulce nalézt, a pak je zpráva p°edána uzlu, který má stejn¥ velký pre x jako sou£asný uzel, ale jeho hodnota je numericky bliº²í klí£i zprávy. Takový uzel musí být v seznamu list·. Pokud v seznamu není, znamená to, ºe zpráva jiº dorazila k uzlu, jehoº nodeId je numericky nejpodobn¥j²í klí£i zprávy. Tento sm¥rovací algoritmus nám zaru£í, ºe zpráva p°ijde k cílovému uzlu maximáln¥ za dlog2b N e skok·. 2.2.4
Vytvá°ení sm¥rovacích tabulek
Sm¥rovací tabulky, seznamy list· a seznamy soused· se vytvá°ejí a upravují p°i p°ipojování a odpojování uzl· v peer-to-peer síti.
2.2.4.1 P°ipojení uzlu P°i p°ipojení nového uzlu je pot°eba vytvo°it jeho sm¥rovací tabulku, seznam list· a seznam soused· a následn¥ informovat ostatní uzly o jeho p°ipojení. P°edpokládá se, ºe nový uzel
6
KAPITOLA 2.
POUITÉ TECHONOLOGIE
zná jednoho svého blízkého souseda, pomocí kterého se p°ipojuje do Pastry sít¥. Nejprve uzel vytvo°í své nodeId (nap°. náhodn¥ nebo hashováním své IP adresy) a vy²le pomocí uzlu, ke kterému se p°ipojuje, propojovací zprávu. Jako cílový klí£ této zprávy uzel nastaví své nodeId a Pastry sí´ zprávu sm¥ruje (jako kaºdou jinou) k uzlu, jehoº nodeId je numericky nejblíºe klí£i zprávy. Kaºdý uzel na cest¥, kterým zpráva projde, po²le novému uzlu své sm¥rovací tabulky. Propojovací zpráva dojde k uzlu, který je k novému uzlu numericky nejblíºe a od tohoto uzlu nový uzel získá seznam list·. Tento seznam m·ºe nový uzel dále upravovat tak, ºe poºádá jednotlivé uzly z tohoto seznamu o jejich seznam list·. Seznam soused· získá od uzlu, ke kterému se p°ipojuje, protoºe z p°edpokladu je pro n¥j tento uzel ten nejbliº²í v síti. Nakonec nový uzel po²le svou sm¥rovací tabulku v²em uzl·m, které nalezne ve svém seznamu soused·, a tyto uzly si podle ní upraví své sm¥rovací tabulky. Zárove¬ informuje v²echny uzly ze seznamu list· o tom, ºe se p°ipojil. Tyto uzly na základ¥ svého rozhodnutí p°idají uzel do svého seznamu list·.
2.2.4.2 Odpojení uzlu K odpojení uzlu m·ºe dojít úmysln¥ nebo jako výpadek uzlu bez varování. Pastry uzel je povaºován za odpojený, kdyº tento uzel nelze kontaktovat, nap°íklad ve chvíli, kdy se mu n¥který z uzl· snaºí zaslat zprávu, ale nem·ºe se k uzlu p°ipojit. Pak uzel, kterému se zprávu nepoda°ilo odeslat, tuto zprávu po²le jinému uzlu (musí dodrºet pravidlo sm¥rování) a pokusí se upravit své sm¥rovací tabulky. Pro odstran¥ní odpojeného uzlu ze seznamu list· se uzel nejprve podívá, do jaké £ásti seznamu list· odpojený uzel pat°í. Pokud pat°í do £ásti uzl· s men²ím nodeId, kontaktuje uzel, který má v seznamu list· numericky nejniº²í nodeId a získá od tohoto uzlu jeho seznam list· a pomocí tohoto seznamu upraví sv·j seznam list·. Pat°í-li odpojený uzel do £ásti s v¥t²ím nodeId v seznamu list·, ud¥lá to samé s uzlem, který má numericky nejvy²²í nodeId v tomto seznamu. Pro opravu sm¥rovací tabulky kaºdý uzel kontaktuje v²echny uzly, které jsou ve stejném °ádku ve sm¥rovací tabulce uzl· jako odpojený uzel a ºádá je o informaci o uzlu se stejným pre xem, v závislosti na £ísle n °ádku odpojeného uzlu. Pokud od ºádného z t¥chto uzl· poºadované informace nezíská, zeptá v²ech uzl·, které jsou na následující °ádce. Takto pokra£uje, dokud neprojde v²echny následující °ádky sm¥rovací tabulky. Seznam soused· není d·leºitý pro ú£ely sm¥rování, ale je nutné, aby byl aktuální, protoºe obsahuje d·leºité informace o vzdálenostech mezi uzly. Proto se uzly v pravidelném intervalu kontaktují, zda jsou stále p°ipojeny do sít¥, vym¥¬ují si své seznamy soused· a kontrolují vzdálenosti mezi sebou. 2.2.5
Chyby v síti
P°i p°enosu dat v Pastry síti m·ºe docházet k chybám. Pokud by byla zpráva vºdy p°ená²ena (sm¥rována) p°es stejné uzly a jeden z t¥chto uzl· by byl chybný, ub¥hne dlouhá doba, neº se sí´ opraví a po tuto dobu nem·ºe být zpráva p°ijata správným uzlem. Nicmén¥ sm¥rování m·ºe být randomizované. P°ipomínám, ºe pro zabrán¥ní nekone£nému ob¥hu zprávy v síti musí být vºdy zpráva p°edána na uzel, který sdílí del²í pre x klí£e, nebo sdílí stejný pre x délky klí£e jako aktuální uzel, ale je £íseln¥ blíºe v mnoºin¥ nodeId ke klí£i zprávy, neº
2.3.
SCRIBE
7
aktuální uzel. Nicmén¥ p°i výb¥ru mezi více uzly, které spl¬ují toto kritérium, m·ºe být vybrán uzel náhodn¥. V p°ípad¥ selhání uzlu podél cesty, m·ºe být dotaz opakován n¥kolikrát ze strany clienta, dokud se trasa, která je zvolena, nevyhne ²patnému uzlu. 2.3
Scribe
Scribe je systém, který vyuºívá peer-to-peer sí´ Pastry pomocí které vytvá°í skupiny. Na tyto skupiny je pak moºné posílat anycasty. Anycast je sluºba, která umoº¬uje uzlu odeslat zprávu na blízkého £lena skupiny, kde blízkost je de nována metrikou, jako je nap°íklad po£et skok· p°i p°enosu zprávy nebo zpoºd¥ní mezi uzly. Scribe se tedy také stará o distribuci anycast· v peer-to-peer síti. Velikost kaºdé skupiny m·ºe být r·zná a také se m·ºe dynamicky m¥nit. Proto je kaºdá skupina organizovaná do stromové struktury, coº umoº¬uje jednoduché p°ipojování a odpojování uzl· ze skupiny s nízkou reºií. Kaºdý uzel v Pastry síti se m·ºe p°ipojit do skupiny a tím se stává jedním z moºných kandidát· pro p°ijetí anycastu. 2.3.1
Skupiny
Scribe [3] vyuºívá Pastry k pojmenování relativn¥ velkého mnoºství skupin. Kaºdá skupina má ur£ený identi kátor nazvaný groupId (struktura tohoto klí£e je naprosto identická s klí£em v Pastry síti). Tento klí£ m·ºe být vytvo°en nap°íklad jako hash jména skupiny. K vytvo°ení skupiny Scribe po²le zprávu p°es Pastry s cílovým klí£em nastaveným na hodnotu groupId. Uzel, ke kterému zpráva dorazí, se stane ko°enem skupiny stromu. Tento uzel má nodeId numerický nejblíºe ke groupId, a proto se kaºdá zpráva s nastaveným klí£em na hodnotu groupId bude sm¥°ovat k tomuto uzlu.
2.3.1.1 P°ipojení do skupiny P°i p°ipojení uzlu do skupiny, uzel ode²le propojovací zprávu s klí£em nastaveným na hodnotu gropuId skupiny a ta je sm¥rována ke ko°enovému uzlu skupiny. Kaºdý uzel na cest¥ od odesílatele zprávy ke ko°eni skupiny zkontroluje, zda jiº není £lenem skupiny. Pokud je, p°idá odesílatele propojovací zprávy ke svým potomk·m a zprávu dál neposílá. Za p°edpokladu existence skupiny, propojovací zpráva vºdy dorazí bu¤ ke ko°enovému uzlu skupiny nebo k n¥kterému z potomk· tohoto uzlu.
2.3.1.2 Odpojení od skupiny Pokud uzel chce opustit skupinu a má n¥jaké potomky, pouze se ozna£í, ºe jiº není £lenem skupiny. Vzhledem k tomu, ºe obsahuje potomky, musí stále p°edávat skupinové zprávy. Pokud nemá ºádné potomky, po²le svému rodi£i zprávu o tom, ºe se odpojuje. Po obdrºení zprávy rodi£ovský uzel odstraní tento uzel ze svého seznamu potomk·. Pokud i ten jiº není £lenem skupiny a nemá ºádné jiné potomky, po²le zprávu svému rodi£i, ºe se odpojuje. A takto to probíhá rekurzivn¥, dokud se nenajde uzel, který je p°ipojený do skupiny nebo má n¥jaké potomky.
8
KAPITOLA 2.
POUITÉ TECHONOLOGIE
P°i vytvá°ení se stromy samy balancují, protoºe propojovací zprávy se zastaví na prvním uzlu, který je £lenem skupiny. Tento uzel by díky Pastry m¥l být i blízko uzlu, který poºadavek odesílá. Stromy lze také vybalancovávat pomocí Tapestry [28], CAN [14] nebo Chrod [18]. 2.3.2
Anycast
Scribe umoº¬uje odeslat anycast jednomu ze £len· skupiny. Tento anycast spoléhá na to, ºe je vytvo°en skupinový strom. Pokud Scribe vyuºívá algoritmy na balancování stromu bude zpráva doru£ena jednomu z nejbliº²ích £len· skupiny. Chce-li uzel, který samoz°ejm¥ nemusí být £lenem skupiny, vyslat anycast, nastaví jako cílový klí£ zprávy groupId a tato zpráva je sm¥rována na ko°enový uzel skupiny. Po cest¥ se na kaºdém uzlu ov¥°í, zda tento uzel nepat°í do skupiny, kterou odesílatel hledá. Pokud pat°í, pak jiº tato anycastová zpráva není p°edána dál. Místo toho se za£ne prohledávat strom do hloubky, zda potomci uzlu, který anycast p°ijal, jsou ve skupin¥ (nemusí být díky odpojování). M·ºe být p°edem ur£eno po°adí prohledávání potomk·, nap°íklad jako náhodné, pevn¥ dané nebo °ízené podle metrických vzdáleností. P°i prohledávání potomk· se k anycastu vºdy p°ipojí identi kátor uzlu, kterým jiº pro²el, aby se tyto uzly neprocházely vícekrát. Po neúsp¥²ném prohledání v²ech potomk· uzel sám zkontroluje, zda není £lenem skupiny. Pokud je, hledání kon£í. Pokud není, p°idá sv·j identi kátor do seznamu a po²le anycast o úrove¬ vý²e ve stromu. Tento seznam jiº prohledaných uzl· se po ur£ité dob¥ promazává, aby z·stal dostate£n¥ malý. V p°ípad¥, ºe skupina neexistuje, je odesílateli anycastu zaslán anycast fail. 2.3.3
Manycast
Scribe také umoº¬uje odesílat manycast, který po²le zprávu ur£itému po£tu £len·. Zde je strom skupiny procházen stejn¥ jako p°i anycastu, dokud není zpráva p°ijata poºadovaným po£tem £len·. 2.3.4
Multicast
Samoz°ejmostí je odesílání manycastu, který p°ijmou v²ichni £lenové skupiny. Jako anycast dorazí bu¤ k jednomu uzlu, který pat°í do Scribe skupiny nebo ke ko°enovému uzlu skupiny. Kaºdý uzel skupiny, ke kterému zpráva dorazí, po²le zprávu jak svým potomk·m, tak p°edkovi, pokud n¥jakého má.
Kapitola 3
Popis problému, speci kace cíle 3.1
Popis problému
Na obrázku 3.1 lze vid¥t dv¥ architektury sí´ové komunikace vlevo je architektura clientserver vpravo architektura peer-to-peer sít¥. P°i stahování webové stránky se v²echna data, pot°ebná pro úplné zobrazení této stránky musí stáhnout od webového serveru. Tyto data poºaduje mnoho uºivatel· najednou, tedy je jasné, ºe webové aplikace stojí na architektu°e client-server. Server, který zde zpracovává poºadavky v²ech uºivatel· na data webové stránky je zde nejslab²ím místem, a proto se CWC snaºí tomuto místu vyhnout. Základním cílem práce je £áste£n¥ p°evést architekturu client-server na architekturu peerto-peer a tím odstranit nejslab²í místo p°i p°enosu webových stránek, tedy omezit komunikaci s webovým serverem a tuto práci p°evést na jednotlivé clienty sít¥. Dal²ím d·vodem pro vznik CWC je skute£nost, ºe webový prohlíºe£ stahuje soubory webové stránky zna£n¥ neefektivn¥. Protoºe webový prohlíºe£ nezná informace o souborech (nap°. velikost souboru) p°ed tím, neº tyto soubory za£ne stahovat, není moºné optimalizovat p°enos dat webové stránky tak. aby byl p°enos z hlediska £asu co nejefektivn¥j²í. Tyto problémy °e²í spoustu nástaveb HTTP [5] protokolu, jako je nap°íklad STTP [19], které v²ak z d·vodu nutnosti implementace t¥chto vylep²ení, jak na serverové tak na clientské stran¥, nejsou p°íli² roz²í°ené. CWC umoº¬uje vyuºívat výhod informací o souborech získaných p°ed stahováním, bez nutnosti jakékoli zm¥ny na stran¥ webového serveru. Kaºdá internetová stránka se skládá ze dvou druh· soubor· a to statických a dynamických. P°íkladem dynamických soubor· je HTML. Tyto soubory se bohuºel vºdy musí získávat p°ímo od webového serveru, protoºe se v £ase m¥ní nebo mohou být pro kaºdého uºivatele jiné. Zde se tedy architektu°e client-server nelze vyhnout. Statické soubory, jako nap°íklad JavaScript, CSS, ve²keré obrázky stránky a dal²í, jsou stále stejné a nem¥ní se. Proto webový prohlíºe£ tyto soubory do£asn¥ ukládá pro p°ípad op¥tovného pouºití. CWC, krom¥ vlastního vyuºití t¥chto do£asn¥ uloºených soubor·, poskytuje tyto soubory pomocí peer-to-peer sít¥ i ostatním uºivatel·m. Webový prohlíºe£ se tak neomezuje jen na vyhledávání soubor· ve své lokální pam¥ti, ale získává statické soubory i z peer-to-peer sít¥. 9
10
KAPITOLA 3.
POPIS PROBLÉMU, SPECIFIKACE CÍLE
Obrázek 3.1: Architektura client/server versus architektura peer-to-peer Protoºe lze ukládat, a tedy i distribuovat, jen statické soubory, systém stojí na skute£nosti, ºe po£et dynamických soubor· je mnohem men²í neº po£et soubor· statických. Na²t¥stí podle statistiky, která je p°evzatá od webových metrik provád¥ných spole£ností Google [23], viz tabulka 3.1, tvo°í statický obsah v pr·m¥r· okolo 90% webové stránky.
3.2
Cíle
Pro funk£nost peer-to-peer sít¥, sdílející statická data webové stránky, je nutné vytvo°it cache, která bude schopna nahradit cache webového prohlíºe£e. Tato cache bude, stejn¥ jako cache webového prohlíºe£e, schopna do£asn¥ ukládat statická data pro budoucí pouºití. Ale na rozdíl od cache webového prohlíºe£e, bude schopna vyhledávat statická data i v cache pam¥ti ostatních uºivatel· peer-to-peer sít¥. Nutnými vlastnosti této cache je dostate£ná rychlost a decentralizovatelnost. V této kapitole jsou popsány cíle, kterých se práce snaºí dosáhnout. Pro ur£ení zda práce t¥chto cíl· dosáhla, slouºí testování, viz kapitola 6.
3.2.1
Rychlost
Systém je pouºitelný jedin¥ v p°ípad¥, kdy se významn¥ nesníºí rychlost stahování webové stránky. V ur£itých p°ípadech je z p°edpokladu dokonce moºné, ºe se celá webová stránka bude stahovat rychleji. Toho lze dosáhnout díky niº²ímu zpoºd¥ní (niº²í £asové vzdálenosti) mezi clienty, oproti zpoºd¥ní mezi pr·m¥rným clientem a webovým serverem, nebo r·znými technikami, jako je nap°íklad p°edstavování soubor· je²t¥ p°ed tím, neº si o tyto soubory webový prohlíºe£ poºádá.
3.3.
REERNÍ ZPRACOVÁNÍ EXISTUJÍCÍCH IMPLEMENTACÍ
11
Tabulka 3.1: Pr·m¥rné velikosti soubor· webové stránky typ
3.2.2
velikost [KB]
Velikost celé stránky
312.04
Obrázky
184.73
Kaskádové styly
27.17
Externí scripty
66.48
Statický obsah
90%
Dynamický obsah
10%
Decentralizovatelnost
Nesmí existovat ºádný centrální prvek, na kterém by závisela celá peer-to-peer sí´. P°i velkém po£tu uºivatel· by tento prvek mohl zpomalovat celou sí´ a navíc výpadek tohoto prvku by znamenal pád celého distribuovaného systému.
3.2.3
Sníºení zatíºení webového serveru
Protoºe se v²echny statické soubory, pokud v síti peer· existují, nestahují p°ímo od webového serveru, bude mít tento server mnohem mén¥ práce, neº je tomu nyní. Navíc s rostoucím po£tem uºivatel· bude p°i pouºití CWC mnohem mén¥ r·st zatíºení serveru, protoºe se kaºdý uºivatel, v okamºiku, kdy má statický soubor uloºený ve své lokální cache, stává poskytovatelem tohoto souboru.
3.3 3.3.1
Re²er²ní zpracování existujících implementací Akamai
Akamai [10] je spole£nost zaji²´ující globální sluºby v oblasti internetového obsahu, streaming medií a aplikací. Pomocí 84.000 zabezpe£ených server·, které jsou vybaveny specializovaným softwarem, rozmíst¥ných v 72 zemích, zvy²uje kvalitu, rychlost a spolehlivost stahování internetových stránek. V p°ípad¥ staºení internetové stránky uºivatelem, která vyuºívá sluºeb spole£nosti Akamai, je tento uºivatel pomocí DNS sm¥rován na nejbliº²í akamai server. Tento server uºivateli poskytne stránku s mnohem v¥t²í rychlostí, neº v p°ípad¥ p°ímého staºení od webového serveru poskytovatele stránek. V²echny tyto sluºby m·ºe Akamai poskytovat pomocí velkého mnoºství výkonného hardwaru, coº samoz°ejm¥ p°edstavuje vícenáklady za tyto sluºby pro poskytovatele webových stránek. Z tohoto d·vodu si sluºby mohou dovolit pouze movité rmy, jako AMD, Apple, Microsoft a dal²í viz [20].
12 3.3.2
KAPITOLA 3.
POPIS PROBLÉMU, SPECIFIKACE CÍLE
Squirrel
Squirrel [6] je stejn¥ jako CWC decentralizovaná peer-to-peer webová cache, která také vyuºívá peer-to-peer sí´ Pastry [16]. Hlavním rozdílem oproti CWC je skute£nost, ºe Squirrel nevyuºívá výhod Scribu [3], ale má vlastní systém pro vyhledávání soubor· v síti. D·vod nevyuºití technologie Scribe je jednoduchý. V dob¥ vzniku této decentralizované peer-to-peer technologie Scribe je²t¥ neexistoval. Squirrel popisuje dva zp·soby vyhledávání v síti, jeden jednoduchý a jeden více so stikovaný. Kaºdý uzel v peer-to-peer síti má p°id¥lený jednozna£ný identi kátor, pomocí n¥hoº se sm¥rují zprávy (více viz [16]). P°i poºadavku na soubor stránky Squirrel nejprve zjistí, zda lze hledaný soubor cachovat. Pokud nelze, pak tento soubor p°ímo stáhne od webového serveru a poskytne prohlíºe£i. Pokud soubor cachovat lze, nejprve se Scribe podívá do své lokální cache. Zjistí-li, ºe soubor je zastaralý nebo v cache není, sm¥ruje dotaz na soubor do peer-to-peer sít¥. Tento dotaz vºdy dojde k jedinému uzlu, který se nazývá Home-node. Uzel Home-node má tu vlastnost, ºe jeho identi kátor je nejblíºe klí£i zprávy, který je vytvo°en hashováním URL hledaného souboru. Díky peer-to-peer síti Pastry je odeslaná zpráva vºdy sm¥rována na tento uzel.
3.3.2.1 Home-store Kaºdý uzel m·ºe vyslat GET nebo cGET dotaz. GET dotaz uzel vysílá, kdyº hledaný soubor ve své lokální cachy nemá. Dotaz cGET posílá v p°ípad¥ existence souboru ve své lokální cache, ale uzel neví, zda je soubor aktuální. Tento dotaz obsahuje hash obsahu souboru, uloºený v lokální cache odesílatele dotazu. Díky tomu m·ºe p°íjemce dotazu identi kovat, zda je soubor odesílatele dotazu aktuální. Oba tyto dotazy sm¥°ují na Home-node. Pokud Home-node obsahuje kopii souboru ve své cache, zkontroluje, zda je tento soubor aktuální, pomocí webového serveru. Pokud zjistí, ºe je soubor aktuální, pak v p°ípad¥ GET dotazu ode²le soubor p°ímo zp¥t na uzel, který ho poºadoval. V p°ípad¥ cGET dotazu ode²le zp¥t jen informa£ní zprávu o aktuálnosti souboru. Pokud poºadovaný soubor ve své cachy nenalezne, pak tyto dotazy sm¥ruje p°ímo na webový server. Odpov¥di jdou op¥t p°es Home-node, který obsah odpov¥dí (bu¤ soubor, nebo informaci o aktuálnosti) vyuºije p°i zpracování dal²ích dotaz· od ostatních uzl·.
3.3.2.2 Directory Druhý p°ístup vyuºívá toho, ºe kaºdý z uzl·, který soubor poºadoval od Home-node, se také m·ºe stát poskytovatelem tohoto souboru. Home-node udrºuje seznam uzl·, kterým poskytl daný soubor a které tedy s velkou pravd¥podobností soubor mají. Cílem je p°esm¥rovat dotazy na náhodn¥ zvolené uzly z tohoto seznamu. Stejn¥ jako v p°ístupu Home-store uzel vytvo°í poºadavek GET nebo cGET a ten je sm¥rován na Home-node. Pokud home-node neosahuje ºádný seznam uzl·, které by mohly vy°e²it poºadavek, ode²le zp¥t krátkou zprávu s informací o tom, ºe poºadovaný soubor nem·ºe poskytnout a uloºí tento uzel do svého seznamu jako prozatímní záznam. Proto uzel, který vyslal poºadavek, sám stáhne soubor od webového serveru. Ve chvíli, kdy uzel stáhne soubor, ode²le do Home-node metadata tohoto souboru. Home-node si je uloºí do své pam¥ti a ve svém seznamu uzel p°ezna£í z do£asného na aktuální.
3.3.
REERNÍ ZPRACOVÁNÍ EXISTUJÍCÍCH IMPLEMENTACÍ
13
Druhým p°ípadem je, kdyº Home-node nemá prázdný seznam uzl· (delegát·). ádost je pak p°edána náhodn¥ na jednoho z delegát·, který poºadavek vy°e²í. Po vy°e²ení poºadavku tento delegát po²le zp¥t metadata souboru (získané od webového serveru) a v p°ípad¥, ºe Home-node porovnáním s metadaty, které má uloºené ve své pam¥ti, usoudí, ºe soubor, jehoº metadata m¥l doposud uloºená, je zastaralý, smaºe celý sv·j seznam delegát·, krom¥ delegáta od kterého tyto metadata získal. Pokud naopak zjistí, ºe se metadata shodují (podle hashe obsahu souboru uloºeným v metadatech), po²le tyto metadata v²em delegát·m ze seznamu, díky kterým si delegáti aktualizují své informace o souboru.
14
KAPITOLA 3.
POPIS PROBLÉMU, SPECIFIKACE CÍLE
Kapitola 4
Analýza a návrh °e²ení 4.1
Struktura
Jak lze vid¥t z obrázku 4.1, navrhovaná architektura systému CWC je vrstevnatá. Celý systém je rozd¥len do t°í základních vrstev. Kaºdá vrstva posílá poºadavky do niº²í vrstvy a vy°izuje poºadavky vy²²í vrstvy. D·vodem výb¥ru této architektury je moºnost jednoduché vým¥ny jednotlivých vrstev jinou implementací se stejným rozhraním. 4.1.1
Proxy
Vrstva Proxy je prost°edníkem mezi webovým prohlíºe£em a CWC. Stará se o p°ijímání HTTP poºadavk· od webového prohlíºe£e a poskytování odpov¥dí na tyto poºadavky. P°i kaºdém dotazu Proxy zjistí, zda se jedná o dotaz na statický nebo dynamický soubor. Pokud je soubor dynamický poºaduje data rovnou od webového serveru, pokud je statický, posune se poºadavek do niº²í vrstvy. Ve²kerá komunikace webového prohlíºe£e musí probíhat p°es tuto vrstvu. Vrstva je realizována jako webová Proxy, která na ur£itém portu a IP adrese [15] (tyto hodnoty je moºné nastavit p°i spou²t¥ní CWC) p°ijímá HTTP poºadavky. Díky vrstevnaté architektu°e by bylo moºné vytvo°it implementaci Proxy vrstvy jako Pluginu, který se jednodu²e nainstaluje p°ímo do webového prohlíºe£e. Tato alternativa by jist¥ byla uºivatelsky p°ív¥tiv¥j²í a nebyla by nutná komunikace p°es protokol HTTP mezi webovým prohlíºe£em a CWC Proxy. Toto °e²ení by ale nebylo univerzální, protoºe pro kaºdý webový prohlíºe£ by musel být vytvo°en vlastní Plugin. Dal²ím d·vodem pro implementaci webové Proxy je jednodu²²í pouºití p°i testování.
Obrázek 4.1: Cooperative Web Cache - základní struktura
15
16 4.1.2
KAPITOLA 4.
ANALÝZA A NÁVRH EENÍ
Service
Service slouºí jako prost°edník mezi Proxy a Pluginy. P°i poºadavku na statický soubor od vrstvy Proxy, postupn¥ prochází v²echny Pluginy a kaºdého se ptá, zda je schopný zpracovat poºadavek. Pokud Plugin z n¥jakého d·vodu nem·ºe zpracovat tento poºadavek, pak se Service zeptá dal²ího. Kdyº Service projde v²echny Pluginy bez úsp¥chu, vrátí Proxy zprávu o tom, ºe poºadavek nemohla zpracovat. V tomto p°ípad¥ Proxy musí stáhnout statický soubor od webového serveru. Service tedy sama o sob¥ nevykonává ºádnou £innost, je jen prost°edníkem mezi vrstvou Proxy a Pluginy. 4.1.3
Pluginy
Kaºdý Plugin se podle své implementace stará o získání statických soubor· webové stránky. Hlavním výhodou Plugin· je moºnost nahrazení n¥kterého z Plugin· jiným nebo p°idáním n¥jakého dal²ího Pluginu. Nap°íklad pokud bychom cht¥li nahradit implementaci Distribuované cache, která je popsána níºe, n¥jakou jinou implementací, jednodu²e vym¥níme tento Plugin za jiný. Toto nám také umoº¬uje existenci více Plugin· poskytujících statické soubory webové stránky. Pokud by jeden z Plugin· soubor nemohl získat, m·ºe tuto £innost vykonat jiný Plugin. To, jakým zp·sobem Plugin soubory získá, závisí pouze na jeho implementaci. Základní Pluginy, tvo°ící funk£nost CWC, jsou dva, Lokální cache a Distribuovaná cache.
4.1.3.1 Lokální cache Tento Plugin se stará o do£asné ukládání soubor·, které uºivatel stáhne od webového serveru nebo od jiného uzlu. Lokální cache nahrazuje cache webového prohlíºe£e a proto pokud uºivatel chce pouºívat CWC, musí pro správnou £innost cache ve svém prohlíºe£i vypnout. Protoºe data z Lokální cache poºaduje jak prohlíºe£, tak i ostatní uzly v síti, musí být cache dostate£n¥ rychlá. Z tohoto d·vodu je stále uloºena ve fyzické pam¥ti po£íta£e. Velikost této pam¥ti je zna£n¥ omezena a proto i Lokální cache má nastavené omezení. Sou£asné nastavení (tj. nastavení pro v²echny testy) je 50MB pam¥ti. Vzhledem k velikosti fyzické pam¥ti b¥ºného po£íta£e, která je °ádov¥ v jednotkách GB, nep°edstavuje toto mnoºství pam¥ti pro uºivatele ºádné velké zatíºení. Pokud je Lokální cache zapln¥na, a chceme do ní uloºit n¥jaká data, je nutné ji uvolnit. Pro tento ú£el je v Lokální cache pouºita metoda Last Recently Used. Soubor, který je nejdéle nepouºit, a´ uº ukládán nebo vybírán z pam¥ti, je odstran¥n, aby uvolnil místo pro nov¥ vkládaný soubor. Vºdy je odebráno jen tolik soubor·, kolik je nutné k tomu, aby se do pam¥ti nový soubor ve²el. P°i odstra¬ování souboru musí Lokální cache informovat ostatní Pluginy o odstran¥ní tohoto souboru. Proto je o kaºdém odstra¬ování souboru informována vrstva Service, která tuto informaci p°edá v²em ostatním Plugin·m.
4.1.3.2 Distribuovaná cache Distribuovaná cache je Plugin, který se stará o získávání soubor· z peer-to-peer sít¥ a poskytování t¥chto soubor· ostatním uzl·m. Pro správnou £innost Distribuované cache je nutné,
4.2.
17
IVOTNÍ CYKLUS POADAVKU
a4 : HTTP request
a6, b4 : (create) join group a3 : group not-exists
origin server
CWC
CWC
b3 : object
a5 : object
a2, b2 : anycast a7, b5 : object a1, b1 : request
CWC
CWC
client
Obrázek 4.2: Cooperative Web Cache - ºivodní cyklus poºadavku aby v seznamu Plugin·, které obsluhují poºadavky, byla i Lokální cache. Bez ní by CWC nemohla ukládat staºené statické soubory a tak poskytovat tyto soubory ostatním uzl·m. Pro vyhledávání soubor· v peer-to-peer síti vyuºívá Distribuovaná cache sluºeb jiº popsaných technologií, Pastry [16] a Scribe [3]. 4.2
ivotní cyklus poºadavku
Jak jiº bylo °e£eno, webové stránky se skládají ze statických a dynamických soubor·. Statické soubory, jako obrázky, CSS, JavaScript, mohou být do£asn¥ ukládány v pam¥ti a poskytovány ostatním uzl·m sít¥, ale dynamické soubory musí být vºdy staºeny p°ímo od webového serveru, protoºe se v £ase m¥ní a jsou £asto pro kaºdého uºivatele r·zné. Na obrázku 4.2 lze vid¥t ºivotní cyklus poºadavku. V prvním kroku webový prohlíºe£ po²le HTTP poºadavek CWC Proxy. Tam je tento poºadavek rozd¥len na dva druhy, dynamický a statický. 4.2.1
Poºadavek na dynamický soubor
Dynamické soubory nelze sdílet mezi uzly sít¥, a proto se tyto soubory nehledají v peer-topeer síti, ale p°ímo se stahují od webového serveru. Tedy vrstva Proxy neposílá poºadavek do niº²í vrstvy, ale sama se postará o zpracování poºadavku. Po staºení se soubory ani neukládají do Lokální cache, ale rovnou se ode²lou webovému prohlíºe£i. 4.2.2
Poºadavek na statický soubor
Postup stahování statických soubor· je nastín¥n na obrázku 4.2. Nejprve webový prohlíºe£ vy²le poºadavek (a1, b1), vrstva Proxy tento poºadavek p°ijme a rozhodne, zda se jedná o poºadavek na statický nebo dynamický soubor. Statický poºadavek se p°epo²le do niº²í vrstvy Service. Service obsahuje dva základní Pluginy, Lokální cache a Distribuovanou cache. Pokud Lokální cache obsahuje poºadovaný soubor, pak se tento soubor rovnou po²le zp¥t webovému prohlíºe£i (a7) a proces kon£í. Pokud poºadovaný soubor neobsahuje, o získání souboru se bude starat Distribuovaná cache. Ta nejprve vy²le anycastový poºadavek na soubor (a2, b2) do sít¥ peer·, tedy na Scribe skupinu s identi kátorem nastaveným jako hash URL souboru. Pokud Scribe skupina existuje, pak jeden z uzl· této skupiny za²le hledaný soubor odesílateli anycastu (b3). Ten se, po uloºení souboru do své Lokální cache, také zaregistruje do této skupiny (b4) a po²le soubor zp¥t webovému prohlíºe£i (b5). Pokud soubor v peer-to-peer síti není (neexistuje hledaná Scribe skupina), p°ijme uzel anycast fail (a3). Proto uzel získá
18
KAPITOLA 4.
ANALÝZA A NÁVRH EENÍ
hledaný soubor od webového serveru (a4, a5), vytvo°í Scribe skupinu s groupId nastavenou na hodnotu URL souboru (a6), a po²le soubor webovému prohlíºe£i (a7).
4.3
Peer-to-peer sí´
Ve²kerý dal²í popis se vztahuje k Distribuované cache, tedy k získávání statických soubor· z peer-to-peer sít¥. 4.3.1
P°ipojování
Jak jiº je popsáno v £ásti zabývající se Pastry, kaºdý uzel, který se chce p°ipojit do peerto-peer sít¥, musí znát n¥kterého z uºivatel· této sít¥. Proto také Distribuovaná cache p°i spou²t¥ní pot°ebuje IP adresu a port n¥kterého z uºivatel·. V praktickém pouºití samoz°ejm¥ není moºné, aby p°ed p°ipojením do sít¥ uºivatel tyto informace vºdy sám zji²´oval. Proto zde musí být alespo¬ jeden centrální prvek, který bude stále v provozu, a jehoº údaje, nutné k p°ipojení, budou v²echny uzly znát. Tento centrální prvek je jedním z uzl· peer-to-peer sít¥ a m·ºe tedy fungovat jako plnohodnotná CWC, jejímº jediným úkolem je slouºit ostatním uºivatel·m pro p°ipojování do peer-to-peer sít¥. Pokud by byl tento centrální prvek pouze jeden, jeho výpadek by znemoºnil p°ipojení nových uzl· a proto by centrálních prvk· m¥lo být více. 4.3.2
Zdroj souboru
Webový prohlíºe£ funguje tak, ºe po zadání URL adresy n¥jaké stránky uºivatelem, stáhne obvykle HTML soubor a tento soubor pak postupn¥ prochází a stahuje dal²í soubory, na které je v HTML souboru odkazováno. Pro vy²²í rychlost stahuje n¥kolik t¥chto soubor· od webového serveru najednou. Z hlediska HTTP Proxy není jednoduché rozli²it, které soubory pat°í k ur£ité webové stránce. Toto je ale pro CWC d·leºitá informace, která m·ºe být nap°íklad pouºita k urychlení stahování webové stránky. Webové prohlíºe£e v¥t²inou p°idávají k HTTP poºadavku nepovinnou hlavi£ku, REFERER [5], která obsahuje informaci o tom, kde webový prohlíºe£ odkaz na soubor na²el. V na²em p°ípad¥ hlavi£ka REFERER obsahuje URL HTML souboru, který se webový prohlíºe£ snaºí zobrazit. Protoºe je hlavi£ka REFERER nepovinná, nelze p°edpokládat, ºe jí webový prohlíºe£ p°idá k dotazu vºdy. Proto musí být CWC schopna pracovat i bez této informace. 4.3.3
Zp·soby vyhledání soubor· v peer-to-peer síti
Soubor v síti peer· musíme nejd°íve nalézt. Scribe umoº¬uje vytvá°et skupiny, které budou identi kovány pomocí URL souboru, a na £leny t¥chto skupin následn¥ vysílat anycasty s poºadavkem na soubor. Pro vytvá°ení t¥chto skupin a reakce na poºadavky (anycasty) odeslané na tyto skupiny existují dv¥ metody (strategie), jednoduchá metoda stahování a metoda p°edstahování.
4.3.
PEER-TO-PEER SÍ
19
4.3.3.1 Jednoduché stahování Tato metoda vytvá°í pro kaºdý soubor uloºený v Distribuované cachy vlastní Scribe skupinu. GropuId této skupiny je vytvá°eno z URL daného souboru. Pokud se n¥který uzel snaºí nalézt soubor, vy²le anycast na tuto skupinu (jejíº groupId získal z URL souboru). Odeslaný anycast p°ijme jeden z uzl· Scribe skupiny, který má poºadovaný soubor (tento soubor musí mít, protoºe je p°ihlá²en do této skupiny). Tento uzel poºadavek zpracuje a soubor ode²le zp¥t odesílateli anycastu. Pokud skupina v síti neexistuje, pak uzel, který vyslal anycast, obdrºí místo souboru anycast fail. Na základ¥ této informace soubor stáhne od webového serveru a vytvo°í novou skupinu. Kaºdý uzel se odpojuje od Scribe skupiny ve chvíli, kdy se soubor vymaºe z Lokální cache. K vymazání souboru z Lokální cache m·ºe dojít bu¤ z d·vodu nutnosti uvoln¥ní pam¥ti nebo m·ºe být vynucené vrstvou Proxy.
Metoda t°ikrát a dost Soubory, které jsou sou£ástí jedné internetové stránky, mají jednu základní vlastnost. Pokud nikdo tuto stránku nestahoval, je velká pravd¥podobnost, ºe ºádný ze statických soubor· webové stránky nebude uloºen v peer-to-peer síti. Proto bylo nutné vytvo°it mechanizmus, který by zamezoval zbyte£ným pokus·m o stahování soubor· z peerto-peer sít¥, tedy zbyte£ným posíláním anycast· do této sít¥. Pro tuto metodu je nutné rozli²ovat, do jaké webové stránky hledaný soubor pat°í. Bez této informace musí vºdy Distribuovaná cache poslat anycast a £ekat dokud nep°ijde anycast fail nebo hledaný soubor. Metoda t°ikrát a dost povolí pouze t°i negativní odpov¥di na poºadavky na soubor. To znamená, ºe pokud p°ijdou t°i záporné odpov¥di na anycasty se stejným zdrojem (dotazy mají stejný obsah hlavi£ky REFERER) za sebou, CWC se nebude pokou²et stahovat dal²í soubory daného zdroje z peer-to-peer sít¥, ale rovnou tyto soubory stáhne od webového serveru. V praxi je situace mnohem komplikovan¥j²í, protoºe webový prohlíºe£ poºaduje najednou více soubor· se stejným zdrojem. Proto se také ode²le více neº t°i anycasty do doby, kdy Distribuovaná cache zjistí, ºe soubory daného zdroje v peer-to-peer síti nejsou.
4.3.3.2 P°edstahování Metodu p°edstahování lze chápat jako vylep²ující funkci jednoduchého stahování, protoºe pokud webový prohlíºe£ neza²le informaci o zdroji souboru, chová se stejn¥ jako jednoduché stahování. Pokud je ale zdroj souboru známý, dokáºe tato metoda významn¥ urychlit stahování celé webové stránky. P°i kaºdém poºadavku uzel nejprve zjistí, zda obsahuje informaci o zdroji. Pokud ji obsahuje, vy²le nejprve anycast do skupiny, jejíº groupId je tvo°eno zdrojem souboru. V²echny dal²í poºadavky na soubor, které mají stejný zdroj, jsou pozastaveny, dokud není tento anycast vy°ízen. Pokud skupina neexistuje, pak uzel p°edpokládá, ºe ºádné soubory z tohoto zdroje v peer-to-peer síti nejsou a v²echny tyto soubory musí CWC stáhnout od webového serveru. Existuje-li uzel, který anycast p°ijme, ode²le zp¥t seznam soubor·, které jsou nutné ke správnému zobrazení webové stránky. Uzel pak za£ne stahovat tyto soubory z peer-topeer sít¥, stejným zp·sobem jako p°i jednoduchém stahování, bez ohledu na to, zda si o tyto soubory webový prohlíºe£ °ekl. Získá tak soubory d°íve, neº o n¥ webový prohlíºe£ v·bec
20
KAPITOLA 4.
ANALÝZA A NÁVRH EENÍ
Tabulka 4.1: Pr·m¥rné velikosti soubor· typ jpg, gif, png
velikost [KB] 184.73
ico
2
css
27.17
js
66.48
poºádá. Poºadavky na soubory od webového prohlíºe£e, které nejsou nalezeny v tomto seznamu, musí uzel stáhnout od webového serveru a následn¥ je do svého seznamu p°idá. Ve chvíli, kdy uzel stáhne v²echny soubory ze seznamu a p°ipojí se do skupin identi kovaných pomocí URL t¥chto soubor·, p°ipojí se také ke skupin¥ identi kované spole£ným zdrojem soubor· nebo, pokud neexistuje, tuto skupinu vytvo°í. Tím se sám stává poskytovatelem tohoto seznamu soubor·. Identi kátory obsaºené v seznamu soubor· obsahují více informací neº pouze URL adresy, jako nap°íklad informaci o velikosti soubor·, která je pouºita pro výpo£et po£tu odeslaných anycast· na jeden seznam soubor· najednou, viz níºe. P°i smazání jediného souboru z Lokální cache obsaºeném v seznamu soubor· se uzel musí, krom¥ odpojení od skupiny identi kované URL souboru, odpojit od skupiny identi kované zdrojem tohoto seznamu soubor·. P°edejde se tak zbyte£ným dotaz·m na soubory ze seznamu, který v peer-to-peer síti není. Díky identi kátor·m soubor·, obsaºených v seznamu soubor·, je moºné rozd¥lovat velké soubory na £ásti, které budou stahovány od více uzl· najednou. Toto °e²ení by m¥lo obejít problém s velmi malým uploadem v¥t²iny uºivatel· (kaºdý b¥ºný uºivatel má v¥t²í download neº upload a tento upload je mnohonásobn¥ men²í neº upload webového serveru). Pro problémy s odesíláním anycast· (viz níºe) se v²ak tato metoda ukázala jako neefektivní.
4.3.
PEER-TO-PEER SÍ
21
Protoºe je metoda p°edstahování náro£n¥j²í na pochopení, uvádím zde pseudokód, popisující staºení jednoho souboru metodou p°edstahování.
//zdroj - zdroj hledaného souboru, obsaºený v poºadavku na soubor //URL - URL souboru, obsaºený v poºadavku na soubor //list_seznam· - container, který obsahuje v²echny seznamy soubor· if (zdroj != null){ seznam = list_seznam·.get(zdroj) if (seznam != null){ //uzel jiº má seznam soubor· daného zdroje if (seznam.obsahuje_identificator(URL)){ //nastaví anycastu, £ekajícímu ve front¥ na odeslání, vy²²í prioritu urychlit odeslání anycastu na skupinu s groupId = hash(URL) } else { soubor v peer-to-peer síti není } } else { /* seznam je staºen od jiného * uzlu pomocí anycastu na skupinu jejíº groupId = hash(zdroj) */ seznam = získej seznam z P2P if (seznam == null){ /* p°idá prázdný seznam soubor· s identifikátorem * nastaveným na hodnodu zdroje */ list_seznam·.add(prázdný seznam, zdroj) soubor v peer-to-peer síti neexistuje } else { if (seznam.obsahuje_identificator(URL)){ p°esu¬ identifikátor v seznamu na první místo } else { soubor v peer-to-peer síti není } //za£ne stahovat soubory, jejichº identifikátory jsou v seznamu for identifikator in seznam { poslat anycast na skupinu s groupId = hash(identifikator.URL) } } } } else { //pokud není informace o zdroji, chová se jako jednoduché stahování poslat anycast na skupinuu s groupId = hash(URL) }
22 4.3.4
KAPITOLA 4.
ANALÝZA A NÁVRH EENÍ
Po£et najednou vyslaných anycast·
P°i pouºití metody p°edstahování je nutné omezovat po£et sou£asn¥ vyslaných anycast·. Kdyby uzel po p°ijetí seznamu soubor· vyslal anycasty na v²echny soubory z tohoto seznamu, zbyte£n¥ by tím zahltil sí´. Proto bylo nutné vytvo°it podmínku pro maximální po£et vyslaných anycast· na jeden seznam soubor·. Pro lep²í výkon stahování je tento po£et závislý na velikosti soubor·, které se díky odeslaným anycast·m budou stahovat. Jedním z parametr· p°i spou²t¥ní CWC je proto maximální velikost najednou stahovaných soubor· pro jeden seznam. Velikost jednotlivých soubor· lze získat p°ímo z identi kátoru v seznamu soubor·. Krom¥ omezení po£tu anycast· na jeden seznam soubor· existuje i omezení celkové velikosti v²ech najednou vyslaných anycast·. Jeho hodnota se také nastavuje p°i spou²t¥ní CWC a jiº se dotýká i metody jednoduchého stahování statických soubor·. V této metod¥, ale neexistuje ºádný seznam soubor·, ze kterého by bylo moºné získat velikosti soubor·. Proto jsout tyto velikosti hledaných soubor· nastaveny na hodnoty podle tabulky 4.1. Typ souboru je ur£en podle koncovky z URL adresy tohoto souboru. Tyto hodnoty byly, stejn¥ jako hodnoty z tabulky 3.1, získány ze statistiky internetových stránek spole£nosti Google [23]a dopln¥ny pr·m¥rnou velikostí formátu ICO, která byla nastavena na 2KB.
Kapitola 5
Realizace Celý systém je implementovaný v programovacím jazyce Java [24]. Hlavním d·vodem pro tuto volbu byl javovský framework FreePastry [4], který implementuje popsané technologie Pastry a Scribe. Implementace se velmi podobá návrhu, který je popsán vý²e. Základní architektura programu je rozd¥lena do t°í vrstev. Kaºdá vrstva p°ijímá poºadavky z vy²²í vrstvy a pomocí funkcí niº²ích vrstev tyto poºadavky zpracovává. 5.1
FreePastry
FreePastry [4] je open-source implementace peer-to-peer sít¥ Pastry. Tento framework, krom¥ Pastry, také zahrnuje implementaci Scribe. Díky tomu framework tvo°í základ pro Distribuovanou cache, která stahuje statické soubory z peer-to-peer sít¥ a poskytuje tyto soubory ostatním uzl·m. Pomocí FreePastry je tedy moºné vytvá°et Scribe skupiny a £len·m t¥chto skupin posílat anycasty. Posílání zpráv (anycast·) mezi uzly je realizováno pomocí spolehlivého protokolu TCP [12]. Tento protokol je sice pomalý p°i navazování spojení, ale zaji²´uje spolehlivý p°enos zpráv mezi uzly. Nespolehlivého protokolu UDP [11] se pouºívá pouze pro kontrolu uzl· ze seznamu nejbliº²ích soused·. 5.2
Vrstva proxy
Proxy slouºí jako prost°edník mezi webovým prohlíºe£em a serverem. Zpracovává uºivatelovy poºadavky a posílá zp¥t soubory, které získá vy°ízením t¥chto poºadavk·. Proxy vyuºívá z hlediska implementace framework Netty [25]. Netty je NIO client-server framework, který umoº¬uje rychlý a snadný vývoj sí´ových aplikací. Tento framework výrazn¥ zjednodu²uje a zefektiv¬uje programování sí´ových aplikací, jako jsou nap°íklad TCP nebo UDP socketové servery. Proxy nejprve zjistí, o jaký typ souboru se jedná. Tuto informaci Proxy získá z koncovky URL hledaného souboru. Soubory s koncovkami jpg, gif, png, ico, css a js jsou ozna£eny jako statické soubory, ostatní soubory jako dynamické. P°ipomínám, ºe statické soubory jsou poºadovány po vrstv¥ Service. Dynamické soubory jsou p°ímo staºeny z webového serveru. P°i 23
24
KAPITOLA 5.
«interface» FileConsumerInterface
*
+ handle(cf : CacheFile) + willNotBeHandle(fileUrl : string)
CacheFile + HTTPHeaders : Map<string, string> + file : byte[] + fileUrl : string
ProxyConsumer 1
+ removeFile(fileUrl : string) + registerFileRequest(fh : FileHandler) + storeFile(cf : CacheFile) 1
+ + + + +
* FileHandler multihandler : bool fileUrl : string handle(cf : CacheFile) addFileConsumer(fc : undef) setWillNotBeHandle()
1 1
1 ServiceListener
REALIZACE
Service + + + +
registerPlugin(plugin : ServicePluginInterface) removeFile(fileUrl : string) registerFileRequest(fh : FileHandler) storeFile(cf : CacheFile)
*
«interface» ServicePluginInterface + removeFile(fileUrl : string) + registerFileRequest(fh : FileHandler) + registerFileConsumer(fh : FileHandler)
Obrázek 5.1: Class diagram vrstvy Service poºadavku na statický soubor Proxy nejprve vytvo°í FileHandler 5.1. Tento FileHandler obsahuje ve²které informace o souboru, které jsou pot°ebné ke zpracování poºadavku n¥kterým z Plugin·. FileHandler také obsahuje odkaz na t°ídu obsaºenou ve vrstv¥ Proxy, implementující rozhraní FileConsumer. Tato t°ída vy£kává na hledaný soubor nebo na informaci o nemoºnosti získání souboru. FileHandler je následn¥ poslán vrstv¥ Service. T°ída, která vy£kává na hledaný soubor, má z d·vodu ochrany proti chybnému chování Plugin· nastavený timeout na 1,2s. Po vypr²ení tohoto £asu, Proxy jiº ne£eká na odpov¥¤ od Service, ale stáhne soubor p°ímo od webového serveru. Framework Netty stojí na architektu°e Pipes & Filters [8], proto je Proxy tvo°ena z n¥kolika ltr·. Nejd·leºit¥j²í z nich je Filtr pro získávání poºadavk· od uºivatele, ltr pro získávání soubor· z vrstvy Service a ltr pro získávání soubor· od webového serveru. Kaºdý poºadavek t¥mito ltry postupn¥ prochází, dokud není získán hledaný soubor. Pokud jeden z ltr· nem·ºe soubor získat, p°edá °ízení poºadavku ltru následujícímu. Odstran¥ním ltru, který komunikuje s vrstvou Service, vznikne jednoduchá Proxy, která nekomunikuje s peer-to-peer sítí ani do£asn¥ neukládá statické soubory. Tato jednoduchá Proxy je pouºita p°i testování, kdy se porovnává CWC s b¥ºným °e²ením stahování webových stránek. 5.3
Vrstva service
Na obrázku 5.1 m·ºete vid¥t základní strukturu této vrstvy. T°ída Service obsahuje n¥kolik Plugin·. Kaºdý z nich se stará o zpracování FileHandleru a tedy o získání souboru pro FileConsumer. FileConsumer m·ºe být t°ídou ve vrstv¥ Proxy nebo n¥kterým z dal²ích
5.4.
25
VRSTVA PLUGINS
Service
Handlers
Plugins
Transport anycasts receiver
anycast fail sender
peer requests handler
plugin
plugin
sender
service requests handler
plugin
plugin
receiver
service
CWC CWCNode
CWC
CWC
anycasts fail receiver
anycasts sender
Obrázek 5.2: Distribuovaná cache - základní struktura Plugin·. Po°adí Plugin· je velmi d·leºité, protoºe Service prochází p°i poºadavku, postupn¥ v²echny Pluginy s dotazem zda tento poºadavek m·ºe Plugin vy°e²it. Pokud m·ºe, Service se dal²ích Pluginu jiº neptá a o FileHandler se dále bude starat jen vybraný Plugin. Po°adí Plugin· je d·leºité i p°i ukládání soubor·, jak je popsáno vý²e, Distribuovaná cache se p°i ukládání zaregistruje do Scribe skupiny poskytující ur£itý soubor. Pokud by se Distribuovaná cache zaregistrovala do skupiny d°íve, neº se soubor uloºí do Lokální cache, mohla by nastat situace, kdy by n¥který uzel poºadoval soubor, který by p°íjemce anycastu ve své Lokální cache je²t¥ nena²el. Proto je nutné nejprve soubor uloºit do Lokální cache a následn¥ aº poté se p°ipojit do skupiny. Z tohoto d·vodu se také soubory odstra¬ují odzadu.
5.4 5.4.1
Vrstva Plugins Lokální cache
Implementace Lokální cache je velmi jednoduchá. Tvo°í jí dv¥ datové struktury Fronta a Hashmapa. Hashmapa obsahuje odkazy na soubory uloºené v pam¥ti, které jsou identi kované svým URL. Pokud je poºadován soubor, Lokální cache jednodu²e prohledá Hashmapu, zda existuje záznam s daným URL. Existuje-li, je vydán, v opa£ném p°ípad¥ Lokální cache vrátí informaci o tom, ºe nem·ºe poºadavek vy°e²it. P°i ukládání souboru jednodu²e uloºí odkaz na soubor do Hashmapy s identi kátorem nastaveným jako URL souboru. Protoºe soubory jsou ukládány do fyzické pam¥ti po£íta£e, a ta není nekone£n¥ veliká, musí se po£et najednou uloºených soubor· omezovat. K tomu slouºí Fronta, pomocí které se realizuje algoritmus Least Recently Used. B¥hem vytvá°ení Lokální cache se nastavuje maximální velikost pam¥ti, kterou nelze p°ekro£it. P°i vkládání nového souboru, se krom¥ vloºení odkazu na soubor do Hashmapy, vloºí URL souboru na konec Fronty. Ve chvíli, kdy je t°eba odebrat soubory z d·vodu p°ekro£ení maximální velikosti pam¥ti, odebírají se soubory, jejichº URL je na za£átku Fronty. Vºdy se odebírá jen tolik soubor·, kolik je nutn¥ pot°eba
26
KAPITOLA 5.
REALIZACE
místa pro vloºení nového souboru. Pokud je soubor p°e£ten z Lokální cache, jeho URL ve Front¥ se p°esune na konec, tím se stává naposledy pouºitým souborem. Ve²keré odstra¬ování soubor· v Lokální cache je nutné nejprve oznámit v²em ostatním Plugin·m. Proto Lokální cache p°ed mazáním souboru vºdy nejprve informuje vrstvu Service, která tuto informaci po²le v²em ostatním Plugin·m. Ve chvíli, kdy jsou v²echny Pluginy informovány, Lokální cache m·ºe smazat soubor. 5.4.2
Distribuovaná cache
Na obrázku 5.2 m·ºete vid¥t základní strukturu Distribuované cache. Ta je stejn¥ jako základní architektura rozd¥lena do vrstev. Jednotlivé vrstvy jsou: 5.4.3
Transport
Tato vrstva se stará o základní sí´ovou komunikaci. Základem je komponenta CWCNode, která °ídí komunikaci mezi jednotlivými uzly v peer-to-peer síti. Poskytuje tyto sluºby ostatním komponentám:
• P°ipojování do sít¥ peer· • Posílání a p°ijímání anycast· • Posílání a p°ijímání chyb
5.4.3.1 P°ipojování do sít¥ peer· P°i vytvo°ení Distribuované cache je nutné se p°ipojit do peer-to-peer sít¥. Pro toto p°ipojení musí CWC znát alespo¬ IP adresu a port jednoho uzlu. P°i spou²t¥ní je náhodn¥ vybrán identi kátor uzlu (nodeId) se kterým se pokusí p°ipojit do peer-to-peer sít¥. Pokud se p°ipojení nepovede, zm¥ní identi kátor a zkusí to znovu. Po p¥ti pokusech se b¥h programu ukon£í chybovou hlá²kou, oznamující nemoºnost p°ipojení do peer-to-peer sít¥.
5.4.3.2 Posílání anycast· Ve²keré poºadavky na soubory do peer-to-peer sít¥ jsou anycasty. Tyto anycasty vytvá°í Service-request-handler a jsou posílány na Anycast-sender, který je ode²le pomocí komponenty CWCNode.
5.4.3.3 P°ijímání anycast· P°ijme-li CWCNode anycast, p°edá ho ke zpracování Anycast-receiveru. Ten vybere vhodný Peer-request-handler, který anycast zpracuje.
5.4.
VRSTVA PLUGINS
27
5.4.3.4 P°ijímání chyb Chyba vznikne tehdy, pokud neexistuje skupina, na kterou uzel anycast odeslal, nebo uzel, ke kterému anycast dorazí, nem·ºe poºadavek zpracovat. První uzel z peer-to-peer sít¥, který zjistí, ºe tato skupina neexistuje, ode²le tomuto uzlu anycast fail. Ten je pak pomocí Anycast-fail-receiveru oznámen správnému Service-request-handleru, který anycast vytvo°il.
5.4.3.5 Posílání chyb Pokud uzel p°ijme poºadavek, který ºádný z Peer-request-handler· nem·ºe zpracovat, ode²le se anycast fail uzlu, který poºadavek vyslal. Krom¥ komponenty CWCNode vrstva také obsahuje Sender a Receiver. Sender se stará o odesílání soubor· a Receiver soubory p°ijímá. P°enos soubor· je realizován pomocí spolehlivého TCP protokolu. 5.4.4
Plugins
Stejn¥ jako v základní architektu°e CWC i do Distribuované cache lze p°idávat Pluginy. Tyto Pluginy slouºí pro úpravu soubor· p°ed odesáláním nebo po jejich p°ijmutí. Soubor, p°ed odesláním nejprve postupn¥ projde výstupními Pluginy. Kaºdý výstupní Plugin m·ºe do odesílaného souboru p°idat r·zné informace. Po p°ijetí p°íjemcem, soubor nejprve projde vstupními Pluginy a tyto Pluginy mohou p°idané informace zpracovat. Pluginy Distribuované cache nejsou z hlediska základní funk£nosti CWC d·leºité. Testovaný program dokonce ºádné Pluginy neobsahuje. Pluginy pouze slouºí pro dal²í budoucí vývoj CWC. 5.4.5
Handlers
Tato vrstva de nuje logiku Distribuované cache. Ur£uje metody pro vyhledávání soubor·, zji²´ování aktuálnosti soubor· nebo zp·sob odesílání soubor·. Rozd¥luje se na dv¥ základní £ásti, Peer-request-handler a Service-request-handler.
5.4.5.1 Peer-request-handler Stará se o zpracování poºadavk· od ostatních uzl· v síti. Posílá soubory uzl·m, kte°í o n¥ pomocí anycastu poºádaly, p°es Pluginy do Senderu, který soubor ode²le správnému uzlu.
5.4.5.2 Service-request-handler P°ijímá poºadavky od vrstvy Service a pokud je to moºné, pak tyto poºadavky zpracuje. Vrstva Service ºádá o jednotlivé soubory a tento handler se je pomocí anycast· snaºí vyhledat. Pokud soubor v peer-to-peer síti existuje, Sender soubor p°ijme (n¥který uzel z peerto-peer sít¥ soubor za²le) a p°es v²echny Pluginy se dostane aº do správného handleru, který soubor ode²le samotné vrstv¥ Service. Pokud soubor neexistuje, handler zachytí p°es Anycast-fail-receiver chybu a ode²le do vrstvy Service negativní odpov¥¤.
28
KAPITOLA 5.
5.4.6
REALIZACE
Kontext
Distribuovaná cache musí ukládat informace o stavu, ve kterém se nachází. Musí znát, ke kterým Scribe skupinám je p°ipojena, které objekty práv¥ stahuje, které jiº má staºené i ty které zatím £ekají na zpracování. Pro tyto informace vytvá°í objekty CWCTopic (viz obrázek 5.3). Topic ve skute£nosti reprezentuje informace o Scribe skupin¥, které si kaºdý uzel vytvá°í sám. Kaºdý Topic se nachází v jednom z p¥ti stav·:
• WAITING - Topic je nový a je²t¥ s ním nebyly provád¥ny ºádné operace • SEARCHING - objekt, který Topic popisuje je práv¥ vyhledáván v peer-to-peer síti • FOUND - objekt byl jiº staºen, ale uzel je²t¥ není p°ipojen ke Scribe skupin¥ • UNFOUND - objekt nebyl nalezen v peer-to-peer síti a musí být staºen od webového serveru • JOINED - objekt je staºen, uloºen v Lokální cache a uzel je p°ipojen ke Scribe skupin¥ Topic dále obsahuje identi kátor Scribe skupiny pomocí kterého CWC vyhledá objekt v peer-to-peer síti, p°ipojuje se nebo se odpojuje od Scribe skupiny. Seznam Topic· je moºné mezi uzly p°eposílat (metoda p°edstahování toho vyuºívá pro posílání seznamu soubor·), ale je zbyte£né posílat celý Topic, protoºe obsahuje informace nutné jen pro uzel, který ho vlastní. Proto kaºdý Topic m·ºe vytvo°it CWCTopicIdenti cator, který obsahuje jen d·leºité informace, které jsou nutné k jeho znovusestavení. 5.4.7
Odesílání anycast·
Kaºdý Topic vytvá°í anycasty, které se vyuºívají k vyhledávání objektu v peer-to-peer síti. Objektem m·ºe být nap°íklad soubor nebo seznam soubor·. Protoºe odesláním velkého mnoºství anycast· a následným p°ijímáním objekt· by se zahltila sí´, je maximální po£et anycast· omezen. Vyhledávané objekty mají r·znou velikost a proto je rozumn¥j²ím °e²ením omezovat po£et anycast· podle velikosti objekt·, které budeme p°ijímat. Velikost objektu bu¤ známe, díky seznamu soubor· nebo ji musíme odhadnout. Ve chvíli, kdy je odesláno maximální mnoºství anycast·, dal²í anycasty £ekají ve front¥, dokud není n¥který odeslaný anycast vy°e²en p°ijetím hledaného objektu nebo anycast fail. Anycasty je moºné navíc °adit do skupin, kde kaºdá skupina má vlastní omezení maximálního po£tu paraleln¥ odeslaných anycast·. Toho se vyuºívá hlavn¥ p°i metod¥ p°edstahování, kdy se musí omezovat po£et najednou stahovaných objekt· pro jednu stránku (jeden zdroj). Z d·vodu testování jsou hodnoty maximální celkové velikosti odeslaných anycast· a maximální velikosti anycast· pro jednu skupinu uºivatelsky de novatelné parametrem p°i spou²t¥ní programu. Tyto hodnoty, v²ak nejsou jediným omezením maximálního po£tu sou£asn¥ odeslaných anycast·. Jak bylo p°i testování zji²t¥no, framework FreePastry dovolí odeslat maximáln¥ 30 anycast· najednou. Toto £íslo není nijak omezující pro metodu jednoduchého stahování a dokonce ani pro metodu p°edstahování p°i rozumném nastavení hodnoty parametru maximální velikosti anycast· pro jednu skupinu. B¥hem testování se toto omezení za£alo projevovat aº p°i rozd¥lování soubor· na £ásti, které jsou stahované kaºdá zvlá²´.
5.4.
VRSTVA PLUGINS
29
Pro získání kaºdé z t¥chto £ástí je nutné vyslat anycast a zde jiº po£et najednou odeslaných anycast·, omezených v závislosti na maximální velikosti v²ech stahovaných dat, zna£n¥ p°ekra£uje hodnotu 30. 5.4.8
Zp·soby vyhledávání soubor·
Z hlediska implementace zp·soby vyhledávání a stahování soubor· ur£uje pouze výb¥r hanlder· ve vrstv¥ Handlers. Výb¥rem t¥chto handler· lze ur£it nejen zp·sob vyhledávání a stahování soubor·, ale i zp·sob kontroly aktuálnosti soubor·, nebo metody pro zabrán¥ní zbyte£ného odesílání anycast· na objekty, které v síti nejsou. Následující metody jiº byly £áste£n¥ popsány v kapitole 2.
5.4.8.1 Jednoduchá metoda stahování - File url storage engine Tento storage engine je z hlediska implementace velmi jednoduchý. Pro kaºdý poºadavek na soubor od n¥kterého z FileConsumer· vytvo°í FileCWCTopic a p°i°adí mu stav SEARCHING a poté vy²le anycast pomocí Anycast-senderu. Uzel, který má hledaný soubor, tento anycast p°ijme. Pak pomocí Service, získá poºadovaný soubor ze své Lokální cache a po²le jej zp¥t uzlu, který o n¥j ºádal. Ten soubor zpracuje a po²le jej zp¥t FileConsumerovi, který poºadavek vytvo°il. Nakonec zm¥ní Topicu stav ze SEARCHING na FOUND. Pokud ºádný z uzl· hledaný soubor nemá (neexistuje Scribe skupina s groupId nastaveným na URL souboru), Pastry automaticky ode²le anycast fail, který uzel obdrºí pomocí Anycastfail-receiveru. Ten FileConsumerovi oznámí, ºe poºadavek nelze vy°ídit, a zm¥ní stav topicu na UNFOUND. Pokud je FileConsumerem Proxy, stáhne soubor p°ímo od webového serveru. Distribuovaná cache se p°ipojí do skupiny ve chvíli kdy je jisté, ºe je soubor uloºen do Lokální cache. Pak p°ejde Topic ze stavu FOUND nebo UNFOUND do stavu JOINED a uzel se p°ipojí do Scribe skupiny identi kované pomocí URL souboru. Aº od této chvíle uzel poskytuje soubor ostatním uzl·m v síti.
5.4.8.2 Metoda p°edstahování - Source url storage engine Zde je situace mnohem komplikovan¥j²í. Pokud poºadavek FileHandler na soubor obsahuje informaci o zdroji (URL stránky ze které se soubory stahují), je nejprve staºen seznam soubor·. Tento seznam soubor· poskytuje kaºdý uzel peer-to-peer sít¥, který má staºeny v²echny soubory daného zdroje. Vºdy, kdyº uzel stáhne n¥jaký soubor a zná jeho zdroj, p°idá tento soubor do seznamu soubor· tohoto zdroje. Z implementa£ního hlediska toto znamená, ºe se FileCWCTopic p°idá do seznamu v SourceCWCTopic. SourceCWCTopic tedy reprezentuje seznam soubor· daného zdroje. Pokud v²echny FileCWCTopic z jednoho seznamu v SourceCWCTopic mají stav nastavený na JOINED, pak se tento SourceCWCTopic p°ipojí do skupiny, ze které pomocí anycastu mohou ostatní uzly tento seznam soubor· stáhnout. Seznam soubor· je tvo°en seznamem identi kátor· Topic·, který obsahuje SourceCWCTopic hledaného zdroje. Podle seznamu m·ºe kaºdý uzel p°edstahovat soubory, které po n¥m je²t¥ webový prohlíºe£ nepoºadoval. Navíc tento seznam m·ºe obsahovat více informací o jednotlivých souborech, jako nap°íklad informaci o jeho velikosti, nebo zda je moºné soubor stahovat po £ástech. To nám umoº¬uje zvý²it rychlost stahování soubor· z peer-to-peer sít¥.
30
KAPITOLA 5.
CWCTopicIdentificator
«enum» TopicState NEW WAITING SEARCHING FOUND JOINED
1
+ getTopics()
FileCWCTopicIdentificator
SourceCWCTopicIdentificator + + + + +
DividedFileCWCTopicIdentificator
«enum» AnycastState NEW SEND WAITING
1 CWCTopic groupId : string 1 id : string getAnycasts() canDownload() : bool setState(state : TopicState)
*
Anycast + size : int
1 1 Request + topicId : string + id : string
FileCWCTopic
SourceCWCTopic
+ setSource(sourceTopic : SourceCWCTopic)
+ addFileCWCTopic(fileTopic : FileCWCTopic)
DividedFileCWCTopic + HTTPHeader : + hash : string + setFilePartCWCTopic(filePartTopic : FilePartCWCTopic)
REALIZACE
FilePartCWCTopic + partNumer : int
FilePartRequest + partNumber : int
FileRequest
SourceRequest
Obrázek 5.3: Class diagram CWCTopic Pokud uzel seznam v síti peer· nenalezne, v²echny soubory z tohoto zdroje musí stahovat p°ímo od webového serveru a tím se stává prvním uzlem, který poskytuje seznam soubor· tohoto zdroje. Pokud poºadavek na soubor neobsahuje informaci o zdroji, chová se tento storage engine stejn¥ jako jednoduché stahování.
Rozd¥lování soubor· Kaºdý identi kátor ze seznamu soubor· obsahuje informaci o velikosti souboru. Z této velikosti je díky, pevn¥ nastavené velikosti £ásti souboru (nastavuje se p°i spu²t¥ní CWC a je pro v²echny uzly stejná), vypo£ítán po£et £ástí kaºdého souboru. Na kaºdou tuto £ást je vyslán anycast do skupiny identi kované groupId vytvo°eným z URL souboru. Jelikoº kaºdý anycast dorazí náhodn¥ jednomu ze £len· Scribe skupiny, stahuje se kaºdá £ást s velkou pravd¥podovností od jiného uzlu. Po staºení v²ech £ástí se sestaví kompletní soubor. Tento soubor se nakonec zkontroluje vytvo°ením hashe z obsahu souboru, která se následn¥ porovná s hashe obsaºenou v identi kátoru souboru. Pokud jsou hashe stejné, je p°ijat správný soubor, pokud ne, soubor se musí stáhnout znovu, tentokrát ale od webového serveru.
Kapitola 6
Testování 6.1
Popis testování
Protoºe celá práce stojí na existenci velké peer-to-peer sít¥, která zaji²´uje sdílení statického obsahu webových stránek mezi uºivateli, bylo nutné otestovat mnoho spu²t¥ných aplikací CWC najednou. Pro testování reálného prost°edí by kaºdá z aplikací m¥la být spu²t¥na na jiném po£íta£i. Kaºdý tento po£íta£ by také m¥l mít ur£ité sí´ové zpoºd¥ní od ostatních uzl· a omezení vlastní ²í°ky pásma. Protoºe pro správnou funkci CWC je vyºadováno v¥t²í mnoºství spu²t¥ných uzl· najednou, není tento zp·sob °e²ení ve velkém po£tu uzl· reáln¥ zvládnutelný. Proto bylo vyvinuto testovací prost°edí, které dokáºe na jednom nebo více po£íta£ích otestovat velký po£et uzl· (Na jednom po£íta£i s opera£ní pam¥tí 4GB bylo p°i testování moºné, bez toho aniº by se uzly navzájem jakkoliv ovliv¬ovaly, spustit aº 50 uzl·). Toto testovací prost°edí tedy dokáºe emulovat reálnou sí´ na jednom, £í více po£íta£ích a na této síti spou²t¥t uzly, které se testují. Protoºe emulace sít¥, °ízení test· a samotné vytvo°ení CWC by bylo mimo rozsah jedné bakalá°ské práce, pro emulaci sít¥ na jednom po£íta£i je vyuºita bakalá°ská práce Petra Prause a pro °ízení test· práce Slávky Jarom¥°ské. Na obrázku 6.1 je vid¥t základní struktura testování. Ve²keré testy °ídí Manager, který
Luboš Mátl CWC or Proxy
CWC or Proxy
...
CWC or Proxy
Petr Praus Tester Shaper
Slávka Jaroměřská Manager
Obrázek 6.1: Testování 31
32
KAPITOLA 6.
TESTOVÁNÍ
Tabulka 6.1: í°ka pásma serveru a uzl· sít¥ pouºité p°i testování Typ
Download [Mbps]
Upload [Mbps]
Server
100
100
USA
3
0,6
Praha CZ
9,3
2,2
UPC CZ
10,5
1,3
na£te scéná° testu, po²le Shaperu p°íkaz o nastavení sít¥, nakonec spustí uzly a p°ikáºe Testeru, které uzly a jak má testovat. Po dokon£ení test· Tester vytvo°í výsledný report. Více informací o testování, neº zde uvádím, lze nalézt nalézt v bakalá°ské práci Petra Prause [13] nebo Slávky Jarom¥°ské [7]. 6.1.1
Tester
Tester zastupuje webový prohlíºe£. Namísto zobrazování webové stránky v²ak pouze m¥°í £asy staºení jednotlivých soubor· této stránky. Protoºe na rozdíl od webového prohlíºe£e nerozumí HTML kódu, pot°ebuje seznam soubor·, které tvo°í celou testovací stránku. Umíst¥ní tohoto seznamu získá Tester od Managera, který p°íkazem zadá, £ím a co má testovat. Je moºné testovat více uzl· najednou, nebo tyto uzly testovat po sob¥. Záleºí na Manageru v jakém po°adí p°íkazy za²le. Komunikace mezi Managerem a Testerem probíhá p°es protokol TCP. Díky tomu Tester a Manager nemusí být na jednom po£íta£i. Na konci testování Manager m·ºe Tester poºádat o vytvo°ení reportu. Tento report obsahuje posloupnost jednotlivých test·. Obsahem výsledného reportu je seznam uzl·, které byly testovány a £asy, pot°ebné pro staºení celé stránky nebo jednotlivých soubor· stránky. Report m·ºe být ve formátu TEX [27] nebo CSV [17]. 6.1.2
Shaper
Shaper slouºí k vytvá°ení um¥lého sí´ového prost°edí na jednom po£íta£i. Vytvá°í tedy um¥lá sí´ová rozhraní, na kterých bude následn¥ Manager spou²t¥t jednotlivé uzly. Kaºdému tomuto rozhraní pak následn¥ m·ºe nastavit r·zné zpoºd¥ní (RTT) nebo ²í°ku pásma. 6.1.3
Manager
Manager prochází testovací scéná° a podle tohoto scéná°e vytvá°í uzly nebo zasílá p°íkazy Testeru a Shaperu. B¥hem provád¥ní scéná°e není nutný ºádný zásah uºivatele. Ve²keré zde uvád¥né testy jsou prací Slávky Jarom¥°ské, uvádím zde jen testy, které jsou d·leºité z hlediska ohodnocení CWC. Dal²í testy, které se týkají i postupného vývoje CWC lze nalézt v bakalá°ské práci Slávky Jarom¥°ské [7].
6.2.
33
NASTAVENÍ TESTOVACÍHO PROSTEDÍ
Tabulka 6.2: Porovnání webového prohlíºe£e a Testeru
6.2 6.2.1
Chrome
Tester
Chrome p°es proxy
Tester p°es proxy
11.23
11.13
11.32
11.76
Nastavení testovacího prost°edí Testovací stránky
Pro ú£ely testování byly vytvo°eny dv¥ testovací stránky. Po£et soubor· první testovací stránky a typy t¥chto soubor· byly zvoleny podle pr·m¥rných hodnot získaných z prvních TOP 10 stránek seznamu webové stránky alexa.com [21]. Protoºe webová stránka adresy www.centrum.cz [22] spl¬uje poºadavky pr·m¥rné stránky, byla testovací stránka vytvo°ena jednoduchým staºením v²ech soubor· této stránky. Stránka má celkovou velikost 799KB, po£et zdroj· stránky je 105. Pr·m¥rná velikost souboru stránky je 7.6KB. Druhá testovací stránka byla vytvo°ena podle jiº zmín¥né metriky poskytované spole£ností Google [23]. Tato testovací stránka má celkovou velikost 477.26KB a pr·m¥rná velikost jednoho souboru je 7.4KB. Krom¥ r·zné velikosti t¥chto dvou stránek je dal²ím rozdílem i rozloºení velikosti jednotlivých soubor·. I kdyº pr·m¥rná velikost souboru je u obou stránek tém¥° stejná, první testovací stránka obsahuje n¥které soubory významn¥ v¥t²ích velikostí neº stránka druhá. 6.2.2
P°enosové rychlosti
D·leºitým parametrem nastavení jsou p°enosové rychlosti, a to jak na stran¥ webového serveru tak na clientské stran¥. P°i testování byly pouºity t°i hodnoty rychlostí na clientské stran¥. Hodnota pro b¥ºnou domácnost státu USA, která byla p°evzata z publikace Speed Matters 2010: Report on Internet Speeds in All 50 States [1], a pr·m¥rné hodnoty p°enosovích rychlostí v²ech uºivatel·, vyuºívajících sluºeb internetového poskytovatele UPC pro celou eskou republiku a pro m¥sto Praha, p°evzaté z webové stránky pro m¥°ení rychlosti www.rychlost.cz [26]. Tyto hodnoty lze nalézt v tabulce 6.1. Hodnoty uploadu a downloadu webového serveru, byly pro v²echny testy stejné. 6.2.3
Zpoºd¥ní (RTT)
Jako poslední parametr nastavení testovacího prost°edí uvádím RTT mezi jednotlivými prvky sít¥. RTT je doba pot°ebná pro p°enos informace k cíli a zp¥t. Protoºe testujeme pouze homogenní sí´ a CWC stahuje statická data od nejbliº²ích uzl· peer-to-peer sít¥ je zpoºd¥ní mezi v²emi uzly sít¥ nastaveno stejn¥ na 20ms. Hodnota 20ms je výsledkem m¥°ení mezi dv¥ma b¥ºnými uºivateli, kte°í se nacházejí v Praze. Zpoºd¥ní mezi uºivatelem a webovým serverem bylo nastaveno na hodnotu 114ms. Tato hodnota byla získána m¥°ením 500 TOP webových stránek ºeb°í£ku webové stránky alexa.com. Pokud v popisu testu neuvedu jinak, pak má test nastaveny práv¥ tyto hodnoty RTT.
34 6.3
KAPITOLA 6.
TESTOVÁNÍ
Srovnání webového prohlíºe£e a testeru
Nejprve zde uvádím test samotného Testeru. Aby bylo moºné porovnávat nam¥°ené hodnoty s reálným pouºitím webového prohlíºe£e, musí být vyvinutý Tester podobn¥ rychlý jako webový prohlíºe£. V tabulce 6.2 jsou výsledky porovnání webového prohlíºe£e Chrome s Testerem, p°i stahování webové stránky o velikosti 1,26MB. Z d·vodu vy²²í p°esnosti byl kaºdý z t¥chto test· opakován 20-krát. Výsledkem jsou pr·m¥rné hodnoty doby staºení celé stránky. Pro m¥°ení £as· stahování stránky webovým prohlíºe£em Chrome, byl pouºit nástroj, který je p°ímo integrovaný v tomto prohlíºe£i. Nejprve byly proti sob¥ testovány Chrome a Tester, kte°í stahovaly testovací stránku p°ímo od webového serveru. Dále Chrome i Tester ke staºení stránky vyuºily Proxy. Tato Proxy je naprosto identická s Proxy CWC s tím rozdílem, ºe neobsahuje ºádné Pluginy ani Service a je tedy jen prost°edníkem mezi serverem a webovým prohlíºe£em nebo Testerem. RTT mezi clientem a serverem bylo v kaºdém testu nastavené na 114ms. Toto RTT je nastaveno vºdy mezi Proxy a serverem nebo Testerem/webovým prohlíºe£em a serverem. Mezi Testerem/webovým prohlíºe£em a Proxy není nastaveno ºádné RTT a ani ²í°ka pásma není nijak omezována. Download na clientské stran¥ byl nastaven na hodnotu Praha CZ. Na základ¥ výsledk· testování viz tabulka 6.2 m·ºeme tvrdit, ºe ve²keré testy provád¥né Testerem, komunikujícím s webovým serverem p°es Proxy, mají p°i pouºití samotného webového prohlíºe£e podobné výsledky a tudíº jsou porovnatelné. V²echny následující testy jsou provád¥ny pomocí Testeru a vºdy je mezi sebou porovnávána pouze Proxy a CWC. 6.4
Zatíºení webového serveru
Jedním z nejd·leºit¥j²ích cíl· CWC je sníºení zatíºení webového serveru. Proto bylo provedeno m¥°ení na stran¥ serveru. P°i tomto m¥°ení bylo postupn¥ spu²t¥no 40 uzl· Proxy nebo CWC a to tak, ºe vºdy po jedné vte°in¥ kaºdý dal²í nový uzel poºadoval testovací stránku. Jak lze vid¥t z obrázku 6.2, po£et poºadavk· na server p°i pouºití CWC významn¥ klesl. Ve chvíli kdy se v Distribuované cache jiº nacházejí v²echny statické soubory stránky, ostatní uzly sm¥rují poºadavky na tyto soubory do peer-to-peer sít¥ a jiº nezat¥ºují webový server. Z grafu je patrné, ºe p°ibliºn¥ po 5 vte°inách jsou v²echny statické zdroje stránky uloºeny v Distribuované cache a poºadavky sm¥°ující na webový server jsou jiº jen na dynamické soubory webové stránky. Oproti tomu Proxy v celém pr·b¥hu testu zna£n¥ zat¥ºovalo webový server. Obrázek 6.3 obsahuje graf ukazující mnoºství p°ená²ených dat od webového serveru v £ase. Op¥t je zde vid¥t, ºe CWC zna£n¥ sniºuje mnoºství p°ená²ených dat od serveru, tedy i zatíºení webového serveru. 6.5
Porovnání jednotlivých strategií
V této £ásti testování budu porovnávat jednoduchou strategii stahování se strategií p°edstahování. Stejn¥ jako p°i p°edchozím testování byly postupn¥ po n¥jakém £ase spou²t¥ny uzly, které stahovaly celou testovací stránku. Na rozdíl od p°edchozího testu byl vºdy dal²í uzel spu²t¥n aº po £ase, který p°edchozí uzel pot°eboval ke staºení testovací stránky. Kaºdým uzlem, který stáhl celou testovací stránku, se mnoºství poskytovatel· statického obsahu zvý²ila. Výsledkem kaºdého testu je £as staºení celé stránky jedním uzlem.
35
POROVNÁNÍ JEDNOTLIVÝCH STRATEGIÍ
Sheet2 70 60
počet požadavků
50 40 30 20 Proxy CWC
10 0 0
5
10
15
20
25
30
35
40
čas [s]
Obrázek 6.2: Zatíºení serveru - po£et poºadavk·
Sheet2 600
500
přenesená data [kB]
6.5.
400
300
200 Proxy CWC
100
0
1
5
10
15
20
25
30
35
40
čas [s]
Page 1
Obrázek 6.3: Zatíºení serveru - mnoºství p°ená²ených dat
36
KAPITOLA 6.
TESTOVÁNÍ
Sheet1 Předstahování Jednoduchá metoda
7000
čas [ms]
6500
6000
5500
5000
4500 1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
počet uzlů
Obrázek 6.4: as stahování testovací stránky Cenrum pro jednotlivé strategie Sheet2 2800 2700 2600
čas [ms]
2500 2400 2300 2200 2100 2000
jednoduchá metoda předstahování
1900 1800
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
počet uzlů
Obrázek 6.5: as stahování testovací stránky Google pro jednotlivé strategie Na obrázku 6.4 je graf popisující toto testování na první testovací stránce (stránce Centrum ). Lze vid¥t, ºe uzly vyuºívající metodu p°edstahování jsou zna£n¥ rychlej²í. Pro toto testování byly nastaveny hodnoty ²í°ky pásma v²ech uzl· na Praha CZ (viz 6.1) a RTT mezi Page 5 uzly i mezi webovým serverem a uzly na 20ms.
V druhém grafu na obrázku 6.5 mezi strategiemi jiº tak velký rozdíl není. Zde je k testu pouºita stránka vytvo°ena podle metriky od spole£nosti Google, která obsahuje velký po£et malých soubor·. Tyto soubory jsou tak malé, ºe v metod¥ p°edstahování maximální po£et paraleln¥ odeslaných anycast· není omezen velikosti v²ech p°ijímaných soubor·, ale je omezen frameworkem FreePastry, který dovolí odeslat najednou pouze 30 anycast·. e²ením tohoto problému, by mohlo být spojování malých soubor· do jednoho celku, který by byl stahován najednou. 6.5.1
P°edstahování
Jako d·kaz tohoto tvrzení uvádím grafy na obrázcích 6.6 a 6.7. Obsahují informaci o mnoºství dat stahovaných 25. uzlem p°i pouºití metody p°edstahování. V²echny ostatní uzly jiº ve své
Page 1
6.5.
37
POROVNÁNÍ JEDNOTLIVÝCH STRATEGIÍ
Sheet1 8
stahovaná data [Mbps]
7 uzel 24 uzel 23 uzel 22 uzel 21 uzel 20 uzel 19 uzel 18 uzel 17 uzel 16 uzel 15 uzel 14 uzel 13 uzel 12
6 5 4 3 2 1 0 0
0,5
1
1,5
2
2,5
uzel 11 uzel 10 uzel 9 uzel 8 uzel 7 uzel 6 uzel 5 uzel 4 uzel 3 uzel 2 uzel 1 server
3
čas [s]
Obrázek 6.6: Mnoºství stahovaných dat 25 uzlu - Centrum Sheet1
7
stahovaná data [Mbps]
6
uzel 24 uzel 23 uzel 22 uzel 21 uzel 20 uzel 19 uzel 18 uzel 17 uzel 16 uzel 15 uzel 14 uzel 13 uzel 12
5 4 3 2 1 0 0
0,5
1
1,5
uzel 11 uzel 10 uzel 9 uzel 8 uzel 7 uzel 6 uzel 5 uzel 4 uzel 3 uzel 2 uzel 1 server
2
čas [s]
Obrázek 6.7: Mnoºství stahovaných dat 25 uzlu - Google pam¥ti obsahují statická data testovací stránky a 25. uzel si tedy m·ºe vybírat, od koho bude statické soubory stahovat. R·zné barvy graf· znamenají stahování dat od r·zných uzl·. Kaºdá barva tedy p°edstavuje staºení jednoho statického souboru webové stránky od jednoho uzlu. Z graf· je tedy vid¥t, ºe uzel stahuje statické soubory najednou od mnoha uzl· z peer-to-peer sít¥. Jak jiº bylo °e£eno, statické soubory první testovací Page 1 stránky mají mnohem v¥t²í velikost. Díky tomu zde dosahuje rychlost stahování dat aº 8Mbps (6.6). V p°ípad¥ druhé stránky dosahuje CWC, z d·vodu omezení na maximáln¥ 30 paraleln¥ odesílaných anycast·, rychlosti pouze kolem 6Mbps (6.7). Proto také p°i stahování této testovací stránky není metoda p°edstahování tak efektivní. 6.5.2
Jednoduchá metoda stahování
Pro jednoduchou metodu stahování jsou výsledky testu mnohem hor²í, protoºe CWC p°edem nezná ºádné informace o souborech webové stránky a proto také nem·ºe ºádným zp·sobem
38
KAPITOLA 6.
TESTOVÁNÍ
List1 4,5 4 peer peer peer peer peer peer peer peer peer peer peer peer peer
stahovaná data [Mbps]
3,5 3 2,5 2 1,5 1 0,5
24 23 22 21 20 19 18 17 16 15 14 13 12
peer 11 peer 10 peer 9 peer 8 peer 7 peer 6 peer 5 peer 4 peer 3 peer 2 peer 1 server
0 0
0,5
1
1,5
2
2,5
3
3,5
4
4,5
čas [s]
Obrázek 6.8: Mnoºství stahovaných dat 25 uzlu - Centrum kontrolovat mnoºství najednou stahovaných soubor·. Pouºitím této metody je CWC závislý na webovém prohlíºe£i tím, ºe posílá poºadavky do peer-to-peer sít¥ aº ve chvíli, kdy od n¥j dostane HTTP dotaz na soubor. Jak je vid¥t z grafu na obrázku 6.8, maximální mnoºství stahovaných dat je p°i stahování první testovací stránky (stránky Centrum ) okolo 4Mbps. Toto je niº²í hodnota neº p°i pouºití metody p°edstahování, z £ehoº je vid¥t, ºe je tato metoda mén¥ ú£inná. 6.5.3
Rozd¥lování soubor·
Pro zkrácení bakalá°ské práce zde neuvádím výsledky testování metody p°edstahování s p°enosem soubor· po £ástech. Tato metoda nebyla efektvivní z d·vodu omezení 30 paralelních anycast· odeslaných najednou. Rychlosti staºení celé testovací stránky se pohybovaly od 8s do 10s, coº, p°i porovnání s výsledky p°edchozích test·, je velmi ²patný výsledek. 6.6
Porovnání CWC a proxy
Pro vyhodnocení zda a v jakých p°ípadech je CWC lep²í neº sou£asné °e²ení stahování webových stránek, se v t¥chto testech mezi sebou porovnává samotná Proxy a CWC. P°edchozím testováním bylo zji²t¥no, ºe metoda p°edstahování má lep²í výsledky neº jednoduchá metoda stahování a proto pro porovnání s Proxy, bude CWC vyuºívat metodu p°edstahování. Stránka 1
6.6.1
RTT webového serveru
Je p°edem z°ejmé, ºe pokud RTT mezi uºivatelem a webovým serverem bude men²í, neº mezi jednotlivými uºivateli sít¥, systém CWC bude pomalej²í, neº b¥ºné staºení webové stránky p°ímo od webového serveru. V této £ástí testování se zji²´uje, jak velké musí být RTT webového serveru, aby se z hlediska rychlosti stahování stránky vyplatilo vyuºít systém CWC. Grafy 6.9, 6.10 porovnávají rychlosti staºení testovacích stránek pomocí CWC nebo
39
POROVNÁNÍ CWC A PROXY
Sheet1
čas stažení webové stránky [s]
25
20
15
praha cwc upc cwc usa cwc praha proxy upc proxy usa proxy
10
5
55
0 10
95
210
90
170
250
330
zpoždění od uživatele k webovému serveru [ms]
Obrázek 6.9: as staºení testovací stránky p°i r·zném RTT serveru - Centrum
Sheet1 10 9
čas stažení webové stránky [s]
6.6.
8 7 6
praha cwc upc cwc usa cwc praha proxy upc proxy usa proxy
5 4 3 2 1 35 55
0 10
75 90
170
zpoždění od uživatele k webovému serveru [ms]
Obrázek 6.10: as staºení testovací stránky p°i r·zném zpoºd¥ní serveru - Google
Page 1
40
KAPITOLA 6.
TESTOVÁNÍ
List1 1600 Alexa TOP500 Praha (63.4%) UPC (60.2%) USA (22.2%)
1400 1200
RTT [ms]
1000 800 600 400 200 0
100 1
300 200
500 400
pořadí Alexa TOP500
Obrázek 6.11: RTT Alexa TOP 500 webových stránek Proxy pro r·zné RTT p°enosu dat mezi webovým serverem a uºivatelem. Z test· vyplývá, ºe pro testovací stránku Centrum je z hlediska rychlosti výhodn¥j²í pouºít CWC p°i RTT webového serveru v¥t²ím neº 55ms - Praha CZ, 95ms - UPC CZ a 210ms - USA. Stránka Google, která je tém¥° o polovinu men²í, se bude stahovat rychleji p°i zpoºd¥ní v¥t²ím neº 35ms - Praha CZ, 55ms - UPC a 75ms - USA. V grafu na obrázku 6.11 je vid¥t RTT TOP 500 webových stránek z ºeb°í£ku Alexa, m¥°eno praºským uºivatelem. Z grafu je patrné, ºe pro nastavení ²í°ky pásma Praha CZ se z tohoto ºeb°í£ku vyplatí stahovat s pouºitím CWC 63.4% webových stránek, pro nastavení UPC CZ 60,2% webových stránek a pro USA uº jen 22.2%. Zatímco pro nastavení Praha CZ a UPC CZ se pouºití CWC vyplatí, pro b¥ºnou americkou domácnost je CWC z hlediska uºivatele nevýhodná. 6.6.2
Po£et uºivatel·
Posledním testováním je porovnání Proxy a CWC p°i r·zném po£tu uºivatel·. P°i pouºití samotné Proxy, doba staºení testovací stránky, p°i zvy²ujícím se po£tu uºivatel· poºadujících stejnou webovou stránku najednou, stoupá. V p°ípad¥ CWC se rychlost nijak nem¥ní, protoºe uzly stahují v¥t²inu soubor· webové stránky od ostatních uzl· sít¥. Pro tento test bylo nastaveno zpoºd¥ní mezi uzly na 20ms a zpoºd¥ní mezi webovým serverem a uzlem na 114ms. Stránka 1 Graf na obrázku 6.12 ukazuje, ºe p°i velkém po£tu uºivatel· je CWC mnohem rychlej²í. 6.7 6.7.1
Srovnání s existujícími °e²eními Akamai
Sou£asným nejlep²ím °e²ením pro poskytovatele webových stránek je vyuºití sluºeb Akamai. Tím, ºe Akamai vyuºívá velké mnoºství server·, dosahuje zna£ného zrychlení z uºivatel-
6.7.
41
SROVNÁNÍ S EXISTUJÍCÍMI EENÍMI
Sheet1_2
čas stažení webové stránky [ms]
7500 7000 6500 6000 5500 5000
Předstahování Proxy – 1 uzel Proxy – 20 uzlů Proxy – 30 uzlů Proxy – 40 uzlů
4500 4000 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
počet uzlů
Obrázek 6.12: as stahování stránky metodou p°edstahování a samotnou Proxy, pro r·zný po£et uºivatel· ského hlediska. Navíc zatíºení webového serveru se také zna£n¥ sníºí. Jednou z hlavních výhod Akami je skute£nost, ºe existuje ur£itá spolupráce mezi originálním serverem a Edge servery (Servery Akamai, které zrychlují provoz cashováním webového obsahu). Nap°íklad pokud nastane zm¥na obsahu na originálním serveru, edge servery jsou o tom informovány a automaticky na£tou nový obsah. Akamai také m·ºe sdílet nem¥nné £ásti dynamického obsahu a to tak, ºe v HTML kódu lze p°idat speciální zna£ky, které dávají informaci o cashovatelných £ástech t¥chto dat. Hlavní nevýhodou a i d·vodem pro vznik CWC je, jak jiº bylo °e£eno, cena za poskytování t¥chto sluºeb. 6.7.2
Squirel
Nejpodobn¥j²í systému CWC je Squirel. Pro p°edstavu porovnání uvedu skute£nost, ºe v systému Squirel ve²keré poºadavky na soubory v peer-to-peer síti sm¥°ují na Home-node. Tento uzel má nodeId nejblíºe ke klí£i zprávy. V Home-store p°ístupu musí Home-node v²echny poºadavky vy°ídit sám. To pro tento uzel m·ºe znamenat zna£né zatíºení. ím nav²t¥vovan¥j²í bude webová stránka, tím víc uºivatel· bude od tohoto uzlu poºadovat soubor, který tato webová stránka obsahuje. Oproti tomu °e²ení Directory zát¥º rozkládá mezi ostatní uzly, které mají jiº soubor staºený, ale v²echny poºadavky stále sm¥°ují p°es Home-store uzel. Tato nevýhoda m·ºe p°i velkém po£tu uºivatel· zna£n¥ zpomalit stahování statických dat z peer-to-peer sít¥. CWC oproti tomuto °e²ení vytvá°í Scribe skupiny. Z tého skupiny je vºdy Page 1 vybrán anycastem náhodný uzel, který poºadavek vy°e²í a navíc je tento uzel vybírán metodou, která zaji²´uje, ºe bude také co do vzdálenosti jedním z nejbliº²ích uzl· k odesílateli anycastu. Kaºdý anycast na skupinu sice sm¥°uje na uzel, který reprezentuje ko°en stromu Scribe skupiny, ale v¥t²inou tento anycast ke ko°enovému uzlu nedorazí, protoºe se zastaví na jednom z uzl· skupiny, kterými zpráva prochází. Díky tomu v²echny poºadavky na statické soubory nesm¥rují na jeden uzel, jako je tomu v p°ípad¥ Squirelu.
42
KAPITOLA 6.
TESTOVÁNÍ
Kapitola 7
Záv¥r Cílem práce bylo analyzovat slabá místa sou£asného °e²ení distribuce webových aplikací a vytvo°ení systému pro vylep²ení distribuce pomocí peer-to-peer sít¥. Tento systém byl vytvo°en a otestován. Podle výsledk· test· systém spl¬uje sv·j ú£el, tedy sniºuje zatíºení webového serveru a v ur£itých p°ípadech zrychluje na£ítání stránek na stran¥ clienta. Systém má zatím mnoho nevýhod a k reálnému pouºití systému vede je²t¥ dlouhá cesta. Jak vyplývá z test· jednoduché metody stahování, webový prohlíºe£ ne vºdy optimáln¥ vysílá poºadavky na soubory stránky. Prohlíºe£ nemá dostate£né informace o t¥chto souborech na to, aby mohl optimalizovat p°enos t¥chto dat. Metoda p°edstahování, díky informaci o velikosti souboru, m·ºe optimáln¥ rozkládat stahování soubor· v závislosti na moºnostech sít¥. Proto tato metoda také v testech dopadla nejlépe, dokonce v ur£itých p°ípadech i lépe neº p°ímé stahování webové stránky od serveru. Protoºe v²echny dotazy na soubory stránky nesm¥°ují p°ímo na webový server, je tento server mnohem mén¥ zatíºený. Pokud nebudeme po£ítat generování dynamických £ástí webové stránky, je zatíºení webového serveru men²í o více neº 90%. Jako hlavní nevýhodu CWC vidím nutnost vyuºívat hardwarových prost°edk· na uºivatelské stran¥. Neochota poskytovat by´ jen malou £ást hardwaru a neznalost uºivatel· bude velkou p°ekáºkou pro reálné nasazení tohoto systému.
7.1 7.1.1
Dal²í pokra£ování práce Sociální sí´
Peer-to-peer sí´, pouºívaná pro sdílení soubor· webových stránek, m·ºe být také velkým informa£ním zdrojem, poskytujícím informace nap°íklad o tom, která stránka je podobná té, kterou práv¥ uºivatel sleduje. Jako p°íklad je moºné uvést situaci, kdy uºivatel hledá informace o ur£itém zboºí. Pokud toto zboºí má na sledované stránce umíst¥ný obrázek, lze pomocí tohoto obrázku nalézt dal²í stránky, které obsahují stejný obrázek. Dal²ím p°íkladem mohou být internetové noviny. Pokud uºivatel vyhledává informace o události, kterou sleduje, je moºné pomocí této sociální sít¥ nalézt dal²í £lánky, které obsahují stejnou informaci na stránce (nap°. fotogra e). 43
44 7.1.2
KAPITOLA 7.
ZÁV
R
Bezpe£nost
Vzhledem k rozsahu práce a skute£nosti, ºe cílem práce byl pouze výzkum toho, zda lze vytvo°it Decentralizovanou Webovou Cache a zda tato cache bude dostate£n¥ rychlá, tak aby byla vyuºitelná v praxy, nebyla zde v·bec diskutována bezpe£nost uºivatel·. Lze nalézt mnoho zp·sob·, jak jeden uzel m·ºe úto£it na druhý nebo na celou sí´. Nap°íklad libovolný uzel m·ºe poskytovat ²patný nebo upravený soubor (nap°. soubor s enormní velikostí), zpoº¤ovat ostatní uºivatele tím, ºe tento uzel nebude odpovídat na poºadavky souborem ani zprávou o chyb¥. Také uzel m·ºe posílat do peer-to-peer sít¥ mnoho anycast·, a tak zahltit sí´ mnoha poºadavky najednou. V²echny tyto útoky, ale nemohou být cílené k napadení ur£itého uzlu, protoºe anycast dorazí vºdy k náhodn¥ vybranému uzlu ze skupiny, pokud tedy uzel není jediným £lenem skupiny. 7.1.3
Plugin do webového prohlíºe£e
Jak jiº je popsáno vý²e, jednou z moºností, jak CWC vyuºít, je vytvo°ení Pluginu do webového prohlíºe£e. Z hlediska uºivatele je toho °e²ení mnohem pouºiteln¥j²í, protoºe spu²t¥ní Proxy serveru a nastavení webového prohlíºe£e tak, aby stahoval data p°es tuto proxy a nepouºíval p°i tom svou lokální cache, není pro b¥ºného uºivatele úpln¥ snadné. Dal²í výhoda spo£ívá v odstran¥ní sí´ové komunikace mezi prohlíºe£em a Proxy, která zbyte£n¥, i kdyº málo, zpomaluje p°enos dat. Z hlediska CWC pro zm¥nu implementace sta£í nahradit vrstvu Proxy vrstvou, která dokáºe p°ímo komunikovat s prohlíºe£em. Bohuºel kaºdý webový prohlíºe£ neumoº¬uje snadnou implementaci Plugin·, navíc pro kaºdý prohlíºe£ je nutné vytvo°it vlastní Plugin. Výhodou sou£asného °e²ení je tedy univerzálnost. 7.1.4
Vyuºití serveru
Jedním z moºných °e²ení na vylep²ení sít¥, je za°adit webový server jako £lena peer-to-peer sít¥. Tento uzel by byl stálým £lenem v²ech skupin, které poskytují soubory z webového obsahu tohoto serveru. Jednou z výhod tohoto °e²ení je moºnost serveru informovat o zm¥n¥ dat ve chvíli, kdy se tyto data na serveru skute£n¥ zm¥ní nebo poskytování seznamu soubor·, které má kaºdý uºivatel z peer-to-peer sít¥ stáhnout pro správné zobrazení dané webové stránky. Dále je moºné, aby server ozna£il, které £ásti dynamického obsahu jsou stále stejné a ty, které se m¥ní. To by umoºnilo sdílet v peer-to-peer síti i £ásti dynamických dat. 7.1.5
Manycast
Z d·vodu omezení maximálního po£tu sou£asn¥ vyslaných anycast· na hodnotu 30 je °e²ení s rozd¥lováním soubor· na £ásti velmi pomalé. Na kaºdou £ást souboru musí uzel vyslat jeden anycast, £ímº se docílí toho, ºe kaºdá £ást souboru se bude (s ur£itou pravd¥podobností v závislosti na velikosti skupiny) stahovat od jiného uzlu. Díky omezení po£tu sou£asn¥ odeslaných anycast· m·ºeme najednou p°ijímat jen 30 £ástí poºadovaných soubor· najednou. Toto £íslo je pro efektivní vyuºití metody rozd¥lování soubor· p°íli² nízké. Navíc £ím v¥t²í je po£et odeslaných anycast· tím v¥t²í je i neºádoucí zatíºení sít¥. Tyto problémy by mohl vy°e²it manycast. Tento manycast by p°ijal takový po£et £len· Scribe skupiny uzl·, majících uloºený hledaný soubor v lokální pam¥ti, kolik je £ástí souboru. Tím, ºe na jeden soubor
7.1.
DALÍ POKRAOVÁNÍ PRÁCE
45
bude odeslán pouze jeden manycast, mizí problém s omezením 30 anycast· odeslaných najednou. Bohuºel manycast není implementován ve FreePastry frameworku a bylo by nutné ho doimplementovat.
46
KAPITOLA 7.
ZÁV
R
Literatura [1] Speed matters aordable high speed internet for america. Technical report, 2010. [2] G. Camarillo and IAB. Peer-to-Peer (P2P) Architecture: De nition, Taxonomies, Examples, and Applicability. RFC 5694 (Informational), Nov. 2009. [3] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. Scalable Application-Level Anycast for Highly Dynamic Groups. pages 4757. Springer-Verlag, 2003. [4] P. Druschel. Freepastry an open-source implementation of pastry. http://www.freepastry.org/FreePastry/, stav z 13. 5. 2011. [5] R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee. Hypertext Transfer Protocol HTTP/1.1. RFC 2616 (Draft Standard), June 1999. Updated by RFCs 2817, 5785. [6] S. Iyer, A. Rowstron, and P. Druschel. Squirrel: A decentralized peer-to-peer web cache. In Proceedings of the twenty- rst annual symposium on Principles of distributed computing, pages 213222. ACM, 2002. [7] S. Jarom¥°ská. Environment for peer-to-peer application simulation with application on cooperative web cache. Czech Technical University in Prague, Faculty of Electrical Engineering, Bachelor thesis, 2011. [8] R. Meunier. The pipes and lters architecture, pages 427440. ACM Press/AddisonWesley Publishing Co., New York, NY, USA, 1995. [9] P. Mockapetris. Domain names - implementation and speci cation. RFC 1035 (Standard), Nov. 1987. Updated by RFCs 1101, 1183, 1348, 1876, 1982, 1995, 1996, 2065, 2136, 2181, 2137, 2308, 2535, 2845, 3425, 3658, 4033, 4034, 4035, 4343, 5936, 5966. [10] E. Nygren, R. K. Sitaraman, and J. Sun. The akamai network: a platform for highperformance internet applications. SIGOPS Oper. Syst. Rev., 44:219, August 2010. [11] J. Postel. User Datagram Protocol. RFC 768 (Standard), Aug. 1980. [12] J. Postel. Transmission Control Protocol. RFC 793 (Standard), Sept. 1981. Updated by RFCs 1122, 3168, 6093. [13] P. Praus. Framework for network management to support simulation of varying network conditions. Czech Technical University in Prague, Faculty of Electrical Engineering, Bachelor thesis, 2011. 47
48
LITERATURA
[14] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable contentaddressable network. In Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, SIGCOMM '01, pages 161172, New York, NY, USA, 2001. ACM. [15] Y. Rekhter, B. Moskowitz, D. Karrenberg, G. J. de Groot, and E. Lear. Address Allocation for Private Internets. RFC 1918 (Best Current Practice), Feb. 1996. [16] A. I. T. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, Middleware '01, pages 329350, London, UK, 2001. Springer-Verlag. [17] Y. Shafranovich. Common Format and MIME Type for Comma-Separated Values (CSV) Files. RFC 4180 (Informational), Oct. 2005. [18] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. SIGCOMM Comput. Commun. Rev., 31:149160, August 2001. [19] B. Swen. Outline of initial design of the structured hypertext transfer protocol. J. Comput. Sci. Technol., 18:287298, May 2003. [20] Akamai customer list. http://www.akamai.com/html/customers/customer_list.html, stav z 8. 5. 2011. [21] Alexa top 500 global sites. http://www.alexa.com/topsites, stav z 5. 5. 2011. [22] Centrum. http://www.centrum.cz/, stav z 5. 5. 2011. [23] Google web metrics: Size and number of resources. http://code.google.com/intl/cs-CZ/speed/articles/web-metrics.html, stav z 8. 5. 2011. [24] Java 2 platform standard edition 5.0 api speci cation. http://download.oracle.com/javase/1.5.0/docs/api/index.html, 5. 5. 2011.
stav
z
[25] Netty project. http://www.jboss.org/netty, stav z 13. 5. 2011. [26] Rychlost.cz test rychlosti p°ipojení k internetu. http://rychlost.cz/, stav z 5. 5. 2011. [27] Wikipedia tex. http://http://en.wikipedia.org/wiki/Tex_(unit)#Tex, stav z 5. 5. 2011. [28] B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and. Technical report, Berkeley, CA, USA, 2001.
P°íloha A
Pouºité zkratky CWC
Cooperative Web Cache
HTML IP
HyperText Markup Language
Internet Protocol
DNS
Domain Name System
P2P
Peer To Peer
TCP
Transmission Control Protocol
UDP
User Datagram Protocol
CSS
Cascading Style Sheets
HTTP
Hypertext Transfer Protocol
URL
Uniform Resource Locator
NIO
New I/O
RTT
Round Trip Time
49
50
PÍLOHA A.
POUITÉ ZKRATKY
P°íloha B
Úºivatelská p°íru£ka B.1
Spu²t¥ní
CWC se spou²tí stejn¥ jako jákákoliv jiná aplikace napsaná v programovacím jazyku Java z p°íkazové °ádky p°íkazem:
java -jar CWC.jar [parametry] B.2
Parametry
-h nebo -help
vypí²e nápov¥du
-chunk-size velikost
velikost £ástí soubor·, na které se budou soubory rozd¥lovat, p°i pouºití metody p°edstahování
-dcache-boot IP:port
IP adresa a port, jiného uzlu, pomocí kterého se CWC p°ipojuje do peer-to-peer sít¥. Pokud je tento uzel první zadá svou IP adresu a port. Není-li tato hodnota nastavena CWC se chová jako Proxy
-dcache-local-port port
port na kterém CWC poslouchá v peer-to-peer síti
-dcache-receiver-port port
pokud pouºíváme jiný zp·soub odesílání soubor· neº p°es Pastry, nastavuje se port systému, který bude p°ijímat soubory
-debug
tento parametr slouºí pro ú£ely lad¥ní, vypisuje do logu podrobné informace o zpracování p°íkaz·
-local-ip IP
IP adresa na které bude CWC naslouchat
-max-group-requests-size velikost jednu skupinu v KB
-max-requests-size velikost skupiny v KB
maximální velikost najednou p°ijímaných dat pro
maximální velikost najednou p°ijímaných dat pro v²echny
51
52
PÍLOHA B.
ÚIVATELSKÁ PÍRUKA
-proxy-port port
port na kterém proxy naslouchá, p°es tento port je webový prohlíºe£ p°ipojen k CWC
-p
pokud je zadán tento parametr, CWC pouºívá metodu p°edstahování
P°íloha C
Obsah p°iloºeného CD P°iloºené CD je rozd¥leno do n¥kolika adresá°·:
doc
text bakalá°ské práce v elektronické podob¥
source tests dist
zdrojový kód programu CWC
jednotkové testy programu CWC zkompilovaný program CWC
gures
obrázky vyuºité v bakalá°ské práci
53
