mmofacts.com

Scheduling / Eventqueue / Dispatching

gepostet vor 16 Jahre, 2 Monate von Kallisti

Machen wir doch mal wieder ein interessanteres Thema auf:

Scheduling / Eventqueue / Dispatching

Nun, ich stelle mir gerade die Frage, wie genau ich meine backend <> daemon Kommunikation gestalte und wie der daemon dann weiter mit den Daten verfährt.

Imho kommt man ab einem gewissen Grad an Spielintelligenz und automatisch ablaufenden Vorgängen nicht mehr um einen daemon herum und das Thema hatten wir ja schon an anderer Stelle, daher soll das hier nicht Punkt der Diskussion sein.

Scheduling

Die Frage ist nun wie mein Backend (bei mir also mein Perl MVC Code, Frontend wäre GUI/Javascript libs/PHP Scripts, die GUI/libs dynamisch einbingen - Frontend und Backend sprechen nur JSON miteinander; Ich habe also je nach Definition irgendwas zwischen 4-tier, 5-tier und 7-tier architecture, genau genommen letzteres) am sinnvollsten mit dem daemon kommuniziert und wie der daemon dann am effektivsten dispatcht.

Für die Kommunikation habe ich ja im Grunde zwei Möglichkeiten.

a) Direkte Kommunikation Backend <> server über sockets/named pipes

b) Datenbank als Zwischenschritt

Vergleichen wir also die beiden Möglichkeiten bei verschiedenen Anwendungsfällen:

Kommunikation

a) Backend und daemon sprechen direkt miteinander. Die Kommunikation ist also instant und der Server weiss sofort was los ist, ohne sich selbst um die Informationen kümmern zu müssen. Es fallen IO Operationen für sockets/pipes an. Das ist zwar bei Datenbanken auch so, aber die sind professionell programmiert und stark optimiert, und es ist zu erwarten ist, dass mein Perl Code langsamer performt.

b) Das Backend schreibt erst einmal in die Datenbank, der Server pollt regelmäßig aus der Datenbank. Das Polling ist ein Mehraufwand und es kann Szenarien geben in denen das für den User zu einer Verzögerung führt, wenn das Polling Interval zu groß ist. Pollt man jedoch sekündlich, sollte das nicht mehr auffallen und man täuscht Echtzeit vor. Sekündliche Polls sind natürlich eine Mehrbelastung, allerdings ist die Datenbank optimiert, die Eventqueue hat indexierte Keys, daher dürfte der Performance Impact gering ausfallen und je mehr das System nach oben skaliert, umso geringer wird der Anteil des Pollings.

Clustering

a) Die direkte Kommunikation erlaubt es einfach weitere daemon Server aufzusetzen, sofern das ganze über sockets läuft. Jeder daemon Server könnte ohne Mehraufwand das komplette Repertoire an Funktionen abdecken, sofern das Dispatching per se erst einmal stateless ist. Wenn der Server jedoch aus Performancegründen selbst Informationen vorhält, wird das komplizierter.

b) Man kann jederzeit weitere Datenbank Server hinzufügen um hier Last abzufangen. Allerdings ist es schwieriger den daemon zu clustern, da ja kein einfacher select auf die Eventqueue mehr ausreicht, weil sonst die verschiedenen daemons dieselben Daten abarbeiten würden. Das heißt man müsste entweder mehrere verschiedene Queue Datenbanken haben oder innerhalb einer Datenbank differenzieren. Dann könnte beispielsweise ein daemon sich um die Abwicklung von Kämpfen, ein anderer um das Arbarbeiten von Auktionen kümmern.

Persistenz

a) Persistenz ist nicht gegeben und muss zusätzlich implementiert werden.

b) Grundsätzlich sind die Daten persistent, möchte man jedoch aus Performancegründen Heap Tables nutzen, ist das wiederum nicht gegeben, allerdings zumindest von den daemon servern gekapselt, müsste aber dennoch zusätzlich implementiert werden. Man könnte aber um erst einmal anzufangen persistente Tabellen nutzen.

Skalierung

a) Die Speicheranforderungen des daemon skalieren linear mit der Menge an Gesamtdaten.

Komplizierter wird es hier, wenn man die Queue bearbeiten möchte, z.B. ein Element an einer bestimmten Position einfügen. Hier müsstem an um performant zu sein im Grunde eine Datenbank nachbauen, was in Perl aber nie an die Performance der echten DB kommen wird. Normalerweise wäre das Einfügen an einer beliebigen Position der lokalen Queue der einzige Anwendungsfall, jedoch einer der nicht unterschätzt werden sollte.

