Java ConcurrentMap - Java ConcurrentMap

Das Java Collections Framework Version 1.5 und höher der Programmiersprache Java definiert und implementiert die ursprünglichen regulären Singlethread-Maps sowie neue threadsichere Maps, die die java.util.concurrent.ConcurrentMapSchnittstelle neben anderen gleichzeitigen Schnittstellen implementieren. In Java 1.6 wurde die java.util.NavigableMapSchnittstelle hinzugefügt, erweitert java.util.SortedMapund die java.util.concurrent.ConcurrentNavigableMapSchnittstelle wurde als Subschnittstellenkombination hinzugefügt.

Java-Kartenschnittstellen

Das Kartenschnittstellendiagramm der Version 1.8 hat die folgende Form. Sets können als Unterfälle entsprechender Maps angesehen werden, in denen die Werte immer eine bestimmte Konstante sind, die ignoriert werden kann, obwohl die Set-API entsprechende, aber anders benannte Methoden verwendet. Unten befindet sich die java.util.concurrent.ConcurrentNavigableMap, die eine Mehrfachvererbung ist.

Implementierungen

ConcurrentHashMap

Für den ungeordneten Zugriff, wie in der java.util.Map-Schnittstelle definiert, implementiert die java.util.concurrent.ConcurrentHashMap java.util.concurrent.ConcurrentMap. Der Mechanismus ist ein Hash-Zugriff auf eine Hash-Tabelle mit Listen von Einträgen, wobei jeder Eintrag einen Schlüssel, einen Wert, den Hash und eine nächste Referenz enthält. Vor Java 8 gab es mehrere Sperren, die jeweils den Zugriff auf ein 'Segment' der Tabelle serialisierten. In Java 8 wird die native Synchronisation auf den Listenköpfen selbst verwendet, und die Listen können zu kleinen Bäumen mutieren, wenn sie durch unglückliche Hash-Kollisionen zu groß zu werden drohen. Außerdem verwendet Java 8 das primitive Vergleichen und Setzen optimistisch, um die Anfangsköpfe in der Tabelle zu platzieren, was sehr schnell ist. Die Leistung ist O(n), aber es gibt gelegentlich Verzögerungen, wenn ein Rehashing erforderlich ist. Nachdem die Hash-Tabelle erweitert wurde, verkleinert sie sich nie, was möglicherweise zu einem Speicherleck führt, nachdem Einträge entfernt wurden.

ConcurrentSkipListMap

Für den geordneten Zugriff, wie durch die java.util.NavigableMap-Schnittstelle definiert, wurde java.util.concurrent.ConcurrentSkipListMap in Java 1.6 hinzugefügt und implementiert java.util.concurrent.ConcurrentMap sowie java.util.concurrent.ConcurrentNavigableMap. Es ist eine Skip-Liste, die Lock-free-Techniken verwendet, um einen Baum zu erstellen. Die Leistung ist O(log(n)).

Ctrie

  • Ctrie Ein Trie-basierter Lock-free-Baum.

Gleichzeitiges Änderungsproblem

Ein Problem, das durch das Java 1.5-Paket java.util.concurrent gelöst wird, ist das gleichzeitige Ändern. Die bereitgestellten Sammlungsklassen können zuverlässig von mehreren Threads verwendet werden.

Alle von Threads gemeinsam genutzten, nicht gleichzeitigen Maps und andere Sammlungen müssen eine Form expliziter Sperre verwenden, wie z. Die gleichzeitige Änderung einer Map durch mehrere Threads zerstört manchmal die interne Konsistenz der Datenstrukturen innerhalb der Map, was zu Fehlern führt, die selten oder unvorhersehbar auftreten und die schwer zu erkennen und zu beheben sind. Außerdem führt die gleichzeitige Änderung durch einen Thread mit Lesezugriff durch einen oder mehrere andere Threads manchmal zu unvorhersehbaren Ergebnissen für den Leser, obwohl die interne Konsistenz der Map nicht zerstört wird. Die Verwendung externer Programmlogik zum Verhindern gleichzeitiger Änderungen erhöht die Codekomplexität und erzeugt ein unvorhersehbares Fehlerrisiko in bestehendem und zukünftigem Code, obwohl es die Verwendung nicht gleichzeitiger Sammlungen ermöglicht. Allerdings können weder Sperren noch Programmlogik externe Threads koordinieren, die mit der Collection in Kontakt kommen könnten.

