Lucene の同時実行バグ: 楽観的同時実行の失敗を修正する方法

Elastic認定の取得をご希望ですか？次回のElasticsearch Engineerトレーニングがいつ開催されるかご確認ください。無料のクラウドトライアルを開始するか、ローカルマシンでElasticを試すことができます。

はい、またバグ修正のブログです。しかし、この事件には意外な展開があり、オープンソースのヒーローが飛び込んできて事態を収拾するのです。

並行性のバグをデバッグするのは簡単ではありませんが、ここで取り上げます。CMU の PASTA ラボによる決定論的同時実行テスト フレームワークである Fray は、不安定な障害を確実に再現可能な障害に変えます。Fray の巧妙なシャドウ ロック設計と正確なスレッド制御のおかげで、私たちは厄介な Lucene のバグを追跡し、ついにそれを撲滅することができました。この投稿では、オープンソースのヒーローとツールが、並行処理のデバッグの負担を軽減し、ソフトウェアの世界を大きく改善している仕組みについて説明します。

並行性バグ：ソフトウェアエンジニアの悩みの種

同時実行バグは最悪です。修正が難しいだけでなく、確実に故障させること自体が最も難しい部分です。このテストの失敗TestIDVersionPostingsFormat#testGlobalVersionsを例に挙げます。これは複数のドキュメント書き込みおよび更新スレッドを生成し、Lucene の楽観的同時実行モデルに挑戦します。このテストでは、楽観的同時実行制御における競合状態が明らかになりました。つまり、ドキュメント操作は、一連の操作の中で最新のものであると誤って主張する可能性があります😱。つまり、特定の状況では、楽観的同時実行制約により失敗するはずの更新または削除操作が実際には成功する可能性があります。

Java スタック トレースが嫌いな方には申し訳ありません。注意: 削除は必ずしも「削除」を意味するわけではありません。Lucene のセグメントは読み取り専用であるため、ドキュメントの「更新」を示すこともできます。

Apache Lucene は、 DocumentsWriterクラスを通じてドキュメントを書き込む各スレッドを管理します。このクラスはドキュメント書き込み用のスレッドを作成または再利用し、各書き込みアクションはDocumentsWriterPerThread (DWPT) クラス内でその情報を制御します。さらに、ライターはDocumentsWriterDeleteQueue (DWDQ) で削除されたドキュメントを追跡します。これらの構造は、すべてのドキュメント変更アクションをメモリ内に保持し、定期的にフラッシュしてメモリ内のリソースを解放し、構造をディスクに保持します。

スレッドのブロックを防ぎ、並行システムでの高いスループットを確保するために、Apache Lucene は非常に重要なセクションのみで同期を試みます。これは実際には良いことですが、他の並行システムと同様に、問題が存在します。

偽りの希望

