Google BigTable e l’archiviazione dei dati storici (…e altre congetture)

nbriani · 04-12-06, 20:05

Ho letto solo in questi giorni questo articolo di fine agosto di Jeffrey Dean (google) e altri autori, su “BigTable” il “sistema di archiviazione distribuita” della base dati di Google.

Nato nel 2004 e effettivamente messo in produzione solo nel 2005 il progetto “BigTable” è un progetto di ingegnerizzazione degli archivi dati di Google con lo scopo dichiarato di migliorare e ottimizzare prestazioni (velocità, consumi, ecc) e scalabilità dell’infrastruttura e di offrire un servizio comune e centralizzato ad uso di tutte le applicazioni (attraverso opportune API che standardizzano i metodi di scrittura/lettura/archiviazione dati anche per applicazioni molto diverse come Google Heart, Google Base, Orkut, il motore di ricerca stesso … ecc ).

L’articolo, molto approfondito e molto tecnico per chi si interessa di ottimizzazione di database di grandi dimensioni, rivela pero’ tutta una serie argomenti “lato SEO” abbastanza interessanti facendo luce, ad esempio, sul sistema di archiviazione dei dati storici di Google di cui tanto si parlo’ ai tempi dei brevetti.

Per cominciare, cosa è "BigTable" e come funziona?

A grandi linee si tratta di una nuova organizzazione dei dati “normalizzata” ad uso di molteplici e differenti applicazioni : Approssimando volutamente immaginate un'unica grande tabella “padre” (BigTable appunto) , in cui tutti e variegati dati vengono archiviati sempre allo stesso modo:
un record per Riga e con ciascuna Colonna ad indicare una specifica variabile/parametro.

L’articolo analizza gli aspetti e i vantaggi della architettura in termini di prestazioni, velocità, consumi energetici, dislocazione su piu’ datacenter, scalabilità attraverso l’introduzione di nuovi server ecc ecc ma tralascio questi aspetti per concentrarmi invece su aspetti secondari ma che hanno attirato la mia attenzione:

BigTable e …i Brevetti sui dati storici

Si è discusso a lungo di come Google possa tenere in considerazione tutti quei dati storici di cui parlavano i famosi brevetti, in particolare sul se e come potesse archiviare davvero quella gran mole di dati e le loro variazioni nel tempo. Ebbene l’articolo toglie ogni dubbio:

Google è perfettamente in grado di registrare le variazioni storiche di TUTTI i paramentri che registra e lo fa attraverso una procedura “standard” comune a tutte le sue applicazioni !

(se poi gli algoritmi ne tengono conto o meno… è tutto un altro discorso… ma diventa, certo, assai probabile)

Infatti Jeffrey Dean, descrive candidamente come BigTable registri “fotografie” ("Timestamps") dei dati a precisi intervalli temporali che vengono memorizzati al suo interno : dice “… immaginate a titolo di esempio, di dover archiviare dati di pagine web e loro referenze in rete (anchor) …. Ecco come si presenterebbero i dati in BigTable :”

(della CNN - interessante l’archiviazione rovesciata della url - si archiviano 2 famiglie di dati: il contenuto HTML della pagina e i testi degli anchor “CNN” e “CNN.com”- presenti nei documenti cnnsi.com e my.look.ca .- )

A ciascuna URL (riga) corrispondono due famiglie di dati (colonne) : il contenuto HTML (contents) e i testi degli ANCHOR di cui Dean ipotizza l’archiviazione della specifica frase di ancora.
(fa impressione vedere nero su bianco certe considerazioni, no?)

Ma di ciascuna URL viene descritto l’archiviazione di “Timestamps” cioè della archiviazione degli stessi dati presi in specifici momenti diversi (t3, t5, t6) avvalorando appunto ogni ipotesi sulla certezza o meno che Google fosse in grado di registrare dati storici… ora sappiamo che lo fa , lo puo’ fare e lo puo’ fare comodamente per qualunque dato registri di un documento web… cio’ rende estremamente probabile quindi che alcuni o forse tutti i possibili parametri descritti nei famosi brevetti siano davvero in uso agli algoritmi di ranking.

