• Super User

    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 :”

    image

    (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)

    image

    (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 .

    :ciauz:
    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? 😄


  • User

    Bravo Nicola,

    post molto Interessante anche alla luce di quello che sto vedendo in questi giorni nella serp.

    Lino


  • User Attivo

    Complimenti per l'esposizione Nicola 🙂

    mi avevi avvisato certo, ma non pensavo a una cosa del genere 🙂

    Ora cerco di darmi una studiata al paper originale di Google, e visto che ci sono una ripassata ai Dati Storici alla luce di queste nuove considerazioni, così ne possiamo parlare al meglio.

    Nel frattempo, un consiglio spassionato a Beke, visto che sarà relatore al Convegno e vi parlerà di TrustRank: Stefanoo, ripassa i Dati Storici 😄

    ... che prima o poi dovremmo anche finire 😉


  • User Attivo

    Io memorizzerei anche le intestazioni che invia il server...
    E dovremmo essere a otto:
    “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 …)
    header del server


  • Community Manager

    Grazie Nicola per questo ottimo topic di discussione (sei pronto a tradurlo in inglese che lo piazziamo nel Forum GT in English? :D) 🙂

    Nei giorni scorsi sono stato al corso di Madri ed ho avuto il piacere di parlare con Enrico di Google in altri termini, sopratutto da punto di vista che ti offre il Libro Google Story che comprerò presto.

    Oltre ad esse colpito ovviamente dalla mentalità "Google" (che è una cosa davvero eccezionale, che non si compra), sono rimasto colpito dai 100.000 computer a disposizione (è la più grande nel Mondo).

    Ma non computer normali, **computer fatti da loro **per massimizzare una serie di cose.

    Sembra quasi che una delle loro forze sia proprio l'hardware e che uno dei segreti del successo sia li. Si ipotizza che Google abbia creato qualcosa di proprio che non è stato ancora rivelato a livello di Hardware.

    L'argoritmo di Google, già molto funzionale da solo, è stato affiancato da persone umane (quality rater) e quindi ora Google si trova con una struttura ben solida e consolidata che gli permette di avere bei dati e concentrarsi su altro.

    Insomma, un motore macchina+uomo è il massimo e penso che per ancora un pò andrà avanti così.

    Sembra quindi che nell'hardware siano davvero avanti, insomma 100.000 computer e molti fabbricati da loro (pare):)

    Secondo me data la mole di dati raccolta fino ad ora è molto probabile che, grazie ai Quality Rater, Google riesca a dare risultati rilevanti prendendo in esame solo i fattori che ritiene migliori.

    Sempre secondo me, in questi anni, Google ha ricercato sempre di scremare dal suo algoritmo quei fattori che incidono poco sulla qualità delle proprie serp. Capisci che il controllo umano è il massimo 🙂

    E che con questo molti fattori possono anche essere scartati. Riuscendo a risparmiare su molte cose (sia a livello Hardware che a livello di Elettricità che di consumo risorse) può investire di più sul controllo umano e fare test sui fattori importanti.

    Oramai penso che sia arrivato ad un Mix davvero importante (Algoritmo (il TrustRank è stato determinante), Controllo Umano, Hardware).

    Più andremo avanti più Google aumenterà il suo abisso di qualità di risultati dagli altri. E pensare che qualcuno diceva che più andavamo avanti, più sarebbe stato facile riuscire a montare qualcosa di ottimo, sopratutto a livello Hardware, invece Google è troppo avanti.

    Veniamo al Seo: è possibile che quindi Google riesca a dare risultati rilevanti solo con 16 famiglie di dati?

    Non sono un grande tecnico, ma penso che Google cercherà sempre di scremare i fattori che incidono poco.

    Il TrustRank ed i Quality Rater hanno portato tanta qualità e Google ha investito tanto in risorse umane.

    Io quando faccio SEO cerco di concentrarmi su:

    • ottimizzazione normale della pagina, cioè un buon Title e contenuto a tema (senza pensare ai tag)

    • buoni contenuti perchè so che il sito viene visitato da persone come me che deve dare un giudizio per la coerenza con quelle serp

    • link con anchor giusto in varie pagine del sito e su siti che stanno ben in alto nelle proprie Serp

    Quello su cui se posso ci tengo a concentrarmi è la continua crescita di backlink e contenuti. E non uso un metro preciso, ma ogni tanto ovviamente cerco di far trovare qualcosa.

    BigTable è interessante, aspetto di leggere i più tecnici 🙂


  • User Attivo

    Premessa: ho "letto" il documento, non studiato a fondo come vorrei, anche perchè, nonostante l'ottima presentazione di Nicola, mi mancano alcune basi per capire il funzionamento di fondo di BigTable, e, imho, capire il meccanismo di funzionamento di un sistema è fondamentale per poter capire ciò che il sistema è in grado di fare e restituire.

    Fino a 10 minuti fa, e non sono ancora sicuro di esserlo, non sapevo neanche cosa fosse una SSTable: dovrebbe essere una collezione di classi per lavorare con tabelle. Sbaglio?

    Nel documento si legge esplicitamente che "SSTable file format is used internally to store Bigtable data"

    Ma veniamo ad alcune considerazioni su BigTable, preliminari almeno per me che devo ancora studiare a fondo il documento.

    **BigTable e i dati storici
    **
    La cosa certa che mi viene da notare ad un primo impatto è la conferma dell'esistenza dei famosi Dati Storici; con la presentazione che ha fatto Nicola, appare abbastanza chiaro che, con i timestamps, possono archiviare diversi tipi di informazioni, e queste informazioni potrebbero essere trattate da un punto di vista "storico": informazioni relative a cambiamenti, aggiornamenti, ritmi di crescita e quant'altro adesso sappiamo con certezza che possono essere monitorate, e archiviate.

    Che poi queste informazioni storiche possano essere usate negli algoritmi di ranking è un altro discorso: ma a questo punto viene lecito domandarsi "Ma allora il brevetto sui dati storici a cosa serviva?"

    Nel brevetto sui dati storici veniva espressamente detto che alcuni fattori, come l'aggiornamento e il cambiamento dei contenuti, dei link, e soprattuto i ritmi con cui questi cambiamenti vengono effettuati possono essere usati per correggere il punteggio di un documento (una pagina o un intero sito) in fase di ranking.

    Così come si diceva che potevano essere monitorate le preferenze degli utenti in una serp, il traffico, e tutti quei comportamenti che in generale definiamo come user-behavior.

    A riguardo di questo ho trovato un blog dedicato all'OSDI, Operating Systems Design and Implementation (OSDI): http://osdi2006.blogspot.com/2006/10/paper-bigtable-distributed-storage.html, in cui Jeff Dean risponde agli utenti, in particolar modo, in riferimento ai Dati storici:

    alla domanda

    > I am just trying to imagine a scenario where there is a need of 3 most recent versions of a URL ( or a data item) and need for ms granularity for time stamps.

    Jeff risponde

    This is more of a client application question, rather than a BigTable question, but, for our crawling application example, it's often useful to be able to look at multiple versions of page over time to see if the page has changed at all, whether it has changed in relatively minor ways (e.g. a last modified date at the bottom of the page), or if the content on the page has changed substantially. Allowing storage of multiple versions in our data model enables clients to do analyses like this relatively easily.

    Ho sottolineato ciò che si riferisce esplicitamente a quello che abbiamo studiato nell'aggiornamento dei documenti nei dati storici.

    Tornando a BigTable

    Tornando al documento, ripeto, non l'ho studiato a fondo e non sono un'esperto, quindi prendete quello che dico con le molle, e, magari fosse come ipotizza Nicola che si fossero fatti scappare quel numeretto, ma purtroppo non la vedo così: nel senso che quelle 16 famiglie sono secondo me un esempio.

    Partiamo col dire cosa sono le tablet servers:

    Since these tables can be quite large, Bigtable allows dynamic partitions of row, called tablets, which are distributed over many Bigtable servers

    Quindi nel momento in cui queste tabelle in cui vengono archiviati i dati diventano troppo grandi,** Bigtable** può partizionare le righe, presumo a seconda dei timestamps, i "tablet" e distribuibirli sui più server.

    Dalla descrizione della tabella:

    Table 2 provides some data about a few of the tables currently in use.

    Quindi "alcuni dati di alcune delle tabelle correntemente in uso"

    Per esempio, nella descrizione di Google Analytics, riferita a quella tabella, si dice:

    We briefly describe two of the tables used by Google Analytics.

    Cioè quelle due righe che vediamo, secondo me, potrebbero essere due di chissa quante relative ad Analytics.

    Un altra cosa che non riesco a capire bene a fondo...sono queste** famiglie**, anche perchè se sono associate a cluster le cose diventano un po più complicate.

    "some that add new base data, some that read the base data and create derived column families,.."

    Cioè, per come lho interpertato io, quel 16 potrebbe essere un numero generato per esempio dall'archiviazione di un tot di dati.

    Non so se riesco a spiegarmi per bene.

    Comunque secondo me per capire a fondo il funzionamento di Bigtable, bisogna capire per bene le basi su cui si fonda

    Tornando a BigTable e alla tesi sul fatidico 16, sempre in quel link, alla fine, si può leggere:

    "CUT ... A given tablet is owned by one server, but load balancing can shift tablets around. Similarly to tablets, locality groups are partitions of column instead of row."

    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.

    Comunque, gran bel post Nicola: mi hai fatto "lavorare" anche stasera, dopo una giornata a studiare 😄

    Aspettiamo con ansia gli esperti, e qualche volontario che magari si offre di tradurre il documento. 🙂

    Saluti a tutti
    :ciauz:

    PS: scusate per eventuali orrori e strafalcioni; è tardi e più rileggo e formatto più mi sembra incasinato 😄


  • Super User

    Grazie Raele,

    le tue considerazioni (gentilmente anticipate in chat) danno maggiore chiarezza ad alcuni passaggi dell'articolo.

    Ho messo tra i preferiti anche quel Blog dell' OSDI dove nelle risposte agli utenti Dean da ancora qualche altro elemento aggiuntivo..

    Venendo al punto cruciale delle tue considerazioni effettivamente andrebbe capito/approfondito cosa si intende per "Locality Groups" se qualcosa di diverso dalle Tablets anche nella sostanza oltre che nella forma "tecnica" di archiviazione...

    Non so, istintivamente propengo per considerare 16 famiglie di dati come un numero plausibile.. l'ho detto prima, lo pensi anche tu...sembrano poche ma famiglie non vuol dire "numeri singoli" ma classi , tipologie di dati similari nella forma di archiviazione... poi ci sono i dati storicizzati e in piu' i "parametri" on-time gestiti dagli algoritmi di ranking come i cluster semantici, la gestione delle query multiple ed infine non si puo' escludere che una o piu di quelle tipologie non venga generata partendo da un insieme piu' grande di parametri.... altra considerazione se una delle famiglie fosse che so' l'HTML di un documento come nell'esempio della prima tabella, allora sarebbe una famiglia che al suo "interno" puo' contenere un infinita serie di parametri da considerare, no?

    Comunque si concordo che la mia "reverse" analisi presta il fianco a molti punti deboli se analizzata nel particolare... abbiamo troppo poche informazioni per poter giungere a conclusioni certe, resta a mio avviso che dal documento originale si apre un interessante ragionamento il cui impianto generale mette in risalto davvero molti spunti di riflessione...


  • Super User

    [LEFT]L'argomento è davvero interessante Nicola,

    non me la sento di esprimere pareri sulla cosa perchè non ho letto il documento e purtroppo adesso non ho tempo per farlo, ma mi faccio un nodo al fazzoletto 😉

    @Raele: è vero, se aspettiamo ancora un pò più che di dati storici si tratterà di dati... archeologici 😄
    Purtroppo, come puoi vedere ho completamente abbandonato le pubblicazioni da mesi a causa del poco tempo a disposizione 😞

    [/LEFT]


  • Super User

    non ho mai votato una discussione, credo, ma lo faccio ora. mi inchino!! 🙂


  • Super User

    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)


  • Super User

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


  • Super User

    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: :sbav: (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?

    :ciauz:
    Nicola


  • Super User

    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!)

    :ciauz:
    Nicola

    -1 al I convegno GT !


  • User Attivo

    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"


  • Super User

    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) :

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

    :ciauz:
    Nicola


  • Community Manager

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


  • User

    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 😉

    :ciauz:


  • Super User

    @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 😉

    :ciauz:

    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?


  • Community Manager