b) Die Speicheranforderungen des daemon skalieren linear mit der Menge an Daten im jeweiligen Zeitfenster der Polls. Sicherheitshalber wird man etwas Daten vorhalten wollen, um im Fehlerfall der Verbindung zur DB nicht sofort auf dem Trockenen zu sitzen. Ich würde sekündlich die Daten der nächsten zehn Sekunden pollen.

Das Bearbeiten der Queue ist hier absolut problemlos, da sich die Datenbank darum kümmert und WHERE, sowie ORDER BY alle normalen Anforderungen abfangen.

Implementierungsaufwand

Das bezieht sich jetzt rein auf die Kommunikation Backend <> daemon.

a) Komplett eigene Implementierung und Codewartung, allerdings auch nicht zu komplex, jedoch schon mit etwas Arbeit verbunden. Schätze mal 10-12 Stunden, um es sauber zu machen.

b) Weniger Aufwand, weil ich bestehende DB Connectoren nutzen kann. Schätze mal 3-5 Stunden, um es sauber zu machen.

Fazit

Ich tendiere zu Variante b), also die Datenbank als Zwischenschritt zu verwenden, weil es einfach Arbeit spart und bewährte Technologie nutzt. Allerdings wäre Clustering komplizierter zu realisieren.

Eventqueue

Meine Idee ist sämtliche Events in einer zentralen Eventqueue abzuarbeiten. Ich bin mir noch nicht sicher, ob ich das Event selbst dabei serialisiere oder fremde Datenbanken referenziere, tendiere aus Performancegründen zu letzterem.

Im Grunde reicht also eine Zuordnung "event_id, event_time, event_type, event_params/event_foreignkey".

Der Eventqueue-Manager im Server würde also immer eine Liste der nächsten Events vorhalten und mit usleep / select pausieren bis das Event aktuell wird (könnte auf Microsekundenbasis geschrieben sein). Daraufhin würde er dispatchen und das Event wird abgearbeitet. Also nun zum nächsten großen Punkt.

Dispatching

Nun, was wäre am sinnvollsten? Fork ist recht performant, threads in Perl eher weniger (weil wie bei einem fork die gesamte Speicherstruktur des parent processes mit übernommen wird und noch weiterer Overhead dazu kommt). Ich habe selbst noch keinen scheduler geschrieben und kann das schlecht einschätzen, aber ich bin mir ziemlich sicher, dass es nicht gerade schlau wäre jedes einzelne Event zu forken. Dass die Events in sich selbst thread-safe sein müssen ist an dieser Stelle ja selbstverständlich. Dennoch wäre es u.U. möglich mehrere ähnliche events zusammenzufassen, jedoch relativ unrealistisch, weil sie zeitlich ja eher nicht zusammen fallen.

Wenn ich also an die Struktur von Software ala Apache denke, arbeitet man dort meist mit einer vorinstanziierten Menge an Threads, die jeweils mit der neuen aufgabe betraut werden. Ich gehe davon aus, dass ich am besten einen Pool an Threads erstelle (20?), an die ich jeweils meine Events dispatche, so dass der Scheduler weiterlaufen kann und die nächsten Events aus der Queue holt. Nur was mache ich, wenn der Threadpool erschöpft und alle Prozesse beschäftigt sind? Wartet die Queue? Erstelle ich neue Threads? Bau ich die daraufhin wieder ab, oder behalte ich einen größeren Pool? Soll das System selbstständig lernen? Bin für Meinungen und vor allem für Erfahrungsberichte sehr dankbar.

Nun meine weiteren Fragen:

- welches Kommunikationsmodell würdet ihr wählen? weshalb?

- denkt ihr das Ganze ist so durchdacht oder hab ich Denkfehler drin?

- fehlt etwas Wichtiges?

- Wie realisiere ich das Threading/Forking zum Dispatchen am besten?

- Habt ihr sonstige Anmerkungen?

Danke für eure Aufmerksamkeit und ich bitte um Kommentare. ;)

gepostet vor 16 Jahre, 2 Monate von TheUndeadable

Erstmal nur eine kurze Antwort, eine längere Antwort wird bei Bedarf folgen.

Da ich das Problem prinzipiell vermeiden wollte, mache ich alles In-Process. Von Datenbank über Spiellogik bis hin zum Webserver. In Zeiten der sicheren/managed Programmierung und 64-Bit-Betriebssystemen sehe ich da keine großen Hindernisse. Beim alten Projekt habe ich ein Pollingverfahren eingesetzt, dass sehr gut funktioniert hat. Allerdings kam das Spiel niemals in Größenordnungen, bei denen Clustering notwendig sein wird.

