Você é bom de algoritmo?

No dia 27 de julho, cientistas da computação da Universidade da Califórnia em San Diego quebraram um novo recorde mundial da informática, ordenando um terabytes (1TB) de dados em apenas 60 segundos. O feito foi realizado na copa mundial de ordenação de dados, a Sort Benchmark Competition.  Um outro recorde também foi quebrado pelo mesmo time: a ordenação de um trilhão de registros em 172 minutos. Tarefa realizada usando apenas 25% de recursos computacionais do último detentor da marca. Um feito e tanto.

Um detalhe muito importante desse projeto é que ele foi realizado com uma quantidade de dados bem maior que a memória dos computadores atuais consegue armazenar. Já existem discos de 2TB, mas não essa quantidade de memória instalada em computadores comuns. Isso exigiu não somente um bom programa de ordenação, mas uma engenharia de como distribuir o processamento e os dados em um conjunto de computadores. A estrutura computacional usada está descrita abaixo:

  • 52 computadores com duas CPU quad core;
  • Cada computador com 24gb de RAM;
  • 16 discos de 500GB em cada computador;
  • Um switch Cisco Nexus 5020

ONDE A ORDENAÇÃO É APLICADA

Ordenar grandes massas de dados não é uma tarefa trivial e requer uma escolha cuidadosa de como fazê-lo.  O primeiro passo é a escolha do algoritmo, para aí sim partir para a montagem da infraestrutura. Segundo Robert Sedgewick, autor do livro Algorithms In C, ” o desafio da ordenação é colocar chaves de de classificação e as informações a elas associadas de forma organizada de acordo com uma regra bem definida”.

A ordenação é usada em vários campos como em uma eleição, por exemplo. Mas é nas empresas de Internet que esse recurso é mais explorado e constantemente aprimorado. Para começar, os algoritmos dos motores de busca classificam as páginas de acordo com os assuntos das mesmas. Outros lugares são: os textos no Twitter, propagandas no Facebook, recomendação de livros na Amazon, lista de preços em sites de compras, etc. O detalhe é que, para essas empresas, os números são um pouco maiores: alguns petabytes de dados (ou 1000 terabytes), tornando o desafio ainda maior.

Um grande portal de Internet como o Facebook, lida com o seguinte volume de dados:
•    500 milhões de usuários ativos;
•    100 bilhões de hits por dia;
•    50 bilhões de fotos;
•    2 trilhões de objetos cacheados, gerando milhões de requisições por segundo;
•    130TB de logs todos os dias.

Para trabalhar com tudo isso calcula-se que o Facebook tenha 60 mil servidores ou mais. Contudo, o recurso mais importante, segundo eles, é o time de engenheiros. São pessoas que constroem e gerenciam os sistemas e eles empregam um engenheiro para cada milhão de usuários. O Facebook tem se mostrado estável desde o seu lançamento e o artigo explica o que eles fizeram para construir o site assim.

Juntando toda as peças, observem que temos 500 milhões de usuários e 50 bilhões de fotos. Quando um usuário vê suas fotos ou as de outra pessoa, a ordenação e a busca entram em ação para trazer as imagens corretas. Fazer isso em segundos e não em minutos faz toda a diferença no sucesso do site.

A Copa do Mundo causou várias instabilidades ao Twitter. Embora o site diga que foi um problema da rede no primeiro relatório, houve vários picos de acesso.  Abaixo alguns números interessantes:

  • A palavra vuvuzela gerou 280 mil tweets por dia;
  • 150 mil tweets por hora durante o jogo de abertura;
  • 3283 tweets por segundo durante o jogo do Japão com a Dinamarca.

PORQUE ESSA NOTÍCIA É IMPORTANTE

A divulgação do fato, como ele foi feito e da infraestrutura utilizada exibem uma ideia do que é necessário para montar uma empresa que necessite ordenar informações. O seu uso abre um leque de possibilidades para o surgimento de um novo buscador, site de relacionamentos, microblogs, etc. Para quem tem alguma idéia de um produto de Internet, já sabe por onde começar.

A ordenação de informações é  um recurso muito importante para as empresas de Internet e não implementá-lo de forma correta e escalável pode significar no mínimo lentidão, chegando até a total indisponibilidade do site. No próximo artigo, como uma continuação deste, abordarei os recursos computacionais e de rede para montar um motor de busca.

Para saber mais:
As informações da competição podem ser visualizadas no site oficial da competição.
Para quem quer entender melhor o funcionamento do algoritmo campeão, pode baixar o artigo aqui.

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s