Parallele Verarbeitung mit dem Disruptor

Architektur/Methoden  –  18 Kommentare

Niedrige Latenzen und hoher Durchsatz sind das Ziel des Disruptor-Mechanismus, der einen neuen Ansatz zum Datenaustausch zwischen Threads bietet.

Was würde passieren, wenn man über das Internet Wetten verwalten wollte und bereits vorab wüsste, dass mit einer nahezu unbegrenzten Anzahl an Anfragen zu rechnen ist, die alle möglichst bald zu platzieren sind? Man würde auf jeden Fall mit den bisherigen Ansätzen sehr schnell an die Grenzen des verwendeten Systems stoßen. Aus dem Grund trifft es sich gut, dass schon jemand vor solch einem Problem stand und es mit dem Disruptor gelöst hat.

Dass viele Anfragen möglichst schnell beantwortet werden müssen, ist zunächst einmal nichts Ungewöhnliches. Wenn dann die Latenz- und Verarbeitungszeiten eine Rolle spielen, wird es schon etwas schwieriger. Sind die Antwortzeiten darüber hinaus zu garantieren, erhöht sich der Schwierigkeitsgrad erneut. Und wenn man sich dann noch mit Java oder .NET herumschlagen muss, also mit Techniken, die einen Garbage Collector einsetzen, kann einem angst und bange werden.

Typischerweise findet in Anwendungen eine Reihe von Ereignissen statt. Das können beispielsweise Anfragen aus dem Internet sein oder eingehende Messwerte. Diese Ereignisse wollen im Anschluss irgendwie verarbeitet werden. Moderne Rechner stellen dazu in der Regel mehrere Kerne und Threads zur Verfügung, also bietet es sich an, sie parallel zu verarbeiten. Aber hier tun sich schon die ersten Probleme auf.

Typische Szenarien bei der Verarbeitung von Ereignissen: (1) Unicast: Eine Quelle (Q), ein Ereignisverarbeiter (V); (2) Sequencer: drei Quellen, ein Verarbeiter; (3) Multicast: eine Quelle, drei Verarbeiter; (4) Diamant: eine Quelle, drei Verarbeiter, eine Endverarbeitung; (5) dreistufige Pipeline: eine Quelle, drei Verarbeiter. (Abb. 1)

Die Ereignisse können aus einer oder mehreren Quellen stammen. Kommen sie nur aus einer, so lässt sich durch Parallelisierung der Durchsatz vervielfachen, aber dazu muss man die Ereignisse irgendwie auf die verfügbaren Threads verteilen. Stammen sie aus mehren Quellen, so könnte jeder Thread zwar eine Quelle verarbeiten, aber dann wäre der Rechner eventuell nicht ausgelastet, wenn die Quellen unterschiedlich viele Ereignisse pro Zeit liefern.

In der Warteschlange

Abhilfe schafft in beiden Fällen eine Warteschlange (Queue), in die man die Ereignisse zunächst einfügt. Aus ihr werden sie dann von den verschiedenen Threads entnommen und verarbeitet. Sind noch weitere Arbeitsschritte nötig oder Ereignisse zusammenzuführen, kann man weitere Warteschlangen nutzen, um parallel zu arbeiten.

Das Problem einer Queue ist allerdings der damit verbundene Aufwand. Zum einen ist bei mehreren Quellen zu garantieren, dass ein gleichzeitiges Schreiben nicht zur Korruption führt, zum anderen muss gewährleistet sein, dass jedes Ereignis nur von genau einem Thread bearbeitet wird. Das hat man aber inzwischen gut im Griff. Java etwa bietet dazu eine Reihe von Implementierungen an.

Bei der Wahl der Umsetzung ist allerdings Vorsicht geboten, denn eine Implementierung als Liste hat den Nachteil, dass viele Objekte zur Verwaltung zu erzeugen sind, die das Programm irgendwann wieder mit dem Garbage Collector einsammeln muss.

Es wird also zweimal Zeit benötigt: einmal beim Erzeugen und ein anderes Mal beim Einsammeln, wobei der Zeitpunkt nicht bekannt ist. Alternativ kann man deshalb auf Array-basierte Implementierungen zurückgreifen, die solch ein Verwaltungsproblem nicht haben, dafür aber nur eine feste Anzahl von Ereignissen gleichzeitig puffern können.

Ergänzend sei noch erwähnt, dass die Warteschlage blockieren muss, wenn sie voll ist. Das heißt, dass die Ereignisquellen in ihrem Ablauf so lange zu blockieren sind, bis wieder Plätze zur Ablage frei sind. Wenn die Warteschlange leer ist, blockieren die bearbeitenden Threads so lange, bis wieder ein Ereignis eintrifft. Das Blockieren auf der Produzentenseite ist nie gut, denn dies könnte bedeuten, dass im schlimmsten Fall Ereignisse bei einer der Quellen verloren gehen. Dahingegen ist das Blockieren auf der Konsumentenseite immer akzeptabel, ist es doch ein Indiz dafür, dass das Bearbeiten der Ereignisse schnell genug vonstatten geht.

So weit, so gut. Mit diesem Vorgehen lassen sich eigentlich alle Probleme lösen. Es sei denn, die Zeit spielt eine sehr große Rolle. Hat man es etwa mit mehreren Ereignisverarbeitern zu tun, sind die Ereignisse zu duplizieren. Arbeitet man mit einer Pipeline-Verarbeitung, braucht man entsprechend viele Warteschlangen und so weiter.