Elosztott adatbázisok és peerto-Peer (P2P) Simon Csaba
[email protected]
Miről lesz szó? Mi a P2P? Kell-e nekünk és miért? Struktúrálatlan P2P ---------- DHT ---------- Elosztott P2P adatbázisok
2
2013. október 16.
P2P
Mi a P2P?
P2P - napjaink egyik legforróbb témája
Alkalmazások
Kazaa – minden idők legtöbbször letöltött alkalmazása
Az Internet forgalom 50-70% P2P
> 300 millió letöltés Nehezen mérhető, az eredmények nem megbízhatóak
FastTrack, eDonkey, iMesh
> 7 millió felhasználó (2004. február 8) Felhasználói statisztikák: http://www.slyck.com/
4
2013. október 16.
P2P (II)
Kutatás
3rd IEEE International Conf. on P2P Computing P2P „Tutorial” és P2P szekció
Infocom, Sigcomm, stb.
P2P Research Group
IRTF (Internet Research Task Force) http://www.irtf.org/charters/p2prg.html
Internet2 http://p2p.internet2.edu/index.html
Stanford, Berkeley, stb.
5
2013. október 16.
Definíció
Peer–to–Peer (P2P):
egy alkalmazáscsoport mely kihasználja az Internet peremén levő felhasználók erőforrásait:
Tárolás – merevlemez kapacitás CPU – számítási kapacitás Tartalom – adatok, informaciók megosztása Bármilyen más megosztható erőforrás, szolgáltatás, funkció
Egy alkalmazás rétegbeli Internet a fizikai Internet topológia fölött 6
2013. október 16.
Definíció (II)
„Peer-to-peer network” = egyenrangú hálózat
„Peer” = veled egyenrangú felhasználó
„Kommunista” rendszer – mindenki egyenlő A kliens-szerver architektúra ellentéte
7
2013. október 16.
Ádámtól Ádámig A. Oram, editor. Peer-to-Peer : Harnessing the Power of Disruptive Technologies. O'Reilly & Associates, 2001.
8
2013. október 16.
Jellemzők
Minden résztvevő peer egyszerre kliens és szerver Nincs központi vezérlés Nincs központi adatbázis Senkinek nincs globális képe a hálózatról A rendszer globális működése a lokális kölcsönhatások eredménye
9
2013. október 16.
Jellemzők (II)
Bármilyen megosztott erőforrás elérhető bárki által Akkor férhetsz mások erőforrásaihoz, ha megosztod a sajátaidat A peer-ek függetlenek egymástól A peer-ek és a kapcsolatok alapvetően megbízhatatlanok
Gyakori be- és kilépés
10
2013. október 16.
Mire jó?
P2P ≠ fájlcsere
Sokminden más:
Elosztott adatbázisok Elosztott számítás (distributed computing) Elosztott hálózati szuperszámítógépek (grid computing) Instant Messaging CSCW (Computer Supported Cooperative Work) Vezetéknélküli ad-hoc hálózatok Alkalmazás rétegbeli multicast szolgáltatás E-commerce, e-business alkalmazások Stb, stb, stb.... 11
2013. október 16.
Miről lehet beszélni P2P kapcsán? Gnutella
WinMX
ICQ BearShare
FastTrack
Morpheus
Chord
MP2P
Pastry
Blubster
CAN
Shareaza
DirectConnect
eDonkey
Jabber
Yoid
Freenet iMesh
Jxta
OverCast
Grokster
@SETI RockitNet
eBay
OceanStore eMule
Napster SoulSeek
BitTorrent Mojo Nation
IRC
Farsite
Piolet LimeWire
Tapestry
Kazaa 12
2013. október 16.
Pontosabban...
Visszatekintés
„korabeli” P2P rendszerek
Usenet, DNS, Telnet, FTP
az Internet átalakulása az új generációs P2P rendszerek megjelenése
A P2P hálózatok sajátosságai:
Szolgáltatás felderítés, topológia felépítés Keresés, útvonalválasztás Hozzáférhetőség, megbízhatóság Biztonsági kérdések 13
2013. október 16.
És még...
P2P architektúrák:
Központosított rendszerek – Napster Elosztott, sík rendszerek – Gnutella Hierarchikus topológiák – Kazaa Más fájlcserélő alkalmazások – BitTorrent, stb.
Elosztott hash táblákra (DHT) alapuló keresők:
CAN, Chord, Pastry, Tapestry
14
2013. október 16.
Továbbá ...
Alkalmazás rétegbeli multicast P2P hálózatokon
A csoportos kommunikáció sajátosságai A hálózati rétegbeli multicast rövid attekintése Alkalmazás rétegbeli multicast
P2P hálózatok
Háló-alapú (mesh-first) módszerek – Narada, Gossamer Fa-alapú (tree-first) módszerek – HMTP, TBCP, Yoid, Overcast, ALMI Implicit módszerek – CAN-Multicast, Scribe, Bayeux, NICE Pletykára alapuló járványszerű átvitel – SCAMP , SWIM, Bi-modal multicast
15
2013. október 16.
P2P és elosztott adatbázisok
Hypothesis
End 2 End arguments in network community
Fast development of applications
Implement a feature on upper layer as much as we can to have easier deployment for Internet Moore law in computer hardware
Relatively slow change in Internet core
Not too many industrial researchers who work on core networking. (http://www.icir.org/floyd/talks/NSF-Jan03.pdf)
2013. október 16.
Key problem: Location and Routing
Hard problem in a system like this:
Locating and messaging to resources and data
Goals for a wide-area overlay infrastructure
Easy to deploy Scalable to millions of nodes, billions of objects Available in presence of routine faults Self-configuring, adaptive to network changes Localize effects of operations/failures
2013. október 16.
The promise of P2P computing
Reliability: no central point of failure
High capacity through parallelism:
Many replicas Geographic distribution Many disks Many network connections Many CPUs
Automatic configuration Useful in public and proprietary settings
2013. október 16.
20
2013. október 16.
DHT implementation challenges 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Scalable lookup Balance load (flash crowds) Handling failures Coping with systems in flux Network-awareness for performance Robustness with untrusted participants Programming abstraction Heterogeneity Anonymity Indexing
Chord
Goal: simple, provably-good algorithms 2013. október 16.
Pond
JNI for crypto, SEDA stages, 280+kLOC Java 2013. október 16.
Strukturálatlan P2P
23
Visszatekintés
A P2P nem egy új ötlet A kezdeti Internet peer-to-peer volt
ARPANET - Advanced Research Projects Agency Network
1969 – US Department of Defense (DoD)
University of California at Los Angeles (UCLA) Stanford Research Institute (SRI) University of California Santa Barbara (UCSB) University of Utah
Különböző operációs rendszerek, egyenrangú felhasználók
24
2013. október 16.
A kezdeti hálózat
25
2013. október 16.
70-es évek
újabb és újabb egyetemek, kutató laboratóriumok csatlakoznak TCP/IP kidolgozása Telnet, FTP
26
2013. október 16.
ARPANET - 1977
27
2013. október 16.
80-as évek
1983. 01. 01 – IP az ARPANET-en 1984 – MILNET (DoD) 1986 – NSFNET
NSF – National Science Foundation
1990 – Az ARPANET bezár
28
2013. október 16.
MILNET - 1989
29
2013. október 16.
Irodalom
A History of The Internet: 1962 – 1992
Hobbes' Internet Timeline
http://www.zakon.org/robert/internet/timeline/
The Request for Comments Reference Guide
http://www.computerhistory.org/exhibits/internet_history/
http://www.ietf.org/rfc/rfc1000.txt
History of Arpanet
http://www.dei.isep.ipp.pt/docs/arpa.html
30
2013. október 16.
A kezdeti hálózat
Egyenrangú felhasználók Bármely két gép képes volt kommunikálni egymással Egy nyított és szabad rendszer
Tűzfalak nem léteztek a 80-as évek végéig
Egyetemi kutatók „játszótere” Biztonsági gondok nem léteztek ...
31
2013. október 16.
Az első P2P alkalmazások
Telnet, FTP
Nem „vérbeli” P2P alkalmazások Szigorúan nézve, kliens/szerver rendszerek
Egy Telnet kliens bejelentkezik egy szerverre Egy FTP kliens fájlokat küld / tölt le egy FTP szerverről
De...
Bárki lehetett kliens is, szerver is Szimetrikus rendszer
32
2013. október 16.
Usenet
A mai P2P alkalmazások nagypapija...
1979
Tom Truscott, Jim Ellis University of North Carolina, Duke University 3 gépből álló hálózat
Unix-to-Unix Control Protocol (UUCP)
Központi vezérlés nélkül fájlokat másol gépek között
Egy UNIX gép automatikus felhívott egy másik gépet Fájlokat cseréltek Megszüntették az összeköttetést
Levelek, fájlok, programok cseréje 33
2013. október 16.
Usenet (II)
Csoportok különböző témakörök körül
A helyi felhasználók a helyi newsgroup „szerverre” csatlakoznak A szerverek periodikusan kicserélik információikat
Newsgroups
Egy felhasználó üzenete minden érdeklődőt elér
A szerverek egy P2P hálózatot alkotnak
34
2013. október 16.
Usenet (III)
A hálózat ma hatalmas
Több ezer szerver Több tízezer témakör Több millió felhasználó
A rendszert skálázhatóva kellett tenni
Egy szerver csak bizonyos csoportokra iratkozik fel A szerverek csak az üzenetek fejlécét továbbítják Ha valaki kiváncsi, lekéri a teljes üzenetet Korlátozott időtartamú tárolás 35
2013. október 16.
Usenet - jellemzők
Elosztott rendszer Nincs központi vezérlés Egy új témacsoport létrehozása
Demokratikus szavazás alapján Javaslat küldése a news.admin csoportnak Vita, szavazás
Bárki szavazhat e-mail-ben
Ha elfogadják, a szerverek elkezdik terjeszteni
Megengedett anarchia
Szavazás nélkül nyitható egy alt.* csoport
36
2013. október 16.
Usenet
Network News Transport Protocol (NNTP)
Optimalizált elárasztás
TCP/IP alapú Útvonal az üzenetek fejlécében Egy szerver csak egyszer kap meg egy üzenetet
Sok új P2P rendszerből hiányzik
Gnutella
37
2013. október 16.
Usenet fájlcsere
Eredetileg csak text fájlok cseréje Bináris fájlok átalakíthatóak Gond – túl hosszú fájlok
700 Mb film – 15 millió sor Szerver korlátok – 10.000 soros üzenetek
Több részre vágott fájlok
38
2013. október 16.
DNS
Domain Name System
Hierarchikus információs rendszer Fájlmegosztásra találták ki (1983)
hosts.txt
39
2013. október 16.
IP útvonalválasztás
IP útvonalválasztók (routerek) peer-ek Felfedezik és fenntartják a topológiát Egy router nem kliens és nem szerver Folyamatosan kommunikálnak egymással Függetlenek egymástól
40
2013. október 16.
Aztán robbant a Net
Robbant a felhasználók száma Tudományosból kereskedelmi hálózat Biztonsági intézkedések váltak szükségessé
Megjelentek az otthoni felhasználók
Egy modemes csatlakozó nem volt többé egyenrangú
Elfogytak az IP címek
Tűzfalak
Dinamikus IP címek, NAT
Megjelent a Web
Új kommunikációs szokások (webkliens – webszerver)
41
2013. október 16.
Mégis P2P?
Újabb fordulat a kommunikációs szokásokban
MP3 – mérföldkő a P2P tekintetében
Elkülönül a „szerző” és a „forgalmazó” Nem csak a saját maguk által készített adatokat (pl. weboldal) osztják meg a felhasználók Lehetővé válik a zenefájlok cseréje DivX kódolás
1999-ben megjelenik a Napster
42
2013. október 16.
Napster
43
Napster
Kronológia
1999 május – Shawn Fenning és Sean Parker megalapítják a Napster-t 1999 december – a RIAA elindítja az első pert a Napster ellen
Recording Industry Association of America (RIAA)
2000 április – Előbb a Metallica, majd Dr. Dre perlik a Napster-t 2000 július – A bíróság felszólítja a Napster-t a bezárásra 2001 február 12 – A bíróság a megosztott fájlok szűrésére kötelezi a Napster-t 2001 február 20 – 1 milliárd dolláros ajánlat a lemezcégeknek 2001 március 2 – Bevezetik a szűrőket, a felhasználók elpártolnak
44
2013. október 16.
Napster
Módosítás – fizetős változat
$9,95 – havi bérlet ¢ 99 – egy fájl http://www.napster.com/
Apple – iTunes
http://www.apple.com/itunes/
45
2013. október 16.
46
2013. október 16.
Boldog zenészek?
P2P hálózatok 47
2013. október 16.
Egy CD költségei Nyereség - 540 Ft
Jogdíj - 900 Ft Kulturális járulék 60 Ft
Forgalmi adó - 1000 Ft
Gyártás - 300 Ft
Design - 100 Ft Stúdió és marketingköltség 800 Ft
Kiskereskedelmi árrés - 1000 Ft Terjesztési díj - 300 Ft
P2P hálózatok 48
2013. október 16.
A Napster működése
Nem „igazi” P2P rendszer
Központi szerver tárolja a megosztott fájlok listáját Keresés a központi szerveren Közvetlen letöltés a peer-ek között
49
2013. október 16.
Példa Napster szerver
1. Bejelentkezés (Alíz, Fájl lista)
2. Keresem a ricky.mp3 fájlt
3. Alíztól kérd
Alíz
4. Közvetlen letöltés
P2P hálózatok 50
Barbara
2013. október 16.
A Napster jellemzői
Hátrányok:
Rossz skálázhatóság
Szerverfarmon belüli terheléselosztás
A szerver szűk keresztmetszet Könnyen perelhető Titkosság hiánya Freeriding lehetőség
Előnyök
Gyors keresés Ismert topológia 51
2013. október 16.
DC++
52
DirectConnect
Központosított rendszer
Korlátozott belépés
Több száz hub Megosztott tartalom mérete (több Gb) IP címtartomány Hozzáférési sebesség
Neo Modus DC
http://www.neo-modus.com/
53
2013. október 16.
DC++
Nyílt forrású (open source) kliens DirectConnect hálózatot használja Előnyök
Barátságosabb GUI Több hub-os párhuzamos csatlakozás, keresés Spyware, adware kiiktatva
DC++
http://www.indx.f2s.com/index.html http://www.broadbandreports.com/faq/dc 54
2013. október 16.
eDonkey
Központosított hálózat
Több szerverre lehet feliratkozni egyszerre
286 magán szerver A szerverek nem kommunikálnak egymással server.met – a szerverek IP címlistája Folyamatosan kell frissíteni
Elosztott letöltés
Megosztáskor egy hash-t (azonosítót) csatol a fájl-hoz A szerver tárolja a hash-eket Kereséskor egy listát kapunk a lehetséges peer-ekről A fájl darabjait külön helyekről, párhuzamosan tölthetjük le 55
2013. október 16.
eDonkey ricky.mp3 (d)
Kliens X
Kliens Y
ricky.mp3 (abcdefg)
ricky.mp3 (abc)
Kliens Z ricky.mp3 (fg)
Kliens W ricky.mp3 (g)
ricky.mp3 ()
http://www.thedonkeynetwork.com/ 56
2013. október 16.
eMule
Népszerű eDonkey kliens Open source változat Nincs spyware, adware
http://www.emule-project.net/
57
2013. október 16.
Gnutella
58
Gnutella
Kronológia
2000 március 14 – Justin Frankle, Nullsoft (winamp)
Eredetileg „receptek cseréje” volt a cél GNU General Public License - Nullsoft web szerver
Pár óra után az AOL letiltotta Több száz példányt már letöltöttek Kód-visszafejtés (reverse engineering) segítségével Több új kliens jelent meg
59
2013. október 16.
Gnutella
Elosztott rendszer, központi szerver nélkül (v0.4) Elárasztás alapú keresés Minden peer...
Megoszt állományokat Továbbítja a szomszédai felé a kapott Query csomagokat Válaszol a Query üzenetekre, ha rendelkezésére áll a keresett fájl
60
2013. október 16.
Gnutella
Keresés Válasz
61
2013. október 16.
Gnutella fejléc
Byte 0 – 15 : Message ID
Byte 16 : Function ID
Hányat ugorhat még
Byte 18 : Hops
Az üzenet tipusa
Byte 17 : TTL (Time To Live)
Egyéni azonosító V 0.6 – Byte 8: 11111111, Byte 15: 00000000
Hányat ugrott már
Byte 19 – 22 : Payload Length
A fejléc utáni adatrész hossza Max csomag hossz: 4 kB 62
2013. október 16.
Üzenettipusok
Function ID
0x00 Ping : peer-ek keresése a gnutella hálózaton 0x01 Pong : válasz egy Ping-re
0x80 Query : keresés indítása
Keresési kritérium (szöveg), minimum sávszélesség
0x81 Query Hit : válasz találat esetén
IP cím, port, megosztott fájlok száma, megosztott könyvtár mérete
IP cím, port, sávszélesség, fájl név, fájl hossz
0x40 Push : „feltöltés” kérése egy tűzfal mögül
Kért fájl adatai, cél IP cím/port http://rfc-gnutella.sourceforge.net/developer/stable/
63
2013. október 16.
Előnyök
Robusztusság, nincs szűk keresztmetszet Egyszerűség Jogilag nehezen támadható
Nincs perelhető központi entitás
64
2013. október 16.
Hátrányok
Az elárasztás nem skálázható megoldás
TTL-t használva (valamilyen szinten) áthidalható Nem minden szomszédnak küldjük tovább az üzeneteket A Message ID alapján, egy üzenetet csak egyszer továbbít egy peer Egy peer többször megkaphat egy üzenetet
65
2013. október 16.
Többszöri kézbesítés
66
2013. október 16.
Hátrányok (II)
Nagy hálózati forgalmat generál Példa:
4 link L / peer TTL = 7 Max csomag szám: TTL
2 ∗ ∑ L ∗ ( L − 1) i i =0
26240 csomag 67
2013. október 16.
Hátrányok (III)
A keresés időtartama nem behatárolható A keresés sikerének valószínűsége nem ismert A topológia ismeretlen, az algoritmusok nem tudják felhasználni A peer-ek „hírneve” nincs figyelembe véve Freeriding ...
68
2013. október 16.
Freeriding
Adar, Huberman, Freeriding on Gnutella, 2000 Sept.
http://www.firstmonday.org/issues/issue5_10/adar/index.html 24 órás mérések: a kliensek 70%-a nem oszt meg semmit a válaszok 50%-át a peer-ek 1%-a szolgáltatja
Társadalmi, és nem technikai probléma Következmények
A rendszer hatákonyságának romlása (skálázhatóság?) A rendszer sebezhetőbb „Központosított” Gnutella – jogi problémák
69
2013. október 16.
Freeriding (II)
Mérések elemzése
A felhasználók nagy hányada freerider A freerider-ek egyenlően oszlanak el a hálózatban Bizonyos peer-ek olyan fájlokat osztanak meg, melyek senkit sem érdekelnek
70
2013. október 16.
Gondok és megoldások
Freeloading:
Megszakadó letöltések
A Gnutella hálózat elérhető volt weboldalakról Webes keresés, letöltés, megosztás nélkül Hosszú letöltési idők a modemes hozzáférés miatt Csak rövid ideig futtaták a gnutella kliens-t (keresés ideje)
Megoldás:
„Nálam van, de foglalt vagyok. Próbalkozz kesőbb” 2000 végén – letöltések 10%-a sikeres 2001 – a letöltések 25%-a sikeres Megoldás? 71
2013. október 16.
Gondok és megoldások
Kis méretű elérhető hálózat
2000: átlagosan 400-800 elérhető peer Modemes felhasználók – kis sávszélesség a keresések továbbítására
Megoldás:
routing black holes
Peer hierarchia kialakítása Csatlakozási preferenciák Nagy sávszélességű peer-ek előnyben Nagyméretű megosztott állománnyal rendelkezők előnyben
Gnutella v0.6 és más hierarchikus rendszerek
72
2013. október 16.
Irodalom
http://www.gnutella.com/ http://www.limewire.com/developer/
P2P hálózatok 73
2013. október 16.
KaZaa
74
KaZaa
A jelenleg legelterjedtebb P2P alkalmazás
A FastTrack hálózatot használja 4 millió felhasználó 3,000 terabyte megosztott adat > 50% az Internet forgalmának
Leginkább az USA-ban népszerű A RIAA legnagyobb célpontja
30-40% csökkenés 2003 végén
75
2013. október 16.
Kronológia
Niklas Zennström ötlete
2001 – Sharman Networks megveszi a FastTrack-et
2001 márciusa - Jaan Tallinn, Ahti Heinla és Priit Kasesalu FastTrack, KaZaa - fejlesztés Észtországban Holland cég megbízása – KaZaa BV Székhely: Vanuatu - sziget a Csendes Óceánban Titkos igazgatótanács, titkos részvényesek
Kazaa.com – LEF Interactive, Ausztrália
LEF – Liberté, Egalité, Fraternité Alkalmazottak mindenhol a világban, nehezen fellelhetők
76
2013. október 16.
KaZaa vs. RIAA
Nemzetközi macska-egér játék
Az amerikai jog nem érvényes máshol Nincs központi entitás, nincs kit perelni
Megoldások?
(Amerikai) felhasználókat perelni? Denial-of-Service (DoS) támadások Vírusok a rendszerben
Hash linkekkel elkerülhetőek Weben keresztül megszerezhető hash-ek
77
2013. október 16.
Architektúra
Hierarchikus architektúra
A peer-ek egy supernode-hoz csatlakoznak
supernode = supernode, hypernode
A supernode-ok egyenrangúak A supernode ismeri a hozzá tartozó peer-ek IP címeit, és a megosztott fájl-ok listáját
Mini Napster/Gnutella hub
78
2013. október 16.
Architektúra (II)
Titkos forráskód
Egy supernode ismer sok más supernode-ot
Majdnem teljes háló (complete mesh)
Bárki lehet supernode
Kód visszafejtés: peer – supernode kommunikáció A supernode – supernode kommunikáció alig ismert
Számítási kapacitás, sávszélesség Automatikus kiválasztás
Kb 10.000 supernode
Kb 200-500 peer/supernode 79
2013. október 16.
Supernode választás
Lehetséges supernode-ok IP címei az alkalmazás letöltésekor Csatlakozás után egy működő supernode keresése Aktuális supernode lista letöltése Ping 5 supernode felé Választás a legkisebb RTT alapján
RTT = Round Trip Time
Ha a supernode „meghal”, új választás 80
2013. október 16.
Keresés
Kulcsszó alapján
A keresést a supernode-hoz küldi
Ha a supernode-nál van x találat, vége
Ha nincs, a kérést a supernode más supernode-oknak küldi
A felhasználó beállítja max. hány találatot vár (x)
Ha van x találat, vége
Ha nincs, újabb supernode-ok kapják meg a kérést
Valószínüleg a kezdeményező supernode indítja az újabb keresést (nem rekurzív) Válaszok hullámokban
81
2013. október 16.
Kazaa Keresem a ricky.mp3 fájlt B-nek megvan Közvetlen letöltés B
A
82
2013. október 16.
Párhuzamos letöltés
Ha több találat, a felhasználó párhuzamos letöltést választhat
A fájl több részre osztva HTTP byte-range header alapján különbözö részek különböző peer-ektől
Új „szerver” peer választása automatikusan, ha az előző „meghal”
83
2013. október 16.
Előnyök
Skálázható
Egy központi szerver helyett több ezer supernode Csak a supernode-ek között történik elárasztás
Sorbanállás kezelése
Előnyt élveznek azok, akiktől sokat töltenek le Hátrány a kis sávszélességgel rendelkezőknek
lassan kerülnek kiszolgálásra
Jogilag nehezen támadható
84
2013. október 16.
Más hierarchikus rendszerek
FastTrack
Kazaa Lite
iMesh
http://www.k-lite.tk/ http://imesh.com/
Grokster
http://www.grokster.com/
P2P hálózatok 85
2013. október 16.
Más hierarchikus rendszerek
Gnutella v0.6
LimeWire
Shareaza
http://www.shareaza.com/
BearShare
http://www.limewire.com
http://www.bearshare.com/
Morpheus
http://www.morpheus.com/
86
2013. október 16.
BitTorrent
BitTorrent
2002 – Bram Cohen, San Francisco Python kód, open source Népszerű nagyméretű adatok elosztott letöltése
Nincs saját keresőmotor
Webes keresés
Nincsenek megosztott könyvtárak Letöltés közben feltöltés mások számára
88
2013. október 16.
BitTorrent
Hagyományos webes keresés .torrent fájl
Hash információ Egy „tracker szerver” címe
Tracker
A csatlakozó peer-nek megad egy véletlenszerű listát a lehetséges peer-ekről Default 50 Altalaban egy peer 20-40 peer-el tart kapcsolatot (peer lista) – Ha 20 alá csökken, újra a trackerhez fordul Statisztika
A Peer-ek idıkozonkent jelentenek a Trackernek Hány letöltés Hány peer-nél van a teljes fájl Hány peer-nél vannak fájl részek 89
2013. október 16.
BitTorrent
Seed (mag) A kezdeti forrás
Leech (pioca)
A peer akinél a letöltés folyamatban van
Swarm (raj)
Egy peer akinél a teljes allomány megtalálható
Egy adott fájl esetében a seed-ek és leech-ek halmaza együtt
A fájl több részre osztva
64 KB és 4 MB kozott
Minden rész hash információja a .torrent fájlban
Ha túl nagy, kisebb a torrent, de nem annyira hatékony Általában 256 KB SHA-1
A részek tovabbi alrészekre osztva 90
2013. október 16.
Alapelvek
Párhuzamos letöltés és feltöltés „Leech resistance” – piócák kiszűrése
Megbízhatóság maximizálása
Minél nagyobb a feltöltési sávszélesség, annál több peer-től tölthetsz le részeket párhuzamosan Csökkenteni a sikertelen letöltések esélyét Bizonyos részek „eltünnek”, a fájl használhatatlan
A működés ezen alapelveknek van alárendelve 91
2013. október 16.
Hogyan működik?
Egy rész teljes letöltése
Ha egy rész egy alrészét letöltjük, a következő alrészek előnyben részesülnek más részek alrészeivel szemben Gyors letöltést biztosít egy rész számára Ha a rész teljes, a peer ellenőrzi a hash-t Ha OK, jelzi a Tracker-nek A rész feltölthetővé válik mások számára
92
2013. október 16.
Mit töltsek?
A legritkább legelőbb (rarest first)
Azt a részt tölti le előbb, mellyel a legkevesebb peer rendelkezik
Előnyök
Növeli a letöltés globális sikerét
Biztosítja a további feltöltési kéréseket
Ha az a néhány peer (esetleg az egyedüli seed) „meghal”, továbbra is elérhetőek lesznek a ritka részek Ha egy ritka résszel rendelkezem, mások tőlem fogják azt kérni Növelem a letöltési sebességem
Növeli a globális letöltési sebességet
A seed-től külön részeket kér le minden peer Ugyanazt a részt nem kell többször feltöltenie a seed-nek
Különösen előnyös ha „lassú” seed 93
2013. október 16.
Mit töltsek?
Véletlenszerű első (4) rész Ameddig nincs mit feltölteni tőlem, letölteni is nehezen tudok – kevés peer-t ismerek Cél egy részt minél gyorsabban megszerezni
Egy ritka részt lassan tudok letölteni
Egy népszerű rész letöltése gyors, de nem olyan hasznos
Kevés peer rendelkezik az alrészekkel Ha letöltöm, sokan kérik majd, nő a letöltési sebességem Kevesen fogják majd tőlem kérni Nem tudom növelni a letöltési sebességem
Megoldás: véletlenszerű választás 94
2013. október 16.
Mit töltsek?
Choking/unchoking – blokkolas/feloldas
Minden peer korlatolt szamu peer-nek tolt fel
Alapertelmezesben 4 slot
Azokat oldom fel, akiknek a legnagyobb a feltöltési sebessége felém és kérnek tőlem valamit 10 másodpercenként újraszámolom a 4 leggyorsabbat
Optimistic unchoking
30 másodpercenként feloldok egy véletlen peert is aki kért tőlem valamit
Hátha nagy sebességgel tudnék letölteni tőle a jövőben Maximum 5 upload slot
Az új peereket háromszor nagyobb valószínűséggel
Bootstrap mechanizmus 95
2013. október 16.
Tulajdonságok
Lassú indulás Változó letöltési sebesség
Sikeres letöltés után illik az alkalmazást tovább futtatni
Ekkor a peer seed-ként működik
Jogilag könnyen támadható
Függ a feltöltés alatt álló résszel rendelkezők számától, feltöltési sebességétől
A tracker szolgáltatása, IP címe nyilvános Felelősségre vonható
Trackerless BitTorrent 96
2013. október 16.
BitTorrent vs. eDonkey
Hasonló elveken működnek
A BitTorrent-ben csak egy fájl-t töltünk le egyszerre
Nagyobb a rendelkezésre álló sávszélesség minden peer-nél (Elvileg) gyorsabb letöltés
Az eDonkey-ban nincs „piócaszűrés”
Részekre osztott fájlok Párhuzamos letöltés
A feltöltésből nincs igazán haszna a peer-nek
A BitTorrent-ben nincs keresőmotor
A .torrent fájlt weben kell megkeresni Jogilag könnyen támadható
A tracker szolgáltatása, IP címe nyílvános Felelősségre vonható 97
2013. október 16.
Egyszerű interfész
P2P hálózatok 98
2013. október 16.
BitTorrent linkek
Hivatalos oldal
Protokoll specifikáció
http://bitconjurer.org/BitTorrent/protocol.html
FAQ
http://bitconjurer.org/BitTorrent
http://www.dessent.net/btfaq/#what
Torrent-ek
http://www.suprnova.org/
2004 végén bezárták
http://isohunt.com/
159k tracker, 6.8mill aktív torrent, 161mill fájl, 12.2 PB adat, 25.8mill peer 99
2013. október 16.
irate Bay
Az egyik legnépszerőbb weboldal a neten
2006. május 31-én a svéd rendőrség lefoglalja a szervereket 3 napig offline a weboldal A per
2009. április 17-én a szolgáltatás működtetőit (Peter Sunde, Fredrik Neij, Gottfrid Svartholm, Carl Lundstrom) 1 év börtönre és 30mill SEK (~700mill HUF) büntetésre ítélik Fellebbezés, a bírót elfogultsággal vádolják
4 millio regisztrált (2009 dec.) felhasználó
2003 novemberben indult
> 25mill peer (2008 nov.) A letöltéshez nem kell regisztrálni csak a kommentekhez és a feltöltéshez
Pirate Party
7.1 % a svéd EU parlamenti választásokon 100
2013. október 16.
Anonimitás – elosztott módon
101
P2P hálózatok
Anonimitás
Első lépés
Követők, lehallgatók összezavarása Nem tudják, hogy ki is tölt le P2P módon együttműködnek a felhasználók
„relay”
102
2013. október 16.
Tor
P2P hálózatok
Tor
103
2013. október 16.
Tor
P2P hálózatok
104
2013. október 16.
Tor
105
2013. október 16.
Anonimitás – elosztott módon
106
P2P hálózatok
Anonimitás
Második lépés
Követők, lehallgatók összezavarása P2P rendszerben történik a routolás is Adatot is szétosztjuk ELOSZTOTT ADATBÁZIS
Igazából egy elosztott cache Keresés
107
2013. október 16.
Freenet Ian
Clarke, végzős hallgató University of Edinburgh Teljesen
elosztott, egyenrangú hálózat
A
peer-ek tárolófelületet és sávszélességet „ajánlanak” fel a rendszernek
Nem tudják a rendszer mit tárol ott Minden adat kódolva van
Freenet
– „földrajzilag elosztott nagyméretű virtuális merevlemez, névtelen (anonymous) hozzáféréssel” 2013. október 16.
Freenet Biztosítja
a „szerzők” és az „olvasók” anonimitását
Nem lehet megállapítani az adatok forrását és célállomását Az adatokat kulcsok azonosítják A peer-ek nem tudják mit tárol a rendszer a gépükön Nem (vagy nehezen) vonhatóak felelősségre
A
keresést abba az irányba továbbítja, ahol a legvalószínűbb a találat
Nincs központi szerver (Napster) Nincs elárasztás (Gnutella)
A
fájlok azonosítása tárolási helyüktől független 2013. október 16.
Freenet Az
adatok dinamikus elosztása a rendszerben
A
hálózati topológia (gráfstruktúra) folyamatosan változik
Új kapcsolatok jönnek létre a peer-ek között Az állományok vándorolnak a rendszerben Dinamikus, adaptív útválasztás
2013. október 16.
Freenet fejléc UniqueID
Azonosítja az üzenetet A hurkok elkerülésére szolgál
Hops
(64 bit)
To Live
Még hányszor lehet továbbküldeni a csomagot
Depth
Hányat ugrott már a küldés óta
Source
Az üzenet forrását azonosítja
2013. október 16.
Üzenet típusok HandshakeRequest
Kapcsolatot kezdeményez egy peer-el
HandshakeReply
Válasz a HandshakeRequest-re
DataRequest
A megadott kulcsnak megfelelő adatot kéri
DataReply
Válasz a DataRequest-re A közbeeső peer-ek cache-ben tárolják az adatot A következő hasonló kérésre már tudnak közvetlenül válaszolni
RequestFailed
Sikertelen keresés esetén 2013. október 16.
Üzenet típusok InsertRequest
Megegyezik a DataRequest-el Azt ellenőrzi, hogy a megadott kulcsnak megfelelő fájl megtálalható-e a rendszerben Ha igen, egy DataReply érkezik Ha nem, egy InsertReply üzenet
DataInsert
Kérés a megadott adat és kulcs tárolására a rendszerben Az InsertRequest útvonalán halad Ott tárolja ahol majd keresni fogják A közbeeső peer-ek cache-ben tárolják az adatot 2013. október 16.
Data Store Minden peer-nek tudnia kell... Merre továbbítani egy kérést Merre továbbítani egy választ Meddig tárolni egy adott dokumentumot
2013. október 16.
Data Store
Lista tetején – „friss”, gyakran kért fájlok Kulcs, adat, származási cím
Lista alján – régi, ritkán kért fájlok Kulcs, elérhetőségi cím
Ha egy kulcs lefele mozog a listán, egy idő után az adatok törlődnek 2013. október 16.
Keresés A
peer-ek által tárolt kulcsok alapján
Egy
Korlátozott számú ugrás, de nagyobb mint a Gnutella esetében Tipikusan 500 Az üzenetek azonosítója alapján szűri a hurkokat
kérés érkezésekor Ha már kezelte a kérést (hurok), visszaválaszol hogy a küldő próbálja másfelé továbbítani („next-best choice”) Ha rendelkezik az állománnyal, válaszol Ha nem, továbbküldi a keresett kulcshoz legközelebb álló kulcsnak megfelelő cím felé
2013. október 16.
Keresés (II) Ha
egy válasz érkezik A kulcs és az adat bekerül a cache-be A legrégebbi kulcs kikerül a data store-ból
Találat
esetén az állomány küldése nem pont-pont közötti
A keresés útvonalán terjed vissza Segíti a cache működését Növeli az anonimitást
2013. október 16.
Keresés - példa DataRequest Start
DataReply RequestFailed
Data
2013. október 16.
Keresés Az
A
elején a Data Store üres
A peer véletlenszerűen választja ki merre küldje a keresési, illetve adatbeviteli kéréseit
Az adatok eloszlása is véletlenszerű lesz
keresés (útválasztás) minősége idővel javul
Lavina effektus
Egy tárolt fájl alapján a peer bekerül más peer-ek adatbázisába, a megfelelő kulccsal Hasonló kulcsok iránti kérések elkezdenek érkezni A válaszok bekerülnek a cache-be
Egyre több hasonló kulcsú állományt tárol
A
peer nem döntheti el milyen kulcstartományra „specializálódik”
A többi peer által tárolt kulcsoktól függ Növeli a rendszer „ellenőrizhetetlenségét”
2013. október 16.
Freenet keresés - példa k10 k9
B A
k10
k10 k36
A C
k36
k36 k9
C B
k7
B
k9
A
k11
B
k10
A
k9
B
A
k7
k36
F
C
k41
k9 k11
k9 ? E
D
k9
A
k9
k11
F
k11
k34
D
k34
k34
C
k9
A
2013. október 16.
Freenet keresés - példa k9 k7
B
k9 k7
k10 k9
A B
k10 k9
k36 k10
C A
k36 k7
k9
A
k11
B
k36 k10
B
A
C B
k7
k36
F
C
k41
k9
k7 ? E
D
k9
A
k11
F
k9
k7 k34
k7
A
k34
C
k9
A
2013. október 16.
Lavina effektus példa
Animáció, klikkelj a „vonalkódra”
2013. október 16.
Keresések eloszlása Slashdot
A
A
effektus (http://slashdot.org/)
Népszerű számítástechnikai hírportál „News for nerds, stuff that matters” Ha egy érdekes hír jelenik meg rajta, mindenki ráklikkel a linkre A hirtelen terhelés megbéníthatja a kisebb kapacitású gépeket
Freenet elkerüli a Slashdot effektust A cache-elés miatt a keresések eloszlanak A források nem kerülnek túl nagy terhelés alá
kulcsok hash-ek Szemantikailag egymáshoz közel álló tartalmak teljesen különböző kulcsokat kaphatnak Egy „hot topic”-hoz tartozó különböző állományok eloszlanak a rendszerben 2013. október 16.
Hash függvény Nagy
értelmezési tartományt képez le egy „szűk” értékkészletre
Változó hosszúságú x paramétert képez le fix hosszúságú h = H(x) értékre
Kriptografikus
hash függvények
Ha adott x, H(x) relatív egyszerűen kiszámítható H(x) egyirányú Ha adott h hash érték, túlzottan számításigényes olyan x-et találni, amire H(x) = h H(x) ütközésmentes H „gyengén ütközésmentes” ha egy adott x-re, túlzottan számításigényes egy olyan y megtalálása (x ≠ y), melyre H(x) = H(y) H „erősen ütközésmentes” ha túlzottan számításigényes bármilyen olyan x és y értékeket találni (x ≠ y), melyre H(x) = H(y) 2013. október 16.
Hash függvény Népszerű
algoritmusok
MD5 – (Message Digest Algorithm 5) Ronald Rivest (MIT), 1991 http://www.ietf.org/rfc/rfc1321.txt SHA-1 (Secure Hash Algorithm)
http://www.itl.nist.gov/fipspubs/fip180-1.htm
2013. október 16.
Kulcsok Minden A
kulcs egy globális azonosító része Uniform Resource Identifiers (URIs): freenet:keytype@data
Több
állományt egy kulcs azonosít
fajta kulcs létezik
Keyword Signed Key (KSK) Signature Verification Key (SVK) SVK Subspace Key (SSK) Content Hash Key (CHK) 2013. október 16.
Keresés
A kereséshez tudni kell az adott kulcsot
A publikáló félnek ezt nyílvánosan meg kell hírdetni
Anonymous hirdetési lehetőség Freenet portálokon Rövid leírás, kulcs Freenet levelező listákon Freenet IRC csatorna irc.freenode.net #freenet Privát e-mail, web Graffiti, hőlégballonon, repülő által húzott reklámszalagon
2013. október 16.
Anonimitás A
peer-ek véletlenszerűen „hazudhatnak” a kérésekkel kapcsolatban
A Depth és a Hop-To-Live értékek változtathatóak
Lehetetlen
kideríteni kitől kapod meg a dokumentumot
A forrás címet bármely csomópont az útvonalon átírhatja a sajátjára
Lehetetlen
kideríteni ki publikált először a rendszerben egy
adott fájlt Igyekeznek a réseket is betömni
Nem
„the Javascript exploit mentioned would not have worked on Freenet because Freenet removes Javascript by default. ”
biztosít igazi anonimitást A nem triviális támadások ellen valószínűleg nem képes védekezni Forgalomanalízis, nagyszámú csomópont kompromittálása
2013. október 16.
Előnyök Teljesen
elosztott rendszer Nagy hibatűrés Robusztus, skálázható Másolatok automatikus generálása Jól alkalmazkodik a felhasználók dinamizmusához Adaptív, hatékony útválasztás Anonim szerzők és olvasók Freeriding nem lehetséges 2013. október 16.
Hátrányok Nem
garantálható a keresések ideje Nem garantálható a keresések sikere Ismeretlen topológia
A kereső algoritmusok nem tudják ezt kihasználni
Nem
biztosítja a tartós tárolást
Egy ma publikált fájl holnapra lehet hogy „kihal” a rendszerből
Nagyméretű
állományoknál nem előnyös egy hosszú útvonal mentén küldeni a választ
Nagy a hibalehetőség „Elpocsékolt” sávszélesség 2013. október 16.
Anonimitás vs. hatékonyság A
Freenet fő célja a cenzúra elkerülése és az anonimitás, nem a hatékonyság
Főként kisméretű fájlok, szöveges dokumentumok tárolására és terjesztésére kiváló Freenet China http://freenet-china.org/
2013. október 16.
Irodalom I.
Clarke, O. Sandberg, B. Wiley, T. W. Hong, , "Freenet: A distributed anonymous information storage and retrieval system", in Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, July 2000.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1 .10.4919 2000 legtöbbször hivatkozott cikke a Citeseer-ben
The
Jelenleg 773 hivatkozás a Citeseer-ben, 2236 hivatkozás a Google Scholar-ban
Free Network Project
http://www.freenetproject.org/ http://freenetproject.org/papers.html 2013. október 16.
133
P2P hálózatok
P2P Keresés
Strukturálatlan P2P rendszerek
Gnutella, KaZaa, stb... Véletlenszerű keresés
Példa: koncentrikusan szélesedő keresés
Nincs információ a fájl lehetséges tárolási helyéről Expanding Ring Search (ERS)
Nagy terhelés a rendszeren Minél több helyen tárolva, annál kisebb a keresés által generált terhelés
134
2013. október 16.
P2P Keresés (II)
Strukturált P2P rendszerek
Irányított keresés
Kijelölt peer-ek kijelölt fájlokat (vagy azok fele mutató pointereket) kell tároljanak
Mint egy információs pult
Ha valaki keresi a fájlt, tudja kit kérdezzen
Elvárt tulajdonságok
Elosztottság
Felelősség elosztása a résztvevők között
Alkalmazkodás
A peer-ek ki és bekapcsolódnak a rendszerbe Az új peer-eknek feladatokat osztani A kilépő peer-ek feladatai újraosztani 135
2013. október 16.
Elosztott hash táblák - DHT
Distributed Hash Tables – DHT Egy hash függvény a keresett fájlhoz egy egyéni azonosítót társít
Példa: h(„P2P_előadás”) -> 123
A hash függvény értékkészletét elosztja a peer-ek között Egy peer-nek tudnia kell minden olyan fájlról, melynek a hash-elt értéke a saját értékkészletébe tartozik
Vagy saját maga tárolja a fájlt.... Vagy tudja ki tárolja a fájlt.
136
2013. október 16.
DHT példa 211-399 200-210
484-799
400-483 100-199
123
0-99
137
h(x) → [0..799]
2013. október 16.
DHT példa 211-399 200-210
484-799
400-483 100-199
123
0-99
138
h(x) → [0..799]
2013. október 16.
DHT útválasztás
Minden peer mely információt tartalmaz egy fájlról elérhető kell legyen egy „rövid” úton
A kereső peer által A fájlt tároló peer-ek által
Korlátozott számú szomszéd
Korlátozott számú lépésen belül
Skálázható a rendszer méretétől függetlenül
A különböző DHT megoldások lényégében az útválasztásban térnek el
CAN, Chord, Pastry, Tapestry
139
2013. október 16.