Non solo ma i metodi di archiviazioni dei dati e le loro variazioni nel tempo sembrano proprio coincidere con le supposizioni che facevamo qui a proposito della considerazione che Google poteva avere della variazione nel tempo del numero di BL : incredibilmente l’ipotesi di un archiviazione a “punti discreti” (sul cui numero vedi piu’ avanti) a cui arrivammo insieme a Paocavo sembra proprio coincedere (a grandi linee !) con i metodi reali del motore… nel caso specifico gli algoritmi di Google si potrebbero trovare proprio a dover gestire un certo numero di valori nel tempo (“timestamps”) della variabile “numero BL” (se esiste davvero!) da dover interpretare…

Ovviamente la tabella della immagine sopra è solo un esempio di come si potrebbero archiviare dei dati relativi a “pagine web” ma dato che il sistema è uno standard per Google è chiaro che anche i dati di “indicizzazione” (index server) da una parte e i dati relativi ai contenuti dei documenti web dall’altra , ambedue ad uso degli algoritmi di ranking del motore di ricerca hanno lo stesso tipo di organizzazione.

Sulla duplice base dati di Google (indicizzazione e contenuti) potete leggere quest’altro mio articolo oppure (meglio! ma in inglese) quest’ altro articolo ("Web Search for a Planet: The Google Cluster Architecture") dello stesso Jeffrey Dean.

<Piccola digressione> : BigTable – BigDaddy …un assonanza casuale?

Matt Cutts parlo’ di BigDaddy cosi’ “….But this is neither an update nor a data refresh; this is new infrastructure. It should be much more subtle/gentle than an update….” ..non un vero e proprio “update” ma un cambio della infastruttura… (!)
Non si puo’ non notare una perfetta coincidenza.. BigDaddy “ il grande papa’ “ potrebbe proprio far riferimento a qualche cambio infrastrutturale imposto dalla nuova infrastruttura data da BigTable (il grande “padre” di tutti i dati della azienda!) anche se le date dichiarate non coincidono perfettamente (c’è una differenza di qualche mese)

Probabilmente una ottimizzata organizzazione proprio dei dati storici potrebbe esser stata alla base di quel update . Possibile?
</ fine della digressione>

Jeffrey Dean conclude l’articolo con una tabella riassuntiva dei dati immagazzinati nella nuova infrastruttura alla data di pubblicazione dell’articolo, ed è attraverso una attenta lettura anche di questa che emergono altre interessanti considerazioni: (Simone Carletti "Weppos" ne parlo’ qui , quando usci’ l’articolo soffermandosi sui dati relativi ai terabyte di dati immagazzinati dalle varie procedure)

(Il crawl di google genra l’archivio piu’ grande: 850 terabyte! Molto piu’ ridotti i dati di Analitics, google base, Google earth e gli altri…)

Vediamo quali altre ipotesi / considerazioni si possono fare:

Sono due e molto differenti gli archivi di Google , appunto (dicevamo sopra) Indicizzazione e Archivio “contenuti”(in fondo una sorta di “replica” normalizzata dell’intero web!!):

L’”indicizzazione” (probabilmente il secondo nella tabella qui sopra) è un archivio alfabetico di tutte le singole parole nelle varie lingue a cui vengono associati i documenti piu’ rilevanti ( o comunque tutti gli ID dei documenti che le contengono e che vengono memorizzati nel secondo archivio “contenuti”) . Come ci dice lo stesso Jeffrey Dean qui, per query multiple sono poi gli algoritmi “on time” a costruire il ranking …

Ma quanti e quali dati vengono indicizzati?

La tabella candidamente rivela 200 miliardi di “celle scritte” e 2 (solo due!) famiglie di dati archiviati : ipotizzo : “keyword” – “Id documento web” (possibile?)

La lingua italiana ha circa 50.000 parole (approssimo volutamente), le lingue gestite da Google sono dell’ordine delle 20 o 30, quindi sempre approssimando, l’archivio di indicizzazione è un qualcosa composto da circa 1.000.000 righe (per ogni “timestamps” di BigTable), quindi piu’ o meno:

