A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases(1979)
May 27, 2023データベースを同期するためのアルゴリズムmajority consensusを提案する。 アプリケーションは任意のデータベースに更新リクエストを送信でき、データベースは更新リクエストの処理について含意をとる。 データベースは、タイムスタンプのついたレコードの集合である。 タイムスタンプは、レコードの値の更新時刻をあらわす。
データベースの値を更新するとき、アプリーケーションは、更新に必要なレコードを取得し、計算した新しい値をデータベースに送り返す。 更新に必要なレコードは、base variablesとよばれる。 更新対象のレコードもbase variablesであり、アプリケーションは更新するためにはレコードを取得しなければならない。 アプリケーションは、新しい値を更新すると、更新後の値とbase variablesのタイムスタンプをデータベースに送る。 更新対象の値はupdate variablesとよばれる。 データベースは、含意アルゴリズムにより、リクエストの承認、棄却を決め、アプリケーションに結果を返す。 承認の合意が成立した場合は、データベースを更新する。
アプリケーションのリクエストを転送するためのデータベースのトポロジーは、ブロードキャストでもデイジーチェーン(数珠つなぎ)でもよいが、解説では後者を採用する。 未投票の送信先のデータベースが見つからない場合や、リクエストを送信する前にデータベースがクラッシュする場合、転送に失敗する。 そこで、メッセージの送信元のデータベースは永続化されており、また、投票から合意形成までの時間にタイムアウトを設定すると仮定する。
アプリケーションのリクエストを転送されたデータベースは、2つの矛盾したリクエストを受理しないように、リクエストの可決か棄却を投票によって決定する。 一方のリクエストのbase variablesと他方のupdate variablesに重複があるとき、2つのリクエストが矛盾するとみなす。 データベースは、受信したbase variableとデータベースにある対応するレコードのtimestampを比較する。 base variableが古ければ、リクエストの棄却に投票する。 base variableが,最新の状態であり、かつ、受理、棄却が決まっていない以前に投票したリクエストと矛盾しない場合、受理を投票する。 最新であるが、以前のより優先度の高いリクエストと矛盾する場合は、PASSを投じる。 それ以外の場合、一定時間投票を遅らせて再度投票のプロセスを実行する。
投票をすませたデータベースは、投票結果が確定したかを確認する。 過半数のデータベースが可決したときに、リクエストが可決される。 任意の2つの過半数の積集合は空集合にならない。 したがって、過半数を基準にすることで、任意の2つのリクエストに可決したデータベースを保証できる。
もし、投票が可決し、majority consensusが存在すれば、データベースはリクエストを受理し、すべてのデータベースとアプリケーションに受理したことを通知する。 棄却に投票していれば、棄却したことを通知する。 PASSに投票し、合意形成が成立しえないと分かれば、棄却したことを通知する。 それ以外の場合、リクエストや未投票の過去のリクエストへの投票を転送する。 リクエストが受理されていれば、データベースにリクエストを反映し、棄却されたら、リクエストによって遅延されていたリクエストの投票を再開する。
雑記
送信したメッセージが届かないこと、データベースを追加、削除することは想定されていない。 過半数が承認したリクエストを棄却したデータベースがupdate variablesで自分のローカルのデータを上書きしてよい理由がわからない。