CAP теорема

Формулировка

CAP теорема (теорема Брюера, 2000) утверждает, что распределённая система может обеспечить только два из трёх свойств одновременно:

C (Consistency) -- согласованность: каждое чтение возвращает результат последней записи
A (Availability) -- доступность: каждый запрос получает ответ (не ошибку)
P (Partition Tolerance) -- устойчивость к разделению сети

Почему только 2 из 3

Сетевые разделения (partition) неизбежны. Поэтому P -- обязательное свойство. Выбор сводится к: CP или AP.

Клиент A --> [Узел 1]     [Узел 2] <-- Клиент B
                    РАЗРЫВ СЕТИ

Клиент A записал x=1 на Узел 1.
Клиент B читает x с Узла 2.

CP: Узел 2 отвечает ошибкой (не может гарантировать актуальность)
AP: Узел 2 отвечает старым значением x=0 (доступность важнее)

CP vs AP системы

CP (Consistency + Partition Tolerance)

Система предпочитает ошибку, чем устаревшие данные.

Примеры: ZooKeeper, etcd, MongoDB (write concern majority), HBase

Когда выбирать: финансовые операции, координация (locks), inventory management

AP (Availability + Partition Tolerance)

Система всегда отвечает, даже если данные устаревшие.

Примеры: Cassandra, DynamoDB, CouchDB, DNS

Когда выбирать: соцсети, метрики, корзина покупок, CDN

Таблица выбора

Система	Тип	Примечание
PostgreSQL (single)	CA	Нет partition (одноузловая)
PostgreSQL + replicas	CP	Зависит от настройки
Redis Sentinel	CP	Downtime при failover
Cassandra	AP	Tunable consistency
MongoDB	CP	Write concern majority
Elasticsearch	AP	Split-brain возможен
etcd	CP	Raft consensus

Tunable Consistency

Некоторые системы позволяют выбирать компромисс per-query.

<?php

declare(strict_types=1);

/**
 * Tunable consistency levels.
 * Strong consistency: R + W > N (read + write replicas > total replicas).
 */
final class TunableConsistency
{
    /**
     * @return array<string, array{read: int, write: int, consistency: string, use_case: string}>
     */
    public static function levels(int $replicas = 3): array
    {
        $quorum = (int) ceil(($replicas + 1) / 2);

        return [
            'ONE_ONE' => [
                'read' => 1,
                'write' => 1,
                'consistency' => 'eventual (R+W < N)',
                'use_case' => 'Metrics, logs, non-critical data',
            ],
            'QUORUM_QUORUM' => [
                'read' => $quorum,
                'write' => $quorum,
                'consistency' => 'strong (R+W > N)',
                'use_case' => 'Most applications, good default',
            ],
            'ALL_ONE' => [
                'read' => $replicas,
                'write' => 1,
                'consistency' => 'strong (N+1 > N)',
                'use_case' => 'Write-heavy workloads',
            ],
            'ONE_ALL' => [
                'read' => 1,
                'write' => $replicas,
                'consistency' => 'strong (1+N > N)',
                'use_case' => 'Read-heavy workloads',
            ],
        ];
    }
}

package consistency

import "math"

// ConsistencyLevel describes a tunable consistency configuration.
type ConsistencyLevel struct {
	Read        int
	Write       int
	Consistency string
	UseCase     string
}

// TunableLevels returns available consistency levels for a given replica count.
// Strong consistency requires: R + W > N
func TunableLevels(replicas int) map[string]ConsistencyLevel {
	quorum := int(math.Ceil(float64(replicas+1) / 2))

	return map[string]ConsistencyLevel{
		"ONE_ONE": {
			Read: 1, Write: 1,
			Consistency: "eventual (R+W < N)",
			UseCase:     "Metrics, logs, non-critical data",
		},
		"QUORUM_QUORUM": {
			Read: quorum, Write: quorum,
			Consistency: "strong (R+W > N)",
			UseCase:     "Most applications, good default",
		},
		"ALL_ONE": {
			Read: replicas, Write: 1,
			Consistency: "strong (N+1 > N)",
			UseCase:     "Write-heavy workloads",
		},
		"ONE_ALL": {
			Read: 1, Write: replicas,
			Consistency: "strong (1+N > N)",
			UseCase:     "Read-heavy workloads",
		},
	}
}

