Comment fonctionne le LMAX ' s disruptor modèle de travail ?

Question

Je suis en train d'essayer de comprendre le perturbateur modèle. J'ai regardé le InfoQ vidéo et essayé de lire leur papier. Je comprends, il y a un anneau de la mémoire tampon, il est initialisé comme un très large éventail de prendre avantage de la localité de cache, d'éliminer l'allocation de mémoire.

Il semble que il ya un ou plusieurs atomique entiers qui ont garder une trace de positions. Chaque "événement" semble avoir une id unique et il est de la position de la bague est trouvée par trouver son module par rapport à la taille de l'anneau, etc., etc.

Malheureusement, je n'ai pas un sens intuitif de la façon dont il fonctionne. J'ai fait de nombreuses applications de négociation et étudié le modèle de l'acteur, regarda SEDA, etc.

Dans leur présentation, ils ont mentionné que ce modèle est fondamentalement la façon dont les routeurs de travail; cependant, je n'ai pas trouvé de bonnes descriptions de la façon dont les routeurs de travail.

Sont là quelques bons pointeurs vers une meilleure explication?

Answer 1

Le Google Code du projet fait référence à un document technique sur la mise en œuvre de l'anneau de la mémoire tampon, mais il est un peu sec, universitaire et difficile pour quelqu'un qui veut apprendre comment il fonctionne. Cependant il y a quelques posts sur des blogs qui ont commencé à expliquer le fonctionnement interne dans un moyen plus lisible. Il y a une explication de l'anneau de la mémoire tampon , qui est la base de la perturbateur modèle, une description de la consommation d'obstacles (la partie relative à la lecture de la perturbateur) et quelques informations sur la gestion de plusieurs producteurs disponibles.

La description la plus simple de le Perturbateur: C'est un moyen d'envoyer des messages entre les threads dans la manière la plus efficace possible. Il peut être utilisé comme une alternative à une file d'attente, mais c'est aussi le partage d'un certain nombre de caractéristiques avec SEDA et des Acteurs.

Par rapport aux Files d'attente:

Le Perturbateur offre la possibilité de faire passer un message sur un autre fils, le réveiller si nécessaire (similaire à un BlockingQueue). Cependant, il y a 3 différences distinctes.

1. L'utilisateur de la Perturbateur définit la façon dont les messages sont stockés en étendant la classe d'Entrée et fournissant une usine pour faire le preallocation. Cela permet la réutilisation de la mémoire (copie) ou l'Entrée peut contenir une référence à un autre objet.
2. Placer des messages dans le Perturbateur est un 2-phase de processus, d'abord une fente est revendiquée dans l'anneau de la mémoire tampon, ce qui permet à l'utilisateur avec l'Entrée qui peut être rempli avec les données appropriées. Ensuite, l'entrée doit être engagé, ce 2-phase d'approche est nécessaire pour permettre la souplesse d'utilisation de la mémoire mentionnés ci-dessus. C'est la validation qui rend le message visible par les consommateurs threads.
3. Il est de la responsabilité du consommateur de conserver une trace des messages qui ont été consommés à partir de l'anneau de la mémoire tampon. Le déplacement de cette responsabilité éloigner de la mémoire tampon en anneau lui-même a contribué à réduire le montant de l'écriture de contention que chaque thread dispose de son propre compteur.

Par rapport aux Acteurs

L'Acteur modèle est plus proche de la Perturbateur que la plupart des autres modèles de programmation, en particulier si vous utilisez la BatchConsumer/BatchHandler classes qui sont fournis. Ces classes de masquer toutes les complexités de maintien de l'consommé des numéros de séquence et de fournir un ensemble de simples rappels lorsque des événements importants se produisent. Cependant, il ya quelques différences subtiles.

1. Le Perturbateur utilise un 1 fil - 1 modèle de consommation, où les Acteurs utilisent un N:M modèle c'est à dire que vous pouvez avoir autant d'acteurs que vous voulez et ils seront distribués à l'échelle d'un fixe nombre de threads (généralement 1 par cœur).
2. Le BatchHandler interface fournit un autre (et très important) rappel onEndOfBatch(). Cela permet de ralentir les consommateurs, par exemple, ceux qui font les I/O pour le lot événements de concert pour améliorer le débit. Il est possible de faire du traitement par lots dans un autre Acteur cadres, cependant, comme presque tous les autres cadres de ne pas fournir un rappel à la fin du lot, vous devez utiliser un délai d'expiration pour déterminer la fin d'un lot, provoquant une faible latence.

Par rapport à SEDA

LMAX construit le Perturbateur modèle pour remplacer un SEDA.

1. La principale amélioration qu'il a fourni plus de SEDA a été la capacité à travailler en parallèle. Pour ce faire, le Perturbateur supporte le multi-casting messages les mêmes messages (dans le même ordre) à plusieurs consommateurs. Cela évite la nécessité de fourche étapes du pipeline.
2. Nous avons également permettre aux consommateurs d'attendre les résultats d'autres consommateurs sans avoir à mettre un autre queuing stade de entre eux. Un consommateur peut simplement regarder le numéro de séquence d'un consommateur qu'il est tributaire. Cela évite la nécessité de joindre les étapes dans le pipeline.

