Java ConcurrentMap - Java ConcurrentMap

Java Collections Framework verze 1.5 a novější v programovacím jazyce Java definuje a implementuje původní běžné jednovláknové Mapy a také nové Mapy bezpečné pro vlákna implementující java.util.concurrent.ConcurrentMaprozhraní mezi jinými souběžnými rozhraními. V prostředí Java 1.6 java.util.NavigableMapbylo přidáno rozhraní, rozšiřující java.util.SortedMapse a java.util.concurrent.ConcurrentNavigableMaprozhraní bylo přidáno jako kombinace podrozhraní.

Rozhraní Java Map

Schéma rozhraní verze 1.8 Map má tvar níže. Sady lze považovat za dílčí případy odpovídajících Map, ve kterých jsou hodnoty vždy určitou konstantou, kterou lze ignorovat, ačkoli rozhraní Set API používá odpovídající, ale odlišně pojmenované metody. V dolní části je java.util.concurrent.ConcurrentNavigableMap, což je vícenásobná dědičnost.

• java.util.Collection
  • java.util.Map
    • java.util.SortedMap
      • java.util.NavigableMap
        • java.util.concurrent.ConcurrentNavigableMap
    • java.util.concurrent.ConcurrentMap
      • java.util.concurrent.ConcurrentNavigableMap

Implementace

ConcurrentHashMap

Pro neuspořádaný přístup podle definice v rozhraní java.util.Map implementuje java.util.concurrent.ConcurrentHashMap java.util.concurrent.ConcurrentMap. Mechanismus je hašovací přístup k hašovací tabulce se seznamy položek, přičemž každá položka obsahuje klíč, hodnotu, hodnotu hash a další odkaz. Před verzí Java 8 existovalo několik zámků, z nichž každý serializoval přístup k „segmentu“ tabulky. V prostředí Java 8 se nativní synchronizace používá na hlavách samotných seznamů a seznamy mohou mutovat do malých stromů, když hrozí, že se kvůli nešťastným kolizím hash příliš zvětší. Java 8 také optimisticky využívá primitivní komparaci k umístění počátečních hlav do tabulky, což je velmi rychlé. Výkon je O (n), ale občas je nutné zpoždění, když je nutné provést opětovné promytí. Poté, co se hashovací tabulka rozšíří, nikdy se nezmenší, což může vést k „úniku paměti“ po odebrání položek.

ConcurrentSkipListMap

Pro objednaný přístup definovaný rozhraním java.util.NavigableMap byla do Java 1.6 přidána java.util.concurrent.ConcurrentSkipListMap, která implementuje java.util.concurrent.ConcurrentMap a také java.util.concurrent.ConcurrentNavigableMap. Jedná se o seznam Přeskočit, který k výrobě stromu používá techniky bez zámku. Výkon je O (log (n)).

Ctrie

• Ctrie Strom bez zámků založený na trie.

Problém se současnou úpravou

Jedním z problémů vyřešených balíčkem Java 1.5 java.util.concurrent je problém se souběžnou úpravou. Třídy kolekce, které poskytuje, mohou být spolehlivě použity více vlákny.

Všechny nesouběžné Mapy a další kolekce sdílené vlákny musí používat nějakou formu explicitního uzamčení, jako je nativní synchronizace, aby se zabránilo souběžné úpravě, jinak musí existovat způsob, jak z logiky programu dokázat, že k souběžné úpravě nemůže dojít. Souběžná úprava mapy více vlákny někdy zničí vnitřní konzistenci datových struktur uvnitř mapy, což povede k chybám, které se projevují zřídka nebo nepředvídatelně a které je obtížné detekovat a opravit. Souběžná úprava jedním vláknem s přístupem ke čtení jiným vláknem nebo vlákny také někdy poskytne čtenáři nepředvídatelné výsledky, ačkoli interní konzistence Map nebude zničena. Použití externí logiky programu k zabránění souběžných úprav zvyšuje složitost kódu a vytváří nepředvídatelné riziko chyb ve stávajícím i budoucím kódu, i když umožňuje použití nesouběžných kolekcí. Zámky nebo logika programu však nemohou koordinovat externí vlákna, která mohou přijít do styku s kolekcí.

Čítače úprav

Abychom pomohli s problémem souběžných modifikací, používají nesouběžné implementace Map a další kolekce interní čítače modifikací, které jsou konzultovány před a po čtení, aby bylo možné sledovat změny: zapisovače zvyšují čítače modifikací. Tento mechanismus má detekovat souběžnou úpravu, která vyvolá výjimku java.util.ConcurrentModificationException, ale není zaručeno, že k ní dojde ve všech případech, a neměla by se na ni spoléhat. Údržba čítače je také reduktorem výkonu. Z důvodů výkonu nejsou čítače nestálé, takže není zaručeno, že se jejich změny budou šířit mezi vlákny.