namespace Consistency;

// ConsistencyLevel describes a tunable consistency configuration.
public sealed record ConsistencyLevel(int Read, int Write, string Consistency, string UseCase);

public static class TunableConsistency
{
    // Levels returns available consistency levels for a given replica count.
    // Strong consistency requires: R + W > N
    public static IReadOnlyDictionary<string, ConsistencyLevel> Levels(int replicas = 3)
    {
        var quorum = (int)Math.Ceiling((replicas + 1) / 2.0);

        return new Dictionary<string, ConsistencyLevel>
        {
            ["ONE_ONE"] = new(
                Read: 1, Write: 1,
                Consistency: "eventual (R+W < N)",
                UseCase: "Metrics, logs, non-critical data"),
            ["QUORUM_QUORUM"] = new(
                Read: quorum, Write: quorum,
                Consistency: "strong (R+W > N)",
                UseCase: "Most applications, good default"),
            ["ALL_ONE"] = new(
                Read: replicas, Write: 1,
                Consistency: "strong (N+1 > N)",
                UseCase: "Write-heavy workloads"),
            ["ONE_ALL"] = new(
                Read: 1, Write: replicas,
                Consistency: "strong (1+N > N)",
                UseCase: "Read-heavy workloads"),
        };
    }
}

import math
from dataclasses import dataclass

@dataclass(frozen=True)
class ConsistencyLevel:
    """A tunable consistency configuration."""

    read: int
    write: int
    consistency: str
    use_case: str

def tunable_levels(replicas: int = 3) -> dict[str, ConsistencyLevel]:
    """Return available consistency levels for a given replica count.

    Strong consistency requires: R + W > N
    """
    quorum = math.ceil((replicas + 1) / 2)

    return {
        "ONE_ONE": ConsistencyLevel(
            read=1,
            write=1,
            consistency="eventual (R+W < N)",
            use_case="Metrics, logs, non-critical data",
        ),
        "QUORUM_QUORUM": ConsistencyLevel(
            read=quorum,
            write=quorum,
            consistency="strong (R+W > N)",
            use_case="Most applications, good default",
        ),
        "ALL_ONE": ConsistencyLevel(
            read=replicas,
            write=1,
            consistency="strong (N+1 > N)",
            use_case="Write-heavy workloads",
        ),
        "ONE_ALL": ConsistencyLevel(
            read=1,
            write=replicas,
            consistency="strong (1+N > N)",
            use_case="Read-heavy workloads",
        ),
    }

## Ограничения CAP теоремы

Partition -- не выбор: разделения случаются, вопрос -- что делать при них
Не бинарный выбор: можно быть "немного" C и "немного" A
Partition -- редкость: большую часть времени система может быть и C, и A
Consistency в CAP != ACID: CAP-consistency -- линеаризуемость, ACID -- целостность данных
Не учитывает latency: CAP говорит о correctness, не о скорости

Для более полной картины: используйте PACELC теорему, которая учитывает latency vs consistency tradeoff в нормальном режиме работы.

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

<?php

declare(strict_types=1);

/**
 * Decision framework for choosing CP vs AP.
 */