In-Process scheitert natürlich völlig bei dem Bedarf an Clustering. Mehr Prozessoren geht ab einer bestimmten Zahl nicht mehr. Auch bei getrennten Frameworks ist eine komplette In-Process-Behandlung nicht möglich.

Ich persönlich habe eine zentrale Eventqueue, dessen Abarbeitung ich bei Bedarf anhalten oder fortsetzen kann. So habe ich zentral alle Zeit-Elemente gespeichert und brauch nicht mir die Elemente aus unterschiedlichen Punkten zusammensuchen. Da ich nicht auf relationaler Datenbankbasis, sondern auf OOP-Basis (auch persistenz auf OOP-Ebene) arbeite, brauche ich diese unsägliche 'params'-Spalte nicht, die im Prinzip nichts anderes als eine Serialisierung ist.

Zum Thema Dispatchen:

Diese habe ich komplett linearisiert, da ich unter allen Umständen vermeiden möchte, dass Ereignisse in falscher zeitlicher Reihenfolge abgehandelt werden.

Triviales Beispiel: Trupp greift an, Zweiter Trupp holt sich eine Sekunde später die Rohstoffe. Sollte ein Multithreading stattfinden, so kann es sein, dass der Kampf noch berechnet wird und der zweite Trupp gnadenlos ins Verderben rennt. Natürlich kann man dieses Problem durch Locking des Rohstofflagers/Stadt/Spielers beheben, aber momentan bestand dort für mich kein Bedarf.

Zum Thema Threading:

Ich nutze einen Threadpool, der von meiner Laufzeitumgebung zur Verfügung gestellt wird. Dieser instantiiert ebenso wie der Apache eine Reihe von Threads vor, die dann vom internen Webserver und anderen asynchronen Operationen genutzt werden. Vorteil des Verfahren: Wartet einer der internen Threads auf Datenbank/Dateisystem, so werden die 'physikalischen' Threads an andere Methoden weitergegeben. Es findet also ein Threading im Threading statt. Bei Bedarf werden bis zu einer konfigurierbaren Anzahl weitere Threads erzeugt. Ich erinnere mich an die Werte 50 arbeitende Threads und 2.000 logische E/A-Threads. Aber ohne Gewähr.

Forks gibt es in meiner Welt nicht ;-). Und ich halte Forks auch eher für ein Relikt vergangener Tage, da sie mir einfach zu dreckig erscheinen. Dies ist aber eine subjektive Wahrnehmung und soll wahrscheinlich nicht in diesem Thread stark behandelt werden.

gepostet vor 16 Jahre, 2 Monate von exe

Original von Kallisti

Kommunikation

a) Backend und daemon sprechen direkt miteinander. Die Kommunikation ist also instant und der Server weiss sofort was los ist, ohne sich selbst um die Informationen kümmern zu müssen. Es fallen IO Operationen für sockets/pipes an. Das ist zwar bei Datenbanken auch so, aber die sind professionell programmiert und stark optimiert, und es ist zu erwarten ist, dass mein Perl Code langsamer performt.

Eine direkte Socket-Kommunikation zu deinem Daemon wird mit Sicherheit deutlich schneller sein als eine Kommunikation über die Datenbank. Bei einer direkten Kommunikation schiebst du ein paar Byte Jobdaten in deinen Daemon welcher die Jobdaten in eine Queue einsortiert. Bei der Datenbank kommt erstmal der SQL-Parser zum Zuge, dann der Optimizer, dann werden die Daten auf Platte geschrieben und erst dann sind sie in deiner Eventqueue einsortiert. Und das wird auf jedenfall langsamer sein weil die Datenbank hier einen massiven Overhead einführt. Nur weil am anderen Ende eine Datenbank lauscht ist ein write() auf einen Socket ja nicht plötzlich auf magische Art und Weise vielfach so schnell ...

b) Das Backend schreibt erst einmal in die Datenbank, der Server pollt regelmäßig aus der Datenbank. Das Polling ist ein Mehraufwand und es kann Szenarien geben in denen das für den User zu einer Verzögerung führt, wenn das Polling Interval zu groß ist. Pollt man jedoch sekündlich, sollte das nicht mehr auffallen und man täuscht Echtzeit vor. Sekündliche Polls sind natürlich eine Mehrbelastung, allerdings ist die Datenbank optimiert, die Eventqueue hat indexierte Keys, daher dürfte der Performance Impact gering ausfallen und je mehr das System nach oben skaliert, umso geringer wird der Anteil des Pollings.

