[2009 WSDM] Desafios na construção de sistemas de recuperação de informação em larga escala

Principais dimensões e trade-offs de sistemas de recuperação de informação

• Ao projetar um sistema, é preciso equilibrar cuidadosamente os trade-offs de engenharia entre os seguintes fatores.
  • Número de documentos indexados
  • Número de consultas processadas por segundo (QPS)
  • Atualidade do índice/velocidade de atualização
  • Latência da consulta
  • Quantidade de informação armazenada para cada documento
  • Complexidade/custo do cálculo de pontuação/algoritmo de busca
• A dificuldade de engenharia tende a ser proporcional ao produto desses parâmetros.
• Todos esses fatores afetam o desempenho geral e a relação custo-benefício do desempenho (desempenho por dólar).

Mudanças na escala do sistema (1999 vs 2009)

• Nos últimos 10 anos, a escala do sistema e os requisitos de desempenho mudaram drasticamente.
  • # documentos: ~70 milhões → vários bilhões (~100x de aumento)
  • número de consultas processadas por dia: (~1000x de aumento)
  • informação de índice por documento: (~3x de aumento)
  • latência de atualização: vários meses → alguns minutos (~10000x de redução)
  • latência média de consulta: <1 segundo → <0,2 segundo (~5x de redução)
  • recursos do sistema: mais máquinas * máquinas mais rápidas (~1000x de aumento)
• Como esses parâmetros continuam mudando, às vezes em várias ordens de grandeza, o projeto do sistema precisa evoluir continuamente.
  • Um projeto adequado em um certo momento (X) pode se tornar um projeto muito ruim em escala 10x ou 100x maior. (Por isso, vale projetar pensando em um crescimento de cerca de 10x, mas planejar uma reescrita antes de chegar a 100x.)
  • Houve 7 grandes reformulações nos últimos 10 anos.

Arquitetura inicial do sistema (1997-1999)

• Fase de projeto de pesquisa (1997):
  • O servidor web de frontend recebia as consultas e distribuía requisições de processamento entre servidores de índice e servidores de documentos
  • Servidores de índice: sharding por ID do documento (docid)
  • Servidores de documentos: sharding por ID do documento (docid)
