Como funciona o Google? (I)

Este é o primeiro duma serie de artigos que irei publicar, desvendando alguns ‘segredos’ do funcionamento desta espectacular plataforma de serviços que funcionam na Web. Dizemos que são ‘segredos’, porque a maior parte da informação que discutiremos convosco foi providenciada pela Google e está disponível a quem quiser. Óbvio que procuraremos usar uma linguagem mais simples possível, tecnicamente acessível a maior parte de nós. Estamos em crer que é bastante interessante o que temos para vos relatar.  A razão porque escolhemos a Google foi por termos verificado que esta corporação que iniciou numa sala dum laboratório universitário em Stanford, tornou-se poderosa, a ponto de consagrar-se um provedor de telecomunicações, publicidade, entretenimento, computação e acima de tudo começa a assumir posições de padronizador/dinamizador em campos de pesquisa absolutamente emergentes hoje em dia, como o BIGData que iremos falar mais adiante.

Eu queria iniciar por contar-vos uma pequena historia: Em 2004/2005 enquanto técnico médio e programador Web freelancer em ASP/ASP.Net/C#/SQL Server fui assistir a conferencia na UCAN que consagrou a já defunta Associaçao Angolana de Software Livre (ASL).
A conferencia estava cheia de gente com bagagem de primeiro grau, como por exemplo Dr Pedro Teta, Eng Dimonekene Ditutala e Msc Mateus Padoca Calado. No entanto o que me chamou mesmo a atenção, foi a declaração do Dr Aires Veloso (um experiente docente de programação), onde  ressaltou que um sistema a serio tinha de ser criado com uma framework/linguagem de verdade, tal como .Net ou Java.
Aquelas palavras ficaram-me na mente, ainda mais, porque não possuía conhecimentos sobre computação paralela. Somente anos depois, percebi que fazia todo sentido ele ter dito aquilo. Aquela era a época dominada por linguagens para desenvolvimento dinâmico como Cold Fusion Modules (CFM), ASP e um tal de PHP, lol. Estas eram, na altura, linguagens não orientadas a objectos e sem suporte a computação paralela.

Por isso era somente natural que um serviço de buscas e publicidade como o Google que crescia a todo vapor se sentisse ‘tentado’ a optar por plataformas como ASP.Net e Java. Mas, nem pensar!!! O génio de Sergey Brin e Lauwrence Page ‘permitiu-os’ seguir um outro caminho: Optaram por utilizar uma linguagem que até então era desconhecida para a Web: O Python (esta linguagem que tive oportunidade de aprender enquanto estagiário numa das instituições governamentais).
De facto, Sergey e Larry, não a escolherem por acaso. Esta linguagem tinha suporte a orientação de objectos, sendo fortemente tipada (tipos de dados interessantes, como listas e dicionários) e sobretudo, é software livre. Tiveram ‘apenas’ o desafio de portar para a Web, porque até então não havia conhecimento do uso desta linguagem na Web de forma massiva, senão em desktop e também aí, muito mais em aplicações para administração de sistemas *.NIX.

Este desafio foi vencido recorrendo ao uso de CGI (Common Gateway Interface) sobre o servidor HTTP Apache, ou seja, por meio dessa interface era possível a código não nativo ser executado pelo Apache. Alguns de vocês deverão lembrar que antes de 2000 e um pouco posterior a isso programava-se para a Web até com linguagem C e C++ (na minha opinião algo terrível) justamente porque a CGI do Apache permitia essa versatilidade. Era algo estranho e inúmeros problemas de segurança envolvendo sobreposição de memoria (Buffer Overflow) sobre HTTP foram revelados. Mas isto está fora do nosso contexto.