Eine priority Queue im RAM ist trotzdem schneller als der Umweg über die Datenbank. Indexierte Keys brauchst du nicht weil du deine Eventqueue sowieso nach Ablaufdatum sortiert hast und immer nur das erste Element in der Queue ausliest. Und eine Queue im RAM durchzusortieren ist auch nicht langsamer als wenn eine Datenbank das macht. Die macht da auch nicht viel anders als die normalen Sortieralgorithmen die jede Programmiersprache schon in seinem Funktionsumfang hat.

Clustering

a) Die direkte Kommunikation erlaubt es einfach weitere daemon Server aufzusetzen, sofern das ganze über sockets läuft. Jeder daemon Server könnte ohne Mehraufwand das komplette Repertoire an Funktionen abdecken, sofern das Dispatching per se erst einmal stateless ist. Wenn der Server jedoch aus Performancegründen selbst Informationen vorhält, wird das komplizierter.

b) Man kann jederzeit weitere Datenbank Server hinzufügen um hier Last abzufangen. Allerdings ist es schwieriger den daemon zu clustern, da ja kein einfacher select auf die Eventqueue mehr ausreicht, weil sonst die verschiedenen daemons dieselben Daten abarbeiten würden. Das heißt man müsste entweder mehrere verschiedene Queue Datenbanken haben oder innerhalb einer Datenbank differenzieren. Dann könnte beispielsweise ein daemon sich um die Abwicklung von Kämpfen, ein anderer um das Arbarbeiten von Auktionen kümmern.

Eine Datenbank clustern ist einfacher gesagt als getan. Relationale Datenbanken sind denkbar schlecht zum Clustern. Im Endeffekt rentiert sich das nur wenn du fast ausschliesslich SELECTs auf die Datenbank hast. Da du in einem Browsergame aber auch eine hohe Schreibrate hast bringt dir das Clustering relativ wenig weil mit mehreren Datenbankservern auch alle Schreibzugriffe repliziert werden müssen und nach wie vor jeden Datenbankserver treffen - was den größten Block der Datenbankbelastung ausmacht.

Mehrere Eventsysteme laufen zu lassen ist, davon abgesehen, kein großes Problem. Die meisten Events in dem Browserspiel werden an einen bestimmten Ort gebunden sein (Planet, Kontinent, Land, Stadt, whatever). Damit kannst du jedes Eventsystem für eine bestimmte Bandbreite an Orten zuständig sein lassen und verhinderst damit auch das von TheUndeadable beschriebene Problem mit zusammengehörenden Events welche den gleichen Ort treffen. Die Aufteilung der Events ist dann nicht mehr wirklich kompliziert und kann über eine einfache Modulo-Operation stattfinden:

SQL:

SELECT * FROM event_queue WHERE location_id % $processCount = $myId

 Wobei $processCount die Anzahl der laufenden Eventsysteme ist und $myId die Nummer des abfragenden Eventsystems.

Persistenz

a) Persistenz ist nicht gegeben und muss zusätzlich implementiert werden.

b) Grundsätzlich sind die Daten persistent, möchte man jedoch aus Performancegründen Heap Tables nutzen, ist das wiederum nicht gegeben, allerdings zumindest von den daemon servern gekapselt, müsste aber dennoch zusätzlich implementiert werden. Man könnte aber um erst einmal anzufangen persistente Tabellen nutzen.

Du kannst auch eine Eventqueue auf Festplatte serialisieren oder, alternativ, die Events trotzdem in die Datenbank einfügen um die Daten bei einem Crash nicht zu verlieren. Oder du nutzt auf dem Eventsystem eine embedded Datenbank wie BerkeleyDB (http://search.cpan.org/~pmqs/BerkeleyDB-0.34/BerkeleyDB.pod) um die Queue zu serialisieren. Spart Implementierungsaufwand und ist auch deutlich schneller als ein fettes DBMS wie MySQL/PostgreSQL.

Skalierung

a) Die Speicheranforderungen des daemon skalieren linear mit der Menge an Gesamtdaten.

Komplizierter wird es hier, wenn man die Queue bearbeiten möchte, z.B. ein Element an einer bestimmten Position einfügen. Hier müsstem an um performant zu sein im Grunde eine Datenbank nachbauen, was in Perl aber nie an die Performance der echten DB kommen wird. Normalerweise wäre das Einfügen an einer beliebigen Position der lokalen Queue der einzige Anwendungsfall, jedoch einer der nicht unterschätzt werden sollte.

