Handelsplattform neu aufsetzen

Hallo,
ich arbeite seit 8 Jahren mit einer Handelsplattform, deren Architektur inzwischen nicht mehr zeitgemäß ist. Ich schreibe euch jetzt, weil ich sie neu realisieren möchte und Inspirationen für die neue Architektur suche.

Stellt euch der Einfachheit halber vor, dass es eine Handelsplattform für Aktien ist.

Im Prinzip macht das Programm folgendes:
- Aus verschiedenen Quellen fragt es die Kurse von Aktien ab
- Da die Aktien eines Unternehmens an verschiedenen Börsen gehandelt werden, muss das Programm die Kurse der verschiedenen Märkte den einzelnen Aktien zuordenen.
- Das Programm führt dann ein Reihe von Rechenoperationen durch und liefert die Daten an alle verbundenen Clienten aus.

Bisher war das so gelöst, dass parallel die Daten von den verschiedenen Quellen abgefragt wurden (ein Thread pro Datenquelle). Nachdem alle Daten abgefragt wurden, werden die Daten in einem einzelnen Thread erst aggregiert, dann werden die Rechenoperationen durchgeführt und dann wird der gesamte Datensatz an die Clienten ausgeliefert.

Da ganze funktionierte solange gut, wie die Anzahl der Aktien überschaubar war aber inzwischen ist die Anzahl extrem stark gestiegen und die Updates dauern viel zu lange. Die Geschwindigkeit muss oberste Priorität haben.

Ich stelle mir die Architektur jetzt eher so vor:
- Pro Datenquelle ein Thread, wobei diese Threads weitere Threads starten, die dann die einzelnen Aktien abfragen.
- Sobald neue Daten in einem Thread gefunden werden, sollen diese an einen Masterthread gemeldet werden, der dann nur die Rechenoperationen für die eine Aktie durchführt und auch nur diese eine neue Information an die Clienten meldet.

Bevor ich jetzt direkt loslege, würde ich gern eure Meinung hören bzw. gerne wissen, wie die großen Börsen (Deutsche Börse, NASDAQ etc.) dieses Problem gelöst haben. Wisst ihr, ob es irgendwelche Papers, Bücher etc. zur Architektur solcher Systeme gibt?

Danke euch und
Grüße,

Michael

C++ Forumbot

Dieser Thread wurde von Moderator/in evilissimo aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

phlox81

Evtl. eignet sich ein Map Reduce Ansatz, der pro Aktie ein MapReduce für die unterschiedlichen Werte durchführt.

Deine Überlegungen finde ich richtig, fragt sich aber wo die Schwachstellen im alten System sind, einen zentralen Thread zum Aggregieren kann sicher ein Problem bei zuviel Last werden. Hier könntest du diesen Thread mit einem MapReduce ersetzen, was dann wiederum auch verteilt laufen könnte.

phlox81 schrieb:

Evtl. eignet sich ein Map Reduce Ansatz, der pro Aktie ein MapReduce für die unterschiedlichen Werte durchführt.

Deine Überlegungen finde ich richtig, fragt sich aber wo die Schwachstellen im alten System sind, einen zentralen Thread zum Aggregieren kann sicher ein Problem bei zuviel Last werden. Hier könntest du diesen Thread mit einem MapReduce ersetzen, was dann wiederum auch verteilt laufen könnte.

Glaub nicht, dass der einzelne Thread zum Aggregieren das Problem ist. Andere Programme berechnen Millionen von Pixeln im Bruchteil einer Sekunde und zeigen sie dann noch an. Wenn er natürlich ein paar Millionen Aktien für tausende von Clients hat, dann schon.

Ich glaub eher das Problem ist, dass auf alle Daten gewartet wird.

Michu schrieb:

Bisher war das so gelöst, dass parallel die Daten von den verschiedenen Quellen abgefragt wurden (ein Thread pro Datenquelle). Nachdem alle Daten abgefragt wurden, werden die Daten in einem einzelnen Thread erst aggregiert, dann werden die Rechenoperationen durchgeführt und dann wird der gesamte Datensatz an die Clienten ausgeliefert.

Ich galub, dass das was du vorschlägst schon ausreicht. Nicht warten bis alle Daten gesammelt wurden, sondern sofort Rechnen und die Clients aktualisieren, wenn die Daten für eine Aktie da sind. Wenn das dann immer noch zu langsam ist, kannst du immer noch mehrere threads zum berechenn verwenden.

