Multithreaded Server - Design Guidelines?

[nwp3]

Um Multithreading sinnvoll nutzen zu können brauchst du voneinander getrennte Aufgaben. Ein Netzwerkthread und ein Spiellogikthread hört sich intuitiv gut an, ist es aber nicht, da diese beiden Threads sehr eng miteinander verbunden sind, zumindest wenn du kein sekundenlanges Delay in Kauf nehmen willst.
Ich kennen mich mit Minecraft nicht so aus. Sind die Welten nicht unabhängig voneinander? Man kann doch von einer Welt nicht auf eine andere Welt Einfluss nehmen, oder? Das könnte man per Thread ausdrücken, aber per Prozess wäre einfacher und sicherer.
Das mit den Entity-Reihenfolgen habe ich nicht verstanden. Wieso kann man nicht erst den Spieler löschen und dann auf der anderen Welt neu erstellen?

Fürs nächste Mal würde ich versuchen voneinander möglichst unabhängige Aufgaben zu identifizieren und nur dafür Threads zu benutzen. Das ist nicht einfach. Weiterhin würde ich nicht vor Synchronisation zurückschrecken. Es sind nicht Mutexe die dir die Performance kaputt machen, es ist der Fakt, dass Threads synchronisiert werden müssen. Wenn du Contention hast bist du verloren und musst dein Design ändern, ob du die Performance per Mutex, Atomic oder Data Race kaputt machst ist egal.

Ahmdals Gesetz gibt dir eine obere Schranke für den Speedup durch Multithreading. Das ist viel weniger als man denkt. Wenn man den Synchronisationsoverhead mit einrechnet gibt es eine gewisse Chance, dass ein 100% ausgelasteter Core und sieben Cores mit 0% Auslastung bereits optimal ist.

Ich hatte mir mal was in der Richtung überlegt. Die Grundidee ist das Spielfeld in Abschnitte aufzuteilen, deren Größe etwa 10x die der Sichtbarkeitsweite entspricht. Ziel ist voneinander unabhängige Abschnitte zu bekommen die parallel abgearbeitet werden können. In der Oberwelt klappt das nicht so gut, aber Höhlen und Häuser ohne Löcher und Fenster könnten sowas bieten. Das Problem dabei ist immer dass man an der Grenze zwischen zwei Abschnitten stehen kann und dann wird es ineffizient. Man muss die Grenzen irgendwie dynamisch verschieben können.

Eine andere Idee ist Validierung und Ausführung zu trennen. Beispiel: Ein Spieler nimmt Gold aus seinem Inventar. Es muss nun geprüft werden, ob der Spieler überhaupt Gold im Inventar hat und es muss an andere Spieler in Sichtweite geschickt werden, dass der Spieler jetzt Gold in der Hand hat.
Ein Thread schickt die "Gold in der Hand"-Nachricht ohne Prüfung an andere Spieler und ein anderer Thread prüft das Inventar und kickt den Spieler wenn er schummelt. Gleiches gilt für durch Wände laufen und ähnliches. Damit sollte man Netzwerk- und Spiellogik ein bisschen trennen können.

Zuletzt würde ich async benutzen, damit man zwischen launch::async und launch::deferred wechseln kann. Macht etwas Aufwand es korrekt für beides hinzukriegen, gibt dir aber den Vorteil prüfen zu können, ob und wie viel die jeweiligen Threads bringen.

[Nathan]

Im neuesten Snapshot haben die Entwickler jede Dimension in einen eigenen Thread gepackt. AFAIK ist da aber sonst nicht viel mehr Multithreading.

[Kellerautomat]

nwp3 schrieb:

Ich kennen mich mit Minecraft nicht so aus. Sind die Welten nicht unabhängig voneinander? Man kann doch von einer Welt nicht auf eine andere Welt Einfluss nehmen, oder?

Die Welten sind im grossen und ganzen unabhaengig voneinander, ja. Allerdings kann es sein, dass jemand per Command auf andere Welten Einfluss nimmt, z.B. /tphere <player>, wenn <player> in einer anderen Welt ist. Das sollte man allerdings mit einem Task-Queue Modell noch irgendwie hinbekommen.

nwp3 schrieb:

Das könnte man per Thread ausdrücken, aber per Prozess wäre einfacher und sicherer.

