Tick Tack..

Ich habe mal eine prinzipielle Frage zur Umsetzung eines Tickers.
Was meine ich mit Ticker? Es ist das Stueck Code das in regelmaessigen Intervallen (eine Stunde - 10 Minuten - whatever) verschiedene Elemente des Spiels aktualisiert:

• Einheiten bewegen sich
• Ressourcen werden aufgefrischt
• Kaempfe werden berechnet und ausgewertet
• Bau&Forschung schreitet voran
• Highscorelisten werden aktualisiert

Nun wie das umzusetzen ist ist ja prinzipiell relativ einfach. Prinzipiell!
Worueber ich gerade nachdenke ist Datenintegritaet bei gleichzeitigem Zugriff allgemein und vor dem Hintergrund der Performanz.
Konkret: was passiert wenn ein Spieler was macht waehrend der Ticker laeuft. Ohne weiter Ueberlegungen anzustellen wird es in einem undefinierten Zustand enden. Das ist unerwuenscht.
Welche Technologien gibt es um das zu umgehen oder zu vermeiden? Tabellen sperren? Usereingaben waehrend Ticker rechnet verbieten? Transaktionen?
Wuerde mich freuen wenn ihr ein paar Tipps geben koenntet wie ihr das Problem loest. Auch wie gesagt vor dem Hintergrund der Performanz.
Danke im Voraus,
cherry

Bei mir werden einfach alle zugriffe zentral über den gleichen code geleitet, wenn der Tick läuft warten alle.

Verstehe ich nicht - liegt vielleicht daran dass ich mit der Technologie die Du einsetzt nicht vertraut bin. Ich bin eher in der C/C++ Welt zu Hause und fuer das Frontend setze ich Serverseitig im Moment PHP ein.
Aber was Du sagst suggeriert irgendwie nur einen einzigen Thread das hoert sich recht ineffizient an. Oder synchronisieren sich alle Userthreads auf den Tickerthread?

Im Prinzip ist es genauso wie bei Tabellen, wenn ich auf eine Tabelle zugreife stelle ich sicher das diese vorher gesperrt wird und kein anderes Skript mir dazwischen funkt.
Genau so muss dein Tick auch laufen, theoretisch, wenn der Tick gerade durchläuft müssen etwaige andere Funktionen die auf ein gleiches Element zugreifen wollen auf Warten gestellt werden bis der Tick fertig ist.
Sonst hast du buntes Kuddelmuddel.

> Welche Technologien gibt es um das zu umgehen oder zu vermeiden? Tabellen sperren?
Ich persönlich nutze Mutex-Objekte, die prozessübergreifend sperren.

Bei mir ist für v2.0 auch eine Serialisierung über einen Datahandler geplant.
Sprich, Anfrage kommt von aussen rein und ich prüfe ob das Objekt gesperrt ist.
Neben Objektsperren, wird es globale Sperren geben, welche aber nur bei extrem großflächigen Änderungen verwendet werden.

Original von cherry
Aber was Du sagst suggeriert irgendwie nur einen einzigen Thread das hoert sich recht ineffizient an. Oder synchronisieren sich alle Userthreads auf den Tickerthread?

Bei jedem Klick in meinem Spiel wird eine kleine unbedeutende Anfrage and den Tick Thread gestellt. Wenn der Tickthread nicht läuft (bzw. laufen tut er schon, aber nicht arbeitet ), geht alles ganz normal durch, ansonsten werden alle Anfragen der User praktisch auf Warten gestellt. Sobald der Tick Thread fertig ist, laufen alle wartenden Prozesse normal weiter bzw. werden nachgeholt.
Was ja nötig ist, weil der Tick-Thread alle Daten berechnet und in der Datenbank festschreibt nach dem Update. Wenn da irgendjemand werkeln könnte, wäre das ungesund für die Konsistenz

