Warcraft Rumble

Por dentro de Warcraft Rumble: Calculando a experiência das minis

Por dentro de Warcraft Rumble: Calculando a experiência das minis

Saudações, fãs do caos!

Sou Andy Lim, engenheiro-chefe de recursos do servidor de Warcraft Rumble. A equipe que cuida do servidor é responsável por todo tipo de coisas que seriam esperadas de uma equipe assim, incluindo gestão de redes, computação em nuvem e armazenamento, mas também desenvolvemos recursos do jogo, como progressão de campanhas e missões. Eu gostaria de compartilhar um pouco mais com vocês sobre como armazenamos a experiência e a usamos para calcular o nível de cada mini.


Conheçam Cassandra

Alerta: detalhes técnicos a seguir! Pode ficar um pouco complicado, mas permaneça conosco.

Vamos começar aprendendo um pouco sobre a solução de armazenamento que usamos para monitorar as alterações frequentes nos dados dos jogadores com tantos usuários simultâneos: Cassandra. Cassandra é um popular e altamente redimensionável banco de dados distribuído de código aberto que nos dá o equilíbrio correto entre consistência e disponibilidade de dados. Quanto aos dados em si, Cassandra lida bem com conjuntos de dados amplos sem forçar um schema rígido. Criamos ferramentas que permitem aos engenheiros definir nossas tabelas de banco de dados e o schema da tabela conforme a necessidade de cada recurso, dando-nos alguma flexibilidade para estrutura e organização conforme desejado. Podemos facilmente escrever e validar nosso schema e consultas.

O que é um schema? Um schema de base de dados define como os dados são organizados em uma base de dados relacional, como os que você encontra em gráficos.


Armazenando experiência como uma operação contábil

Cassandra é conhecido por ser muito rápido em gravar dados, mas lento em lê-los. A atualização de dados no local geralmente é uma operação de leitura e gravação e, portanto, também seria lenta. Para contornar isso, projetamos os dados dos nossos jogadores de forma a serem armazenados como em um livro-razão. Nele, você escreve cada linha como uma alteração e, lendo-o, têm-se todas as entradas para calculá-las.

Um bom exemplo dessa dinâmica é o seu cartão de crédito. Cada transação é escrita como uma única entrada de valor positivo ou negativo. Cada vez que você o utiliza, há uma transação com valor negativo; cada vez que você paga, há uma transação avaliada positivamente. Como você sabe quanto deve? É preciso olhar para o registro inteiro e adicionar/subtrair cada valor.

Pense nos dados locais como tendo uma única coisa que você possa armazenar. Sempre que quiser alterar esse valor, você deve lê-lo, fazer a alteração e, em seguida, escrever qual é o novo valor. Portanto, se for um placar de futebol, sempre que um time marcar um gol, você deve fazer uma leitura para ver qual foi o último total, adicionar o novo gol e anotá-lo novamente no placar.

Um exemplo concreto vindo de Arclight é a contabilidade da experiência de cada mini. Sempre após uma missão, uma fileira é adicionada ao livro-razão de cada mini, indicando a quantidade de experiência recebida por aquela mini. Após cinco missões, as entradas devem ser mais ou menos assim:

Tabela 1

Jogador

Mini

Valor

Hora

Andy

Brutamontes Gnoll

3

14h de segunda-feira

Andy

Cavalga-Grifo

3

14h05 de segunda-feira

Andy

Brutamontes Gnoll

3

14h10 de segunda-feira

Andy

Piloto da V.E.R.A.

3

14h15 de segunda-feira

Andy

Brutamontes Gnoll

3

14h20 de segunda-feira

Por fim, para obter a experiência total das minis, simplesmente recuperamos todas essas as entradas, agrupamos de acordo com cada mini e adicionamos os valores de experiência. O resultado ficaria assim:

Tabela 2

Jogador

Mini

Total

Andy

Brutamontes Gnoll

9

Andy

Cavalga-Grifo

3

Andy

Piloto da V.E.R.A.

3


Concluindo o processo de pacotes cumulativos

Agora que estabelecemos como armazenamos experiência, vejamos como podemos refinar os cálculos que precisam ser feitos para cada mini. Armazenar linhas individuais para o ganho de experiência de cada mini seria volumoso demais para ser lido integralmente. Haveria linhas demais e a tabela cresceria indefinidamente... PARA SEMPRE. Digamos que seu dia típico jogando Rumble envolva uma combinação de 15 missões ou partidas JxJ, mais 20 partidas intensificadas por semana em busca de ouro e uma sessão de masmorra semanalmente para dar aquela aprimorada no exército. Isso daria 100 entradas por semana. Após cerca de 3 meses de jogo, teríamos algo como 1.260 entradas para contabilizar. Agora, para calcular seus totais, teríamos que recuperá-los por meio do sistema Cassandra, de leituras lentas.Ouch.

