Wie funktioniert das Disruptor-Muster von LMAX?

Ich versuche zu verstehen, die disruptor pattern. Ich habe beobachtet, wie die InfoQ-video und versucht zu Lesen Ihre Zeitung. Ich verstehen, es ist ein ring-Puffer, das es initialisiert wird, wie ein extrem großes array zu nutzen, cache-Lokalität, beseitigen Zuweisung neuer Speicher.

Es klingt wie es eine oder mehrere Atomare Ganzzahlen, die Spur zu halten von Positionen. Jedes 'Ereignis' scheint, um eine eindeutige id und die position im ring ist gefunden durch Suche nach deren E-Modul in Bezug auf die Größe der ring, etc., etc.

Leider ich don ' T haben ein intuitives Gefühl dafür, wie es funktioniert. Ich habe viele trading-Anwendungen und studierte die Schauspieler-Modell, sah SEDA, etc.

In Ihrem Vortrag erwähnten Sie, dass dieses Muster ist im Grunde wie ein Router funktionieren; aber ich habe nicht gefunden eine gute Beschreibungen, wie ein Router funktioniert.

Gibt es einige gute Hinweise, um eine bessere Erklärung?

InformationsquelleAutor der Frage Shahbaz | 2011-07-02

201

Den Google-Code-Projekt hat Referenz ein technisches Papier auf die Umsetzung der ring-Puffer, jedoch ist es ein wenig trocken, akademisch und hart, das geht für jemanden zu wollen, zu lernen, wie es funktioniert. Es gibt jedoch einige blog-Beiträge, die begonnen haben, zu erklären, die Interna in einem besser lesbaren Weise. Es ist ein Erklärung der ring-Puffer das ist der Kern der disruptor-Muster, eine Beschreibung des Verbraucher-Barrieren (der Teil bezüglich Lesen aus dem disruptor) und einige Informationen über die Handhabung von mehreren Produzenten zur Verfügung.

Die einfachste Beschreibung der Disruptor ist: Es ist ein Weg, das senden von Nachrichten zwischen threads in die effizienteste Art und Weise möglich. Es kann als alternative verwendet werden, um eine Warteschlange, sondern es teilt auch eine Reihe von features, mit SEDA und Akteure.

Im Vergleich zu Warteschlangen:

Den Disruptor bietet die Möglichkeit, eine Botschaft auf andere threads, aufwachen, wenn erforderlich (ähnlich einer BlockingQueue). Es gibt jedoch 3 verschiedene Unterschiede.
1. Der Benutzer von den Disruptor definiert, wie Nachrichten gespeichert werden, durch die Ausweitung der Eintrag Klasse und die Bereitstellung einer Fabrik zu tun, die preallocation. Dies ermöglicht entweder Speicher wiederverwenden (kopieren) oder der Eintrag enthält einen Verweis auf ein anderes Objekt.
2. Setzen Nachrichten in der Disruptor ist eine 2-Phasen-Prozess zuerst einen Steckplatz in Anspruch genommen wird in der ring-Puffer, die dem Benutzer den Eintrag, der gefüllt werden kann mit den entsprechenden Daten. Dann den Eintrag müssen verpflichtet werden, dieses 2-Phasen-Ansatz ist erforderlich, um für die flexible Nutzung der Speicher oben erwähnt. Es ist der commit macht die Nachricht für die Verbraucher sichtbar threads.
3. Es liegt in der Verantwortung der Verbraucher zu verfolgen, die Nachrichten, die verbraucht wurden aus dem ring-buffer. Verschieben diese Verantwortung Weg von den ring-Puffer selbst dazu beigetragen, reduzieren die Menge der schreiben, die Behauptung, da jeder thread besitzt seinen eigenen Zähler.
Im Vergleich zu Akteuren

Die Schauspieler-Modell ist näher der Disruptor als die meisten anderen Programmier-Modelle, vor allem, wenn Sie die BatchConsumer/BatchHandler Klassen zur Verfügung gestellt werden. Diese Klassen ausblenden all der Komplexität der Aufrechterhaltung der verbraucht Sequenznummern und bieten eine Reihe von einfachen Rückrufe, wenn wichtige Ereignisse eintreten. Es gibt jedoch ein paar feine Unterschiede.
1. Der Disruptor verwendet eine 1-thread - 1-consumer-Modell, wo die Schauspieler verwenden eine N:M-Modell, d.h. Sie können so viele Akteure, wie Sie möchten und Sie werden verteilt über eine Feste Anzahl von threads (in der Regel 1 pro Kern).
2. Die BatchHandler-Schnittstelle bietet eine zusätzliche (und sehr wichtig) callback onEndOfBatch(). Dies ermöglicht eine langsame Verbraucher, z.B. diejenigen, die I/O-zu-batch-Veranstaltungen zusammen, um den Durchsatz zu steigern. Es ist möglich, die Dosierung in anderen Schauspieler frameworks, jedoch wie fast alle anderen frameworks bieten keinen callback am Ende der batch müssen Sie ein Zeitlimit, um zu bestimmen, die Ende der Partie, was zu einer schlechten Latenz.
Im Vergleich zu SEDA

