Warcraft Rumble

Einblicke in Warcraft Rumble: Die Berechnung der Mini-Erfahrung

Blizzard Entertainment

Hallo Rumblers!

Ich bin Andy Lim, Lead Engineer für Server-Features für Warcraft Rumble. Das Server-Team ist für all die Dinge zuständig, die man von einem Server-Team erwarten würde, also Netzwerkbetrieb, Cloud-Computing und Speicherung, aber wir arbeiten auch an Spielfeatures wie Kampagnenfortschritt und Quests. Ich möchte euch gern einen kleinen Einblick geben, wie wir Erfahrung speichern und sie dann nutzen, um die Stufen für jede Mini zu berechnen.

Darf ich vorstellen? Cassandra

Achtung! Es folgen einige technische Details und es könnte etwas komplex werden, aber bleibt dran.

Zuerst möchte ich euch unsere Speicherlösung vorstellen, mit der wir die häufigen Änderungen unserer Spielerdaten bei vielen gleichzeitig aktiven Benutzern im Blick behalten: Cassandra. Cassandra ist eine beliebte, äußerst skalierbare, verteilte Open-Source-Datenbank, die uns genau die richtige Balance an Datenkonsistenz und -verfügbarkeit bietet. Was die Daten selbst betrifft, so kommt Cassandra mit ausgedehnten Datensätzen zurecht, ohne ein strenges Schema durchzusetzen. Wir haben Tools entwickelt, die es den Engineers ermöglichen, unsere Datenbanktabellen und Tabellenschemata so zu definieren, wie es für jedes Feature erforderlich ist. So können wir Aufbau und Organisation nach Bedarf flexibel gestalten. Wir können unsere Schemata und Anfragen ohne Probleme schreiben und auswerten.

Was ist ein Schema? Ein Datenbankschema legt fest, wie Daten in einer relationalen Datenbank organisiert sind, so wie beispielsweise in Tabellen.

Erfahrung als Verzeichnis speichern

Cassandra ist bekanntlich sehr schnell darin, Daten zu schreiben, aber langsam beim Lesen. Um bestehende Daten zu aktualisieren, müssen diese oft zuerst gelesen und dann überschrieben werden, also verläuft auch dieser Prozess langsam. Um das zu vermeiden, haben wir unsere Spielerdaten wie ein Verzeichnis aufgebaut. In einem Verzeichnis schreibt man jede Zeile als Änderung. Wenn man es liest, liest man alle Einträge und stellt dann Berechnungen dazu an.

Ein gutes Beispiel für ein Verzeichnis ist zum Beispiel eine Kreditkarte. Jede Transaktion ist ein einzelner Eintrag mit einem positiven oder negativen Wert. Immer wenn man sie verwendet, wird eine Transaktion mit negativem Wert festgehalten. Immer wenn sie bezahlt wird, ist das eine Transaktion mit positivem Wert. Und wie weiß man, welcher Betrag noch offen ist? Man sieht sich das gesamte Verzeichnis an und addiert/subtrahiert jeden Wert.

Ortsfeste Daten kann man sich als einzelnen Wert vorstellen, der gespeichert werden kann. Immer wenn ihr diesen Wert ändern wollt, müsst ihr ihn lesen, die Änderung vornehmen und dann den neuen Wert aufschreiben. Wenn es beispielsweise um die Punkte bei einem Fußballspiel ginge, müsste man bei jedem Tor nachlesen, wie der letzte Punktestand war, das neue Tor hinzufügen und die Punkte dann aktualisieren.

Ein konkretes Beispiel für Arclight ist das Erfahrungsverzeichnis für jede Mini. Nach jeder Mission wird für eine einzelne Mini eine Zeile im Verzeichnis hinzugefügt, die angibt, wie viel Erfahrung diese Mini gesammelt hat. Nach fünf Missionen könnte das Verzeichnis dann so aussehen:

Tabelle 1

Spieler	Mini	Wert	Uhrzeit
Andy	Gnollschläger	3	Montag, 14:00 Uhr
Andy	Greifenreiterin	3	Montag, 14:05 Uhr
Andy	Gnollschläger	3	Montag, 14:10 Uhr
Andy	S.I.C.H.E.R.-Pilotin	3	Montag, 14:15 Uhr
Andy	Gnollschläger	3	Montag, 14:20 Uhr

Um dann die gesamte Mini-Erfahrung herauszufinden, nehmen wir einfach alle diese Einträge her, sortieren sie nach Mini und addieren die Erfahrungswerte. Das Ergebnis würde dann so aussehen:

Tabelle 2

Spieler	Mini	Gesamtwert
Andy	Gnollschläger	9
Andy	Greifenreiterin	3
Andy	S.I.C.H.E.R.-Pilotin	3

Der Rollup-Prozess

Wir haben jetzt also geklärt, wie wir die Erfahrung speichern. Jetzt wollen wir uns ansehen, wie wir die Berechnungen verfeinern, die wir für jede Mini anstellen. Wenn jede neue Mini-Erfahrung in einer einzelnen Zeile festgehalten würde, gäbe es extrem viel auszulesen. Es gäbe unglaublich viele Zeilen und die Tabelle würde endlos wachsen … FÜR IMMER. Nehmen wir an, ein typischer Tag in Rumble besteht aus 15 Quests oder PvP neben 20 Überladungen pro Woche für Gold und einem Dungeon pro Woche für die Armeeaufwertung. Das wären 100 Einträge pro Woche. Nach 3 Monaten hätten wir ca. 1.260 Einträge im Verzeichnis. Und um den Gesamtwert zu berechnen, müssten wir diese Einträge durch den langsamen Lesevorgang von Cassandra schicken. Oh weh.

Dafür haben wir eine Lösung entwickelt: Rollups. Ein Rollup ist eine Berechnung von Werten bis zu einem bestimmten Zeitpunkt. In diesem Fall addieren wir alle Werte und geben sie in einer einzelnen Zeile wieder. Diese speichern wir in einer zweiten Tabelle. Jetzt seht ihr auch, warum wir die Zeitangabe brauchen. Die Erfahrung wird nach Spieler und Mini sortiert und dann als Summe berechnet.Machen wir also einen Rollup für alle Verzeichniseinträge bis Dienstag um 00:00 Uhr und speichern die Ergebnisse in einer zweiten Tabelle in Cassandra. Die Einträge könnten so aussehen:

Tabelle 3

Spieler	Mini	Gesamtwert	Enddatum
Andy	Gnollschläger	9	Dienstag, 0:00 Uhr
Andy	Greifenreiterin	3	Dienstag, 0:00 Uhr
Andy	S.I.C.H.E.R.-Pilotin	3	Dienstag, 0:00 Uhr

Ihr spielt am Mittwoch weiter und sammelt weitere Erfahrungseinträge. Die ursprüngliche Erfahrungstabelle wäre gewachsen.

Tabelle 4

Spieler	Mini	Wert	Uhrzeit
Andy	Gnollschläger	3	Montag, 14:00 Uhr
Andy	Greifenreiterin	3	Montag, 14:05 Uhr
Andy	Gnollschläger	3	Montag, 14:10 Uhr
Andy	S.I.C.H.E.R.-Pilotin	3	Montag, 14:15 Uhr
Andy	Gnollschläger	3	Montag, 14:20 Uhr
Andy	S.I.C.H.E.R.-Pilotin	3	Mittwoch, 12:00 Uhr
Andy	Kettenblitzschlag	3	Mittwoch, 12:05 Uhr
Andy	Greifenreiterin	3	Mittwoch, 12:10 Uhr

Jetzt wollen wir alles auslesen und berechnen, wie die Mini-Stufen nach diesen Spielen aussehen. Wir öffnen beide Tabellen – die Rollup-Tabelle mit dem einzelnen Eintrag und das Verzeichnis für Einträge nach diesem Zeitpunkt – und addieren die Werte, um eine Tabelle mit der endgültigen Gesamterfahrung zu erhalten. Wir lesen also Tabelle 3 und nutzen Tabelle 4 nur für Daten, die nach jeder Zeile in Tabelle 3 existieren. Hier eine Liste der Schritte, die wir ausführen würden:

Eine Zeile von Tabelle 3 auslesen

Greifenreiterin

Dienstag, 0:00 Uhr

Zeilen von Tabelle 3 für Greifenreiterin nach Dienstag, 0:00 Uhr, auslesen

Greifenreiterin

Mittwoch, 12:10 Uhr

Jetzt addieren wir beide Datensätze und haben einen Gesamtwert von:

Greifenreiterin

Man sieht, dass man sich mit diesem Ansatz einige Zeilen in Tabelle 4 erspart.