Das ist ein einfacher Sortieralgorithmus der in Perl nicht wesentlich langsamer ist als in einer Datenbank. Ich glaube du überschätzt ein bisschen die Geschwindigkeit von relationalen Datenbanken. Genau genommen sind die Datenbanken für den von dir angedachten Zweck keineswegs schnell sondern im Gegenteil stinklangsam. Du hast in einer Datenbank eine Menge Overhead (SQL-Parsen, Optimieren, Transaktionssicherheit/Crashsicherheit von Daten (explizite Flushs auf Festplatte), Indexierung etc.pp.) der dir für eine einfache Eventqueue in deinem Eventsystem gar nichts bringt ausser Zeitverlust. Wenn du eine priority Queue im RAM liegen hast musst du bei einem neuen Event nur dieses eine Event an der passenden Stelle einfügen da die Queue ansonsten immer passend sortier ist. Bei der Datenbank sortierst du die gesamte Queue bei jedem Poll (also jede Sekunde).

Dispatching

Nun, was wäre am sinnvollsten? Fork ist recht performant, threads in Perl eher weniger (weil wie bei einem fork die gesamte Speicherstruktur des parent processes mit übernommen wird und noch weiterer Overhead dazu kommt). Ich habe selbst noch keinen scheduler geschrieben und kann das schlecht einschätzen, aber ich bin mir ziemlich sicher, dass es nicht gerade schlau wäre jedes einzelne Event zu forken. Dass die Events in sich selbst thread-safe sein müssen ist an dieser Stelle ja selbstverständlich. Dennoch wäre es u.U. möglich mehrere ähnliche events zusammenzufassen, jedoch relativ unrealistisch, weil sie zeitlich ja eher nicht zusammen fallen.

Wenn ich also an die Struktur von Software ala Apache denke, arbeitet man dort meist mit einer vorinstanziierten Menge an Threads, die jeweils mit der neuen aufgabe betraut werden. Ich gehe davon aus, dass ich am besten einen Pool an Threads erstelle (20?), an die ich jeweils meine Events dispatche, so dass der Scheduler weiterlaufen kann und die nächsten Events aus der Queue holt. Nur was mache ich, wenn der Threadpool erschöpft und alle Prozesse beschäftigt sind? Wartet die Queue? Erstelle ich neue Threads? Bau ich die daraufhin wieder ab, oder behalte ich einen größeren Pool? Soll das System selbstständig lernen? Bin für Meinungen und vor allem für Erfahrungsberichte sehr dankbar.

Dir wird in der Praxis nicht von jetzt auf gleich mal der Threadpool oder Prozesspool erschöpft sein. Deine Spielerzahlen, und damit die Eventrate, steigt eher gemächlich an, wodurch du auch kein selbstlernendes System benötigst sondern immer noch eine manuelle Administrationsentscheidung treffen kannst: mehr Server oder mehr Threads/Prozesse oder bessere Hardware? Das ist dann der Fall wenn du merkst das zu Spitzenzeiten dein Eventsystem lagt.

Nun meine weiteren Fragen:

- welches Kommunikationsmodell würdet ihr wählen? weshalb?

Ich würde eher die direkte Kommunikation über Sockets nehmen. Das ist nicht wirklich kompliziert zu implementieren und spart dir den Umweg über die Datenbank. Von Threads würde ich in Perl eher absehen - es sei denn es wurde in den letzten 12 Monaten eine vernünftige Threadingimplementierung geschrieben welche nicht auf Forks basiert.

- Wie realisiere ich das Threading/Forking zum Dispatchen am besten?

Ich würde einen Masterprozess machen welcher eine Anzahl von Childs forkt und sich ansonsten nur darum kümmert eingehende Jobs an die Childs weiterzuleiten. Da du in Perl programmierst wird Threading sowieso keine Option sein. Vorteil daran ist, dass der Masterprozess damit ziemlich schlank bleibt und du nicht viel RAM durch das Forken verbrauchst. Und das System ist deutlich stabiler als ein Threadingmodell. Wenn dir ein Child abstürzt kannst du es einfach neu Forken und es reisst nicht, wie beim Threading, eventuell den Rest der Anwendung noch mit.

Btw: benutzt du irgendwelche speziellen Frameworks für dein MVC in Perl?

gepostet vor 16 Jahre, 2 Monate von Kallisti

Erst einmal ein dickes Dankeschoen fuer eure umfangreichen Kommentare. Das ist schon mehr als ich erwartet habe. :)

Ich hatte wohl wirklich den Overhead eines relationalen DBMS unterschaetzt.

Ortsgebundene Events sind bei mir nicht so einfach, allerdings muss man ja gar nicht unterscheiden, wenn man die direkte Socket Kommunikation waehlt. ;) Denn in dem Fall koennte man einfach bei jedem Eventqueue push random einen Server auswaehlen und haette bereits die simpelste Form von Load Balancing. Oder man nutzt etwas wie http://search.cpan.org/~wsnyder/Schedule-Load-3.052/Load.pm um nach dem dispatchen zu balancen (nur beim herumstoebern im CPAN entdeckt, ob es wirklich applikabel ist, waere eine andere Frage), denn die Queueverwaltung selbst sollte eigentlich in der Lage sein zig tausend User zu verarbeiten. Ich denke da stehen mir schon alle Moeglichkeiten offen.