Änderungszähler

Um bei dem Problem der gleichzeitigen Änderung zu helfen, verwenden die nicht gleichzeitigen Map-Implementierungen und andere Sammlungen interne Änderungszähler, die vor und nach einem Lesevorgang abgefragt werden, um auf Änderungen zu achten: Die Schreiber inkrementieren die Änderungszähler. Eine gleichzeitige Änderung soll von diesem Mechanismus erkannt werden, der eine java.util.ConcurrentModificationException auslöst, aber es ist nicht garantiert, dass sie in allen Fällen auftritt und sollte nicht als Verlass sein. Die Zählerwartung ist auch ein Leistungsminderer. Aus Leistungsgründen sind die Leistungsindikatoren nicht flüchtig, daher kann nicht garantiert werden, dass Änderungen an ihnen zwischen Threads weitergegeben werden.

Collections.synchronizedMap()

Eine Lösung für das Problem der gleichzeitigen Modifikation besteht darin, eine bestimmte Wrapper-Klasse zu verwenden, die von einer Factory in Collections bereitgestellt wird: public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)die eine vorhandene nicht-thread-sichere Map mit Methoden umschließt, die sich auf einen internen Mutex synchronisieren. Es gibt auch Wrapper für die anderen Arten von Collections. Dies ist eine Teillösung, da es immer noch möglich ist, dass Threads, die unverpackte Referenzen behalten oder erhalten, versehentlich auf die zugrunde liegende Map zugreifen. Außerdem implementieren alle Collections das, java.lang.Iterableaber die synchronisierten umschlossenen Maps und andere umschlossene Collections bieten keine synchronisierten Iteratoren die synchronisierte Karte. Die gesamte Dauer der Iteration muss ebenfalls geschützt werden. Außerdem hat eine Map, die zweimal an verschiedenen Stellen gewickelt ist, verschiedene interne Mutex-Objekte, auf die die Synchronisationen angewendet werden, was Überlappungen ermöglicht. Die Delegierung ist ein Leistungsreduzierer, aber moderne Just-in-Time-Compiler inline oft stark, was die Leistungsreduzierung begrenzt. So funktioniert die Umhüllung innerhalb des Wrappers - der Mutex ist nur ein letztes Objekt und m ist die letzte umschlossene Map: 

    public V put(K key, V value) {
        synchronized (mutex) {return m.put(key, value);}
    }

Die Synchronisierung der Iteration wird wie folgt empfohlen, jedoch wird dies auf dem Wrapper und nicht auf dem internen Mutex synchronisiert, wodurch Überlappungen möglich sind: 

    Map<String, String> wrappedMap = Collections.synchronizedMap(map);
          ...
    synchronized (wrappedMap) {
        for (String s : wrappedMap.keySet()) {
            // some possibly long operation executed possibly 
            // many times, delaying all other accesses
        }
    }

Native Synchronisation

Jede Map kann in einem Multithread-System sicher verwendet werden, indem sichergestellt wird, dass alle Zugriffe darauf vom Java-Synchronisationsmechanismus abgewickelt werden: 

    Map<String, String> map = new HashMap<String, String>();
    ...
    // Thread A
    // Use the map itself as the lock. Any agreed object can be used instead.
    synchronized(map) {
       map.put("key","value");
    }
    ..
    // Thread B
    synchronized (map) {
        String result = map.get("key");
         ...
     }
    ...
    // Thread C
    synchronized (map) {
        for (Entry<String, String> s : map.entrySet()) {
            /*
             * Some possibly slow operation, delaying all other supposedly fast operations. 
             * Synchronization on individual iterations is not possible.
             */ 
            ...
        }
    }

WiedereintretendReadWriteLock

