プロンプトとユースケース
線形化可能性と順序一貫性の違いを説明し、両者の結果が異なる読み取り/書き込みの履歴を示した上で、分散システムにおける一貫性、レイテンシ、可用性のトレードオフについて説明してください。これはシステム設計、バックエンド、データ、インフラストラクチャの職種において有用な深掘り質問です。
これは単なる用語テストではありません。面接官は、最新値、実時間（リアルタイム）順序、クライアントごとの順序、レプリカの遅延を組み合わせた、検証可能な1つの履歴を求めています。
面接官が評価するポイント
- 線形化可能な操作が、呼び出し（invocation）と応答（response）の間のいずれかの時点で瞬間的に有効になるように見えると述べているか。
- 順序一貫性は各スレッドのプログラム順序を保持する1つのグローバルな順序を要求するものの、スレッド間の実時間順序は要求しないと述べているか。
- 単に一方が「より強い」と言うだけでなく、反例を用いてその違いを証明できるか。
- これらのモデルを、etcdなどのシステムにおける読み取りモードやコストと結び付けているか。
回答前の確認事項
議論の対象が単一オブジェクトなのかトランザクションなのか、クライアントが単一なのか複数なのか、そして呼び出し時間と応答時間が判明しているかを確認します。線形化可能性は通常、並行オブジェクトを対象とします。複数オブジェクトのトランザクションには、さらに原子性と分離性の保証が必要です。
30秒の回答
線形化可能性は、実時間を尊重するグローバルな順序を要求します。完了した書き込みは、その後に開始された読み取りに対して必ず可視でなければなりません。順序一貫性は各スレッドのプログラム順序のみを保持するため、異なるスレッドからの操作は並べ替えられる可能性があります。書き込み完了後の古い値の読み取り（stale read）は線形化可能性に違反します。しかし、呼び出し間隔が重複している場合、グローバル順序において読み取りを先に配置することで順序一貫性を満たすことができます。より強力なモデルにはより多くの調整が必要となり、レイテンシとネットワーク分断時の可用性が犠牲になります。
ステップごとの解説
操作履歴を記述する
すべての操作について、呼び出し時刻、応答時刻、スレッド、引数、および結果を記録します。線形化可能性では、各呼び出しと応答の間の1点を選択し、すべての操作が正当なシングルスレッド実行を形成し、かつ完了した操作がその実時間順序を保持するようにします。
順序一貫性のルール
順序一貫性は、各スレッドの操作がそれぞれのプログラム順序どおりに現れる1つのグローバルシーケンスを要求します。履歴に必須の実時間制約がない限り、実時間（ウォールクロック）の順序が存在する場合でも、異なるスレッドからの操作は並べ替えられることがあります。
反例のタイムライン
スレッドA：write(x=1) がリターンします。その後、スレッドBが read(x) を呼び出して0を取得します。同一オブジェクトに対して、この履歴は線形化できません。呼び出し間隔が重複している場合、システムはグローバルシーケンスにおいてBの読み取りをAの書き込みの前に配置することができ、実時間順序には違反するものの順序一貫性を満たすことが可能です。
~~~text Linearizable: A: write(1) ---- returns B: read() -> 1
Not linearizable: A: write(1) ---- returns B: read() -> 0
Sequentially consistent but not necessarily linearizable: A: write(1) ========= B: read() -> 0 ========= Global order may place B before A when the calls overlap. ~~~
結果整合性との対比
結果整合性は、書き込みが停止し十分な時間が経過した後に収束することを保証します。古い値の読み取りを許容し、read-your-writes（自分の書き込みの読み取り）や単調読み取り（monotonic reads）を自動的には提供しません。線形化可能性は、通常リーダーやクォーラムを経由して読み書きをルーティングすることにより、より強力な実時間セマンティクスを提供します。
模範解答
私は線形化可能性を「実時間における単一コピーの錯覚」と説明します。すべての操作は呼び出しと応答の間に線形化ポイントを持ち、すべての操作が正当な逐次履歴を形成し、完了した操作はその実時間順序を維持します。順序一貫性は各スレッドのプログラム順序を保持するグローバルな履歴のみを要求するため、スレッド間の実時間順序は失われる可能性があります。
Aが1を書き込んでリターンした後にBが読み取りを開始した場合、Bが0を返すのは線形化可能性違反です。呼び出し間隔が重複している場合、Bの読み取りがグローバル履歴上でAの書き込みより前に現れることができ、順序一貫性は依然として満たされます。ビジネスニーズに基づいてモデルを選択してください。ロック、リース、条件付き更新には多くの場合線形化可能性が必要です。検索インデックスや分析用レプリカでは、レイテンシの短縮や可用性の向上のために、より弱いセマンティクスを受け入れることができます。
よくある間違い
- 実時間順序を明示せずに、システムを「強一貫性（strongly consistent）」と呼ぶこと。
- 順序一貫性を、スレッドごとのプログラム順序ルールではなく、サーバー時間によるソートとして説明すること。
- read-your-writesや単調読み取りに言及せず、結果整合性は「最終的に最新の値を読み取る」とだけ言うこと。
- 読み取りが合意形成パスに参加しているかを確認せずに、クォーラムが自動的に線形化可能性を意味すると見なすこと。
- 単一オブジェクトの線形化可能性を、複数オブジェクトトランザクションの完全な分離性と同一視すること。
フォローアップ質問と回答
なぜ線形化可能性は通常コストが高くなるのか？
読み取り時に現在のリーダーまたはクォーラムからの確認が必要になる場合があり、クロスリージョンのラウンドトリップが発生するためです。ネットワーク分断時、システムは実時間順序に違反する結果を返すくらいならリクエストを拒否することがあります。
順序一貫性はどこが弱いのか？
スレッド間の実時間（ウォールクロック）順序を保持しません。各スレッドのプログラム順序を保持するグローバルシーケンスであればどれも正当になり得るため、「完了した書き込みがその後の読み取りに反映されなかった」という事象が隠れやすくなります。
etcdの読み取りモードとは？
etcdはデフォルトで線形化可能性を保証するとドキュメントに記載しています。serializable 読み取りはクォーラムに対して古いデータを返す可能性がありますが、そのリスクと引き換えに低レイテンシと高スループットを実現します。設定名を単独で挙げるのではなく、ビジネスリスクと結び付けてください。
線形化可能性はどのようにテストするか？
呼び出し時刻、応答時刻、スレッド、入力、結果を記録し、正当な線形化順序を探索します。遅延、プロセスのポーズ、リーダー交代を注入します。順次実行するだけのテストでは、重大な障害を検出できません。
結果整合性で十分なのはどのような場合か？
プロダクトとしてそのトレードオフを明示的に許容している場合、フィード、検索インデックス、レポートなどは有界な古さ（bounded staleness）を受け入れることができます。重要な書き込みには、依然としてread-your-writes、バージョン番号、または明示的な更新パスが必要になる場合があります。
回答をどのように締めくくるべきか？
タイムラインから始め、モデルの制約を述べ、ビジネス上の保証ならびにレイテンシと可用性のコストで締めくくります。これにより、単にCAP定理のスローガンを暗誦する以上の深い理解を示すことができます。