← 分散システム 一覧

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：一貫性モデルの地図　|　関連：Raft・クォーラム（R+W>N）

要点（BLUF）

• 線形化可能性（linearizability）は最も強い一貫性。各操作が「呼び出しと応答の間のある一点で瞬間的に効く」かのように、実時刻に矛盾しない唯一の直列順が存在する。
• 逐次一貫性（sequential consistency）は「全プロセスが同一の順序で見る」が、その順序は実時刻に一致しなくてよい。線形化より弱い。
• 違いは「実時刻（リアルタイム順）を尊重するか」。線形化＝尊重する、逐次＝各プロセス内順序だけ守ればよい。線形化は合成可能（局所性）、逐次は合成不可。

問題設定 ── 「最新が見える」を厳密に定義する

「書いた直後に読めば最新が返る」を形式化したのが線形化可能性。複製があっても1台のように振る舞う（single-copy）こと、と言い換えられます。ロック・カウンタ・リーダー選出（Raft）など、直観的な正しさが要る所で必須です。

モデル ── 操作を1点に潰す

線形化可能性は、各操作（呼び出し〜応答の区間）を、その区間内のある瞬間に「効いた」とみなせること。その瞬間（線形化点）を並べた順序が、逐次仕様（1台のオブジェクトの挙動）に合致する必要があります。

sequenceDiagram
    participant A as クライアントA
    participant B as クライアントB
    A->>A: write(x=1) 完了
    Note over A,B: 実時刻でwriteが完了した後…
    B->>B: read(x) 開始・完了
    Note over B: 線形化可能なら必ず 1 を返す(古い0は不可)

実時刻で「write が完了した後」に始まった read は、必ずその write 以降を見る。これが線形化の核心です。

違法な履歴の例 ── 線形化を破る読み

• A が x=1 を書き、応答を受け取った（write完了）。
• その後にB が read(x) して 0（古い値）を得た。

これは線形化違反。なぜなら「write完了 → read開始」という実時刻順があるのに、read が write 前の値を返したから。唯一の直列順に並べられません。一方、逐次一貫性なら合法になりえます（全プロセスが「read→write」という同一順序で見ていると解釈でき、実時刻は不問だから）。

線形化 vs 逐次 ── 決定的な違い

**合成可能性（局所性）**が線形化の強力な性質：個々のオブジェクトが線形化可能なら、それらを組み合わせたシステム全体も自動的に線形化可能。逐次一貫性にはこの性質が無く、部分が逐次でも全体は逐次にならない。

正しさの観点 ── なぜ強一貫はコストが高いか

線形化を保つには、読み書きのたびに「自分が最新を見ている」ことを確認する必要があり、複製間の**調整（合意・クォーラム）**が要る。CAP（CAP定理）では、線形化＝強いCで、分断時に可用性を諦める側（CP）。クォーラム（クォーラム（R+W>N））の R+W>N は、線形化に近い読みを得るための重なり条件です。

なぜ分散だと難しいか（直観）

1台のメモリは無料で線形化可能（書いたら次に読めば最新）。複製では「書き込みが全コピーに行き渡る前の読み」を禁じるために、毎回コピー間で足並みを揃える＝遅延と可用性低下を払う。強一貫は無料ではない、が分散の根本制約です。

⚠️ よくある誤解・落とし穴

• 「線形化可能＝直列化可能」→ 別物。線形化は単一オブジェクトの実時刻順、直列化は複数オブジェクトのトランザクション順。両立が strict serializable。
• 「逐次一貫性は線形化とほぼ同じ」→ 実時刻を尊重しないので、書いた直後に古い値が見えうる。体感は大きく違う。
• 「強一貫なら速い（最新だから）」→ 逆。最新を保証するため調整コストが乗り遅い。
• 「読みは調整不要」→ 線形化では読みも最新確認が要る（古い複製を読めない）。

対応ラボ

なし（概念回）。線形化に近い読みを支える重なり条件は クォーラム（R+W>N） のラボで定量化します。

関連

• 強一貫を作る合意は Raft
• 分断時の取引は CAP定理
• 重なり条件は クォーラム（R+W>N）

← 第4章 一貫性モデル 目次