¿Cómo funciona una consulta en una vuelta enorme base de datos con latencia insignificante?

Question

Por ejemplo, cuando se busca algo en Google, los resultados vuelven casi-instantánea.

Yo entiendo que las clases de Google y las páginas que indexa con algoritmos etc., pero me imagino que no resulta factible para los resultados de cada consulta puede ser indexado (y los resultados son personalizados, lo que hace esto aún más inviable)?

Por otra parte, ¿no la latencia de hardware en el hardware de Google ser enorme? Incluso si los datos de Google se almacena en todos los SSD Tb / s, me imagino que la latencia de hardware a ser enorme, dada la enorme cantidad de datos de proceso.

¿El MapReduce ayuda a resolver este problema?

EDIT: Bueno, por lo que entiendo que las búsquedas populares pueden almacenar en caché en la memoria. Pero ¿qué pasa con las búsquedas impopulares? Incluso para la búsqueda más oscura que he llevado a cabo, no creo que la búsqueda nunca se ha informado de que más de 5 segundos. ¿Cómo es esto posible?

Answer 1

Bueno, no estoy seguro de si se trata de MapReduce que resuelve el problema, pero sin duda no sería MapReduce suficiente como para resolver todas estas cuestiones que ha planteado. Pero aquí hay cosas importantes a tener en cuenta, y que lo convierten en factible tener tan baja latencia en las consultas de todos estos TB de datos en diferentes máquinas:

1. Distributed Computing: al ser distribuidos, no significa que los índices se distribuyen simplemente en diferentes máquinas, en realidad están replicados a lo largo de diferentes grupos, lo que permite una gran cantidad de usuarios que realizan diferentes consultas con un bajo tiempo de recuperación (sí, grandes empresas pueden permitirse el lujo para que gran parte de las máquinas);
2. almacenamiento en caché: cachés tremendamente reducen el tiempo de ejecución, ya sea para la etapa de rastreo, para la recuperación de páginas, o para la exihibition clasificación y de los resultados;
3. un montón de ajustes: todos los algoritmos anteriores y muy eficientes / soluciones sólo puede ser eficaz si la aplicación es también eficiente. Hay toneladas de (codificados duro) optimizaciones, tales como localidad de referencia, compresión, almacenamiento en caché; todos ellos por lo general appliable a diferentes partes del proceso.

Teniendo en cuenta que, Vamos a tratar de responder a sus preguntas:

pero me imagino que no resulta factible para los resultados de cada consulta puede ser indexada

Sí, sería, y en realidad no es factible tener resultados para cada consulta sea posible . Hay un número infinito de términos en el mundo (incluso si se asume que los únicos términos bien escritas será introducido), y hay un número exponencial de consultas de estos términos n -> inf (2^n). Entonces, ¿qué se hace? El almacenamiento en caché. Pero si hay tantas consultas / resultados, cuáles caché? Almacenamiento en caché de las políticas. Las más frecuentes / populares / relevante-para-el-usuario se almacenan en caché las consultas de los queridos.

No sería la latencia de hardware en el hardware de Google ser enorme? Incluso si los datos de Google se almacenan en TB / s SSDs

Hoy en día, con este tipo de procesadores altamente desarrollados, las personas tienden a pensar que todas las posibles tareas que terminan imprescindible dentro de un segundo (o menos), y que se ocupa de tantos datos, deben ser procesados ??por los procesadores muy potentes con múltiples núcleos y las porciones de la memoria. Sin embargo, la única cosa gobernante de mercado es dinero, y los inversores no están interesados ??en desperdiciarla. Entonces, ¿qué se hace?

La preferencia es en realidad por tener una gran cantidad de máquinas, cada uno usando sencilla / accesible (en términos de coste) procesadores, lo que reduce el precio de la construcción de la multitud de grupos que hay. Y sí, funciona. El principal cuello de botella siempre se reduce en el disco, si se tiene en cuenta el rendimiento de las mediciones simples . Pero una vez que hay tantas máquinas, uno puede permitirse para cargar las cosas a la memoria principal, en lugar de trabajar en los discos duros.

Las tarjetas de memoria son caros para nosotros, simples seres humanos, pero son muy barato para las empresas que compran un montón de este tipo de tarjetas a la vez. Ya que no es costoso, tener tanta memoria como sea necesario para mantener los índices de carga y cachés que nos ocupa no es un problema. Y ya que hay muchas máquinas, no hay necesidad de procesadores rápidos súper, como se puede dirigir consultas a diferentes lugares, donde hay conglomerados de máquinas responsables de la atención regiones geográficas específicas , que permite una mayor < em> especializada de almacenamiento en caché de datos, y aún mejor los tiempos de respuesta.

¿El MapReduce ayuda a resolver este problema?

A pesar de que no creo que la información utilizando MapReduce o no está restringida dentro de Google, no estoy versado sobre este punto. Sin embargo, la implementación de Google de MapReduce (que seguramente es no Hadoop) debe tener un montón de optimizaciones, muchos relacionados con los aspectos discutidos anteriormente. Por lo tanto, la arquitectura de MapReduce que probablementelps guiando cómo los cálculos se distribuyen físicamente, pero hay muchos otros puntos a tener en cuenta para justificar tal velocidad en el tiempo la consulta.

De acuerdo, por lo que entiendo que las búsquedas populares pueden almacenar en caché en la memoria. Pero ¿qué pasa con las búsquedas impopulares?

