2 つのイテレータの物語: Java における競合的な変更戦略

このメモの著者は、クラクフ (ポーランド) 出身のソフトウェア開発者、Grzegorz Mirek です。彼は大学在学中の約 6 年前に Java での開発を始め、それ以来、この分野のスキルを絶えず磨いています。彼は特に JVM のパフォーマンスと最適化に興味を持っており、それについて主にブログで書いています。 Java の面接で最も人気のある質問には次のようなものがあります。 フェイルファスト反復子とフェイルセーフ反復子の違いは何ですか? これに対する最も単純な答えは次のとおりです。 反復中にコレクションが変更された場合、フェイルファスト反復子は ConcurrentModificationException をスローしますが、フェイルセーフ反復子はスローしません。 これは非常に意味深に聞こえますが、インタビュアーがフェイルセーフで何を意味するのかは不明のままです。Java 言語仕様では、この用語をイテレータに関して定義していません。ただし、競合する変更戦略は 4 つあります。

競争力のある改良

まず、競合 (または並行) 変更とは何かを定義しましょう。コレクションがあり、イテレータがアクティブなときに、このイテレータに起因しないいくつかの変更が発生したとします。この場合、競合する変更が得られます。簡単な例を示します。いくつかのスレッドがあるとします。最初のスレッドが反復し、2 番目のスレッドが同じコレクションに対して要素を挿入または削除します。ただし、シングルスレッド環境で実行すると ConcurrentModificationException が発生する可能性があります。

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

フェイルファスト

上記のコード部分は、フェイルファスト反復子の例です。ご覧のとおり、 iterator から 2 番目の要素を取得しようとしたときにConcurrentModificationExceptionがスローされました。イテレータは、コレクションが作成されてから変更されたことをどのようにして知るのでしょうか? たとえば、コレクションには、lastModifiedなどの日付/時刻スタンプが含まれる場合があります。イテレータを作成するときは、このフィールドをコピーしてイテレータ オブジェクトに保存する必要があります。次に、next()メソッドが呼び出されるたびに、コレクションのlastModified値とイテレータのコピーを単純に比較します。非常によく似たアプローチが、たとえばArrayListクラスの実装で使用されます。これには、リストが変更された回数を格納する インスタンス変数modCountがあります。

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

フェイルファスト反復子は最善の組み合わせで動作すること に注意することが重要です。つまり、同時変更のイベントでConcurrentModificationException がスローされるという保証はありません。したがって、これらに依存すべきではありません。むしろ、エラーを検出するために使用する必要があります。ほとんどの非同時コレクションはフェイルファスト反復子を提供します。

弱い一貫性

java.util.concurrentパッケージ内のほとんどの同時コレクション( ConcurrentHashMapやほとんどのQueueなど) は、一貫性の低いイテレータを提供します。この用語の意味はドキュメントで非常に詳しく説明されています。

• 他の操作と同時に処理できます
• ConcurrentModificationException をスローすることはありません
• これらは、反復子が作成された時点で既存の要素を 1 回だけ走査することが保証されており、その後の変更を反映できます (ただし、必須ではありません)。

スナップショット

この戦略では、反復子はコレクションの作成時の状態 (コレクションのスナップショット) に関連付けられます。元のコレクションに変更を加えると、基礎となるデータ構造の新しいバージョンが作成されます。これにより、スナップショットは変更されないままになるため、イテレーターの作成後に発生したコレクションへの変更は反映されません。これは古き良きコピーオンライト (COW) 手法です。これにより、同時変更の問題が完全に解決されるため、このアプローチではConcurrentModificationExceptionは生成されません。さらに、反復子は要素を変更する操作をサポートしません。コピーオンライト コレクションは使用するにはコストが高すぎる傾向がありますが、変更の発生頻度がイテレータの走査よりもはるかに低い場合には、コレクションを使用するのが理にかなっています。例としては、CopyOnWriteArrayList クラスとCopyOnWriteArraySetクラスがあります。

未定義の動作

VectorやHashtableなどの従来のコレクション型では、未定義の動作が発生する可能性があります。どちらも標準のフェイルファスト反復子を備えていますが、さらに、Enumerationインターフェイスの実装の使用を許可しており、同時変更の場合にどのように動作するかはわかりません。いくつかの要素が繰り返されたり欠落したり、あるいは奇妙な例外が発生したりする場合もあります。彼らとは遊ばないほうがいいですよ！