Calcolo parallelo anno 2004/2005 - the

Calcolo parallelo
anno 2004/2005
Putting it all together:
The Google Cluster of PCs
Rabbi Massimo 799761
Breve storia di Google





Nasce da un’idea di Larry Page e Sergey Brin nel 1998
all’università di Stanford: (http://google.stanford.edu).
Nel 1999 la sede diventa Mountain View (California).
Col passare degli anni diventa il motore di ricerca più
importante e più diffuso: il suo database viene infatti
venduto anche ad altri motori.
18 agosto 2004: Google viene quotato in borsa.
Attualmente è una società con più di 2500 dipendenti
nel mondo valutata attorno i 36 miliardi di dollari.
Cercare sul web usando Google
Esempio di ricerca semplice



La ricerca viene effettuta in tempi molto brevi,
comunque sempre inferiori a 250ms.
Possibilità di consultazione dell’URL originale, della
copia cached della pagina o ricercare pagine simili.
Fornisce una “snippet” del documento puntato.
Caratteristiche di Google




Google ha tra i sui principi progettuali la capacità di
scalare in maniera proporzionale al crescere di
informazioni indicizzate e di query da soddisfare.
Tecniche utilizzate per la qualità dei risultati: page rank,
link popularity, anchor text, keyword text.
Google deve essere sempre disponibile: i motori di ricerca
sono usati in qualsiasi momento del giorno e in qualsiasi
parte del mondo.
Bisogna garantire informazioni sempre aggiornate: le
pagine cached vengono visitate almeno una volta al mese.
Evoluzione della struttura di Google



DICEMBRE 2000:
- 6.000 pc e 12.000 dischi fissi per un totale di più di un
petabyte di storage su disco.
- 2 siti nella Silicon Valley e un sito in Virginia.
- Ogni sito è collegato a Internet mediante link di tipo
OC48 (2,5 Gbit/sec).
- Linee di backup di tipo OC12 (622 Mbit/sec).
2002-2003:
- Dai 15.000 ai 50.000 pc.
2004:
- Più di 100.000 elaboratori distribuiti in oltre una
dozzina di datacenters nel mondo.
Infrastruttura operativa di Google 1/3
ALCUNE PRECISAZIONI:
 Informazioni e notizie su tutto ciò che riguarda Google
sono state nel corso degli ultimi anni, imprecise e poco
dettagliate (rilasciate in maniera anonima o da personale
interno).
 Nel proseguio vedremo l’organizzazione del cluster
cosi’ come descritta nel documento (dicembre 2000).
 A conclusione dell’analisi cercheremo di fare alcune
considerazioni su come potrebbe essersi evoluta
architettura.
Infrastruttura operativa di Google 2/3
Organizzazione tipica di un datacenter (vista dall’alto)




2 switch Foundry BigIron 8000, collegati alle linee OC48 e OC12.
40 rack interconnessi via Gbit Ethernet (doppio link) a entrambi gli switch
(ridondanza).
Ogni Foundry Switch puo’ gestire fino a 128 interfacce Gbit Ethernet, e quindi
fino a 64 rack.
Un rack per ogni Foundry Switch con funzioni di load balancing e monitoring.
Infrastruttura operativa di Google 3/3




Switch centrale HP
Procurve 4000.
20 pc sopra e 20 sotto
(uno per rack-unit).
40 interfacce Ethernet
100 Mbit e 2 interfacce
Ethernet 1 Gbit.
80 rack-unit in totale
(fronte e retro)
Rack in dettaglio
Le unità del cluster


Ogni rack-unit contiene un’unità di elaborazione
“completa” con le seguenti caratteristiche:
- 2 hd Maxtor capacità 40-80 GB, 5400-7200 rpm
- 256 MB SDRAM 100-133 Mhz
- processore Intel tipicamente:
a) Celeron 533 Mhz
b) Pentium III 800 Mhz
- motherboard e alimentatore
- sistema operativo: Linux 2.2.x (RedHat modificata)
- costo finale variabile tra 1300$ e 1700$
Domanda: perché queste configurazioni di livello
medio-basso?
Fattori di progettazioni