Der Code, der ein java.util.concurrent.ReentrantReadWriteLock verwendet, ähnelt dem für die native Synchronisierung. Aus Sicherheitsgründen sollten die Sperren jedoch in einem Try/Finally-Block verwendet werden, damit ein frühes Beenden wie das Auslösen einer Ausnahme oder das Break/Continue sicher durch die Entsperrung geht. Diese Technik ist besser als die Verwendung der Synchronisierung, da sich Lesevorgänge überlappen können. Es gibt ein neues Problem bei der Entscheidung, wie die Schreibvorgänge in Bezug auf die Lesevorgänge priorisiert werden sollen. Der Einfachheit halber kann stattdessen ein java.util.concurrent.ReentrantLock verwendet werden, das keine Lese-/Schreibunterscheidung macht. Es sind mehr Operationen an den Schlössern möglich als bei der Synchronisation, wie tryLock() und tryLock(long timeout, TimeUnit unit). 

    final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    final ReadLock readLock = lock.readLock();
    final WriteLock writeLock = lock.writeLock();
    ..
    // Thread A
    try {
        writeLock.lock();
        map.put("key","value");
        ...
    } finally {
        writeLock.unlock();
    }
    ...
    // Thread B
    try {
        readLock.lock();
        String s = map.get("key");
        ..
    } finally {
        readLock.unlock();
    }
     // Thread C
    try {
        readLock.lock();
        for (Entry<String, String> s : map.entrySet()) {
            /*
             * Some possibly slow operation, delaying all other supposedly fast operations. 
             * Synchronization on individual iterations is not possible.
             */ 
            ...
        }
    } finally {
        readLock.unlock();
    }

Konvois

Der gegenseitige Ausschluss hat ein Lock-Konvoi- Problem, bei dem sich Threads auf einer Sperre anhäufen können, was dazu führt, dass die JVM teure Warteschlangen von Kellnern unterhalten und die wartenden Threads "parken" muss. Das Parken und Entparken eines Threads ist teuer, und es kann zu einem langsamen Kontextwechsel kommen. Kontextwechsel benötigen Mikrosekunden bis Millisekunden, während die eigenen grundlegenden Operationen der Karte normalerweise Nanosekunden dauern. Die Leistung kann auf einen kleinen Bruchteil des Durchsatzes eines einzelnen Threads sinken, wenn die Konkurrenz zunimmt. Wenn es keine oder nur wenige Konflikte für die Sperre gibt, hat dies jedoch nur geringe Auswirkungen auf die Leistung, mit Ausnahme des Konflikttests der Sperre. Moderne JVMs integrieren den größten Teil des Sperrcodes und reduzieren ihn auf nur wenige Anweisungen, wodurch der Fall ohne Konflikte sehr schnell bleibt. Wiedereintrittstechniken wie die native Synchronisation oder java.util.concurrent.ReentrantReadWriteLock haben jedoch zusätzliches leistungsminderndes Gepäck bei der Aufrechterhaltung der Wiedereintrittstiefe, was sich auch auf den Fall ohne Konkurrenz auswirkt. Das Convoy-Problem scheint sich mit modernen JVMS zu lösen, kann aber durch langsames Kontextwechseln verdeckt werden: In diesem Fall erhöht sich die Latenz, aber der Durchsatz ist weiterhin akzeptabel. Bei Hunderten von Threads erzeugt eine Kontextwechselzeit von 10 ms eine Latenz in Sekunden.

Mehrere Kerne