最初の調査で、適切に同期されていない重要なセクションがいくつか見つかりました。特定のDocumentsWriterDeleteQueueに対するすべてのやり取りは、それを囲むDocumentsWriterによって制御されます。したがって、個々のメソッドはDocumentsWriterDeleteQueue内で適切に同期されない可能性がありますが、そのメソッドの世界へのアクセスは適切に同期されます (または同期される必要があります)。(所有権とアクセスがどのように混乱するかについては深く考えないことにします。これは、多くの貢献者によって書かれた長期にわたるプロジェクトです。少しは余裕を持ってください。

しかし、フラッシュ中に同期されていない場所が 1 か所見つかりました。

これらのアクションは、単一のアトミック操作に同期されません。つまり、 newQueueが作成されてからgetMaxSeqNoが呼び出されるまでの間に、 documentsWriterクラス内のシーケンス番号を増分する他のコードが実行された可能性があります。バグを見つけました!

しかし、ほとんどの複雑なバグと同様に、根本原因を見つけるのは簡単ではありませんでした。その時、英雄が登場した。

戦いの英雄

私たちのヒーロー、PASTA ラボのAo Liと彼の同僚の登場です。フレイでどうやって彼らが危機を救ったのか、彼に説明してもらいましょう。

Fray は、カーネギーメロン大学のPASTA ラボの研究者によって開発された決定論的並行性テスト フレームワークです。Fray 構築の背後にある動機は、学界と業界の間にある顕著なギャップに起因しています。決定論的並行性テストは学術研究において 20 年以上にわたって広範に研究されてきましたが、実践者は並行プログラムをテストするために、信頼性が低く不安定であると広く認識されている方法であるストレス テストに依然頼っています。したがって、私たちは、一般性と実用性を主な目標として、決定論的な同時実行テスト フレームワークを設計および実装したいと考えました。

核となるアイデア

Fray は、本質的に、シンプルでありながら強力な原則である「順次実行」を活用します。Java の並行性モデルは重要な特性を提供します。プログラムにデータ競合がない場合、すべての実行は順次一貫しているように見えます。これは、プログラムの動作を一連のプログラム ステートメントとして表現できることを意味します。

Fray は、ターゲット プログラムを順次実行することで動作します。各ステップで、1 つを除くすべてのスレッドを一時停止し、スレッドのスケジュールを正確に制御できるようにします。同時実行をシミュレートするためにスレッドはランダムに選択されますが、選択内容は後続の確定的な再生のために記録されます。実行を最適化するために、Fray は、スレッドがロックやアトミック/揮発性アクセスなどの同期命令を実行しようとしているときにのみコンテキストスイッチを実行します。データ競合の自由に関する優れた特性は、この限定されたコンテキスト切り替えが、あらゆるスレッドインターリーブによるすべての観察可能な動作を調査するのに十分であるということです (私たちの論文には証明の概要があります)。

課題: スレッドのスケジュール制御

中心となるアイデアはシンプルに見えますが、Fray の実装には大きな課題がありました。スレッドのスケジュールを制御するには、Fray は各アプリケーション スレッドの実行を管理する必要があります。一見すると、同時実行プリミティブをカスタマイズされた実装に置き換えるという単純なことのように思えるかもしれません。ただし、JVM での同時実行制御は複雑であり、バイトコード命令、高レベルライブラリ、ネイティブメソッドが混在します。

これはウサギの穴であることが判明しました:

• たとえば、すべてのMONITORENTER命令には、同じメソッド内に対応するMONITOREXITが必要です。Fray がMONITORENTERスタブ/モックへのメソッド呼び出しに置き換える場合は、 MONITOREXIT置き換える必要があります。
• object.wait/notifyを使用するコードでは、 MONITORENTERが置き換えられる場合、対応するobject.waitも置き換えられる必要があります。この置換チェーンはobject.notify以降まで拡張されます。
• JVM は、ネイティブ コード内で特定の並行性関連のメソッド (たとえば、スレッドが終了するとobject.notify ) を呼び出します。これらの操作を置き換えるには、JVM 自体を変更する必要があります。
• クラス ローダーやガベージ コレクション (GC) スレッドなどの JVM 機能でも、同時実行プリミティブが使用されます。これらのプリミティブを変更すると、JVM 機能との不一致が生じる可能性があります。
• JDK で並行性プリミティブを置き換えると、初期化フェーズで JVM がクラッシュすることがよくあります。

これらの課題により、並行性プリミティブを包括的に置き換えることは不可能であることが明らかになりました。

私たちの解決策：シャドウロック設計

これらの課題に対処するために、Fray は、同時実行プリミティブを置き換えることなくスレッド実行を調整するための新しいシャドウ ロック メカニズムを使用します。シャドウ ロックは、スレッドの実行をガイドする仲介者として機能します。たとえば、ロックを取得する前に、アプリケーション スレッドは対応するシャドウ ロックと対話する必要があります。シャドウ ロックは、スレッドがロックを取得できるかどうかを決定します。スレッドが続行できない場合、シャドウ ロックによってそのスレッドがブロックされ、他のスレッドの実行が許可されるため、デッドロックが回避され、同時実行が制御されます。この設計により、Fray は並行性セマンティクスの正確性を維持しながら、スレッドインターリーブを透過的に制御できます。各同時実行プリミティブは、健全性と完全性を確保するために、シャドウ ロック フレームワーク内で慎重にモデル化されます。より詳しい技術的な詳細については、当社の論文をご覧ください。

さらに、この設計は将来を見据えたものとなっています。同時実行プリミティブの周囲にシャドウ ロックのインストルメンテーションのみを必要とするため、新しいバージョンの JVM との互換性が確保されます。これは、JVM の並行性プリミティブのインターフェースが比較的安定しており、長年にわたって変更されていないため実現可能です。

テストの乱闘

Fray を構築した後、次のステップは評価でした。幸いなことに、Apache Lucene などの多くのアプリケーションには、すでに同時実行テストが含まれています。このような同時実行テストは、複数のスレッドを生成し、何らかの作業を実行し、その後 (通常は) それらのスレッドが終了するまで待機し、何らかのプロパティをアサートする通常の JUnit テストです。ほとんどの場合、これらのテストは 1 つのインターリーブのみを実行するため合格します。さらに悪いことに、前述のように、一部のテストは CI/CD 環境でたまにしか失敗しないため、これらの失敗をデバッグするのは非常に困難です。同じテストを Fray で実行したところ、多数のバグが発見されました。特に、Fray は、このブログの焦点であるTestIDVersionPostingsFormat.testGlobalVersionsを含め、信頼できる再現がないため未修正のまま残っていた、以前に報告されたバグを再発見しました。幸いなことに、Fray を使用すると、それらを確定的に再生して開発者に詳細な情報を提供できるため、問題を確実に再現して修正することができます。

フレイの次のステップ

Elastic の開発者から、Fray が並行性バグのデバッグに役立ったという話を聞き、大変嬉しく思っています。私たちは、より多くの開発者が Fray を利用できるようにするために、引き続き取り組んでいきます。

私たちの短期的な目標には、乱数ジェネレータやobject.hashcodeの使用など、他の非決定論的な操作が存在する場合でも、スケジュールを決定論的に再生する Fray の機能を強化することが含まれます。また、Fray の使いやすさを向上させ、開発者が手動介入なしに既存の同時実行テストを分析およびデバッグできるようにすることを目指しています。最も重要なことは、プログラム内の同時実行の問題のデバッグやテストで課題に直面している場合は、ぜひご連絡ください。遠慮なく、 Fray Github リポジトリに問題を投稿してください。

同時実行バグを修正する時間

Ao Li と PASTA ラボのおかげで、このテストが確実に失敗するインスタンスができました。ついにこの問題を解決できます。重要な問題は、 DocumentsWriterPerThreadPoolスレッドとリソースの再利用をどのように許可するかにありました。

ここでは、世代 0 の初期削除キューを参照して各スレッドが作成されていることがわかります。

その後、フラッシュ時にキューの前進が発生し、キュー内の前の 7 つのアクションが正しく確認されます。

しかし、すべてのスレッドがフラッシュを完了する前に、2 つのスレッドが追加のドキュメントに再利用されます。

これにより、 seqNoはフラッシュ時に7と計算された想定最大値を超えて増加します。セグメント_3とnumDocsInRAMが追加されていることに注意してください。 _0

その結果、Lucene はフラッシュ中のドキュメント アクションのシーケンスを誤って考慮し、このテストの失敗が発生します。

すべての適切なバグ修正と同様に、実際の修正は約10 行のコードです。しかし、実際に理解するまでに 2 人のエンジニアが数日かかりました。

すべてのヒーローがマントを着ているわけではない

はい、決まり文句ですが、それは真実です。

並行プログラムのデバッグは非常に重要です。これらの扱いにくい同時実行バグをデバッグして解決するには、膨大な時間がかかります。Rust のような新しい言語には、このような競合状態を防ぐためのメカニズムが組み込まれていますが、世の中のソフトウェアの大部分はすでに作成されており、しかもRust以外の言語で書かれています。Java は、何年も経った今でも、最も使用されている言語の 1 つです。JVM ベースの言語でのデバッグを改善することで、ソフトウェア エンジニアリングの世界がより良くなります。また、一部の人々がコードは大規模言語モデルによって記述されると考えていることを考えると、エンジニアとしての私たちの仕事は、最終的には自分自身の悪いコードだけでなく、悪い LLM コードをデバッグすることだけになるかもしれません。しかし、ソフトウェア エンジニアリングの将来がどうであろうと、並行プログラムのデバッグはソフトウェアの保守と構築にとって重要なままです。

これをさらに素晴らしいものにしてくれた PASTA ラボの Ao Li 氏と同僚の皆さんに感謝します。

よくあるご質問