Qualche informazione in piu' su BigTable....

oltre all'OSDI (Operating System Design and Implementation , Seattle Wa) del 6/8 novembre scorso, dove è stata fatta una presentazione del progetto e il cui Blog è stato segnalato da Raele ( http://osdi2006.blogspot.com/2006/10/paper-bigtable-distributed-storage.html )

...ho trovato altro materiale interessante : BigTable fu infatti presentato nell'ottobre del 2005 in una conferenza alla Università di Washington, e oltre ad un paio di resoconti dell'evento fatto da studenti nel loro Blog ( http://glinden.blogspot.com/2005/09/googles-bigtable.html e http://andrewhitchcock.org/?post=214 ),

**è disponibile l'intero video della presentazione di Jeffrey Dean **(dura un ora) :

http://video.google.com/videoplay?docid=7278544055668715642&q=bigtable inutile sottolineare che è davvero molto, molto intereessante (oltre che davvero ben fatto: montaggio perfetto e slides perfettamente leggibili)

@Raele-l'Angelo said:

Qui bisogna capire il funzionamento di questi "locality groups", che sono simili alle Tablet servers ma invece di essere partizioni di righe come per le tablet, sono partizioni di colonne: quindi quelle 16 famiglie potrebbero essere le principali per un determinato tipo di dati, soprattuto se fossero variabili in relazione al cluster di appartenenza.

Ciao Raele,

ho ripensato a questa tua affermazione in effetti corretta.. ma, se guardi bene la tabella di cui sopra (la seconda) ci sono dichiarati anche il numero dei "Locality Groups" dell'archivio di "Crawl" ... esattamente 8...
il che potrebbe far supporre che le 16 famiglie (sempre sedici restano) vengono divise in 8 "locality" groups... e non che esistono ulteriori "Locality Groups" con altre "famiglie" non elencate in tabella.. non credi?

Aggiornamento: ho scritto una mail a Jeffrey Dean ... (!;) )

ho cominciato col chiedergli che cosa rappresentavano i due progetti "Crawl" all'interno della tabella di cui sopra e sul perchè quel secondo database avesse due sole famiglie di dati e due locality groups...

Tempo mezz'ora ed ho ricevuto la sua risposta: (mitici sti americani!)

*Hi Nicola,