Die Frage waere nun, wie ich Interprozesskommunikation in Perl regle. Ich habe bisher schon einmal mit threads::shared gearbeitet, aber wie du schreibst ist das alles andere als optimal.

Ich denke die einzige Chance ist wohl eine Endlosschleife zu haben, die in definierten Intervallen per IO::Select ueber die offenen Sockets switched und nach neuen Daten Ausschau haelt, die dann in die Queue sortiert werden. Am besten waere es wohl, die Socket Selects selbst wie ein queue event zu verarbeiten, oder? Ich benoetige ja die neuen Queue Daten im selben Prozess, der eben auch die Queue managed.. d.h. ein externer Server bringt mir herzlich wenig, weil ich dann wiederum irgendwie die Informationen in meinen Queue Prozess bringen muss.

Und wie kommuniziere ich mit den Worker forks, die die Events dann verarbeiten sollen? Wiederum named/pipes oder sockets nehme ich an, wobei es hier einfacher ist, weil die Worker durchweg lauschen koennen und im Gegensatz zur Queue selbst keine andere Aufgabe haben, solang sie nicht arbeiten.

Als MVC Framework nutze ich Catalyst. Das ist ziemlich aehnlich wie RoR oder phpcake und quasi der Nachfolger von Maypole. Die Entscheidung die Clientseite komplett ueber Javascript und JSON zu regeln und keine traditionellen HTML Views zu nutzen habe ich aber erst kuerzlich gefaellt.

Bin mit dem Ganzen noch ziemlich am Anfang, wobei ich viel Zeit in Planung, Gamedesign und Prototypen investiert habe, so dass ich hoffentlich recht schnell voran komme, sobald das Grundgeruest steht (momentan harpert es eher an ein paar Javascripts).

gepostet vor 16 Jahre, 2 Monate von exe

Original von Kallisti

Die Frage waere nun, wie ich Interprozesskommunikation in Perl regle. Ich habe bisher schon einmal mit threads::shared gearbeitet, aber wie du schreibst ist das alles andere als optimal.

Das letzte Mal als ich mit Threads und Perl zu tun hatte war das Problem, dass man bei geshareten Datenstrukturen (Hash/Liste) jedes Element einzeln sharen musste, was ein ziemlicher Umstand ist und enorm fehleranfällig. Ich würde vom Threading daher komplett absehen und auf Forks zurückgreifen. Afair bauen die Threading-Implementierungen in Perl sowieso nur auf Forks auf und machen intern ein ziemlich hässliches synchronisieren der Zustände über Shared Memory.

Für die Interprozesskommunikation würde ich, auf einem lokalen System Unix Sockets nehmen, wenn die Workerprozesse langlebig sind. Unix Sockets brauchen etwas länger zum Aufbauen als Shared Memory, haben dafür aber einen vielfach höheren Datendurchsatz wenn sie mal stehen. Bei sehr kurzlebigen Childs würde ich SysV Message Queues verwenden. Die haben nicht den Durchsatz von Unix Sockets, lassen sich dafür aber wesentlich schneller aufbauen. Wenn das Eventsystem auf mehreren Rechnern laufen soll bleiben sowieso nur Netzwerk-Sockets übrig. Vorteil an Sockets und Message Queues ist, dass die Childs einfach an der Queue/dem Socket hängen und Blocken können bis neue Jobs eingehen. Da brauchst du also auch kein Polling vom Masterprozess.

Ich denke die einzige Chance ist wohl eine Endlosschleife zu haben, die in definierten Intervallen per IO::Select ueber die offenen Sockets switched und nach neuen Daten Ausschau haelt, die dann in die Queue sortiert werden. Am besten waere es wohl, die Socket Selects selbst wie ein queue event zu verarbeiten, oder? Ich benoetige ja die neuen Queue Daten im selben Prozess, der eben auch die Queue managed.. d.h. ein externer Server bringt mir herzlich wenig, weil ich dann wiederum irgendwie die Informationen in meinen Queue Prozess bringen muss.

Der Masterprozess bräuchte wohl definitiv eine Liste von offenen Sockets, da er ja von mehreren Apache Childs parallel zugegriffen wird. Auf die offenen Sockets würde ich einfach einen blockierenden select() aufruf machen, so dass der Prozess blockt bis ein neuer Job eingeht und an einen Worker verteilt werden muss.

