examples complexity big performance algorithm

performance - complexity - ¿Cómo puede Google ser tan rápido?



o 1 (19)

  1. Almacenamiento, procesamiento y recuperación de datos en varias etapas

  2. Distribución EFICIENTE (100 de 1000 de máquinas) de las tareas anteriores

  3. Buen marco para almacenar los datos sin procesar y los resultados procesados

  4. Buen marco para recuperar los resultados

Cómo se hacen exactamente todos estos se resume en todos los enlaces que tiene en el resumen de la pregunta

¿Cuáles son las tecnologías y las decisiones de programación que hacen que Google pueda atender una consulta tan rápido?

Cada vez que busco algo (una de las varias veces al día) siempre me sorprende cómo sirven los resultados en cerca o menos de 1 segundo. ¿Qué tipo de configuración y algoritmos podrían tener implementados para lograr esto?

Nota al pie: Es un poco abrumador pensar que incluso si tuviera que poner una aplicación de escritorio y usarla en mi máquina, probablemente no sería la mitad de rápido que Google. Sigue aprendiendo lo que digo.

Estas son algunas de las excelentes respuestas y consejos proporcionados:

¡Todos saben que es porque usan palomas , por supuesto!

Oh sí, eso y Mapreduce.

Google contrata lo mejor de lo mejor. Algunas de las personas más inteligentes en TI trabajan en google. Tienen dinero prácticamente infinito para tirar en hardware e ingenieros.

Usan mecanismos de almacenamiento altamente optimizados para las tareas que están realizando.

Tienen granjas de servidores ubicadas geográficamente.

Han implementado algoritmos buenos y distribuidos que se ejecutan en una gran cantidad de hardware.

Hardware.

Montones y montones de hardware. Usan clústeres masivos de PC básicas como su granja de servidores.

Latencia es aniquilada por los accesos al disco. Por lo tanto, es razonable creer que todos los datos utilizados para responder consultas se mantienen en la memoria. Esto implica miles de servidores, cada uno replicando uno de muchos fragmentos. Por lo tanto, es poco probable que la ruta crítica para la búsqueda llegue a cualquiera de sus tecnologías emblemáticas de sistemas distribuidos GFS, MapReduce o BigTable. Estos se usarán para procesar los resultados del rastreador, crudamente.

Lo útil de la búsqueda es que no es necesario tener resultados muy consistentes ni datos completamente actualizados, por lo que no se impide que Google responda a una consulta porque está disponible un resultado de búsqueda más actualizado.

Entonces, una arquitectura posible es bastante simple: los servidores frontales procesan la consulta, normalizándola (posiblemente eliminando palabras de parada, etc.) y luego distribuyéndola a cualquier subconjunto de réplicas que posea esa parte del espacio de consulta (una arquitectura alternativa es dividir el datos por páginas web, de modo que uno de cada conjunto de réplicas debe ser contactado para cada consulta). Muchas, muchas réplicas son probablemente consultadas, y las respuestas más rápidas ganan. Cada réplica tiene consultas de mapeo de índice (o términos de consulta individuales) para documentos que pueden usar para buscar resultados en la memoria muy rápidamente. Si los resultados diferentes provienen de diferentes fuentes, el servidor de aplicaciones para el usuario puede clasificarlos a medida que escupe el html.

Tenga en cuenta que esto probablemente sea muy diferente de lo que Google realmente hace; habrán diseñado la vida útil de este sistema para que haya más cachés en áreas extrañas, índices extraños y algún tipo de esquema funky de equilibrio de carga, entre otras posibles diferencias .

Prácticamente tienen una copia local de Internet almacenada en caché en miles de PC en sistemas de archivos personalizados.

Si está interesado en obtener más detalles sobre cómo funciona el clúster de Google, sugeriré esta implementación de código abierto de su HDFS .

Está basado en Mapreduce por google.

TraumaPony tiene razón. Gran cantidad de servidores y arquitectura inteligente para equilibrar la carga / almacenamiento en caché y listo para ejecutar consultas en menos de 1 segundo. Hubo muchos artículos en la red que describen la arquitectura de servicios de google. Estoy seguro de que puedes encontrarlos a través de Google :)

Un hecho que siempre he encontrado gracioso es que Google está dirigido por bioinformática (''kay, me parece gracioso porque soy un bioinf ... cosa cursi). Dejame explicar.