Vielleicht denkt ihr, wir sollten einfach nur die neu berechneten Daten nach dem Speichern eines neuen Verzeichniseintrags speichern. In der Theorie klingt das gut, aber das Ergebnis wären inkonsistente Daten und eine verschlechterte Leistung. Ein Beispiel für die mögliche Leistungsabnahme wäre, dass das System mit neuen Berechnungen und dem Speichern von Daten beschäftigt ist, oft verursacht durch die Aufgabe, erst zu lesen und dann zu schreiben. Wir müssen die Berechnung hier in einem guten Gleichgewicht halten, während wir das Spiel für alle mit einer angemessenen Leistung zur Verfügung stellen.

Ein Beispiel für inkonsistente Daten wäre der Umgang mit den Berechnungen am Spielende. Unsere Serverinfrastruktur und Plattform unterstützen spät eintreffende Nachrichten. Ein Beispiel ist ein Übertragungsproblem zwischen zwei Datenzentren (A und B). Die Nachricht über die Mini-Erfahrung wird von A gesendet, hat B aber noch nicht erreicht. Stellt euch dieses Szenario vor: Ihr spielt ein Spiel genau vor Mitternacht. Ihr spielt und gewinnt. Es ist Mittwoch, 23:59 Uhr. Der Rollup wurde so programmiert, dass er täglich für alle Daten bis zum aktuellen Tag stattfindet. Er würde also um Mitternacht starten und die gesamten Erfahrungswerte bis Donnerstag um 00:00 Uhr berechnen. Die Daten würden in der zweiten Tabelle gespeichert werden und beim erneuten Auslesen der Erfahrung würde der letzte gespeicherte Wert herangezogen und mit allen nach Donnerstag um 00:00 Uhr addiert. Bei einer spät eintreffenden Nachricht funktioniert das so: Wir erhalten sie und stellen fest, dass das Spiel am Mittwoch um 23:59 Uhr abgeschlossen wurde. Also halten wir den Eintrag mit dieser Uhrzeit fest. In der Rollup-Tabelle würde dieser Eintrag aber fehlen und in der Abfrage nach späteren Daten würde er auch nicht auftauchen. Diese unvollständigen Daten wären ein Problem. Und was ist mit Nachrichten, die mit einigen Tagen Verzögerung eintreffen? Wir haben Überwachungs- und Warnverfahren, die fast immer garantieren, dass diese neuen Informationen rechtzeitig für den nächsten Rollup verarbeitet werden.

Berechnung von Mini-Stufen

Vielleicht ist euch aufgefallen, dass in der Tabelle mit der Gesamterfahrung noch keine Stufen berechnet wurden. Wir haben nur die Summe der jemals gesammelten Erfahrung. Unabhängig davon gibt es eine gleichbleibende Tabelle, die die Game Designer erstellt haben, und die ungefähr so aussieht. Eine Mini beginnt mit Stufe 1. Sobald sie einen Erfahrungspunkt verdient hat, erreicht sie Stufe 2. Sie braucht dann 3 Punkte, um Stufe 3 zu erreichen.

Stufe	Menge für nächste Stufe
1	1
2	3
3	6
4	10
5	20
…	…
10	250

Wenn wir die beiden Tabellen vereinen, können wir berechnen, welche Stufe eine Mini hat. Wir ermitteln den Gesamtwert und haben dann diesen Datensatz:

Mini	Stufe	EP	Menge für nächste Stufe
Gnollschläger	3	5	1
Greifenreiterin	3	2	4
S.I.C.H.E.R.-Pilotin	3	2	4
Kettenblitzschlag	2	2	1

Die Game Designer können flexibel ändern, wie viel Erfahrung für eine Stufe erforderlich ist. Sie könnten beschließen, dass es zu schwierig ist, auf niedrigen Stufen voranzukommen, und die Punkteanzahl für die nächste Stufe herabsetzen. Dadurch würden die Minis alle eine kleine Erhöhung der aktuellen Stufe bekommen und weniger Punkte für die nächste Stufe brauchen, ohne dass wir Änderungen an den Spielerdaten in der Datenbank vornehmen müssten. Das funktioniert auch andersrum. Wenn die Game Designer befinden, dass die Stufen zu schnell erreicht werden können, und die Werte erhöhen, gibt es keinen Erfahrungsersatz, damit Minis die Stufen vor der Änderung behalten. Das bedeutet aber nicht, dass das Design-Team nicht die Möglichkeit hätte, einigen Minis ein wenig Erfahrung zu erstatten, um die Änderung ein wenig besser verkraftbar zu machen.

