Що таке теорема CAP?

Архітектура~6 хв читання

Теорема CAP стверджує, що розподілена система, яка реплікує дані між кількома вузлами, не може одночасно гарантувати Consistency (узгодженість), Availability (доступність) і Partition tolerance (стійкість до розбиттів) під час мережевого розбиття.

Теорія

TL;DR

Компроміс спрацьовує тільки під час розбиття мережі; у нормальному режимі цілься в усі три властивості
Partition tolerance в реальній мережі не є опцією: береш як константу і обираєш між CP і AP
CP (ZooKeeper, CockroachDB): блокує або відхиляє записи під час розбиття, зберігає узгодженість
AP (Cassandra, DynamoDB): завжди відповідає, може повертати застарілі локальні дані
CA існує тільки як одновузловий міф, не як реальна архітектура

Швидкий приклад

javascript

class CAPDemo {
  constructor() {
    this.nodes = [{ balance: 100 }, { balance: 100 }];
  }

  // CP: відмовляє від запису, якщо репліки розійшлись
  cpWrite(amount) {
    if (this.nodes[0].balance !== this.nodes[1].balance) {
      throw new Error('Partition: відмовляю від запису для збереження узгодженості');
    }
    this.nodes.forEach(n => (n.balance += amount));
    return this.nodes[0].balance;
  }

  // AP: пише до локального вузла, відповідає завжди
  apWrite(amount, nodeId) {
    this.nodes[nodeId].balance += amount;
    return this.nodes[nodeId].balance;
  }
}

const demo = new CAPDemo();
console.log(demo.cpWrite(50));    // 150 - обидва вузли оновлено
demo.nodes[1].balance = 200;      // імітуємо розбиття: вузол 1 відхилився
console.log(demo.apWrite(10, 0)); // 160 - вузол 0 відповідає, але не узгоджений з вузлом 1

CP відмовляє від запису при розбіжності реплік. AP пише локально і відповідає швидко. Обидва варіанти правильні для своїх сценаріїв.

CP проти AP: реальний компроміс

Мережеві розбиття не є теоретичним edge case. AWS документує збої, свіч дропає пакети, канали між датацентрами рвуться. Partition tolerance береш як даність і вибираєш, від чого відмовитись.

CP-системи блокують або відхиляють операції під час розбиття, щоб не повернути неузгоджені дані. ZooKeeper перестає приймати записи без кворуму. CockroachDB на Raft: немає більшості - немає коміту. Саме це потрібно розподіленим блокуванням і фінансовим регістрам.

AP-системи продовжують відповідати. Cassandra приймає запис на локальний вузол і розповсюджує його асинхронно. Netflix використовує Cassandra для більш ніж 100 PB даних про події користувачів. Застаріла рекомендація - дрібна UX-проблема. Таймаут сервісу - помилка, яку бачить юзер.

Коли що використовувати

Банківські перекази, баланс рахунку: CP. Відхилений запис краще за подвійне списання.
Leader election, розподілені блокування: CP. Kafka використовує ZooKeeper, Kubernetes - etcd, обидва на Raft.
Стрічки новин, повідомлення, таймлайни: AP. Пост із запізненням на дві секунди прийнятний.
Аналітика, трекінг подій: AP. Приблизна свіжість краща за простій.
Кошик покупця з вирішенням конфліктів: AP з CRDTs або last-write-wins. Саме так Amazon спроектував оригінальний Dynamo.

Порівняльна таблиця

	CP	AP	CA
Узгодженість	Так, чекає кворуму	Eventual, можливі застарілі читання	Так, але без partition tolerance
Доступність	Відмовляє під час розбиття	Завжди відповідає локально	Так, для одного вузла
Partition tolerance	Так	Так	Ні
Сценарій	Блокування, фінанси, конфіги	Стрічки, кеші, великі обсяги подій	Одновузлові dev/test середовища
Приклади	ZooKeeper, CockroachDB, etcd	Cassandra, DynamoDB (за замовчуванням)	PostgreSQL без реплікації

Як це працює всередині

CP-протоколи (Raft, Paxos) вимагають більшість кворуму перед будь-яким комітом. Лідер надсилає пропозицію фолловерам, чекає підтвердження від більшості, тоді комітить. Якщо розбиття ізолює вузли нижче порогу більшості - ці вузли зупиняються. Математика: N=3 вузли, кворум=2. Один вузол ізольований - два ще можуть комітити. Два ізольовані - система зупиняється.

AP-протоколи використовують gossip-реплікацію. Кожен вузол приймає записи локально і поширює стан на сусідів асинхронно. Vector clocks або timestamps відстежують версії і допомагають вирішити конфлікти після відновлення. У Cassandra це можна налаштувати: CONSISTENCY QUORUM з RF=3, R=2, W=2 дає W+R > N - майже CP-гарантія з AP-гнучкістю для менш критичних читань.