El siguiente gráfico presenta una curva de cómo las clases de consultas se producen. Se puede ver que hay tres principales tipos de búsquedas, cada una de ellas con aproximadamente un tercio del volumen de consultas (área bajo la curva). La ley muestra el gráfico de potencia y refuerza el hecho de que las consultas más pequeños son los más populares. El segundo tercio de las consultas siguen siendo viables para procesar, ya que tienen pocas palabras. Pero el conjunto de los llamados consultas oscuras , que por lo general consisten en consultas de los usuarios sin experiencia, no son una parte insignificante de las consultas.

Y ahí está el espacio de soluciones novedosas. Ya que no es sólo una o dos consultas (pero un tercio de ellos), deben tener resultados relevantes. Si escribe en algo demasiado oscurecer en una búsqueda en Google, no se necesitará más tiempo para devolver una lista de resultados, pero lo más probable es mostrar algo que inferido 'd gustaría decir. O puede simplemente que no existía un documento con los términos - o incluso reducir su búsqueda a 32 palabras (que acaba de pasar a mí en una prueba al azar aquí)

.

Hay heurística de appliable, que pueden ser o bien hacer caso omiso de algunas palabras, o para tratar de romper la consulta en los más pequeños, y recoger la mayor cantidad de Resultados de docenas. Y todas estas soluciones pueden ser adaptados y ajustados a respetar tiempos de espera factibles de, por ejemplo, a menos de un segundo? : D

Answer 2

MapReduce no tiene nada que ver con nada en tiempo real. Es un marco de procesamiento orientado a lotes adecuados para algunas tareas fuera de línea, como ETL y creación del índice. Google se ha movido fuera de MapReduce para la mayoría de puestos de trabajo ahora, e incluso el ecosistema Hadoop está haciendo lo mismo.

La respuesta a la baja latencia es generalmente para mantener los índices calculados previamente en la memoria. Cualquier cosa que toque el disco es difícil hacer rápido y escala. Esta es la forma más nueva generación de motores SQL como Impala obtener tanta velocidad en comparación con infraestructura basada en MapReduce como Colmena , por ejemplo.

Buscar infraestructura no puede almacenar en caché los resultados de cada consulta. Pero seguro que puede almacenar en caché los resultados intermedios, o, resultados más completos para consultas más frecuentes. Con un poco de almacenamiento en caché puede servir resultados para una minoría significativa de todas las consultas.

Busca también se divide en servidores. Así que una máquina puede delegar al 100 para cada una, una parte del resultado y luego combinarlas.

También puede salirse con cierto grado de aproximación. Google no forman literalmente miles de páginas de resultados de búsqueda; sólo tiene que conseguir la primera página sobre la derecha.

Tenga en cuenta que Google tiene millones de los ordenadores de todo el mundo. Sus consultas van a un centro de datos geográficamente cerca de usted y que sólo está sirviendo su geografía. Esto reduce la mayor parte de la latencia, que es la red y el tiempo no procesar en el centro de datos.

Answer 3

MapReduce no se utiliza en la búsqueda. Fue utilizado hace mucho tiempo para construir el índice; pero es un marco de procesamiento por lotes, y la mayoría de la web no cambia todo el tiempo, por lo que las arquitecturas más nuevos son todos incrementales en lugar de lotes orientado.

Buscar en Google funcionará en gran medida el mismo que funciona en Lucene y elástico de la búsqueda, a excepción de una gran cantidad de afinado ponderación y optimizaciones adicionales. Pero en el corazón mismo, van a utilizar alguna forma de un índice invertido . En otras palabras, que hacen no buscar varios terabytes cuando se introduce una consulta de búsqueda (incluso cuando no se almacena en caché). Probablemente no se fijan en los documentos reales en absoluto. Pero utilizan una tabla de búsqueda que las listas de los documentos que responden a su término de consulta (con despalillado, faltas de ortografía, sinónimos, etc. todas las secuencias previamente). Es probable que recuperar el de los principales 10000 documentos para cada palabra (10k enteros! - sólo unos pocos kb) y calcular los mejores partidos desde que. Sólo si no hay buenos partidos en estas listas, se expanden a los próximos tales bloques, etc.

Las consultas de palabras comunes puede ser fácilmente almacenado en caché; y por medio de preprocesamiento se puede construir una lista de los resultados arriba 10k y luego los rerank de acuerdo con el perfil de usuario. No hay nada que ganar mediante el cálculo de una respuesta "exacta", también. En cuanto a la parte superior 10k resultados es bastante probable; no hay una respuesta correcta; y si alguna parte un mejor resultado en la posición 10001 se pierde, nadie sabrá o aviso (o cuidado). Es probable que ya se clasificó en el procesamiento previo y no habría logrado entrar en el top 10 que se presenta al usuario al final (o la parte superior 3, el usuario realmente mira)

términos raros, por otro lado, no son mucho más que un reto, ya sea -. Una de las listas sólo contiene unos primeros documentos correspondientes, y se puede deseche inmediatamente todas las demás

recomiendo la lectura de este artículo:

La Anatomía de un Gran Escala hipertextual Web motor de búsqueda
Sergey Brin y Lawrence Página
Departamento de Ciencias de la Computación de la Universidad de Stanford, Stanford, CA 94305
http://infolab.stanford.edu/~backrub/google.html

Y sí, eso es los fundadores de Google que escribieron esto. No es el último estado, pero será ya el trabajo a gran escala bastante.