Utilizzare cluster basati su pc di fascia media
piuttosto che costosi server multiprocessore.
Molto vantaggioso in termini economici, di
consumi energetici, dissipazione di calore e
raffreddamento.
Tutti i fattori vengono calcolati e analizzati in
accoppiata con il fattore performance.
Costi aggiuntivi derivanti amministrazione di
sistema e riparazioni: facilmente ammortizzabili.
Affidabilità hardware e software




La disponibilità continua ad operare dell’intera
architettura è fondamentale.
Dal punto di vista hardware:
- 2%/3% dei pc sostituiti ogni anno: guasti ai dischi e
alla ram (95% dei casi) e problemi motherboard (5%
rimanente).
- rari problemi agli switch dei vari rack.
Dal punto di vista software:
- problemi di reboot o crash software
- meccanismi che isolano i nodi “inattivi” o interessati
da attività anomala
Problemi marginali dovuti alla rete o all’alimentazione.
Ipotesi sull’architettura attuale 1/2






Parco macchine di più di 100.000 elaboratori.
Più di una dozzina di datacenters nel mondo.
100.000 / 15 ≈ 6700 elaboratori per datacenter.
Incrementato il numero di rack (in media raddoppiato)
e di rack-unit per rack.
Incrementato il numero dei link verso la rete Internet.
I datacenter distribuiti nel mondo permettono di
assicurare tempo di risposta “sempre” inferiori i 250 ms
e mai superiori il mezzo secondo.
Ipotesi sull’architettura attuale 2/2


In base all’evoluzione del mercato un’ unità di
elaborazione:
- 2/4 hd con capacità 120-160Gb 7200 rpm
- 512MB-1GB Ram con ECC o 2GB non ECC
- CPU: classe Xeon o Pentium 4
- sistema operativo: GNU/Linux 2.4.x o 2.6.x
- costo calcolato: sui 1000-1200 euro
Switch della stessa fascia, eventualmente con più
interfacce.
Stime sulle performance attuali

Banda necessaria per la gestione delle query:
300 milioni query/day x 4000B/query x 8 bits/B
24x60x60 secondi/day
120 Mbit/s

Dicembre 2000:
70 milioni di query
26 Mbit/s
Banda necessaria per l’indicizzazione delle pagine:
8 miliardi pagine x 30KB/page x 8 bits/B
24x60x60 secondi/day x 7 days
3,5 Gbit/s
Dicembre 2000:
1 miliardo di pagine
59 Mbit/s
Conclusioni 1/2




Difficoltà di distribuire e effettuare il calcolo del
page rank delle singole pagine indicizzate, senza che
l’utente se ne accorga.
I datacenter vengono aggiornati un po’ alla volta
dopo il Deep Crawl: questo vuol dire che alcune
risposte alle query degli utenti possono sembrare
“incongruenti”.
Cosiddetto Fenomeno del GOOGLE DANCE
http://www.seo-guy.com/seo-tools/google-dc.php
Conclusioni 2/2




Google è tuttora il motore di ricerca più famoso
e diffuso sul web.
Yahoo però sta recuperando terreno: ha
acquisito AllTheWeb, Altavista, Overture,
Teoma.
Nuova sfida lanciata da Microsoft con MSN
(ancora in versione beta).
Il futuro è quindi incerto e aperto.
Google oggi…

Direttamente dalla home page di Google.








Pagine web indicizzate: oltre 8 miliardi
Immagini: 800 milioni
Messaggi Usenet: 845 milioni
Interfacce Google in lingue diverse: oltre 100
Lingue diverse per i risultati: 35
Domini Internazionali: oltre 100
Dipendenti: 2500 in tutto il mondo
Nuovi datacenter vengono aperti in segreto!
http://crm.ittoolbox.com/news/dispnews.asp?i=124767&t=99
Bibliografia e riferimenti
[1] “Putting it all together: The Google Cluster of PCs”
– Hennessy, Patterson –
[2] “The Anatomy of a Large-Scale Hypertextual Web
Search Engine”
– Page, Brin –
[3] “Web Search for a Planet: The Google Cluster
Architecture”
– Barroso, Dean, Holze –
[4] http://www.googlerank.com
[5] http://www.search-marketing.info/searchengines/major-search-engines/google.htm