Warning: include_once(/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php): failed to open stream: No such file or directory in /var/www/html/fields/dbp09/local/config.php on line 4

Warning: include_once(): Failed opening '/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php' for inclusion (include_path='.:/opt/php/lib/php') in /var/www/html/fields/dbp09/local/config.php on line 4

Warning: Cannot modify header information - headers already sent by (output started at /var/www/html/fields/dbp09/local/config.php:4) in /var/www/html/pmwiki-2.2.86/pmwiki.php on line 1250
Datenbankpraktikum SS 2009 - Gruppe 1 - Backend-ticker

Ticker

Aufgaben und Anforderungen

  • Ankommende Flotten und fertiggestellte Gebäude müssen abgerechnet und entsprechende Änderungen an der Datenbasis durchgeführt werden. Dies soll im Sekundentakt geschehen, da bei koordinierten Angriffen von mehreren Spielern das Timing durchaus eine wichtige Rolle spielen kann. Weiterhin sind einige Gebäude-Updates und inbesondere Flottenbewegungen relativ rechenaufwändig. Die dadurch erzeugte Server-Last soll möglichst gleichmäßig verteilt werden. Die Sekundentaktung verhindert eine große Ansammlung zu berechnender Operationen, sodass ein flüssiger Spielablauf besser gewährleistet werden kann.
  • Die Produzierten Rohstoffe und Forschungspunkte müssen berechnet und upgedated werden. Diese Operationen findet nur alle 5 Sekunden statt, da sie sämtliche vorhandenen Spieler und bewohnten Planeten betrifft und folglich relativ aufwändig ist.
  • Der normale Spieltrieb darf durch den Ticker nicht unterbrochen und auchnicht signifikant verlangsamt werden.
  • Fehler dürfen die Ticker-Berechnungen nicht unterbrechen. Der Ticker muss endlos laufen.

Arbeitsweise

Baufträge und Flottenbewegungen

Jeder Bauauftrag (Schiffe, Gebäude) und jede Flottenbewegung erhält bei der Erstellung einen Zeitstempel mit dem Zeitpunkt der Fertigstellung/Ankunft. Über die entsprechenden Modelklassen ( BuildOrder, SpaceshipBuildOrder, TroopMovement ) fragt der Ticker aus der Datenbank diejenigen Datensätze ab, die einen Zeitstempel <= der aktuellen Zeit haben. Diese werden dann zur weiteren Verarbeitung an die entsprechender Controller weitergegeben und evtl. weitere Aktionen durchgeführt, z.B. das Versenden einer Nachricht an den Spieler, wenn ein Gebäude fertiggestellt wird.

Rohstoffe und Forschungspunkte

Zunächst wurde eine ähnlich vorgehensweise wie bei den Bauaufträge und Flottenbewegungen angestrebt. Der gravierende Unterschied war allerdings, dass der Ticker für die Rohstoffe/Forschungspunkte bei jedem Durchlauf sämtliche vorhandenen Planeten und Spieler verarbeiten muss. Die Zahl der in der gleichen Sekunde abgeschlossenen Bauaufträge/Flottenbewegungen ist im Vergleich dazu äußerst gering.

Erste Tests unter Verwendung der ActiveRecord-Modelklassen und der dynamischen Berechnung der Rohstoffproduktion anhand der relevanten Faktoren ( Gebäudestufe, Rasse, Taktik, Planetenbonus ) ergaben bei ca. 1300 Usern und Planeten eine Laufzeit von ca. 100 Sekunden. Durch Setzen einiger Indizes auf die Fremdschlüssel der beteiligten Entitäten ließ sich diese Zeit um 70% auf ca. 30 Sekunden verringern. Dennoch wurde dies als völlig inakzeptabel eingestuft.

Das ActiveRecord-Framework erwies sich also als deutlich zu langsam, wenn es um eine Vielzahl von Updates geht. Zu jedem aus der Datenbank gelesenen Datensatz wird ein entsprechendes Objekt erstellt. Beim speichern der Änderungen an den Objekten wird eine Vielzahl von Validierungen und Callbacks durchgeführt. All dies kostet deutlich zu viel Zeit.

Als Lösung erhielt jeder Planet pro Rohstoff ein weiteres Datenfeld für die jeweilige Produktion pro Stunde und ein Datenfeld mit der momentanen Lagerkapazität. Diese Datenfelder müssen nun zwar bei jedem Gebäudebau und jeder Änderung der Taktik aktualisiert werden, es erlaubt aber sämtliche Planeten und User jeweils mit einer einzigen SQL-Query upzudaten. Bei jedem Update wird der Zeitstempel für den letzten Update-Zeitpunkt ausgelesen und daraus und aus der Stundenproduktion berechnet wieviele Rohstoffe dazuaddiert werden müssen. Dann wird der Zeitstempel noch auf die aktuelle Zeit gesetzt. Wichtig war noch zu beachten, dass die Rohstoffe eins Planeten niemals die Lagerkapazität überschreiten. Dies wird durch die "SELECT IF"-Statements realisiert, die ähnlich dem aus diversen Programmiersprachen bekannten Ausdruck "foo == bar ? bar : foo" funktionieren.

