Репликация и модели согласованности

Зачем нужна репликация

Репликация -- хранение копий данных на нескольких узлах. Это фундаментальный механизм для:

Отказоустойчивости -- при падении одного узла данные доступны на других
Масштабирования чтения -- запросы распределяются между репликами
Географической близости -- реплики ближе к пользователям

┌──────────────────────────────────────────────────┐
│                 Replication                        │
│                                                    │
│  ┌─────────┐     ┌─────────┐     ┌─────────┐     │
│  │ Primary │────>│ Replica │     │ Replica │     │
│  │  (NYC)  │  │  │  (LON)  │     │ (TOK)   │     │
│  └─────────┘  │  └─────────┘     └─────────┘     │
│      ▲        │       ▲               ▲           │
│      │        └───────┼───────────────┘           │
│    Writes           Reads distributed              │
│                     across replicas                │
└──────────────────────────────────────────────────┘

Топологии репликации

Single-Leader (Primary-Replica)

                  ┌──────────┐
    Writes ──────>│  Primary │
                  └────┬─────┘
                       │ replication stream
              ┌────────┼────────┐
              ▼        ▼        ▼
         ┌────────┐┌────────┐┌────────┐
  Reads  │Replica1││Replica2││Replica3│  Reads
  ──────>│        ││        ││        │<──────
         └────────┘└────────┘└────────┘

Свойство	Описание
Запись	Только на Primary
Чтение	С любого узла
Конфликты	Невозможны (один writer)
Bottleneck	Primary (все записи)
Примеры	PostgreSQL, MySQL, MongoDB, Redis Sentinel

Multi-Leader (Active-Active)

         ┌──────────┐             ┌──────────┐
Writes ─>│ Leader A │<──────────>│ Leader B │<─ Writes
  (NYC)  │          │  bi-dir    │          │  (LON)
         └──────────┘  repl.     └──────────┘

Свойство	Описание
Запись	На любой лидер
Конфликты	Возможны! Нужна стратегия разрешения
Задержка	Ниже (пишем в ближайший)
Сложность	Высокая (conflict resolution)
Примеры	CockroachDB, Galera Cluster, DynamoDB Global Tables

Leaderless (Dynamo-style)

Client ──── Write ──────> Node A  (W=2: write to 2 of 3)
       ──── Write ──────> Node B  ✓
       ──── Write ──────> Node C  ✓
                          Node A  (missed, will repair later)

Client ──── Read ───────> Node A  (R=2: read from 2 of 3)
       ──── Read ───────> Node B  ✓ v2
       ──── Read ───────> Node C  ✓ v2

Свойство	Описание
Лидер	Нет
Запись	На W из N узлов
Чтение	С R из N узлов
Strong consistency	R + W > N
Примеры	Cassandra, Riak, DynamoDB

Синхронная vs Асинхронная репликация

Синхронная:
Primary: Write ──────> Replica: Write ──────> ACK ──────> Client: OK
                       (ждём подтверждения)
         ├──────────── high latency ───────────────────────┤

Асинхронная:
Primary: Write ──────> Client: OK     Replica: Write (позже)
         ├── low latency ──┤
                                       Может потерять данные
                                       при падении Primary!

Аспект	Синхронная	Асинхронная	Semi-синхронная
Задержка	Высокая	Низкая	Средняя
Потеря данных	Невозможна	Возможна	1 реплика гарантирована
Доступность	Ниже	Выше	Компромисс
PostgreSQL	`synchronous_commit=on`	`synchronous_commit=off`	`synchronous_standby_names`

Модели согласованности

Спектр согласованности

Слабая ──────────────────────────────────────────── Сильная

Eventual    Monotonic    Read-your-   Causal     Sequential   Strong
Consistency  Reads       writes       Consistency Consistency  (Linear-
                                                              izability)
   │           │            │            │           │            │
   ▼           ▼            ▼            ▼           ▼            ▼
  AP    ────────── компромиссы ──────────────────────────────    CP
  Fast                                                         Slow

Strong Consistency (Линеаризуемость)