Gegenseitige Ausschlusslösungen nutzen nicht die gesamte Rechenleistung eines Multi-Core-Systems, da jeweils nur ein Thread innerhalb des Map-Codes zulässig ist. Die Implementierungen der bestimmten gleichzeitigen Maps, die vom Java Collections Framework und anderen bereitgestellt werden, nutzen manchmal mehrere Kerne, die Lock-freie Programmiertechniken verwenden. Lock-free-Techniken verwenden Operationen wie die intrinsische Methode CompareAndSet(), die in vielen Java-Klassen wie AtomicReference verfügbar ist, um bedingte Aktualisierungen einiger Map-interner Strukturen atomar durchzuführen. Das primitive CompareAndSet() wird in den JCF-Klassen durch nativen Code erweitert, der für einige Algorithmen (unter Verwendung eines „unsicheren“ Zugriffs) CompareAndSet auf speziellen internen Teilen einiger Objekte ausführen kann. Die Techniken sind komplex und stützen sich oft auf die Regeln der Interthread-Kommunikation, die durch flüchtige Variablen bereitgestellt werden, die Vorher-Beziehung, spezielle Arten von sperrfreien „Wiederholungsschleifen“ (die nicht wie Spin-Locks sind, da sie immer Fortschritt erzeugen). . Das CompareAndSet() basiert auf speziellen prozessorspezifischen Anweisungen. Es ist für jeden Java-Code möglich, die Methode CompareAndSet() für verschiedene gleichzeitige Klassen für andere Zwecke zu verwenden, um eine sperrenfreie oder sogar wartefreie Parallelität zu erreichen, die eine endliche Latenzzeit bietet. Lock-free-Techniken sind in vielen gängigen Fällen und bei einigen einfachen Sammlungen wie Stapeln einfach.

Das Diagramm zeigt, dass die Synchronisierung mit Collections.synchronizedMap(), die eine reguläre HashMap (lila) umschließt, möglicherweise nicht so gut skaliert werden kann wie ConcurrentHashMap (rot). Die anderen sind die geordneten ConcurrentNavigableMaps AirConcurrentMap (blau) und ConcurrentSkipListMap (CSLM grün). (Die flachen Stellen können Rehashes sein, die Tabellen erzeugen, die größer sind als die Nursery, und ConcurrentHashMap benötigt mehr Platz. Beachten Sie, dass auf der y-Achse 'Puts K' stehen sollte. Das System ist 8-Core i7 2,5 GHz, mit -Xms5000m, um GC zu verhindern). Die GC- und JVM-Prozesserweiterung verändern die Kurven erheblich, und einige interne Lock-Free-Techniken erzeugen bei Konflikten Müll.

Die Hash-Tabellen sind beide schnell

Nur die geordneten Maps skalieren und die synchronisierte Map fällt zurück Die synchronisierte Karte ist zurückgefallen, um den skalierten geordneten Karten ähnlich zu sein

Vorhersehbare Latenz

Ein weiteres Problem bei Ansätzen mit gegenseitigem Ausschluss besteht darin, dass die Annahme einer vollständigen Atomizität, die von einem Code mit einem einzigen Thread gemacht wird, sporadisch unannehmbar lange Verzögerungen zwischen den Threads in einer gleichzeitigen Umgebung erzeugt. Insbesondere Iteratoren und Massenoperationen wie putAll() und andere können eine zur Map-Größe proportionale Zeit in Anspruch nehmen und andere Threads verzögern, die eine vorhersehbar niedrige Latenz für Nicht-Massenoperationen erwarten. Ein Webserver mit mehreren Threads kann beispielsweise nicht zulassen, dass einige Antworten durch lang andauernde Iterationen anderer Threads verzögert werden, die andere Anforderungen ausführen, die nach einem bestimmten Wert suchen. Damit verbunden ist die Tatsache, dass Threads, die die Map sperren, keine Notwendigkeit haben, die Sperre jemals aufzugeben, und eine Endlosschleife im Besitzer-Thread kann eine dauerhafte Blockierung an andere Threads weitergeben. Langsame Besitzer-Threads können manchmal unterbrochen werden. Auch Hash-basierte Karten unterliegen beim Rehashing spontanen Verzögerungen.

Schwache Konsistenz