Ich weiss ja nicht, was eure "tick threads" alles tolles machen, aber teilweise klingt es, als wuerdet ihr quasi die komplette DB locken, weil das backend grad einen Angriff durchrechnet oder so...
Sicher muss man locken, aber doch nur die Teilbereiche in denen man zu gange ist und auch nur in bestimmten Faellen (alles was man atomar mit einem statement erledigen kann braucht keine locks...).
Mehrere threads/forks brauchst du auch nur wenn du nen Server mit mehreren Prozessoren hast oder die Datenbank auf nem anderen Server laeuft und du auf I/O warten musst... und selbst dann ist die Frage ob der Managementprozess threaded sein muss oder es so langt.
Was tut euer Backend denn so alles, dass ihr da von ewig langen locks und wartereien redet? Wenn ich z.B. einen Angriff berechnen moechte und dafuer die entsprechenden Tabellen locke, dann aber doch nur fuer die Dauer des Angriffs... muessen eben Userinputs kurz warten bis der Angriff berechnet wurde und koennen dann ihren input schreiben und der naechste Angriff wird berechnet...

Ich weiss ja nicht, was eure "tick threads" alles tolles machen, aber teilweise klingt es, als wuerdet ihr quasi die komplette DB locken, weil das backend grad einen Angriff durchrechnet oder so...

Wer würde denn so etwas machen Oo

Was tut euer Backend denn so alles, dass ihr da von ewig langen locks und wartereien redet?

Wieso "ewig lang"? Hat doch keiner etwas von erzählt, bisher halten wir uns mit relativen Zeitverhältnissen auf zumindest gehe ich davon aus. Ein Lock dauert dem nach keine wirklich zählbare Zeit, dennoch ist er notwendig wenn die Datenbank entsprechend dumm ist ^^

Bei mir ist in v2.0 z.B. geplant die gesamten Resourcentabellen während der alle 15 Minuten stattfindenden Resourcenberechnungen.
Bevor ich jede Zeile einzeln sperre, hau ich eine globale Sperre drauf rein, flitze durch die Updates und gebe alles wieder frei.

Welche Datenbank nutzt du denn? myisam Tabellen sollten immer die komplette Tabelle locken und nicht einzelne Zeilen? Oder kannst du das nicht mit einem einzelnen query fuer alle User abhandeln?
Macavity: "Bei mir werden einfach alle zugriffe zentral über den gleichen code geleitet, wenn der Tick läuft warten alle." klang fuer mich schon so. ^^

InnoDB, bzw. demnächst DDC (Dynamic Data Cache), was eine Eigenentwicklung darstellt.

Naja, wenn ich in einer Schleife alle Planeten durchgehe und die Daten und Ressourcenproduktion, Bauaufträge, Flottenbewegenung usw. berechne wärs schon schön, wenn da niemand reinpfuscht.
Um teilweises locken zu ermöglichen müsste ich für alle Aktionen festgelegt haben, ob diese Aktion jetzt eine reine Leseaktion ist oder nicht.
Es geht dabei weniger um die Datenbank, als darum das ich die Daten "nebenher" im RAM halte und in diesen Daten sollte halt ein konsistenter Zustand herrschen.
Und da eben wirklich ALLES durchgerechnet wird ... Planet für Planet .. ist ein kompletter Lock aller Prozesse das Vernünftigste. (Zumindest solange die Zeit für das Tickupdate in vernünftigem Zeitrahmen bleibt)

Original von RaydenDD
ansonsten werden alle Anfragen der User praktisch auf Warten gestellt. Sobald der Tick Thread fertig ist, laufen alle wartenden Prozesse normal weiter bzw. werden nachgeholt.