Esta decisão, longe de ser uma espécie de estilo NERD por parte de Sergey e Larry, foi antes uma estratégia de longo prazo que viria a influenciar toda a politica de crescimento da infra-estrutura da Google, ou seja, seria suportada por produtos de baixo preço, mas de elevado desempenho operacional, o que permitiria que sua infra-estrutura fosse facilmente escalável sobre custos baixos. Se a Google apostasse em desenvolver a sua infra-estrutura sobre frameworks como ASP.Net ou Java, corria o risco de ficar muito dependente de patentes e tecnologias de empresas que sabiam eles, mais cedo ou mais tarde, seriam seus adversários de negócios.

O problema do crescimento

Com o aumento da quantidade de informação produzida via Web, os serviços de indexação da google foram crescendo de tamanho. Por exemplo de 1999 a 2009, ou seja em 10 anos a google passou a indexar de 70 milhões a muitos biliões de documentos, a media da pedidos processados/dia aumentou cerca de 1000 vezes, cada documento passou a ter 3 (três) vezes mais informações nos serviços de indexação.

Gerir tamanha quantidade de informação (índices e documentos) mostrou desde o inicio ser um desafio e tanto para o pessoal da Google.
Como todo projecto vencedor tem uma base forte, a Google não foge a regra. E a sua força encontra-se também na excelente esquematizar da sua arquitectura, simples mas sobretudo inteligente.
A principio a Google adoptou a seguinte arquitectura (1997):

Arquitectura Google em 1997

Arquitectura Google em 1997

Apesar da sua aparente simplicidade, era uma arquitectura já aparentemente complexa possuindo elementos que estão a ser utilizados até hoje. Como podemos notar, existem dois grupos de servidores (clusters) que desempenham um papel importante por detrás dos pedidos de pesquisa (query) recebidos pelo servidor que chamaremos frontal (frontend): Os servidores de indexação e de documentação.
Os servidores de indexação possuem algumas informações sobre paginas, como por exemplo um índice invertido duma URL, do tipo ‘com.wordpress.snnangola‘. Os servidores de documentação armazenam todos os documentos possíveis existentes na Web e os ordenam aleatoriamente por fragmentos de documentação que falaremos mais abaixo. Cada documento possui propriedades tais como, um ID único conhecido como docid, um conjunto de palavras-chave que permitirão corresponde-lo a uma possível procura, e um Score atribuído pelo algoritmo PageRank.

Quando um pedido de pesquisa é enviado para servidor frontal, este encaminha para o servidor de indexação que mapeia individualmente cada palavra do pedido para uma lista de documentos relevantes. A relevância (Score) ou o grau de importância do documento, é determinada pelo PageRank. Essa relevância determina a ordem de saída dos documentos para a resposta ao pedido do usuário (melhor PageRank sai primeiro).

Essa aparente facilidade, entretanto esconde uma alta complexidade. Como já dissemos, com o aumento do numero de documentos, usuários e mobilidade na Web, o numero de pedidos de pesquisa/segundo aumentou brutalmente, o que perigosamente poderia aumentar o latência (o atraso ou RTT time) na resposta aos pedidos dos usuários, afinal haveria mais pedidos disputando entre si, sobre quem seria atendido primeiro. Felizmente a Google também tem uma solução para este problema, recorrendo a computação paralela. Como assim?

Pela figura acima observamos que tanto os servidores de indexação, como os servidores de documentos, possuem fragmentos (shards). Interessa de facto, falar sobre os fragmentos de indexação, porque estes lidam directamente com os pedidos dos usuários, via servidor frontal, logo os servidores de indexação, estariam em teoria mais sujeitos a estresse. Bom, isto já não é um problema porque os fragmentos possuem aleatoriamente índices para um subconjuntos de documentos do índice total. Esta técnica é conhecida como particionamento da indexação por documento.

Isto constitui inúmeras vantagens, na medida que por exemplo, cada fragmento pode processar cada pedido independentemente, também melhora o desempenho do tráfego da rede, e facilita a gestão da manutenção de informação por documento.
Mas também tem os seus contras, na medida que cada fragmento precisa processar cada pedido, e cada palavra da pesquisa necessita de ser procurada em cada N fragmentos.
Para minimizar estes efeitos, os pedidos feitos a um fragmento são distribuídos a uma pool de servidores. Cada fragmento também está distribuído numa pool de servidores no cluster de indexação.