Die Lösung der Pakete java.util.concurrency für das Concurrent-Modification-Problem, das Convoy-Problem, das Predictable-Latency-Problem und das Multi-Core-Problem beinhaltet eine Architekturentscheidung, die als schwache Konsistenz bezeichnet wird. Diese Wahl bedeutet, dass Lesevorgänge wie get() nicht blockiert werden, selbst wenn Aktualisierungen im Gange sind, und es ist sogar zulässig, dass sich Aktualisierungen mit sich selbst und mit Lesevorgängen überschneiden. Eine schwache Konsistenz ermöglicht beispielsweise, dass sich der Inhalt einer ConcurrentMap während einer Iteration derselben durch einen einzelnen Thread ändert. Die Iteratoren sind so konzipiert, dass sie von jeweils einem Thread verwendet werden. So kann beispielsweise eine Map, die zwei voneinander abhängige Einträge enthält, von einem Leser-Thread während der Änderung durch einen anderen Thread inkonsistent gesehen werden. Ein Update, das den Schlüssel eines Eintrags ( k1,v ) atomar in einen Eintrag ( k2,v ) ändern soll, müsste einen remove( k1 ) und dann einen put( k2,v ) ausführen , während eine Iteration fehlschlagen könnte den Eintrag oder sehen Sie es an zwei Stellen. Abrufe geben den Wert für einen bestimmten Schlüssel zurück, der die letzte vorherige abgeschlossene Aktualisierung für diesen Schlüssel widerspiegelt . Es gibt also eine „passiert-vorher“-Beziehung.

Es gibt keine Möglichkeit für ConcurrentMaps, die gesamte Tabelle zu sperren. Es besteht keine Möglichkeit einer ConcurrentModificationException wie bei einer versehentlichen gleichzeitigen Änderung von nicht gleichzeitigen Maps. Die Methode size() kann viel Zeit in Anspruch nehmen, im Gegensatz zu den entsprechenden nicht gleichzeitigen Karten und anderen Sammlungen, die normalerweise ein Größenfeld für den schnellen Zugriff enthalten, da sie möglicherweise die gesamte Karte auf irgendeine Weise scannen müssen. Wenn gleichzeitige Änderungen auftreten, spiegeln die Ergebnisse den Zustand der Map zu einem bestimmten Zeitpunkt wider, aber nicht unbedingt einen einzigen konsistenten Zustand, daher können size(), isEmpty() und containsValue() am besten nur für die Überwachung verwendet werden.

ConcurrentMap 1.5-Methoden

Es gibt einige Operationen, die von ConcurrentMap bereitgestellt werden, die nicht in Map enthalten sind - die es erweitert -, um die Atomarität von Änderungen zu ermöglichen. Der replace( K, v1, v2 ) testet auf die Existenz von v1 in dem durch K identifizierten Eintrag und nur wenn er gefunden wird, wird v1 atomar durch v2 ersetzt . Das neue replace( k,v ) führt nur dann einen put( k,v ) aus, wenn k bereits in der Map vorhanden ist. Außerdem führt putIfAbsent( k,v ) nur dann einen put( k,v ) aus, wenn k noch nicht in der Map vorhanden ist, und remove(k,v) entfernt den Eintrag für v nur, wenn v vorhanden ist. Diese Atomarität kann für einige Multithread-Anwendungsfälle wichtig sein, steht jedoch nicht im Zusammenhang mit der Einschränkung der schwachen Konsistenz.

Für ConcurrentMaps sind die folgenden atomar.

m.putIfAbsent(k, v) ist atomar, aber äquivalent zu: 

    if (k == null || v == null)
            throw new NullPointerException();
    if (!m.containsKey(k)) {
        return m.put(k, v);
    } else {
        return m.get(k);
    }

m replace(k, v) ist atomar, aber äquivalent zu: 

    if (k == null || v == null)
            throw new NullPointerException();
    if (m.containsKey(k)) {
        return m.put(k, v);
    } else {
        return null;
    }

m.replace(k, v1, v2) ist atomar, aber äquivalent zu: 

    if (k == null || v1 == null || v2 == null)
            throw new NullPointerException();
     if (m.containsKey(k) && Objects.equals(m.get(k), v1)) {
        m.put(k, v2);
        return true;
     } else
        return false;
     }

m.remove(k, v) ist atomar, aber äquivalent zu: 

    // if Map does not support null keys or values (apparently independently)
    if (k == null || v == null)
            throw new NullPointerException();
    if (m.containsKey(k) && Objects.equals(m.get(k), v)) {
        m.remove(k);
        return true;
    } else
       return false;
    }

ConcurrentMap 1.8-Methoden