final class ConsistencyDecision
{
    /**
     * @return array{model: string, reason: string, systems: string[]}
     */
    public static function recommend(
        bool $financial,
        bool $global,
        int $staleTolerance,
    ): array {
        if ($financial) {
            return [
                'model' => 'CP',
                'reason' => 'Financial operations require strong consistency',
                'systems' => ['PostgreSQL + sync replication', 'CockroachDB'],
            ];
        }

        if ($global && $staleTolerance > 5) {
            return [
                'model' => 'AP with tunable consistency',
                'reason' => 'Global reach + latency needs AP; strong for critical paths',
                'systems' => ['DynamoDB', 'Cassandra LOCAL_QUORUM'],
            ];
        }

        return [
            'model' => 'CP with read replicas',
            'reason' => 'Consistency for writes, tolerate stale reads',
            'systems' => ['PostgreSQL + read replicas', 'MongoDB replica set'],
        ];
    }
}

package consistency

// Recommendation holds the suggested consistency model.
type Recommendation struct {
	Model   string
	Reason  string
	Systems []string
}

// Recommend suggests a consistency model based on requirements.
func Recommend(financial, global bool, staleToleranceSec int) Recommendation {
	if financial {
		return Recommendation{
			Model:   "CP",
			Reason:  "Financial operations require strong consistency",
			Systems: []string{"PostgreSQL + sync replication", "CockroachDB"},
		}
	}

	if global && staleToleranceSec > 5 {
		return Recommendation{
			Model:   "AP with tunable consistency",
			Reason:  "Global reach + latency needs AP; strong for critical paths",
			Systems: []string{"DynamoDB", "Cassandra LOCAL_QUORUM"},
		}
	}

	return Recommendation{
		Model:   "CP with read replicas",
		Reason:  "Consistency for writes, tolerate stale reads",
		Systems: []string{"PostgreSQL + read replicas", "MongoDB replica set"},
	}
}

namespace Consistency;

// Recommendation holds the suggested consistency model.
public sealed record Recommendation(string Model, string Reason, IReadOnlyList<string> Systems);

public static class ConsistencyDecision
{
    // Recommend suggests a consistency model based on requirements.
    public static Recommendation Recommend(bool financial, bool global, int staleToleranceSec)
    {
        if (financial)
        {
            return new Recommendation(
                Model: "CP",
                Reason: "Financial operations require strong consistency",
                Systems: ["PostgreSQL + sync replication", "CockroachDB"]);
        }

        if (global && staleToleranceSec > 5)
        {
            return new Recommendation(
                Model: "AP with tunable consistency",
                Reason: "Global reach + latency needs AP; strong for critical paths",
                Systems: ["DynamoDB", "Cassandra LOCAL_QUORUM"]);
        }

        return new Recommendation(
            Model: "CP with read replicas",
            Reason: "Consistency for writes, tolerate stale reads",
            Systems: ["PostgreSQL + read replicas", "MongoDB replica set"]);
    }
}

from dataclasses import dataclass

@dataclass(frozen=True)
class Recommendation:
    """The suggested consistency model."""

    model: str
    reason: str
    systems: list[str]

def recommend(financial: bool, global_reach: bool, stale_tolerance_sec: int) -> Recommendation:
    """Suggest a consistency model based on requirements."""
    if financial:
        return Recommendation(
            model="CP",
            reason="Financial operations require strong consistency",
            systems=["PostgreSQL + sync replication", "CockroachDB"],
        )

    if global_reach and stale_tolerance_sec > 5:
        return Recommendation(
            model="AP with tunable consistency",
            reason="Global reach + latency needs AP; strong for critical paths",
            systems=["DynamoDB", "Cassandra LOCAL_QUORUM"],
        )

    return Recommendation(
        model="CP with read replicas",
        reason="Consistency for writes, tolerate stale reads",
        systems=["PostgreSQL + read replicas", "MongoDB replica set"],
    )

## Выводы

CAP теорема: из C, A, P можно выбрать только два, и P обязателен
CP: консистентность важнее доступности (финансы, координация)
AP: доступность важнее консистентности (соцсети, метрики)
Tunable consistency позволяет выбирать компромисс per-query
CAP -- полезная модель, но упрощает реальность
Для полной картины используйте PACELC теорему