Michu schrieb:

Hallo,
- Pro Datenquelle ein Thread, wobei diese Threads weitere Threads starten, die dann die einzelnen Aktien abfragen.

Nur als Hinweis verstehen da ich nicht weis wie intensiv Du Dich schon mit Multithreading auseinandergesetzt hast... Aber diese Aussage deutet darauf hin das Du den allgemein verbreiteten Denkfehler machst, mehr Threads = mehr Performance. Das Gegenteil ist eher der Fall. Jeder Thread erzeugt einen Overhead der durch Context-Switch etc verursacht wird. Je mehr Threads Du also startest, desto mehr Rechenleistung geht durch die Threads verloren. Wahrscheinlich hast Du am Ende ein System das dann unterm Strich noch viel langsamer läuft.

Als Beispiel kannst Du Dir mal Webserver anschauen, da wird auch nicht für jede Connection ein Thread gestartet (naiver Ansatz), sondern einzelne Threads arbeiten die Anfragen sequentiell ab. (-> siehe select-Befehl).

Threads sollte man einsetzen um einzelne Kompenenten voneinander zeitlich zu entkoppeln, wie in dienem Fall z.B. ein Verwaltungsthread, Workerthreads usw.

Eventuell (ohne genauer in das Projekt reinzuschauen) kannst Du z.B. auch dadurch Performance gewinnen das Du nicht mehr einen Thread pro Datenquelle startest, sondern z.B. einen Workerthread pro Prozessor(Core) und die dann optimiert sequentiell die Datenquellen abarbeiten... (Und nur als Gedanke, auch im Multithreading wird die eigendliche Arbeit sequentiell abgearbeitet, halt ein Thread nach dem anderen...)

loks schrieb:

(Und nur als Gedanke, auch im Multithreading wird die eigendliche Arbeit sequentiell abgearbeitet, halt ein Thread nach dem anderen...)

Die Zeiten als ein Rechner nur eine CPU hatte sind schon lang vorbei. Heute laufen die Threads wirklich parallel und nicht nacheinander

Ähhh schrieb:

loks schrieb:

(Und nur als Gedanke, auch im Multithreading wird die eigendliche Arbeit sequentiell abgearbeitet, halt ein Thread nach dem anderen...)

Die Zeiten als ein Rechner nur eine CPU hatte sind schon lang vorbei. Heute laufen die Threads wirklich parallel und nicht nacheinander

Soso... dann brauchen wir also heutzutage keinen Task-Sheduler mehr wenn ja alles wirklich parallel läuft

Die maximale Parallelität wird durch die vorhandenen Cores bestimmt, und das sind auf üblichen Systemen eher nur ne Handvoll. Betrachtet man die Ansazhl der durchschnittlich laufenden Threads (200+) werden da zu jedem Zeitpunkt Threads im Wartezustand sein bis sie mal Rechenzeit auf einem der wenigen Cores zugewiesen bekommen...

Natürlich stimmt es das auf Mehrkernsystemen tatsächlich immer ein paar Threads parallel laufen (vorrausgesetzt die Software unterstützt das auch, was nicht immer der Fall ist), aber das Grundverhalten bleibt eine Sequentielle Abarbeitung der vorhandenen Threads. Alles was sich ändert ist, daß immer der nächste wartende Thread an die nächste frei werdende CPU (oder Core) verteilt wird soweit der Thread nicht an eine bestimmte CPU (Core) gebunden ist, dann muß er warten bis der entsprechende Core wieder frei wird.

Um das Ganze Denkmodel zu vereinfachen spreche ich davon das eigendlich immer noch eine Sequentielle Abarbeitung der Threads passiert.

loks schrieb:

Ähhh schrieb:

loks schrieb:

(Und nur als Gedanke, auch im Multithreading wird die eigendliche Arbeit sequentiell abgearbeitet, halt ein Thread nach dem anderen...)

Die Zeiten als ein Rechner nur eine CPU hatte sind schon lang vorbei. Heute laufen die Threads wirklich parallel und nicht nacheinander

Soso... dann brauchen wir also heutzutage keinen Task-Sheduler mehr wenn ja alles wirklich parallel läuft

Kein Sinn/Zusammenhang vorhanden