The two tables contain different data. The larger one contains the full contents of web pages, along with a bunch of other
data about each page, while **the second one just contains some meta information about the pages **(and does't have the contents).

The second table has 2 families and 2 locality groups because sometimes we need to scan just oneof the columns, and don't
want to pay the I/O cost ofn reading both columns of data in order to return just one. This is the main purpose of locality
groups: to segregate different types of data into distinct underlying files, so that scains over subset of column familes are
more eficent.

• Jeff

P.s. My family and I had a great time in Florence this last summer .*

Favoloso! Quanto dichiara sembra proprio avvalorare la mia ipotesi ..l'intero www archiviato in quei 800 TB di dati con le sue 16 famiglie di dati e con 1000 miliardi di celle scritte....

Interessante anche la seconda parte che spiega bene l'utilità e l'utilizzo deli Locality group... e che a mio avviso avvalora anche l'ipotesi sulla composizione del secondo DB (quello di indicizzazione) .

Ho comunque riscritto a Jeff, illustrandogli stavolta nel dettaglio cio' che ho qui supposto e chiedendogli esplicitamente conferma.. bè vediamo che dice e se risponde... vi tengo informati...

Che ne pensate?

Nicola

Mi ha già risposto....

queste le mie domande:

"it'is correct to say " With "BigTable system", Google stored (and "normalized") the world wide web (something like 10 billions of pages indexing) in a "single" table of 800 TB, with 1.000 billions of cells and with 16 types of families datas" ?

e poi (sempre piu' sfacciato e avventato

"... While the second table rappresent the indexing database that maps every query words in a matching id list of documents; correct ? "

Ecco la sua risposta:

"The first table desription above is pretty much correct.
...
*The second table isn't actually an index in the sense of mapping words *
*to lists of documents. We use other systems (that we have not *
*published papers about) for that because the performance and system *
*design constraints are different. Rather, **the second table just ***
**stores meta information about various web pages, like the last time ***
that we crawled the page, a hash of the content of the page at various ***
times, etc. "

Direi che si possa considerare quel "pretty much correct" come una conferma delle supposizioni fatte...(grande! :D) per quel che riguarda il primo DB della tabella...

Si aprono invece diversi interrogativi su quel DB "ridotto" dedicato a "various web pages" (quindi non tutti i documenti?) e che non rappresenta quindi l'indicizzazione, come da me ipotizzato, (gestita invece fuori da BigTable) ma meta-dati aggiuntivi relativi ai documenti chissà per quale motivo archiviati separatamente (magari per la diversa compressione di archiviazione , come si vede dalla tabella) .

Tutto molto interessante... (ora sono 18 le tipologie di dati da scoprire!)

Nicola

-1 al I convegno GT !

Nbriani scrive:

"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?"

Ammetto che un po' mi sono perso dato la difficolta' dell'argomento.

Una prima considerazione, per le sole parole usate da americani ed inglesi in genere conto ad oggi circa 2 milioni di termini, marchi e nomi propri compresi.

Non ho idea per tutte le altre lingue...

La seconda considerazione e' cosa se ne faccia G delle sole parole secche, ma se come ipotizzato parliamo di:

"“keyword” – “Id documento web” (possibile?)"

allora per la sola lingua inglese saremmo ad oggi ad almeno 50 milioni di keywords usate normalmente, non si parla di tutte le possibili combinazioni naturali ed innaturali possibili in base alla commutazione delle parole.

Pertanto se ipotizziamo "keywords" allora per tutte le lingue potremmo ipotizzare anche ed almeno qualche centinaia di milioni di keywords.

Se dividessimo 200 miliardi per soli 200 milioni avremmo circa 1000 siti di riferimento per ogni key usata ad oggi normalmente nelle query.

Il che potrebbe starci, visto che le serp di G visibili per query sono circa di quella lunghezza.

Queste considerazioni mi porterebbero a pensare che:

"Google NON teneva conto di “Timestamp” di indicizzazione nel tempo"

Ciao Agoago,

cerco di riassumere un po' i punti salienti, per cercare di essere un po' piu' chiaro...

no, nessuna delle due "tabelle" di "Crawl" relative alle prime due righe di questa tabella riassuntiva dell'articolo di Jeffrey Dean è relativa all'archivio di indicizzazione di Google come da me qui sopra supposto (quindi tutti i ragionamenti fatti sul numero di parole delle lingue, ecc ecc non hanno rispondenza parlando di BigTable) :

Ambedue fanno invece riferimento all'archiviazione dei contenuti dei documenti mentre l'indicizzazione (cioè il legame parola-id documenti rlevanti) viene gestita esternamente da BigTable come confermato dalla mail che ci ha scritto lo stesso Dean...

La prima nettamente piu' grande è il dato riassuntivo relativamente all'archiviazione dei contenuti delle pagine web, la seconda invece riguarda alcuni meta-dati (relativi alle pagine web, ma non contenuti!) come ad esempio la data di Crawler, come suggerito dallo stesso autore.

Ritornando quindi alla mia supposizione iniziale dovrei correggerla cosi:

Le prime due righe della tabella ci dicono 1.200 miliardi di celle di BigTable occupate e 18 famiglie di dati complessivamente dislocate in 10 differenti locality groups!!

*Google riesce quindi a replicare, normalizzare e fotografare nel tempo l’intero web in circa 1200 miliardi di dati, cio’ significherebbe che se sono dai 5 ai 10 miliardi i documenti indicizzati, mediamente *

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

Possibile?

Se senza dubbio i Link sono una delle 18 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 … 18 ingredienti ! WOW !! Plausibile?

Nicola

Di questo abbiamo parlato nel Botta e Risposta (un Live Forum). Non so se Nicola ha in mente di fare un piccolo riassunto

Ho letto il thread con interesse. Volevo fare qualche commento anche prima ma poi me ne sono scordato...
Dopo aver letto il messaggio di Jeff Dean (e considerando anche i nomi dei progetti nella tabella allegata) credo che la cosa vada interpretata cosi':

Il progetto Crawl riguarda evidentemente gli spider, e non l'indicizzazione (sono due fasi ben diverse).

A occhio e croce, la tabellona piu grande contiene il contenuto vero e proprio delle pagine (piu' vari dati aggiuntivi, tipo http headers, content-type, data, eventuali redirect etc.).

La tabella piu' piccola invece contiene probabilmente soltanto lo stato degli URL da scaricare (e/o scaricati), informazioni quali l'IP, la frequenza con cui "colpire" l'host, eventuali errori/redirect/404 etc., magari qualche informazione su PR, priorita' con cui selezionare gli URL per il crawling, chissa' forse pure qualche info su eventuali sitemaps etc.

Non credo invece che, queste tabelle, contengano informazioni particolari per il ranking vero e proprio (tra il crawling e il ranking ci sono diversi passi intermedi), e poi mi sembra di capire che Jeff Dean ( http://labs.google.com/people/jeff/ ) si occupi piu' di infrastruttura che di "search quality".

Per quanto riguarda i "locality groups" credo che siano principalmente una questione di ottimizzazione (per le performances), cioe' se programmi diversi accedono a gruppi diversi di colonne, possono limitarsi a leggere solo le colonne che gli interessano, invece di caricare l'intera riga.

Considera che qui stiamo parlando di tabellone costruite ad-hoc, non tabelle di database SQL, e non e' possibile formulare queries sql complicate, per cui, se ho capito bene l'articolo, secondo me, questi locality groups sono l'equivalente di query sql precompilate, cioe' se un programma ha bisogno di leggere solo le colonne x,y,z viene creato un locality-group per queste tre colonne (e quindi i dati relativi a queste colonne vengono affidati alle stesse macchine).

Infine, credo che prima di pubblicare l'articolo, sia stato passato sotto esame da gente tipo Matt Cutts per filtrare eventuali informazioni che potessero essere di aiuto ai SEO

@Ray71 said:

Ho letto il thread con interesse. Volevo fare qualche commento anche prima ma poi me ne sono scordato...

Grazie, per essertene "ricordato"

@Ray71 said:

Dopo aver letto il messaggio di Jeff Dean (e considerando anche i nomi dei progetti nella tabella allegata) credo che la cosa vada interpretata cosi':

Il progetto Crawl riguarda evidentemente gli spider, e non l'indicizzazione (sono due fasi ben diverse).

Infatti, avevo fatto una supposizione errata.. lo stesso Dean (Jeff per gli amici! ) lo dice chiaramente, l'indicizzazione non sta in Big Table...

@Ray71 said:

A occhio e croce, la tabellona piu grande contiene il contenuto vero e proprio delle pagine (piu' vari dati aggiuntivi, tipo http headers, content-type, data, eventuali redirect etc.).

La tabella piu' piccola invece contiene probabilmente soltanto lo stato degli URL da scaricare (e/o scaricati), informazioni quali l'IP, la frequenza con cui "colpire" l'host, eventuali errori/redirect/404 etc., magari qualche informazione su PR, priorita' con cui selezionare gli URL per il crawling, chissa' forse pure qualche info su eventuali sitemaps etc.

Quoto. La tabellona contiene "the full contents" (Jeff) delle pagine web... a mio giudizio quindi i "parametri di base" (16 tipologie? ) di ogni successiva elaborazione (ranking)

@Ray71 said:

Non credo invece che, queste tabelle, contengano informazioni particolari per il ranking vero e proprio (tra il crawling e il ranking ci sono diversi passi intermedi), e poi mi sembra di capire che Jeff Dean ( http://labs.google.com/people/jeff/ ) si occupi piu' di infrastruttura che di "search quality".

Infatti. Punto cruciale ... chiaro che il ranking è un altra cosa e probabilmente come dici tu gli algoritmi si basano anche su tabelle di dati ulteriori ... ma l'impressione che ho è che comunque la base di queste, gli ingredienti "primordiali" di algoritmi "di ranking" (o che comunque elaborino parametri ai fini del ranking) possano essere proprio quelli in quella grande prima tabellona...

@Ray71 said:

Per quanto riguarda i "locality groups" credo che siano principalmente una questione di ottimizzazione (per le performances), cioe' se programmi diversi accedono a gruppi diversi di colonne, possono limitarsi a leggere solo le colonne che gli interessano, invece di caricare l'intera riga.

Considera che qui stiamo parlando di tabellone costruite ad-hoc, non tabelle di database SQL, e non e' possibile formulare queries sql complicate, per cui, se ho capito bene l'articolo, secondo me, questi locality groups sono l'equivalente di query sql precompilate, cioe' se un programma ha bisogno di leggere solo le colonne x,y,z viene creato un locality-group per queste tre colonne (e quindi i dati relativi a queste colonne vengono affidati alle stesse macchine).

si esatto è quello che ho capito anchio...

@Ray71 said:

Infine, credo che prima di pubblicare l'articolo, sia stato passato sotto esame da gente tipo Matt Cutts per filtrare eventuali informazioni che potessero essere di aiuto ai SEO

Certo, certo... indiscutibile... comuque, come detto anche al convegno, non è per carpire segreti SEO che è interessante approfondire, ma capire il funzionamento generale del motore di certo aiuta a farci far valutare piu' correttamente il "seo quotidiano" e tutto il suo mondo di ipotesi e teorie....

(per la cronaca, oggi ho scritto pure a Matt Cutts ... vediamo se dice qualcosa al riguardo... gli ho solo chiesto "Bigaddy=Bigtable?" Tra le altre cose il nome Bigdaddy era a sentire Cutts, il nomignolo con cui i bambini chiamavano un webmaster conosciuto durante un incontro il cui nick è .... JEFFM ! ...;) )

@giorgiotave said:

Di questo abbiamo parlato nel Botta e Risposta (un Live Forum). Non so se Nicola ha in mente di fare un piccolo riassunto

Bè... ancora? .. dopo lo scherzetto al convegno (ancora devo smaltire adrenalina ed emozione) ... ancora un intervento , vuoi?

Faccio un estremissima sintesi:

BigTable (sistema di archiviazione in funzione da fine 2005 per diverse applicazioni di Google, tra cui il motore stesso)

1° conclusione : Dati storici e brevetti (?) (L'articolo su BigTable rivela che la storicizzazione dei dati, qualunque essi siano, è nativa e standard in BigTable) ora siamo certi che Google puo' tenerne conto!

2° conclusione (azzardata) : Probabilmente l'analisi fatta con paocavo qui, relativamente ai metodi di tracciamento di dati storici (nel caso specifico il numero di BL di un documento) tramite "punti discreti" è plausibile!

1° ipotesi (azzardata) : BigDaddy = Bigtable ?

2° Ipotesi (iper-azzardata ) : La tabella riassuntiva esposta nell'articolo ci dice diverse cose interessanti sull'archivio di Google

• circa 100/200 dati mediamente archiviati per documento e 16/18 tipologie di dati .... 1000 miliardi di celle occupate per 10 miliardi di documenti, plausibile?
• quindi un numero limitato di "timestamps"? (cioè di intervalli di dati archiviati)

altre idee?

Per i nostalgici...

http://www.readwriteweb.com/hack/2011/07/google-open-sources-nosql-data.php

http://code.google.com/p/leveldb/