結果整合性 - Eventual Consistency と BASE 特性

結果整合性（Eventual Consistency）は、分散システムにおいて、更新が一時的に各ノードで異なる状態になっても、最終的には全ノードで同じ値に収束することを保証するモデルです。本記事では、ACID と BASE の違い、一貫性のスペクトラム、実装パターン、ユースケースを体系的に解説します。

概要

結果整合性とは

結果整合性は、Werner Vogels（Amazon CTO）が2008年に体系化した概念で、強い一貫性（Strong Consistency）を犠牲にして可用性と性能を得るトレードオフです。

sequenceDiagram
    participant C as Client
    participant N1 as Node 1
    participant N2 as Node 2
    participant N3 as Node 3

    C->>N1: Write(x=10)
    N1-->>C: OK
    Note over N1,N3: 非同期レプリケーション開始

    C->>N2: Read(x)
    N2-->>C: x=5 (古い値!)

    Note over N1,N3: レプリケーション完了

    C->>N2: Read(x)
    N2-->>C: x=10 (最新値)

ACID vs BASE

原則・定義

BASE 特性の詳細

Basically Available（基本的に利用可能）

システムは部分的な障害があっても応答を返す。一部のノードがダウンしても、他のノードが処理を継続します。

Soft state（柔軟な状態）

システムの状態は時間とともに変化する可能性があります。外部入力がなくても、レプリケーションにより状態が変わります。

Eventually consistent（結果整合性）

更新がすべてのレプリカに伝播すれば、最終的に全ノードが同じ値になります。

一貫性のスペクトラム

flowchart LR
    Linearizable["Linearizable<br/>(線形化可能)"]
    Sequential["Sequential<br/>(逐次一貫性)"]
    Causal["Causal<br/>(因果一貫性)"]
    ReadYourWrites["Read-Your-Writes<br/>(自分の書き込み読取)"]
    MonotonicReads["Monotonic Reads<br/>(単調読取)"]
    Eventual["Eventual<br/>(結果整合性)"]

    Linearizable --> Sequential --> Causal --> ReadYourWrites --> MonotonicReads --> Eventual

    style Linearizable fill:#fee
    style Eventual fill:#efe

一貫性レベルの定義

Read-Your-Writes（自分の書き込み読取）

ユーザーが書き込んだデータは、同じユーザーが読み取る際に必ず最新である。

await db.write("profile", { name: "Alice" });
const profile = await db.read("profile"); // 必ず { name: "Alice" }

Monotonic Reads（単調読取）

一度新しい値を読んだら、それ以降古い値に戻らない。

const v1 = await db.read("counter"); // 10
const v2 = await db.read("counter"); // 10 または 11 以上（9 には戻らない）

Monotonic Writes（単調書込）

同じクライアントの書き込みは、全ノードで同じ順序で適用される。

Causal Consistency（因果一貫性）

因果関係のある操作は、全ノードで同じ順序で見える。

構成要素

レプリケーション戦略

競合解決戦略

複数ノードが同時に同じキーを更新した場合、競合を解決する必要があります。

実装例

1. Read-Your-Writes の実装（セッション一貫性）

class SessionConsistentStore {
  private primaryDB: Database;
  private replicaDB: Database;
  private userWriteTimes = new Map<string, number>(); // userId -> timestamp

  async write(userId: string, key: string, value: any): Promise<void> {
    await this.primaryDB.write(key, value);
    this.userWriteTimes.set(userId, Date.now());
  }

  async read(userId: string, key: string): Promise<any> {
    const lastWriteTime = this.userWriteTimes.get(userId);

    // 最近書き込んだユーザーはプライマリから読む
    if (lastWriteTime && Date.now() - lastWriteTime < 5000) {
      return this.primaryDB.read(key);
    }

    // それ以外はレプリカから読む（負荷分散）
    return this.replicaDB.read(key);
  }
}

2. Monotonic Reads の実装（スティッキーセッション）

class MonotonicReadsRouter {
  private replicaAssignments = new Map<string, string>(); // userId -> replicaId

