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

¿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 muestran 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 margen: es abrumador pensar que incluso si tuviera que poner una aplicación de escritorio y usarla en mi máquina, probablemente no sería ni la mitad de rápido que Google. Sigue aprendiendo, digo.

Estas son algunas de las excelentes respuestas y sugerencias proporcionadas:

• Plataforma de Google
• Mapa reducido
• Algoritmos cuidadosamente elaborados
• Hardware: granjas de clústeres y una gran cantidad de computadoras baratas
• Almacenamiento en caché y equilibrio de carga
• Sistema de archivos de Google

Los accesos al disco eliminan la latencia. 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 de los cuales replica uno de los muchos fragmentos. Por lo tanto, es poco probable que la ruta crítica para la búsqueda llegue a cualquiera de sus tecnologías de sistemas distribuidos emblemáticos GFS, MapReduce o BigTable. Estos se utilizarán para procesar los resultados del rastreador, de forma burda.

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

Entonces, una posible arquitectura es bastante simple: los servidores frontales procesan la consulta, normalizándola (posiblemente eliminando las palabras vacías, 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). Probablemente se consultan muchas, muchas réplicas, y las respuestas más rápidas ganan. Cada réplica tiene consultas de mapeo de índices (o términos de consulta individuales) a documentos que pueden usar para buscar resultados en la memoria muy rápidamente. Si se obtienen diferentes resultados 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 realmente hace Google: 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 de equilibrio de carga funky entre otras posibles diferencias .

Es demasiado para ponerlo en una sola respuesta. http://en.wikipedia.org/wiki/Google_platform

Un hecho que siempre me ha parecido gracioso es que Google está dirigido por la bioinformática (bueno, eso me parece gracioso porque soy una bioinf ... cosita). Dejame explicar.

La bioinformática tuvo desde el principio el desafío de buscar textos pequeños en cadenas gigantes muy rápido. Para nosotros, la "cadena 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 pequeños textos son proteínas o su contraparte genética, un gen. La mayor parte del primer trabajo de los biólogos computacionales se limitó a encontrar homologías entre genes. Esto se hace para establecer la función de genes recién descubiertos al observar similitudes con genes que ya se conocen.

Ahora, estas cadenas de ADN se vuelven realmente muy grandes y (¡con pérdidas!) La búsqueda debe realizarse 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, la búsqueda de texto convencional se agotó. 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 procesando previamente 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 una 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 se debe tener en cuenta el equilibrio de carga entre los servidores, el preprocesamiento y algunas otras cosas sofisticadas.

Pero, en esencia, el llamado índice 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 combinación posible 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 que se indexó (o en el caso de Google, para cada sitio web).

Para mitigar el gran tamaño, Google probablemente utilizará múltiples índices (de hecho, lo hacen , para ofrecer servicios como corrección ortográfica). Los más altos no funcionarán a nivel de personaje sino a nivel de palabra. Esto reduce q pero hace que S sea infinitamente más grande, por lo que tendrán que usar tablas hash y de colisión para hacer frente al número infinito de palabras diferentes.

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

En pocas palabras, estas estructuras de datos de índice de q -gram son posiblemente la parte más central del algoritmo de búsqueda de Google. Desafortunadamente, no hay buenos artículos no técnicos que expliquen cómo funcionan los índices q -gram. La única publicación que conozco que contiene una descripción de cómo funciona tal índice es ... ay, mi tesis de licenciatura .

Estas son algunas de las excelentes respuestas y sugerencias proporcionadas:

• Plataforma de Google
• Mapa reducido
• Algoritmos cuidadosamente elaborados
• Hardware: granjas de clústeres y una gran cantidad de computadoras baratas
• Almacenamiento en caché y equilibrio de carga
• Sistema de archivos de Google

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

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

Todos saben que es porque usan palomas , ¡claro!

Oh, sí, eso y Mapreduce.

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

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 invertir en hardware e ingenieros.

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

Tienen granjas de servidores ubicadas geográficamente.

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

1. Parellelize solicitudes (p. Ej., Dividir una sola solicitud en conjuntos más pequeños)
2. Asincrónico (haga lo más asincrónico posible, por ejemplo, no bloqueará la solicitud del usuario)
3. Memoria / caché (la E / S del disco es lenta, mantenga la mayor cantidad posible en la memoria)
4. Cálculo previo (haga todo el trabajo posible de antemano, no espere a que un usuario solicite datos / procesamiento)
5. Preocúpese por su HTML de front-end (consulte Yslow y sus amigos)

Puede encontrar en la página de inicio de investigación de Google algunos consejos sobre los artículos de investigación escritos por algunos de los chicos de Google. Debe comenzar con la explicación del sistema de archivos de Google y el algoritmo map / reduce para intentar comprender qué sucede detrás de las páginas de Google.

Este enlace también es muy informativo Detrás de las escenas de una consulta de Google

Hardware.

Mucho, mucho hardware. Usan grupos masivos de PC básicos como su granja de servidores.

TraumaPony tiene razón. Toneladas de servidores y arquitectura inteligente para equilibrio de carga / almacenamiento en caché y listo, puede ejecutar consultas en menos de 1 segundo. Había muchos artículos en la red que describían la arquitectura de los servicios de Google. Estoy seguro de que puedes encontrarlos a través de Google :)

HenryR probablemente tenga razón.

Map Reduce no juega un papel en la búsqueda en sí, sino que solo se usa para indexar. Vea esta entrevista en video con los inventores de Map Reduce .

Una razón adicional parece ser que hacen trampa en el algoritmo de inicio lento de TCP.

http://blog.benstrong.com/2010/11/google-and-microsoft-cheat-on-slow.html

Y algoritmos que pueden aprovechar esa potencia del hardware. Como mapreduce, por ejemplo.

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 de Google.

1. Almacenamiento, procesamiento y recuperación de datos en múltiples etapas

2. Distribución EFICIENTE (cientos de miles 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