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インターフェースがサブインターフェースの組み合わせとして追加されました。

Java マップ インターフェース

バージョン1.8のMapインターフェース図は以下のようになります。Setは対応するMapのサブケースと考えることができます。Mapの値は常に特定の定数であり、この定数は無視できますが、Set APIは対応するメソッド（ただし名前は異なります）を使用します。下部には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))です。

州

同時変更問題

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

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

変更カウンター

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

コレクション.synchronizedMap()

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

public V put ( Kキー、V値) { synchronized ( mutex ) { return m . put (キー、値); } }

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

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

ネイティブ同期

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

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 ( Entry < String , String > s : map . entrySet ()) { /*  * 何らかの遅い操作により、他の高速な操作が遅延される可能性があります。 * 個々の反復処理での同期は不可能です。 */ // ... } }

再入可能読み取り書き込みロック

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

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

護送船団

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

複数のコア

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

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

ハッシュテーブルはどちらも高速です
ハッシュテーブルはどちらも高速です

順序付けられたマップのみが拡大縮小され、同期されたマップは後退します同期されたマップは、スケールされた順序付きマップと似たものになりました。

予測可能なレイテンシ

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

一貫性が弱い

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

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

ConcurrentMap 1.5 メソッド

ConcurrentMapが提供する操作の中には、 には含まれないものがありますMap。これは、 を拡張することで変更のアトミック性を実現します。 は、で識別されるエントリにreplace(K, v1, v2)が存在するかどうかをテストし、 が見つかった場合にのみ、 をアトミックに に置き換えます。 new は、が既に に存在する場合にのみを実行します。また、 は、が既に に存在しない場合にのみ を実行し、が存在する場合にのみ からを削除します。このアトミック性は、一部のマルチスレッド環境では重要になりますが、弱い一貫性制約とは関係ありません。 v1Kv1v2replace(k, v)put(k, v)kMapputIfAbsent(k, v)put(k, v)kMapremove(k, v)Entryvv

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

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

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

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

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

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

k == null || v1 == null || v2 == nullの場合{新しいNullPointerException ()をスローします。 }if ( m . containsKey ( k ) && Objects . equals ( m . get ( k ), v1 )) { m . put ( k , v2 ); trueを返します。} else falseを返します。}

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

// Map が null キーまたは null 値をサポートしていない場合 (明らかに独立して) if ( k == null || v == null ) { throw new NullPointerException (); }if ( m . containsKey ( k ) && Objects . equals ( m . get ( k ), v )) { m . remove ( k ); trueを返します。} else falseを返します。}

ConcurrentMap 1.8 メソッド

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 実装は自動的にアトミックになります。ロックフリーの手法は具象クラスにおけるオーバーライドよりも遅くなる可能性があるため、具象クラスではそれらをアトミックに実装するかどうかを選択し、並行性プロパティをドキュメント化することができます。

ロックフリーの原子性

ConcurrentMaps には、十分に高いコンセンサス数、つまり infinity を持つメソッドが含まれているため、ロックフリーの手法を使用できます。つまり、任意の数のs をコーディネートできます。この例は Java 8 でも実装できますが、より一般的なロックフリーのパターン全体を示しています。この例は ConcurrentMap の内部構造とは関係なく、クライアントコードによる ConcurrentMap の使用法に関するものです。例えば、Map 内の値に定数 C をアトミックに乗算したいとします。 Threadmerge()

static final long C = 10 ; void atomicMultiply ( ConcurrentMap < Long , Long > map , long key ) { while ( true ) { 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 ) { while ( true ) { 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 ]コレクションパッケージに由来しています。

参照

引用

  1. ^ a b Goetz et al. 2006、pp. 84–85、§5.2 並行コレクション。
  2. ^ Goetz et al. 2006、pp.85-86、§5.2.1 ConcurrentHashMap。
  3. ^ Goetz et al. 2006、pp. 82–83、§5.1.2 Iterators and ConcurrentModificationException。
  4. ^ Goetz et al. 2006、pp.84-85、§5.2.1 ConcurrentHashMap。
  5. ^ "java.util.Collections.synchronizedMap" . Java / Java SE / 11 / API / java.base. Oracleヘルプセンター. 2018年9月19日. 2020年7月17日閲覧。
  6. ^ Goetz et al. 2006、pp.95–98、§13.5 読み取り/書き込みロック。
  7. ^ Goetz et al. 2006、pp.85-86、§5.21 ConcurrentHashMap。
  8. ^ Vanhelsuwé, Laurence (1999年1月1日). 「コンテナフレームワークの戦い：どれを使うべきか？」 . JavaWorld . 2020年7月17日閲覧。
  9. ^ Lea, Doug . 「util.concurrentパッケージリリース1.3.4の概要」 。 2011年1月1日閲覧。

参考文献

  • ブライアン・ゲッツ、ティム・パイエルス、ジョシュア・ブロック、ジョセフ・ボウビア、デイビッド・ホームズ、ダグ・リー（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プログラミングには、コレクションに関するページがあります。
「 https://en.wikipedia.org/w/index.php?title=Java_ConcurrentMap&oldid=1325768580」から取得