  selectReplica(userId: string, replicas: string[]): string {
    // 同じユーザーは常に同じレプリカに固定
    if (!this.replicaAssignments.has(userId)) {
      const replica = replicas[Math.floor(Math.random() * replicas.length)];
      this.replicaAssignments.set(userId, replica);
    }
    return this.replicaAssignments.get(userId)!;
  }
}

// 使用例
const router = new MonotonicReadsRouter();
const replicas = ["replica-1", "replica-2", "replica-3"];

const r1 = router.selectReplica("user-123", replicas); // replica-2
const r2 = router.selectReplica("user-123", replicas); // replica-2 (同じ)

3. Last-Write-Wins（LWW）の実装

interface VersionedValue {
  value: any;
  timestamp: number;
  nodeId: string; // タイムスタンプが同じ場合の tie-breaker
}

class LWWStore {
  private data = new Map<string, VersionedValue>();

  write(key: string, value: any, timestamp: number, nodeId: string): void {
    const existing = this.data.get(key);

    if (!existing || this.isNewer(timestamp, nodeId, existing)) {
      this.data.set(key, { value, timestamp, nodeId });
    }
  }

  private isNewer(ts: number, nodeId: string, existing: VersionedValue): boolean {
    if (ts > existing.timestamp) return true;
    if (ts < existing.timestamp) return false;
    // タイムスタンプが同じ場合は nodeId の辞書順で決定
    return nodeId > existing.nodeId;
  }

  read(key: string): any {
    return this.data.get(key)?.value;
  }
}

4. CRDTs（G-Counter）の実装

// Grow-only Counter（増加のみカウンター）
class GCounter {
  private counts = new Map<string, number>(); // nodeId -> count

  constructor(private readonly nodeId: string) {
    this.counts.set(nodeId, 0);
  }

  increment(): void {
    this.counts.set(this.nodeId, (this.counts.get(this.nodeId) ?? 0) + 1);
  }

  value(): number {
    return Array.from(this.counts.values()).reduce((sum, c) => sum + c, 0);
  }

  // 他ノードからのマージ（競合なし）
  merge(other: GCounter): void {
    for (const [nodeId, count] of other.counts) {
      const current = this.counts.get(nodeId) ?? 0;
      this.counts.set(nodeId, Math.max(current, count));
    }
  }
}

// 使用例（分散カウンター）
const counter1 = new GCounter("node-1");
const counter2 = new GCounter("node-2");

counter1.increment();
counter1.increment(); // node-1: 2

counter2.increment(); // node-2: 1

counter1.merge(counter2);
console.log(counter1.value()); // 3 (2+1)

メリット・デメリット

メリット

1. 高可用性: ノード障害時も他のノードが応答
2. 低レイテンシ: 非同期レプリケーションで書き込みが高速
3. スケーラビリティ: 読み取り負荷を複数レプリカに分散
4. 耐障害性: ネットワーク分断時も片方のクラスタが動作継続

デメリット

1. 古いデータ: 一時的に stale な値を返す
2. 複雑性: アプリケーション層で競合解決が必要
3. 推論困難: 「いつ一致するか」が不明確
4. デバッグ難: タイミング依存のバグが発生しやすい

ユースケース

結果整合性が適する場面

1. SNS のタイムライン

Twitter や Instagram のタイムラインは、数秒の遅延は許容されます。全ユーザーが同時に同じタイムラインを見る必要はありません。

2. ショッピングカート（Amazon Dynamo の元ネタ）

カートに商品を追加する操作は、短時間の重複や漏れより、「カートが使えない」状態を避けることが優先されます。

3. DNS（ドメインネームシステム）

DNS レコードの更新は世界中に伝播するまで数時間かかりますが、最終的に一致すれば問題ありません。

4. いいね数・閲覧数

YouTube の再生回数や Facebook のいいね数は、リアルタイムで完全に一致する必要はありません。

強い一貫性が必要な場面

• 銀行口座の残高
• 在庫管理（二重販売防止）
• チケット予約
• 分散ロック