Dass du hier jetzt Prozesse vorschlaegst, ueberrascht mich. Ich habe mich damit noch nie wirklich beschaeftigt, warum waere es einfacher und was sind die Vorteile? Wie siehts mit Kommunikation der Prozesse aus, wie in oben genannten Faellen?

nwp3 schrieb:

Das mit den Entity-Reihenfolgen habe ich nicht verstanden. Wieso kann man nicht erst den Spieler löschen und dann auf der anderen Welt neu erstellen?

Nun, mein Gedanke war, dass wenn ich zuerst die alte Entity loesche, in der Zeit zwischen dem Loeschen und dem Zuweisen der neuen Entity entweder der Client keine Entity hat, oder sein Entity-Zeiger auf ein nicht mehr vorhandenes Objekt zeigt. Das Problem gibt es bei der festen Reihenfolge nicht. Ist aber auch nicht so wichtig, ich hab ja schon rausgefunden, dass das Modell nicht funktioniert

nwp3 schrieb:

Fürs nächste Mal würde ich versuchen voneinander möglichst unabhängige Aufgaben zu identifizieren und nur dafür Threads zu benutzen. Das ist nicht einfach. Weiterhin würde ich nicht vor Synchronisation zurückschrecken. Es sind nicht Mutexe die dir die Performance kaputt machen, es ist der Fakt, dass Threads synchronisiert werden müssen. Wenn du Contention hast bist du verloren und musst dein Design ändern, ob du die Performance per Mutex, Atomic oder Data Race kaputt machst ist egal.

Das ergibt Sinn. Ich finde Mutexe halt ungut, weil sie Threading entgegenwirken (nur 1 Thread hat Zugriff). Deshalb versuche ich, diese moeglichst zu vermeiden.

nwp3 schrieb:

Ich hatte mir mal was in der Richtung überlegt. Die Grundidee ist das Spielfeld in Abschnitte aufzuteilen, deren Größe etwa 10x die der Sichtbarkeitsweite entspricht. Ziel ist voneinander unabhängige Abschnitte zu bekommen die parallel abgearbeitet werden können. In der Oberwelt klappt das nicht so gut, aber Höhlen und Häuser ohne Löcher und Fenster könnten sowas bieten. Das Problem dabei ist immer dass man an der Grenze zwischen zwei Abschnitten stehen kann und dann wird es ineffizient. Man muss die Grenzen irgendwie dynamisch verschieben können.

Daran habe ich auch schon gedacht, und wie du bereits gesagt hast, sind hier die Grenzen das Problem. Was man allerdings immer machen koennte, ist einzelne Aufgaben gezielt manuell auf mehrere Threads zu verteilen. Das ist unabhaengig vom restlichen Threading und koennte je nach Aufgabe etwas bringen.

nwp3 schrieb:

Eine andere Idee ist Validierung und Ausführung zu trennen. Beispiel: Ein Spieler nimmt Gold aus seinem Inventar. Es muss nun geprüft werden, ob der Spieler überhaupt Gold im Inventar hat und es muss an andere Spieler in Sichtweite geschickt werden, dass der Spieler jetzt Gold in der Hand hat.
Ein Thread schickt die "Gold in der Hand"-Nachricht ohne Prüfung an andere Spieler und ein anderer Thread prüft das Inventar und kickt den Spieler wenn er schummelt. Gleiches gilt für durch Wände laufen und ähnliches. Damit sollte man Netzwerk- und Spiellogik ein bisschen trennen können.

Ich fuerchte, dass das parallele Validieren durch den Kopieraufwand von Daten zunichte gemacht wird. Was ist beispielsweise, wenn ich Bewegungen validieren moechte? Dann muss ich die Welt um den Spieler kopieren.

nwp3 schrieb:

Zuletzt würde ich async benutzen, damit man zwischen launch::async und launch::deferred wechseln kann. Macht etwas Aufwand es korrekt für beides hinzukriegen, gibt dir aber den Vorteil prüfen zu können, ob und wie viel die jeweiligen Threads bringen.

Guter Tipp

