Java Concurrency Utility mit JCTools

1. Übersicht

In diesem Tutorial stellen wir die JCTools-Bibliothek (Java Concurrency Tools) vor.

Einfach ausgedrückt bietet dies eine Reihe von Dienstprogrammdatenstrukturen, die für die Arbeit in einer Multithread-Umgebung geeignet sind.

2. Nicht blockierende Algorithmen

Traditionell verwendet Multithread-Code, der in einem veränderlichen gemeinsam genutzten Status arbeitet, Sperren , um Datenkonsistenz und Veröffentlichungen sicherzustellen (Änderungen, die von einem Thread vorgenommen wurden und für einen anderen sichtbar sind).

Dieser Ansatz weist eine Reihe von Nachteilen auf:

  • Threads werden möglicherweise blockiert, wenn versucht wird, eine Sperre zu erhalten, und es werden keine Fortschritte erzielt, bis der Vorgang eines anderen Threads abgeschlossen ist. Dies verhindert effektiv Parallelität
  • Je stärker die Sperrenkonflikte sind, desto mehr Zeit verbringt die JVM mit dem Planen von Threads, dem Verwalten von Konflikten und Warteschlangen wartender Threads und desto weniger realer Arbeit leistet sie
  • Deadlocks sind möglich, wenn mehr als eine Sperre beteiligt ist und sie in falscher Reihenfolge erfasst / freigegeben werden
  • Eine Gefahr der Prioritätsumkehr ist möglich - ein Thread mit hoher Priorität wird gesperrt, um zu versuchen, eine Sperre durch einen Thread mit niedriger Priorität zu erhalten
  • Meistens werden grobkörnige Schlösser verwendet, was die Parallelität stark beeinträchtigt. Feinkörnige Verriegelungen erfordern eine sorgfältigere Konstruktion, erhöhen den Verriegelungsaufwand und sind fehleranfälliger

Eine Alternative besteht darin, einen nicht blockierenden Algorithmus zu verwenden, dh einen Algorithmus, bei dem ein Ausfall oder eine Unterbrechung eines Threads keinen Ausfall oder eine Unterbrechung eines anderen Threads verursachen kann .

Ein nicht blockierender Algorithmus ist sperrenfrei, wenn garantiert ist, dass mindestens einer der beteiligten Threads über einen beliebigen Zeitraum Fortschritte erzielt, dh während der Verarbeitung können keine Deadlocks auftreten.

Darüber hinaus sind diese Algorithmen wartungsfrei, wenn auch ein garantierter Fortschritt pro Thread vorliegt.

Hier ist ein Beispiel für einen nicht blockierenden Stapel aus dem hervorragenden Buch "Java Concurrency in Practice". es definiert den Grundzustand:

public class ConcurrentStack { AtomicReference
    
      top = new AtomicReference
     