Collections.synchronizedMap ()

Jedním z řešení problému souběžných úprav je použití konkrétní třídy obálky poskytované továrnou v kolekcích: public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)která zabalí existující Mapu, která není bezpečná pro vlákna, metodami, které se synchronizují na interním mutexu. Existují také obaly pro ostatní druhy sbírek. Jedná se o částečné řešení, protože je stále možné, že k podkladové Map je možné přistupovat neúmyslně pomocí vláken, která uchovávají nebo získávají nezabalené odkazy. Všechny kolekce také implementují, java.lang.Iterableale synchronizované zabalené mapy a další zabalené kolekce neposkytují synchronizované iterátory, takže synchronizace je ponechána na kód klienta, který je pomalý a náchylný k chybám a není možné očekávat, že bude duplikován jinými spotřebiteli synchronizovaná mapa. Musí být chráněno také celé trvání iterace. Kromě toho mapa, která je zabalena dvakrát na různých místech, bude mít různé interní objekty mutexu, na kterých synchronizace fungují, což umožňuje překrývání. Delegace je reduktor výkonu, ale moderní kompilátory Just-in-Time se často silně vkládají, což omezuje snížení výkonu. Takto funguje obal uvnitř obalu - mutex je jen finální objekt am je finální zabalená mapa:

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

Synchronizace iterace se doporučuje následovně, ale synchronizuje se spíše na obálce než na interním mutexu, což umožňuje překrytí:

    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
        }
    }

Nativní synchronizace

Libovolnou mapu lze bezpečně použít v systému s více vlákny tím, že zajistíte, aby všechny přístupy k ní byly zpracovávány synchronizačním mechanismem Java:

    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.
             */ 
            ...
        }
    }

ReentrantReadWriteLock

Kód používající java.util.concurrent.ReentrantReadWriteLock je podobný kódu pro nativní synchronizaci. Z bezpečnostních důvodů by však měly být zámky použity v bloku try / finally, takže předčasný odchod, jako je házení výjimek nebo přerušení / pokračování, jistě projde odemknutím. Tato technika je lepší než použití synchronizace, protože čtení se mohou navzájem překrývat, při rozhodování o tom, jak upřednostnit zápis s ohledem na čtení, nastává nový problém. Pro jednoduchost lze místo toho použít java.util.concurrent.ReentrantLock, což nedělá žádný rozdíl pro čtení a zápis. Je možné více operací se zámky než se synchronizací, například tryLock() a 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();
    }

Konvoje

Vzájemné vyloučení má problém s konvojem Lock , ve kterém se vlákna mohou hromadit na zámku, což způsobí, že JVM bude muset udržovat drahé fronty číšníků a „zaparkovat“ čekající vlákna. Je nákladné zaparkovat a zrušit odstavení vlákna a může dojít k pomalému přepínání kontextu. Kontextové přepínače vyžadují od mikrosekund po milisekundy, zatímco vlastní základní operace Mapy obvykle trvají nanosekundy. Se zvyšováním sporu může výkon klesnout na malý zlomek propustnosti jednoho vlákna. Pokud pro zámek neexistuje žádný nebo jen malý spor, je zde malý dopad na výkon, s výjimkou testu konfliktu zámku. Moderní JVM začlení většinu zamykacího kódu a omezí jej pouze na několik pokynů, takže případ bez sporu bude velmi rychlý. Reentrantní techniky, jako je nativní synchronizace nebo java.util.concurrent.ReentrantReadWriteLock, však mají při údržbě hloubky reentrancy další zavazadla snižující výkon, což ovlivňuje také případ bez sporu. Zdá se, že problém s konvojem se s moderním JVMS uvolňuje, ale lze ho skrýt pomalým přepínáním kontextu: v tomto případě se latence zvýší, ale propustnost bude i nadále přijatelná. Se stovkami vláken vytváří doba přepnutí kontextu 10 ms latenci v sekundách.

Více jader

