Batman e a escalabilidade

Dia desses eu resolvi colocar os meus gibis em ordem (tarefa bem difícil, dada a quantidade deles). Mas logo no começo eu já apanhei pra conseguir ordenar dois deles. Ambos eram Punisher #1, ambos do Garth Ennis, mas qual veio antes?

Normalmente esse tipo de dúvida eu resolvo consultando o Grand Comics Database, um repositório imenso de informações sobre gibis. Porém, após usar um pouco a busca do site, eu notei que ela, hm, não funciona tão bem.

Por exemplo, um dos meus gibis é o Sergio Aragonés' Groo: Mightier than the Sword. Se você buscar no site por "mightier than sword", ele não acha, porque só faz match exato. Se você buscar por "Groo", também não acha. O nome foi indexado como "Groo:", e sem os dois pontos no final ele não acha. Por fim, se você buscar por "Aragones" ele também não acha, porque você não colocou o acento.

A primeira coisa em que pensei foi "poxa, é simples fazer melhor que isso". Mas falar é fácil né? O jeito é arregaçar as mangas e fazer um search que funcione!

Design

Vamos então aos requisitos: eu quero fazer um buscador que me retorne todas as séries que constem no database do GCD. O buscador precisa ser web-based, escalável e de latência baixa.

Para conseguir latência baixa, o jeito mais fácil é fazer alguma coisa que seja AJAX-like. E pra isso, minha ferramenta predileta é o Google Web Toolkit. Eu até gosto de programar em javascript, acho a linguagem legal, mas o problema é que cada browser implementa javascript de um jeito, e na prática você precisa perder um tempão com as peculiaridades de cada browser.

Com o GWT você escreve a aplicação uma vez só, em Java, e ele então compila seu código, gerando um javascript customizado para cada browser. Quando você faz o request, ele faz o download só do javascript correspondente, assim você não precisa gastar banda baixando código do Firefox se está rodando o Chrome. Daí em em diante é tudo AJAX, ou melhor, AJAJ (por default ele usa JSON ao invés de XML).

Para que a aplicação fosse escalável, eu usei o Google App Engine. Com ele, você pode rodar seu servidor direto na infraestrutura do Google, com todas as vantagens que isso implica. Por exemplo, você não precisa se preocupar em ficar dimensionando quantas máquinas são necessárias, ele faz isso sozinho pra você, adicionando máquinas conforme a carga no servidor começa a subir.

O App Engine ainda tem outra vantagem: ele é gratuito! Quer dizer, é gratuito até um certo limite, mas um buscador de gibis é uma aplicação de nicho, e na prática eu não vou ter tráfego suficiente para precisar passar desses limites. Por exemplo, o limite do database gratuito é 1GB, mais que suficiente pra guardar todos os dados que vão ser buscados.

Implementação

Definida a plataforma, vamos à implementação. O jeito mais fácil de fazer um buscador é usando uma lista invertida. Por exemplo, suponha que o database contém os gibis abaixo:

1 - Green Arrow
2 - Green Lantern
3 - Iron Lantern
4 - Green Lantern: Rebirth

A lista invertida correspondente fica assim:

arrow: 1

green: 1,2,4

iron: 3

lantern: 2,3,4
rebirth: 4

Tendo a lista invertida é fácil fazer a busca: basta procurar na lista invertida cada palavra da minha query, e fazer a intersecção dos conjuntos resultantes. Por exemplo, "Green Lantern" retorna {1,2,4} e {2,3,4}, cuja intersecção é {2,4}, que são os dois gibis que vamos retornar. Se as listas estiverem ordenadas, você pode calcular essa intersecção em O(n), e se não estiverem ordenadas, você ainda pode fazer em O(n) usando um pouco de espaço extra (como?)

Dentro do App Engine, as listas invertidas vão ficar guardadas no Datastore, que é um database escalável construído em cima da BigTable. Vale notar que o Datastore não é um database convencional: ao invés da analogia comum de uma tabela com linhas e colunas, o mais apropriado é pensar nele como se fosse um dicionário de dicionários: cada "linha" agora é a chave do dicionário mais externo, e as "colunas" são as chaves dos dicionários internos. Dessa maneira, não é obrigatório que cada "linha" tenha sempre as mesmas "colunas".

Adicionalmente à lista invertida, nós vamos guardar também uma lista direta. Assim, quando eu descobrir que os gibis a mostrar são o 2 e o 4, eu posso ir na lista direta e pegar mais dados sobre eles, como nome, editora, ano de lançamento, etc.

Depois disso, nós ainda precisamos fazer alguma espécie de ranking pra descobrir em qual ordem vamos mostrar os resultados. Em geral essa é uma das partes mais difíceis de uma search engine, mas eu resolvi simplificar e ordenar por número de edições (então Action Comics, que tem quase 900 edições, vai aparecer antes de Slave Girl Comics, que tem só duas).

Por fim, todo esse trabalho de lista invertida, intersecção, lista direta e ranking pode eventualmente ficar meio pesado, então nós vamos colocar um cache no caminho para guardar todas as queries já feitas, sem precisar repetir trabalho. O App Engine fornece um módulo de Memcache que é ideal para isso.

Preparando os dados

Antes de começar a usar o buscador, precisamos gerar as listas e colocá-las dentro do Datastore. O GCD fornece um arquivão com o dump do MySQL deles (que na verdade é um arquivo texto com 330MB de INSERTs). Com os dados em mãos, eu escrevi um script python que lê esses dados, cria a lista invertida e a lista direta, e faz o bulk upload desses dados para o Datastore.