Criamos uma solução para isso: pacotes cumulativos. Um pacote cumulativo é um cálculo para valores até um ponto no tempo. Nesse caso, adicionamos todos eles e os representamos em uma única linha. Vamos armazenar isso em uma segunda tabela. Agora dá para entender a utilidade de registrar os horários. Para a experiência, a chave será o jogador e a mini, e o cálculo é uma soma.  Vamos preparar um pacote cumulativo para todas as entradas contabilizadas até terça-feira ao meio-dia e armazenar os resultados em uma segunda tabela do Cassandra. As entradas podem ter esta aparência:

Tabela 3

Jogador

Mini

Total

Data final

Andy

Brutamontes Gnoll

9

12h de terça-feira

Andy

Cavalga-Grifo

3

12h de terça-feira

Andy

Piloto da V.E.R.A.

3

12h de terça-feira

Você joga mais partidas na quarta-feira e gera mais entradas de experiência. A tabela original de experiência terá crescido.

Tabela 4

Jogador

Mini

Valor

Hora

Andy

Brutamontes Gnoll

3

14h de segunda-feira

Andy

Cavalga-Grifo

3

14h05 de segunda-feira

Andy

Brutamontes Gnoll

3

14h10 de segunda-feira

Andy

Piloto da V.E.R.A.

3

14h15 de segunda-feira

Andy

Brutamontes Gnoll

3

14h20 de segunda-feira

Andy

Piloto da V.E.R.A.

3

12h de quarta-feira

Andy

Cadeia de Raios

3

12h05 de quarta-feira

Andy

Cavalga-Grifo

3

12h10 de quarta-feira

Agora, queremos fazer uma pesquisa completa e recalcular quais são os níveis reais da mini depois de jogar essas partidas. Consultamos ambas as tabelas (a de pacote cumulativo para a entrada única e a contabilidade das entradas após aquele ponto no tempo) e somamos os valores para obter uma tabela de experiência total final. Portanto, lemos a Tabela 3 e, em seguida, consultamos a Tabela 4 apenas para saber que dados surgiram após cada linha da Tabela 3. Aqui está uma lista das etapas que teríamos:

  1. Ler uma linha da Tabela 3
     

Cavalga-Grifo

3

12h de terça-feira

  1. Ler linhas da Tabela 3 sobre o Cavalga-Grifo após a meia-noite de terça-feira
     

Cavalga-Grifo

3

12h10 de quarta-feira

  1. Agora somamos ambos os conjuntos de dados para gerar um total de:

Cavalga-Grifo

6

Você pode perceber que essa abordagem causaria um curto-circuito em algumas das leituras da Tabela 4.

Você pode pensar que deveríamos armazenar apenas os dados recém-calculados depois de armazenar uma nova entrada na contabilidade. Em teoria, isso pode parecer bom, mas resultaria em dados inconsistentes e desempenho reduzido. Um exemplo de desempenho reduzido é que o sistema estaria ocupado recalculando e armazenando dados, geralmente devido à necessidade de ler e então gravar. Precisamos equilibrar o cálculo aqui enquanto executamos o jogo com um desempenho adequado para todos os jogadores.

Um exemplo de dados inconsistentes é lidar com os cálculos de fim de partida. Nossa infraestrutura de servidor e plataforma suportam mensagens atrasadas. Um exemplo é um problema temporal em duas centrais de processamentos de dados (A e B), e a mensagem para dar a um jogador a experiência da mini é enviada de A, mas ainda não chegou a B. Imagine este cenário: você está jogando uma partida pouco antes da meia-noite. Você joga e vence, são 23h59 de uma quarta-feira. O processador de pacote cumulativo foi configurado para executar diariamente todos os dados de cada dia. Então, ele começaria à meia-noite e calcularia seus valores totais de experiência até a meia-noite de quinta-feira. Esses dados seriam armazenados na segunda tabela e novas leituras da experiência procurariam o último valor armazenado e somariam tudo após a meia-noite de quinta-feira. O que acontece com uma mensagem que chega atrasada é que nós a recebemos, mas notamos que a partida foi concluída na quarta-feira às  23h59 e escrevemos a entrada da experiência com esse horário. A tabela de pacotes cumulativos não teria essa entrada incluída, e a consulta de dados posteriores também não mostraria essa entrada. Esses dados incompletos seriam um problema. E as mensagens que chegam com alguns dias de atraso? Bem, temos monitoramento e alertas em vigor que quase sempre garantem que essas novas informações serão processadas a tempo para o próximo pacote cumulativo.


Calculando níveis das minis

Olhando novamente a tabela de experiência total, você notará que não há níveis calculados lá. Temos apenas um total da quantidade de experiência já adquirida. Separadamente, há uma tabela estática que os designers de jogo definiram e que é mais ou menos assim: uma mini começa no nível 1 e, uma vez que ela ganha 1 ponto de experiência, será nível 2 e, então, precisará ganhar 3 pontos para chegar ao nível 3.

 Nível

Quantidade até o próximo nível

1

1

2

3

3