Und wie kommuniziere ich mit den Worker forks, die die Events dann verarbeiten sollen? Wiederum named/pipes oder sockets nehme ich an, wobei es hier einfacher ist, weil die Worker durchweg lauschen koennen und im Gegensatz zur Queue selbst keine andere Aufgabe haben, solang sie nicht arbeiten.

Wie oben geschrieben: Sockets oder IPC Message Queues. Siehe http://perldoc.perl.org/perlipc.html

Prinzipiell könnte der Aufbau dann so aussehen: du hast einen Master welcher seine Worker forkt und ansonsten nur auf die offenen Sockets von den Apache Childs select()ed. Zu jedem Worker hast du entweder einen Unix/TCP-Socket offen oder du verwendest eine Message Queue für alle Childs (über die message types kannst du eine Queue für alle Worker verwenden). Wenn der Master ein Event kriegt sucht er sich den passenden Worker raus und schiebt den Job über die Queue oder den Socket an den Worker. Der bearbeitet das ganze und schreibt die Ergebnisse in die DB.

Eine Überlegung wäre vielleicht auch sowas wie POE (http://search.cpan.org/~rcaputo/POE-1.003/lib/POE.pm) zu verwenden. Ist halt mit etwas Einarbeitungsaufwand verbunden, da das doch ein recht umfangreiches System ist. Dafür hast du dein ganzes Multitasking und IPC schon fertig implementiert.

gepostet vor 16 Jahre, 2 Monate von Kallisti

Es gibt mittlerweile eine Funktion in threads::shared mit der man z.B. einen Hash oder ein Array komplett sharen kann (shared_clone), es wird nur bei jeder Zuweisung ein Aufruf faellig. Aber Sockets sind mir generell auch lieber.

Jo, so hatte ich es mir auch gedacht, nur das schwierige ist ja, dass ich die eingehenden Events nicht direkt weiterleiten kann, sondern im Eventqueue Manager erst einmal sammeln und sortieren muss und dann quasi wie eine Art Cronjob zur richtigen Zeit aufrufe. Dafuer hatte ich mir eine Endlosschleife vorgestellt, die eben select/usleep macht, bis das naechste Event ansteht und es dann dispatcht.

Dadurch, dass ich nun aber gleichzeitig einen listening socket server im selben Prozess brauche, ueber welchen das backend die neuen Queue Events einschiebt, ist das nicht mehr ganz so trivial.

Aber ich denke, es gibt da keine andere Loesung, als select und das staendige Wechseln zwischen den listening sockets waehrend die Queue parallel dazu laeuft.. d.h. ich habe nur eine Schleife in der beide Vorgaenge passieren muessen. Dadurch kann es aber passieren, dass das Einlesen neuer Events die Verarbeitung anstehender Events blockiert.

Insgesamt sieht es ja so aus:

Client <--JSON--> Backend --SOCKET--> Daemon --SOCKET--> Worker --SOCKET--> Database

Nun muss der Daemon also die Sockets zum Backend, sowie die Sockets der Worker managen. letztere sind trivial, da hier der Daemon jederzeit "weiss" wann Daten anfallen.

Nur die parallele Verwaltung von eigehenden Daten und den Events der Queue bereitet mir noch Unsicherheiten. Denke aber, dass es gar nicht anders geht, als eben quasi auch ein Event zu definieren, das regelmaessig wiederkehrt und das "Polling" der Daten aus den existierenden Sockets uebernimmt. Dann am besten die Byte-Laenge der Events vor jedes Packet haengen (ich wusste doch, es wuerde sich irgendwann mal auszahlen einen clientless Diablo 2 Bot anzufangen xD), so dass ich unbuffered sysread nutzen kann und mit variabler Argumentenliste hat Perl ja eh kein Problem. :)

gepostet vor 16 Jahre, 2 Monate von exe

 Original von Kallisti

Jo, so hatte ich es mir auch gedacht, nur das schwierige ist ja, dass ich die eingehenden Events nicht direkt weiterleiten kann, sondern im Eventqueue Manager erst einmal sammeln und sortieren muss und dann quasi wie eine Art Cronjob zur richtigen Zeit aufrufe. Dafuer hatte ich mir eine Endlosschleife vorgestellt, die eben select/usleep macht, bis das naechste Event ansteht und es dann dispatcht.

Du kannst beim select auch einen Timeout angeben. Wenn dein Eventsystem eine Auflösung von 1 Sekunde hat machst du halt einen 1-sekündigen Timeout nach dem du dann alle abgelaufenen Events an die Worker weiterreichst. Dann hast du eine Eventschleife welche einmal pro Sekunde Events auslöst und ansonsten eben auf neue Daten wartet.