Danke fuer deinen Post, hat mir auf jeden Fall etwas weitergeholfen. Ich habe mir jetzt ueberlegt, dass ich anstatt einen Netzwerk-Thread zu machen, die Clients einfach den World-Threads ihrer aktuellen Welt zuweise. Damit sollten Welt-interne Events gar keine Synchronisierung benoetigen und Cross-World Events werden wohl irgendwie durch einen globalen Mutex (global im Sinne von "fuer alle Welten") geloest.
Mein einziges Problem bei diesem Modell ist, dass ich keinen Plan habe, wie ich das designen soll. Ich habe im Moment Netzwerk und Simulation sehr sauber getrennt, wodurch ich vermutlich den Simulations-Teil wiederbenutzen kann. Bei diesem Modell waechst beides sehr stark zusammen. Eine World-Klasse haette dann irgendwie mit Netzwerk-IO zu tun, was mir absolut nicht ins Konzept passt. Findet ihr diesen Ansatz gut, und wie koennte man das loesen?

[volkard]

Kellerautomat schrieb:

Eine World-Klasse haette dann irgendwie mit Netzwerk-IO zu tun, was mir absolut nicht ins Konzept passt.

Bin jetzt nicht sicher. Also wenn sich in der Welt was ändert, bekommt es jeder angemeldete Observer(pattern) mit. Da weiß die Welt gar nix von Netzwerk-IO.

Pro Client ein Client-Thread? Das finde ich fein.

Alles Folgende ist vage Vermutung und wenns nicht passt, ists nicht schlimm. Vielleicht passt doch ein winziges Bißchen und DU kannst ne Anregung rausziehen.

Die parallel laufenden Welten-Threads verlangen jetzt von mir als Spieler, daß ich so Sachen versuche, wie "Verlixt schnell (per Makroplayer) Kiste öffnen, Ding nehmen, Welt wechseln, alte Welt kann Ding nicht an den weggesprungenen Char liefern (Exception flieg oder nicht), Ding bleibt in der Kiste, im Invetar isses aber schon und ist mitgehüpft, hab ein Doppelding und freue mich".

Weiß nicht, ob es sich lohnt oder gangbar ist, sowas genau zu synchronisieren, vielleicht hätte man dann einfach zu viele Locks nötig, vielleicht muss im Code nur immer die Reihenfolge so sein, daß ein Objekt immer erst genommen und dann gegeben wird. Vielleicht eine Interweltkommunikation (auch per Sockets) einführen, wo sich die Welten auch mal unterhalten können, welche Player gerade wo sind.

Dein Code macht mir ein wenig Angst.

noid switchWorld(Client& client, World& to)
{
    auto& from = client.entity->world;

    to.spawnTask(
        [=] (World& world)
        {
            auto entity = world.spawnPlayer(client.name());//Player jetzt in beiden Welten?
//Jetzt baut er aus seinen Uber-Ressis ein Uber-Tool. 
//Bekommt er in beiden Welten das Tool ins Inventar? 
            client.spawnTask(
                [=] (Client& client)
                {
                    auto oldPlayer = client.entity;
                    client.entity = entity;

                    from.spawnTask(
                        [=] (World& world)
                        {
                            world.despawnPlayer(oldPlayer);
                        }
                    );
                }
            );
        }
    );
}

Kenne Deinen Entwurf ja nicht genau. Kann sein, daß meine Befürchtung ohne jede Grundlage ist, weil andere Sachzwänge dazu führen, daß da nix schiefgehen kann. Ich würde irgendwie automatisch erst despawnen und dann erst in der neuen Welt spawnen. Vielleicht in den Player oder Client eine atomic Variable basteln, die sagt, auf welchem Server er gerade ist und nur (im Verlauf des Weltwechselns) damit garantieren, daß er nicht aus Versehen auf zweien sein kann.

[Kellerautomat]

volkard schrieb:

Kellerautomat schrieb:

Eine World-Klasse haette dann irgendwie mit Netzwerk-IO zu tun, was mir absolut nicht ins Konzept passt.

Bin jetzt nicht sicher. Also wenn sich in der Welt was ändert, bekommt es jeder angemeldete Observer(pattern) mit. Da weiß die Welt gar nix von Netzwerk-IO.

Observer ist ja schoen und gut, aber irgendjemand muss die Client Objekte auch besitzen. Die Frage ist: Wer?

volkard schrieb:

Pro Client ein Client-Thread? Das finde ich fein.

Das fuehrt vermutlich zu voelligem Chaos und skaliert zudem nicht besonders gut. Ich habe mir 1k concurrent players als untere Grenze gesetzt. Idealerweise moechte ich in den Bereich bis 5k skalieren koennen. Es gibt Server-Netzwerke, die in der Tat solche Userzahlen haben, das ist also kein unrealistisches Dahingerede. Ich kenne einen Admin eines solchen Netzwerkes persoenlich, die haben um die 50 Root-Server nur fuer Minecraft. Eine ordentliche Software koennte hier eine Menge Geld sparen.