Auf die Weise ergibt sich eine Laufzeit von weniger als einer Sekunde.

UPDATE users u
 SET u.technology_score = u.technology_score +
                      (
                        SELECT SUM(p.technology_score_production * (#{now} - u.last_tick_tech) / 3600)
                        FROM  planets p
                        WHERE p.user_id = u.id
                      ),
     u.last_tick_tech = #{now}
 
UPDATE planets p
   SET p.ore = (SELECT IF( ( p.ore + (p.ore_production / 3600) * (#{now} - p.last_tick_res)) > p.storage_capacity ,
                p.storage_capacity, 
                ( p.ore + (p.ore_production / 3600) * (#{now} - p.last_tick_res)) ) ),
       p.gas =(SELECT IF( ( p.gas + (p.gas_production / 3600) * (#{now} - p.last_tick_res)) > p.storage_capacity , 
               p.storage_capacity, 
               ( p.gas + (p.gas_production / 3600) * (#{now} - p.last_tick_res)) ) ),
       p.crystal =(SELECT IF( ( p.crystal + (p.crystal_production / 3600) * (#{now} - p.last_tick_res)) > p.storage_capacity , 
                p.storage_capacity, 
                ( p.crystal + (p.crystal_production / 3600) * (#{now} - p.last_tick_res)) ) ),
       p.last_tick_res = #{now}
WHERE user_id IS NOT NULL

Nebenläufigkeit und Reaktion auf Fehler

Die Nebenläufigkeit des Tickers wird erreicht, indem er als eigener Prozess parallel zum Server gestartet wird. Man kann ihn entweder mit dem Kommandozeilenbefehl
script/ticker.rb
direkt als unabhängigen Prozess starten, oder aber mittels dem Flag -t beim Serverstart als Kindprozess des Serverprozesses starten:
script/server -t 1

Innerhalb des Ticker-Prozesses wird für jede der vier Tickerfunktionen ein eigener Thread gestartet. In diesem Thread läuft eine Endlosschleife, die die jeweilige Operation aus dem BackendTickerController aufruft und dann für das vorgegebene Intervall in einen sleep geht.

Sollte innerhalb der jeweiligen Operation ein Fehler jeglicher Art auftreten, so wird dieser abgefangen und zu Logging-Zwecken mitsamt dem backtrace in die Standardausgabe geschrieben. Dann wird versucht die Operation mittels retry nochmals durchzuführen.

Als Beispiel der Code für den Rohstoff- und Forschungspunkteticker:

# Thread starten
Thread.new do
  puts "...ResourceTicker started."
  # Endlosschleife
  while true
    begin
      BackendTickerController.calc_res
    # Exceptions fangen, damit der Thread nicht beendet wird
    rescue Exception => c_r_error
      puts "Error while processing Resource-Calculation: " + c_r_error 
      puts c_r_error.backtrace.to_s
      retry
    end
    # Nur alle 5 Sekunden
    sleep 5
  end
end

Performance

Performance-Test

Um die tatsächliche Performance des gesamten Systems und die Auswirkung des Tickers darauf zu testen wurde ein kleines Testsystem entwickelt, welches den Spielbetrieb mit einer beliebigen Anzahl von Usern simuliert.

Zunächst wurde ein Script geschrieben, mit dem man mittels eines Kommandozeilen-Befehls eine beliebige Anzahl von PerformanceTestUsern anlegen kann:

script/generate_test_users.rb -c <anzahl>

Die so erstellen Testuser erhalten einen Startplaneten, auf dem initial das Lager auf 50 gesetzt wird. Weiterhin erhalten sie von jeder Schiffsklasse 1000 Schiffe und einige Millionen Einheiten Rohstoffe von jeder Rohstoffsorte. Mittels dem Befehl
script/spawn_orders.rb -w <zeitintervall>
wird im vorgegebenen Zeitinvertall einer der vorhandenen PerformanceTestUser zufällig ausgewählt und auf einem Planeten jeweils ein Bauauftrag, ein Schiffbauauftrag, eine Forschung und eine Flottenbewegung gestartet.

Ein solcher Test mit 1300 PerformanceTestUsern ergab bei einem Zeitintervall von 2 Sekunden einen Load-Average auf dem Server on ca. 1,0. Das bedeutet mit dem zur Verfügung stehenden Server können maximal 2 Orders pro Sekunde ohne Verzögerung abgesetzt werden.

Die Tickerfunktionen liefen auch bei dieser Anzahl an Orders und Planeten noch in einer relativ guten Zeit ab. Zwei Auszüge aus der Logdatei des Testlaufes:

1353 Planets and 1337 Users updated in 0.778814s
1353 Planets and 1337 Users updated in 0.574504s
1353 Planets and 1337 Users updated in 0.308708s
2 SpaceshipBuildOrders finished in 0.028714s
1 BuildOrders finished in 0.077058s
0 TroopMovements finished in 0.001791s
1 SpaceshipBuildOrders finished in 0.012603s
0 BuildOrders finished in 0.002414s
0 TroopMovements finished in 0.001436s

Die gefundenen Lösungen für die anfänglichen Probleme erwiesen sich also durchaus als sehr praktikabel. Insbesondere das Sekündliche abrufen der fertiggestellten Bauaufträge und Flottenbewegungen sorgt dafür, dass sich garnicht erst große Mengen ansammeln, die abgearbeitet werden müssen, sodass alles in einer akzeptablen Zeitspanne ablaufen kann und dem Spieler wirklich ein Gefühl von Echtzeit vermittelt.

Problem: Häufige Deadlocks

Es ergab sich allerdings zunächst das Problem, dass sehr häufig Deadlocks auftraten und Datenbankanfragen teilweise mehr als 50 Sekunden benötigten. Als grundsätzeliche Ursache wurde die Vielzahl der Transaktionen ausgemacht. Diese sind aber notwendig, z.B. dürfen die Rohstoffe auf einem Planeten nur dann abgezogen werden, wenn der Bauauftrag tatsächlich auch erzeugt worden ist.

Es begann nun also die Suche in den MySQL-Server-Logdateien nach denjenigen Transaktionen, die die Hauptursache für die Deadlocks und die langen Wartezeiten waren, in der Hoffnungn diese evtl. anpassen zu können. Die Query "SHOW INNODB STATUS" förderte folgendes zu Tage ( Ausschnitt ):

[...]
------------------------
LATEST DETECTED DEADLOCK
------------------------
[...]
*** (1) TRANSACTION:
TRANSACTION 0 5490351, ACTIVE 0 sec, process no 4266, OS thread id 2899278736 fetching rows
mysql tables in use 2, locked 2
LOCK WAIT 371 lock struct(s), heap size 27968, 4352 row lock(s), undo log entries 9
MySQL thread id 122945, query id 8254784 dbs.informatik.uni-osnabrueck.de 131.173.12.19 mmog Sending data
UPDATE users u
                   SET u.technology_score = u.technology_score +
                   (
                     SELECT SUM(p.technology_score_production * (1250076993 - p.last_tick) / 3600)
                     FROM  planets p
                     WHERE p.user_id = u.id
                   )
 
[...]
 
*** (2) TRANSACTION:
TRANSACTION 0 5490322, ACTIVE 1 sec, process no 4266, OS thread id 2902969232 starting index read, 
thread declared inside InnoDB 500
mysql tables in use 1, locked 1
3 lock struct(s), heap size 320, 2 row lock(s), undo log entries 1
MySQL thread id 125289, query id 8254788 131.173.210.41 mmog Updating
UPDATE `users` SET `updated_at` = '2009-08-12 11:36:34', `perishable_token` = 'Tqk66TGG6mne7_I-T91l', 
`technology_score` = 999900.833, `speed_techlevel` = 4 WHERE `id` = 2234
 
[...]

Mehrmaliges ausführen der Query ergab, dass die Ticker-Queries für das Rohstoff- und Forschungspunkteupdate an nehezu jedem Deadlock beteiligt waren. Am aufschlussreichsten dabei waren allerdigns vorallem diese beiden Zeilen:

mysql tables in use 2, locked 2
[...]
mysql tables in use 1, locked 1

Daraus ließ sich erkennen, dass für die Updates jeweils die komplette Tabelle gelockt wird, obwohl die InnoDB-Storage-Engine auch locking auf Row-Ebene beherrscht. Eine Rechere in der MySQL-Dokumentation förderte zu Tage, dass man dies mit einer einfachen Config-Änderung umgehen konnte:

innodb_table_locks = 0

Dadurch ließ sich die Häufigkeit auftretender Deadlocks etwas vermindern. Dennoch kamen sie in nicht vertretbaren Intervallen vor, und Datenbankanfragen dauerten teilweise immernoch 50 Sekunden und mehr. Es stellte sich heraus, dass der Default-Wert für die Wartezeit einer Transaktion auf einen Lock ehe sie neugestartet wird 50 Sekunden beträgt ( MySQL-Referenz ).

Nach der Konfigurationsänderung des Timeouts auf 1 Sekunde traten weder weitere Deadlocks im Spielbetrieb, noch lange Wartezeiten bei Datenbankanfragen auf.


Page last modified on August 18, 2011, at 05:51 PM