Como o Google pode ser tão rápido?

Quais são as tecnologias e decisões de programação que tornam o Google capaz de atender a uma consulta com tanta rapidez?

Cada vez que eu procuro algo (uma das várias vezes por dia), sempre me surpreendo como eles veiculam os resultados em quase ou menos de 1 segundo. Que tipo de configuração e algoritmos eles poderiam ter para fazer isso?

Nota lateral: É meio opressor pensar que mesmo se eu colocasse um aplicativo de desktop e usasse em minha máquina, provavelmente não seria nem metade da velocidade do Google. Continue aprendendo, eu digo.

Aqui estão algumas das ótimas respostas e dicas fornecidas:

• Plataforma Google
• Reduzir mapa
• Algoritmos cuidadosamente elaborados
• Hardware - fazendas de cluster e grande número de computadores baratos
• Cache e balanceamento de carga
• Sistema de arquivos do Google

A latência é eliminada por acessos ao disco. Portanto, é razoável acreditar que todos os dados usados ​​para responder às consultas são mantidos na memória. Isso implica milhares de servidores, cada um replicando um dos muitos shards. Portanto, é improvável que o caminho crítico para a pesquisa atinja qualquer uma de suas tecnologias de sistemas distribuídos, GFS, MapReduce ou BigTable. Eles serão usados ​​para processar os resultados do rastreador, de maneira grosseira.

O útil sobre a pesquisa é que não há necessidade de resultados fortemente consistentes ou dados completamente atualizados, portanto, o Google não é impedido de responder a uma consulta porque um resultado de pesquisa mais atualizado tornou-se disponível.

Portanto, uma possível arquitetura é bastante simples: os servidores front-end processam a consulta, normalizando-a (possivelmente removendo palavras de interrupção, etc.) e depois distribuindo para qualquer subconjunto de réplicas que possui essa parte do espaço de consulta (uma arquitetura alternativa é dividir o dados por páginas da web, de modo que um de cada conjunto de réplicas precisa ser contatado para cada consulta). Muitas, muitas réplicas são provavelmente consultadas e as respostas mais rápidas ganham. Cada réplica possui consultas de mapeamento de índice (ou termos de consulta individuais) para documentos que podem ser usados ​​para pesquisar resultados na memória muito rapidamente. Se resultados diferentes vierem de fontes diferentes, o servidor front-end pode classificá-los à medida que cospe o html.

Observe que este é provavelmente um longo caminho diferente do que o Google realmente faz - eles terão projetado a vida deste sistema, então pode haver mais caches em áreas estranhas, índices estranhos e algum tipo de esquema de balanceamento de carga esquisito entre outras possíveis diferenças .

É um pouco demais colocar em uma única resposta. http://en.wikipedia.org/wiki/Google_platform