6

4

10

5

20

10

250

Combinando as duas, podemos calcular no tempo de execução qual é o nível real de uma mini por meio de um total acumulado, obtendo, assim, o seguinte conjunto de dados:

Mini

Nível

Exp

Quantidade até o próximo nível

Brutamontes Gnoll

3

5

1

Cavalga-Grifo

3

2

4

Piloto da V.E.R.A.

3

2

4

Cadeia de Raios

2

2

1

Os designers do jogo têm flexibilidade para alterar quanta experiência é necessária para ganhar um nível. Eles podem decidir que está muito difícil subir de nível nos níveis mais baixos e diminuir a quantidade de experiência necessária para chegar ao próximo nível. Isso significaria que, sem fazer nenhuma alteração nos dados do jogador salvos no banco de dados, todas as minis teriam um leve aumento em seu nível atual e precisariam de menos para chegar ao próximo nível. Isso também vale na outra ponta: se for decidido que os níveis estão sendo alcançados muito rapidamente e os valores forem aumentados, não iremos simplesmente gerar uma experiência a fim de restaurar os níveis das minis anteriores à mudança. Isso não quer dizer que não podemos dar aos designers a opção de conceder alguma experiência às minis para ajudar a amenizar a situação.


Abordagens alternativas que foram consideradas

Antes de usar a solução que temos atualmente, nós analisamos várias abordagens sobre como armazenar os ganhos de experiência e calcular o nível resultante para as minis. Algumas envolviam um tempo extra fora do ar que nos permitiria alterar a experiência de um jogador, enquanto outras ofereciam uma boa experiência simultaneamente à progressão de um jogador.

"Sempre armazenar o nível, a experiência e a quantidade necessária ao próximo nível da mini"

Que tal usarmos apenas um modelo SQL padrão e atualizações transacionais? Elas permitem que você atualize um conjunto de dados em sua totalidade, tipo tudo ou nada. Se uma parte não for gravada, todas serão revertidas ao valor original. Elas fornecem as propriedades A.C.I.D.: atomicidade, consistência, isolamento e durabilidade.

Isso usaria uma única linha para manter a experiência e o nível total de cada mini, tornando as leituras realmente leves.

À medida que cada mini ganha experiência, atualize esta mini em 2 pontos de experiência, faltando 8 pontos para o próximo nível, sendo o atual igual a 3. Esse tipo de alteração força uma leitura dos dados, um novo cálculo e, em seguida, uma gravação no banco de dados. Esse padrão não casa bem com Cassandra e seus pontos fortes. Outro problema com essa abordagem é que alterar as quantidades necessárias para o próximo nível exigiria colocar o jogo offline para modificarmos os dados de todas as minis de todos os jogadores.

"Armazene em forma percentual"

Nós também cogitamos armazenar em forma de porcentagem o necessário para o próximo nível. Por exemplo:

Mini

Nível

Para o próximo nível

Brutamontes Gnoll

3

20%

Cavalga-Grifo

2

20%

Piloto da V.E.R.A.

2

20%

E, então, após uma partida, faríamos alguns cálculos rápidos. Por exemplo: o Brutamontes Gnoll recebe +3 de exp., a porcentagem é +3 / 10; vamos dar ao Brutamontes Gnoll 30% de um nível, resultando em:

Mini

Nível

Para o próximo nível

Brutamontes Gnoll

3

50%

Cavalga-Grifo

2

20%

Piloto da V.E.R.A.

2

20%

Isso nos daria flexibilidade se alterássemos a curva de nível da mini, mas não resultaria em nenhuma alteração de nível para a mini. Isso também nos proporcionaria algumas visualizações mais simples na interface do usuário do jogo, pois diríamos apenas para preencher 30% da barra, sem necessidade de matemática adicional. No entanto, esse tipo de padrão resultaria em porcentagens muito pequenas nos níveis mais altos. Quando uma mini recebe 10 pontos de experiência por jogo e precisa de 100.000 para subir de nível, esse valor seria representado em 0,01%. As unidades centrais de processamento (CPUs) podem lidar com flutuações, mas precisão e exatidão podem causar bugs se não levarmos em conta a natureza da matemática de vírgula flutuante.


Até mais...

Muitas opções foram consideradas no âmbito da tecnologia de banco de dados, quais ferramentas poderiam ser fornecidas e, finalmente, como armazenar e calcular as coisas. Como acontece com qualquer coisa ainda em desenvolvimento, podemos mudar tudo isso mais tarde se encontrarmos algo que funcione ainda melhor, mas esse pareceu um bom ponto de partida para este jogo.

Obrigado por se juntar a nós nesta atualização da engenharia!

~ Andy Lim

Aliás, quero registrar oficialmente que eu não sou o bandido dos olhos esbugalhados. No meu primeiro dia nesta equipe, o bandido marcou os meus monitores novinhos em folha. Eles ficam me encarando o dia todo... o dia… todo. 

Próximo artigo

Destaques