Interessant.
Ich sehe ein Problem bei diesem Ansatz. Es gibt immer noch einen undefinierten Zustand naemlich fuer den Benutzer. Der Benutzer kann nicht unbedingt vorhersehen was der Ticker berechnet und wenn er aufgrund der Informationen die er vor dem Tickerstart hat eine Aktion taetigt die nach dem Tick keinen Sinn mehr macht schaut er mit dem Ofenrohr ins Gebirge. Ich finde das ist auch eine Art von Inkonsistenz.
Mein Gedanke: macht es nicht mehr Sinn dem Benutzer zu sagen "Ne Du, sorry aehm das Spiel tickt grade versuchs in einer Minute nochmal, ja?" anstelle die Aktionen zu queuen?
Die komplette Tabelle oder komplette Datenbank oder komplettes Spiel oder nur Zeilen sperren Frage ist auch spannend. Theoretisch ist es meinen Ueberlegungen nach nicht notwendig eine komplette Datenbank oder Tabelle zu sperren sondern lediglich die Felder/Zeilen die fuer den aktuellen Rechenschritt (z.b. ein Kampf) benoetigt werden. Ich stimme Kallisti zu.

Hmm ja da sprichst du einen guten Punkte an ... die einzig kritsche Situation ist eigentlich, wenn man mit mehreren Spieler zusammen Flotten timen will, das sie zum gleichen Zeitpunkt ankommen. Wenn du das während des Updates machst, startest du natürlich erst zu t+1

Wenn du ein rein Tickbasierendes Spiel hast, dann macht es nichts aus ob die Aktion bei Tick+5 Sekunden oder Tick+1 Minute durchgeführt wurde.
Ok, der Spieler ist ein wenig abgenervt, aber wenn das passiert, dann muß man eh den Code erstmal aufräumen um Performanceprobleme zu fixen.
Bei einem Spiel, wo die Aktionen sekundengenau ausgeführt werden und man z.B. (so wie bei mir) alle 15 Minuten Resourcenticks hat, stellt das schon ein Problem dar.
Da die alte Version nur noch die Testwiese für mich ist, werde ich das bei mir nicht mehr ändern, aber das Problem haben bestimmt noch andere.
Sorry für die wuschigen Texte heute... mein Hirn leidet unter einer Erkältung

Original von Kallisti
(alles was man atomar mit einem statement erledigen kann braucht keine locks...).

atomar != einem statement .
nur um evt. Probleme bei dir im Vorfeld zu vermeiden...

Mit MaxDB lassen verschiedene Transaktionsgrade einstellen (ebenfalls mit DB2 und Oracle):
www.iwiki.de/wiki/index.php/Isolationsgrade
Ich empfehle den Read Commited für HTTP-Requests und Repeatable Read für Hintergrundjobs (hat sich bei uns bewährt).

Original von BBana

Original von Kallisti
(alles was man atomar mit einem statement erledigen kann braucht keine locks...).

atomar != einem statement .
nur um evt. Probleme bei dir im Vorfeld zu vermeiden...
War bischen unglueckliche Wortwahl, ich bezog mich nicht auf das im Datenbankjargon uebliche "atomar" (also im Sinne des Wertebereiches), sondern auf "atomar" als Ausdruck fuer die kleinste Einheit, also in diesem Fall mit einem einzigen Statement.
Streich das Wort einfach.

Nun ja vielleicht sollten wir uns eher auf Transaktion festlegen ... 1 Statement muss im Kontext des Browsergames noch lange nicht Atomar sein.

Kannst du mir ein Beispiel nennen wo es zu Race Conditions bei zwei einzelnen Statements kommen kann?

Ich meine das eher darauf bezugnehmend das dieser Thread glaube ich ein bisschen zu weit übers Ziel hinausschiesst.
Es kann ja sein das mehrere Statements mit Zeitverzögerung nacheinander ausgeführt werden. Und wenn der Benutzer einen Klick macht und eine Seite angezeigt bekommt, die Informationen von verschiedenen Tabellen sammelt, die aber noch nicht alle aktualisiert wurden.
Insofern hätte der Zugriff verhindert werden sollen, solange noch nicht die ganze Transaktion durchgeführt wurde. Somit wäre die Transaktion für eine fehlerfreie Anzeige der Seite atomar.

