Multithreaded Server - Design Guidelines?

[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.

[DOSen]

hustbaer schrieb:

Und wie sah der Throughput der beiden Varianten aus?

Annähernd gleich. Allerdings war die Latenz beim Starten eines neuen Threads bzw. einqueuen eine Clients bei der Variante mit einem Thread pro Client viel höher als bei der ThreadPool Variante.

hustbaer schrieb:

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

Habe ich mittels SetThreadPriority(threads.back()->native_handle(), THREAD_PRIORITY_BELOW_NORMAL); ausprobiert. Das ist zwar deutlich besser, aber vom Ansprechverhalten immer noch schlechter als die ThreadPool Variante.

Aber Danke für den Hinweis. Da hatte ich nicht dran gedacht. Im Gegenzug gibt es natürlich die Option auch beim ThreadPool, plus man kann die Poolgröße ja auch noch hochdrehen.

Oder hast Du vielleicht noch eine Alternative in petto?

[hustbaer]

Oder hast Du vielleicht noch eine Alternative in petto?

Alternative für was?

Für Fälle wo der Server für die Clients nur lauter Dinge zu machen hat die keine hohe Rechenleistung im Connection-Thread erfordern kann man denke ich nix mehr drehen. Wenn da der "1 Thread pro Connection" Server in die Knie geht, dann ist man mit der Variante wohl am Limit.

Bei Fällen wo der Server in den Connection Threads richtig viel rechnen würde, könnte ich mir aber vorstellen dass man die beiden Varianten hübsch kombinieren kann.
Also die ganzen "billigen" Sachen macht man direkt im Connection Thread, und aufwendigere Berechnungen lagert man in einen Thread Pool aus.
Also quasi

Reply Connection::HandleFooRequest(Foo foo)
{
   LogSomething(foo);
   if (!VerifySomething(foo, m_someOtherValue))
   {
       LogSomethingElse(foo);
       return MakeErrorReply("blub");
   }

   // ...

   DoSomeStuffThatMightBlockTheThreadForSeveralSeconds();

   // ...

   auto fooData = m_pool.Queue([&](){ return LongRunningCalculation(foo); });

   // ...
   // ...

   auto fooData2 = m_pool.Queue([&](){ return AnotherHeavyCalculation(foo); });

   // ...
   // ...

   return MakeFooReply(fooData.get(), fooData2.get());
}

Das hat den Vorteil dass man viel Code der nur sehr lästig asynchron zu machen wäre im Connection Thread lassen kann, aber trotzdem nicht tausende Threads hat die permanent die CPU mit rechenintensiven Sachen hämmern.

Ich schätze mal das sollte sich sehr positiv auf die Responsiveness des Servers auswirken.

ps: Ich hab aber den Thread hier nicht sehr aufmerksam gelesen. Also falls meine Antwort total unpassend ist bitte einfach ignorieren (oder auch gerne kurz darauf hinweisen wieso).

[volkard]

DOSen schrieb:

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…

Hab den Code mit 3000 Threads mal getestet.
Linux 64Bit i7 16G.
Schlechte Ansprechbarkeit bemerke ich eigentlich nicht, aber ich kriege nur 32273 Threads auf.

[hustbaer]

DOSen schrieb:

hustbaer schrieb:

Und wie sah der Throughput der beiden Varianten aus?

Annähernd gleich. ...

ps: Danke für die Info

[Kellerautomat]

Ich weiss immer noch nicht, wie ich die Simulation von IO unabhaengig bekommen soll. Ich benutze fuer IO boost.asio, d.h. das Threading wird hier mittels asio's io_service erledigt. Wenn ich allerdings einen Thread pro Welt haben moechte, funktioniert das nicht, weil die Welt dann ebenfalls ueber den io_service bescheid wissen muss.

Ich habe einen Scheduler, der so aussieht:

struct WorldScheduler
{
	typedef std::function<void(World&)> Task;

	WorldScheduler(World& world)
		: world_(&world)
		, run_(true)
		, thread_(&WorldScheduler::executeTasks, this)
	{}

	~WorldScheduler()
	{
		run_ = false;
		thread_.join();
	}

	void spawnTask(Task task)
	{
		scheduledTasks_.push(std::move(task));
	}

	void spawnRepeatedTask(Task task)
	{
		repeatedTasks_.push_back(std::move(task));
	}

private:
	void executeTasks()
	{
		Stopwatch sw;

		while(run_)
		{
			tick();

			for(Task task; sw.expired() < TICK_DURATION && scheduledTasks_.try_pop(task);)
				task(*world_);

			auto expired = sw.reset();

			if(expired < TICK_DURATION)
				std::this_thread::sleep_for(TICK_DURATION - expired);
		}
	}

	void tick()
	{
		for(auto& task : repeatedTasks_)
			task(*world_);
	}

	World* world_;
	atomic<bool> run_;
	concurrent_vector<Task> repeatedTasks_;
	concurrent_queue<Task> scheduledtasks_;

	std::thread thread_;
};

Die Welt braucht hier volle Kontrolle ueber das Scheduling, u.A. aufgrund der Server-Ticks, die 20 mal pro Sekunde ausgefuehrt werden sollen. Kann man das irgendwie sinnvoll mit boost.asio zusammenbringen?

[DOSen]

Volkard schrieb:

Schlechte Ansprechbarkeit bemerke ich eigentlich nicht, aber ich kriege nur 32273 Threads auf.

Interessant. Dann scheint das ja eher am Windows Scheduler zu liegen. Hast Du mal, wenn die 32k Threads laufen einen Audiostream laufen lassen? Das ist eigentlich ein guter Test, ob das System noch damit zurecht kommt.

Unter Windows habe ich extra 1s Wartezeit eingebaut, bevor die Threads zu rechnen anfangen, ansonsten wurde das Aufstarten weiterer Threads so langsam, dass ich nie über ein paar Hundert glecihzeitig laufender Threads gekommen bin.
Ich hatte zuerst vermutet, dass die Threads schneller fertig werden als neue hinzu kommen, aber das bleibt gleich, auch wenn man die Werte entsprechend ändert.

hustbaer schrieb:

Also die ganzen "billigen" Sachen macht man direkt im Connection Thread, und aufwendigere Berechnungen lagert man in einen Thread Pool aus.

Ja, das ist wahrscheinlich ein brauchbarer Ansatz. Wenn ich allerdings Volkards Messungen in Betracht ziehe, scheint es ja vor allem am OS zu liegen. Sprich, bei vielen Clients ist der Overhead für das Thread Scheduling unter Windows (in Zusammenhang mit dem Design des Codes) problematisch.

Ich habe hier leider kein Linux System im Zugriff auf dem ich das ausprobieren könnte...

[volkard]

DOSen schrieb:

Volkard schrieb:

Schlechte Ansprechbarkeit bemerke ich eigentlich nicht, aber ich kriege nur 32273 Threads auf.

Interessant. Dann scheint das ja eher am Windows Scheduler zu liegen. Hast Du mal, wenn die 32k Threads laufen einen Audiostream laufen lassen? Das ist eigentlich ein guter Test, ob das System noch damit zurecht kommt.

Ich habe normal weitergesurft, im Forum geschaut, und ein youtube-Video lief dazu.

[DOSen]

volkard schrieb:

Ich habe normal weitergesurft, im Forum geschaut, und ein youtube-Video lief dazu.

Beeindruckend. Entweder ich mache noch etwas grundlegend falsch oder der Windows-Scheduler ist wirklich schlecht.