Event Loop

Ich habe gerade einen Knoten im Kopf bezüglich der besten Methode spielerunspezifische Ereignisse zu triggern.
Bisher hatten wir lediglich Ereignisse mit geringer Frequenz, die über einen Timer aufgerufen wurden.
Nun kommt aber eine Auktion dazu, in der mit hoher Frequenz und vor allem parallel zahlreiche Objekte angeboten werden, auf die die Spieler bieten können. Nach Ablauf der Auktion wird ermittelt, wer den Zuschlag bekommt.
Die Frage stellt sich mir nun, wie gehe ich damit um ohne den Server komplett lahm zu legen. Drei Varianten gehen mir durch den Kopf:
a) Die Erzeugung und Beendigung der Auktionen wird wie bisher über timergesteuerte Methoden abgewickelt.
b) Ich erzeuge einen permanent laufenden Main-Loop, in dessen Event-Queue sich die Ereignisse eintragen und der pausiert wenn nichts zu tun ist.
c) Der Start der Auktionen nach a oder b, aber danach kümmert sich jede Auktion selbst darum, sich nach Ablauf zu beenden (scheint mir aber problematisch bei vielen Auktionen)
d) Eine bessere Lösung, an die ich nicht gedacht habe ;-)
Ich bin dankbar über alle Tipps, Links oder Literaturhinweise.

eine queue anlegen, wo die abrechen/endzeitpunkte der auktionen drinne gespeichert sind und bei jeder useraktion (die die autktionen tangiert) checken ob was abzurechnen ist. alternativ aller n minuten per cron die queue überprüfen (je nach dem wie genu die auktion zu ende gehen muss)

Das ist ja quasi Lösung a mit dem Timer.
Leider muss das Ganze Echtzeit sein und unabhängig von Spielerinteraktion.
So eine Auktion läuft etwa 120 Sekunden und kann von den Spielern beobachtet werden. Sobald die Auktion beendet wird, werden also alle Spieler benachrichtigt, die Online sind und die Auktion beobachten.

Ich würde eine Queue nehmen, in die man Ereignisse stellen kann. Die Queue ist sortiert nach dem Zeitpunkt der Ausführung. Ein Thread setz einen Timer auf das erste Ereignis in der Queue und wartet, bis dieser Zeitpunkt erreicht ist. Je nach dem, wie CPU lastig das ganze wird, führt der thread das Ereignis aus, oder legt es in eine Queue, von der aus es von worker threads abgearbeitet wird.
Ich habe die Erfahrung gemacht, dass es durchaus einen signifikaten Unterschied machen kann, ob die Funktion, die das Ereignis dann bearbeitet mit der realen Zeit, oder mit der Zeit, zu der das Ereignis hätte ausgelöst werden sollen rechnet. Wenn periodisch austretende Ereignisse unter hoher Serverlast auch zusammen gefast werden könnten, kann es auch Sinn machen, mit beiden Zeiten zu rechnen.
Dein Erstellen einer Auktion, wäre dann ein Ereignis, dass bei Prozessstart in die Queue gestellt werden würde. Bei der Ausführung würde es die Auktionen erzeugen, und Auktions-Ende-Ereignisse in die Queue stellen und zu guter Letzt wieder ein Ereignis zur Erzeugung von neuen Auktionen in die Queue stellen.

Nehmen wir an, alle Auktionsenden sind in einer zentralen, nach Durchführungszeitpunkt sortierten Eventqueue.
Nehmen wir weiter an, jedes Gebot in einer Auktion soll dessen Laufzeit um ein paar Sekunden verlängern. Dann müsste die Eventqueue ständig neu sortiert werden; zumindest müsste sich die Auktion neu einordnen.
Mein Bauchgefühl sagt mir, das ist noch nicht optimal. Aber eine bessere Lösung ist mir trotzdem noch nicht eingefallen.

Du bräuchtest zusätzlich einen Index auf die Auktion, damit du nicht linear in der Liste suchen müstest. Und das entfernen und wieder einfügen eines Elements in z.B. einen RB Baum ist O(log n).

Ich würde eine Liste nehmen, die als Schlüssel einen Timestamp besitzt und als Wert eine Liste von AuktionIds.
In C++ würde sich da eine map eignen, pseudoCode:
map auctions;
map[1234567890] = [1,2,3,4];
Der Mainloop guckt dann jede Sekunde, ob Elemente in der Liste der jetzigen Sekunde sind und arbeitet die ab.
Wenn sich eine Auktion verschiebt, musst du nur die Aktion aus der einen Liste nehmen und in eine Liste mit anderem timestamp setzen. So brauchst die Liste nicht neu sortieren.