Самая строгая модель. Любая операция чтения возвращает результат последней завершённой записи. Система ведёт себя так, будто реплика одна.

Timeline:
─────────────────────────────────────────────>

Client A: Write(x=1)     Write(x=2)
          ├────┤          ├────┤
                    Client B:     Read(x) → must return 2
                                  ├──┤

После завершения Write(x=2) любой Read ОБЯЗАН вернуть 2.

Реализация: Consensus (Raft, Paxos), synchronous replication

Примеры: ZooKeeper, etcd, Spanner

Цена: Каждая запись требует подтверждения от кворума → высокая задержка

Eventual Consistency (Конечная согласованность)

Если прекратить записи, со временем все реплики станут согласованными. Но "со временем" -- неопределённый период.

Timeline:
─────────────────────────────────────────────>

Primary: Write(x=1)
Replica1:              x=? → x=? → x=1 (replicated!)
Replica2:              x=? → x=? → x=? → x=1

Окно несогласованности (inconsistency window):
├──────── stale reads возможны ──────────┤

Реализация: Асинхронная репликация

Примеры: DNS, Cassandra (ONE/ONE), DynamoDB (default)

Плюсы: Высокая доступность и низкая задержка

Read-Your-Writes (Read-After-Write)

Гарантия: клиент всегда видит свои собственные записи. Но может не видеть записи других клиентов.

Client A: Write(x=1) ──────> Read(x) → ГАРАНТИРОВАНО x=1
                              (даже если читает с реплики)

Client B:                     Read(x) → x=0 (может быть!)
                              (не видит запись Client A)

Реализации:

Подход	Описание
Sticky session	Клиент всегда идёт на одну реплику
Read from primary	После записи читать с primary
Logical timestamp	Клиент передаёт timestamp последней записи; реплика ждёт

// Sticky session approach
Client A → Write → Primary (timestamp=42)
Client A → Read  → Primary (или реплика с timestamp >= 42)

// Token-based approach
POST /orders → Response: { id: 123, _token: "t=42" }
GET /orders/123 → Header: X-Read-After: t=42
  Server: if replica.position < 42, redirect to primary

Monotonic Reads

Гарантия: если клиент прочитал значение v, при следующем чтении он увидит v или более новое значение. Время не "откатывается назад".

БЕЗ monotonic reads:
Client: Read(x) from Replica1 → x=2
Client: Read(x) from Replica2 → x=1  ← Откат! Видит старое значение!

С monotonic reads:
Client: Read(x) from Replica1 → x=2
Client: Read(x) from Replica2 → x=2 или x=3 (никогда не x=1)

Реализация: Sticky sessions (клиент всегда на одной реплике) или передача version token.

Causal Consistency (Причинная согласованность)

Если событие B причинно зависит от события A, все узлы увидят A перед B. Конкурентные события могут быть в любом порядке.

User A: Post("Hello!")          ← Event A
User B: Reply("Hi!", to=A)     ← Event B (B depends on A)

Causal consistency guarantees:
All users see Post BEFORE Reply

User C reads:
  ✓ "Hello!" → "Hi!"           (correct order)
  ✗ "Hi!" → "Hello!"           (violates causality)
  ✓ But concurrent posts may appear in any order

Реализация: Vector clocks, causal dependency tracking

Примеры: MongoDB (causal sessions), Cosmos DB

Sequential Consistency

Все узлы видят операции в одинаковом порядке, но этот порядок может отличаться от real-time порядка.

Sequential Consistency:
Client A: Write(x=1)     Write(x=2)
Client B: Write(y=1)     Write(y=2)

Valid orderings (all nodes see same order):
  x=1, y=1, x=2, y=2  ✓
  y=1, x=1, y=2, x=2  ✓
  x=1, x=2, y=1, y=2  ✓

Invalid:
  x=2, x=1, ...        ✗ (violates per-client order)

Сравнительная таблица моделей