      (); private static class Node { public E item; public Node next; // standard constructor } }
     
    

Und auch ein paar API-Methoden:

public void push(E item){ Node newHead = new Node(item); Node oldHead; do { oldHead = top.get(); newHead.next = oldHead; } while(!top.compareAndSet(oldHead, newHead)); } public E pop() { Node oldHead; Node newHead; do { oldHead = top.get(); if (oldHead == null) { return null; } newHead = oldHead.next; } while (!top.compareAndSet(oldHead, newHead)); return oldHead.item; }

Wir können sehen , dass der Algorithmus verwendet feinkörnig Vergleichs- und Swap (CAS) Anweisungen und Lock-frei (auch wenn mehrere Threads nennen top.compareAndSet () gleichzeitig, einer von ihnen gewährleistet ist , erfolgreich zu sein) , aber nicht WAIT kostenlos, da es keine Garantie gibt, dass CAS für einen bestimmten Thread erfolgreich ist.

3. Abhängigkeit

Fügen wir zunächst die JCTools-Abhängigkeit zu unserer pom.xml hinzu :

 org.jctools jctools-core 2.1.2 

Bitte beachten Sie, dass die neueste verfügbare Version auf Maven Central verfügbar ist.

4. JCTools-Warteschlangen

Die Bibliothek bietet eine Reihe von Warteschlangen zur Verwendung in einer Umgebung mit mehreren Threads, dh ein oder mehrere Threads schreiben in eine Warteschlange und ein oder mehrere Threads lesen threadsicher und sperrenfrei daraus.

Die gemeinsame Schnittstelle für alle Warteschlangenimplementierungen ist org.jctools.queues.MessagePassingQueue .

4.1. Arten von Warteschlangen

Alle Warteschlangen können nach ihren Produzenten- / Konsumentenrichtlinien kategorisiert werden:

  • Einzelproduzent, Einzelkonsument - solche Klassen werden mit dem Präfix Spsc benannt , z. B. SpscArrayQueue
  • Einzelproduzent, mehrere Konsumenten - verwenden Sie das Spmc- Präfix, z. B. SpmcArrayQueue
  • Mehrere Hersteller, ein einziger Verbraucher - verwenden Sie das Mpsc- Präfix, z. B. MpscArrayQueue
  • Mehrere Hersteller, mehrere Verbraucher - verwenden Sie das Präfix Mpmc , z. B. MpmcArrayQueue

Es ist wichtig zu beachten, dass intern keine Richtlinienprüfungen durchgeführt werden, dh eine Warteschlange kann bei falscher Verwendung stillschweigend fehlerhaft funktionieren .

Der folgende Test füllt beispielsweise eine Warteschlange mit einem einzelnen Hersteller aus zwei Threads und besteht, obwohl dem Verbraucher nicht garantiert wird, dass er Daten von verschiedenen Herstellern sieht:

SpscArrayQueue queue = new SpscArrayQueue(2); Thread producer1 = new Thread(() -> queue.offer(1)); producer1.start(); producer1.join(); Thread producer2 = new Thread(() -> queue.offer(2)); producer2.start(); producer2.join(); Set fromQueue = new HashSet(); Thread consumer = new Thread(() -> queue.drain(fromQueue::add)); consumer.start(); consumer.join(); assertThat(fromQueue).containsOnly(1, 2);

4.2. Warteschlangenimplementierungen

Hier ist die Liste der JCTools-Warteschlangen, die die obigen Klassifizierungen zusammenfassen:

  • SpscArrayQueue - Einzelproduzent, Einzelkonsument, verwendet ein intern gebundenes Array mit gebundener Kapazität
  • SpscLinkedQueue - einzelner Produzent, einzelner Verbraucher, verwendet intern verknüpfte Liste, ungebundene Kapazität
  • SpscChunkedArrayQueue - Einzelproduzent, Einzelkonsument, beginnt mit der Anfangskapazität und wächst bis zur maximalen Kapazität
  • SpscGrowableArrayQueue - Einzelproduzent, Einzelkonsument, beginnt mit der Anfangskapazität und wächst bis zur maximalen Kapazität. Dies ist der gleiche Vertrag wie bei SpscChunkedArrayQueue . Der einzige Unterschied besteht in der internen Chunks-Verwaltung. Es wird empfohlen, SpscChunkedArrayQueue zu verwenden,da die Implementierung vereinfacht ist
  • SpscUnboundedArrayQueue - einzelner Produzent, einzelner Verbraucher, verwendet ein Array intern, ungebundene Kapazität
  • SpmcArrayQueue - Ein einzelner Produzent, mehrere Konsumenten, verwendet ein intern gebundenes Array mit gebundener Kapazität
  • MpscArrayQueue - Mehrere Produzenten, ein einziger Konsument, verwenden ein intern gebundenes Array mit gebundener Kapazität
  • MpscLinkedQueue - Mehrere Hersteller, einzelne Verbraucher, verwenden intern eine verknüpfte Liste mit ungebundener Kapazität
  • MpmcArrayQueue - Mehrere Produzenten, mehrere Konsumenten, verwenden ein Array intern, gebundene Kapazität

4.3. Atomic Queues

Alle im vorherigen Abschnitt genannten Warteschlangen verwenden sun.misc.Unsafe . Mit dem Aufkommen von Java 9 und JEP-260 ist diese API jedoch standardmäßig nicht mehr zugänglich.

Es gibt also alternative Warteschlangen, die java.util.concurrent.atomic.AtomicLongFieldUpdater (öffentliche API, weniger performant) anstelle von sun.misc.Unsafe verwenden .

They are generated from the queues above and their names have the word Atomic inserted in between, e.g. SpscChunkedAtomicArrayQueue or MpmcAtomicArrayQueue.

It's recommended to use ‘regular' queues if possible and resort to AtomicQueues only in environments where sun.misc.Unsafe is prohibited/ineffective like HotSpot Java9+ and JRockit.

4.4. Capacity

All JCTools queues might also have a maximum capacity or be unbound. When a queue is full and it's bound by capacity, it stops accepting new elements.

In the following example, we:

  • fill the queue
  • ensure that it stops accepting new elements after that
  • drain from it and ensure that it's possible to add more elements afterward

Please note that a couple of code statements are dropped for readability. The complete implementation can be found over on GitHub:

SpscChunkedArrayQueue queue = new SpscChunkedArrayQueue(8, 16); CountDownLatch startConsuming = new CountDownLatch(1); CountDownLatch awakeProducer = new CountDownLatch(1); Thread producer = new Thread(() -> { IntStream.range(0, queue.capacity()).forEach(i -> { assertThat(queue.offer(i)).isTrue(); }); assertThat(queue.offer(queue.capacity())).isFalse(); startConsuming.countDown(); awakeProducer.await(); assertThat(queue.offer(queue.capacity())).isTrue(); }); producer.start(); startConsuming.await(); Set fromQueue = new HashSet(); queue.drain(fromQueue::add); awakeProducer.countDown(); producer.join(); queue.drain(fromQueue::add); assertThat(fromQueue).containsAll( IntStream.range(0, 17).boxed().collect(toSet()));

5. Other JCTools Data Structures

JCTools offers a couple of non-Queue data structures as well.

All of them are listed below:

  • NonBlockingHashMap a lock-free ConcurrentHashMap alternative with better-scaling properties and generally lower mutation costs. It's implemented via sun.misc.Unsafe, so, it's not recommended to use this class in a HotSpot Java9+ or JRockit environment
  • NonBlockingHashMapLong like NonBlockingHashMap but uses primitive long keys
  • NonBlockingHashSet a simple wrapper around NonBlockingHashMaplike JDK's java.util.Collections.newSetFromMap()
  • NonBlockingIdentityHashMap like NonBlockingHashMap but compares keys by identity.
  • NonBlockingSetInta multi-threaded bit-vector set implemented as an array of primitive longs. Works ineffectively in case of silent autoboxing

6. Performance Testing

Let's use JMH for comparing the JDK's ArrayBlockingQueue vs. JCTools queue's performance. JMH is an open-source micro-benchmark framework from Sun/Oracle JVM gurus which protects us from indeterminism of compiler/jvm optimization algorithms). Please feel free to get more details on it in this article.

Note that the code snippet below misses a couple of statements in order to improve readability. Please find the complete source code on GitHub:

public class MpmcBenchmark { @Param({PARAM_UNSAFE, PARAM_AFU, PARAM_JDK}) public volatile String implementation; public volatile Queue queue; @Benchmark @Group(GROUP_NAME) @GroupThreads(PRODUCER_THREADS_NUMBER) public void write(Control control) { // noinspection StatementWithEmptyBody while (!control.stopMeasurement && !queue.offer(1L)) { // intentionally left blank } } @Benchmark @Group(GROUP_NAME) @GroupThreads(CONSUMER_THREADS_NUMBER) public void read(Control control) { // noinspection StatementWithEmptyBody while (!control.stopMeasurement && queue.poll() == null) { // intentionally left blank } } }

Results (excerpt for the 95th percentile, nanoseconds per-operation):

MpmcBenchmark.MyGroup:MyGroup·p0.95 MpmcArrayQueue sample 1052.000 ns/op MpmcBenchmark.MyGroup:MyGroup·p0.95 MpmcAtomicArrayQueue sample 1106.000 ns/op MpmcBenchmark.MyGroup:MyGroup·p0.95 ArrayBlockingQueue sample 2364.000 ns/op

We can see thatMpmcArrayQueue performs just slightly better than MpmcAtomicArrayQueue and ArrayBlockingQueue is slower by a factor of two.

7. Drawbacks of Using JCTools

Using JCTools has an important drawback – it's not possible to enforce that the library classes are used correctly. For example, consider a situation when we start using MpscArrayQueue in our large and mature project (note that there must be a single consumer).

Unfortunately, as the project is big, there is a possibility that someone makes a programming or configuration error and the queue is now read from more than one thread. The system seems to work as before but now there is a chance that consumers miss some messages. That is a real problem which might have a big impact and is very hard to debug.

Ideally, it should be possible to run a system with a particular system property which forces JCTools to ensure thread access policy. E.g. local/test/staging environments (but not production) might have it turned on. Sadly, JCTools does not provide such a property.

Eine weitere Überlegung ist, dass JCTools zwar erheblich schneller als das Gegenstück des JDK ist, dies jedoch nicht bedeutet, dass unsere Anwendung die gleiche Geschwindigkeit erreicht, mit der wir die benutzerdefinierten Warteschlangenimplementierungen verwenden. Die meisten Anwendungen tauschen nicht viele Objekte zwischen Threads aus und sind meistens E / A-gebunden.

8. Fazit

Wir haben jetzt ein grundlegendes Verständnis der von JCTools angebotenen Utility-Klassen und haben gesehen, wie gut sie im Vergleich zu den Gegenstücken des JDK unter hoher Last abschneiden.

Zusammenfassend lässt sich sagen, dass es sich lohnt, die Bibliothek nur zu verwenden, wenn wir viele Objekte zwischen Threads austauschen, und selbst dann muss sehr vorsichtig vorgegangen werden, um die Richtlinien für den Threadzugriff beizubehalten.

Wie immer finden Sie den vollständigen Quellcode für die obigen Beispiele auf GitHub.