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 ...
fuente
Respuestas:
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:
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.
Obviamente hay más de 15 minutos de material para discutir aquí, pero espero que sea suficiente para comenzar.
fuente
La publicación sobre Quora arrojó el artículo original publicado por Sergey Brin y Larry Page. Parece ser una excelente referencia para este tipo de preguntas.
fuente