¿Cómo regresa una consulta a una gran base de datos con una latencia insignificante?

12

Por ejemplo, al buscar algo en Google, los resultados regresan casi al instante.

Entiendo que Google clasifica e indexa páginas con algoritmos, etc., pero imagino que no es factible indexar los resultados de cada consulta posible (y los resultados son personalizados, lo que hace que esto sea aún más inviable).

Además, ¿no sería enorme la latencia de hardware en el hardware de Google? Incluso si los datos en Google estuvieran todos almacenados en SSD de TB / s, imagino que la latencia del hardware es enorme, dada la gran cantidad de datos para procesar.

¿MapReduce ayuda a resolver este problema?

EDITAR: Ok, entiendo que las búsquedas populares se pueden almacenar en la memoria caché. ¿Pero qué pasa con las búsquedas impopulares? Incluso para la búsqueda más oscura que he realizado, no creo que se haya informado que la búsqueda sea mayor de 5 segundos. ¿Cómo es esto posible?

resgh
fuente

Respuestas:

13

Bueno, no estoy seguro de si es MapReduce el que resuelve el problema, pero seguramente no sería MapReduce solo para resolver todas estas preguntas que planteó. Pero aquí hay cosas importantes a tener en cuenta, y que hacen posible tener una latencia tan baja en las consultas de todos estos TB de datos en diferentes máquinas:

  1. Computación distribuida: al distribuirse no significa que los índices se distribuyan simplemente en diferentes máquinas, en realidad se replican a lo largo de diferentes clústeres, lo que permite que muchos usuarios realicen consultas diferentes con un tiempo de recuperación bajo (sí, las grandes empresas pueden permitirse eso de máquinas);
  2. almacenamiento en caché: los cachés reducen enormemente el tiempo de ejecución, ya sea para el paso de rastreo, para la recuperación de páginas, o para la clasificación y exposición de resultados;
  3. muchos ajustes: todos los algoritmos / soluciones anteriores y muy eficientes solo pueden ser efectivos si la implementación también es eficiente. Hay toneladas de optimizaciones (codificadas), como la localidad de referencia, la compresión, el almacenamiento en caché; todos ellos generalmente aplicables a diferentes partes del procesamiento.

Teniendo en cuenta eso, tratemos de responder a sus preguntas:

pero me imagino que no es posible indexar los resultados de cada consulta posible

Sí, lo sería, y en realidad no es factible tener resultados para cada consulta posible . Hay un número infinito de términos en el mundo (incluso si asume que solo se ingresarán los términos escritos correctamente), y hay un número exponencial de consultas de estos n -> inftérminos ( 2^n). Entonces, ¿qué se hace? Almacenamiento en caché. Pero si hay tantas consultas / resultados, ¿cuáles almacenar en caché? Políticas de almacenamiento en caché. Las consultas más frecuentes / populares / relevantes para el usuario son las que se almacenan en caché.

¿No sería enorme la latencia de hardware en el hardware de Google? Incluso si los datos en Google estuvieran almacenados en SSD de TB / s

Hoy en día, con procesadores tan altamente desarrollados, las personas tienden a pensar que cada tarea posible que debe terminar en un segundo (o menos), y que trata con tantos datos, debe ser procesada por procesadores extremadamente potentes con múltiples núcleos y mucha memoria. Sin embargo, lo único que rige el mercado es el dinero, y los inversores no están interesados ​​en desperdiciarlo. Entonces, ¿qué se hace?

La preferencia es en realidad tener muchas máquinas, cada una con procesadores simples / accesibles (en términos de costo), lo que reduce el precio de construir la multitud de clústeres que existen. Y sí, funciona. El cuello de botella principal siempre se reduce al disco, si considera mediciones simples de rendimiento . Pero una vez que hay tantas máquinas, uno puede permitirse cargar cosas en la memoria principal, en lugar de trabajar en discos duros.

Las tarjetas de memoria son caras para nosotros, simples seres humanos, pero son muy baratas para las empresas que compran muchas de esas tarjetas a la vez. Como no es costoso, no es un problema tener tanta memoria como sea necesaria para cargar índices y mantener cachés a mano. Y dado que hay tantas máquinas, no hay necesidad de procesadores súper rápidos, ya que puede dirigir las consultas a diferentes lugares y tener grupos de máquinas responsables de atender regiones geográficas específicas , lo que permite un almacenamiento en caché de datos más especializado y una respuesta aún mejor veces.

¿MapReduce ayuda a resolver este problema?

Aunque no creo que el uso o no de MapReduce sea información restringida dentro de Google, no estoy familiarizado con este punto. Sin embargo, la implementación de MapReduce de Google (que seguramente no es Hadoop) debe tener muchas optimizaciones, muchas de las cuales involucran los aspectos discutidos anteriormente. Entonces, la arquitectura de MapReduce probablemente ayuda a guiar cómo se distribuyen físicamente los cálculos, pero hay muchos otros puntos a considerar para justificar tal velocidad en el tiempo de consulta.

Bien, entiendo que las búsquedas populares pueden almacenarse en la memoria caché. ¿Pero qué pasa con las búsquedas impopulares?

El siguiente gráfico presenta una curva de cómo se producen los tipos de consultas. Puede ver que hay tres tipos principales de búsquedas, cada una de las cuales contiene aproximadamente 1/3 del volumen de consultas (área debajo de la curva). La trama muestra la ley de poder y refuerza el hecho de que las consultas más pequeñas son las más populares. El segundo tercio de las consultas aún es factible de procesar, ya que contienen pocas palabras. Pero el conjunto de las llamadas consultas oscuras , que generalmente consisten en consultas de usuarios no experimentados, no son una parte insignificante de las consultas.