Я бачив, як команди розгортають Cassandra як "стандартна масштабована БД" без усвідомленого вибору CAP, а потім витрачають спринти на відлагодження застарілих даних у платіжних флоу. Вибрати AP не помилка. Вибрати AP випадково - помилка.

Типові помилки

Помилка: CAP обмежує систему завжди

Теорема CAP активується тільки під час розбиття мережі. Поза цим сценарієм система може підтримувати і узгодженість, і доступність одночасно. Не треба жертвувати узгодженістю на кожному запиті.

javascript

// Неправильно: завжди чекати підтвердження від всіх реплік
await Promise.all(nodes.map(n => n.write(value))); // один повільний вузол блокує все

// Краще: кворумний запис - більшість достатня
const quorum = Math.ceil(nodes.length / 2) + 1;
await Promise.all(nodes.slice(0, quorum).map(n => n.write(value)));

Помилка: CA як реальна опція

CA - теоретична конструкція. MongoDB роками позиціонувався як CA, але розбиття призводили до реальних збоїв доступності. Усі виробничі розподілені бази даних є CP або AP.

Помилка: AP не вимагає обробки конфліктів

AP не означає "пишемо де завгодно, читаємо де завгодно". Два вузли, що приймають конфліктні записи під час розбиття, призводять до розбіжного стану. Без last-write-wins, CRDTs або логіки злиття на рівні застосунку отримаєш втрату даних або помилки подвійного списання у фінтеху.

Помилка: Узгодженість CAP = ACID Consistency

C в CAP - це лінеаризовність (linearizability): читання завжди повертає результат останнього запису, ніби система є одним вузлом. C в ACID означає, що обмеження транзакції залишаються дійсними після коміту. Ці властивості різні. Система може бути CAP-consistent, але не ACID-serializable.

Помилка: Масштабування реплік без вибору CP/AP

Більше реплік без усвідомленого вибору означає, що система працює з налаштуваннями бази даних за замовчуванням. Cassandra - AP за замовчуванням. MongoDB replica sets - CP для primary-читань. Визнач свій сценарій до масштабування.

Реальне застосування

Cassandra (AP): Netflix, 100+ PB подій користувачів. CONSISTENCY QUORUM для чутливих читань, ONE для масових записів
ZooKeeper (CP): координація брокерів Kafka, розподілене блокування
CockroachDB (CP): serializable ізоляція для банківських клієнтів
DynamoDB (AP за замовчуванням): e-commerce AWS. ConsistentRead=true переходить до CP-режиму за вищої затримки
etcd (CP): стан кластера Kubernetes, Raft-кворум
MongoDB replica sets (CP primary): Uber для історії поїздок; читання з secondary дає більшу пропускну здатність за рахунок свіжості даних

Питання для співбесіди

Q: Як PACELC розширює теорему CAP?
A: PACELC додає компроміс затримки для випадку без розбиття (E = else). Навіть у здоровій мережі є вибір між низькою затримкою (L) і сильною узгодженістю (C). DynamoDB оптимізує L при нормальній роботі, а не тільки під час збоїв.

Q: Яка різниця між linearizability і eventual consistency?
A: Linearizability (C в CAP) означає, що читання завжди повертає результат останнього запису, глобально впорядкованого. Eventual consistency означає, що репліки в кінцевому рахунку зійдуться, але під час поширення читання може повернути застарілі дані. Відстань між ними і є вибором AP/CP.

Q: Як W, R і N пов'язані з CAP у кворумних системах?
A: При N реплік, якщо W+R > N, будь-яке читання перетинається з будь-яким записом - це гарантує лінеаризовані читання. Cassandra з RF=3, W=2, R=2: W+R=4 > N=3. W=1, R=1 - чистий AP: швидко, але з ризиком застарілих читань.

Q: Як спроектувати систему з 99.999% доступності і узгодженими переказами коштів?
A: Базовий шар - AP з асинхронною міжрегіональною реплікацією для доступності. Тільки для коду переказів застосовуєш синхронний кворумний запис (CP-підмножина). Вся система залишається доступною, CP виконується тільки там, де втрата даних недопустима. Calvin protocol і залежні транзакції з prepare-commit - це виробничі патерни для цього завдання.

Q: Як тестувати CAP-властивості в CI?
A: Jepsen - стандартний інструмент. Він вводить мережеві розбиття і перевіряє узгодженість фінального стану. Знайшов реальні баги в etcd, Riak, CockroachDB. Для легших інтеграційних тестів - Toxiproxy імітує partition і затримку між сервісами.

Приклади

Базовий: CP проти AP під час розбиття

javascript

class ReplicaSet {
  constructor() {
    this.nodes = [
      { id: 0, value: 0, version: 0 },
      { id: 1, value: 0, version: 0 },
      { id: 2, value: 0, version: 0 },
    ];
    this.partition = false;
  }

  cpWrite(value) {
    if (this.partition) {
      throw new Error('CP: розбиття активне, запис відхилено');
    }
    this.nodes.forEach(n => { n.value = value; n.version++; });
    return value;
  }

