Ranking de jogo em tempo real

01 · CONTEXTO E REQUISITOS

O que é um ranking em tempo real

Em um ranking de jogo, cada jogador acumula pontos e quem tem mais pontos fica no topo. No cenário do livro da ByteByteGo, o jogador ganha um ponto a cada partida vencida e, a cada mês, um novo torneio começa com um novo ranking. O blog de banco de dados da AWS descreve o ranking como um recurso social em que os jogadores comparam seu desempenho.

Os requisitos funcionais são mostrar os 10 melhores jogadores e a posição de um usuário específico; como bônus, mostrar os jogadores quatro posições acima e abaixo dele. O requisito não funcional central é a atualização em tempo real, pois não se aceita um histórico em lote. Se dois jogadores têm a mesma pontuação, ficam na mesma posição.

02 · ESTIMATIVA DE ESCALA

Contas de guardanapo

O enunciado do livro fala em 5 milhões de usuários ativos por dia e 25 milhões por mês, com cada jogador disputando em média 10 partidas por dia.

Espalhando os 5 milhões de usuários ao longo do dia, dá cerca de 50 usuários por segundo. Com as partidas, são cerca de 500 pontos por segundo na média e, com pico de cinco vezes a média, 2.500 por segundo. Já a consulta do top 10 fica em torno de 50 por segundo, porque o livro supõe que o jogador abre o jogo uma vez por dia e só então carrega o ranking.

03 · API E PRIMEIRA TENTATIVA

Começando pelo banco relacional

O livro propõe três rotas de API: uma para atualizar a pontuação, uma para buscar o topo e uma para buscar a posição de um usuário. A de atualização é interna, chamada só pelos servidores de jogo, porque deixar o cliente definir a pontuação não é seguro, pois fica sujeito a ataque man-in-the-middle.

Quando o jogador vence, o cliente avisa o serviço de jogo, que confere se a vitória é válida e chama o serviço de ranking para atualizar a pontuação.

A solução mais simples é uma tabela relacional com usuário e pontuação: cada vitória soma um ponto e a posição vem de ordenar a tabela pela pontuação, em ordem decrescente.

1. O jogador vence uma partida e o cliente avisa o serviço de jogo.

2. O serviço de jogo valida a vitória e chama o serviço de ranking.

3. O serviço de ranking incrementa a pontuação do usuário na tabela.

4. Para mostrar a posição, o serviço de ranking precisa ordenar os jogadores da tabela, o que fica lento com milhões de linhas.

O problema aparece com milhões de linhas: segundo o livro, uma operação de posição leva dezenas de segundos, o que é inaceitável para tempo real, e como os dados mudam o tempo todo o cache não é viável. Mesmo com índice e LIMIT, achar a posição de um usuário exige varrer a tabela. O blog de banco de dados da AWS cita 35 segundos em média numa tabela com 50 milhões de registros, mesmo com índices. Um banco relacional serviria em lote, mas isso não atende ao tempo real.

04 · SORTED SETS DO REDIS

Um ranking que já nasce ordenado

O Redis guarda tudo em memória, o que permite leituras e escritas rápidas. Sua estrutura de dados para esse caso é o sorted set: uma coleção de strings únicas, os membros, ordenadas por uma pontuação associada. As pontuações podem se repetir e, quando isso acontece, a documentação diz que as strings são ordenadas lexicograficamente. A própria documentação cita rankings de jogos online como caso de uso e descreve o uso típico como combinar os melhores usuários com a posição do usuário no ranking.

Por dentro, o livro descreve uma tabela hash e uma skip list: a hash liga usuários a pontuações e a skip list liga pontuações a usuários. A documentação do Redis descreve a mesma ideia e diz que cada elemento adicionado custa uma operação logarítmica; atualizar a pontuação de um elemento existente também. O blog da AWS resume a diferença para o banco relacional: o sorted set posiciona o item na ordem certa já na inserção ou atualização, e encontra posições de forma logarítmica, enquanto o banco relacional ordena durante a consulta.