O processo de pesquisa pode então ser resumido da seguinte forma:

  1.  O usuário digita uma única/serie de palavra(s) (como por exemplo: ‘capital de angola‘);
  2.  O servidor frontal recebe o pedido e envia para um dos fragmentos localizado numa das pools do cluster de indexação;
  3.  O fragmento dado a(s) palavra(s) corresponde a uma lista ordenada de documentos composta por docid, score, etc;
  4.  Um dos fragmentos numa das pools do cluster de documentação recebe a mensagem do fragmento de indexação e dado o docid e a(s) palavra(s), gera um conjunto de documentos, composto por titulo e trecho. Claro que com o docid já é mais fácil localizar o documento completo no disco.

No entanto, isso levanta uma outra questão: Se um dos servidores dos cluster‘s de indexação/documentação vai abaixo, por qualquer motivo, a pesquisa é abolida? A reposta encontra-se na estratégia de computação distribuída que a Google adoptou desde o inicio.

Estratégia de computação distribuída

A google sempre adoptou uma estratégia de computação distribuída. Isso mesmo pode ser percebido pela sua arquitectura já descrita na figura acima, mas que actualizaremos já, sobre uma outra perspectiva na figura abaixo:

Arquitectura google 1997 suportando cache e Ad Sense

Arquitectura google 1997 suportando cache e Ad Sense

Podemos facilmente perceber as mudanças ocorridas:

  1. Introdução de replicação
  2. Introdução de caching

O investigador Português Jorge Cardoso no livro ‘Programação de sistemas distribuídos em JAVA, Editora FCA‘ escreveu que ‘o principio da localidade, admite que a comunicação entre computadores segue dois padrões distintos. Primeiro, é mais provável que um computador comunique com computadores que estejam mais próximos do que com computadores que estejam mais longe. Segundo, é provável que um computador comunique com o mesmo conjunto de computadores repetidamente‘.

Se você percebeu, notou claramente que o primeiro padrão é técnica de replicação, e o segundo a técnica de caching. Pela figura acima nota-se claramente a existência dos dois conceitos. Exactamente ao lado do servidor frontal notamos a presença dum conjunto de servidores de caching que não sabemos com toda certeza se pertencem a um cluster. Entretanto, isso é bastante útil, quando os usuários realizam pesquisas que não foram actualizadas. Nesse caso, se elas não mudaram então não é necessário encaminhar a pesquisa para o cluster de indexação, mas sim para o suposto  cluster de caching que encaminha os documentos, já anteriormente pesquisados, para o usuário.

Pela figura acima notamos também a existência de replicação vertical nos fragmentos de indexação de de documentação. Isso é muito importante, na medida em que explica porque raramente sentimos uma pesquisa no Google ser abolida ou gerar um erro. Notamos, que ainda que um fragmento vá abaixo por causa dum erro lógico ou físico num dos servidores do cluster, pela capacidade de replicação, automaticamente a tarefa passa para outro fragmento pertencente a outra pool de servidores. Isso é uma maravilha, já que estamos em crer ser difícil que uma pool inteira falhe, mas mesmo que falhe haverá sempre outra pool para a substituir.

Por esta altura já conseguimos perceber porque o Google consegue responder de forma tão rápida as nossas pesquisas. Sim, existem outras técnicas e alguma delas iremos abordar mais adiante, no entanto, isso é em parte porque eles conseguem manter imagens de toda a Web replicadas em seus cluster’s de documentação por todo mundo.