Par rapport aux Barrières de la Mémoire

Une autre façon de penser, c'est comme structuré, ordonné barrière de mémoire. Lorsque le producteur de la barrière de la forme de la barrière d'écriture et le consommateur de la barrière est lire la barrière.

Answer 2

D'abord nous aimerions comprendre le modèle de programmation qu'il offre.

Il y a un ou plusieurs auteurs. Il y a un ou plusieurs lecteurs. Il y a une ligne d'entrées, totalement ordonnée de l'ancien au nouveau (comme sur la photo de gauche à droite). Les écrivains peuvent ajouter de nouvelles entrées à l'extrémité droite. Chaque lecteur lit les entrées séquentiellement de gauche à droite. Les lecteurs ne peuvent pas lire le passé des écrivains, évidemment.

Il n'y a pas de concept d'entrée de suppression. J'utilise le "lecteur" au lieu de "consommateur" pour éviter l'image des entrées de consommation. Toutefois, nous comprenons que les entrées sur la gauche de la dernière lecteur de devenir inutile.

Généralement, les lecteurs peuvent lire simultanément et de manière indépendante. Cependant, nous pouvons déclarer des dépendances chez les lecteurs. Lecteur de dépendances peut être arbitraire graphe acyclique. Si le lecteur B dépend de lecteur, un lecteur de B ne peut pas lire au-delà de lecteur A.

Lecteur de la dépendance se pose parce que les lecteurs peuvent annoter une entrée, et le lecteur B dépend que de l'annotation. Par exemple, Un fait un peu de calcul sur une entrée, et stocke le résultat dans le champ a dans l'entrée. Un passer ensuite, et maintenant B peut lire à l'entrée, et la valeur de a stockée. Si le lecteur C ne dépend pas de A, C ne doit pas tenter de lire en a.

C'est en effet un intéressant modèle de programmation. Quelle que soit la performance, le modèle seule peut bénéficier beaucoup d'applications.

Bien sûr, LMAX, son but principal est la performance. Il utilise un pré-alloués anneau d'entrées. L'anneau est assez grand, mais il est délimité, de sorte que le système ne sera pas chargé au-delà de la capacité de conception. Si l'anneau est plein, écrivain(s) doit attendre jusqu'à ce que le plus lent des lecteurs de l'avance et de faire de la place.

Entrée objets sont pré-attribuées et de vivre éternellement, pour réduire le coût de la collecte des ordures. Nous ne l'insérez pas l'entrée de nouveaux objets ou supprimer les anciens de l'entrée des objets, au lieu de cela, l'écrivain demande de pré-inscription, le remplir ses champs, et d'en informer les lecteurs. Cette apparente 2-phase d'action est vraiment tout simplement une action atomique

setNewEntry(EntryPopulator);

interface EntryPopulator{ void populate(Entry existingEntry); }

Pré-affectation des entrées signifie également adjacent entrées (très probable) localiser dans les zones adjacentes de cellules de mémoire, et parce que les lecteurs de lire les entrées de façon séquentielle, c'est important d'utiliser des caches CPU.

Et beaucoup d'efforts pour éviter de verrouillage, CAS, même barrière de mémoire (par exemple, utilisation d'un non-volatile variable de séquence si il n'y a qu'un écrivain)

Pour les développeurs de lecteurs: les Différents annoter les lecteurs doivent écrire dans différents domaines, pour éviter d'écrire de contention. (En fait, ils doivent écrire à différentes lignes de cache.) Une annotation lecteur ne doit pas toucher quelque chose que les autres non-dépendante lecteurs peuvent lire. C'est pourquoi je dis que ces lecteurs annoter les entrées, au lieu de modifier les entrées.

Answer 3

Martin Fowler a écrit un article sur LMAX et le modèle disruptor, LMAX de l’Architecture, il peut préciser davantage.

Answer 4

J'ai effectivement pris le temps d'étudier la source, par pure curiosité, et l'idée derrière cela est assez simple. La version la plus récente au moment de la rédaction de ce post est 3.2.1.

Il y a un tampon de stockage de pré-alloués événements qui va contenir les données pour les consommateurs à lire.

Le tampon est soutenu par un ensemble d'indicateurs (tableau d'entiers) de sa longueur qui décrit la disponibilité de la mémoire tampon de fentes (voir plus loin pour les détails). Le tableau est accessible comme une java#AtomicIntegerArray, donc, pour les fins de la présente explenation on peut tout aussi bien supposer qu'il soit.