O único cuidado extra nessa etapa é tomar cuidado com o unicode, já que eu quero que buscas por "mônica" e "monica" retornem o mesmo resultado. Uma maneira seria tirando os acentos no cliente, mas pra que fazer isso online se você pode fazer offline né? Mais fácil, na hora de criar a lista invertida, gerar duas entradas iguais, uma com "mônica" e outra com "monica".

Outra idéia que tive foi retornar as capas dos gibis, e não apenas os nomes deles. Nesse caso o processo foi um pouco mais complicado, porque o GCD não fornece um arquivão com todas as capas, assim como eles fazem com o dump do MySQL. Eles acham que fornecer esse arquivão para download poderia ser uma violação do fair use, então a recomendação é "se você quer as capas, faça um crawling você mesmo".

Bora fazer um crawler então! Usando várias threads em python foi tranquilo, eu baixei os 500MB de capas em poucas horas. Como o Datastore não foi feito para guardar imagens, eu optei por hospedar as capas no meu próprio servidor (www.ricbit.com).

O cliente

Escrever o cliente usando o GWT foi a parte mais difícil. Não que programar em GWT seja difícil, pelo contrário, usando UiBinder é bastante fácil. O problema mesmo é que eu manjo de CSS menos do que gostaria, então demorei um tempão até conseguir o layout desejado. Mas, como esperado, o resultado funciona em tudo quanto é browser, até mesmo no IE!

E para dar um toque especial no layout, eu pedi para a minha esposa fazer umas ilustrações para o logo e para a tela de loading do site, que ficaram bem bacanas (se você precisa de ilustrações para o seu site, fale com a Ila Fox!)

Por fim, eu ainda precisava de um jeito de fazer profiling do site, então fiz com que o servidor me retornasse o tempo gasto em cada etapa do processamento, e usei o Google Chart Tools para apresentar esses dados de uma maneira fácil de interpretar.

Segurança

Você não pode fazer uma aplicação web-based sem pensar na segurança, certo? Mas, felizmente, esse buscador não tem muitos pontos vulneráveis. O único ponto onde o usuário malicioso pode tentar fazer alguma coisa é no campo da query, mas eu não preciso nem sequer sanitizar, porque tudo que a aplicação retorna são os nomes dos gibis que já estão no datastore.

Na verdade, só de rodar a aplicação no App Engine você ainda ganha na faixa um monte de vantagens, entre elas detecção de ataques de DoS. Ele sabe sozinho filtrar ips que estão te bombardeando sem nem precisar configurar nada.

Juntando as peças

No final, o sistema completo ficou assim:

Se você quiser testar a aplicação, basta clicar no screenshot abaixo:

Agora finalmente dá para achar aquele gibi do Groo :)

Profiling

Com o sistema completo e funcionando já dá pra fazer o profiling. Para isso, basta digitar "debug:" antes de uma query qualquer. Por exemplo, se você fizer "debug: Groo" logo após o deploy do servidor, o resultado vai ser esse:

O App Engine faz resource management de maneira bem agressiva, se você não tiver nenhuma query em 10min, ele derruba sua instância. Daí, a primeira query que você fizer tem o overhead de levantar o serviço novamente, que nesse caso foi de quase 5 segundos. Mas se você fizer em seguida a mesma query, ela vai ser bem mais rápida:

Bem melhor né? Alguns poucos milisegundos no memcache, o resto é só o tempo de trafegar o resultado do servidor pro seu cliente. No total, pouco menos de 350ms de roundtrip, o que é bastante rápido.

Mas essa é uma query fácil. Uma das queries mais difíceis é "debug: Batman", porque existem muitos, muitos gibis do Batman. Vejamos:

O tempo é praticamente todo gasto baixando os dados dos gibis da lista direta, quase 3 segundos. Mesmo considerando que é um batch request de 824 gibis, três segundos é meio lento. Mas ao usar o Datastore, o importante é notar que esse tempo é independente da carga. Você até consegue uma solução customizada mais rápida que isso, mas sem tomar muito cuidado, o tempo de cada request vai aumentar se o número de usuários simultâneos crescer. Com o Datastore, o tempo é sempre o mesmo, e você está imune a baleiadas.

Naturalmente, isso só vale para a primeira vez. Se outro usuário buscar por Batman logo em seguida, ele vai pegar o resultado do memcache:

Agora deu só 500ms, e o tempo todo é praticamente só o overhead do download dos 824 gibis.

Outra query curiosa é "debug: Captain America Comics". Existem inúmeros gibis com captain (Captain America, Captain Marvel, etc), inúmeros com america (Captain America, Justice League of America, etc), e um outro sem número de Comics, então o tempo agora não é dominado pela lista direta:

Dessa vez dá pra ver o tempo que ele gasta fazendo a intersecção das listas invertidas (e note que até agora nós nem vimos tempo algum com ranking, é desprezível). O tempo total foi de 800ms, mesmo sem o memcache.

O source

É claro que isso tudo foi uma visão bem high-level do Gibit, tem um monte de detalhes curiosos que eu omiti para não deixar o post muito grande. Se você quiser ver a implementação, o código é open source e está disponível no Google Code:

Source code do Gibit

Se você tiver alguma dúvida específica, é só deixá-la nos comentários que eu tento responder. Enjoy :)