• Princípios básicos:
  • Os documentos recebem IDs inteiros (docids) (documentos importantes/de alta qualidade recebem IDs menores)
  • Servidores de índice: (consulta) → retornam uma lista ordenada de (pontuação, docid, ...). Sharding por docid, com replication para garantir capacidade. Custo O(#consultas * #documentos no índice).
  • Servidores de documentos: (docid, consulta) → geram (título, snippet). Mapeamento de docid → texto completo do documento em disco. Sharding por docid. Custo O(#consultas).
• Sistema de serving (1999):
  • Foram adicionados à estrutura do projeto de pesquisa servidores de cache e integração com sistema de anúncios
  • Operação com réplicas (Replicas) dos shards de índice/documentos
  • Caching: cache tanto dos resultados de índice quanto dos snippets de documentos. Taxa de acerto de cache de 30-60%. Grande contribuição para melhorar o desempenho e reduzir a latência de consulta. (Mas é preciso cuidado com grandes picos de latência ao atualizar o índice/limpar o cache.)

Estratégias de particionamento do índice

• Por documento (By doc): cada shard possui o índice de uma parte dos documentos (escolha do Google)
  • Vantagens: processamento de consulta independente por shard, facilidade para manter informações adicionais por documento, menor tráfego de rede (requisição/resposta)
  • Desvantagens: todos os shards precisam processar a consulta; para uma consulta com K palavras, são necessários O(K*N) seeks de disco em N shards
• Por palavra (By word): cada shard possui o índice de uma parte das palavras sobre o conjunto completo de documentos
  • Vantagens: uma consulta com K palavras é processada por no máximo K shards, com O(K) seeks de disco
  • Desvantagens: exige muito mais largura de banda de rede (é preciso reunir em um só lugar as informações por palavra dos documentos correspondentes), além de dificultar a manutenção de informações por documento

Crawling e indexação iniciais (1998-1999)

• Crawling:
  • Sistema simples de crawling em batch: lista de URLs iniciais → crawl das páginas → extração de links e inclusão na fila → interrupção ao coletar páginas suficientes
  • Pontos a considerar: evitar sobrecarregar sites específicos, decidir a prioridade das páginas ainda não rastreadas (ex.: PageRank), gerenciar eficientemente a fila de URLs não rastreadas, lidar com falhas de máquinas
• Indexação:
  • Sistema simples de indexação em batch baseado em ferramentas Unix simples
  • Problemas: falhas de máquina eram dolorosas pela ausência de checkpointing; ocorreram erros de bits de hardware por falta de checksums dos dados brutos (agravados pela ausência de ECC/paridade nas máquinas iniciais, gerando o problema de “majoritariamente ordenado”); experiência de “memória adversária e programação”
  • Solução: desenvolvimento de uma abstração de arquivo capaz de armazenar checksums de pequenos registros e pular registros corrompidos/re-sincronizar

Forma de atualização do índice (1998-1999)

• Periodicidade: cerca de uma vez por mês
• Processo:
  1. Esperar o horário de menor tráfego
  2. Colocar algumas réplicas offline
  3. Copiar o novo índice para as réplicas offline
  4. Iniciar um novo frontend apontando para o índice atualizado e direcionar parte do tráfego para ele
• Estratégia de uso de disco dos servidores de índice:
  • A parte externa do disco (outer part) oferece maior largura de banda
  1. (Enquanto o índice antigo continua em serviço) copiar o novo índice para a parte interna do disco (inner half)
  2. Reiniciar para usar o novo índice
  3. Excluir o índice antigo
  4. Copiar novamente o novo índice para a metade externa mais rápida (faster half)
  5. Excluir a primeira cópia do novo índice feita na parte interna
  6. Usar o espaço interno liberado para estruturas de dados que melhoram o desempenho (ex.: Pair cache - pré-cálculo do resultado da interseção de listas de postings para pares de termos de consulta que aparecem com frequência juntos)

Reação ao crescimento e expansão (1999-2001)

• Em '99, '00 e '01, o tamanho do índice e o tráfego cresceram rapidamente (~50 milhões → mais de 1 bilhão de páginas, crescimento de tráfego de 20% ao mês + parceria com o Yahoo dobrando o tráfego da noite para o dia etc.)
• O desempenho dos servidores de índice tornou-se extremamente importante: expansão contínua do número de máquinas + necessidade de melhorias de desempenho via software de 10-30% por mês
• Forma de expansão: adição de mais shards (Shards) e réplicas (Replicas)
• Implicações:
  • O tempo de resposta de um shard é afetado pelo número de seeks de disco e pelo volume de dados que precisa ser lido
  • Áreas com potencial de melhoria de desempenho: melhor escalonamento de disco, codificação de índice aprimorada

Evolução das técnicas de codificação de índice

• Codificação inicial ('97): formato muito simples alinhado por byte (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). O hit contém posição + atributos (tamanho da fonte, título etc.). Tabelas de skip foram adicionadas para listas de postings grandes. A decodificação era barata, mas a taxa de compressão era baixa, exigindo muita largura de banda de disco.
• Diversas técnicas de codificação:
  • Nível de bit: Unary, Gamma, Rice_k (caso especial de código de Golomb), Huffman-Int
  • Alinhado por byte: varint (7 bits por byte + bit de continuidade)
• Formato de índice baseado em blocos: redução tanto de espaço quanto de uso de CPU (~30% menor), com ganho de velocidade de decodificação. Uso de blocos de tamanho variável. Cabeçalho (delta, comprimento etc.) + deltas de ID de documento (Rice_k) + número de hits (Gamma) + atributos dos hits (run-length Huffman) + posições dos hits (Huffman-Int).
• Novo formato de índice (após 2004): uso de um único espaço plano de posições. Estruturas auxiliares acompanham os limites dos documentos. As listas de postings são listas de posições codificadas por delta. Tanto a compacidade quanto a decodificação muito rápida são importantes.

Sistema de índice em memória (início de 2001)

• Contexto: a expansão por sharding + aumento das réplicas permitiu acumular memória total suficiente para manter cópias do índice inteiro em memória
• Arquitetura: frontend → balanceador de carga (bal) → shard (com várias réplicas de servidores de índice em memória por shard)
• Vantagens: grande aumento de throughput e forte redução de latência (especialmente para consultas complexas que antes exigiam I/O de disco na casa de GB, como “circle of life”)
• Problemas:
  • Variância (Variance): usar milhares de máquinas em vez de dezenas aumenta a imprevisibilidade (ex.: jobs cron aleatórios causando problemas)
  • Disponibilidade (Availability): cada dado de índice de documento tinha apenas 1 ou poucas réplicas → “consulta da morte” (queda simultânea de todos os backends), além de problemas de disponibilidade dos dados de índice em caso de falha de máquina (principalmente para documentos importantes, que precisam de replicação)

Projeto de sistema posterior e tecnologias (após 2004)

• Hardware: data centers maiores, racks de projeto próprio, placas-mãe de classe PC, hardware barato de armazenamento/rede, Linux + software desenvolvido internamente
• Design de serving (edição 2004): estrutura hierárquica
  • Servidor Root → servidores Parent → servidores Leaf (carregando Repository Shard a partir do GFS via File Loader)
  • Integração com servidores de cache

Codificação Group Varint

• Ideia: resolver a ineficiência da decodificação de Varint (muitas operações de branch/shift/mask). Agrupa 4 valores inteiros e os codifica em 5~17 bytes.
• Método:
  • Reúne 4 tags de 2 bits, cada uma indicando o comprimento em bytes (1~4 bytes) de cada valor, para gerar 1 byte de prefixo (prefix)
  • Após o byte de prefixo, são armazenados os bytes reais dos dados
• Decodificação: lê-se o byte de prefixo e ele é usado como índice em uma tabela pré-calculada de 256 entradas → obtêm-se offsets e máscaras para decodificar os 4 valores de uma vez
• Desempenho: muito mais rápido que os métodos anteriores (Group Varint: ~400M/s, 7-bit Varint: ~180M/s, 30-bit Varint w/ 2-bit len: ~240M/s)

Busca universal (2007)

• Sistema que integra e apresenta não apenas resultados de busca na web, mas também vários tipos de informação (imagens, informações locais, notícias, vídeos, blogs, livros etc.).
• Um nó super root envia consultas para vários sistemas de busca especializados (motores de busca verticais) e agrega os resultados.

Desafios do crawling e da indexação de baixa latência

• Refletir atualizações em poucos minutos é um desafio muito difícil.
• Heurísticas de crawling: quais páginas devem ser rastreadas?
• Sistema de crawling: é preciso rastrear as páginas rapidamente.
• Sistema de indexação: depende de dados globais como PageRank, texto-âncora etc. → exige aproximação online em tempo real.
• Sistema de serving: precisa estar preparado para aceitar atualizações durante o processamento das consultas (o que exige estruturas de dados muito diferentes de um sistema de atualização em batch).

Importância da experimentação e da infraestrutura

• Facilidade para experimentar: extremamente importante (ciclos rápidos de experimentação → mais experimentos → mais melhorias).
• Tipos de experimento:
  • Experimentos fáceis: ajuste de pesos sobre dados existentes etc.
  • Experimentos difíceis: exigem novos dados que não existem no índice de produção. (É preciso que gerar/integrar novos dados e usá-los em experimentos seja fácil.)
• Infraestrutura central:
  • GFS: sistema de arquivos distribuído em larga escala
  • MapReduce: facilita escrever/executar tarefas de processamento de dados em larga escala. (Acelera a geração dos dados do índice de produção e a execução rápida de experimentos temporários.)
  • BigTable: sistema de armazenamento semi-estruturado. (Permite acesso online/eficiente a informações por documento e possibilita que vários processos atualizem informações de documentos de forma assíncrona — algo importante para passar de atualizações em horas para atualizações em minutos.)

Ciclo de experimentação e lançamento

1. Concepção da ideia e experimentos offline:
   • Geração de dados com MapReduce, BigTable etc.
   • Execução de experimentos offline e verificação dos efeitos (conjuntos de consultas com avaliação humana, conjuntos aleatórios de consultas etc.)
   • Nesta etapa, a latência/throughput do protótipo não é importante.
   • Melhorias iterativas com base nos resultados dos experimentos.
2. Experimentos em produção:
   • Se os resultados offline forem bons, realiza-se um experimento em produção com uma pequena fração real de tráfego de usuários (tiny sliver), em geral com amostra aleatória e, às vezes, focado em uma classe específica de consultas.
   • Nesta etapa, a latência é mais importante que o throughput! O framework de experimentação deve se comportar de forma próxima à latência do ambiente de produção.
3. Ajuste de desempenho e lançamento:
   • Se os resultados do experimento em produção forem bons, faz-se tuning/reimplementação para permitir execução sob carga total (ex.: pré-cálculo de dados em vez de cálculo em tempo de execução; uso de aproximações mais baratas quando “bom o suficiente”).
   • O processo de lançamento (Rollout) é importante: é preciso considerar continuamente o trade-off entre qualidade e custo, equilibrando rapidez no lançamento com baixa latência/estabilidade do site (é necessária boa colaboração entre a equipe de qualidade de busca e a equipe responsável por desempenho/estabilidade).

Direções futuras e desafios

• Recuperação de informação multilíngue (Cross-Language IR): traduzir todos os documentos do mundo para todos os idiomas → enorme aumento do tamanho do índice e alto custo computacional. (Melhoria contínua da qualidade da tradução e necessidade de sistemas em larga escala para lidar com modelos de linguagem maiores e mais complexos.)
• Listas de controle de acesso (ACLs) dentro de sistemas de recuperação de informação: ambiente misto de documentos privados/semiprivados/amplamente compartilhados/públicos. (É preciso construir um sistema que trate ACLs de tamanhos muito diferentes com eficiência — a solução ótima para um documento compartilhado com 10 pessoas não é a mesma de um documento compartilhado com o mundo inteiro, e os padrões de compartilhamento podem mudar ao longo do tempo.)
• Construção automática de sistemas de IR eficientes: hoje são usados vários sistemas voltados a finalidades distintas (para atualizações ultrarrápidas, para volume gigantesco de documentos etc.). (Seria possível desenvolver um único sistema capaz de construir automaticamente um sistema de busca eficiente de acordo com os requisitos informados como parâmetros?)
• Extração de informação a partir de dados semi-estruturados: há pouquíssimos dados com rótulos semânticos claros. Tabelas, formulários e outros dados semi-estruturados são abundantes. (São necessários melhores algoritmos/técnicas para extrair informação estruturada de fontes não estruturadas/semi-estruturadas — apesar do ruído, aproveitando redundância e a capacidade de relacionar/combinar/agregar informações de várias fontes.)

Conclusão

• Projetar e construir sistemas de recuperação de informação em larga escala é um trabalho desafiador e interessante.
• Novas tecnologias de busca frequentemente exigem novos projetos de sistema.