Die maximale Parallelität wird durch die vorhandenen Cores bestimmt, und das sind auf üblichen Systemen eher nur ne Handvoll. Betrachtet man die Ansazhl der durchschnittlich laufenden Threads (200+) werden da zu jedem Zeitpunkt Threads im Wartezustand sein bis sie mal Rechenzeit auf einem der wenigen Cores zugewiesen bekommen...

Und 200+ Threads davon tun meistens nichts. Übrigens widerlegst du damit selber deine Aussage, dass der Overhead durch Context-Switches so ein großes Problem ist, weil er sowieso passiert nur eben zu einem Thread der nicht dir gehört.

Natürlich stimmt es das auf Mehrkernsystemen tatsächlich immer ein paar Threads parallel laufen (vorrausgesetzt die Software unterstützt das auch, was nicht immer der Fall ist), aber das Grundverhalten bleibt eine Sequentielle Abarbeitung der vorhandenen Threads. Alles was sich ändert ist, daß immer der nächste wartende Thread an die nächste frei werdende CPU (oder Core) verteilt wird soweit der Thread nicht an eine bestimmte CPU (Core) gebunden ist, dann muß er warten bis der entsprechende Core wieder frei wird.

Um das Ganze Denkmodel zu vereinfachen spreche ich davon das eigendlich immer noch eine Sequentielle Abarbeitung der Threads passiert.

Merkst du ja schon selber, dass dein Denkmodel veraltet ist.

Vielen Dank für eure bisherige Diskussion. Der Kommentar von Schalalalaladida geht schon genau in die Richtung, in der ich das Problem vermute. Selbst, wenn eine Datenquelle komplett abgefragt wurde, wartet das Programm noch weiter, bis auch die letzte Datenquelle abgefragt wurde.

Ein anderes Problem über das ich mir noch den Kopf zerbreche ist die Frage der Datenverwaltung. Die Datenmenge liegt noch in einem Rahmen, in dem ich alle Daten im RAM halten kann und an dieser Stelle wird es wohl auch auf absehbare Zeit keine Probleme geben. Wir reden von ~200MB Daten. Das sollte also in jedem Fall schneller sein, als wenn ich noch eine Datenbank dazu nehme, oder?

Ich habe bisher mit Vector'en gearbeitet und bin damit eigentlich auch sehr zufrieden. Was passiert aber, wenn ich ...
... jeden Thread direkt in den Vector schreiben lasse? Der Fachbegriff fehlt mir gerade aber sind dafür nicht genau CriticalSections gedacht? Ich meine mal gelesen zu haben, dass es Fehler geben kann, wenn alle Threads prallel im Vector schreiben und lesen.
... man könnte natürlich auch die Daten auf einen Stack legen und dann nur einen einzelnen Thread alle Daten aus dem Stack in den Master-Vector schreiben lassen.

Läuft das hier darauf hinaus, dass ich mir verschiedene Archtikturen überlege und die dann in kleinen Testanwendungen nach dem trial and error-Prinzip teste oder wie gehe ich am Besten bei der Planung vor?

Probleme gibts immer dann, wenn zwei Threads an der gleichen Speicherstelle was machen. Wenn du z.B. Pointer hast die an unterschiedliche Stellen im Vector zeigen und die Threads nur diese Daten und nicht den Vector selber ändern, ist das kein Problem. Welche Sprache nimmst du überhaupt? Du musst natürlich auch aufpassen, dass nicht schon ausgelesen wird, vor der Thread fertig geschrieben hat.

Ähhh schrieb:

Merkst du ja schon selber, dass dein Denkmodel veraltet ist.

Veraltet vielleicht ja, aber deswegen noch nicht grundsätzlich falsch. Das Denkmodell "Alles läuft gleichzeitig" dagegen halte ich nach wie vor für falsch und gefährlich, weil es die Problematik ignoriert.

Ähhh schrieb:

Übrigens widerlegst du damit selber deine Aussage, dass der Overhead durch Context-Switches so ein großes Problem ist, weil er sowieso passiert nur eben zu einem Thread der nicht dir gehört.

http://en.wikipedia.org/wiki/Context_switch

http://msdn.microsoft.com/en-us/library/ms682105(VS.85).aspx

http://msdn.microsoft.com/en-us/library/ms684261(VS.85).aspx

Zitat msdn