Řešení vzájemného vyloučení nedokážou využít veškerý výpočetní výkon vícejádrového systému, protože uvnitř kódu Map je najednou povolen pouze jeden podproces. Implementace konkrétních souběžných map poskytovaných rámcem Java Collections Framework a dalšími někdy využívají výhod více jader pomocí technik programování zdarma Lock . Techniky bez blokování využívají k provádění podmíněných aktualizací některých interních struktur Map atomové operace, jako je vnitřní metoda compareAndSet () dostupná u mnoha tříd Java, jako je AtomicReference. Primitiv compareAndSet () je ve třídách JCF rozšířen o nativní kód, který dokáže u některých algoritmů provést porovnáníAndSet na speciálních vnitřních částech některých objektů (pomocí „nebezpečného“ přístupu). Techniky jsou složité a často se spoléhají na pravidla mezivláknové komunikace poskytované těkavými proměnnými, relace předcházející, speciální druhy bezzámkových „opakovacích smyček“ (které nejsou jako zámky rotace v tom, že vždy vytvářejí pokrok) . CompareAndSet () se spoléhá na speciální instrukce specifické pro procesor. Je možné, aby jakýkoli kód Java použil pro jiné účely metodu compareAndSet () na různých souběžných třídách, aby bylo dosaženo souběžnosti bez Lock nebo dokonce Wait, která poskytuje konečnou latenci. Techniky bez zámku jsou v mnoha běžných případech jednoduché as některými jednoduchými sbírkami, jako jsou komíny.

Diagram ukazuje, jak synchronizace pomocí Collection.synchronizedMap () zabalení běžného HashMap (fialová) nemusí mít měřítko stejně dobře jako ConcurrentHashMap (červená). Ostatní jsou objednané ConcurrentNavigableMaps AirConcurrentMap (modré) a ConcurrentSkipListMap (CSLM zelené). (Plochými místy mohou být opakovaná míchání vytvářející tabulky, které jsou větší než Nursery, a ConcurrentHashMap zabírá více místa. Všimněte si, že osa y by měla říkat „put K“. Systém je 8jádrový i7 2,5 GHz, s -Xms5000m, aby se zabránilo GC). Expanze procesů GC a JVM značně mění křivky a některé interní techniky Lock-Free generují odpadky při sporech.

Předvídatelná latence

Ještě dalším problémem přístupů vzájemného vyloučení je, že předpoklad úplné atomicity provedený nějakým jednovláknovým kódem vytváří sporadická nepřijatelně dlouhá zpoždění mezi vlákny v souběžném prostředí. Zejména Iterátory a hromadné operace, jako je putAll () a další, mohou trvat déle úměrně velikosti Map, což zpozdí další vlákna, která očekávají předvídatelně nízkou latenci pro jiné než hromadné operace. Například webový server s více vlákny nemůže povolit zpoždění některých odpovědí pomocí dlouhotrvajících iterací jiných vláken provádějících další požadavky, které hledají konkrétní hodnotu. S tím souvisí skutečnost, že vlákna, která zamknou mapu, ve skutečnosti nemají vůbec žádný požadavek na vzdání se zámku, a nekonečná smyčka ve vlákně vlastníka může šířit trvalé blokování na další vlákna. Pomalá vlákna vlastníka mohou být někdy přerušena. Hash-based Mapy také podléhají spontánním zpožděním během opakovaného mytí.

Slabá konzistence

Řešení balíčků java.util.concurrency pro problém souběžné úpravy, problém konvoje, problém předvídatelné latence a vícejádrový problém zahrnuje architektonickou volbu nazvanou slabá konzistence. Tato volba znamená, že čtení jako get () nebude blokováno, i když aktualizace probíhají, a je možné, aby se i aktualizace překrývaly samy se sebou a při čtení. Slabá konzistence umožňuje například změnit obsah ConcurrentMap během jeho iterace jedním vláknem. Iterátory jsou navrženy pro použití po jednom vlákně najednou. Například mapa obsahující dvě položky, které jsou vzájemně závislé, může být čtenářským vláknem viděna nekonzistentně během úpravy jiným vláknem. Aktualizace, která má změnit klíč Entry ( k1, v ) na Entry ( k2, v ) atomicky, bude muset provést remove ( k1 ) a poté put ( k2, v ), zatímco iterace může chybět nebo jej zobrazte na dvou místech. Načtení vrátí hodnotu pro daný klíč, která odráží poslední předchozí dokončenou aktualizaci pro tento klíč. Existuje tedy vztah „stane se před“.

ConcurrentMaps neexistuje způsob, jak uzamknout celou tabulku. Neexistuje žádná možnost ConcurrentModificationException, protože existuje s neúmyslnou souběžnou úpravou nesouběžných map. Metoda size () může trvat dlouho, na rozdíl od odpovídajících nesouběžných map a dalších kolekcí, které obvykle obsahují pole velikosti pro rychlý přístup, protože může být nutné nějakým způsobem skenovat celou Mapu. Když dochází k souběžným úpravám, výsledky odrážejí stav Map v určitém čase, ale ne nutně jediný konzistentní stav, tedy size (), isEmpty () a containsValue () může být nejlépe použit pouze pro monitorování.

