# 線形化可能性 ## 定義 線形化可能性(linearizability)とは、レプリケートされたシステムが、データのコピーが実際には複数あるにもかかわらず、あたかもコピーが1つしかなく、そのすべての操作がアトミックに実行されるかのように振る舞う一貫性モデルである。atomic consistency・strong consistency・immediate consistency・外部一貫性(external consistency)とも呼ばれる。線形化可能なシステムでは、ある書き込みが完了した時点以降にすべてのクライアントが読み取りを行うと、必ずその書き込みで設定された値(かそれ以降の値)を読み取れる。これは recency guarantee(直近性保証)と呼ばれる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Linearizability") 形式的には、複数クライアントの読み書き操作を「開始時刻から応答時刻までの区間」として捉え、各操作がその区間内のある一点で瞬間的に実行されたとみなせるように順序線を引けること、かつその順序線が常に時間方向に前進すること(逆行しないこと)が要件になる。ある読み取りが新しい値を返した後は、それより後に開始する別の読み取りは古い値に戻ってはならない。 ## 何が線形化可能性を要求するか - **ロックとリーダー選出**: リースを2ノードが同時に獲得することがあってはならない。ZooKeeper・etcd のようなコーディネーションサービスは、コンセンサスアルゴリズムで線形化可能な操作を実現し、この用途を支える。 - **一意性制約**: ユーザー名・ファイルパス・口座残高・在庫数のような「全ノードが合意する単一の最新値」を要求する制約は線形化可能性を必要とする。外部キー制約など緩く扱える制約は線形化可能性なしでも実装できる。 - **クロスチャネルタイミング依存**: ストレージとメッセージキューのように独立した2つの通信チャネルがある場合、ストレージ側が線形化可能でなければ、後発チャネルの通知が先に届いて古いデータを処理してしまう競合状態が起こりうる。 (Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Relying on Linearizability") ## レプリケーション方式ごとの線形化可能性 | レプリケーション方式 | 線形化可能性 | |---|---| | 単一リーダー(リーダーのみ読み書き) | 概ね可能。ただしリーダーの誤認(delusional leader)や非同期レプリケーションでのフェイルオーバー時のデータ損失に注意 | | コンセンサスアルゴリズム | 概ね可能。ただしリーダー確認なしの読み取りは陳腐化しうる | | マルチリーダー | 不可能(複数ノードで並行に書き込みが処理され非同期に伝播するため) | | リーダーレス(Dynamo型) | クォーラム条件 w + r > n を満たしても保証されない。線形化可能にするには同期的な read repair と、書き込み前の quorum read によるタイムスタンプ確認が必要(Riak は前者を省略、Cassandra は時刻ベースのタイムスタンプ採用のため後者を満たせない) | (Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Implementing Linearizable Systems") ## 共有メモリレジスタとしての一貫性の段階 *詳説 データベース*11章は、線形化可能性を単一レジスタの並行アクセス挙動として捉え直し、並行操作時のレジスタの挙動によって3種類のレジスタを区別する。**セーフレジスタ**は並行書き込み操作時のレジスタの範囲に含まれる任意の値を返しうる(バイナリ値なら書き込みと並行する読み取り時に2値の間でちらつきうる)。**レギュラーレジスタ**は、最後に完了した書き込みの値か、現在の読み取りとオーバーラップしている書き込みの値のどちらかだけを返す(プライマリで書き込みを受け入れ読み取りワーカーへレプリケートするデータベースで生じる挙動)。**アトミックレジスタ**は線形化可能性そのものを保証し、すべての書き込みにある単一の瞬間があり、その前後で古い値・新しい値が明確に分かれる。この3分類は、線形化可能性を「アトミックレジスタとして振る舞うこと」という具体的な実装可能性の言葉で定義し直したものである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.3) **線形化ポイント**は、操作の効果が可視化される単一の瞬間を指す用語であり、DDIA が定義する「開始時刻から応答時刻までの区間内のある一点で瞬間的に実行される」という要件を、ロック・アトミックな読み取り/書き込み・read-modify-write プリミティブで実装する際の焦点として明示化する。線形化ポイントを過ぎると、すべてのプロセスはその操作で書き込んだ値かそれ以降の値を見なければならず、可視化された値は次の値が見えるまで安定した状態を保つ必要がある(レジスタは最新の2状態の間で変化してはならない)。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.5.2.1) ## コスト Attiya and Welch の証明によれば、線形化可能な読み書きの応答時間はネットワーク遅延の不確実性に本質的に比例する。これより高速な線形化可能ストレージのアルゴリズムは存在しない。マルチコア CPU の共有メモリでさえ、キャッシュ・ストアバッファによる非同期更新のため線形化可能ではなく、性能のために意図的に一貫性を犠牲にしている。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "The Cost of Linearizability") CAP 定理は、この一貫性(C)と可用性(A)のトレードオフをネットワーク分断(P)発生時に限定して定式化したものであり、線形化可能性という単一の一貫性モデルとネットワーク分断という単一の障害種別だけを対象にした狭い定理として位置づけられる。PACELC 原則はこれを拡張し、分断がなくても低レイテンシと一貫性の間にトレードオフがあることを指摘する。 ## 横断的知見 - **DDIA の線形化可能性の定義と、Spanner/CockroachDB 系の外部一貫性・厳密直列化可能性の定義は同一線上にある**: [[外部一貫性]] ページは「T1 のコミットが T2 の開始より実時間で先行するなら T1 のコミットタイムスタンプが T2 より小さい」という Spanner の形式的定義を扱うが、これは本章が言う「操作が瞬間的に実行される順序線が時間方向に逆行しない」という線形化可能性の一般定義を、複数キーにまたがるトランザクションに拡張したものである(外部一貫性はトランザクション版、線形化可能性は単一レジスタ版)。CockroachDB が「単一キー線形化可能性のみ」を HLC + Read Refresh で保証し、真の外部一貫性(厳密直列化可能性)には commit wait 相当のコストが避けられないと報告している点は、本章が示す Attiya and Welch の不可能性結果(線形化可能性はネットワーク遅延の不確実性に比例したコストを要する)の具体例になっている。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "The Cost of Linearizability", [[外部一貫性]] の Source: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] §4.2〜4.3) - **Dynamo-style クォーラム(w + r > n)の限界は、結果整合性と線形化可能性の間の「見せかけの強い一貫性」という誤解に対する明示的な反証になっている**: [[結果整合性]] ページは Dynamo・Cassandra が R + W > N のクォーラムで整合性を調整可能にすると述べるが、本章は同じ w + r > n の条件を満たしていても、書き込みと並行するクォーラム読み取りが古い値を返しうる非線形化可能な実行例(図10-6)を具体的に示す。これは「クォーラムを満たせば強い一貫性が得られる」という直感的な誤解を、線形化可能性の厳密な定義に照らして訂正するものであり、[[クォーラムベースレプリケーション]] ページが指摘する「w+r>nでも救えない実運用上の落とし穴」の一種として位置づけられる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Implementing Linearizable Systems", [[結果整合性]] の Source: [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]) - **DDIA の「線形化可能性」と 詳説 データベースの「一貫性モデルの階層」は、同じ強弱の順序を異なる語彙で表現する**: DDIA は線形化可能性を単独の最強モデルとして定義し、逐次一貫性・因果一貫性などとの相対関係には深入りしないのに対し、詳説 データベース11章は線形化可能性(実時間順序を保証)→逐次一貫性(グローバル全順序のみ)→因果一貫性(因果関係のある操作のみ順序付け)→PRAM/FIFO 一貫性(同一発行元の操作順序のみ)という明示的な階層を「まとめ」節で提示する。両者を突き合わせると、DDIA が単発で論じる線形化可能性は、詳説 データベースが示す4段階の一貫性モデル階層のうち最上位の1点に位置づけられることが分かり、DDIA 単独では見えなかった「線形化可能性より緩いが結果整合性より強い」複数の中間段階(逐次一貫性・因果一貫性・PRAM)の存在が明確になる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Linearizability", [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.11 まとめ) - **CAP 定理の「一貫性」は線形化可能性と同一視されるが、ACID の一貫性とは異なる**: 詳説 データベース11章は「CAP における一貫性は ACID における一貫性の定義とかなり異なる」と明示し、CAP の一貫性を「操作がアトミックであり、データを一貫性のない状態のままで放置しない」ことと定義する。これは DDIA が線形化可能性を「複数コピーが1つしかないかのように振る舞う」recency guarantee として定義するのと同じ焦点(単一操作の実時間順序)を持ち、両ソースは独立に「一貫性」という多義語を CAP/線形化可能性の文脈で明確化する必要性を確認している。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.2.1, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Linearizability") - **合意アルゴリズム自身が、性能最適化のために自ら線形化可能性を破りうることを明示的に自覚している**: 本ページはこれまでレプリケーション方式(単一リーダー・コンセンサス・マルチリーダー・リーダーレス)ごとに線形化可能性の可否を整理してきたが、いずれも「レプリケーション方式の選択」という設計時の判断として線形化可能性を論じている。[[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.4 は、コンセンサスアルゴリズム(Multi-Paxos)を採用してもなお、運用中の最適化(リーダーリースによるクォーラム読み取りの省略)が線形化可能性を損ないうることを示す: 「ノード間のクロックのドリフト(ズレ)が大きくなりすぎて、リースがまだ有効であるとリーダーが思っているのに、他のノードはリースの有効期間がきれたと思っている場合、線形化可能性を保証できない」。これは「コンセンサスアルゴリズムなら概ね線形化可能」という本ページの表の記載を、リース最適化という具体的な失敗モードで補強するものであり、線形化可能性の破れが方式選択の誤りだけでなく、正しい方式の内部でも時刻同期への依存という形で忍び込みうることを示す。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.4) ## 未解決の問い - Attiya and Welch の不可能性結果は理論的な下限を示すが、実運用でのネットワーク遅延不確実性が縮小し続ける(データセンター内 RDMA・専用インターコネクト等)場合、線形化可能性のコストは実質的にどこまで無視できる水準に近づくか。 - CAS 操作がコンセンサス数∞(任意ノード数で解ける)であるのに対し、fetch-and-add はコンセンサス数2に留まるという非対称性は、ID 生成器のような fetch-and-add ベースの設計にどのような実用上の制約を課すか。 - 詳説 データベースが示すセーフ/レギュラー/アトミックのレジスタ分類は、DDIA が定義する線形化可能性のコスト論(Attiya and Welch の不可能性結果)とどのように対応するか。レギュラーレジスタ(プライマリ書き込み・ワーカー読み取り)は、単一リーダーレプリケーションの非同期フォロワーが持つ結果整合性とどこまで同一視できるか。 ## 関連 - ソース: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] - 概念: [[外部一貫性]] / [[分散コンセンサス]] / [[結果整合性]] / [[クォーラムベースレプリケーション]] / [[TrueTime]] / [[ID生成器と論理クロック]] / [[直列化可能性]] / [[CAP定理]] ## 出典 - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] - [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.3 共有メモリ, §11.5.2 線形化可能性, §11.5.2.1 線形化ポイント - [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.4(Multi-Paxosのリーダーリースとクロックドリフトによる線形化可能性の喪失)