La bioinformática desde el principio tuvo el desafío de buscar textos pequeños en cadenas gigantescas muy rápido. Para nosotros, la "cuerda gigantesca" es, por supuesto, ADN. A menudo no es un solo ADN sino una base de datos de varios ADN de diferentes especies / individuos. Los textos pequeños son proteínas o su contraparte genética, un gen. La mayor parte del primer trabajo de biólogos computacionales se restringió para encontrar homologías entre los genes. Esto se hace para establecer la función de genes recién encontrados al observar similitudes con genes que ya se conocen.

Ahora, estas cadenas de ADN se hacen muy grandes y (¡con pérdidas!) La búsqueda tiene que hacerse de manera extremadamente eficiente. La mayor parte de la teoría moderna de la búsqueda de cadenas se desarrolló así en el contexto de la biología computacional.

Sin embargo, hace bastante tiempo, se agotó la búsqueda de texto convencional. Se necesitaba un nuevo enfoque que permitiera buscar cadenas grandes en tiempo sublineal, es decir, sin mirar cada carácter individual. Se descubrió que esto se puede resolver preprocesando la cadena grande y construyendo una estructura de datos de índice especial sobre ella. Se han propuesto muchas estructuras de datos diferentes. Cada uno tiene sus fortalezas y debilidades, pero hay uno que es especialmente notable porque permite una búsqueda en tiempo constante. Ahora, en los órdenes de magnitud en los que opera Google, esto ya no es estrictamente cierto porque debe tenerse en cuenta el equilibrio de carga en los servidores, el preprocesamiento y algunas otras cosas sofisticadas.

Pero en esencia, el llamado índice de q-gram permite una búsqueda en tiempo constante. La única desventaja: la estructura de datos se vuelve ridículamente grande. Esencialmente, para permitir una búsqueda de cadenas con hasta q caracteres (de ahí el nombre), se requiere una tabla que tenga un campo para cada posible combinación de q letras (es decir, q S , donde S es el tamaño del alfabeto , digamos 36 (= 26 + 10)). Además, debe haber un campo para cada posición de letra en la cadena indexada (o en el caso de google, para cada sitio web).

Para mitigar el tamaño, Google probablemente usará varios índices (de hecho, lo hacen , para ofrecer servicios como la corrección ortográfica). Los más altos no funcionarán en el nivel de personaje sino en el nivel de palabra. Esto reduce q pero hace que S sea ​​infinitamente más grande, por lo que tendrán que usar hashing y tablas de colisión para lidiar con el infinito número de palabras diferentes.

En el siguiente nivel, estas palabras hash señalarán otras estructuras de datos de índice que, a su vez, arrojarán caracteres que apuntan a sitios web.

Para abreviar, estas estructuras de datos de índice q -gram son posiblemente la parte más central del algoritmo de búsqueda de Google. Desafortunadamente, no hay buenos documentos no técnicos que expliquen cómo funcionan los índices de q -gramos. La única publicación que sé que contiene una descripción de cómo funciona dicho índice es ... por desgracia, mi tesis de licenciatura .

Un intento de una lista generalizada (que no depende de que tenga acceso a las herramientas internas de Google):

  1. Solicitudes de Parellelize (por ejemplo, dividir una sola solicitud en conjuntos más pequeños)
  2. Async (hacer la mayor cantidad de asincronía posible, por ejemplo, no bloqueará la solicitud del usuario)
  3. Memoria / caché (la E / S de disco es lenta, mantenga tanto como sea posible en la memoria)
  4. Precálculo (haga todo el trabajo posible antes de la mano, no espere a que un usuario solicite datos / procesamiento)
  5. Tenga cuidado con su HTML de front-end (vea Yslow y sus amigos)

Uno de los retrasos más importantes es que los servidores web reciban su consulta al servidor web y la respuesta vuelva. Esta latencia está limitada por la velocidad de la luz, que incluso Google debe obedecer. Sin embargo, tienen centros de datos en todo el mundo. Como resultado, la distancia promedio a cualquiera de ellos es menor. Esto mantiene la latencia baja. Claro, la diferencia se mide en milisegundos, pero importa si la respuesta debe llegar dentro de 1000 milisegundos.