Модель	Гарантия	Задержка	Доступность	Пример
Strong	Последняя запись	Высокая	Низкая	Spanner, etcd
Sequential	Одинаковый порядок	Средняя	Средняя	ZooKeeper
Causal	Причинный порядок	Низкая-Средняя	Высокая	MongoDB sessions
Read-your-writes	Свои записи видны	Низкая	Высокая	Sticky sessions
Monotonic reads	Нет "откатов"	Низкая	Высокая	Sticky sessions
Eventual	"Когда-нибудь"	Минимальная	Максимальная	DNS, Cassandra

Quorum-based репликация

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

N = total number of replicas
W = write quorum (number of ACKs for write success)
R = read quorum (number of nodes to read from)

Strong consistency: R + W > N

Примеры конфигураций (N=3)

W	R	R+W	Согласованность	Характеристика
1	1	2	Eventual	Max throughput
2	1	3	Eventual reads, durable writes	Write-heavy
1	2	3	Fast writes, consistent reads	Read-heavy
2	2	4	Strong	Balanced
3	1	4	Strong, slow writes	Read-optimized

Read Repair

Client reads from R=2 replicas:

Node A: x=2 (version 5)
Node B: x=1 (version 3)   ← stale!

Read Repair:
1. Return x=2 to client (newest version)
2. Send x=2 to Node B → Node B updates to version 5

After repair: all read replicas consistent

Anti-Entropy (Merkle Trees)

Node A                    Node B
┌──────────┐              ┌──────────┐
│ Hash(root)│             │ Hash(root)│
│   abc123  │<── compare ─│   xyz789  │  ← Different!
├────┬─────┤              ├────┬─────┤
│Left│Right│              │Left│Right│
│ h1 │ h2  │              │ h1 │ h3  │  ← Right subtree differs
└────┴─────┘              └────┴─────┘

Only sync the differing subtree → efficient!

Conflict Resolution

При multi-leader и leaderless репликации конфликты неизбежны. Стратегии разрешения:

Last-Write-Wins (LWW)

Node A: Write(x=1, timestamp=100)
Node B: Write(x=2, timestamp=101)

Resolution: x=2 (timestamp 101 > 100)
Problem: data loss! Write from Node A is silently discarded.

Подходит для: Кэши, метрики, данные без конфликтов

Application-Level Merge

Shopping Cart Merge:
Node A: cart = {item1, item2}
Node B: cart = {item1, item3}

Merge: cart = {item1, item2, item3}  (union)

CRDTs (Conflict-free Replicated Data Types)

CRDTs -- структуры данных, которые математически гарантируют сходимость без координации.

CRDT	Описание	Пример
G-Counter	Только растущий счётчик	Подсчёт просмотров
PN-Counter	Растущий/убывающий счётчик	Лайки/дизлайки
G-Set	Только добавление в множество	Список тегов
OR-Set	Добавление и удаление из множества	Корзина покупок
LWW-Register	Последняя запись побеждает	Поле профиля

G-Counter (distributed):
Node A: [3, 0, 0]   // A added 3
Node B: [0, 2, 0]   // B added 2
Node C: [0, 0, 1]   // C added 1

Merge: max per element → [3, 2, 1]
Total: 3 + 2 + 1 = 6

Convergent: any order of merge gives same result ✓

Что говорить на интервью

Framework для выбора модели согласованности

1. Определить тип данных:
   Финансовые → Strong consistency
   Социальные → Eventual / Causal

2. Определить паттерн доступа:
   Read-heavy → Больше реплик, R=1
   Write-heavy → W=1, eventual reads

3. Определить географию:
   Один регион → Strong доступна
   Multi-region → Eventual / Causal

4. Определить допустимое окно:
   0ms → Strong (дорого)
   1-5s → Read-your-writes / Causal
   Минуты → Eventual

Типичные вопросы и ответы

Q: "Как обеспечить, что пользователь видит свой пост после создания?" A: Read-your-writes consistency. Sticky sessions или read from primary после записи.

Q: "Как масштабировать чтение для social feed?" A: Асинхронная репликация + eventual consistency. Read replicas в разных регионах.

Q: "Как реплицировать данные глобально?" A: Multi-leader или leaderless с causal consistency. CRDTs для автоматического разрешения конфликтов.