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 Elosztott P2P adatbázisok CAP
2
2015. október 30.
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
2015. október 30.
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
2015. október 30.
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
2015. október 30.
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
2015. október 30.
Ádámtól Ádámig A. Oram, editor. Peer-to-Peer : Harnessing the Power of Disruptive Technologies. O'Reilly & Associates, 2001.
8
2015. október 30.
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
2015. október 30.
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
2015. október 30.
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
2015. október 30.
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
2015. október 30.
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
2015. október 30.
É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
2015. október 30.
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ó-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
2015. október 30.
P2P és elosztott adatbázisok
Hipotézis
End 2 End (végpontok közötti kapcsolatok) érvek az Interneten
Gyors alkalmazásfejlesztés
Felső szinteken megvalósítás, amennyire lehet Könnyebb telepíteni, mert nem szorul rá a hálózat támogatására Moore törvény analógiájára
Az Internet maghálózat (core) viszonylag lassan változik
Kevesebben kutatják. (http://www.icir.org/floyd/talks/NSF-Jan03.pdf) 2015. október 30.
Kulcskérdés: Lokalizáció és routing
Egy végpontokban megvalósított rendszer nehézségei
Lokalizálni, üzeneteket küldeni
Erőforrásokat, adatokat
Nagyméretű fedő hálózat céljai
wide-area overlay infrastructure Könnyű telepíthetőség Skálázható millió felhasználóra Szokásos hibákkal szemben toleráns Ön-konfiguráló, adaptív Hibákat lokalizálja
2015. október 30.
A P2P ígérete
Megbízható: nincs központi hibalehetőség
Párhuzamos erőforrások, nagy kapacitás
Sok másolat (replica) Földrajzilag elosztott
Sok HDD Sok kapcsolat (= sávszélesség) Sok CPU
Automatikus configurálhatóság Nyilvános- és magánhálózatok esetében is hasznos
2015. október 30.
Példa: pond
JNI for crypto, SEDA stages, 280+kLOC Java 2015. október 30.
Strukturálatlan P2P
21
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
22
2015. október 30.
A kezdeti hálózat
23
2015. október 30.
70-es évek
újabb és újabb egyetemek, kutató laboratóriumok csatlakoznak TCP/IP kidolgozása Telnet, FTP
24
2015. október 30.
ARPANET - 1977
25
2015. október 30.
80-as évek
1983. 01. 01 – IP az ARPANET-en 1984 – MILNET (DoD) 1986 – NSFNET
NSF – National Science Foundation
1990 – Az ARPANET bezár
26
2015. október 30.
MILNET - 1989
27
2015. október 30.
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
28
2015. október 30.
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 ...
29
2015. október 30.
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
30
2015. október 30.
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 31
2015. október 30.
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
32
2015. október 30.
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 33
2015. október 30.
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
34
2015. október 30.
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
35
2015. október 30.
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
36
2015. október 30.
DNS
Domain Name System
Hierarchikus információs rendszer Fájlmegosztásra találták ki (1983)
hosts.txt
37
2015. október 30.
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
38
2015. október 30.
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)
39
2015. október 30.
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
40
2015. október 30.
Napster
41
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
42
2015. október 30.
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/
43
2015. október 30.
44
2015. október 30.
Boldog zenészek?
P2P hálózatok 45
2015. október 30.
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 46
2015. október 30.
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
47
2015. október 30.
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 48
Barbara
2015. október 30.
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 49
2015. október 30.
DC++
50
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/
51
2015. október 30.
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 52
2015. október 30.
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 53
2015. október 30.
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/ 54
2015. október 30.
eMule
Népszerű eDonkey kliens Open source változat Nincs spyware, adware
http://www.emule-project.net/
55
2015. október 30.
Gnutella
56
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
57
2015. október 30.
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
58
2015. október 30.
Gnutella
Keresés Válasz
59
2015. október 30.
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 60
2015. október 30.
Ü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/
61
2015. október 30.
Előnyök
Robusztusság, nincs szűk keresztmetszet Egyszerűség Jogilag nehezen támadható
Nincs perelhető központi entitás
62
2015. október 30.
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
63
2015. október 30.
Többszöri kézbesítés
64
2015. október 30.
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 65
2015. október 30.
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 ...
66
2015. október 30.
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
67
2015. október 30.
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
68
2015. október 30.
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? 69
2015. október 30.
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
70
2015. október 30.
Irodalom
http://www.gnutella.com/ http://www.limewire.com/developer/
P2P hálózatok 71
2015. október 30.
KaZaa
72
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
73
2015. október 30.
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
74
2015. október 30.
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
75
2015. október 30.
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
76
2015. október 30.
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 77
2015. október 30.
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 78
2015. október 30.
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
79
2015. október 30.
Kazaa Keresem a ricky.mp3 fájlt B-nek megvan Közvetlen letöltés B
A
80
2015. október 30.
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”
81
2015. október 30.
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ó
82
2015. október 30.
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 83
2015. október 30.
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/
84
2015. október 30.
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
86
2015. október 30.
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 87
2015. október 30.
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 88
2015. október 30.
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 89
2015. október 30.
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
90
2015. október 30.
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 91
2015. október 30.
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 92
2015. október 30.
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 93
2015. október 30.
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 94
2015. október 30.
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ó 95
2015. október 30.
Egyszerű interfész
P2P hálózatok 96
2015. október 30.
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 97
2015. október 30.
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 98
2015. október 30.
Anonimitás – elosztott módon
99
P2P
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”
100
2015. október 30.
Tor
P2P
Tor
101
2015. október 30.
Tor
P2P
102
2015. október 30.
Tor
103
2015. október 30.
Anonimitás – elosztott módon
104
P2P
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
105
2015. október 30.
Freenet Clarke, végzős hallgató University of Edinburgh Ian
Teljesen
elosztott, egyenrangú hálózat
peer-ek tárolófelületet és sávszélességet „ajánlanak” fel a rendszernek A
Nem tudják a rendszer mit tárol ott Minden adat kódolva van
– „földrajzilag elosztott nagyméretű virtuális merevlemez, névtelen (anonymous) hozzáféréssel” Freenet
2015. október 30.
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 2015. október 30.
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
2015. október 30.
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
2015. október 30.
Ü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 2015. október 30.
Ü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 2015. október 30.
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
2015. október 30.
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 2015. október 30.
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é
2015. október 30.
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
2015. október 30.
Keresés - példa DataRequest Start
DataReply RequestFailed
Data
2015. október 30.
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”
2015. október 30.
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
2015. október 30.
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
2015. október 30.
Lavina effektus példa
Animáció, klikkelj a „vonalkódra”
2015. október 30.
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 2015. október 30.
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) 2015. október 30.
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
2015. október 30.
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) 2015. október 30.
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
2015. október 30.
Anonimitás peer-ek véletlenszerűen „hazudhatnak” a kérésekkel kapcsolatban A
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
2015. október 30.
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 2015. október 30.
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 2015. október 30.
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/
2015. október 30.
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 2015. október 30.
CAP
P2P
131
2015. október 30.
Legal Download in EU
http://index.hu/kultur/2013/10/30/uhd/
132
2015. október 30.
CAP tétel
CAP = Consistency, Availability, Partition Tolerance
Elosztott rendszerekben Egyszerre nem lehet mind a három célt elérni
http://www.julianbrowne.com/article/vie wer/brewers-cap-theorem 133
2015. október 30.
CAP tulajdonságok
CAP - mozaikszó
Konzisztencia (consistency) Rendelkezésre állás (availability) Partíció tolerancia (partition tolerance)
Elosztott rendszerekben egyidejűleg legfeljebb két fenti tulajdonság garantálható teljesen
A. Fox, E. Brewer, „Harvest, yield, and scalable tolerant systems”. Workshop on Hot Topics in Operating Systems, 1999. http://sharkcollection.googlecode.com/svn/docs/Technique/Architect/%5B8%5DHarvest,%20Yield,%20a nd%20Scalable%20Tolerant%20Systems.pdf
134
2015. október 30.
CAP tétel
„C” - Konzisztencia: bármely időpontban, bármely csomóponttól lekérdezhetjük bármelyik „atomi” adatot ugyanaz az érték „A” - Rendelkezésre állás: minden működő csomóponthoz érkező kérésre tud válaszolni „P” - Partíció tolerancia: adott kérésre hálózati partíció esetén is végre lehet hajtani az írás vagy olvasás műveletet CAP tétel: elosztott rendszerben a hálózat partíciója esetén a rendszer műveletei nem lesznek atomiak és/vagy az adategységei elérhetetlenek lesznek 135
2015. október 30.
CAP elvárások a gyakorlatban
CAP tétel szerint nem valósítható meg egy működő elosztott adatbázis
Ugyanis az nagyszámú, egymástól független elemből állna Ez meg „behozza” a particionálás veszélyét a rendszerbe
Ugyanakkor globális cégek működtetnek ilyen rendszereket. Hogyan?
A három feltétel egyikének lazításával Pl: ha a formális konzisztencia követelménynél gyengébb elvárás megengedése
Amazon Dynamo - „A”, „P” tulajdonságokat garantálja
Pl. ha a késleltetés minimalizálását helyezik előtérbe
Yahoo PNUTS – „P” tulajdonságot minden esetben garantálja 136
2015. október 30.
P2P anyagrészből vizsgára kért tananyag
Napster 47-49 Gnutella 58-59, 62-63, 66, Freeriding 67-69 Kazaa 76-83 BitTorrent 87-93 Anonimitás P2P rendszerekkel: megoldások két lépésben: 100, 105 Freenet 107-108, 111-117, 126-129 Slashdot hatás 121 CAP – 134, 135 137
2015. október 30.