落とし穴

1. 「最終的に」の定義が不明確

「最終的に一致する」が数秒なのか数時間なのか、仕様で明示しないとバグになります。SLA で「レプリケーション遅延 < 1秒（99パーセンタイル）」等を定義しましょう。

2. Read-Your-Writes の欠如

ユーザーが投稿した内容が自分に見えない（別レプリカから読んだため）と、バグと誤解されます。セッション一貫性が必須です。

3. 無限に増えるデータ構造（CRDTs）

CRDTs の Set や Map は削除が困難で、メモリが無限に増えます。Tombstone（削除マーカー）の GC が必要です。

4. 競合解決の誤実装

Last-Write-Wins はデータロスの可能性があります。Amazon のカートは「両方の追加を保持」で解決します。

5. ベクタークロックの肥大化

ベクタークロックは、ノード数が多いとメタデータが巨大化します。Dotted Version Vector 等の改良版を使いましょう。

比較表

一貫性レベルとレプリケーション戦略

主要 NoSQL の一貫性設定

ベストプラクティス

1. 一貫性レベルを明示: API ごとに必要な一貫性を決定
2. Read-Your-Writes を実装: セッション追跡またはプライマリ読み
3. Monotonic Reads を保証: スティッキーセッション
4. 競合解決戦略を文書化: LWW / Vector Clock / アプリ層
5. レプリケーション遅延を監視: Prometheus メトリクスで可視化
6. タイムアウト設定: 古いレプリカからの読取に上限を設ける
7. CRDTs は慎重に: 適用場面を限定
8. カオステスト: Jepsen で分断時の挙動を検証

まとめ

結果整合性は、分散システムにおいて可用性と性能を優先するための重要な設計選択です。

• BASE 特性: ACID の対極、高可用性志向
• 一貫性スペクトラム: Linearizable ↔ Eventual の間に多様なレベル
• 競合解決: LWW / Vector Clock / CRDTs / アプリ層
• 適用場面: SNS、カート、DNS、カウンター等
• 実装: Read-Your-Writes、Monotonic Reads を提供

全てのシステムが強い一貫性を必要とするわけではありません。要件に応じた一貫性レベルを選びましょう。

応用トピック

Dotted Version Vector（DVV）

従来のベクタークロックの改良版で、ノード数増加時のメタデータ肥大化を抑えます。Riak 2.0 以降で採用されています。

Hybrid Logical Clocks（HLC）

物理時刻と論理時刻を組み合わせ、因果関係と実時間の両方を追跡します。CockroachDB で使用されています。

Quorum-based Consistency

R + W > N（R: 読取ノード数、W: 書込ノード数、N: レプリカ総数）を満たすと、強い一貫性が得られます。

// Cassandra 風の Quorum 設定
const config = {
  replicationFactor: 3, // N=3
  writeConsistency: "QUORUM", // W=2
  readConsistency: "QUORUM", // R=2
};
// W + R = 4 > N=3 → 強い一貫性

Conflict-free Replicated Data Types（CRDTs）の種類

• G-Counter: 増加のみカウンター
• PN-Counter: 増減可能カウンター
• G-Set: 追加のみセット
• 2P-Set: 追加・削除可能セット
• LWW-Element-Set: Last-Write-Wins セット
• OR-Set: Observed-Remove セット

参考リソース

• Eventually Consistent - Werner Vogels (Amazon CTO)
• Dynamo: Amazon’s Highly Available Key-value Store (SOSP 2007)
• A Comprehensive Study of Convergent and Commutative Replicated Data Types (CRDTs)
• Consistency Models - Jepsen
• Designing Data-Intensive Applications - Chapter 5 & 9
• CAP Twelve Years Later: How the “Rules” Have Changed - Eric Brewer

関連記事

• CAP定理入門 - 一貫性・可用性・分断耐性のトレードオフと結果整合性の位置づけ
• データベースレプリケーション - 同期・非同期レプリケーションと一貫性レベルの関係