Não existirão teoricamente muitos problemas de paginas armazenadas no cluster mas que já não existem nos servidores onde estavam alojadas. O sistema Google é inteligente o suficiente para verificar isso, e actualizar se possível, da forma mais rápida. Mas isso as vezes não acontecia tão rapidamente, e por um motivo muito simples. Os cluster’s da Google começaram a expandir-se muito rapidamente, até a escala global.
As vezes fazemos uma pesquisa a partir de Angola, e os resultados Web vem da Irlanda, mas os de Video (Youtube) vem do Brasil, o AdSense do Polo Norte (exagerei!!!) no entanto, não existe praticamente latência. Como tudo isso é possível? Se um cluster de documentação nos EUA actualiza os seus documentos, os cluster’s em todo mundo necessitam fazer isso de forma automática com mínimo de atrasos possíveis, sob pena de elevadas receitas serem perdidas.
O próximo artigo falará sobre isso.

6th Sense. Um novo conceito

Nao sei bem como explicar o que é o 6th sense, mas o seu conceito parece ser o de ‘use em qualquer lugar’ ou seja usar o computador em qualquer lugar, em cima da mesa, na parede, no jornal etc. E mais, torne estas interfaces tateis e interativas, esqueça portanto teclados, mouses etc. Que incrivel!!! Este video ilustra um bocado do que pode fazer este conceito que custou apenas 350 USD em equipamentos:

Links:

http://www.pranavmistry.com/projects/sixthsense/

Magalhães PC em Angola, ou a velha estoria dos UMM?

Uma coisa nao entendo. Porque razão é que sempre que alguma coisa a ver com tecnologia em Portugal sai da toca, imediatamente torna-se Angola um destino, e não países mais avançados?

Curiosamente hoje fala-se do Intel ClassMate (foto a esquerda), NetBook da Gigante do Hardware, Intel que estranhamente tem um nome diferente em Portugal, sabem qual? Pois, Magalhães (foto a direita)!

Foi uma jogada de mestre da Intel que ao licenciar a produção do seu NetBook a JP Sá Couto/Prológica de Portugal que apenas faz a montagem do hardware e a tradução do software  para lingua Portuguesa (até mal feita por sinal) possibilitou que o mesmo fosse vendido a países antes impensaveis como já noticiamos aqui. É claro que na Europa ninguem iria comprar um produto a Portugal quando poderiam discutir a preços mais acessiveis directamente com a Intel como fez a Nigeria, por exemplo.

Duma coisa tenho a certeza: Mesmo em Portugal, ninguem acredita nesta ‘estoria’ do Magalhães, e é claro Angola está longe de ser Portugal, porque senão nao teriamos sido dos poucos países onde os famigerados UMM Alter, conseguiram vender-se.

Índia envia missão não-tripulada à lua (fotos)

O Chandrayaan-1, espaçonave cubóide construída pela Organização Indiana de Pesquisas Espaciais (Isro, na sigla em inglês), foi lançado de um centro espacial no sul do país, logo após o amanhecer. Com o lançamento, a Índia celebra suas ambições de progresso científico e espera ganhar mais espaço nos negócios espaciais.

fonte: yahoo, the times of india

“Human Jet” voará de França a Inglaterra

Yves Rossy é um Suiço que criou um dispositivo planador que acoplado ao corpo humano mais parece um filme de ficção cientifica. Como ele funciona está fora de minhas intenções tentar perceber. A verdade é que voa e voa mesmo, prova disso, o mesmo voará de Calais em França a Dover em Inglaterra, percorrendo 35 Km de distancia.

Acelerador gigante de partículas vai parar durante dois meses

O acelerador gigante de partículas LCH do Centro Europeu de Investigação Nuclear (CERN) vai estar parado durante dois meses, depois de um “incidente” registado durante o ensaio ter danificado um elemento do mecanismo, anunciou hoje um porta-voz da instituição.

Em comunicado, o CERN explica que o problema foi provocado por uma importante fuga de hélio ocorrida ontem no túnel.

