Come fa una query in un ritorno enorme database con una latenza trascurabile?

Question

Ad esempio, quando si cerca qualcosa su Google, i risultati restituiscono pressoché istantaneamente.

Capisco che Google i tipi e le pagine indici con algoritmi ecc, ma immagino che non fattibile per i risultati di ogni singola possibile richiesta da indicizzare (ed i risultati sono personalizzati, che rende questo ancora più fattibile)?

Inoltre, non sarebbe la latenza dell'hardware in hardware di Google essere enorme? Anche se i dati in Google sono stati tutti conservati negli SSD TB / s, immagino la latenza hardware per essere enorme, data l'enorme quantità di dati da elaborare.

non MapReduce aiutare a risolvere questo problema?

EDIT: Okay, quindi capisco che ricerche più frequenti possono essere memorizzate nella cache in memoria. Ma per quanto riguarda le ricerche impopolari? Anche per la ricerca più oscuro ho condotto, non credo che la ricerca è stata mai segnalato per essere più grande di 5 secondi. Come è possibile?

Answer 1

Beh, non sono sicuro se è MapReduce che risolve il problema, ma sicuramente non sarebbero MapReduce da solo di risolvere tutte queste domande sollevate. Ma qui ci sono cose importanti da prendere in considerazione, e che lo rendono fattibile per avere tale bassa latenza su query da tutti questi TB di dati in macchine diverse:

1. Distributed Computing: per essere distribuiti non significa che gli indici sono semplicemente distribuiti in macchine diverse, in realtà sono replicati lungo diversi cluster, che consente per un sacco di utenti che eseguono query diverse con un basso tempo di recupero (sì, grandi aziende possono permettersi per che gran parte delle macchine);
2. la cache: cache di ridurre enormemente il tempo di esecuzione, sia per la fase di scansione, per il recupero di pagine, o per l'exihibition classifica e dei risultati;
3. un sacco di tweaking: tutti gli algoritmi di cui sopra e molto efficiente / soluzioni può essere efficace solo se l'implementazione è anche efficace. Ci sono tonnellate di (hard coded) ottimizzazioni, come frazione di riferimento, compressione, memorizzazione nella cache; tutti loro solito appliable a diverse parti del trattamento.

Considerando che, consente di provare a rispondere alle tue domande:

ma immagino che non fattibile per i risultati di ogni singola possibile query per essere indicizzati

Sì, sarebbe, e in realtà è praticamente impossibile avere risultati per ogni possibile domanda . C'è un numero infinito di termini in tutto il mondo (anche se si assume che solo i termini correttamente farro sarà inserito), e non v'è un numero esponenziale di richieste da questi termini n -> inf (2^n). Quindi, ciò che è fatto? Caching. Ma se ci sono così tanti query / risultati, quelli da cache? Caching politiche. I più frequenti / popolare / rilevanti-per-il-user query sono quelli memorizzati nella cache.

non sarebbe la latenza dell'hardware in hardware di Google essere enorme? Anche se i dati in Google sono stati tutti memorizzati in TB / s SSD

Oggigiorno, con tali processori altamente sviluppati, le persone tendono a pensare che tutte le possibili attività che finitura mosto all'interno di un secondo (o meno), e che si occupa di così tanti dati, devono essere trattati da estremamente potenti processori con più core e un sacco di memoria. Tuttavia, l'unica cosa al potere di mercato è il denaro, e gli investitori non sono interessati a sprecarla. Quindi, che cosa è fatto?

La preferenza è in realtà per avere un sacco di macchine, ciascuna utilizzando semplici / accessibile (in termini di costo) processori, che abbassa il prezzo di costruire la moltitudine di cluster esistono. E sì, funziona. Il collo di bottiglia principale riduce sempre su disco, se si considera semplici misurazioni delle prestazioni . Ma una volta che ci sono tante macchine, può permettersi di caricare le cose alla memoria principale, invece di lavorare sui dischi rigidi.

Le schede di memoria sono costoso per noi, semplici esseri umani, ma sono molto a buon mercato per le imprese che acquistano un sacco di tali carte in una sola volta. Poiché non è costoso, avendo molta memoria, come necessario per mantenere indici di carico e cache in questione non è un problema. E poiché ci sono così tante macchine, non v'è alcuna necessità di processori veloci eccellenti, come è possibile indirizzare le query in posti diversi, e hanno cluster di macchine responsabili per la partecipazione a specifiche regioni geografiche , che consente per più < em> specializzata di caching dei dati, e anche meglio tempi di risposta.

non MapReduce aiutare a risolvere questo problema?

Anche se non credo che le informazioni utilizzando o meno MapReduce è limitato all'interno di Google, io non sono al corrente di questo punto. Tuttavia, l'implementazione di Google di MapReduce (che è sicuramente non Hadoop) deve avere un sacco di ottimizzazioni, molti che coinvolge gli aspetti discussi sopra. Così, l'architettura di MapReduce probabilmente luilps guidando come i calcoli sono distribuiti fisicamente, ma ci sono molti altri punti da tenere in considerazione per giustificare tale velocità nel tempo l'esecuzione di query.

Ok, capisco che le ricerche più frequenti possono essere memorizzate nella cache in memoria. Ma per quanto riguarda le ricerche impopolari?