LMAX gebaut, das Disruptor pattern zu ersetzen, eine SEDA-basierte Ansatz.
1. Die wichtigste Verbesserung, dass es über SEDA war die Fähigkeit, Arbeit zu verrichten parallel. Dazu der Disruptor unterstützt multi-casting die gleichen Meldungen (in derselben Reihenfolge) an mehrere Verbraucher. Dies vermeidet die Notwendigkeit für Gabel-Stufen in der pipeline.
2. Wir ermöglichen auch die Verbraucher warten auf die Ergebnisse anderer Verbraucher, ohne dass eine weitere queuing Bühne zwischen Ihnen. Verbraucher können einfach beobachten Sie die Sequenz-Nummer des Verbrauchers, dass er abhängig ist. Dies vermeidet die Notwendigkeit für join-Stufen in der pipeline.
Im Vergleich zu Speicher Barrieren

Einen anderen Weg zu denken, es ist wie eine strukturierte, geordnete memory-Barriere. Wo die Hersteller Barriere bildet die schreib-Barriere und der Verbraucher Barriere ist die lese-Barriere.

InformationsquelleAutor der Antwort Michael Barker
130

Zunächst möchten wir verstehen, das Programmiermodell, die er anbietet.

Gibt es einen oder mehrere Autoren. Gibt es einen oder mehrere Leser. Es gibt eine Reihe von Einträgen, Total geordnet von alt zu neu (im Bild von Links nach rechts). Autoren können neue Einträge hinzufügen, auf der rechten Seite. Jeder Leser liest die Einträge sequentiell von Links nach rechts. Die Leser können nicht Lesen Vergangenheit Schriftsteller, offensichtlich.

Gibt es kein Konzept der Eintrag löschen. Ich "Leser" statt "Verbraucher" zu vermeiden, das Bild von Einträgen, die verbraucht wird. Aber wir verstehen, dass die Links auf die Einträge der letzten reader unbrauchbar.

In der Regel können die Leser Lesen gleichzeitig und unabhängig voneinander. Aber wir können erklären, die die Abhängigkeiten zwischen den Lesern. Leser-Abhängigkeiten können beliebige azyklische Graphen. Wenn Leser B ist abhängig von reader A reader B nicht Lesen können, Vergangenheit reader A.

Reader Abhängigkeit entsteht, weil die Leser Einen können Sie kommentieren einen Eintrag, und reader B hängt davon ab, Anmerkung. Zum Beispiel, Ein paar Berechnung auf einen Eintrag und speichert das Ergebnis in Feld a im Eintrag. Ein verschieben Sie dann auf, und jetzt B Lesen Sie den Eintrag, und den Wert von a Eine gespeichert. Wenn Leser C nicht davon abhängen, A, C, sollten nicht versuchen zu Lesen a.

Dies ist in der Tat ein Interessantes Programmiermodell. Unabhängig von der Leistung, die das Modell allein können profitieren viele Anwendungen.

Natürlich, LMAX Hauptziel ist die Leistung. Es verwendet einen pre-allocated ring der Einträge. Der ring ist groß genug, aber es ist begrenzt so dass das system nicht geladen werden, über design-Kapazität. Wenn der ring voll ist, wird writer(s) warten, bis der langsamste Leser Voraus und machen Platz.

Eintrag Objekte sind bereits vergeben und ewig Leben, reduzieren sich die garbage collection Kosten. Wir nicht einfügen neuen Eintrag Objekte oder löschen Sie die alte Eingabe-Objekte, sondern ein Schriftsteller fragt, für einen bereits vorhandenen Eintrag, füllen Sie die Felder, und informieren die Leser. Dieser scheinbare phase-2-Aktion ist wirklich einfach eine Atomare Aktion
```
setNewEntry(EntryPopulator);

interface EntryPopulator{ void populate(Entry existingEntry); }
```
Pre-allocating-Einträge bedeutet auch benachbarte Einträge (sehr wahrscheinlich) suchen Sie in benachbarte Speicher-Zellen, und weil die Leser Lesen Einträge hintereinander, das ist wichtig, zu nutzen, um die CPU-caches.