Metody ConcurrentMap 1.5

Existují některé operace poskytované ConcurrentMap, které nejsou v Mapě - což rozšiřuje - aby umožnily atomicitu úprav. Nahradit ( K, v1, v2 ) otestuje existenci v1 v záznamu identifikovaném K a pouze pokud je nalezen, pak je v1 atomicky nahrazen v2 . Nová náhrada ( k, v ) provede put ( k, v ) pouze v případě, že k je již na mapě. PutIfAbsent ( k, v ) také provede put ( k, v ) pouze v případě, že k již není na mapě, a remove (k, v) odstraní položku pro v, pouze pokud je v přítomné. Tato atomicita může být důležitá pro některé případy použití s ​​více vlákny, ale nesouvisí s omezením slabé konzistence.

Pro ConcurrentMaps jsou následující atomové.

m.putIfAbsent (k, v) je atomový, ale ekvivalentní:

    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) je atomové, ale ekvivalentní:

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

m.place (k, v1, v2) je atomový, ale ekvivalentní:

    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) je atomový, ale ekvivalentní:

    // 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;
    }

Metody ConcurrentMap 1.8

Protože Map a ConcurrentMap jsou rozhraní, nelze k nim přidat nové metody bez porušení implementací. Java 1.8 však přidala možnost pro výchozí implementace rozhraní a přidala do výchozích implementací rozhraní Map některé nové metody getOrDefault (Object, V), forEach (BiConsumer), replaceAll (BiFunction), computeIfAbsent (K, Function), computeIfPresent ( K, BiFunction), spočítat (K, BiFunction) a sloučit (K, V, BiFunction). Výchozí implementace v Mapě nezaručují atomicitu, ale v přepisujících výchozích hodnotách ConcurrentMap používají k dosažení atomicity techniky Lock free a existující implementace ConcurrentMap budou automaticky atomické. Bezblokové techniky mohou být pomalejší než přepsání v konkrétních třídách, takže konkrétní třídy se mohou rozhodnout je implementovat atomicky nebo ne a zdokumentovat vlastnosti souběžnosti.

Atomicita bez zámku

Je možné použít bezblokové techniky s ConcurrentMaps, protože obsahují metody dostatečně vysokého konsensuálního čísla, konkrétně nekonečna, což znamená, že může být koordinován libovolný počet vláken. Tento příklad lze implementovat pomocí Java 8 merge (), ale ukazuje celkový vzor bez zámku, který je obecnější. Tento příklad nesouvisí s vnitřními částmi ConcurrentMap, ale s použitím kódu klienta ConcurrentMap. Například pokud chceme vynásobit hodnotu v Mapě konstantou C atomově:

    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 ) je také užitečné, když je povoleno, aby položka pro klíč chyběla. Tento příklad lze implementovat pomocí Java 8 compute (), ale ukazuje celkový vzor bez zámku, který je obecnější. Náhrada ( k, v1, v2 ) nepřijímá nulové parametry, takže je někdy nutná jejich kombinace. Jinými slovy, je-li v1 null, pak je vyvolána putIfAbsent ( k, v2 ), jinak je vyvolána nahrazení ( k, v1, v2 ).

    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);
    }

Dějiny

Rámec kolekcí Java navrhl a vyvinul primárně Joshua Bloch a byl představen v JDK 1.2 . Původní třídy souběžnosti pocházely z balíčku kolekce Doug Lea .

Viz také

• Rámec kolekcí Java
• Kontejner (datová struktura)
• Souběžnost Java
• Zamkněte zdarma

Reference

• Goetz, Brian; Joshua Bloch; Joseph Bowbeer; Doug Lea; David Holmes; Tim Peierls (2006). Souběžnost Java v praxi . Addison Wesley. ISBN 0-321-34960-1. OL  25208908M .
• Lea, Doug (1999). Souběžné programování v Javě: Principy a vzory designu . Addison Wesley. ISBN 0-201-31009-0. OL  55044M .

externí odkazy

• Lekce sbírek
• Výukový program kolekce Java 6 - autor Jakob Jenkov, Kadafi Kamphulusa
• Zkrocení tygra: Rámec sbírek
• 'The Collections Framework' (dokumentace Oracle Java SE 8)
• „Výukové programy Java - sbírky“ od Josha Blocha
• Jakou kolekci Java mám použít? - Praktický vývojový diagram pro zjednodušení výběru sbírek
• "Kterou kolekci Java použít?" - Janeve George