domingo, 23 de maio de 2010

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 :)

29 comentários:

  1. Fico pensando em como o Gibit estará daqui uns anos... será que todas coleções e capas estarão disponíveis?

    Se alguém quiser ajudar com o conteúdo (edições que faltam e tal), como pode fazer?

    p.s - Ah, orgulho do meu Pinguim Azul. ;-)

    ResponderExcluir
  2. Pra adicionar gibis novos tem que fazer um cadastro direto no GCD:

    www.comics.org

    Eu estou colocando os gibis do Celton lá :)

    ResponderExcluir
  3. Olá Ricardo,
    Li seu novo Post sobre o GIBIT... (Na verdade, não merece ser chamado de Post), daria o nome de artigo, ou alguma nomeclatura científica... Rs. Sua escrita e melhor que muitos publicações e materiais de treinamentos oficiais de algumas tecnologias... Gostaria de deixar meus parabéns. Esse foi o segundo artigo seu que li. Muito bacana.

    ResponderExcluir
  4. Ricardo, muito legal post. Agora, como se faz o crawler para baixar as capas? Tem o link do fonte ai?

    ResponderExcluir
  5. Todos os fontes estão no Google Code, o link para o crawler é o abaixo:

    http://code.google.com/p/gibit/source/browse/tools/crawl_covers.py

    ResponderExcluir
  6. Olá. Sou leitora do site da Ila, e resolvi dar uma passadinha por aqui. Eu achava que ela exagerava quando falava q vc era um nerd, mas depois de toda essa explicação que não acabei de ler neste post, vi que ela está certa(no bom sentido é claro). hehehe
    Vou começar a me informar mais sobre gibis. Parabéns por conseguir instigar a imaginação e curiosidade dos teus leitores :)
    abraço. Rafaela

    ResponderExcluir
  7. ricbit, é possível filtrar a busca por idioma ?

    ResponderExcluir
  8. Muito legal este post. E sobre o algoritimo quando as listas nao estiverem ordenadas? Como faço isso?

    ResponderExcluir
  9. @igor Ainda não, está na minha lista de features a fazer.

    @douglas Olha lá no repositório como eu fiz :)

    ResponderExcluir
  10. Cara muito foda, vou fazer um post sobre o gibit lá no meu blog (ou tem problema?).

    ResponderExcluir
  11. OK, devo publicar próxima semana, (ou quem sabe até antes :P)

    ResponderExcluir
  12. Ricardo, fico impressionado com a criatividade que demonstra e mais ainda com a facilidade para "botar em prática". Sou profissional de desenvolvimento web e até então foi o post mais bacana que já li sobre os assuntos. Parabéns!

    ResponderExcluir
  13. Oi Ricbit,

    Quanto tempo você levou para fazer o sistema todo?

    ResponderExcluir
  14. Acho que foram 3 semanas, 1 hora por dia.

    ResponderExcluir
  15. buuuuuuuuuuu
    eu juro q eu tentei ler, mas acho q vou ficar soh com o blog da Ila mesmo x.x

    ResponderExcluir
  16. Cara... eu pensei que eu era um cara anormal e fora do comum. kkkkkk
    Ninguém da facul viu isso aqui ainda!!!
    Muito legal o seu artigo e a capacidade de demonstração do conhecimento em prática é mto dez. Estou lendo os outros. Ah... Alguém já ganhou o cubo mágico da gooogle?
    [s]
    Marcos

    ResponderExcluir
  17. @Marcos

    Sim, o resultado do Ricbit Jam #2 já saiu!

    http://www.ricbit.com/ricbitjam/ricbitjam2.html

    ResponderExcluir
  18. Fez um bom trabalho.
    Jefhcardoso do
    http://jefhcardoso.blogspot.com

    ResponderExcluir
  19. Não sabia que o Google App Engine liberava 1gb para BD. Vi lá que o tráfego suporta um bom volume, e o espaço em disco de 500mb. Não tinha essa informação com relaçao ao BD.

    Genial sua aplicação !!!

    ResponderExcluir
  20. Parabéns pelo artigo, um amigo indicou o seu blog e eu realmente curti muito. Eu já tinha implementado uma solução de busca idêntica a sua (com algumas diferenças claro) em um aplicativo de Livros online, foi a melhor forma que encontrei pra isso no GAE. Fiquei muito surpreso e feliz ao ver que outros também chegaram na mesma solução :)

    ResponderExcluir
  21. Ricardo,

    Muito bacana seu post sobre o App Engine.

    Um abraço,

    Alan

    CF: Wfhg n pvbefvghl: V fnj lhbe jsvr vf yavivt va OU, grua V nz fchcbvfat lbh ner jvexbat ng tbytbr, etuvg?

    ResponderExcluir
  22. Como um bom paraquedista de google, cheguei ao teu blog. IT não é bem minha área mas fiquei impressionado com seu esmero e dedicação na produção do gibit. Tenho um problema parecido (mas mais simples, envolve uma máscara que não tem comportamento fixo) ainda em aberto e gostaria de entrar em contato contigo para ver se tens interesse. No mais, parabéns pelas "publicações" :)

    ResponderExcluir
  23. É... mas qual é o e-mail? :) Só fiz um comentário aqui porque procurei em todos os seus blogs e não achei nada. Só posso acreditar que o o nível de percepção do meu personagem seja muito limitado ou que haveria alguma razão para tal! rsss (Aproveitando, cade os posts no blog de viagens?!) Abraço.

    ResponderExcluir