分散システムでは、いくつかの基本的な問題があります。効率的な分散トランザクション、1回だけのデータ処理、物理クロックの正確な同期です。 後者の問題を解決するために、異なるタイプの論理クロック が発明されました 。
それにもかかわらず、 ベクトルクロックには不快な特性があります。つまり、存在しないイベントと、実際に存在するイベントとの間に条件付きの関係が生じます。
ただし、より信頼性の高いもの-Kronosを考え出すことができます。 この記事では、因果関係アカウンティングアルゴリズムと、分散トランザクションでKey-Valueストレージを構築するためのそのアプリケーションについて説明します。
問題
すでに述べたように、論理クロックには多くの問題があります。
存在しない依存関係が発生するのは、論理クロックがイベントの完全な順序を導入するためです。つまり、任意の2つのイベントのいずれかが条件付きでより早く、条件付きでより遅いと言えます。 契約は条件付きです。なぜなら、特別な相対性理論によるものも含めて、時間内のイベント間の関係を正確に決定することは不可能だからです。
一方、ロジッククロックは、システム内のメッセージを介した相互接続のみを考慮します。 いくつかの2つのイベントが接続されているが、たとえばユーザーを介してシステムの外部にある場合（システムの一部でバスケットに商品を追加->注文の支払い）、論理クロックはこの関係を見逃す可能性があります。
論理クロックは外部からアクセスできません。また、いくつかの独立したコンポーネント（分散ファイルシステム、要求処理サービス、分析）を相互接続することも困難です。
解決策
Kronosによる2014年の記事：イベントオーダーサービスの設計と実装では 、ソリューションが提案されています。これは、イベントの因果関係を処理するスタンドアロンサービスです。
Kronos内の主な抽象化は、部分的な順序付けが導入されるイベントです。 原因と結果の関係は推移的です。つまり、たとえば、ファイルの作成がその変更に先行し、変更が削除に先行することがわかっている場合、作成は削除の前に発生したという論理的な結論を出すことができます。
最小限のAPIは、次の一連のメソッドで定義できます。
| 方法 | 結果 | 解説 |
|---|
create_event() | e | Kronosで新しいイベントを作成します |
query_order([(e_1, e_2), ...]) | [<-, concurrent, ->, ...] | クエリの各ペアに対して、因果関係の方向、またはイベントの同時性を返します |
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...]) | OK/FAIL | 要求のペアごとに、因果関係の方向を設定します |
acquire_ref(e) | OK | このイベントの参照カウンターを増やします。 |
release_ref(e) | OK | このイベントの参照カウントを減らします。 |
実装
システムは、イベントの関係をチェックする効果的な幅優先探索、障害発生時の安定性メカニズム、およびガベージコレクションを備えた、イベントの指向グラフに基づいていることは論理的です。
APIからわかるように、 assign_orderリクエストは、因果関係タイプ（ mustまたはprefer assign_order受け入れます。 厳密な不変条件に対応しているmust -たとえば、 _->_ 、 must関係と競合する場合はpreferが適用されない場合がmustます。 preferを使用する例としては、先に来たリクエストが先にラップされたほうが良いが、これは正確さに影響しない
効果的なBFS
私たちの場合、グラフは大きいかもしれませんが、検証リクエストが実行されるイベントは通常近いでしょう。 したがって、このような場合にはBFSをより速く実行する必要があります。
標準実装では、最長の場所は訪問した頂点の配列の初期化であり、これは常にグラフ内の頂点の数に等しい時間がかかります。 代わりに、ハッシュテーブルを使用するか、他のトリックを適用できます。
ガベージコレクション
表からわかるように、 acquire_refとrelease_ref 2つのメソッドがあります。
Kronos内では、イベントごとに参照カウンターが保存されます。 一部のサービスはイベントを処理するか、現在のイベントの後に発生する新しいイベントを追加する機能を予約している間、リンクを保存します。 この必要性がなくなると、サービスはrelease_ref呼び出します。
Kronosは、すべての条件が満たされるとイベントを削除します。
- リンクの数がゼロに達しました
- これに先行するすべてのイベントはすでにグラフから削除されています。
このアプローチは可能なクエリを制限しませんが、Kronos内のメモリを節約します。
用途
分散トランザクションでのキー値ストレージの例として、システムの使用を検討してください。
複数のサーバーがあり、各サーバーが一連のキーを担当しているとします。
各トランザクションは、Kronosのイベントに対応しています。 サーバーは、キーごとに、このキーが参加した最後のトランザクションの番号を保存する必要があります。 クライアントはイベントを作成し、このトランザクションによってキーが影響を受けるすべてのサーバーにその番号を送信します。 サーバーは、現在のトランザクション番号とこのキー用に保存された前のイベントとの間にKronosで依存関係を作成しようとしています。 依存関係を作成できない場合、トランザクションは失敗として認識されます（これまではデータとの対話がまだないことに注意してください）。
すべての依存関係の追加操作が正常に完了した場合-これは、トランザクションが実行され、実行できることを意味します。 サーバーはこれについてクライアントから学習し、トランザクションの一部を実行し始めます。
このようなトランザクションはACIDになることに注意してください。
- アトミック性 ：トランザクションはKronosでスケジュールされないか、すべてのノードで実行されるようにスケジュールされます。
- 一貫性 ：KVリポジトリで自動的に。
- 分離 ：2つのトランザクションがデータに従って交差する場合、それらはKronosの因果関係によって接続されます。つまり、一方が他方の前に実行されます。
- 耐久性 ：Kronosはドロップ耐性があり、ボールトの各レプリカも安定していると想定しているため、証明する唯一のことは、保留中のトランザクションのデータの永続性です。 確かに、クライアントによってトランザクションが成功とマークされているが、サーバー上でレコードがまだ完了していない場合、サーバーはトランザクションの完了部分も追跡するため、この事実を簡単に確立できます。
性能
このようなKVストレージを実装すると、本当に効果的です。 元の記事は、KVストレージの説明された実装がロックに基づくトランザクションより4倍速いというデータを引用しています。
さらに、MongoDBは分散トランザクションを使用しないにもかかわらず、MongoDBと比較して、Kronos上のシステムはわずか6％遅れています。
分析
ただし、クロノスの運用にはいくつかの欠点があります。
- まず、Kronosにアクセスするオーバーヘッドがあります。各リクエストには少なくとも1つの呼び出しが必要です。
- Kronosは単一障害点にもなります。この記事の著者は、イベントグラフを分割する方法を提供していません。
- システムに多くのメソッドを追加すると便利です。 たとえば、KVストレージを使用した例では、トランザクションのステータスについてサーバーに通知するコールバックがあると便利です-必要なすべての依存関係とともにグラフに正常に追加されました-または、逆に、トランザクションを完了できませんでした。
それにもかかわらず、記述されたシステムは、イベント間の因果関係の柔軟な制御を可能にし、必要な不変条件への予測可能なコンプライアンスを保証します。
おわりに
これについて、GoTo Schoolでは、分散システムの方向で生徒と生徒を指導しています。
また、 アルゴリズムとアプリケーション 、応用プログラミング、バイオインフォマティクス、 データ分析があります
10月27日〜11月4日に秋の学校 、または1月上旬にウィンタースクールに来てください。
そして、あなたがもはや学生でも生徒でもない場合は、 教えに来てください 。