Como você implementaria a Pesquisa do Google? [fechadas]

35

Supostamente você foi perguntado em uma entrevista "Como você implementaria a Pesquisa do Google?" Como você responderia a essa pergunta? Pode haver recursos por aí que expliquem como algumas peças no Google são implementadas (BigTable, MapReduce, PageRank, ...), mas isso não se encaixa exatamente em uma entrevista.

Qual arquitetura geral você usaria e como você explicaria isso em um intervalo de tempo de 15 a 30 minutos?

Gostaria de começar explicando como criar um mecanismo de pesquisa que lide com ~ 100k documentos e, em seguida, expanda isso por meio de sharding para cerca de 50 milhões de documentos, então talvez outro salto arquitetônico / técnico.

Esta é a vista de 20.000 pés. O que eu gostaria é dos detalhes - como você realmente responderia em uma entrevista. Quais estruturas de dados você usaria? Quais serviços / máquinas sua arquitetura é composta? O que seria uma latência de consulta típica? E quanto a problemas de failover / split brain? Etc ...

    
por ripper234 19.01.2011 / 17:31
fonte

2 respostas

18
por 03.02.2011 / 07:16
fonte
40

Considere o meta-ponto: o que o entrevistador está procurando?

Uma pergunta gigantesca como essa não está procurando por você para desperdiçar seu tempo na questão da implementação de um algoritmo do tipo PageRank ou como fazer uma indexação distribuída. Em vez disso, concentre-se na imagem completa do que seria necessário. Parece que você já conhece todas as grandes peças (BigTable, PageRank, Map / Reduce). Então, a questão é, então, como você realmente os conecta?

Aqui está minha facada.

Fase 1: Infra-estrutura de indexação (gaste 5 minutos explicando)

A primeira fase de implementação do Google (ou qualquer mecanismo de busca) é construir um indexador. Essa é a parte do software que rastreia o corpus de dados e produz os resultados em uma estrutura de dados mais eficiente para fazer leituras.

Para implementar isso, considere duas partes: um rastreador e um indexador.

O trabalho do rastreador da Web é vincular links de páginas da Web e despejá-los em um conjunto. O passo mais importante aqui é evitar ser pego em loop infinito ou em conteúdo gerado infinitamente. Coloque cada um desses links em um arquivo de texto massivo (por enquanto).

Segundo, o indexador será executado como parte de um trabalho Mapear / Reduzir. (Mapeie uma função para cada item na entrada e, em seguida, reduza os resultados em uma única 'coisa'.) O indexador terá um único link da Web, recuperará o site e o converterá em um arquivo de índice. (Discutido a seguir.) A etapa de redução será simplesmente agregar todos esses arquivos de índice em uma única unidade. (Em vez de milhões de arquivos soltos.) Como as etapas de indexação podem ser feitas em paralelo, você pode fazer o farm dessa tarefa Mapear / Reduzir em um datacenter arbitrariamente grande.

Fase 2: Especificidades dos Algoritmos de Indexação (gaste 10 minutos explicando)

Depois de ter informado como você processará as páginas da Web, a próxima parte está explicando como você pode calcular resultados significativos. A resposta curta aqui é "muito mais Mapear / Reduzir", mas considere o tipo de coisas que você pode fazer:

  • Para cada site, conte o número de links recebidos. (Páginas mais ligadas devem ser "melhores").
  • Para cada site, veja como o link foi apresentado. (Links em um < h1 > ou < b > devem ser mais importantes do que aqueles enterrados em um < h3 >.)
  • Para cada site, observe o número de links externos. (Ninguém gosta de spammers.)
  • Para cada site, veja os tipos de palavras usadas. Por exemplo, 'hash' e 'table' provavelmente significa que o site está relacionado à Ciência da Computação. 'hash' e 'brownies', por outro lado, implicariam que o site era sobre algo muito diferente.

Infelizmente, não sei o suficiente sobre os tipos de maneiras de analisar e processar os dados para serem super úteis. Mas a ideia geral é formas escalonáveis de analisar seus dados .

Fase 3: Servindo Resultados (gaste 10 minutos explicando)

A fase final está realmente servindo os resultados. Espero que você tenha compartilhado alguns insights interessantes sobre como analisar dados de páginas da Web, mas a questão é como você realmente consulta isso? Curiosamente, 10% das consultas de pesquisa do Google por dia nunca foram vistas antes. Isso significa que você não pode armazenar em cache resultados anteriores.

Você não pode ter uma única "pesquisa" a partir dos seus índices da Web. Então, qual você tentaria? Como você olharia para diferentes índices? (Talvez combinar resultados - talvez a palavra-chave "stackoverflow" tenha surgido em vários índices.)

Além disso, como você procuraria de qualquer maneira? Que tipos de abordagens você pode usar para ler dados de quantidades de informações enormes rapidamente? (Sinta-se à vontade para nomear seu banco de dados NoSQL favorito aqui e / ou ver o que é o BigTable do Google.) Mesmo que você tenha um índice impressionante que seja altamente preciso, você precisa encontrar uma maneira de encontrar dados rapidamente. (Por exemplo, localize o número de classificação para "stackoverflow.com" dentro de um arquivo de 200 GB.)

Edições aleatórias (tempo restante)

Depois de ter coberto os "ossos" do seu mecanismo de pesquisa, sinta-se à vontade para abordar qualquer tópico individual sobre o qual você tenha conhecimento especial.

  • Desempenho do frontend do site
  • Gerenciando o data center para o seu mapa / reduzir empregos
  • Melhorias nos mecanismos de pesquisa de teste A / B
  • Integração do volume de pesquisas / tendências anteriores à indexação. (Por exemplo, esperar que as cargas do servidor do frontend aumentem 9-5 e desapareçam no início da manhã).

Há obviamente mais de 15 minutos de material para discutir aqui, mas esperamos que seja o suficiente para você começar.

    
por 20.01.2011 / 06:33
fonte