Todo mês cria-se um novo sorted set e os anteriores vão para armazenamento histórico. O livro calcula que, no pior caso, o ranking ocupa cerca de 650 MB no Redis e que, mesmo dobrando esse valor pela sobrecarga, um servidor Redis moderno é mais que suficiente; o pico de 2.500 escritas por segundo também fica dentro da capacidade de um único servidor.

Sobre durabilidade: o Redis tem persistência, mas reiniciar uma instância grande a partir do disco é lento. Costuma-se também configurar uma réplica de leitura, promovida quando a principal falha. Nome e foto dos usuários ficam em MySQL, e os pontos registrados ali podem recriar o ranking após uma falha de infraestrutura.

1. Com a vitória validada, o serviço de ranking incrementa a pontuação do jogador no sorted set do mês com ZINCRBY.

2. Para o topo do ranking, o serviço lê o sorted set em ordem decrescente com ZREVRANGE, sem precisar ordenar nada na hora.

3. Para a posição de um jogador, o serviço chama ZREVRANK.

4. Nomes e fotos vêm do MySQL e são juntados ao resultado.

5. Se o Redis principal falhar, a réplica é promovida e uma nova réplica é anexada.

6. Se o Redis for perdido por completo, os pontos registrados no MySQL permitem recriar o ranking.

05 · ESCALAR E ALTERNATIVAS

Sharding e NoSQL

Com 5 milhões de usuários por dia, um Redis basta. O livro imagina então uma escala cem vezes maior, com 500 milhões por dia, em que o pior caso passa a 65 GB e 250.000 consultas por segundo, o que pede sharding.

Na partição fixa, divide-se o ranking por faixas de pontuação, por exemplo dez shards de cem pontos cada, e o sharding é feito no código da aplicação. Isso exige que as pontuações se distribuam de forma uniforme entre as faixas. Para saber em que faixa o usuário está, uma opção mais rápida é um cache secundário com o mapeamento de usuário para pontuação, e quando ele muda de faixa é preciso removê-lo do shard atual e movê-lo para o novo.

1. Cada shard guarda o sorted set de uma faixa de pontuação, e a aplicação decide a qual shard falar.

2. Ao somar pontos, o serviço descobre em que shard o usuário está usando o mapa de usuário para pontuação.

3. Se a pontuação cruza uma faixa, o usuário sai de um shard e entra no seguinte, como de um shard de pontuação menor para um intermediário.

4. O topo do ranking vem do shard das maiores pontuações.

5. A posição de um usuário soma o rank local no shard dele ao total de jogadores com pontuação maior nos outros shards.

A alternativa é o Redis Cluster, que divide as chaves automaticamente em 16384 hash slots. O top 10 passa a exigir reunir o top 10 de cada shard e ordenar na aplicação; com muitas partições a latência sobe, porque a consulta espera a mais lenta, e não há solução direta para a posição de um usuário. Por isso o livro opta pela partição fixa. Na AWS, o ElastiCache for Redis em modo cluster adiciona shards para escalar escrita e réplicas de leitura para escalar leitura.

Outra alternativa é um NoSQL otimizado para escrita e capaz de ordenar itens por pontuação dentro da partição: o livro cita DynamoDB, Cassandra ou MongoDB. Se a chave de partição for só jogo e mês, os dados do mês recente caem numa partição quente. A saída é o write sharding, que espalha o mês em várias partições ao custo de complicar leitura e escrita, pois para ler o mês é preciso consultar todas as partições e juntar os resultados.

06 · FECHAMENTO

Empate, falhas e quando escolher o quê

Para desempate, o livro sugere guardar o timestamp da vitória mais recente de cada usuário: em caso de empate, quem tem o timestamp mais antigo fica à frente. Um hash do Redis com o objeto do usuário evita ir ao banco buscar nome e foto. Se o Redis todo for perdido, dá para recriar o ranking chamando ZINCRBY uma vez por registro de cada usuário.

O ponto de partida do livro é um único sorted set, que cobre a escala inicial; o sharding só entra quando o tamanho e as consultas passam do que um servidor suporta.