200 miliardi di celle / (diviso) 1.000.000 righe farebbe circa 200.000 celle occupate per riga (e quindi circa 200.000 riferimenti medi a pagine web (id doc web) per ciascuna parola e per ciascuna lingua… plausibile?
Certo sembrano pochi (si pensi che si parla pero’ di numero medio per qualunque parole in qualunque lingua) , e non ho nemmeno considerato i “Timestamps” possibilmente archiviati ma visti i numeri i gioco e se le ipotesi e le approssimazioni che ho fatto reggono, sono tentato di concludere che all’epoca della tabella o

Google NON teneva conto di “Timestamp” di indicizzazione nel tempo oppure il loro numero è dell’ordine delle poche unità… Voi che ne pensate?

<Piccola II digressione>

Se l’organizzazione di cui sopra “regge” non vedo posto al trattamento dei cluster semantici e degli acronimi se non di fase di algoritmi On-time
</ fine della digressione>

Andiamo avanti e arriviamo alla parte piu’ “succulenta” parliamo dell’archivio vero e proprio del motore:

La tabella ci dice 1.000 miliardi di celle di BigTable occupate e 16 famiglie di dati !!

Google riesce quindi a replicare, normalizzare e fotografare nel tempo l’intero web in circa 1000 miliardi di dati, cio’ significherebbe che se sono 5/6/7 miliardi i documenti indicizzati, mediamente

vengono quindi archiviate 200 celle (quindi “parametri”) per ciascun documento divise in 16 tipologie di dati…

Possibile?

Se senza dubbio i Link sono una delle 16 famiglie (vedi l’esempio nella prima tabella) forse 200 celle divise pure per alcune “Timestamps” sembrano poche… ma di nuovo dobbiamo considerare che stiamo parlando della media sulla totalità dei documenti i rete…

Certo visti i numeri sono tentato ad ipotizzare che se Google tiene uno storico dei dati questo non sia eccessivamente enorme (almeno alla data della pubblicazione della tabella) e che sia ipotizzabile un numero dell’ordine di qualche unità … 3, 5, ? Ovviamente non vuol dire necessariamente “gli ultimi 3, 5 valori” ma magari il primo, l’ultimo e alcuni valori intermedi che potrebbero comunque dare al motore una idea di massima sull’andamento storico (anche se non troppo accurato) di tutti i dati nel tempo…

Starà poi agli algoritmi dare un senso ed una interpretazione corretta a questi dati…
Certo un altro dato emerge prepotente dall’analisi del documento: non sappiamo come si fatta ma la

“formula magica “ di Google pare proprio che abbia … 16 ingredienti ! WOW !! Plausibile?

16 famiglie di dati sono infatti quelli archiviati… e allora proviamo a trovarli insieme:

“HTML” , “ANCHOR/BL” , PR , (contenuto html, link e pr questa la base.. siamo a 3)
LINGUA, TIPO DOC (due dati sul tipo di contenuto…. E siamo a 5 ne manca 11!! )
IP, ADMIN-C, SCADENZA (qualche dato sul dominio ? e siamo a 8 …)

Quali altri paramentri ? … ipotizziamo:

Dati social? Click nelle serp, che altro? …
Penalizzazioni ? (sarà sicuramente un dato di cui gli algo tengono conto!)
Trust Rank ?
Altro? … mi date una mano? J

N.B.
Non sono un ingegnere di Google (e si vede!) quindi NON prendete alla lettera questi miei ragionamenti a “voce alta” frutto soltanto di una mia personale interpretazione di alcuni articoli letti in rete... se gli ho postati è solo per sottoporli ad un contradditorio critico per un sempre auspicabile e interessante confronto/studio .

Nicola

P.s.

Avviso ai relatori del Convegno GT (soprattutto quelli del dibattito “botta e risposta” del secondo giorno) … non penserete mica che vi risparmi qualche domanda sull’argomento, vero?

04-12-06, 20:05	#1 (permalink)
nbriani ModSenior Data di registrazione: May 2005 Ubicazione: Firenze Messaggi: 1,938	Google BigTable e l’archiviazione dei dati storici (…e altre congetture) Ho letto solo in questi giorni questo articolo di fine agosto di Jeffrey Dean (google) e altri autori, su “BigTable” il “sistema di archiviazione distribuita” della base dati di Google. Nato nel 2004 e effettivamente messo in produzione solo nel 2005 il progetto “BigTable” è un progetto di ingegnerizzazione degli archivi dati di Google con lo scopo dichiarato di migliorare e ottimizzare prestazioni (velocità, consumi, ecc) e scalabilità dell’infrastruttura e di offrire un servizio comune e centralizzato ad uso di tutte le applicazioni (attraverso opportune API che standardizzano i metodi di scrittura/lettura/archiviazione dati anche per applicazioni molto diverse come Google Heart, Google Base, Orkut, il motore di ricerca stesso … ecc ). L’articolo, molto approfondito e molto tecnico per chi si interessa di ottimizzazione di database di grandi dimensioni, rivela pero’ tutta una serie argomenti “lato SEO” abbastanza interessanti facendo luce, ad esempio, sul sistema di archiviazione dei dati storici di Google di cui tanto si parlo’ ai tempi dei brevetti. Per cominciare, cosa è "BigTable" e come funziona? A grandi linee si tratta di una nuova organizzazione dei dati “normalizzata” ad uso di molteplici e differenti applicazioni : Approssimando volutamente immaginate un'unica grande tabella “padre” (BigTable appunto) , in cui tutti e variegati dati vengono archiviati sempre allo stesso modo: un record per Riga e con ciascuna Colonna ad indicare una specifica variabile/parametro. L’articolo analizza gli aspetti e i vantaggi della architettura in termini di prestazioni, velocità, consumi energetici, dislocazione su piu’ datacenter, scalabilità attraverso l’introduzione di nuovi server ecc ecc ma tralascio questi aspetti per concentrarmi invece su aspetti secondari ma che hanno attirato la mia attenzione: BigTable e …i Brevetti sui dati storici Si è discusso a lungo di come Google possa tenere in considerazione tutti quei dati storici di cui parlavano i famosi brevetti, in particolare sul se e come potesse archiviare davvero quella gran mole di dati e le loro variazioni nel tempo. Ebbene l’articolo toglie ogni dubbio: Google è perfettamente in grado di registrare le variazioni storiche di TUTTI i paramentri che registra e lo fa attraverso una procedura “standard” comune a tutte le sue applicazioni ! (se poi gli algoritmi ne tengono conto o meno… è tutto un altro discorso… ma diventa, certo, assai probabile) Infatti Jeffrey Dean, descrive candidamente come BigTable registri “fotografie” ("*Timestamps") dei dati a precisi intervalli temporali che vengono memorizzati al suo interno : dice “… immaginate a titolo di esempio,* di dover archiviare dati di pagine web e loro referenze in rete (anchor) …. Ecco come si presenterebbero i dati in BigTable :” (della CNN - interessante l’archiviazione rovesciata della url - si archiviano 2 famiglie di dati: il contenuto HTML della pagina e i testi degli anchor “CNN” e “CNN.com”- presenti nei documenti cnnsi.com e my.look.ca .- ) A ciascuna URL (riga) corrispondono due famiglie di dati (colonne) : il contenuto HTML (contents) e i testi degli ANCHOR di cui Dean ipotizza l’archiviazione della specifica frase di ancora. (fa impressione vedere nero su bianco certe considerazioni, no?) Ma di ciascuna URL viene descritto l’archiviazione di “Timestamps” cioè della archiviazione degli stessi dati presi in specifici momenti diversi (t3, t5, t6) avvalorando appunto ogni ipotesi sulla certezza o meno che Google fosse in grado di registrare dati storici… ora sappiamo che lo fa , lo puo’ fare e lo puo’ fare comodamente per qualunque dato registri di un documento web… cio’ rende estremamente probabile quindi che alcuni o forse tutti i possibili parametri descritti nei famosi brevetti siano davvero in uso agli algoritmi di ranking. Non solo ma i metodi di archiviazioni dei dati e le loro variazioni nel tempo sembrano proprio coincidere con le supposizioni che facevamo qui a proposito della considerazione che Google poteva avere della variazione nel tempo del numero di BL : incredibilmente l’ipotesi di un archiviazione a “punti discreti” (sul cui numero vedi piu’ avanti) a cui arrivammo insieme a Paocavo sembra proprio coincedere (a grandi linee !) con i metodi reali del motore… nel caso specifico gli algoritmi di Google si potrebbero trovare proprio a dover gestire un certo numero di valori nel tempo (“timestamps”) della variabile “numero BL” (se esiste davvero!) da dover interpretare… Ovviamente la tabella della immagine sopra è solo un esempio di come si potrebbero archiviare dei dati relativi a “pagine web” ma dato che il sistema è uno standard per Google è chiaro che anche i dati di “indicizzazione” (index server) da una parte e i dati relativi ai contenuti dei documenti web dall’altra , ambedue ad uso degli algoritmi di ranking del motore di ricerca hanno lo stesso tipo di organizzazione. Sulla duplice base dati di Google (indicizzazione e contenuti) potete leggere quest’altro mio articolo oppure (meglio! ma in inglese) quest’ altro articolo ("Web Search for a Planet: The Google Cluster Architecture") dello stesso Jeffrey Dean. <Piccola digressione> : BigTable – BigDaddy …un assonanza casuale? Matt Cutts parlo’ di BigDaddy cosi’ “….But this is neither an update nor a data refresh; this is new infrastructure. It should be much more subtle/gentle than an update….” ..non un vero e proprio “update” ma un cambio della infastruttura… (!) Non si puo’ non notare una perfetta coincidenza.. BigDaddy “ il grande papa’ “ potrebbe proprio far riferimento a qualche cambio infrastrutturale imposto dalla nuova infrastruttura data da BigTable (il grande “padre” di tutti i dati della azienda!) anche se le date dichiarate non coincidono perfettamente (c’è una differenza di qualche mese) Probabilmente una ottimizzata organizzazione proprio dei dati storici potrebbe esser stata alla base di quel update . Possibile? </ fine della digressione> Jeffrey Dean conclude l’articolo con una tabella riassuntiva dei dati immagazzinati nella nuova infrastruttura alla data di pubblicazione dell’articolo, ed è attraverso una attenta lettura anche di questa che emergono altre interessanti considerazioni: (Simone Carletti "Weppos" ne parlo’ qui , quando usci’ l’articolo soffermandosi sui dati relativi ai terabyte di dati immagazzinati dalle varie procedure) (Il crawl di google genra l’archivio piu’ grande: 850 terabyte! Molto piu’ ridotti i dati di Analitics, google base, Google earth e gli altri…) Vediamo quali altre ipotesi / considerazioni si possono fare: Sono due e molto differenti gli archivi di Google , appunto (dicevamo sopra) Indicizzazione e Archivio “contenuti”(in fondo una sorta di “replica” normalizzata dell’intero web!!): L’”indicizzazione” (probabilmente il secondo nella tabella qui sopra) è un archivio alfabetico di tutte le singole parole nelle varie lingue a cui vengono associati i documenti piu’ rilevanti ( o comunque tutti gli ID dei documenti che le contengono e che vengono memorizzati nel secondo archivio “contenuti”) . Come ci dice lo stesso Jeffrey Dean qui, per query multiple sono poi gli algoritmi “on time” a costruire il ranking … Ma quanti e quali dati vengono indicizzati? La tabella candidamente rivela 200 miliardi di “celle scritte” e 2 (solo due!) famiglie di dati archiviati : ipotizzo : “keyword” – “Id documento web” (possibile?) La lingua italiana ha circa 50.000 parole (approssimo volutamente), le lingue gestite da Google sono dell’ordine delle 20 o 30, quindi sempre approssimando, l’archivio di indicizzazione è un qualcosa composto da circa 1.000.000 righe (per ogni “timestamps” di BigTable), quindi piu’ o meno: 200 miliardi di celle / (diviso) 1.000.000 righe farebbe circa 200.000 celle occupate per riga (e quindi circa 200.000 riferimenti medi a pagine web (id doc web) per ciascuna parola e per ciascuna lingua… plausibile? Certo sembrano pochi (si pensi che si parla pero’ di numero medio per qualunque parole in qualunque lingua) , e non ho nemmeno considerato i “Timestamps” possibilmente archiviati ma visti i numeri i gioco e se le ipotesi e le approssimazioni che ho fatto reggono, sono tentato di concludere che all’epoca della tabella o Google NON teneva conto di “Timestamp” di indicizzazione nel tempo oppure il loro numero è dell’ordine delle poche unità… Voi che ne pensate? <Piccola II digressione> Se l’organizzazione di cui sopra “regge” non vedo posto al trattamento dei cluster semantici e degli acronimi se non di fase di algoritmi On-time </ fine della digressione> Andiamo avanti e arriviamo alla parte piu’ “succulenta” parliamo dell’archivio vero e proprio del motore: La tabella ci dice 1.000 miliardi di celle di BigTable occupate e 16 famiglie di dati !! Google riesce quindi a replicare, normalizzare e fotografare nel tempo l’intero web in circa 1000 miliardi di dati, cio’ significherebbe che se sono 5/6/7 miliardi i documenti indicizzati, mediamente vengono quindi archiviate 200 celle (quindi “parametri”) per ciascun documento divise in 16 tipologie di dati… Possibile? Se senza dubbio i Link sono una delle 16 famiglie (vedi l’esempio nella prima tabella) forse 200 celle divise pure per alcune “Timestamps” sembrano poche… ma di nuovo dobbiamo considerare che stiamo parlando della media sulla totalità dei documenti i rete… Certo visti i numeri sono tentato ad ipotizzare che se Google tiene uno storico dei dati questo non sia eccessivamente enorme (almeno alla data della pubblicazione della tabella) e che sia ipotizzabile un numero dell’ordine di qualche unità … 3, 5, ? Ovviamente non vuol dire necessariamente “gli ultimi 3, 5 valori” ma magari il primo, l’ultimo e alcuni valori intermedi che potrebbero comunque dare al motore una idea di massima sull’andamento storico (anche se non troppo accurato) di tutti i dati nel tempo… Starà poi agli algoritmi dare un senso ed una interpretazione corretta a questi dati… Certo un altro dato emerge prepotente dall’analisi del documento: non sappiamo come si fatta ma la “formula magica “ di Google pare proprio che abbia … 16 ingredienti ! WOW !! Plausibile? 16 famiglie di dati sono infatti quelli archiviati… e allora proviamo a trovarli insieme: “HTML” , “ANCHOR/BL” , PR , (contenuto html, link e pr questa la base.. siamo a 3) LINGUA, TIPO DOC (due dati sul tipo di contenuto…. E siamo a 5 ne manca 11!! ) IP, ADMIN-C, SCADENZA (qualche dato sul dominio ? e siamo a 8 …) Quali altri paramentri ? … ipotizziamo: Dati social? Click nelle serp, che altro? … Penalizzazioni ? (sarà sicuramente un dato di cui gli algo tengono conto!) Trust Rank ? Altro? … mi date una mano? J N.B. Non sono un ingegnere di Google (e si vede!) quindi NON prendete alla lettera questi miei ragionamenti a “voce alta” frutto soltanto di una mia personale interpretazione di alcuni articoli letti in rete... se gli ho postati è solo per sottoporli ad un contradditorio critico per un sempre auspicabile e interessante confronto/studio . Nicola P.s. Avviso ai relatori del Convegno GT (soprattutto quelli del dibattito “botta e risposta” del secondo giorno) … non penserete mica che vi risparmi qualche domanda sull’argomento, vero?
	__________________ Web Marketing Consultant Focus on: IV Convegno GT ! Ultima modifica di nbriani : 04-12-06 20:35.