Java コンカレントマップ

Javaプログラミング言語のJava Collections Frameworkバージョン1.5以降では、元の通常のシングルスレッドMapと、java.util.concurrent.ConcurrentMap他の並行インターフェースの中で インターフェースを実装する新しいスレッドセーフなMapが定義および実装されています。^[1] Java 1.6ではjava.util.NavigableMapインターフェースが追加され、 を拡張しjava.util.SortedMap、java.util.concurrent.ConcurrentNavigableMapインターフェースがサブインターフェースの組み合わせとして追加されました。

バージョン 1.8 の Map インターフェース ダイアグラムは、以下の形をしています。Set は、対応する Map のサブケースと考えることができます。その値は常に特定の定数であり、無視できますが、Set API は対応するものの、名前が異なるメソッドを使用します。一番下にはjava.util.concurrent.ConcurrentNavigableMap、多重継承である があります。

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

インターフェースで定義されている順序なしアクセスの場合java.util.Map、 はjava.util.concurrent.ConcurrentHashMapを実装しますjava.util.concurrent.ConcurrentMap。^[2]このメカニズムは、エントリのリストを持つハッシュ テーブルへのハッシュ アクセスです。各エントリには、キー、値、ハッシュ、および次の参照が含まれます。Java 8 より前は、テーブルの「セグメント」へのアクセスをシリアル化する複数のロックがありました。Java 8 では、リスト自体のヘッドでネイティブ同期が使用され、不幸なハッシュ衝突によりリストが大きくなりすぎる恐れがある場合、リストは小さなツリーに変化することができます。また、Java 8 は、比較と設定のプリミティブを楽観的に使用して、初期ヘッドをテーブルに配置します。これは非常に高速です。パフォーマンスはO(n)ですが、再ハッシュが必要なときに時々遅延が発生します。ハッシュ テーブルが拡大すると、縮小することはなく、エントリが削除された後にメモリの「リーク」につながる可能性があります。

インターフェースで定義されている順序付きアクセスのためにjava.util.NavigableMap、java.util.concurrent.ConcurrentSkipListMapJava 1.6で追加されました^[1]java.util.concurrent.ConcurrentMap 。また、およびも実装します。これは、ロックフリー技術を使用してツリーを作成するスキップリストjava.util.concurrent.ConcurrentNavigableMapです。パフォーマンスはO(log(n))です。

• Ctrieトライベースのロックフリーツリー。

Java 1.5java.util.concurrentパッケージによって解決された問題の 1 つは、同時変更の問題です。このパッケージが提供するコレクション クラスは、複数のスレッドによって確実に使用できます。

スレッド共有の非並行 Map およびその他のコレクションはすべて、同時変更を防ぐためにネイティブ同期などの何らかの明示的なロック形式を使用するか、プログラム ロジックから同時変更が起こらないことを証明する方法が必要です。 をMap複数のスレッドが同時に変更すると、 内のデータ構造の内部一貫性が破壊されることがありMap、まれにまたは予期せず現れ、検出と修正が困難なバグにつながります。また、1 つのスレッドによる読み取りアクセスを伴う別のスレッドによる同時変更は、マップの内部一貫性が破壊されることはありませんが、読み取り側に予期しない結果をもたらすことがあります。 同時変更を防ぐために外部プログラム ロジックを使用すると、非並行コレクションを使用できるようになりますが、コードの複雑さが増し、既存および将来のコードに予期しないエラーのリスクが生じます。ただし、ロックまたはプログラム ロジックのいずれも、 と接触する可能性のある外部スレッドを調整することはできませんCollection。

同時変更の問題に対処するため、非同時Map実装とその他のCollectionは、読み取りの前後で参照され変更を監視する内部変更カウンタを使用します。書き込み側は変更カウンタを増分します。同時変更はこのメカニズムによって検出され、 をスローすることになっていますがjava.util.ConcurrentModificationException、^[3]すべての場合に発生するとは保証されていないため、依存すべきではありません。カウンタの維持もパフォーマンスを低下させます。パフォーマンス上の理由から、カウンタは揮発性ではないため、カウンタへの変更が 間で伝播されることは保証されませんThread。