  apWrite(value, nodeId = 0) {
    const node = this.nodes[nodeId];
    node.value = value;
    node.version++;
    // поширюємо на інші вузли тільки якщо немає розбиття
    if (!this.partition) {
      this.nodes.filter(n => n.id !== nodeId).forEach(n => {
        n.value = value;
        n.version = node.version;
      });
    }
    return { value, nodeId };
  }

  read(nodeId = 0) {
    return this.nodes[nodeId].value;
  }
}

const rs = new ReplicaSet();
rs.cpWrite(100);
rs.partition = true;

try {
  rs.cpWrite(200);
} catch (e) {
  console.log(e.message); // CP: розбиття активне, запис відхилено
}

rs.apWrite(200, 0);
console.log(rs.read(0)); // 200
console.log(rs.read(1)); // 100 - застарілі дані, але система залишилась доступною

Після відновлення мережі AP-система має виконати reconciliation. Cassandra використовує last-write-wins за timestamp. Для складніших випадків застосовують CRDTs - структури даних злиття (conflict-free replicated data types), які зливаються без конфліктів.

Середній рівень: Кворумне сховище (стиль Cassandra)

javascript

class TunableStore {
  constructor(rf = 3) {
    this.replicas = new Array(rf).fill(null).map((_, i) => ({
      id: i,
      data: {},
      online: true,
    }));
  }

  async write(key, value, w = 2) {
    const available = this.replicas.filter(r => r.online);
    available.forEach(r => { r.data[key] = { value, ts: Date.now() }; });
    if (available.length < w) {
      throw new Error(`Кворум запису не досягнуто: ${available.length} з ${w} потрібних`);
    }
    return value;
  }

  async read(key, r = 2) {
    const available = this.replicas.filter(n => n.online && n.data[key]);
    if (available.length < r) {
      throw new Error(`Кворум читання не досягнуто: ${available.length} з ${r} потрібних`);
    }
    return available
      .map(n => n.data[key])
      .sort((a, b) => b.ts - a.ts)[0].value;
  }
}

const store = new TunableStore(3);
await store.write('balance', 500, 2);
store.replicas[2].online = false;     // один вузол вимикається

console.log(await store.read('balance', 2)); // 500 - кворум з 2 вузлів працює

store.replicas[1].online = false;     // другий вузол вимикається

try {
  await store.read('balance', 2);
} catch (e) {
  console.log(e.message); // Кворум читання не досягнуто: 1 з 2 потрібних
}

Формула W+R > N у дії. RF=3, W=2, R=2: будь-яке читання перетинається з будь-яким записом. Знижуєш до W=1, R=1 - отримуєш чистий AP з ризиком застарілих читань. Вибір залежить від того, що гірше для твого сценарію: відмова від читання або застарілі дані.

Просунутий рівень: Гібридний підхід для фінтеху

javascript

// Патерн: AP-база з CP-примусом тільки для критичних операцій
class HybridStore {
  constructor() {
    this.regions = {
      us: { balance: 1000, version: 1, online: true },
      eu: { balance: 1000, version: 1, online: true },
    };
    this.pendingTransfers = [];
  }

  read(region) {
    return this.regions[region]; // AP: локальне читання, швидко
  }

  transfer(fromRegion, amount) {
    const allOnline = Object.values(this.regions).every(r => r.online);
    if (!allOnline) {
      // ставимо в чергу, виконуємо після відновлення
      this.pendingTransfers.push({ fromRegion, amount, ts: Date.now() });
      throw new Error('Розбиття активне: переказ поставлено в чергу');
    }
    if (this.regions[fromRegion].balance < amount) {
      throw new Error('Недостатньо коштів');
    }
    Object.values(this.regions).forEach(r => { r.balance -= amount; r.version++; });
    return this.regions[fromRegion].balance;
  }

  heal() {
    Object.values(this.regions).forEach(r => (r.online = true));
    const pending = [...this.pendingTransfers];
    this.pendingTransfers = [];
    return pending.map(t => {
      try {
        return { ...t, result: this.transfer(t.fromRegion, t.amount) };
      } catch (e) {
        return { ...t, error: e.message };
      }
    });
  }
}

const store = new HybridStore();
store.regions.eu.online = false; // регіон EU недоступний

try {
  store.transfer('us', 200);
} catch (e) {
  console.log(e.message); // Розбиття активне: переказ поставлено в чергу
}

console.log(store.read('us').balance); // 1000 - AP-читання доступне

const resolved = store.heal();
console.log(resolved);                 // переказ виконано після відновлення
console.log(store.read('us').balance); // 800

Це патерн для міжрегіонального банкінгу: AP для читань скрізь, CP тільки для операцій переказу. Черга відкладених транзакцій з replay після відновлення дає можливість зберегти доступність без ризику втрати фінансових даних під час розбиття.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Дочитали статтю?