Il peut être n'importe quel nombre de producteurs. Lorsque le producteur veut écrire dans la mémoire tampon, un long numéro est généré (comme dans l'appel de AtomicLong#getAndIncrement, le Perturbateur utilise sa propre mise en œuvre, mais il fonctionne de la même manière). Appelons cela a généré un long producerCallId. De manière similaire, un consumerCallId est généré lorsqu'un consommateur se TERMINE la lecture d'un logement à partir d'un tampon. La plus récente consumerCallId est accessible.

(Si il y a beaucoup de consommateurs, l'appel avec le plus petit id est choisie.)

Ces identifiants sont ensuite comparés, et si la différence entre les deux est moindre que le tampon de côté, le producteur est autorisé à écrire.

(Si le producerCallId est plus grande que la récente consumerCallId + bufferSize, cela signifie que la mémoire est pleine, et le producteur est obligé de bus-attendre jusqu'à ce qu'une place devient disponible.)

Le producteur est ensuite affecté à l'emplacement dans la mémoire tampon en fonction de son callId (qui est prducerCallId modulo bufferSize, mais depuis le bufferSize est toujours une puissance de 2 (limite appliquée sur le tampon de la création), le actuall fonctionnement utilisé est producerCallId & (bufferSize - 1)). Il est ensuite libre de les modifier le cas dans cet emplacement.

(L'algorithme est un peu plus compliqué, impliquant la mise en cache récente consumerId dans un autre atomique de référence pour l'optimisation).

Lorsque l'événement a été modifié, le changement est "publié". Lors de la publication de la fente respective dans le drapeau de tableau est rempli avec la mise à jour du drapeau. La valeur de l'indicateur est le nombre de la boucle (producerCallId divisé par la taille de tampon (nouveau depuis bufferSize est une puissance de 2, le fonctionnement réel est un décalage à droite).

De manière similaire, il peut être n'importe quel nombre de consommateurs. Chaque fois qu'un consommateur qui souhaite accéder à la mémoire tampon, une consumerCallId est généré (en fonction de la façon dont les consommateurs ont été ajoutés à la perturbateur atomiques utilisés dans la génération d'identifiants peuvent être partagées ou distincte pour chacun d'eux). Cette consumerCallId est ensuite comparée à la plus récente producentCallId, et si c'est le moindre des deux, le lecteur est autorisé à passer.

(De même, si le producerCallId est de même pour la consumerCallId, cela signifie que la mémoire tampon est empety et le consommateur est obligé d'attendre. La manière d'attente est défini par un WaitStrategy pendant perturbateur de la création.)

Pour les consommateurs individuels (ceux avec leurs propres id generator), la prochaine chose à vérifier la capacité de lot de consommer. Les fentes dans la mémoire tampon sont examinées dans l'ordre de l'un respectif de la consumerCallId (l'indice est déterminé de la même manière que pour les producteurs), à l'un respectif de la récente producerCallId.

Ils sont examinés dans une boucle, en comparant la valeur de l'indicateur écrit dans le drapeau de tableau, à l'encontre d'un indicateur de la valeur générée pour la consumerCallId. Si les indicateurs de match cela signifie que les producteurs de remplissage des fentes a commis leurs modifications. Si non, la boucle est cassé, et le plus engagé changeId est retourné. Les fentes de ConsumerCallId à reçu en changeId peut être consommé dans le lot.

Si un groupe de consommateurs lisez ensemble (celles qui ont partagé id generator), chacun ne prend qu'un seul callId, et seule la fente pour que seul callId est vérifié et retourné.

Answer 5

À partir de cet article:

Le perturbateur modèle est un dosage de la file d'attente soutenue par une circulaire tableau (c'est à dire la mémoire tampon en anneau) rempli de pré-alloué de transfert les objets qui utilise de la mémoire-les obstacles à synchroniser les producteurs et les les consommateurs par le biais de séquences.

Mémoire-les obstacles sont un peu difficile à expliquer et Trisha du blog a fait la meilleure tentative à mon avis avec ce post: http://mechanitis.blogspot.com/2011/08/dissecting-disruptor-why-its-so-fast.html

Mais si vous n'avez pas envie de plonger dans les détails de bas niveau, vous pouvez simplement savoir que la mémoire des obstacles en Java sont mis en œuvre par l' volatile mot-clé ou par l'intermédiaire de l' java.util.concurrent.AtomicLong. Le perturbateur modèle de séquences d' AtomicLongs et sont communiquées en arrière et en avant entre les producteurs et les consommateurs par le biais de la mémoire-les obstacles au lieu de les verrous.

Je trouve plus facile de comprendre un concept à l'aide de code, de sorte que le code ci-dessous est un simple helloworld de CoralQueue, qui est un perturbateur modèle de mise en œuvre effectuée par CoralBlocks avec laquelle je suis affilié. Dans le code ci-dessous vous pouvez voir comment le perturbateur modèle met en œuvre le dosage et la façon de l'anneau de la mémoire tampon (c'est à dire tableau circulaire) permet d'ordures-la libre communication entre deux 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...
    }
}