Da Map und ConcurrentMap Schnittstellen sind, können ihnen keine neuen Methoden hinzugefügt werden, ohne Implementierungen zu beschädigen. Java 1.8 fügte jedoch die Fähigkeit für Standardschnittstellenimplementierungen hinzu und fügte den Standardimplementierungen der Map-Schnittstelle einige neue Methoden hinzu getOrDefault(Object, V), forEach(BiConsumer), replaceAll(BiFunction), computeIfAbsent(K, Function), computeIfPresent( K, BiFunction), compute(K,BiFunction) und merge(K, V, BiFunction). Die Standardimplementierungen in Map garantieren keine Atomarität, aber in den überschreibenden ConcurrentMap-Standards verwenden diese sperrenfreie Techniken, um Atomarität zu erreichen, und vorhandene ConcurrentMap-Implementierungen sind automatisch atomar. Die sperrfreien Techniken können langsamer sein als Überschreibungen in den konkreten Klassen, sodass konkrete Klassen wählen können, ob sie sie atomar implementieren oder nicht und die Parallelitätseigenschaften dokumentieren.

Sperrfreie Atomarität

Bei ConcurrentMaps ist es möglich, Lock-free- Techniken zu verwenden, da sie Methoden mit einer ausreichend hohen Konsenszahl, nämlich unendlich, beinhalten, sodass beliebig viele Threads koordiniert werden können. Dieses Beispiel könnte mit Java 8 merge() implementiert werden, zeigt aber das allgemeine Lock-free-Muster, das allgemeiner ist. Dieses Beispiel bezieht sich nicht auf die Interna der ConcurrentMap, sondern auf die Verwendung der ConcurrentMap durch den Clientcode. Wenn wir beispielsweise einen Wert in der Map atomar mit einer Konstanten C multiplizieren möchten: 

    static final long C = 10;
    void atomicMultiply(ConcurrentMap<Long, Long> map, Long key) {
        for (;;) {
            Long oldValue = map.get(key);
            // Assuming oldValue is not null. This is the 'payload' operation, and should not have side-effects due to possible re-calculation on conflict
            Long newValue = oldValue * C;
            if (map.replace(key, oldValue, newValue))
                break;
        }
    }

putIfAbsent( k, v ) ist auch nützlich, wenn der Eintrag für den Schlüssel fehlen darf. Dieses Beispiel könnte mit Java 8 compute() implementiert werden, zeigt jedoch das allgemeine Lock-free-Muster, das allgemeiner ist. Der replace( k,v1,v2 ) akzeptiert keine Nullparameter, daher ist manchmal eine Kombination von ihnen erforderlich. Mit anderen Worten, wenn v1 null ist, wird putIfAbsent( k, v2 ) aufgerufen, andernfalls wird replace( k,v1,v2 ) aufgerufen. 

    void atomicMultiplyNullable(ConcurrentMap<Long, Long> map, Long key) {
        for (;;) {
            Long oldValue = map.get(key);
            // This is the 'payload' operation, and should not have side-effects due to possible re-calculation on conflict
            Long newValue = oldValue == null ? INITIAL_VALUE : oldValue * C;
            if (replaceNullable(map, key, oldValue, newValue))
                break;
        }
    }
    ...
    static boolean replaceNullable(ConcurrentMap<Long, Long> map, Long key, Long v1, Long v2) {
        return v1 == null ? map.putIfAbsent(key, v2) == null : map.replace(key, v1, v2);
    }

Geschichte

Das Framework für Java-Sammlungen wurde hauptsächlich von Joshua Bloch entworfen und entwickelt und wurde in JDK 1.2 eingeführt . Die ursprünglichen Parallelitätsklassen stammen aus Doug Leas Sammlungspaket.

Siehe auch

Verweise

  • Götz, Brian; Joshua Bloch; Joseph Bowbeer; Doug Lea; David Holmes; Tim Peierls (2006). Java-Parallelität in der Praxis . Addison Wesley. ISBN 0-321-34960-1. OL  25208908M .
  • Lea, Doug (1999). Gleichzeitiges Programmieren in Java: Designprinzipien und Muster . Addison Wesley. ISBN 0-201-31009-0. OL  55044M .

Externe Links