In so einem Fall (wenn ein Zusammenhang da ist), muss man ja eben auch manuell locken... allerdings auf der Seite, wo der Zusammenhang besteht, also beim Zugriff. Bzw. wenn ein Zusammenhang besteht, eigentlich auch beim Schreiben...
Auf der anderen Seite sollte so etwas eigentlich nicht vorkommen koennen. Nenn mir halt auch hier ein Beispiel, wo eine Aktualisierung erfolgt ist und beim Auslesen an anderer Stelle etwas durcheinander kommen kann.

Wenn man seinen Ticker thematisch sortiert und halbwegs intelligent abarbeitet, sollte es nicht zu sowas kommen.
Bsp:
Wenn die Kämpfe abgearbeitet werden. Am Anfang werden die Daten geholt, welche Heere dabei sind, und dann der Kampf berechnet. Probleme könnten hier nur entstehen, wenn jemand Einheiten aus diesen Heeren entfernt - wenn das im Konzept aber bedacht ist, gibt es dabei eigentlich kein Problem.
Bsp. Ressourcenproduktion:
Alle Werte sammeln, mit einem Update die Werte verändern - natürlich relativ, nicht absolut.
Problematisch:
ressource = wert_aus_datenbank
ressource -= gesamter_gewinn
sql_statement("UPDATE ressourcen SET `ressource` = '" + ressource + "'")
Damit könnte im Extremfall ein Spieler zwischen dem Wert holen und dem Wert eintragen Einheiten bauen - so schon passiert bei Aquata, in Speedrunden in den Anfängen. Ja, innerhalb von Millisekunden.
Lösung:
ressourcengewinn = gesamter_gewinn
sql_statement("UPDATE ressourcen SET `ressource` = `ressource` + '" + ressource + "'");
Wenn man das durchgehend so macht, ist es eigentlich ziemlich egal wie lang der Tick braucht zum berechnen - sofern die Werte, mit denen der Tick arbeitet nicht vom Spieler ad absurdum geführt werden können (Einheiten nicht mehr da; Einkommensproduktion mit sofortiger Wirkung von A nach B verschoben;..) macht das nichts.
Anmerkung: Wenn man sich in einer Query alle Daten holt die relevant sind, macht auch Punkt 2, Einkommensproduktion verschoben, nichts; in dem Fall würde die Produktion halt noch bei der vorigen Station fertig werden.

Aber dann evtl nochmal von der anderen Station berechnet werden, wenn diese erst 10 MS später dran ist und er genau dazwischen verschoben hat!

Nein, wie gesagt: Wenn man sich alle Daten in einer Query holt, dann passiert das nicht.
(Extrem simples) Pseudocode - Beispiel:
data = sql_query("SELECT * FROM ressource_producers");
while(row IN data)
{
ressource_production_data_of_user[row->user] = row->income;
}
[... Hier andere Daten aus der Datenbank holen, wie Boni etc. ...]
data = sql_query("SELECT * FROM users");
while(row IN data)
{
income = ressource_production_data_of_user[row->user] * ressource_production_modifier[row->user];
sql_query("UPDATE users SET `ressource` = `ressource` + '" + income + "' WHERE `user` = '" + row->user + "'");
}

Ob Dein Beispiel funktioniert haengt wohl von der Implementierung der Datenbank ab. Denn auch wenn Du nur ein SQL Statement hast werden trotzdem Read, Add und Writeback ausgefuehrt. Wenn zwischen dem Read und dem Writeback jemand dazwischenfunken kann hast Du wieder das selbe Problem.
Wenn die Datenbank aber sicherstellt dass das Statement "ununterbrechbar" ist (niemand kann dazwischenfunken.. effektiv wohl das selbe wie eine Sperrung der Zeile/Tabelle) bist Du auf der sicheren Seite.
Unangenehmer wird es wohl wenn ein Kampf berechnet werden soll. Die koennen in der Regel ja nicht mit einem einzigen SQL Statement abgehandelt werden und folglich muss man ein "Dazwischenfunken" ueber mehrere Statements hinweg verbieten. Transaktionen?
Mir ist nicht klar wie man das im Konzept bedenken kann. Klar kann man sich zusaetzliche Einschraenkungen ueberlegen wie z.B. einen Tick vor der Schlacht koennen Einheiten nicht zurueckgezogen werden oder sonstwas aber das ist ja eigentlich unsinnig.