Distribución de cola pesada

Y ahí yace espacio para soluciones novedosas. Dado que no son solo una o dos consultas (sino un tercio de ellas), deben tener resultados relevantes . Si escribe algo demasiado oscuro en una búsqueda en Google, no tardará más en devolver una lista de resultados, pero lo más probable es que le muestre algo que dedujo que le gustaría decir. O simplemente puede indicar que no había ningún documento con tales términos, o incluso reducir su búsqueda a 32 palabras (lo que me sucedió en una prueba aleatoria aquí).

Hay docenas de heurísticas aplicables, que pueden ser ignorar algunas palabras o tratar de dividir la consulta en otras más pequeñas y obtener los resultados más populares . ¿Y todas estas soluciones se pueden adaptar y ajustar para respetar los tiempos de espera factibles de, digamos, menos de un segundo? :RE

Rubens
fuente
Edité la pregunta para agregar otra consulta.
resgh
@namehere Traté de abordar su edición; Espero que ayude a responder la pregunta.
Rubens
10

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

La respuesta a la baja latencia generalmente es mantener índices precalculados en la memoria. Cualquier cosa que toque el disco es difícil de hacer rápido y escalar. Así es como los motores SQL de última generación basados ​​en Hadoop como Impala obtienen tanta velocidad en comparación con la infraestructura basada en MapReduce como Hive , por ejemplo.

La infraestructura de búsqueda 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 las principales consultas. Con un poco de almacenamiento en caché puede servir resultados para una minoría significativa de todas las consultas.

La búsqueda también se divide entre servidores. Por lo tanto, una máquina puede delegar a 100 para obtener una parte del resultado y luego combinarlas.

También puede salirse con la suya con cierto grado de aproximación. Google no forma literalmente mil páginas de resultados de búsqueda; solo tiene que obtener la primera página correcta.

Tenga en cuenta que Google tiene millones de computadoras en todo el mundo. Sus consultas van a un centro de datos geográficamente cerca de usted y eso solo sirve a su geografía. Esto elimina la mayor parte de la latencia, que es la red y no el tiempo de procesamiento en el centro de datos.

Sean Owen
fuente
Primero, edité la pregunta para agregar otra consulta. Además: me imagino que incluso con una minoría significativa precalculada, el resto de la consulta debería tardar mucho tiempo en completarse. Además, cuando el proceso se delega de una máquina a 100 máquinas, ¿no se incrementa realmente la latencia (latencia de red entre máquinas y la latencia total es la máxima de las latencias de todas las máquinas)?
resgh
Quiero decir que responder a la consulta "spaghetti diamond", que es una consulta rara y rara, podría acelerarse por los resultados calculados previamente para "spaghetti" y "diamond" individualmente. Las conexiones intra-DC son muy rápidas y de baja latencia. Un salto extra o dos adentro no es nada comparado con los ~ 20 saltos entre su computadora y el DC. El problema dominante en la distribución del trabajo es el problema rezagado; debe eliminar los resultados de algún subconjunto si no responden a tiempo. Estas son todas generalizaciones generales pero apuntan en la dirección correcta.
Sean Owen
4

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 parte de la web no cambia todo el tiempo, por lo que las arquitecturas más nuevas son incrementales en lugar de orientadas por lotes.

La búsqueda en Google funcionará en gran medida de la misma manera que funciona en Lucene y Elastic Search, excepto por una gran cantidad de ajustes y optimizaciones adicionales. Pero en el fondo, usarán alguna forma de índice invertido . En otras palabras, no buscan varios terabytes cuando ingresa una consulta de búsqueda (incluso cuando no está en caché). Es probable que no vean los documentos reales en absoluto. Pero usan una tabla de búsqueda que enumera qué documentos coinciden con el término de su consulta (con derivaciones, errores ortográficos, sinónimos, etc., todos preprocesados). Probablemente recuperen la lista de los 10000 documentos principales para cada palabra (10k enteros, ¡solo unos pocos kb!) Y calculan las mejores coincidencias a partir de eso. Solo si no hay buenas coincidencias en estas listas, se expanden a los siguientes bloques, etc.

Las consultas de palabras comunes se pueden almacenar en caché fácilmente; y a través del preprocesamiento puede crear una lista de los mejores resultados de 10k y luego volver a ajustarlos según el perfil del usuario. Tampoco se gana nada calculando una respuesta "exacta". Mirar los mejores resultados de 10k es bastante probable; no hay respuesta correcta; y si se pierde un mejor resultado en algún lugar de la posición 10001, nadie lo sabrá ni lo notará (ni le importará). Es probable que ya haya sido clasificado en el preprocesamiento y no habría llegado al top 10 que se presenta al usuario al final (o al top 3, el usuario realmente mira)

Los términos raros, por otro lado, tampoco son un gran desafío: una de las listas solo contiene algunos documentos coincidentes, y puede descartar inmediatamente todos los demás.

Recomiendo leer este artículo:

La anatomía de un motor de búsqueda web hipertextual a gran escala
Sergey Brin y Lawrence Page
Departamento de informática de la Universidad de Stanford, Stanford, CA 94305
http://infolab.stanford.edu/~backrub/google.html

Y sí, esos son los fundadores de Google que escribieron esto. No es el último estado, pero ya funcionará a una escala bastante grande.

HA SALIDO - Anony-Mousse
fuente