同時変更の問題に対する 1 つの解決策は、 のファクトリによって提供される特定のラッパー クラスを使用することです。public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) これは、内部ミューテックスで同期するメソッドを使用して、java.util.Collections 既存の非スレッドセーフをラップします。 ^[4]他の種類のコレクション用のラッパーもあります。これは部分的な解決策です。ラップされていない参照を保持または取得するによって、基になる が誤ってアクセスされる可能性があるからです。また、すべてのコレクションは を実装していますが、同期ラップされた Map やその他のラップされた は同期イテレータを提供しないため、同期はクライアント コードに委ねられます。このクライアント コードでは、処理が遅く、エラーが発生しやすく、同期された の他のコンシューマによって複製されることは期待できません。反復処理の全期間も保護する必要があります。さらに、異なる場所で 2 回ラップされた は、同期が動作する異なる内部ミューテックス オブジェクトを持つため、重複が可能になります。委譲はパフォーマンスを低下させますが、最近の Just-in-Time コンパイラはインライン化が頻繁に行われるため、パフォーマンスの低下が制限されます。ラッパー内でのラッピングの仕組みは次のとおりです。ミューテックスは単なる final で、m はラップされた final です。 MapMapThreadjava.lang.IterableCollectionsMapMapObjectMap

    パブリックV put ( Kキー、V値) { synchronized ( mutex ) { return m . put (キー、値); } }      
           
               
        
    