Hinweis:
In allen mir bekannten Datenbanksystemen werden einzelne Statements atomar abgewickelt. Konkret: MySQL, SQL Server und diverse JDBC und ADO.Net-Datenbankprovider.

Naja, siehs mal als konkretes Beispiel bei mir, Aquata.
Dort werden am Anfang alle Flotten abgefragt.
Flotten kann man in dieser Zeit (während sie Fliegen) nur zurückziehen, Verteidigungsflotten könnten weggeschickt werden. Das Allerschlimmste was passieren könnte, wäre, dass bei der Verteidigung ein Schiff von einer in die nächste Flotte verschoben wird.
Das macht aber auch nichts, da bei der Verteidigung alle Flotten als am Kampf teilnehmend gelten, und diese Änderung vom Skript einfach rückgängig gemacht werden würde.
Das bedeutet, dass man mit den Flotten bei mir z.B. nichts machen könnte, was die Integrität der Daten wirklich schwerwiegend abändert - denn selbst wenn die Flotte abgezogen wird, die Verluste hat sie trotzdem, wenn sie bei der ersten Query (und ja, es ist eine) dabei war.
Natürlich sind im Kampf selbst noch mehrere Queries am Werkeln - Schiffsdaten, Kommandoschiffdaten, Skills, Einstellungen, Trefferchance/Schaden/Reihenfolgenqueue, Namen... aber hier ist auch nichts, was die Flotten beeinflussen könnte. (siehe: Kampfablauf)
Für den Ressourcenklau wird die Tabelle allerdings gesperrt. Da war mir der Security-Check aber einfach nur zuviel Arbeit..

Original von Nuky
Nein, wie gesagt: Wenn man sich alle Daten in einer Query holt, dann passiert das nicht.
(Extrem simples) Pseudocode - Beispiel:
data = sql_query("SELECT * FROM ressource_producers");
while(row IN data)
{
ressource_production_data_of_user[row->user] = row->income;
}
[... Hier andere Daten aus der Datenbank holen, wie Boni etc. ...]
data = sql_query("SELECT * FROM users");
while(row IN data)
{
income = ressource_production_data_of_user[row->user] * ressource_production_modifier[row->user];
sql_query("UPDATE users SET `ressource` = `ressource` + '" + income + "' WHERE `user` = '" + row->user + "'");
}

Je nach Datenmenge könnte es aber Problematisch sein sich alle Daten erst zusammenzulesen.
Beispiel Ogame zu glanzzeiten:
10000 User (Die inaktiven mal mitgezählt), mit 9 Planeten. Macht schonmal 90000 Sätze. Bei entsprechender Komplexität der Sätze könnte das schon problematisch werden, zumal der Rest ja dynamisch weiterläuft.

Dann setze ich das Memory-Limit vorher höher.. gefällt mir jedenfalls viel besser, als die Tabelle für diese Zeit zu locken o.ä.

bei ca. alle 10 min lohnen sich cronjobs, oder?

und ansonsten nicht? Ich verwend cronjobs auch für Statistikauswertung 2x täglich

doch ich auch, aber bei alle 20 sekunden oder jede min ist ein cronjob unpraktisch, oder irre ich mich?

achso du hast nach unten gemeint .. ja .. bei 10 sekunden würd ich auch kein cronjob mehr verwenden.

Jede Minute? Kein Problem...?

Denk ich auch, dass das kein Problem ist. Hauptsache, der gestartete Job läuft nicht länger als das definierte cron-Intervall... Das kann (je nach art des Jobs) dann problematisch werden.