volkard schrieb:

Die parallel laufenden Welten-Threads verlangen jetzt von mir als Spieler, daß ich so Sachen versuche, wie "Verlixt schnell (per Makroplayer) Kiste öffnen, Ding nehmen, Welt wechseln, alte Welt kann Ding nicht an den weggesprungenen Char liefern (Exception flieg oder nicht), Ding bleibt in der Kiste, im Invetar isses aber schon und ist mitgehüpft, hab ein Doppelding und freue mich".

Weiß nicht, ob es sich lohnt oder gangbar ist, sowas genau zu synchronisieren, vielleicht hätte man dann einfach zu viele Locks nötig, vielleicht muss im Code nur immer die Reihenfolge so sein, daß ein Objekt immer erst genommen und dann gegeben wird. Vielleicht eine Interweltkommunikation (auch per Sockets) einführen, wo sich die Welten auch mal unterhalten können, welche Player gerade wo sind.

In meinem neuen Modell waere sowas nicht moeglich. Das Event, ein Item rauszunehmen waere garantiert fertig abgeschlossen, bevor ich eine weitere Aktion taetigen kann wie teleportieren.

volkard schrieb:

Dein Code macht mir ein wenig Angst.

...

Kenne Deinen Entwurf ja nicht genau. Kann sein, daß meine Befürchtung ohne jede Grundlage ist, weil andere Sachzwänge dazu führen, daß da nix schiefgehen kann. Ich würde irgendwie automatisch erst despawnen und dann erst in der neuen Welt spawnen. Vielleicht in den Player oder Client eine atomic Variable basteln, die sagt, auf welchem Server er gerade ist und nur (im Verlauf des Weltwechselns) damit garantieren, daß er nicht aus Versehen auf zweien sein kann.

Der Code ist deshalb in der Hinsicht unproblematisch, weil immer nur eine einzige Entitaet mit dem Spieler assoziert sein kann. Heisst: Selbst wenn es 2 Entitaeten gibt, ist eine davon "unbenutzt".

[volkard]

Kellerautomat schrieb:

volkard schrieb:

Pro Client ein Client-Thread? Das finde ich fein.

Das fuehrt vermutlich zu voelligem Chaos und skaliert zudem nicht besonders gut.

Miss mal. Also 10000 Threads pro Sekunde kannste starten?
Mhhm.
Die Threads haben alle testhalber 60 geschlafen und das Hauptsytem hat davon nix gemerkt?

Falls beides wahr ist, wo sind Deine Bedenken, nicht wie in den 80-ern zu proggen? Die üblichem Tuts zu Netzwerken schreiben von üblichen Tuts zu netzwerken ab.

Es ist nicht Dein Job, hocheffiziente Algos zu finden wie man mit begrenzten Ressourcen (nur 4 Kernen) ohne jede Wartezeit alle Ressis voll auslastet. Da versuchen sich Hochschulprofesoren dran und scheitern zu 99-100%. Manchmal hat einer noch ein Mikrokleines Detail, wie man die Aufgaben noch besser verschränken kann um noch mehr Prozessorpower zu benutzen. Das veröffentlichen die dann. Ist mitunter saukompliziert. Teuer bezahlte bei MS oder/und gute bei Linux Leute klopfen das ins BS rein. So fett kannste gar nicht selber auf dem neuesten Stand sein. Und kannst auch nicht (bus auf wenige Ausnahmen) selber annähernd so effizient sein wie die Profis, was die Lastverteilung angeht. Und 1000000 Threads kann Dein BS doch locker, oder? Kann es 1000000 Sockets? Falls ja, sollte es Deine 1000 Spieler doch auch packen.

[Kellerautomat]

Meine Bedenken liegen nicht darin, dass der Scheduler zu viel zu tun haette, sondern schlicht an der Synchronisation, die dafuer noetig ware. Zudem sehe ich auch den Sinn nicht. Mit dem Modell, ueber das ich gerade nachdenke, sollte ich eigentlich recht gut voran kommen. Warum wuerdest du pro Client einen Thread erzeugen? Ich sehe die Motivation dahinter nicht.

[volkard]

Kellerautomat schrieb:

Meine Bedenken liegen nicht darin, dass der Scheduler zu viel zu tun haette, sondern schlicht an der Synchronisation, die dafuer noetig ware. Zudem sehe ich auch den Sinn nicht. Mit dem Modell, ueber das ich gerade nachdenke, sollte ich eigentlich recht gut voran kommen. Warum wuerdest du pro Client einen Thread erzeugen? Ich sehe die Motivation dahinter nicht.

Um das Kommunikationsprotokoll mit dem Client nicht als endlichen Automaten darstellen zu müssen, sondern schlicht als main() des Client-Threads oder deren Subfunktionen schlicht mit read() und write() arbeiten zu können. Es vereinfacht alles. Der Client kann beliebig Sachen machen und der ClientThread kann mit if/for/do und so reagieren und insbesondere read() bzw operator>> und sein Status liegt nicht als Variable vor, sondern wie üblich als Position im Code.

[Kellerautomat]

Ich hab kein Problem mit Automaten. Ich muss so oder so Event-Handling irgendwie bauen, da duerfte das relativ egal sein.

[DOSen]

volkard schrieb:

Pro Client ein Client-Thread? Das finde ich fein.

Das halte ich fuer keinen guten Ansatz, da man damit die Maschine komplett platt machen kann. Besser ist ein Threadpool, in den die Weltobjekte gequeuet werden koennen, wenn etwas zu tun ist. So ist die Abarbeitung der Anforderungen nach first-come-first-served fuer die Anfragen gesichert.

Mit einem Thread/client oeffnet man Denial of Service Attacken auf einfachste Art und Weise die Tuer, da man nicht nur die Anwendung, sondern direkt die ganze Maschine in die Knie zwingt.

[volkard]

DOSen schrieb:

volkard schrieb:

Pro Client ein Client-Thread? Das finde ich fein.

Das halte ich fuer keinen guten Ansatz, da man damit die Maschine komplett platt machen kann. Besser ist ein Threadpool, in den die Weltobjekte gequeuet werden koennen, wenn etwas zu tun ist. So ist die Abarbeitung der Anforderungen nach first-come-first-served fuer die Anfragen gesichert.

Mit einem Thread/client oeffnet man Denial of Service Attacken auf einfachste Art und Weise die Tuer, da man nicht nur die Anwendung, sondern direkt die ganze Maschine in die Knie zwingt.

Schlangenöl.

[DOSen]

volkard schrieb:

Schlangenöl.

Sehr konstruktiv.

Ich habe Deine Meinung ebenfalls mal vertreten musste mich aber in einem Test geschlagen geben (ein Kollege hat den Threadpool/Master-Worker-Queue Ansatz vertreten). Kurz: Die Realitaet hat mich eines Besseren belehrt (zumindest im bei mir gegebenen Szenario. YMMV)

Daher mein Vorschlag an Kellerautomat: Probier es einfach aus, in einem Hochlastszenario und nimm das, was am besten funktioniert.

[win32]

Unter Windows 32-Bit kann man nicht mal viel mehr als 1000 Threads erstellen.

[Kellerautomat]

win32 schrieb:

Unter Windows 32-Bit kann man nicht mal viel mehr als 1000 Threads erstellen.

Weder interessirt mich Windows, noch 32-Bit Systeme. :p

[nwp3]

Kellerautomat schrieb:

nwp3 schrieb:

Eine andere Idee ist Validierung und Ausführung zu trennen. Beispiel: Ein Spieler nimmt Gold aus seinem Inventar. Es muss nun geprüft werden, ob der Spieler überhaupt Gold im Inventar hat und es muss an andere Spieler in Sichtweite geschickt werden, dass der Spieler jetzt Gold in der Hand hat.
Ein Thread schickt die "Gold in der Hand"-Nachricht ohne Prüfung an andere Spieler und ein anderer Thread prüft das Inventar und kickt den Spieler wenn er schummelt. Gleiches gilt für durch Wände laufen und ähnliches. Damit sollte man Netzwerk- und Spiellogik ein bisschen trennen können.

Ich fuerchte, dass das parallele Validieren durch den Kopieraufwand von Daten zunichte gemacht wird. Was ist beispielsweise, wenn ich Bewegungen validieren moechte? Dann muss ich die Welt um den Spieler kopieren.

