問題タブ [consensus]

R + W > N の状況があるとします。ここで、R は読み取りクォーラム レベル、W は書き込みクォーラム レベル、N はレプリケーション ファクターです。さらに、R = W = N/2 + 1 と仮定できます。

キーの更新操作が進行中のシナリオを想像してみましょう。Cassandra が更新をタイムスタンプ t の単一のレプリカにコミットしたとします。また、他のレプリカのキーが < t のタイム スタンプで格納されていると仮定します。更新の進行中にオブジェクトの読み取り要求が発生した場合、読み取りクォーラムには、タイム スタンプ t のキーを含む更新が発生した単一のレプリカが含まれ、まだコミットされていない値が返される可能性があります。 (可能な将来の値 - 更新が実際に失敗する可能性があるため、「可能」と言います) t > 読み取りクォーラム内の他のレプリカからのタイム スタンプ。

問題は、R + W > N 構成が強い一貫性を保証するはずではないかということです。さらに、この問題はどのように解決されますか?

ペーパーCORFU: A Distributed Shared Logは、削除メッセージを検証しない疑似コードでプロトコルを提示します。論文を引用するには：

これは、まだ書き込まれていないページを削除できることを意味します。また、クライアントが古いクラスター構成を使用してページを削除できることも意味します。これは、論文で提示されているプロトコルが削除を失う可能性があることを意味しませんか?

論文によると、CORFU はメモリ空間の最適化として、削除されたアドレスの最高水準点を維持します。削除を失う可能性がある場合、そのハイ ウォーターマークは移動せず、メモリが出血します。

ステート マシンのレプリケーションに CORFU を使用すると、ステート マシンのスナップショットを作成し、スナップショットまでのログを削除できます。削除を失う可能性がある場合、ログは実際には永遠に大きくなります。

検証なしで単に削除を適用するのではなく、実装で単純に削除を冪等にするだけでなく、次のように検証します。

それとも、何らかの形で安全性やパフォーマンスを損なうでしょうか?