分散システムの線形化可能性のテスト

最近、とてもよく書かれた記事を見ました。著者のアニッシュさんの同意を得て、中国語に翻訳することにしました。ただし、理解を深めるために、一部の部分は逐語的に翻訳せず、若干調整します。

[[204318]]

分散システムを正しく実装することは、同時実行性と障害の問題を適切に処理する必要があるため、非常に困難です。ネットワーク パケットは遅延、重複、順序の乱れ、またはドロップが発生する可能性があり、マシンはいつでもクラッシュする可能性があります。たとえいくつかの設計が論文によって正しいことが証明されたとしても、実装時にバグを回避することは依然として困難です。

形式手法を使用しない限り、実装が正しいと仮定してもシステムをテストする必要があります。分散システムのテストも非常に困難な作業です。同時実行性と不確実性により、テスト中にバグ、特に同時マシンクラッシュや極端なネットワーク遅延などの極端な状況でのみ発生するバグを検出することが非常に困難になります。

正確さ

分散システムの正確性のテストについて説明する前に、まず「正確性」の意味を定義しましょう。単純なシステムであっても、システムが期待どおりであることを完全に保証するのは非常に複雑です。

Put(key, value) と Get(key) の 2 つの操作をサポートする、etcd などの単純なキー値システムを考えてみましょう。まず、順次実行する場合の動作を考慮する必要があります。

シーケンシャル仕様

通常、キー値ストアの場合、順次操作での動作は直感的に理解できます。Get 操作が Put 操作の後に来ると、Put 操作の結果が取得されます。たとえば、Put("x", "y") の場合、後続の Get("x") は "y" を取得しますが、"z" を取得する場合はこれは誤りです。

Python を使用して、単純なキー値ストアを定義します。

上記のコードは比較的単純ですが、初期状態が何であるか、操作の結果によって内部状態がどのように変化するか、操作からキー値ストアから返される結果が何であるかなど、十分な情報が含まれています。ここで、Get() は存在しないキーに対して空の文字列を返すことに注意する必要があります。

線形化可能性

次に、同時実行時にキー値ストアがどのように動作するかを考えてみましょう。順序の指定は、同時操作時に何が起こるかを指示するものではないことに注意してください。たとえば、順序の仕様では、次のシナリオでキー値ストアが実行できる操作は指定されません。

Get("x") 操作によってどのような結果が返されるかはすぐにはわかりません。直感的に言えば、Get("x") は Put("x", "y") および Put("x", "z") と一緒に実行されるため、値、または "" を返す可能性があります。後で別の Get("x") 操作が実行されると、これが最後に書き込まれた値であり、その時点で他の同時書き込みがないため、確実に "z" が返されると言えます。

順次仕様に基づく並行操作の場合、一貫性モデル、つまり線形一貫性を使用してその正確性を説明します。線形化可能なシステムでは、呼び出しと戻りの間で、あらゆる操作をアトミックかつ瞬時に実行できます。線形一貫性に加えて、他の一貫性モデルもいくつかありますが、ほとんどの分散システムは線形一貫性操作を提供します。線形一貫性は強力な一貫性モデルであり、線形一貫性システムに基づいて他のシステムを構築するのは簡単です。キー値ストアでの操作に関する次の過去の例を考えてみましょう。

この歴史は直線的なものです。下の画像の青い領域に、実際に直線性が一貫しているポイントをマークしました。この順次履歴 Put("x", "0"), Get("x") -> "0", Put("x", "1"), Get("x") -> "1" は、順次仕様の正しい履歴です。

それに応じて、次の履歴は線形に一貫していません。

この履歴は、順次仕様に関して線形化できません。つまり、この履歴の操作内で線形化可能なポイントを指定することはできません。クライアント 1、2、3 の値はプロットできますが、クライアント 4 の値は明らかに古い値であるためプロットできません。同様に、クライアント 1、2、4 を描画すると、クライアント 2 の操作は 4 の操作の後に確実に開始されますが、クライアント 3 を処理することはできず、合法的に "" または "0" を返すことしかできません。

テスト

正確性の定義があれば、分散システムをテストする方法を検討できます。通常の方法は、マシンのクラッシュ、ネットワークの分離など、正しい操作にランダムなエラーを継続的に挿入することです。ネットワーク全体をシミュレートして、長期的なネットワーク遅延などを実行することもできます。テストはランダムに行われるため、システムの実装が正しいことを確認するには、テストを何度も実行する必要があります。

専門的なテスト

実際に正しく動作しているかどうかをどのようにテストするのでしょうか?最も単純なソフトウェアでは、assert(expected_output == f(input)) などの入出力テストを使用できます。分散システムでも同様のアプローチを使用できます。たとえば、キー値ストアの場合、複数のクライアントが操作の実行を開始すると、次のテストを実行できます。

