¿Cómo implementaría la Búsqueda de Google? [cerrado]

44

Supongamos que se le preguntó en una entrevista "¿Cómo implementaría la Búsqueda de Google?" ¿Cómo responderías a esa pregunta? Puede haber recursos que expliquen cómo se implementan algunas piezas en Google (BigTable, MapReduce, PageRank, ...), pero eso no encaja exactamente en una entrevista.

¿Qué arquitectura general usarías y cómo explicarías esto en un lapso de tiempo de 15-30 minutos?

Comenzaría explicando cómo construir un motor de búsqueda que maneje ~ 100k documentos, luego expandir esto mediante fragmentación a alrededor de 50 millones de documentos, luego quizás otro salto arquitectónico / técnico.

Esta es la vista de 20,000 pies. Lo que me gustaría son los detalles: cómo respondería eso en una entrevista. ¿Qué estructuras de datos usarías? De qué servicios / máquinas está compuesta su arquitectura. ¿Cuál sería una latencia de consulta típica? ¿Qué pasa con los problemas cerebrales de failover / split? Etc ...

ripper234
fuente
1
Esa es una pregunta de entrevista. ¿Cuántos detalles estaban buscando?
Paddy
1
En realidad, esa es una pregunta que utilicé cuando hice algunas entrevistas hace un tiempo. Lo bueno es que la cantidad de detalles que das depende realmente de ti, y el tiempo que tu entrevistador quiere pasar en esto.
ripper234
2
"¡Mapa reducido! Siguiente pregunta por favor". "Te llamaremos."
2
buena pregunta pero del tipo que podrías pasar horas respondiendo. Tal vez entraría en google con una unidad flash
Creo que esta es una buena pregunta, aunque me resultaría abrumadora. Recientemente he estado pensando en cómo construir un algoritmo para "ponderar" artículos en un sitio de noticias (solo en teoría, algo para mantenerme ocupado en la ducha :) y admito que incluso esta idea es bastante difícil /complejo.

Respuestas:

45

Considere el metapunto: ¿qué está buscando el entrevistador?

Una pregunta gigantesca como esa no busca que pierdas tu tiempo en el meollo de la implementación de un algoritmo de tipo PageRank o cómo hacer una indexación distribuida. En cambio, concéntrese en la imagen completa de lo que se necesitaría. Parece que ya conoces todas las piezas grandes (BigTable, PageRank, Map / Reduce). Entonces, la pregunta es, ¿cómo los conecta realmente?

Aquí está mi puñalada.

Fase 1: Infraestructura de indexación (dedica 5 minutos a explicar)

La primera fase de implementación de Google (o cualquier motor de búsqueda) es construir un indexador. Esta es la pieza de software que rastrea el corpus de datos y produce los resultados en una estructura de datos que es más eficiente para hacer lecturas.

Para implementar esto, considere dos partes: un rastreador e indexador.

El trabajo del rastreador web es arañar enlaces de páginas web y volcarlos en un conjunto. El paso más importante aquí es evitar quedar atrapado en un bucle infinito o en contenido generado infinitamente. Coloque cada uno de estos enlaces en un archivo de texto masivo (por ahora).

En segundo lugar, el indexador se ejecutará como parte de un trabajo de Mapa / Reducir. (Asigne una función a cada elemento en la entrada y luego reduzca los resultados en una sola 'cosa'). El indexador tomará un solo enlace web, recuperará el sitio web y lo convertirá en un archivo de índice. (Discutido a continuación.) El paso de reducción simplemente agregará todos estos archivos de índice en una sola unidad. (En lugar de millones de archivos sueltos). Dado que los pasos de indexación se pueden realizar en paralelo, puede agrupar este trabajo de Mapa / Reducir en un centro de datos arbitrariamente grande.

Fase 2: detalles de los algoritmos de indexación (dedica 10 minutos a explicar)

Una vez que haya indicado cómo procesará las páginas web, la siguiente parte explica cómo puede calcular resultados significativos. La respuesta corta aquí es 'mucho más Mapa / Reducciones', pero considere el tipo de cosas que puede hacer:

  • Para cada sitio web, cuente la cantidad de enlaces entrantes. (Las páginas más vinculadas deberían ser 'mejores').
  • Para cada sitio web, mire cómo se presentó el enlace. (Los enlaces en un <h1> o <b> deberían ser más importantes que los enterrados en un <h3>).
  • Para cada sitio web, observe la cantidad de enlaces salientes. (A nadie le gustan los spammers).
  • Para cada sitio web, observe los tipos de palabras utilizadas. Por ejemplo, 'hash' y 'table' probablemente significan que el sitio web está relacionado con la informática. 'hash' y 'brownies' por otro lado implicarían que el sitio se trata de algo muy diferente.

Desafortunadamente, no sé lo suficiente sobre el tipo de formas de analizar y procesar los datos para ser súper útil. Pero la idea general es formas escalables de analizar sus datos .

Fase 3: Resultados de la publicación (dedica 10 minutos a explicar)

La fase final en realidad está sirviendo los resultados. Espero que haya compartido algunas ideas interesantes sobre cómo analizar los datos de la página web, pero la pregunta es ¿cómo lo consulta realmente? Anecdóticamente, el 10% de las consultas de búsqueda de Google cada día nunca antes se habían visto. Esto significa que no puede almacenar en caché los resultados anteriores.

No puede tener una sola 'búsqueda' de sus índices web, entonces, ¿cuál probaría? ¿Cómo mirarías a través de diferentes índices? (Tal vez combinando resultados, tal vez la palabra clave 'stackoverflow' surgió altamente en múltiples índices).

Además, ¿cómo lo buscarías de todos modos? ¿Qué tipo de enfoques puede usar para leer datos de grandes cantidades de información rápidamente? (Siéntase libre de nombrar su base de datos NoSQL favorita aquí y / o ver de qué se trata BigTable de Google). Incluso si tiene un índice increíble que sea muy preciso, necesita una forma de encontrar datos rápidamente. (Por ejemplo, encuentre el número de rango para 'stackoverflow.com' dentro de un archivo de 200GB).

Problemas aleatorios (tiempo restante)

Una vez que haya cubierto los 'huesos' de su motor de búsqueda, siéntase libre de criticar cualquier tema individual sobre el que esté especialmente informado.

  • Rendimiento de la interfaz del sitio web
  • Administrar el centro de datos para sus trabajos de Mapa / Reducir
  • Mejoras en el motor de búsqueda de pruebas A / B
  • Integrando el volumen / tendencias de búsqueda anteriores en la indexación. (Por ejemplo, esperar que las cargas del servidor frontend aumenten de 9 a 5 y desaparezcan a principios de la mañana).

Obviamente hay más de 15 minutos de material para discutir aquí, pero espero que sea suficiente para comenzar.

Chris Smith
fuente
1
Esta es una gran respuesta, pero creo que no comienza a abordar los problemas de escala con la creación de Google. Creo que la parte más desafiante está en Servir resultados, parte de su respuesta, y en dónde reside gran parte de la magia de Google. Tengo alguna idea sobre cómo diseñar algo así, pero me interesa escuchar a otros.
ripper234
Le pregunté esto a Quora, creo que puede tener la audiencia para responder esta pregunta. quora.com/…
ripper234
Mira mi respuesta.
ripper234