gepostet vor 16 Jahre, 2 Monate von Kallisti

Ich wollte es aber im Milli- oder gar Microsekundenbereich realisieren. xD Aber das mit dem Timeout ist klar und der akzeptiert ja auch fractional seconds.

Jau, aber ich denke das bekomm ich hin. Wenn ich die Zeit finde, ein wenig draufloszuhacken, poste ich mal nen proof of concept Code hier, dann könnten wir den vielleicht mal analysieren bzw. ihr dürft mir sagen ob das okay ist, oder ich etwas verkehrt gemacht habe / besser machen könnte.

gepostet vor 16 Jahre, 2 Monate von exe

Ich rechne bei mir intern auch in Millisekunden weil nunmal alle Timer und Timeoutangaben in Java in Millisekunden abgegeben werden. Daher speicher ich auch sämtliche Timestamps in Millisekunden. Im Spiel selber macht eine Auflösung unter einer Sekunde aber keinen Sinn mehr, von daher kann man es sich auch leisten das Eventdispatching im Sekundentakt "ticken" zu lassen.

Davon abgesehen kannst du im Millisekundenbereich auch gar nicht exakt rechnen solange du kein Realtimesystem hast. Alleine zwischen Abnahme des Timestamps im Apache Child und dem Queuen des Events im Eventsystem vergehen schon mehrere Millisekunden. Von eventuellen Abweichungen der Serveruhren im Millisekundenbereich mal abgesehen.

Von daher würde ich mir das rechnen in Millisekunden, wenns um Genauigkeit geht, von vornerein sparen.

gepostet vor 16 Jahre, 2 Monate von Kallisti

Soo, dann mal ein Update von mir.

http://pastebin.com/m707d9e70

Das ist jetzt der aktuelle Stand der Dinge.

  • lokaler TCP Server, ueber den Clients neue Events einhaengen koennen 
  • das Ganze mit einer Art RPC ueber PoCo IKC, der Client bekommt also auch Feedback
  • Jobs die in Cron-Manier zu bestimmten Zeitpunkten abgearbeitet werden (inkl. Konfiguration per Cron Syntax)
  • Anstehende Events werden der Reihe nach von einer begrenzten Zahl von Workern abgearbeitet
  • Logische Trennung in "Sessions" durch Event-basierte Programmierung
  • Ordentliches Logging / Dumping, sowie Kommentare (noch kein POD, erst wenn ich es am Ende modularisiere, das kommt aber erst, wenn soweit alles fertig ist)

Und all das in 200 Zeilen Code. ;) CPAN und POE machen es moeglich. Deshalb liebe ich Perl. xD In Sachen POE bin ich allerdings selbst noch ein ziemlicher Rookie, habe es bislang noch nie benutzt. Das Callback von der Jobqueue bei Erfuellung eines Auftrages klappt so weit noch nicht, da muesste ich noch einmal nachhaken. Sind noch ein paar Code Segmente unfertig / noch nicht in Benutzung.

Ich tendiere allerdings ein wenig dazu eher zu etwas wie http://poe.perl.org/?POE_Cookbook/Child_Processes_3 zu wechseln, um die Worker in anderen Prozessen zu haben, damit die Queue auch bei groesseren Berechnungen weiter bearbeitet werden kann. Andererseits ist die Frage ob man das wirklich moechte, weil man dann ja riskiert, dass die Reihenfolge durcheinander geraet. Ansonsten limitiert man aber natuerlich die Performance auf Multicore Systemen, wobei ich davon ausgehe, dass sowieso immer mehr als genug andere Dinge laufen und dieser Server hier gut genug skalieren sollte und dabei das geringste Problem darstellt.

Immerhin funktioniert es nun erst einmal, eine Umstellung sollte aufgrund der grossen Abstraktion kein Problem darstellen und auch sehr spaet noch moeglich sein.

Die Eventqueue poste ich mal nicht hier, denke die API ist selbsterklaerend und das Ding ist auch noch nicht ordentlich fertig. Momentan sortiere ich das Array mit den Events bei jedem Hinzufuegen neu, anstatt einen balanced tree oder so zu verwenden. Ist aber durch OOP und Kapselung problemlos spaeter austauschbar.

gepostet vor 16 Jahre, 2 Monate von exe

Wenn du langlebige Events hast macht es auf jedenfall Sinn auf eigene Prozesse für die Worker zu setzen, da POE selbst ja nur kooperatives Multitasking macht.

Schön, das es soweit so gut geklappt hat. Ich hab bisher auch nicht wirklich mit POE gearbeitet ;)

Auf diese Diskussion antworten