テストが失敗した場合、システムは間違いなく線形化できません。もちろん、線形化できないシステムでもテストに合格する可能性があるため、このテストは完全ではありません。

線形化可能性

より良いアプローチは、同時クライアントで完全にランダムな操作を実行することです。たとえば、kvstore.put(rand(), rand()) および kvstore.get(rand()) の呼び出しをループすると、少数のキーのみを使用することで衝突の可能性が高くなる可能性があります。しかし、この場合、正しい操作とは何であるかをどのように定義するのでしょうか?上記の簡単なテストでは、各クライアントが独立したキーで動作するため、出力結果を非常に明確に知ることができます。

しかし、クライアントが同じキーセットを同時に操作すると、状況は複雑になります。単一の答えがないため、各操作の戻り値を予測することはできません。しかし、別のアプローチを使用することもできます。つまり、操作履歴全体を記録し、この操作履歴が線形に一貫していることを検証することができます。

線形化可能性の検証

線形化可能性検証ツールは、順次仕様と並行操作の履歴を受け取り、履歴が仕様に基づいて線形化可能かどうかを確認するための決定手順を実行します。

NP完全

残念ながら、線形化可能性の検証は NP 完全です。証明は非常に簡単です。線形化可能性は NP 困難であることを示すことができ、NP 困難な問題は線形化可能性に還元できることも示すことができます。明らかに、線形化可能性の検証は NP 問題です。たとえば、すべての操作の線形化可能性は、関連する順序仕様に従って多項式時間で検証できます。

線形化可能性の検証が NP 困難であることを示すために、サブセット問題を線形化可能性の検証に簡略化することができます。サブセット問題では、負でない数の集合 S={s1,s2,…,sn} と目標結果 t が与えられ、合計が t に等しい S のサブセットが存在するかどうかを判断する必要があります。この問題は、次の線形化可能性の検証に簡略化できます。順次仕様を検討してください:

そして歴史:

サブセットの質問に対する答えが「はい」である場合にのみ、履歴は直線的になります。履歴が線形である場合、任意の Add(s_i) 操作に対して、Get() 操作の前に線形一貫性ポイントがあり、それがサブセット内の Si に対応し、その合計が t であると考えられます。このセット内に合計が t となるサブセットがある場合、Get 操作が発生する前にサブセット Si に対応する Add(s_i) 操作と、Get() 操作後の残りの操作を持つ線形化を構築できます。

追記：この章の意味は大体分かっていますが、もっと良い翻訳方法が見つからなかったので、そのまま訳しました。さらに詳しく知るために、後でその論文を読んでみましょう。

成し遂げる

線形化可能性の検証は NP 完全ですが、実際には小さな履歴でも十分に機能します。線形化可能性検証の実装は、実行可能な仕様を受け取り、履歴を追加し、検索空間を制限および縮小するためのいくつかのトリックを使用して、線形化可能性を構築するための検索を実行します。

Jepsen には一貫性検証ツール Knossos がありますが、残念ながら、一部の分散キー値ストアをテストする場合、Knossos はうまく機能しません。これは、少数の同時クライアントと数百のイベントの履歴にのみ適用できる可能性があります。ただし、一部のテストではクライアントの数が多くなり、より多くの履歴イベントが生成されます。 Knossos の問題に対処するために、著者らは Go で書かれたより高速な線形化可能性検証ツールである Procupine を開発しました。 Porcupine は、Go で記述された実装仕様を使用して、履歴が線形であることを検証します。実際のテストによると、Porcupine は Knossos よりも何倍も高速です。

効果

分散システムの線形化可能性をテストする場合、フォールト注入は効果的な方法です。

対照的に、著者は専用のテストを使用して Porcupine でキーバリューストアをテストする際に、両方のアプローチを使用しました。著者は、独自のキー値ストアを実装する際に、変更後の期限切れの読み取りなどのさまざまな設計エラーを導入し、これらのテストが失敗するかどうかを確認しました。専門的なテストでは多くのバグを検出できますが、より微妙なバグを検出することはできません。相対的に言えば、著者は線形化可能性テストでは検出できない正確性のバグをまだ発見していません。

1. 形式手法は分散システムの正確性を保証します。たとえば、UM PLSE 研究グループは最近、Coq 証明支援を使用して Raft コンセンサス プロトコルを検証しました。残念ながら、検証には専門知識が必要であり、実際のシステムを検証するのは大変な作業です。いつかは、検証が実際のシステムで使用できるようになるかもしれませんが、現時点では、検証よりもテストが主です。
2. 理論的には、すべての製品システムには正式な仕様があり、一部のシステムではすでに正式な仕様があります。たとえば、Raft には TLA+ で記述された正式な仕様があります。残念ながら、ほとんどのシステムではそうではありません。

[この記事は51CTOコラムニスト「PingCAP」によるオリジナル記事です。転載する場合は著者に連絡して許可を得てください。

この著者の他の記事を読むにはここをクリックしてください