反復処理の同期は以下のように推奨されます。ただし、これは内部ミューテックスではなくラッパー上で同期するため、重複が可能になります。^[5]

    Map < String , String > wrapperMap = Collections . synchronizedMap ( map ); ... synchronized ( wrapperMap ) { for ( final String s : wrapperMap . keySet ()) { // おそらく長時間かかる操作が何度も実行され、他のすべてのアクセスが遅延される} }    
          
      
              
            
            
        
    

Any はMap、それに対するすべてのアクセスが Java 同期メカニズムによって処理されることを保証することにより、マルチスレッド システムで安全に使用できます。

    final Map < String , String > map = new HashMap <> (); ... // スレッド A // マップ自体をロックとして使用します。代わりに、合意された任意のオブジェクトを使用できます。synchronized ( map ) { map . put ( "key" , "value" ); } .. // スレッド B synchronized ( map ) { String result = map . get ( "key" ); ... } ... // スレッド C synchronized ( map ) { for ( final Entry < String , String > s : map . entrySet ()) { /*              * おそらく遅い操作があり、他のすべての高速な操作を遅らせます。             * 個々の反復での同期は不可能です。             */ ... } }      
    
    
    
     
       
    
    
    
      
           
         
     
    
    
      
               
            


 
            
        
    

を使用するコードは、java.util.concurrent.ReentrantReadWriteLockネイティブ同期のコードと似ています。ただし、安全のために、ロックは try/finally ブロック内で使用する必要があり、java.lang.Exceptionスローや break/continue などの早期終了が確実にロック解除を通過するようにします。この手法は同期^{[6] を}使用するよりも優れています。読み取りが互いに重複する可能性があるため、読み取りに関して書き込みをどのように優先順位付けするかを決定するという新しい問題があります。簡単にするためにjava.util.concurrent.ReentrantLock、代わりに読み取り/書き込みを区別しない を使用できます。同期よりもロックに対する操作が多く、 や などが可能tryLock()ですtryLock(long timeout, TimeUnit unit)。

    final ReentrantReadWriteLock lock = new ReentrantReadWriteLock (); final ReadLock readLock = lock . readLock (); final WriteLock writeLock = lock . writeLock (); .. // スレッド A try { writeLock . lock (); map . put ( "key" , "value" ); ... } finally { writeLock . unlock (); } ... // スレッド B try { readLock . lock (); final String s = map . get ( "key" ); .. } finally { readLock . unlock (); } // スレッド C try { readLock . lock (); for ( final Entry < String , String > s : map . entrySet ()) { /*              * おそらく遅い操作で、他のすべての高速な操作が遅延されます。             * 個々の反復処理での同期は不可能です。             */ ... } } finally { readLock . unlock (); }     
        
        
    
    
     
        
        
        
      
        
    
    
    
     
        
            
        
      
        
    
     
     
        
               
            


 
            
        
      
        
    

相互排他制御にはロック コンボイ問題があり、スレッドがロック上に積み重なると、JVM はコストのかかる待機者のキューを維持し、待機中のスレッドを「パーク」する必要がありますThread。 スレッドのパークとパーク解除にはコストがかかりThread、コンテキスト スイッチが遅くなる可能性があります。コンテキスト スイッチにはマイクロ秒からミリ秒かかりますが、Map 自体の基本操作は通常ナノ秒しかかかりません。Thread競合が増加すると、パフォーマンスは単一のスループットのほんの一部にまで低下する可能性があります。ロックの競合がないかほとんどない場合は、パフォーマンスへの影響はほとんどありません。ただし、ロックの競合テストは除きます。最近の JVM はロック コードのほとんどをインライン化し、数個の命令にまで削減して、競合がない場合は非常に高速に保ちます。java.util.concurrent.ReentrantReadWriteLockただし、ネイティブ同期やなどの再入可能手法では、再入深度の維持においてパフォーマンスを低下させる余分な負担があり、競合がない場合にも影響します。 Convoy 問題は、最新の JVM では緩和されているように見えますが、コンテキスト切り替えが遅いために隠れてしまうことがあります。この場合、レイテンシは増加しますが、スループットは許容範囲内に留まります。数百Threads の場合、コンテキスト切り替え時間が 10 ミリ秒であれば、レイテンシは数秒になります。

Thread排他制御ソリューションでは、コード内でMap一度に1 つしか許可されないため、マルチコア システムの計算能力をすべて活用できません。Java Collections Framework などが提供する特定の同時実行 Map の実装では、ロックフリープログラミング手法を使用して複数のコアを活用することがあります。ロックフリー手法では、多くの Java クラスで使用できる compareAndSet() 組み込みメソッドなどの操作を使用して、AtomicReference一部の Map 内部構造の条件付き更新をアトミックに実行します。JCF クラスでは、compareAndSet() プリミティブがネイティブ コードによって拡張され、一部のアルゴリズムの一部のオブジェクトの特殊な内部部分に対して compareAndSet を実行できます (「安全でない」アクセスを使用)。この手法は複雑で、多くの場合、揮発性変数によって提供されるスレッド間通信のルール、事前発生関係、特殊な種類のロックフリー「再試行ループ」(常に進行する点でスピン ロックとは異なります) に依存します。compareAndSet() は、プロセッサ固有の特別な命令に依存します。 Java コードでは、さまざまな並行クラスの compareAndSet() メソッドを他の目的で使用して、有限のレイテンシを提供するロックフリーまたは待機フリーの並行性を実現できます。ロックフリーの手法は、多くの一般的なケースや、スタックなどのいくつかの単純なコレクションでは簡単です。

この図は、通常の HashMap (紫) をラップして同期するCollections.synchronizedMap(java.util.Map)と、ConcurrentHashMap (赤) ほどスケールしない可能性があることを示しています。他の 2 つは、順序付けされた ConcurrentNavigableMap の AirConcurrentMap (青) と ConcurrentSkipListMap (CSLM 緑) です。(平坦な部分は、Nursery よりも大きいテーブルを生成する再ハッシュである可能性があり、ConcurrentHashMap はより多くのスペースを占めます。y 軸は「puts K」であることに注意してください。システムは 8 コアの i7 2.5 GHz で、GC を防ぐために -Xms5000m が設定されています)。GC と JVM プロセスの拡張により曲線は大幅に変化し、一部の内部ロックフリー手法では競合時にガベージが生成されます。

排他制御アプローチのさらに別の問題は、一部のシングルスレッド コードによる完全なアトミック性の想定により、並行環境では許容できないほど長いスレッド間遅延が散発的に発生することです。特に、イテレータや putAll() などのバルク操作は、 Map のサイズに比例した時間がかかることがあり、バルクThread操作以外の低レイテンシが予想される他の を遅延させます。たとえば、マルチスレッド Web サーバーでは、特定の値を検索する他の要求を実行する他のスレッドの長時間反復によって一部の応答が遅延することを許容できません。これに関連して、Threadをロックする は実際にはロックを解放する必要がまったくなく、所有者 での無限ループによって他の に永続的なブロックが伝播する可能性があるMapという事実があります。遅い所有者は、時々中断されることがあります。ハッシュベースの Map も、再ハッシュ中に自発的な遅延の影響を受けます。 ThreadThreadThread

java.util.concurrent同時変更問題、護送船団問題、予測可能なレイテンシ問題、およびマルチコア問題に対するパッケージのソリューションには、弱い一貫性と呼ばれるアーキテクチャ上の選択が含まれています。この選択は、更新が進行中であっても のような読み取りがブロックget(java.lang.Object)されず、更新がそれ自体および読み取りと重複しても許容されることを意味します。弱い一貫性により、たとえば、ConcurrentMap1 つの による反復処理中に の内容が変更されることが許容されますThread。^[7]イテレータは、Thread一度に 1 つずつ使用されるように設計されています。したがって、たとえば、Map相互に依存する 2 つのエントリを含む は、Thread別の による変更中にリーダーから一貫性のない方法で参照される可能性がありますThread。エントリ ( k1,v ) のキーをエントリ ( k2,v )にアトミックに変更することになっている更新では、 remove( k1 ) を実行してから put( k2, v ) を実行する必要がありますが、反復処理ではエントリが見つからないか、2 か所でエントリが参照される可能性があります。取得では、特定のキーに対して、そのキーの最新の完了した更新を反映する値を返します。したがって、「事前に起こる」関係が存在します。

ConcurrentMapがテーブル全体をロックする方法はありません。ConcurrentModificationException同時実行でない を不注意に同時変更した場合のように、 が発生する可能性はありませんMap。このsize()メソッドは、対応する同時実行でない やその他のコレクション (通常は高速アクセス用にサイズ フィールドを含む) とは異なり、長い時間がかかる可能性があります。これMapは、何らかの方法で 全体をスキャンする必要がある場合があるためですMap。同時変更が発生している場合、結果はある時点での の状態を反映しますMapが、必ずしも単一の一貫した状態を反映しているわけではありません。したがってsize()、isEmpty()はcontainsValue(java.lang.Object)監視のみに使用するのが最適です。

によって提供される操作の中には、変更のアトミック性を可能にするために拡張されるものConcurrentMapがあり、 には含まれていません。 replace( K, v1, v2 ) は、 Kによって識別されるエントリにv1が存在するかどうかをテストし、見つかった場合にのみ、アトミックにv1をv2に置き換えます。新しい replace( k,v )は、 k がすでにマップ内にある場合にのみput( k,v ) を実行します。また、 putIfAbsent( k,v )は、 k がにまだ存在しない場合にのみput( k,v ) を実行し、 remove(k, v) は、 v が存在する場合にのみ v のエントリを削除します。このアトミック性は、一部のマルチスレッドの使用例では重要になる可能性がありますが、弱い一貫性制約とは関係ありません。 MapMap

sの場合ConcurrentMap、以下はアトミックです。

m.putIfAbsent(k, v) はアトミックですが、次と同等です:

    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) はアトミックですが、次と同等です:

    if ( k == null || v == null )の場合、新しいNullPointerException ()をスローします。if ( m.containsKey ( k )) { return m.put ( k , v ); } else { return null ; }       
          
      
          
      
         
    

m.replace(k, v1, v2) はアトミックですが、次と同等です:

    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) はアトミックですが、次と同等です:

    // Map が null キーまたは値をサポートしていない場合 (明らかに独立して) 
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 ; }           
          
         
        
         
     
        
    