Andere Ansätze, über die wir nachgedacht haben

Bevor wir uns für die aktuelle Lösung entschieden haben, haben wir uns verschiedene Ansätze angesehen, wie wir Erfahrungszugewinne speichern und die entsprechenden Stufen für Minis berechnen können. Einige würden zusätzliche Ausfallzeiten bedeuten, in denen wir die Spielererfahrung anpassen, während andere ein angenehmes Erlebnis garantieren und gleichzeitig den Spielerfortschritt festhalten.

„Immer die Mini-Stufe, die EP und die Schwelle zur nächsten Stufe speichern“

Wie wäre es mit einem Standard-SQL-Muster und der Verwendung von Transaktionsaktualisierungen? Mit Transaktionsaktualisierungen kann man einen gesamten Datensatz aktualisieren – entweder alles oder nichts. Wenn ein Teil nicht aktualisiert wird, werden alle auf den Originalwert zurückgesetzt. Dadurch werden Atomizität, Konsistenzhaltung, Isolation und Dauerhaftigkeit gewährleistet.

Dadurch würde man eine einzelne Zeile brauchen, um die Erfahrung und Stufe jeder Mini festzuhalten, wodurch das Auslesen supereinfach wäre.

Eine Mini gewinnt Erfahrung, die Erfahrung wird auf 2 Punkte aktualisiert, mit 8 Punkten, die zur nächsten Stufe fehlen, und sie ist aktuell auf Stufe 3. Diese Änderung erzwingt ein Auslesen der Daten, eine erneute Berechnung und dann eine Aktualisierung der Datenbank. Dieses Muster funktioniert weniger gut mit Cassandra und ihren Stärken. Ein weiterer Nachteil dieses Ansatzes ist, dass wir bei einer Änderung der Stufengrenzen das Spiel offline nehmen müssten, um die Daten für alle Minis und alle Spieler zu überarbeiten.

„Als Prozentzahl speichern“

Wir haben uns auch überlegt, die Schwelle zur nächsten Stufe als Prozentzahl festzuhalten, in etwa so:

Mini	Stufe	Zu nächster Stufe
Gnollschläger	3	20 %
Greifenreiterin	2	20 %
S.I.C.H.E.R.-Pilotin	2	20 %

Nach einem Spiel wären dann ein paar schnelle Berechnungen notwendig. Zum Beispiel: Gnollschläger erhält +3 EP, der Prozentsatz ist +3 / 10. Gnollschläger erhält dadurch 30 % bis zur nächsten Stufe, also:

Mini	Stufe	Zu nächster Stufe
Gnollschläger	3	50 %
Greifenreiterin	2	20 %
S.I.C.H.E.R.-Pilotin	2	20 %

Das würde uns Flexibilität geben, wenn wir die Mini-Stufenkurve anpassen, hätte aber keine Stufenänderungen für Minis zur Folge. Außerdem wären die Visualisierungen in der Benutzeroberfläche im Spiel einfacher, da wir die Leiste einfach um 30 % füllen könnten, ohne zusätzliche Berechnungen anstellen zu müssen. Aber dieses Muster hätte auf höheren Stufen sehr geringe Prozentzahlen zur Folge. Wenn eine Mini 10 EP pro Spiel sammelt und 100.000 für die nächste Stufe braucht, wäre das ein Wert von 0,01 %. CPUs kommen mit Gleitkommazahlen zurecht, aber es können Fehler im Hinblick auf Präzision und Genauigkeit eingeführt werden, wenn wir die Eigenheiten der Gleitkomma-Arithmetik nicht berücksichtigen.

Bis zum nächsten Mal …

Wir haben uns viele Gedanken zur Datenbanktechnologie, zu den möglichen Tools und auch zur Speicherung und Berechnung der Daten gemacht. Da wir uns noch mitten in der Entwicklung befinden, könnte sich all das zu einem späteren Zeitpunkt noch ändern, wenn wir etwas finden, das noch besser funktioniert, aber der aktuelle Ansatz schien uns ein guter Startpunkt zu sein.

Danke, dass ihr euch dieses Engineering-Update durchgelesen habt!

~ Andy Lim

Übrigens möchte ich ganz offiziell festhalten, dass ich nicht der Wackelaugen-Bandit bin. An meinem ersten Tag im Team wurden meine brandneuen Bildschirme zu Opfern des Banditen. Jetzt sehen sie mich den ganzen Tag lang an … den ganzen … Tag.