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:
- 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);
- 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;
- 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.
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
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.
fuente
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:
Y sí, esos son los fundadores de Google que escribieron esto. No es el último estado, pero ya funcionará a una escala bastante grande.
fuente