Und viele Anstrengungen zu vermeiden, Sperre, CAS, auch memory-Barriere (z.B. eine nicht-flüchtige Sequenz variable, wenn es nur einen Autor)

Für Entwickler von Lesern: Verschiedene Anmerkungen sollten die Leser schreiben zu verschiedenen Bereichen, zu vermeiden, schreiben Sie den Streit. (Eigentlich sollten Sie schreiben, um verschiedene cache-Zeilen.) Eine Markierung der Leser sollte nicht direkt auf etwas, dass andere nicht-abhängig-Leser gelesen werden kann. Dies ist der Grund, warum ich sagen, dass diese Leser kommentieren Einträge, statt ändern Einträge.

InformationsquelleAutor der Antwort irreputable
41

Martin Fowler hat einen Artikel geschrieben über LMAX und der disruptor pattern, Die LMAX-Architektur, kann es eine weitere Klärung.

InformationsquelleAutor der Antwort ChucK
16

Ich tatsächlich die Zeit genommen, die Untersuchung der eigentlichen Quelle, aus reiner Neugier, und die Idee dahinter ist ganz einfach. Die neueste version zum Zeitpunkt des Schreibens dieser post ist 3.2.1.

Es ist eine Puffer-Speicherung von pre-allocated Ereignisse, die halten die Daten für den Verbraucher zu Lesen.

Puffer wird unterstützt durch ein array von flags (integer-array) von seiner Länge, beschreibt die Verfügbarkeit der Puffer-slots (siehe weiter unten für details). Das array zugegriffen wird, wie ein java#AtomicIntegerArray, so dass für die Zwecke dieses explenation Sie können ebenso davon ausgehen, es zu sein.