Mapと はインターフェースであるためConcurrentMap、実装を壊さずに新しいメソッドを追加することはできません。ただし、Java 1.8 では、デフォルトのインターフェース実装の機能が追加され、Mapインターフェースにいくつかの新しいメソッド getOrDefault(Object, V)、forEach(BiConsumer)、replaceAll(BiFunction)、computeIfAbsent(K, Function)、computeIfPresent(K, BiFunction)、compute(K,BiFunction)、および merge(K, V, BiFunction) のデフォルト実装が追加されました。 のデフォルト実装はMapアトミック性を保証しませんが、オーバーライドのデフォルトでは、ロックフリーConcurrentMap技術を使用してアトミック性を実現し、既存の ConcurrentMap 実装は自動的にアトミックになります。ロックフリー技術は、具象クラスでのオーバーライドよりも低速になる可能性があるため、具象クラスでは、それらをアトミックに実装するかどうかを選択して、並行性プロパティをドキュメント化できます。

ConcurrentMap には、十分に高いコンセンサス数、つまり infinityのメソッドが含まれているため、ロックフリーの手法を使用できます。つまり、任意の数の を調整できます。この例は、Java 8 の merge() を使用して実装できますが、より一般的な全体的なロックフリー パターンを示しています。この例は、ConcurrentMap の内部とは関係ありませんが、クライアント コードの ConcurrentMap の使用に関係しています。たとえば、Map 内の値に定数 C をアトミックに掛ける場合は、次のようになります。 Thread

    static final long C = 10 ; void atomicMultiply ( ConcurrentMap < Long , Long > map , Long key ) { for (;;) { Long oldValue = map . get ( key ); // oldValue が null でないと仮定します。これは「ペイロード」操作であり、競合時に再計算される可能性があるため、副作用はありません。Long newValue = oldValue * C ; if ( map . replace ( key , oldValue , newValue )) break ; } }     
          
          
               
            
                 
               
                
        
    

putIfAbsent( k, v ) は、キーのエントリが存在しないことが許可されている場合にも役立ちます。この例は、Java 8 の compute() を使用して実装できますが、より一般的な全体的なロックフリー パターンを示しています。replace( k,v1,v2 ) は null パラメータを受け入れないため、場合によってはそれらの組み合わせが必要になります。つまり、v1 が null の場合は putIfAbsent( k, v2 ) が呼び出され、それ以外の場合は replace( k,v1,v2 ) が呼び出されます。

    void atomicMultiplyNullable ( ConcurrentMap < Long , Long > map , Long key ) { for (;;) { Long oldValue = map . get ( key ); // これは「ペイロード」操作であり、競合時に再計算が行われる可能性があるため、副作用があってはなりません。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 ); }      
          
               
            
                       
                
                
        
    
    
               
                    
    

Javaコレクションフレームワークは主にJoshua Blochによって設計・開発され、JDK 1.2で導入されました。^[8]オリジナルの並行クラスはDoug Leaの^[9]コレクションパッケージから生まれました。

• Java コレクション フレームワーク
• コンテナ（データ構造）
• Java の並行性
• ロックフリー

• Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer , Joseph; Holmes, David; Lea, Doug (2006)。Java Concurrency in Practice。Addison Wesley。ISBN 0-321-34960-1. OL  25208908M.
• Lea, Doug (1999)。『Java による並行プログラミング: 設計原則とパターン』 Addison Wesley。ISBN 0-201-31009-0. OL  55044M.

Wikibook Javaプログラミングには、コレクションに関するページがあります。

• コレクションレッスン
• Java 6 コレクションのチュートリアル — Jakob Jenkov、Kadafi Kamphulusa 著
• 虎を飼いならす: コレクションフレームワーク
• 「コレクション フレームワーク」(Oracle Java SE 8 ドキュメント)
• Josh Bloch 著「Java チュートリアル - コレクション」
• どの Java コレクションを使用すればよいですか? — コレクションの選択を簡素化する便利なフローチャート
• 「どの Java コレクションを使うべきか?」— Janeve George 著