The system consumes memory for the context information required by both processes and threads. Therefore, the number of processes and threads that can be created is limited by available memory.
Keeping track of a large number of threads consumes significant processor time. If there are too many threads, most of them will not be able to make significant progress. If most of the current threads are in one process, threads in other processes are scheduled less frequently.

loks schrieb:

Ähhh schrieb:

Merkst du ja schon selber, dass dein Denkmodel veraltet ist.

Veraltet vielleicht ja, aber deswegen noch nicht grundsätzlich falsch. Das Denkmodell "Alles läuft gleichzeitig" dagegen halte ich nach wie vor für falsch und gefährlich, weil es die Problematik ignoriert.

Der "Threads laufen sequentiell" Gedanke ist falsch und viel gefährlicher. Das führt nur dazu, dass man Critical Sections nicht richtig behandeln, wenn man meint, dass es keine parallelen Zugriffe gibt. Nur weil es ein paar DAUs gibt, die meinen 100000 Threads sind immer besser als 10, muss man nicht so denken, als ob alles sequentiell läuft.

Zum Thema Threads habe ich verstanden, dass mehr nicht unbedingt besser ist. Aber nur damit die Diskussion nicht in die falsche Richtung läuft, wir reden hier nicht über tausende von Threads, sondern über max. 40, wobei auch das schon für mich viel klingt.

Ich werde einfach mal testen müssen, ob ich bessere Ergebnisse mit
- ein Thread pro Datenquelle bekomme, oder
- Innerhalb einer Datenquelle noch weiter Differenzieren

Wahrscheinlich lässt sich die Performance auch noch dadurch steigern, dass ich die Datenabfrage und -verarbeitung noch stärker auf relevante Daten fokussiere. Momentan verfolgt mein Programm eher einen Vollständigkeitsanspruch, obwohl der für meinen eigentlichen Handel gar nicht notwendig ist.

--

Das Thema Pointer auf den Vector klingt interessant. Sogar sehr interessant. Momentan durchläuft mein Aggregierungs-Thread noch ständig den Master-Vector, um zu suchen, wo ein Datensatz aktualisiert werden soll. Wenn ich aber den Pointer auf die entsprechende Stelle direkt speichere, dann müsste ja dieser ganze Prozess wegfallen, oder?

--

Das ganze ist mit VC++ geschrieben, wobei ich momentan stark am Grübeln bin, ob ich auf Linux umsteigen soll. Ich habe gehört, dass inbesondere bei sehr rechenintensiven Anwendungen eher Linux zu empfehlen ist. Ich zögere aber noch etwas vor dem Schritt, weil die Umstellung wahrscheinlich zu Beginn etwas holperig wird, wenn man von seinen hübschen bunten GUIs kommt und dann mit Linux wieder in Konsolen arbeitet. Ich weiß schon, dass es auch Linux Distributionen mit GUI gibt aber die Idee ist ja genau sich die Rechenzeit für die GUI zu sparen.

Grüße,
Michael

Michu schrieb:

Das ganze ist mit VC++ geschrieben, wobei ich momentan stark am Grübeln bin, ob ich auf Linux umsteigen soll. Ich habe gehört, dass inbesondere bei sehr rechenintensiven Anwendungen eher Linux zu empfehlen ist.

Lass es bleiben. Linux bringt hier keinen Vorteil.

Die Antwort hätte ich jetzt nicht erwartet. Normalerweise liest man doch überall, wie alle davon schwärmen.

Mr. N

Michu schrieb:

Die Antwort hätte ich jetzt nicht erwartet. Normalerweise liest man doch überall, wie alle davon schwärmen.

Ja, aber nicht wegen roher Geschwindigkeit von schlichten Berechnungen.

@Michu

Mir drängt sich so ein bischen die Befürchtung auf das Du über Lösungsansätze nachdenkst ohne das eigendliche Performanceproblem analysiert zu haben. Hast Du z.B. mal nen Profiler eingesetzt?

phlox81

Michu schrieb:

Die Antwort hätte ich jetzt nicht erwartet. Normalerweise liest man doch überall, wie alle davon schwärmen.

Würde dir empfehlen das Plattformunabhängig zu implementieren, mit boost::thread und asio/lib pion für die Netzwerkabfragen kannst du dann die Plattform immer noch recht einfach wechseln.
Das Linux da aber große Vorteile bringt bezweifel auch ich.