Inside Warcraft Rumble: Calculating Mini Experience
Greetings Rumblers!
I'm Andy Lim, Lead Engineer on server features for Warcraft Rumble. The server team is responsible for all the things you'd expect from a server team, including networking, cloud computing, and storage, but we also build game features such as campaign progression and quests. I'd like to peel back the blue curtain and share a bit more about how we store experience and then use it to calculate levels for each Mini.
Meet Cassandra
Warning! Technical details ahead; it could get a little heavy, but stick with us.
Let’s kick things off by getting to know a bit about our storage solution we use to keep track of the frequent changes to our player data for a lot of concurrent users—Cassandra. Cassandra is an open-source, popular, highly scalable, distributed database and gives us the right balance of data consistency and availability. For the data itself, Cassandra deals well with wide data sets without forcing a hard schema. We have built tooling that enables engineers to define our database tables and the table schema as each feature needs it, giving us some flexibility for structure and organization as desired. We can easily write and validate our schema and queries.
What’s a Schema? A database schema defines how data is organized within a relational database, such as what you find in tables.
Storing Experience as a Ledger
Cassandra is well known to be very fast at writing data but slow at reading it. Updating in place data is often a read-and-then-write operation, so that would be slow also. To get around that, we designed our player data to be stored as a ledger. In a ledger, you write each line as a change, and when you read it, you read all the entries and then do some calculations on it.
A good example of a ledger is something like your credit card. Each transaction is written as a single entry of positive or negative value. Each time you use it, there’s a negatively valued transaction; each time you pay it, there’s a positively valued transaction. How do you know how much you owe? You must look at the entire ledger and add/subtract each value.
Think of in place data as having a single thing you can store. Any time you want to change that value, you must read it, make the change, then write what the new value is. So, if this is a soccer scoreline, any time a team scores, you must do a read to see what the last total was, add the new goal, and then write it back into the scoreline.
A concrete example for Arclight is the experience ledger for each Mini. After each mission, a row will be added to the ledger for a single Mini, indicating the amount of experience gained by that Mini. After five missions, you might have entries that look like this:
Table 1
|
Player |
Mini |
Value |
Time |
|---|---|---|---|
|
Andy |
Gnoll Brute |
3 |
Monday 2:00 pm |
|
Andy |
Gryphon Rider |
3 |
Monday 2:05 pm |
|
Andy |
Gnoll Brute |
3 |
Monday 2:10 pm |
|
Andy |
S.A.F.E. Pilot |
3 |
Monday 2:15 pm |
|
Andy |
Gnoll Brute |
3 |
Monday 2:20 pm |
Finally, to get to the total Mini experience, we simply retrieve all those ledger entries, group them up by each Mini, and add the experience values. The result would look like this:
Table 2
|
Player |
Mini |
Total |
|---|---|---|
|
Andy |
Gnoll Brute |
9 |
|
Andy |
Gryphon Rider |
3 |
|
Andy |
S.A.F.E. Pilot |
3 |
Winding up the Rollups Process
Now that we’ve established how we store experience, let’s look at how we can refine the calculations that need to be done for each Mini. Storing individual rows for each Mini experience gain would be intense to read back out. There would be so many rows, and this table grows endlessly… FOREVER. Let's say that your typical day with Rumble is a combination of 15 quests or PVP, along with 20 Surges a week for Gold and a dungeon run weekly for that army upgrade. That would be 100 entries per week. After about 3 months of playing, you would have something like 1260 ledger entries. Now, to calculate your totals, we would have to retrieve them through Cassandra's system of slow reads. Ouch.
We've engineered a solution for that: rollups. A rollup is a calculation for values up to a point in time. In this case, we're adding them all together and representing them in a single row. We will store this in a second table. Now you can see where the timestamp can be useful. For experience, the key will be the player and Mini, and the calculation is a summation. Let's do a rollup for all the ledger entries until Tuesday at 12 am and store the results into a second Cassandra table. The entries might look like this:
Table 3
|
Player |
Mini |
Total |
EndDate |
|---|---|---|---|
|
Andy |
Gnoll Brute |
9 |
Tuesday 12 am |
|
Andy |
Gryphon Rider |
3 |
Tuesday 12 am |
|
Andy |
S.A.F.E. Pilot |
3 |
Tuesday 12 am |
You play more games on Wednesday and generate more exp entries. The original experience table would've grown.
Table 4
|
Player |
Mini |
Value |
Time |
|---|---|---|---|
|
Andy |
Gnoll Brute |
3 |
Monday 2:00 pm |
|
Andy |
Gryphon Rider |
3 |
Monday 2:05 pm |
|
Andy |
Gnoll Brute |
3 |
Monday 2:10 pm |
|
Andy |
S.A.F.E. Pilot |
3 |
Monday 2:15 pm |
|
Andy |
Gnoll Brute |
3 |
Monday 2:20 pm |
|
Andy |
S.A.F.E. Pilot |
3 |
Wednesday 12 pm |
|
Andy |
Chain Lightning |
3 |
Wednesday 12:05 pm |
|
Andy |
Gryphon Rider |
3 |
Wednesday 12:10 pm |
Now, we want to do a full lookup and recompute what the actual Mini levels are after playing these games. We query both tables— the rollup table for the single entry and the ledger for entries after that point in time— and sum up the values to have a final total experience table. So, we read Table 3 and then query Table 4 only for data that exists after each row for Table 3. Here's a list of steps that we would do:
- Read a row from Table 3
|
Gryphon Rider |
3 |
Tuesday 12 am |
- Read rows from Table 3 for Gryphon Rider after Tuesday 12 am
|
Gryphon Rider |
3 |
Wednesday 12:10 pm |
- Now we sum both data sets to generate a total of:
|
Gryphon Rider |
6 |
You can see how this approach would short-circuit quite a few of the reads from Table 4.
You might think that we should just store the newly calculated data after storing a new ledger entry. This may look good on paper, but it would result in data inconsistency and performance degradation. One example of possible performance degradation is that the system would be busily recomputing and storing data, often due to the need to read and then write. We need to balance the calculation here while we run the game at a suitable performance for all players.
One example of data inconsistency is dealing with the end-of-game calculations. Our server infrastructure and platform support late-arriving messages. An example is a transient issue across two data centers (A and B), and the message for giving a player Mini experience gets sent from A but hasn't arrived at B yet. Imagine this scenario: You're playing a game right before midnight. You play and win, and it’s Wednesday 11:59 pm. The rollup processor was configured to run daily for all data up to the current day. So, it would kick off at midnight and compute your total experience values up to Thursday at 12 am. That data would be stored in the second table, and new reads on experience would look for the last value stored and sum everything up after Thursday at 12 am. What happens with a late arriving message is that we get it but notice that the game was completed on Wednesday at 11:59 pm and write the experience entry with that time. The rollup table would not have had this entry included, and the query for later data also wouldn't show this entry. This incomplete data would be a problem. What about messages that arrive a few days late? Well, we have monitoring and alerting in place that almost always guarantees that this new information will get processed in time for the next rollup.
Calculating Mini Levels
Looking back at the total experience table, you will notice that there are no levels calculated there. We only have a total of the amount of experience ever gained. Separately, there is a static table that game designers have set that looks something like this. A Mini starts at level 1, and once it gains 1 point of experience, it will be level 2 and then needs to earn 3 points in order to get to level 3.
|
Level |
Amount To Next Level |
|---|---|
|
1 |
1 |
|
2 |
3 |
|
3 |
6 |
|
4 |
10 |
|
5 |
20 |
|
… |
… |
|
10 |
250 |
Combining the two lets us compute at runtime what the actual level of a Mini is by doing a running total, giving us this final data set:
|
Mini |
Level |
Exp |
Amount to Next Level |
|---|---|---|---|
|
Gnoll Brute |
3 |
5 |
1 |
|
Gryphon Rider |
3 |
2 |
4 |
|
S.A.F.E. Pilot |
3 |
2 |
4 |
|
Chain Lightning |
2 |
2 |
1 |
The game designers have the flexibility to change how much experience is needed to gain a level. They might decide that it's too hard to level up at low levels and decrease the amounts needed to get to the next level. This would mean that without making any changes to the player data saved in the database, the Minis would all get a slight bump up in their current level and have less needed to get to the next level. This also cuts the other way. If game designers decide the levels are too fast and increase the values, we won't be giving any makeup experience in order to restore Minis to the levels they had before the change. That's not to say we can't give design the option to grant some experience to Minis to help ease some of that pain.
Alternate Approaches Considered
Prior to using the solution we currently have, we looked at varying approaches on how to store experience gains and calculate the resulting level for Minis. Some would mean extra downtime that would allow us to alter a player’s experience, while others were just right in delivering a good experience while still keeping up with a player’s progression.
‘Always store Mini's level and xp and to next level’
How about we just use a standard SQL pattern and use transactional updates? Transactional updates allow you to update a set of data in its entirety, as all or none. If one part fails to write, they all will be rolled back to the original value. They give you the A.C.I.D. properties of atomicity, consistency, isolation, and durability.
This would use a single row to maintain each Mini's experience and total level, making reads super lightweight.
As each Mini gains experience, update this mini to 2 points of experience with 8 points to go, and it is level 3. This type of change forces a read on the data, a recompute, and then a write to the database. This pattern doesn't play nicely with Cassandra and its strengths. Another issue with this approach is that changing amounts needed to level would require taking the game offline for us to modify data for all Minis for all players.
‘Store it as a percentage’
We also thought about storing a percentage to the next level, for example:
|
Mini |
Level |
ToNextLevel |
|---|---|---|
|
Gnoll Brute |
3 |
20% |
|
Gryphon Rider |
2 |
20% |
|
S.A.F.E. Pilot |
2 |
20% |
Then after a game, we would do some quick calculations. For example, Gnoll Brute gets +3 exp, the percentage is +3 / 10; let's give Gnoll Brute 30% of a level, resulting in:
|
Mini |
Level |
ToNextLevel |
|---|---|---|
|
Gnoll Brute |
3 |
50% |
|
Gryphon Rider |
2 |
20% |
|
S.A.F.E. Pilot |
2 |
20% |
This would give us flexibility if we changed the Mini level curve but wouldn't result in any level changes for a Mini. This would also give us some easier visualizations in the game User Interface, as we'd just say fill up 30% of the bar, with no additional math needed. However, this kind of pattern would result in very small percentages at higher levels. When a Mini is granted 10 xp per game, and it requires 100,000 to level, that value would be represented at 0.01%. Central Processing Units (CPUs) can deal with floats, but precision and accuracy can introduce bugs if we don't account for the nature of floating-point math.
Until next time...
There were many options considered across the database tech, what tooling could be provided, and finally, how to store and calculate things. As with anything still in development, we might change all this later if we find something that works even better, but this seemed like a good point to start from for this game.
Thanks for joining us for this engineering update!
~ Andy Lim
By the way, I am officially noting that I am not the googly-eyed bandit. On my first day on this team, the Bandit tagged my brand-new monitors. They stare at me all day…all… day.