Какой знаешь способ доказательства теоремы CAP?

CAP теорема и её доказательство

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

CAP теорема (Brewer's Theorem, 2000) гласит, что распределённая система может одновременно гарантировать только два из трёх следующих свойств:

• Consistency (Согласованность) — все узлы видят одинаковые данные в одно время
• Availability (Доступность) — система отвечает на запросы
• Partition tolerance (Устойчивость к разделению) — система работает при разделении сети

Классическое доказательство через противоречие

Доказательство от противного (Proof by Contradiction):

Предположим, что система может одновременно обеспечить все три свойства: C, A и P.

Сценарий: Сетевой раздел

Имаем распределённую систему с двумя узлами: Node A и Node B.

┌─────────────┐         ┌─────────────┐
│   Node A    │ ───╳──── │   Node B    │
│ (Partition) │         │ (Partition) │
└─────────────┘         └─────────────┘

Возникает сетевой раздел (network partition): узлы не могут общаться друг с другом.

Шаг 1: Принимаем запрос на Node A

// Клиент отправляет запрос на Node A
writing = true;  // key = "value1"

// Node A получает и обрабатывает запрос
Data data = new Data("value1");
stateA = data;  // Node A: key = "value1"

Шаг 2: Попытка синхронизации

Node A пытается отправить изменение на Node B, но сетевой раздел препятствует:

// Node A отправляет: key = "value1" на Node B
// ❌ Ошибка: сеть разделена, сообщение не доходит
stateB = null;  // Node B остаётся со старым состоянием (если было)

Шаг 3: Противоречие с требованиями

Теперь у нас есть:

• Node A: key = "value1"
• Node B: key = old_value (или неизвестно)

Анализ:

1. Если выбираем Consistency (C):

   • Нужно отклонить запрос на Node A, чтобы не нарушить согласованность
   • Но тогда Availability (A) нарушена — система не отвечает

   // Отклонение запроса
   throw new ConsistencyException("Cannot write: network partition");
   

2. Если выбираем Availability (A):

   • Node A принимает запрос (доступна)
   • Node B не обновляется (недоступна сеть)
   • Нарушена Consistency (C) — разные узлы видят разные данные

   // Приём запроса, но нарушение консистентности
   accept(request);  // A доступна
   // но C нарушена: A != B
   

3. Partition tolerance (P) обязателен:

   • В распределённой системе сетевые разделы неизбежны
   • Мы не можем избежать P
   • P принимается как данность

Вывод: При сетевом разделе мы ВСЕГДА выбираем между C и A. Невозможно иметь все три.

Формальное доказательство (упрощённое)

Дано:
- Распределённая система с узлами N1, N2, ..., Nk
- Сетевой раздел P разделяет систему на две группы
- Запрос W пришёл к группе G1

Доказать: Невозможно гарантировать C, A, P одновременно

Доказательство:

1. Partition Tolerance (P) = обязателен
   - В реальных системах разделы сети происходят (AWS outages, etc.)
   - P is non-negotiable

2. Допустим W пришёл на узел в G1:
   - G1 получает W: request_received = true
   - G2 не получает W: request_received = false

3. Выполнение W на G1:
   - State_G1 = updated_state
   - State_G2 = old_state (не обновлён)

4. Вывод:
   - Если Consistency требуется: REJECT W → Availability нарушена ✗
   - Если Availability требуется: ACCEPT W → Consistency нарушена ✗
   - Оба не достижимы одновременно ✗

Q.E.D.

Практический пример на Java

public class CAPExample {
    // Распределённая система из 2 узлов
    class DistributedDatabase {
        Map<String, String> nodeA = new ConcurrentHashMap<>();
        Map<String, String> nodeB = new ConcurrentHashMap<>();
        boolean networkPartition = false;
        
        // Сценарий: попытка записи при разделе сети
        public void writeWithPartition(String key, String value) {
            // Node A получает запрос
            nodeA.put(key, value);
            System.out.println("Node A: " + key + " = " + value);
            
            // Попытка синхронизации
            if (networkPartition) {
                System.out.println("⚠ Сетевой раздел: не могу отправить на Node B");
                // Node B остаётся несинхронизированной
            } else {
                nodeB.put(key, value);
                System.out.println("Node B: " + key + " = " + value);
            }
            
            // Результат: выбираем между C и A
            printState();
        }
        
        void printState() {
            System.out.println("Node A state: " + nodeA);
            System.out.println("Node B state: " + nodeB);
            System.out.println("Consistency: " + nodeA.equals(nodeB));
        }
    }
    
    public static void main(String[] args) {
        DistributedDatabase db = new DistributedDatabase().new DistributedDatabase();
        
        System.out.println("=== Сценарий 1: С доступностью (A), но без консистентности (C) ===");
        db.networkPartition = true;
        db.writeWithPartition("user_id", "123");
        // Node A видит обновление, Node B нет → C нарушена
        
        System.out.println("\n=== Сценарий 2: С консистентностью, но без доступности ===");
        // Отклонили бы запрос на Node A, чтобы гарантировать C
        System.out.println("❌ Write rejected: Network partition detected (C over A)");
    }
}

Три варианта выбора в CAP

1. CP (Consistency + Partition Tolerance)

• Выбираем консистентность
• Отклоняем операции при разделе
• Примеры: HBase, MongoDB (по умолчанию)

if (networkPartition) {
    throw new PartitionException("Cannot guarantee consistency");
}

2. AP (Availability + Partition Tolerance)

• Выбираем доступность
• Принимаем запросы при разделе
• Разрешаем конфликты потом (eventual consistency)
• Примеры: Cassandra, DynamoDB, Riak

if (networkPartition) {
    accept(write);  // Принимаем
    scheduleSync(); // Синхронизируем позже
}

3. CA (Consistency + Availability)

• Невозможно в распределённых системах
• Работает только в single-node или fully-connected systems

Важные замечания

• CAP теорема не говорит о выборе между C и A просто так — она говорит о выборе при сетевом разделе
• Modern databases часто используют Eventual Consistency (AP) — консистентность гарантируется "в конце концов"
• PACELC теорема расширяет CAP для нормального состояния сети (без раздела)

Резюме доказательства

Доказательство CAP теоремы основано на логическом противоречии: при сетевом разделе система не может одновременно:

1. Отклонить запрос (C) и принять его (A)
2. Обновить все узлы (C) и ответить сразу (A)

Это фундаментальное ограничение распределённых систем, а не недостаток конкретной реализации.