Daten kopieren ist natürlich Mist, lässt sich aber meiner Meinung nach auch vermeiden.
Für die Kollisionen kann man die Welt einmalig kopieren, aber mit 1 Bit pro Block für Hindernis oder nicht Hindernis. Vielleicht auch 2 Bit für Hindernis, kein Hindernis, Wasser/Lava und Blätter/Spinnenweben. Vielleicht lohnt sich der erhöhte Datenaufwand für die Laufzeit. Wahrscheinlich nicht. Bei anderen Dingen funktioniert das vielleicht besser: Ein Thread ist für die Spielwelt zuständig, ein anderer für das Inventar des Spielers. Beide sind aus Datensicht völlig unabhängig voneinander. Aber so super lange wird das Prüfen des Inventars nicht dauern. Eigentlich habe ich keine Ahnung was bei einem Minecraft-Server lange dauern soll.

Nathan schrieb:

Im neuesten Snapshot haben die Entwickler jede Dimension in einen eigenen Thread gepackt. AFAIK ist da aber sonst nicht viel mehr Multithreading.

Wie soll das denn gehen? Wir reden hier nicht on X-Y-Z als Dimensionen, oder?

volkard schrieb:

...

Es geht nicht darum hocheffiziente Algorithmen zu bauen die garantiert alle Ressourcen bestmöglich ausnutzen. Es soll doch nur ein Javaprogramm geschlagen werden. (richtig?)
Ein Thread pro Client ist riskant. Wenn der Rechner ausgelastet wird wird es schwierig Fairness zu garantieren. Ich weiß gerade nicht wie teuer ein Thread-Switch ist, aber davon hätte man dann recht viele.

Kellerautomat schrieb:

nwp3 schrieb:

Das könnte man per Thread ausdrücken, aber per Prozess wäre einfacher und sicherer.

Dass du hier jetzt Prozesse vorschlaegst, ueberrascht mich. Ich habe mich damit noch nie wirklich beschaeftigt, warum waere es einfacher und was sind die Vorteile? Wie siehts mit Kommunikation der Prozesse aus, wie in oben genannten Faellen?

Prozesse haben den großen Vorteil, dass sie untereinander keine Data Races haben. Das macht vieles sehr viel einfacher beim programmieren, weil man auf Kram wie Mutexe verzichten kann.
Außerdem hat man noch anderen Vorteile. Wenn jede Welt ein Prozess ist, dann kann man Prozesse/Welten unabhängig voneinander erschaffen, neu starten, abstürzen lassen, in VM's stecken und auf verschiedene Rechner verteilen. Den Teleport sollte man leicht implementieren können. Login und Logout brauchst du sowieso und ein Teleport ist unter der Haube nur ein Logout(aktuelleWelt) + Login(neueWelt).

Vielleicht funktioniert das doch mit den Bereichen: Man teilt die Welt in ~100³ große Blöcke ein. Außerdem hat man einen Threadpool und eine Messagequeue wo Aufträge drin stehen. Threads nehmen einen Auftrag, locken die benötigten Blöcke, bearbeiten sie, fügen ein Arbeitspaket "Sende Spielern meine gemachten Änderungen" und geben den Lock wieder frei. Man kann auch den Lock freigeben bevor man das Arbeitspaket hinzugefügt hat, aber dann ist die Ordnung nicht mehr garantiert, was man aber mit einer laufenden Nummer auf Clientseite reparieren kann.
Damit können mehrere Threads gleichzeitig an der Welt rumändern. Ich weiß nicht ob immer allen Spielern alle Änderungen geschickt werden oder nur Änderungen von sichtbaren Objekten. Letzteres wäre etwas aufwendiger, da man sich merken müsste welche Clients welche veralteten Blöcke haben.
Das skaliert gut solange Spieler sich nicht im selben Block aufhalten und daran rumhacken. Wenn sie es doch tun könnte man vielleicht einen Thread für den entsprechenden Block abstellen.
Außerdem kann man so einen Spaß machen wie eine Priority Queue für die Messagequeue nehmen. Nahe Blöcke haben höhere Priorität als Blöcke, die weit weg sind. Wenn ein Block ein Update bekommt bevor ein vorheriges Update für diesen Block geschickt wurde, dann wird das alte Update nicht geschickt. Wenn sich so viele Elemente in der Priority Queue ansammeln, dass sie ineffizient wird, dann hat man noch andere Sorgen.

[mmoprogger]

http://www.gamedev.net/topic/657588-mmos-and-modern-scaling-techniques/

[DOSen]

Hab's auf meinem core i5 (sandy bridge, 4GB Win7) und i7 (haswell 16GB Win8) getestet.