Apesar de garantir que o incidente não representou qualquer perigo para a segurança do pessoal, um porta-voz da instituição afirma que um “elemento da máquina tem de ser reparado”, o que obrigará à paragem durante dois meses da experiência.

Este é já o terceiro problema registado no Grande Acelerador de Hadrões (conhecido pela sigla em inglês, LHC), o maior instrumento de física do mundo. O primeiro foi um ataque de “hackers” no arranque da experiência, a 10 de Setembro, mas só noticiado alguns dias depois.

Logo no dia seguinte, um problema eléctrico que afectou o sistema de refrigeração do circuito, com 27 quilómetros, obrigou à suspensão da experiência por uma semana, para a substituição de um transformador de 30 toneladas

O LHC começou a funcionar no passado dia 10 de Setembro numa cerimónia de pompa e circunstância. Trata-se de um projecto faraónico que juntou milhares de cientistas do mundo durante 20 anos e que procura simular os primeiros milésimos de segundo do Universo, há cerca de 13,7 mil milhões de anos atrás, sendo já considerado a experiência científica do século. É a maior máquina do mundo, tão grande e sofisticada que não poderia nunca ser fabricada por uma única empresa, ou um único país. Envolve 6000 cientistas, levou uma década a construir e custou dez mil milhões de dólares.

O objectivo final desta grande experiência é poder dar resposta a muitas perguntas sobre a origem do Universo, entender por que a matéria é muito mais abundante no Universo do que a anti-matéria, e chegar a descobertas que “mudarão profundamente a nossa visão do Universo”, segundo o director do CERN, Robert Aymar. Uma das aspirações dos cientistas é encontrar o hipotético bosão de Higgs, uma partícula que nunca foi detectada com os aceleradores existentes, muito menos potentes que o LHC.

Fonte: publico

Promis? Nao! “Siemens Intelligence Platform”

Já devemos ter ouvido falar sobre o Promis um suposto sistema de espionagem usado por agencias ocidentais capaz de filtrar mensagens electronicas, documentos etc e que supostamente estaria instalado em sistemas bancarios e outros pontos chave de acesso vitais. Também devemos ter ouvido falar do Echelon um sistema de filtragem de voz capaz de alertar sobre possiveis mensagens de conteudo perigoso disparadas por varias centrais e backobones de telefonia que colocado em pontos chave existia para alertar sobre possiveis ataques terroristas e acções perigosas etc.

Numa das ultimas conferencias da Defcon maior evento de segurança informatica do mundo e que se realiza anualmente em Las vegas um funcionario da NSA, agencia de segurança dos EUA afirmou que o Echelon simplesmente como era conhecido nao existia e era impossivel de existir por ser “impossivel” tecnicamente suportar filtragem e analise de tantos pacotes de voz ainda de que de um modo automatico.

Só que estas “estorias” provocam ideias e a Siemens gigante Alemão da eletronica afirma ter produzido uma plataforma de espionagem (composta por modulos de fiscalização) capaz de filtrar e identificar ameaças de terroristas, por analisar diversos tipos de documentos, chamadas telefonicas, emails, transacções bancarias etc. Combinadas estas recolhas elas podem ser combinadas no sentido de se procurar por nomes, numeros e outros dados que representem uma ameaça bem como por meio destes ser possivel ligar as ameaças a possivel documentaçao ou ligações.

O software parece ter inteligencia artificial suficiente para identificar “padrões de comportamento” a fim “suspeitar” por exemplo duma transacção bancaria realizada a um banco estrangeiro ou do numero de ligações a uma determinada entidade.

Junto com tudo isto este pacote vem ainda acompanhado dum centro de monitoramento de chamadas telefonicas desenvolvido pela Nokia em conjunto com a propria Siemens.

No entanto especialistas como Bruce Schneier ja avisaram que este sistema nao é 100% fiavel e que pode produzir tanto false-positives como false-negatives, questionando mesmo as intenções da Siemens que afirma ter já vendido o mesmo a mais de 60 países.