Considera il meta-point: che cosa sta cercando l'intervistatore?
Una domanda gigantesca come quella non ti sta cercando di sprecare il tuo tempo nel nocciolo di implementare un algoritmo di tipo PageRank o come fare l'indicizzazione distribuita. Invece, concentrati sulla immagine completa di ciò che sarebbe necessario. Sembra che tu sappia già tutti i pezzi grandi (BigTable, PageRank, Map / Reduce). Quindi la domanda è: come li colleghi effettivamente?
Ecco la mia pugnalata.
Fase 1: infrastruttura di indicizzazione (dedica 5 minuti alla spiegazione)
La prima fase di implementazione di Google (o di qualsiasi motore di ricerca) è la creazione di un indicizzatore. Questo è il software che esegue la scansione del corpus di dati e produce i risultati in una struttura dati più efficiente per la lettura.
Per implementarlo, considera due parti: un crawler e un indicizzatore.
Il lavoro del web crawler è di spiderare collegamenti a pagine Web e scaricarli in un set. Il passo più importante qui è evitare di rimanere intrappolati in un loop infinito o su un contenuto infinitamente generato. Inserisci ciascuno di questi collegamenti in un unico file di testo (per ora).
In secondo luogo, l'indicizzatore verrà eseguito come parte di un lavoro Map / Reduce. (Mappare una funzione per ogni elemento nell'input e quindi Ridurre i risultati in una singola 'cosa'.) L'indicizzatore utilizzerà un singolo collegamento Web, recupererà il sito Web e lo convertirà in un file di indice. (Discusso successivamente). Il passaggio di riduzione sarà semplicemente l'aggregazione di tutti questi file di indice in una singola unità. (Piuttosto che milioni di file sfusi.) Poiché le operazioni di indicizzazione possono essere eseguite in parallelo, è possibile coltivare questo lavoro di Map / Reduce su un data center di dimensioni arbitrarie.
Fase 2: specifiche degli algoritmi di indicizzazione (dedica 10 minuti alla spiegazione)
Una volta stabilito come elaborerai le pagine web, la parte successiva spiegherà come è possibile calcolare risultati significativi. La risposta breve qui è "molto più Mappa / Riduci", ma considera il tipo di cose che puoi fare:
- Per ogni sito web, conta il numero di link in entrata. (Le pagine maggiormente collegate a pagine dovrebbero essere "migliori").
- Per ogni sito web, guarda come è stato presentato il link. (I collegamenti in < h1 > o < b > devono essere più importanti di quelli sepolti in < h3 >.)
- Per ogni sito web, guarda il numero di link in uscita. (A nessuno piacciono gli spammer.)
- Per ogni sito web, guarda i tipi di parole usate. Ad esempio, "hash" e "table" indicano probabilmente che il sito Web è correlato a Computer Science. "hash" e "brownies" d'altra parte implicherebbero che il sito riguardasse qualcosa di molto diverso.
Purtroppo non conosco abbastanza i modi per analizzare ed elaborare i dati per essere di grande aiuto. Ma l'idea generale è modi scalabili per analizzare i tuoi dati .
Fase 3: Risultati dei servizi (dedica 10 minuti alla spiegazione)
La fase finale sta effettivamente servendo i risultati. Si spera che tu abbia condiviso alcuni spunti interessanti su come analizzare i dati delle pagine web, ma la domanda è: come lo si interroga effettivamente? Aneddoticamente, il 10% delle query di ricerca di Google ogni giorno non è mai stato visto prima. Ciò significa che non puoi memorizzare nella cache i risultati precedenti.
Non puoi avere una sola "ricerca" dai tuoi indici web, quindi quale vorresti provare? Come guarderesti attraverso diversi indici? (Forse combinando i risultati - forse la parola chiave "stackoverflow" è risultata molto interessante in più indici.)
Inoltre, come lo guarderesti comunque? Che tipo di approcci puoi utilizzare per leggere rapidamente i dati di massime quantità di informazioni? (Sentiti libero di denominare qui il tuo database NoSQL preferito e / o guardare in che cosa consiste Google's BigTable.) Anche se hai un indice fantastico che è estremamente accurato, hai bisogno di un modo per trovare rapidamente i dati. (Ad esempio, trova il numero di rank per "stackoverflow.com" all'interno di un file da 200 GB.)
Problemi casuali (tempo rimanente)
Dopo aver coperto le "ossa" del tuo motore di ricerca, sentiti libero di cimentarti in ogni singolo argomento di cui sei particolarmente informato.
- Prestazioni del frontend del sito web
- Gestione del data center per la mappa / Riduzione dei lavori
- A / B verifica i miglioramenti del motore di ricerca
- Integrazione del volume di ricerca / tendenze precedenti nell'indicizzazione. (Ad esempio, aspettando che i carichi del server di frontend raggiungano il picco 9-5 e muoiano all'inizio del mattino.)
Ovviamente qui ci sono più di 15 minuti di materiale da discutere, ma si spera che sia sufficiente per iniziare.