Um fato que sempre achei engraçado é que o Google é, na verdade, administrado por bioinformática ('ok, acho isso engraçado porque sou um bioinfo ... coisinha). Deixe-me explicar.

A bioinformática teve desde o início o desafio de pesquisar pequenos textos em cadeias gigantescas com muita rapidez. Para nós, a “corda gigante” é, obviamente, DNA. Freqüentemente, não um único DNA, mas um banco de dados de vários DNAs de diferentes espécies / indivíduos. Os pequenos textos são proteínas ou sua contraparte genética, um gene. A maior parte do primeiro trabalho de biólogos computacionais se restringiu a encontrar homologias entre genes. Isso é feito para estabelecer a função de genes recém-descobertos, observando semelhanças com genes que já são conhecidos.

Agora, essas sequências de DNA ficam realmente muito grandes e a pesquisa (com perdas!) Deve ser feita de forma extremamente eficiente. A maior parte da teoria moderna de pesquisa de cordas foi desenvolvida no contexto da biologia computacional.

No entanto, há muito tempo, a busca convencional de texto estava esgotada. Era necessária uma nova abordagem que permitisse pesquisar grandes strings no tempo sublinear, ou seja, sem olhar para cada caractere único. Foi descoberto que isso pode ser resolvido com o pré-processamento da string grande e a construção de uma estrutura de dados de índice especial sobre ela. Muitas dessas estruturas de dados diferentes foram propostas. Cada um tem seus pontos fortes e fracos, mas há um que é especialmente notável porque permite uma pesquisa em tempo constante. Agora, nas ordens de magnitude em que o Google opera, isso não é estritamente verdadeiro porque o balanceamento de carga entre os servidores, o pré-processamento e algumas outras coisas sofisticadas devem ser levadas em consideração.

Mas, em essência, o chamado índice q-gram permite uma pesquisa em tempo constante. A única desvantagem: a estrutura de dados fica ridiculamente grande. Essencialmente, para permitir uma pesquisa de strings com até q caracteres (daí o nome), é necessária uma tabela que tenha um campo para cada combinação possível de q letras (ou seja, q ^S , onde S é o tamanho do alfabeto , digamos 36 (= 26 + 10)). Além disso, deve haver um campo para cada posição da letra na string que foi indexada (ou no caso do google, para cada site).

Para mitigar o tamanho, o Google provavelmente irá usar vários índices (na verdade, eles fazem , para oferecer serviços como correção ortográfica). Os primeiros não funcionam no nível do personagem, mas sim no nível da palavra. Isso reduz q, mas torna S infinitamente maior, de modo que eles terão que usar tabelas de hash e de colisão para lidar com o número infinito de palavras diferentes.

No próximo nível, essas palavras hash apontarão para outras estruturas de dados de índice que, por sua vez, farão hash caracteres apontando para sites.

Para encurtar a história, essas estruturas de dados de índice q -gram são indiscutivelmente a parte mais central do algoritmo de pesquisa do Google. Infelizmente, não existem bons artigos não técnicos explicando como funcionam os índices q -gram. A única publicação que conheço que contém uma descrição de como esse índice funciona é ... infelizmente, minha tese de bacharelado .

Aqui estão algumas das ótimas respostas e dicas fornecidas:

• Plataforma Google
• Reduzir mapa
• Algoritmos cuidadosamente elaborados
• Hardware - fazendas de cluster e grande número de computadores baratos
• Cache e balanceamento de carga
• Sistema de arquivos do Google

Eles implementaram algoritmos bons e distribuídos em uma grande quantidade de hardware.

Um dos atrasos mais importantes é que os servidores web estão obtendo sua consulta ao servidor web e a resposta de volta. Essa latência é limitada pela velocidade da luz, que até mesmo o Google tem que obedecer. No entanto, eles possuem datacenters em todo o mundo. Como resultado, a distância média para qualquer um deles é menor. Isso mantém a latência baixa. Claro, a diferença é medida em milissegundos, mas é importante se a resposta deve chegar em 1000 milissegundos.

Todo mundo sabe que é porque eles usam pombos , é claro!

Oh sim, isso e Mapreduce.

Eles praticamente possuem uma cópia local da Internet em cache em milhares de PCs em sistemas de arquivos personalizados.

O Google contrata o melhor dos melhores. Algumas das pessoas mais inteligentes em TI trabalham no google. Eles têm dinheiro virtualmente infinito para investir em hardware e engenheiros.

Eles usam mecanismos de armazenamento altamente otimizados para as tarefas que estão executando.

Eles têm farms de servidores localizados geograficamente.

Uma tentativa de lista generalizada (que não depende de você ter acesso às ferramentas internas do Google):

1. Parelele solicitações (por exemplo, divida uma única solicitação em conjuntos menores)
2. Assíncrono (torna o mais assíncrono possível, por exemplo, não bloqueia a solicitação do usuário)
3. Memória / cache de disco (I / O é lento, manter, tanto quanto possível na memória)
4. Pré-cálculo (faça o máximo de trabalho possível com antecedência, não espere que um usuário peça dados / processamento)
5. Preocupe-se com seu HTML de front-end (consulte Yslow e amigos)

Você pode encontrar na página inicial de pesquisa do Google algumas dicas sobre os trabalhos de pesquisa escritos por alguns dos caras do Google. Você deve começar com a explicação do sistema de arquivos do Google e do algoritmo map / Reduzir para tentar entender o que está acontecendo por trás das páginas do Google.

Este link também é muito informativo, nos bastidores de uma consulta do Google

Hardware.

Muito e muito hardware. Eles usam clusters enormes de PCs básicos como seu farm de servidores.

TraumaPony está certo. Toneladas de servidores e arquitetura inteligente para balanceamento de carga / cache e voila, você pode executar consultas em menos de 1 segundo. Havia muitos artigos na rede descrevendo a arquitetura de serviços do Google. Tenho certeza que você pode encontrá-los através do Google :)

HenryR provavelmente está correto.

O Map Reduce não desempenha um papel para a pesquisa em si, mas é usado apenas para indexação. Confira esta entrevista em vídeo com os inventores do Map Reduce .

Uma razão adicional parece ser que eles trapaceiam no algoritmo de início lento do TCP.

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

E algoritmos que podem aproveitar essa potência do hardware. Como mapreduce, por exemplo.

Se você estiver interessado em mais detalhes sobre como o cluster do google funciona, vou sugerir esta implementação de código aberto de seu HDFS .

É baseado no Mapreduce do google.

1. Armazenamento, processamento e recuperação de dados em vários estágios

2. Distribuição EFICIENTE (centenas de milhares de máquinas) das tarefas acima

3. Boa estrutura para armazenar os dados brutos e os resultados processados

4. Boa estrutura para recuperar os resultados

Como exatamente tudo isso é feito é resumido por todos os links que você tem no resumo da pergunta