Imho ganz klar Loesung b).
Der einfachste Weg ist da meiner Meinung nach ein simpler Deamon, der z.B. alle x Sekunden (je nachdem wie zeitkritisch die Updates kommen, ich hab da nicht so einen Druck und würde es aus performance Gründen alle 30-60 Sekunden oder so ausführen) ausstehende Jobs aus einer Eventqueue in der DB ausliest und lokal im Speicher vorhält. Wenn es zeitlich knapper ist, spaart man sich eben den Umweg über die Datenbank und arbeitet mit Sockets oder named pipes und lässt front- und backend direkt miteinander reden... Dann ist es aber umso wichtiger, dass man auf performante Datenstrukturen setzt (wie Todi ja schon schrieb).
Das Ding lässt man dann in 100ms-500ms Intervallen sleepen und checken ob ein Item der Queue ins Zeitfenster gerutscht ist, wenn ja wird es je nach Komplexität direkt abgearbeitet oder geforked/per Interprozesskommunikation weitergeleitet, so dass die Queue ihre Arbeit fortsetzen kann.
Würde und werde ich für alles einsetzen, was in irgendeiner Form zeitgesteuert stattfinden soll (Angriffe, Eroberungen, Buffs, Debuffs, Quests, Ereignisse, Missionen, uswusw).
Ist imho allein schon um Serverlast zu Peakzeiten zu reduzieren und verheerende Crossabhängigkeiten zu vermeiden unabdingbar.

Warum wollt ihr den Prozess/Thread immer eine fixe Zeit lang schlafen lassen? Auf fast jedem System gibt es die Möglichkeit, bis zu einem bestimmten Zeitpunkt zu warten.

Das Topic würde mich auch mal interessieren...
wie sieht es den performance-mäßig mit
a) erzeugen von Timer-Objekten (.Net) die dann ne Methode aufrufen, wenn die Aktion starten soll,
im Vergleich mit
b) in einer Schleife die Objekte durchzulaufen und kucken obs was zu tun gibt
falls b) schneller sein sollte, denke ich, empfiehlt sich der Ansatz mit der sortierten Liste (dh. an 1. Stelle ist das am nächsten zu bearbeitende Element). Dort muss man nicht immer die gesamte Liste durchsuchen, obwohl das Einfügen/Ändern von Aufgaben dann performance-intensiver ist. Es kommt also darauf an, wie oft man etwas ändert im Verhältnis wie oft die Liste durchlaufen werden soll.

Edit, an Todi natürlich:
In meinem Fall, weil ich gerade nicht wüsste, wie ich es auf vergleichbar einfache Weise in Perl machen kann. Ich kenne ehrlich gesagt nur sleep/select (und wait/waitpid bei anderen prozessen)
Ich mein, ich kann natuerlich mit select (perldoc.perl.org/functions/select.html) "sleepen", so lang ich es gern hätte und das auch mit einer Granularität von Millisekunden, aber genau das meinte ich ja mit "100-500ms".
Wie würde man das denn sonst regeln bzw. wie würdest du es machen?
Edit2: mit Time::HiRes kann man glaub ich auch im Millisekundenbereich sleepen, fällt mir grad noch ein... was da technisch im Hintergrund passiert, weiß ich allerdings nicht.

Original von Kallisti
Ich mein, ich kann natuerlich mit select (perldoc.perl.org/functions/select.html) "sleepen", so lang ich es gern hätte und das auch mit einer Granularität von Millisekunden, aber genau das meinte ich ja mit "100-500ms".
Wie würde man das denn sonst regeln bzw. wie würdest du es machen?

Ja, select ist bestimmt keine schlechte Idee auf Posix-Systemen kann man dann auch noch pthread_cond_timedwait verwenden. Beim Eintrag in die Liste gucken, ob sich der frühste Aufwachzeitpunkt geändert hat, wenn ja Timer ggf. canceln und auf den neuen Zeitpunkt verschieben. Man muss sich ggf. noch überlegen, wie robust man gegen das verstellen der Systemzeit sein möchte.

mhhh
welche db wird denn benutzt ?

Ich habe jetzt die Java-Klasse DelayQueue verwendet, die das Ganze im Grunde fertig vorbereitet und sogar Multi-Threading geeignet bereit stellt.
Einzig das Rekonstruieren des Spielzustands nach einem möglichen Fehler oder Crash ist lästig (und zur Sicherheit Singlethreaded)