Simuliert habe ich 3000 Clients, die zyklisch Integer und Floating Point Operationen ausfuehren und dann jeweils 20ms nichts machen (also z.B. auf das naechste Netzwerkpaket warten, simuliert mit this_thread::sleep() ).

Einmal mit einem ThreadPool/Master-Worker-Queue und einmal mit 3000 Threads.

Ergebnis: Wie erwartet gibt es bei der Verarbeitungsleistung praktisch keinen Unterschied. In beiden Faellen war die CPU durch den Prozess mit 94%-97% bzw 96%-99% ausgelastet. Aber: Mit 3000 Threads ist die Maschine praktisch nicht mehr benutzbar gewesen. Habe testweise im Hintergrund einen InetRadioStream laufen lassen. Bei 3000 Threads hat man nur noch abgehackte Fetzen hoeren koennen, beim Threadpool lief alles ohne dropouts weiter.

Fazit: Fuer so etwas am besten also einen Master-Worker Ansatz nehmen.

[volkard]

DOSen schrieb:

Simuliert habe ich 3000 Clients, die zyklisch Integer und Floating Point Operationen ausfuehren und dann jeweils 20ms nichts machen (also z.B. auf das naechste Netzwerkpaket warten, simuliert mit this_thread::sleep() ).

Zeig mal den Code, dann teste ich hier auch mal, falls er auf Linux läuft.

[DOSen]

Volkard schrieb:

Zeig mal den Code, dann teste ich hier auch mal, falls er auf Linux läuft.

Da ich hier fuer den ThreadPool interne libs nutze, kann ich leider nicht den ganzen Code posten. Aber zumindest die Stueckwerke gehen (bitte nicht auf Schoenheit achten, ist schnell hingehackt)

Hauptprogramm

#include <ctime>
#include <algorithm>

#include <vector>
#include <iostream>
#include <thread>
#include <future>

#include "ThreadPool.h"
#include "Semaphore.h"
#include "PerformanceCounterWin32.h"

#include "DummyFunctorThreadPool.h"
#include "DummyFunctorAsync.h"

using namespace std;

const size_t numClients = 3000;
const size_t numActionCycles = 100;
const size_t numBurnCycles = 10000;
const size_t vecSize = 100;

const int startDelayInMilliseconds = 2000;
const int idleTimeInMilliseconds = 20;

Semaphore semTP(0);
Semaphore semAsync(0);

void startAsync()
{
	vector<shared_ptr<thread>> threads; // these threads will execute the DummyFunctorAsync operator() method

	for(int i = 0; i<numClients; ++i)
	{
		threads.emplace_back(make_shared<thread>(DummyFunctorAsync(&semAsync)));
	}
	for(int i = 0; i<numClients; ++i)
	{
		threads[i]->join();
	}

	cout << "started" << endl;
	semAsync.acquire(numClients);
	cout << "finished" << endl;
}

void startThreadPooled()
{
	ThreadPool tp(thread::hardware_concurrency()*2);

	// in a ThreadPool approach, a worker will be terminated when a task is finished and need to be
	// enqueued again
	for(int i = 0; i<numClients*numActionCycles; ++i)
	{
		tp.process(move(unique_ptr<DummyFunctor>(new DummyFunctor(&semTP))));
	}

	cout << "started" << endl;
	semTP.acquire(numClients*numActionCycles);

	cout << "finished" << endl;
}

int main() 
{
	PerformanceCounterWin32 perfCount;

	perfCount.startMeasurement();
	{
		startThreadPooled();
	}

	perfCount.queryCounter();
	{
		startAsync();
	}

	perfCount.queryCounter();

	cout << "ThreadPool took " << perfCount.getDeltaInSeconds(1, 2) << "\n";
	cout << "ASync took " << perfCount.getDeltaInSeconds(0, 1) << "\n";
	cout << endl;
}

DummFunctor fuer den ThreadPool
.h

#pragma once

#include <vector>
#include "ThreadPool.h"
#include "Semaphore.h"

#include "constants.h"

class DummyFunctor : public WorkItem
{
public:
	// intializes semaphore plus vector
	DummyFunctor(Semaphore* sem);
	DummyFunctor(DummyFunctor&& rhs);
	DummyFunctor& operator=(const DummyFunctor& rhs);

	// execute some actions in order to simulate a client
	void operator()();
protected:
	// method that does the processing using both integer and floating point
	void burnSomeCPUCycles();

