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.

PRISM: Isso é alguma novidade?

Não tenho duvidas que já não adianta falar mais sobre o PRISM, porque quase tudo já foi revelado a imprensa sobre ele. Sua capacidade de aceder facilmente aos dados pessoais de quem quer que seja com um ou dois cliques no rato, espantariam até pessoal optimista da craveira de George Orwell.

O PRISM é ‘abastecido’ de informações de diversas fontes diferentes

No entanto, muito mais do que ficar espantado com o PRISM, fiquei mesmo, sim admirado, com o espanto das pessoas perante revelação da existência de tal programa. É que ao que consta daquilo que venho acompanhando desde 2000/2001, o PRISM já existia, embora parece que com outros nomes, ou seja os EUA sempre tiveram os seus sistemas de vigilância electrónica.

Vamos então a uma resenha, se você esqueceu, provavelmente lembrará da maior parte deles:

1 – FBI Carnivore

Esse sistema de vigilância electrónica deu que falar no inicio de 2000. Tratava-se entretanto de algo bem ‘simples’. Um computador com Windows NT ou 2000 e um software farejador de pacotes em modo promiscuo (ou seja, ‘recebia’ tudo) que ficava estrategicamente posicionado nos provedores Internet de interesse da vigilância do FBI. Como eram muitos dados a serem recebidos em submúltiplos de segundo, o software actuava como um classificador de dados, armazenando e descartando informação. Essa forma de actuação do software, bem como o facto de ter sido revelado a imprensa fizeram o FBI descontinuar o seu uso.

A repercussão dele foi tanta que tive um colega em 2001 que dizia de pés juntos que conhecia pessoas em Luanda que usavam o Carnivore. Claro que o colega estava a viajar, mas deu para medir o impacto da informação sobre o Carnivore (também, com um nome desses?).

2 – Prosecutor’s Management Information System (PROMIS)

As informações sobre o PROMIS são tão movie style que até hoje me pergunto se realmente chegou a existir. Em 2000/2001 dizia-se que era um software que podia saber o numero da sua conta bancaria, e rastrear suas transacções financeiras em qualquer parte do mundo, aliás este foi o objectivo numero um da sua criação. Diz-se dele que não dependia da Internet para transmissão dos dados colectados, mas sim, ficou teorizado que o PROMIS era vendido e introduzido nas empresas alvo juntamente com hardware. Este ultimo tinha instalado secretamente um sistema de transmissão dos dados recolhidos via espalhamento espectral, o que até faz todo sentido, porque quem leu um bocado de técnicas de modulação CDMA sabe que o sinal aparece como ruído e os códigos de espalhamento pseudo-aleatórios tornam difícil a interpretação da informação.

Entretanto, entre informações ‘enroladas’, como por exemplo, aquele que dava conta que Bin Laden tinha uma copia dele (é, vocês devem lembrar do ‘computadorzeco’ encontrado em Abbottabad, lol), praticamente nunca foram confirmadas, por fonte oficial. Hoje já quase que não existem pessoas interessadas em falar sobre ele.

3 – National Security Agency (NSA) ECHELON/Five Eyes/UKUSA

Esse é o único que eu acredito que podia existir. Trata-se já, dum sistema de maior dimensão e com uma abrangência geográfica bastante interessante, passando pelos USA, UK, New Zealand e Austrália. Diz-se dele como um conjunto de sistemas SIGINT (Signal Intelligence) capazes de interceptar comunicações que envolvam transmissões radio, fax, email e web. Para isso beneficia-se de estar  instalado estrategicamente e com recursos tecnológicos de elevada capacidade de intercepção via rádio e via sistemas de comutação de provedores de telefonia e Internet.

File:120715 Grondstation Nationale SIGINT Organisatie (NSO) Burum Fr NL.jpg

Por outro lado, poderosos filtros que actuam em tempo real conseguem classificar a informação de forma mais apurada e ‘disparar alarmes’ para interceptores, escutas e gravadores de dados e voz. Essas características fazem dele algo diferente do ‘modesto’ Carnivore.

4 – National Security Agency (NSA) PRISM

Os anos foram passando, veio o 11 de Setembro, o nível de vigilância electrónica aumentou, mas sobretudo também, apareceu um novo conceito da utilização da Web: As redes sociais. A quantidade de informação que essas redes começaram a gerir era dum espanto brutal. Sempre se disse, e sempre se desconfiou que Microsoft, Google, Facebook, etc, entregavam dados de quem quisessem a quem ‘de direito’ pedisse. Essas informações nunca foram confirmadas por essas empresas e até hoje mesmo com o escândalo do PRISM e que envolve também um outro escândalo recente envolvendo escutas na telefónica Verizon, continuam veementemente a negar qualquer envolvimento. E nós estamos a falar de volumes de dados completamente ‘galácticos’. Só o Facebook possui mais de 50 biliões de fotos e 1 bilião de utilizadores. O Google transacciona milhões de comunicações e pedidos por segundo, portanto gerir e interpretar isto não é brincadeira de crianças. Ou pelo menos não era até a bem poucos anos, porque de um tempo a esta parte foram sendo feitos avanços importantes na interpretação de dados, reconhecimento facial e reconhecimento de voz, ao ponto de termos disponíveis em dispositivos domésticos como Smartphones e televisores inteligentes. São esses avanços que permitiram a  Edward Snowden sentar na sua cadeira na sede da NSA e saber da vida de quem ele quisesse saber, sem supervisão de ninguém.

No meu entender só pode se espantar com essas informações quem tem algo a esconder. Quem não tem nada a esconder não tem motivos para estar preocupado com o facto de existir uma rapaziada que gosta de andar ao ‘farejote’ de informações sobre a vida dos outros. Pensar que um país como são os USA se mantém de pé, sem andar ao ‘bisbilhote’ da vida alheia é pura ilusão. E vão continuar independentemente de quem reclamar disso. É a conjuntura dum sistema mundial que está no seu fim e não tarda irá colapsar.