比較・疑問解決 · 基礎から応用へ

逐次一貫性と線形化可能性

各参加者の操作順を守る逐次一貫性と、操作の実時間の前後も守る線形化可能性を、レジスターの履歴で比較します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 共通するのは直列の説明を求めること
  2. 完了後に別の参加者が読む例
  3. 同じ参加者の順序は保つ
  4. オブジェクトを組み合わせると差がある
  5. 進捗と性能は別の評価軸にする
  6. 短い履歴から要求を明文化する
  7. この記事をロゲイアに質問する理解を確かめる

共通するのは直列の説明を求めること

逐次一貫性では、並行した操作の結果を、各参加者のプログラム内の順序を保つ一つの直列順で説明できることを求めます。線形化可能性でも仕様に合う直列の説明を考えますが、操作が呼出しから応答までの間に起きたように扱い、重ならない操作の実時間上の順序も守ります。どちらも「値がそのうち一致する」という説明だけでは足りません。一つの順序の中で、読取りが返した値と書込みの位置が整合するかを調べます。比較の対象はメモリや共有オブジェクトの操作であり、DB取引の原子的なまとまりとは別に定義する必要があります。

完了後に別の参加者が読む例

初期値0のレジスターに、Aが1を書いて応答を受け、その後Bが最初の読取りを開始したとします。他の書込みがなければ、線形化可能性の下ではBが0を返すことはできません。Aの完了がBの開始に先立つからです。一方、参加者ごとの順序以外に追加の制約がない逐次一貫性のモデルでは、BのreadをAのwriteより前へ置ける場合があります。Bが最初の操作であることがこの例の条件です。追加の通信や同期を含む履歴では制約が増えるため、いつでも自由に古い値を返してよい、という意味へ広げないようにします。

同じ参加者の順序は保つ

Aがwrite(1)を行い、その後同じAがreadを行う場合、ほかの書込みがなければ、逐次一貫性でもreadを最初のwriteより前に移動できません。A自身のプログラム順を保つ必要があるためです。この点を省くと、逐次一貫性を単に「古い値が返ってもよい弱い保存先」と誤解しやすくなります。複数の変数を含む例では、各参加者の操作列と読取り値を書き、許される全体の並びを考えます。CPUで速く実行された順、ログファイルへ行が書かれた順、仕様が要求する操作順は、同じ観測で得られるとは限りません。

オブジェクトを組み合わせると差がある

線形化可能性には、適切なオブジェクト単位で性質を確かめた結果を、全体へ組み合わせて考えられるという重要な特徴があります。逐次一貫性では、個々の変数について整合する説明があるだけで、複数の変数全体にも一つの整合する順序があるとは限りません。Aがxを書いてyを読み、Bがyを書いてxを読むような履歴では、変数ごとの説明と参加者の順序を両方合わせる必要があります。一方、個々の操作を線形化可能にしても、アプリが別々に行うread・計算・writeを一つの取引にするわけではありません。合成できる性質の範囲を正確に読むことが大切です。

進捗と性能は別の評価軸にする

どちらの順序条件も、すべての操作が一定時間内に完了することを直接保証しません。実装は、結果の順序を守るための通信や待機を必要とする場合があります。障害や分断のある環境では、どこで拒否し、どこで待ち、どこで古い読取りを許すのかを明確にします。低いレイテンシだけで保証を推測することも、強い保証の名前だけで遅いと決めつけることも適切ではありません。同じオブジェクトの仕様、同じ利用条件、同じ正しさの要件をそろえて測ります。ここでの履歴は保証の比較例で、特定実装の速さを示したものではありません。

短い履歴から要求を明文化する

検証用には、参加者、操作ID、引数、戻り値、呼出しと応答の関係を残します。二つの操作が重なったのか、一方の完了後に他方が始まったのかを区別できる情報が重要です。異なるマシンの時計をそのまま比較できないなら、どの通信や観測が前後関係の根拠になるかを決めます。必要なのが自分の直前の書込みの反映なのか、他者も含む完了済み操作の反映なのかによって、選ぶ保証も変わります。曖昧な「一貫している」ではなく、許したい読取りと許せない読取りを短い具体例で示すと、製品の仕様と照合できます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 17

学習コースから次を選ぶ