	double sum;
	std::vector<double> vec;
	Semaphore* sem;
};

.cpp dazu

#include "DummyFunctorThreadPool.h"

#include <algorithm>
#include <random>
#include <vector>
#include <iostream>

using namespace std;

DummyFunctor::DummyFunctor(Semaphore* sem) : sum(0.0), vec(vecSize), sem(sem)
{
	mt19937 rng;

	generate(vec.begin(), vec.end(), rng);
}

DummyFunctor::DummyFunctor(DummyFunctor&& rhs)
{
	this->sum = rhs.sum;
	this->vec = rhs.vec;
	this->sem = rhs.sem;
}
DummyFunctor& DummyFunctor::operator=(const DummyFunctor& rhs)
{
	this->sum = rhs.sum;
	this->vec = rhs.vec;
	this->sem = rhs.sem;
	return *this;
}

void DummyFunctor::operator()()
{
	burnSomeCPUCycles();
	sem->release();
}

void DummyFunctor::burnSomeCPUCycles()
{
	//		this_thread::sleep_for(chrono::milliseconds(idleTimeInMilliseconds));
	for (int i=0; i<numBurnCycles; ++i)
	{
		sum += log(sin(vec[i%vecSize]));
	}
}

Dasselbe fuer den ASync Teil
.h

#pragma once

#include <vector>
#include "ThreadPool.h"
#include "Semaphore.h"

#include "constants.h"

#include "DummyFunctorThreadPool.h"

class DummyFunctorAsync : public DummyFunctor
{
public:
	DummyFunctorAsync(Semaphore* sem);
	DummyFunctorAsync(DummyFunctorAsync&& rhs);
	DummyFunctorAsync& operator=(const DummyFunctorAsync& rhs);

	void operator()();
};

.cpp

#include "DummyFunctorAsync.h"

using namespace std;
using namespace neotaix;

DummyFunctorAsync::DummyFunctorAsync(Semaphore* sem) : DummyFunctor(sem)
{
}

DummyFunctorAsync::DummyFunctorAsync(DummyFunctorAsync&& rhs) : DummyFunctor(rhs)
{
}

void DummyFunctorAsync::operator()()
{
	// wait for all threads to start up. This is required here because otherwise
	// processing will start immediately leading to a contention where not all threads 
	// can started completely before the first are finishing
	this_thread::sleep_for(chrono::milliseconds(startDelayInMilliseconds));
	// the thread stays active until all actions are done
	for(int i = 0; i < numActionCycles; ++i)
	{
		burnSomeCPUCycles();
		this_thread::sleep_for(chrono::milliseconds(idleTimeInMilliseconds));
	}
	sem->release();
}

und der header zum Bekanntmachen der Konstanten

#pragma once
extern const size_t numClients;
extern const size_t numActionCycles;
extern const size_t numBurnCycles;
extern const size_t vecSize;
extern const int idleTimeInMilliseconds;
extern const int startDelayInMilliseconds;

Und noch die Deklaration fuer den WorkItem

/**
     * A WorkItem object is an object that provides void operator(void)
     */ 
    class WorkItem : public unary_function<void, void>
    {
    public:
		/**
		 * Overload this method in order to implement your own concurrent processing. Use class
		 * member variables to transport parameters into the method.
		 * If exceptions might be thrown from this method, you should use futures to handle that. Otherwise,
		 * the threadpool will catch and rethrow it.
		 */
        virtual result_type operator()(argument_type) = 0;
    };

[hustbaer]

DOSen schrieb:

Ergebnis: Wie erwartet gibt es bei der Verarbeitungsleistung praktisch keinen Unterschied. In beiden Faellen war die CPU durch den Prozess mit 94%-97% bzw 96%-99% ausgelastet. Aber: Mit 3000 Threads ist die Maschine praktisch nicht mehr benutzbar gewesen. Habe testweise im Hintergrund einen InetRadioStream laufen lassen. Bei 3000 Threads hat man nur noch abgehackte Fetzen hoeren koennen, beim Threadpool lief alles ohne dropouts weiter.

Und wie sah der Throughput der beiden Varianten aus?
DAS wäre nämlich viel interessanter.

DOSen schrieb:

Fazit: Fuer so etwas am besten also einen Master-Worker Ansatz nehmen.

Dann dreh die Thread-Priorität der Server-Threads auf -1, und die Sache ist gegessen.