Что такое теорема Брюера?

Что такое теорема Брюера?

Теорема Брюера (Brewer's theorem) — это фундаментальная теоретическая основа проектирования распределённых систем. Её также называют теоремой CAP (Consistency-Availability-Partition tolerance). Сформулирована в 1999 году профессором Эриком Брюером из UC Berkeley.

Формулировка теоремы

Добавить: распределённая система не может одновременно гарантировать три следующих свойства:

┌──────────────────────────────────────────────┐
│  Распределённая система может гарантировать │
│     максимум ДВА из трёх свойств:            │
│                                              │
│   C (Consistency)                            │
│   A (Availability)                           │
│   P (Partition tolerance)                    │
└──────────────────────────────────────────────┘

Три свойства CAP

1. Consistency (Согласованность данных)

Все узлы системы имеют одинаковые актуальные данные в любой момент времени.

// Пример согласованности
// Клиент 1 читает value = 100
Datastore datastore = connect("server1");
int value = datastore.read("account:123"); // 100

// В тот же момент клиент 2 пишет новое значение
Datastore datastore2 = connect("server2");
datastore2.write("account:123", 150);

// Клиент 1 читает СРАЗУ ЖЕ ещё раз
int newValue = datastore.read("account:123"); // ДОЛЖНО быть 150 (Consistent)

// Если получит 100 — система INCONSISTENT

Примеры систем с высокой согласованностью:

• Банковские системы
• Системы бронирования
• Базы данных SQL

2. Availability (Доступность)

Система всегда отвечает на запросы (не зависает, не отказывает).

// Пример доступности
public class AvailableService {
    public Response handleRequest(Request request) {
        try {
            // Всегда должна вернуть ответ
            return processRequest(request);
        } catch (Exception e) {
            // Даже при ошибке возвращаем результат
            return createErrorResponse(e);
        }
        // НИКОГДА не зависает, не блокируется, не отказывает
    }
}

// Прибор доступности
long start = System.currentTimeMillis();
Response response = service.handleRequest(request);
long latency = System.currentTimeMillis() - start;

// Система должна ответить за разумное время
if (latency > timeout) {
    // Service потеряла доступность!
}

Примеры систем с высокой доступностью:

• Кэши (Redis, Memcached)
• Социальные сети
• Системы логирования
• CDN

3. Partition tolerance (Устойчивость к разделению сети)

Система продолжает работать даже когда сетевое соединение между узлами порвано.

Сценарий разделения сети (Network Partition):

┌─────────┐                    ┌─────────┐
│ Node 1  │     РАЗРЫВ СЕТИ    │ Node 2  │
│ online  │ ════════════════    │ online  │
│ Group A │                     │ Group B │
└─────────┘                     └─────────┘

// Node 1 и Node 2 не могут общаться
// Но оба должны продолжать работать
Node1.handleRequest(request1); // Должна ответить
Node2.handleRequest(request2); // Должна ответить

// Java пример
public class PartitionTolerantService {
    public void handlePartition() {
        try {
            // Пытаемся связаться с другими узлами
            boolean canReachOtherNodes = ping("node2");
            
            if (!canReachOtherNodes) {
                // Сеть разделена, но мы продолжаем работать
                // (может быть с кэшированными данными)
                serveCachedData();
                
                // Синхронизируемся позже, когда сеть восстановится
                pendingChanges.add(change);
            }
        } catch (Exception e) {
            // Продолжаем работать несмотря на разрыв сети
        }
    }
}

Три возможные комбинации CAP

          ┌─────┐
        /  CAP  \
      /     │     \
    C       │       A
     \      │      /
      \  P──┴─────/
        \  /
        CP   CA   AP

CP системы (Consistency + Partition tolerance)

Устойчивы к разделению сети, но жертвуют доступностью.

// Google BigTable, HBase, Zookeeper, MongoDB
// Пример: банковская система

public class BankingService implements CP {
    public void transfer(String from, String to, BigDecimal amount) {
        // При разделении сети система может отказать
        if (!canReachMajority()) {
            throw new ServiceUnavailableException(
                "Cannot guarantee consistency, denying request"
            );
        }
        
        // Только если уверены в согласованности
        processTransfer(from, to, amount);
    }
}

// Компромисс: лучше отказать, чем дать несогласованные данные

AP системы (Availability + Partition tolerance)

Доступны при разделении сети, но жертвуют консистентностью (eventual consistency).

// Dynamo, Cassandra, Riak, Redis
// Пример: социальная сеть

public class SocialNetworkService implements AP {
    public void like(String postId, String userId) {
        // Всегда отвечаем, даже при разделении сети
        try {
            database.like(postId, userId);
            
            // Если другой узел недоступен, запишем локально
            localCache.like(postId, userId);
            
            // Синхронизируемся в фоне, когда сеть восстановится
            syncInBackground();
        } catch (Exception e) {
            // Даже при ошибке пытаемся ответить
            return createPartialResponse();
        }
    }
}

// Компромисс: данные могут быть временно несогласованными

CA системы (Consistency + Availability)

У них нет устойчивости к разделению сети (редко используются в распределённых системах).

// Традиционные SQL базы (MySQL, PostgreSQL с одним сервером)
// ACID базы данных

public class TraditionalDatabase implements CA {
    // При разделении сети система падает
    // Не может работать распределённо
    // Но всегда согласована и доступна (пока работает)
}

// В реальном распределённом мире CA почти невозможно

Визуальное сравнение

CP (Consistent + Partition-tolerant)
┌─────────────────────────────────┐
│ СОГЛАСОВАННОСТЬ:    высокая     │
│ ДОСТУПНОСТЬ:        может отказать│
│ РАЗД. СЕТИ:         работает     │
│ ПРИМЕРЫ:            БД, Zookeeper│
└─────────────────────────────────┘

AP (Available + Partition-tolerant)
┌─────────────────────────────────┐
│ СОГЛАСОВАННОСТЬ:    временная    │
│ ДОСТУПНОСТЬ:        всегда       │
│ РАЗД. СЕТИ:         работает     │
│ ПРИМЕРЫ:            Cassandra    │
└─────────────────────────────────┘

CA (Consistent + Available)
┌─────────────────────────────────┐
│ СОГЛАСОВАННОСТЬ:    высокая     │
│ ДОСТУПНОСТЬ:        всегда       │
│ РАЗД. СЕТИ:         ПАДАЕТ       │
│ ПРИМЕРЫ:            Монолит БД   │
└─────────────────────────────────┘

Practical примеры выбора

// 1. БАНК (CP)
// Функция: перевод денег
// Требование: НИКОГДА не потерять деньги
// Решение: при разделении сети отказать в операции

public class BankTransfer implements CP {
    @Transactional(isolation = Isolation.SERIALIZABLE)
    public void transfer(Account from, Account to, BigDecimal amount) 
            throws NetworkPartitionException {
        if (networkDivided()) {
            throw new NetworkPartitionException("Cannot guarantee consistency");
        }
        // Выполнить с гарантией ACID
    }
}

// 2. TWITTER (AP)
// Функция: лайк на твит
// Требование: всегда должна работать
// Решение: лайк может быть видн не сразу везде

public class TwitterLike implements AP {
    public void addLike(String tweetId, String userId) {
        // Добавляем лайк локально (всегда успешно)
        localDatabase.addLike(tweetId, userId);
        
        // Асинхронно синхронизируем с другими регионами
        eventBus.publish(new LikeEvent(tweetId, userId));
    }
}

// 3. GMAIL (CP)
// Требование: сообщение либо отправлено везде, либо нет

public class GmailService implements CP {
    public void sendEmail(Email email) throws PartitionException {
        // Гарантируем, что все узлы знают об этом письме
        // Или ничего не знают
        try {
            database.save(email);
        } catch (PartitionException e) {
            // Отказываем отправку
            throw e;
        }
    }
}

Практические рекомендации

Выбери CP, если:
- Критична консистентность (финансы, инвентарь)
- Разделение сети редко
- Допустимо периодически отказывать
- Приватные данные

Выбери AP, если:
- Критична доступность (публичные данные)
- Временная несогласованность допустима
- Большие распределённые системы
- Кэширование и реплика в разных регионах

Важные уточнения (Spanner, NewSQL)

С развитием технологий (Google Spanner, CockroachDB) граница между CP и AP стирается:

// CockroachDB использует более хитрую тактику
// Гарантирует ACID + доступность + масштабируемость
// Но с допустимой задержкой консистентности

Теорема Брюера (CAP) — критический инструмент для понимания trade-offs при проектировании распределённых систем. Выбор между CP и AP определяет архитектуру всего приложения.