Il grafico sottostante presenta una curva di come il tipo di query si verificano. Si può vedere che ci sono tre tipi principali di ricerche, ognuno dei quali in possesso di circa 1/3 del volume delle query (area sotto la curva). La legge mostra trama di potere, e rafforza il fatto che le query più piccole sono più popolari. Secondo terzo query sono ancora fattibile elaborare, in quanto titolari poche parole. Ma l'insieme dei cosiddetti query oscuri , che di solito consistono di query non-esperti degli utenti, non sono una parte trascurabile delle query.

E ci si trova lo spazio per nuove soluzioni. Dal momento che non è solo una o due domande (ma un terzo di essi), devono avere rilevanti risultati. Se si digita qualcosa di troppo oscurare in una ricerca su Google, non deve richiedere più tempo per restituire un elenco di risultati, ma sarà molto probabilmente vi mostrerà qualcosa che dedotto si 'd come per dire. Oppure può semplicemente affermare che non vi era alcun documento con tali termini - o anche ridurre la ricerca a 32 parole (che è appena successo a me in un test casuale qui)

.

Ci sono decine di euristica Appliable, che possono essere sia di ignorare alcune parole, o per cercare di rompere la query in quelle più piccole, e raccogliere il maggior numero di popolare risultati. E tutte queste soluzioni possono essere adattate e ottimizzato per rispettare tempi di attesa possibili di, diciamo, meno di un secondo? : D

Answer 2

MapReduce non ha nulla a che fare con il tempo reale qualsiasi cosa. Si tratta di un framework di elaborazione batch-oriented adatta per alcune attività non in linea, come ETL e la costruzione dell'indice. Google si è spostata fuori di MapReduce per la maggior parte dei lavori ora, e anche l'ecosistema Hadoop sta facendo lo stesso.

La risposta a bassa latenza è generalmente di mantenere indici precalcolate in memoria. Tutto ciò che tocca disco è difficile da rendere veloce e la scala. Questo è il modo più recente generazione Hadoop-based motori SQL come Impala ottenere molto di velocità rispetto alle infrastrutture MapReduce-based come Hive , per esempio.

Cerca di infrastrutture non può memorizzare nella cache i risultati di ogni singola query. Ma sicuramente può memorizzare nella cache i risultati intermedi, o, più risultati completi per query principali. Con un po 'di cache si può servire risultati per una minoranza significativa di tutte le query.

La ricerca è anche diviso tra i server. Quindi, una macchina può delegare a 100 per ciascuna ottenere una parte del risultato e poi combinarle.

Si può anche ottenere via con un certo grado di approssimazione. Google non letteralmente forma un migliaio di pagine di risultati di ricerca; è solo per ottenere la prima pagina sulla destra.

Tenga presente che Google ha milioni di computer in tutto il mondo. Le vostre domande stanno andando a un centro dati geograficamente vicino a voi e che sta scontando solo il vostro geografia. Questo taglia la maggior parte della latenza, che è la rete e il tempo non elaborazione nel centro dati.

Answer 3

MapReduce non è usato nella ricerca. E 'stato utilizzato molto tempo fa per costruire l'indice; ma è un quadro elaborazione batch, e la maggior parte del nastro non cambia continuamente, così le architetture più recenti sono tutti incrementale invece di lotto orientato.

la ricerca in Google sarà in gran parte funzionerà lo stesso lavora in Lucene e elasticsearch, tranne che per un sacco di perfezionato ponderazione in più e ottimizzazioni. Ma al cuore molto, useranno una qualche forma di un indice invertito . In altre parole, lo fanno non cercare diversi terabyte quando si entra in una query di ricerca (anche quando non viene memorizzato nella cache). Essi probabilmente non guardano i documenti reali a tutti. Ma usano una tabella di ricerca che le liste che i documenti corrispondenti al termine di query (con diraspatura, errori di ortografia, sinonimi ecc tutti pre-elaborati). Probabilmente recuperare il dei primi 10000 documenti per ogni parola (10k interi! - solo alcuni kb) e calcolare i migliori partite da questo. Solo se non ci sono buone partite in questi elenchi, si espandono per i prossimi tali blocchi etc.

Le query per le parole comuni può essere facilmente memorizzato nella cache; e via pre-elaborazione è possibile costruire una lista di risultati superiore 10k e poi li rerank in base al profilo utente. Non c'è nulla da guadagnare calcolando una risposta "esatta", anche. Guardando in alto 10k risultati è probabile che sufficiente; non esiste una risposta corretta; e se un migliore da qualche risultato in posizione 10001 è mancato, nessuno saprà o preavviso (o cura). E 'probabile che già classificata in giù in pre-elaborazione e non avrebbe fatto nella top 10 che viene presentato all'utente al termine (o la parte superiore 3, l'utente guarda in realtà a)

termini rari, d'altro canto, non sono molto più di una sfida o -. Una delle liste contiene solo alcuni documenti di corrispondenza, e si può immediatamente scartare tutti gli altri

Mi raccomando di leggere questo articolo:

Anatomia di un motore di ricerca su larga scala Hypertextual Web
Sergey Brin e Lawrence Page
Dipartimento di Informatica, Università di Stanford, Stanford, CA 94305
http://infolab.stanford.edu/~backrub/google.html

E sì, questo è i fondatori di Google che hanno scritto questo. Non è l'ultimo stato, ma sarà già opera su larga scala abbastanza.