Conceitos
Busca: shards de índice, réplicas e scatter-gather
Intuição
Imagine uma biblioteca tão grande que nenhum bibliotecário consegue vasculhar tudo sozinho em tempo razoável. Você divide o acervo em várias seções, e cada seção tem vários bibliotecários idênticos. Quando chega uma pergunta, ela é entregue ao mesmo tempo a um bibliotecário de cada seção; cada um procura só na sua parte e, no final, alguém junta as respostas parciais numa lista só. Se um bibliotecário adoece, outro da mesma seção atende no lugar, e ninguém precisa interromper a biblioteca.
Como funciona
Segundo Barroso, Dean e Hölzle, os documentos e o índice invertido derivado deles somam muitos terabytes, então o índice é dividido em index shards, cada um com um subconjunto escolhido aleatoriamente dos documentos. Para cada shard existe um pool de máquinas réplicas, e o cluster de índice tem um pool por shard. Uma consulta é atendida por um servidor web (GWS) que a envia, via balanceador de carga, a uma máquina de cada pool. Cada shard consulta o índice invertido, intersecta as listas de documentos das palavras e calcula a relevância apenas sobre o seu subconjunto. Os resultados parciais são combinados numa lista ordenada de identificadores de documento (docids). Em seguida, os servidores de documentos, que usam o mesmo esquema de shards aleatórios com várias réplicas e balanceador, buscam em disco título, URL e o trecho com a palavra-chave em contexto. Como os shards não precisam se comunicar entre si, o ganho de velocidade ao paralelizar é quase linear e a latência média cai. Os dois eixos de crescimento são independentes: mais máquinas por pool aumentam a capacidade de atendimento, e mais shards acomodam um índice maior. Se uma réplica cai, o balanceador evita usá-la, o gerenciamento do cluster tenta reavivá-la ou substituí-la, a capacidade cai na proporção da fatia perdida e todas as partes do índice continuam disponíveis. Isso funciona porque o acesso é majoritariamente de leitura, com atualizações raras feitas desviando consultas da réplica.
Na prática
O mesmo desenho aparece em sistemas de busca que dividem um índice grande em partições replicadas e combinam os resultados parciais. Você o escolhe quando a carga é de leitura e o índice não cabe numa máquina, e quando quer escalar capacidade e tamanho do índice separadamente. O artigo mostra que ele permite construir a confiabilidade no software, com réplicas em PCs comuns e sem hardware tolerante a falhas, e aumentar o número de shards para compensar CPUs mais lentas. Este conceito trata de como o índice é particionado e replicado. O efeito de esperar o shard mais lento num fan-out amplo e as técnicas de hedging para contê-lo são tratados à parte, em concept_tail_latency_fanout e concept_hedged_tied_requests.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.