Kann es eine beliebige Anzahl von Produzenten. Wenn der Hersteller will, zu schreiben in den Puffer, eine lange Zahl erzeugt (wie beim Aufruf AtomicLong#getAndIncrement, den Disruptor benutzt seine eigene Implementierung, aber es funktioniert in der gleichen Weise). Nennen wir diese generierte lange producerCallId. In ähnlicher Weise kann ein consumerCallId wird generiert, wenn ein Verbraucher ENDET der Lektüre ein Ablagefach aus einem Puffer. Die jüngsten consumerCallId zugegriffen wird.

(Wenn es viele Verbraucher, die Anruf mit der mit der kleinsten id gewählt.)

Diese ids werden dann verglichen, und wenn der Unterschied zwischen den beiden ist weniger, dass die Puffer-Seite, der Hersteller erlaubt ist zu schreiben.

(Wenn die producerCallId größer ist, als die letzten consumerCallId + bufferSize, es bedeutet, dass der Puffer voll ist, und der Hersteller ist gezwungen, den bus-warten, bis eine Stelle frei wird.)

Anschließend wird der producer zugeordnet den Schlitz in dem Puffer auf der Grundlage seiner callId (das ist prducerCallId modulo bufferSize, aber da die bufferSize ist immer eine Potenz von 2 ist (limit durchgesetzt Puffer Schöpfung), der aktuellen operation verwendet wird producerCallId & (bufferSize - 1)). Es ist dann zu ändern, die Veranstaltung in diesem slot.

(Der tatsächliche Algorithmus ist etwas komplizierter, mit caching letzten consumerId in einem separaten atomic Referenz für die Optimierung Zwecke.)

Wenn das Ereignis geändert wurde, die änderung ist "veröffentlicht". Bei der Veröffentlichung der jeweilige slot im flag-array ist gefüllt mit der neuen fahne. Der flag-Wert ist die Anzahl der loop (producerCallId geteilt durch bufferSize (wieder da bufferSize ist Potenz von 2, die eigentliche operation wird ein rechts-shift).

In einer ähnlichen Art und Weise kann es eine beliebige Anzahl von Verbrauchern. Jedes mal, wenn ein Verbraucher will, um Zugriff auf den Puffer, consumerCallId generiert (je nachdem, wie die Verbraucher wurden Hinzugefügt, um die Unterbrecher der atomaren verwendet in id-Generierung können gemeinsam oder getrennt für jeden von Ihnen). Diese consumerCallId ist dann im Vergleich zu den letzten producentCallId, und wenn es ist das kleinere der beiden, das Leser erlaubt, um die Fortschritte.

(Ebenso, wenn die producerCallId ist auch der consumerCallId, es bedeutet, dass der Puffer ist empety und der Verbraucher ist gezwungen, zu warten. Die Art des Wartens ist definiert durch eine WaitStrategy während Unterbrecher der Schöpfung.)

Für einzelne Verbraucher (die mit Ihrer eigenen id generator), das nächste, was geprüft wird die Fähigkeit, batch verbrauchen. Die Schlitze in den Puffer untersucht, um die von dem jeweiligen consumerCallId (der index ist bestimmt in der gleichen Weise wie für Produzenten), der einer jeweiligen der letzten producerCallId.

Sind, werden Sie untersucht in einer Schleife durch den Vergleich der fahne geschriebene Wert im flag-array, der gegen ein flag-Wert generiert für die consumerCallId. Wenn die flags entsprechen, es bedeutet, dass die Produzenten füllen die slots begangen hat, deren änderungen. Wenn nicht, wird die Schleife unterbrochen, und die höchste begangen changeId zurückgegeben. Die slots von ConsumerCallId zu erhalten in changeId verbraucht werden kann, in batch.

Wenn eine Gruppe von Verbrauchern zusammen zu Lesen (die, die mit shared-id-generator), die jeweils nur eine einzige callId, und nur der Steckplatz für das einzelne callId wird überprüft und zurückgegeben.

InformationsquelleAutor der Antwort Martin A. Kwasowiec

Vom dieser Artikel:

Den disruptor pattern ist ein Dosier-Warteschlange gesichert durch eine kreisförmige
array (d.h. der ring-Puffer) gefüllt mit pre-allocated transfer
Objekte, die verwendet Speicher-Hindernisse für Produzenten und synchronisieren
der Verbraucher durch die Sequenzen.

Memory-Barrieren sind schwer zu erklären und Trisha ' s blog hat das beste getan, versucht meiner Meinung nach mit diesem Beitrag: http://mechanitis.blogspot.com/2011/08/dissecting-disruptor-why-its-so-fast.html

Aber wenn Sie nicht wollen, Tauchen Sie ein in die low-level-details können Sie einfach wissen, dass die memory-Barrieren, die in Java implementiert sind, durch die volatile Stichwort oder über die java.util.concurrent.AtomicLong. Das disruptor pattern-Sequenzen sind AtomicLongs und kommuniziert werden hin und her zwischen Produzenten und Konsumenten durch die memory-Barrieren statt sperren.

Ich finde es einfacher zu verstehen, ein Konzept über einen code, also der code unten ist ein einfaches helloworld von CoralQueue, das ist ein disruptor pattern-Umsetzung erfolgt durch CoralBlocks mit denen ich mich angeschlossen. Im code unten sehen Sie wie das disruptor pattern implementiert Dosierungs-und wie der ring-Puffer (D. H. kreisförmige array) ermöglicht die Müll-freie Kommunikation zwischen zwei threads:

package com.coralblocks.coralqueue.sample.queue;

import com.coralblocks.coralqueue.AtomicQueue;
import com.coralblocks.coralqueue.Queue;
import com.coralblocks.coralqueue.util.MutableLong;

public class Sample {

    public static void main(String[] args) throws InterruptedException {

        final Queue<MutableLong> queue = new AtomicQueue<MutableLong>(1024, MutableLong.class);

        Thread consumer = new Thread() {

            @Override
            public void run() {

                boolean running = true;

                while(running) {
                    long avail;
                    while((avail = queue.availableToPoll()) == 0); //busy spin
                    for(int i = 0; i < avail; i++) {
                        MutableLong ml = queue.poll();
                        if (ml.get() == -1) {
                            running = false;
                        } else {
                            System.out.println(ml.get());
                        }
                    }
                    queue.donePolling();
                }
            }

        };

        consumer.start();

        MutableLong ml;

        for(int i = 0; i < 10; i++) {
            while((ml = queue.nextToDispatch()) == null); //busy spin
            ml.set(System.nanoTime());
            queue.flush();
        }

        //send a message to stop consumer...
        while((ml = queue.nextToDispatch()) == null); //busy spin
        ml.set(-1);
        queue.flush();

        consumer.join(); //wait for the consumer thread to die...
    }
}

InformationsquelleAutor der Antwort rdalmeida

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.