Введение

Репликация — это хранение копий одних и тех же данных на нескольких узлах. Если шардирование (глава 13) решает проблему объёма — данных слишком много для одного сервера, — то репликация решает три другие фундаментальные проблемы:

1. Отказоустойчивость — если один узел умирает, данные не теряются, а система продолжает работать.
2. Производительность чтения — запросы на чтение распределяются между несколькими репликами.
3. Географическая близость — реплики в разных дата-центрах обслуживают пользователей ближайшего региона с минимальной латенси.

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

                    ┌────────────────┐
         Отказ      │   Node 1 X     │    Данные потеряны?
        ─────▶      │  (единственн)  │  Без репликации — ДА.
                    └────────────────┘

С репликацией:
                    ┌────────────────┐
         Отказ      │    Node 1 X    │  Данные в безопасности!
        ─────▶      │   (primary)    │
                    └────────────────┘
                    ┌────────────────┐  ┌───────────────┐
                    │    Node 2 ✓    │  │    Node 3 ✓   │
                    │   (replica)    │  │   (replica)   │
                    └────────────────┘  └───────────────┘
                     

На практике шардирование и репликация работают вместе: каждый шард реплицируется для отказоустойчивости.

Шардирование + репликация:

  Shard A                Shard B                Shard C
  ┌──────────┐          ┌──────────┐          ┌──────────┐
  │ Primary  │          │ Primary  │          │ Primary  │
  │ (DC-1)   │          │ (DC-2)   │          │ (DC-1)   │
  └────┬─────┘          └────┬─────┘          └────┬─────┘
       │                     │                     │
  ┌────┴─────┐          ┌────┴─────┐          ┌────┴─────┐
  │ Replica  │          │ Replica  │          │ Replica  │
  │ (DC-2)   │          │ (DC-1)   │          │ (DC-2)   │
  └────┬─────┘          └────┬─────┘          └────┬─────┘
       │                     │                     │
  ┌────┴─────┐          ┌────┴─────┐          ┌────┴─────┐
  │ Replica  │          │ Replica  │          │ Replica  │
  │ (DC-3)   │          │ (DC-3)   │          │ (DC-3)   │
  └──────────┘          └──────────┘          └──────────┘

В этой главе мы разберём три фундаментальные модели репликации — single-leader, multi-leader и leaderless, — сравним синхронную и асинхронную репликацию, а также погрузимся в стратегии разрешения конфликтов.

---

1. Single-leader репликация

Single-leader (она же master-slave, primary-replica) — самая распространённая модель репликации. Один узел назначается лидером (primary/master), и все операции записи проходят только через него. Остальные узлы — фолловеры (replicas/slaves) — получают поток изменений от лидера и применяют его к своей копии данных.

Single-leader репликация:

   Клиенты (запись)         Клиенты (чтение)
       │                    │       │       │
       ▼                    ▼       ▼       ▼
  ┌──────────┐        ┌────────┐┌────────┐┌────────┐
  │  Leader  │───────▶│Follower││Follower││Follower│
  │ (primary)│  WAL   │   1    ││   2    ││   3    │
  │  R + W   │ stream │  R     ││  R     ││  R     │
  └──────────┘        └────────┘└────────┘└────────┘
       │
       │  Replication Log (WAL / binlog / oplog)
       ▼
  Каждый фолловер применяет
  те же операции в том же порядке

Как работает

1. Клиент отправляет запись на лидера. Это может быть INSERT, UPDATE, DELETE или любая мутация данных.
2. Лидер записывает изменение в свой локальный WAL (Write-Ahead Log) или аналогичную структуру.
3. Лидер отправляет запись в replication log — поток изменений, доступный фолловерам.
4. Каждый фолловер получает лог и применяет изменения к своей копии данных строго в том же порядке.
5. Чтение может идти с любого узла — лидера или фолловера — в зависимости от требований к согласованности.

Форматы replication log

PostgreSQL использует WAL-based streaming replication. MySQL — row-based binlog (по умолчанию с 8.0). MongoDB — oplog (logical, document-level).

Настройка реплик: полный процесс

Добавление новой реплики к работающему кластеру — не тривиальная задача. Нельзя просто скопировать файлы, потому что данные постоянно меняются.

Добавление реплики:

1. Создать consistent snapshot лидера
   (pg_basebackup, mysqldump --single-transaction, mongodump)

2. Скопировать snapshot на новый узел

3. Реплика подключается к лидеру и запрашивает все изменения
   после позиции snapshot (LSN в PostgreSQL, binlog position в MySQL)

4. Реплика «догоняет» лидера (catching up)

5. Реплика готова обслуживать чтения

   ┌──────────┐  snapshot   ┌──────────┐
   │  Leader  │ ──────────▶ │ New      │
   │          │  + stream   │ Replica  │
   └──────────┘  changes    └──────────┘
       t=0          t=1         t=2
    (snapshot)   (streaming)  (caught up)

Failover: что происходит при отказе лидера

Когда лидер выходит из строя, одна из реплик должна стать новым лидером. Этот процесс называется failover и включает:

1. Обнаружение отказа — обычно через heartbeat/timeout. Если лидер не отвечает N секунд, он считается мёртвым.
2. Выбор нового лидера — выбирается реплика с наиболее актуальными данными (минимальный replication lag).
3. Переконфигурация — клиенты перенаправляются на нового лидера, старые реплики подключаются к новому лидеру.

Failover процесс:

   До:                          После:
   ┌──────────┐                 ┌──────────┐
   │ Leader X │                 │ Old Lead │ (отключён)
   └──────────┘                 └──────────┘
   ┌──────────┐                 ┌──────────┐
   │Replica 1 │  ──────────▶    │ Leader ✓ │  (promoted)
   └──────────┘                 └──────────┘
   ┌──────────┐                 ┌──────────┐
   │Replica 2 │                 │Replica 2 │──▶ follows new leader
   └──────────┘                 └──────────┘

Опасности failover:

• Потеря данных при асинхронной репликации. Если лидер принял записи, но не успел отправить их репликам до отказа — эти записи потеряны. Когда старый лидер возвращается, он может иметь конфликтующие данные.

• Split-brain — ситуация, когда два узла считают себя лидерами. Например, старый лидер вернулся и не знает, что произошёл failover. Оба принимают записи — данные расходятся. Решение: механизм fencing (STONITH — Shoot The Other Node In The Head) — принудительное отключение старого лидера.

• Каскадный отказ — некорректный failover может привести к цепочке проблем. Реальный пример: инцидент GitHub в 2012 году, когда failover MySQL привёл к рассинхронизации auto-increment ID между MySQL и Redis, что вызвало утечку приватных данных в чужие репозитории.

# Пример: простой механизм обнаружения отказа лидера
import time
import threading

class FailureDetector:
    def __init__(self, heartbeat_interval=1.0, timeout=5.0):
        self.heartbeat_interval = heartbeat_interval
        self.timeout = timeout
        self.last_heartbeat = {}  # node_id -> timestamp
        self.lock = threading.Lock()

    def receive_heartbeat(self, node_id: str):
        with self.lock:
            self.last_heartbeat[node_id] = time.time()

    def is_alive(self, node_id: str) -> bool:
        with self.lock:
            last = self.last_heartbeat.get(node_id, 0)
            return (time.time() - last) < self.timeout

    def get_dead_nodes(self) -> list[str]:
        with self.lock:
            now = time.time()
            return [
                node_id for node_id, last in self.last_heartbeat.items()
                if (now - last) >= self.timeout
            ]

Read-after-write consistency

При single-leader репликации с чтением из реплик возникает проблема: пользователь записал данные через лидера, но при следующем чтении попал на реплику, которая ещё не получила это обновление.

Проблема stale read:

   Клиент: "Обновить имя на 'Bob'"
       │
       ▼
   ┌──────────┐  (ещё не доставлено)  ┌───────────┐
   │  Leader  │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─▶│ Replica   │
   │ name=Bob │                       │ name=Alice│  ← stale!
   └──────────┘                       └───────────┘
                                           ▲
   Клиент: "Прочитать имя"                 │
       │───────────────────────────────────┘
       ▼
   Ответ: "Alice"  ← Пользователь в шоке!

Решения:

# Стратегия read-after-write: чтение с лидера после записи
class ReadRouter:
    def __init__(self, leader, replicas):
        self.leader = leader
        self.replicas = replicas
        self.user_last_write = {}  # user_id -> timestamp

    def route_read(self, user_id: str, query: str):
        last_write = self.user_last_write.get(user_id, 0)

        # Если пользователь писал менее 10 секунд назад — читаем с лидера
        if time.time() - last_write < 10:
            return self.leader.execute(query)

        # Иначе — читаем с ближайшей реплики
        replica = self.select_replica(user_id)
        return replica.execute(query)

    def route_write(self, user_id: str, query: str):
        self.user_last_write[user_id] = time.time()
        return self.leader.execute(query)

    def select_replica(self, user_id: str):
        # Sticky session: один и тот же пользователь
        # всегда попадает на одну реплику (monotonic reads)
        idx = hash(user_id) % len(self.replicas)
        return self.replicas[idx]

Реальные реализации

---

2. Multi-leader репликация

В multi-leader (она же master-master, active-active) конфигурации запись принимается несколькими узлами одновременно. Каждый лидер одновременно является и фолловером для других лидеров.

Multi-leader репликация:

   ┌──────────┐         ┌──────────┐         ┌──────────┐
   │ Leader 1 │◀───────▶│ Leader 2 │◀───────▶│ Leader 3 │
   │ (DC-1)   │  async  │ (DC-2)   │  async  │ (DC-3)   │
   │  R + W   │  replic │  R + W   │  replic │  R + W   │
   └────┬─────┘         └────┬─────┘         └────┬─────┘
        │                    │                    │
   ┌────┴─────┐         ┌────┴─────┐         ┌────┴─────┐
   │ Follower │         │ Follower │         │ Follower │
   │ (DC-1)   │         │ (DC-2)   │         │ (DC-3)   │
   └──────────┘         └──────────┘         └──────────┘

   Каждый DC принимает записи локально → минимальная латенси.
   Конфликты разрешаются асинхронно.

Когда использовать multi-leader

Основные use cases:

1. Мульти-дата-центр развёртывание. Каждый ДЦ имеет своего лидера. Пользователи пишут в ближайший ДЦ с минимальной латенси, а данные реплицируются между ДЦ асинхронно.

2. Оффлайн-клиенты. Каждое устройство — это фактически «лидер», который принимает записи оффлайн, а потом синхронизируется. Примеры: Google Calendar, Apple Notes, Notion offline mode.

3. Collaborative editing. Несколько пользователей одновременно редактируют документ. Каждый клиент принимает локальные изменения и асинхронно синхронизируется (Google Docs, Figma).

Сравнение single-leader vs multi-leader при мульти-DC:

Single-leader (write только в DC-1):

   Пользователь (DC-3)        Пользователь (DC-1)
        │                          │
        │ ~~~ 200ms RTT ~~~        │  < 5ms
        ▼                          ▼
   ┌──────────┐              ┌──────────┐
   │ Leader   │              │ Leader   │
   │ (DC-1)   │              │ (DC-1)   │
   └──────────┘              └──────────┘

Multi-leader (write в любой DC):

   Пользователь (DC-3)        Пользователь (DC-1)
        │                          │
        │  < 5ms                   │  < 5ms
        ▼                          ▼
   ┌──────────┐              ┌──────────┐
   │ Leader   │◀────────────▶│ Leader   │
   │ (DC-3)   │   async      │ (DC-1)   │
   └──────────┘              └──────────┘

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

Способ, которым лидеры обмениваются изменениями, определяет топологию репликации.

Топологии multi-leader репликации:

1. Circular (кольцо):         2. Star (звезда):          3. All-to-all:

   ┌───┐                        ┌───┐                     ┌───┐
   │ A │───▶┌───┐               │ B │                     │ A │◀──────▶┌───┐
   └───┘    │ B │               └───┘                     └───┘        │ B │
     ▲      └─┬─┘                 │                         ▲  ╲       └───┘
     │        ▼                   ▼                         │   ╲        ▲
   ┌───┐    ┌───┐         ┌───┐◀────▶┌───┐               ┌───┐   ╲       │
   │ D │◀───│ C │         │ A │  Hub │ C │               │ C │◀─╌────────┘
   └───┘    └───┘         └───┘      └───┘               └───┘
                                  │
   Один отказ →                   ▼                      Самая устойчивая,
   разрыв цепи.                 ┌───┐                    но сложнее всего
                                │ D │                    избежать дубликатов.
                                └───┘
                            Hub — single
                            point of failure

All-to-all — наиболее устойчивая топология, но требует решения проблемы causality: изменения могут приходить не в том порядке, в котором были сделаны.

Проблема causality в all-to-all:

   Leader A: INSERT user (id=1, name='Alice')  ─────────▶  Leader C
   Leader B: UPDATE user SET name='Bob' WHERE id=1  ────▶  Leader C

   Если UPDATE приходит в C раньше INSERT — ошибка!

   Решение: version vectors, Lamport timestamps, или
   causal ordering через dependency tracking.

Главная проблема multi-leader: конфликты записи

Когда два лидера принимают конкурирующие записи одновременно, возникает write conflict.

Write conflict:

   Пользователь 1 (DC-1):                Пользователь 2 (DC-2):
   UPDATE page SET title='A'              UPDATE page SET title='B'
        │                                      │
        ▼                                      ▼
   ┌──────────┐                           ┌──────────┐
   │ Leader 1 │                           │ Leader 2 │
   │ title='A'│───── conflict! ──────────▶│ title='B'│
   │          │◀─── conflict! ────────────│          │
   └──────────┘                           └──────────┘

   Оба лидера успешно приняли запись (нет ошибки для клиента).
   Но данные разошлись. Что делать?

Стратегии разрешения конфликтов мы подробно рассмотрим в разделе 14.5.

Реальные реализации multi-leader

---

3. Leaderless репликация (Dynamo-style)

В leaderless (бeзлидерной) модели лидера нет вообще. Клиент отправляет запись напрямую нескольким репликам одновременно (или через координатор, который не является лидером). Чтение тоже идёт с нескольких реплик параллельно, и клиент выбирает наиболее актуальный ответ.

Эту модель популяризовала Amazon в Dynamo paper (2007), поэтому её часто называют Dynamo-style.

Leaderless репликация:

   Запись (W=2 из N=3):                Чтение (R=2 из N=3):

   Клиент                              Клиент
     │                                   │
     ├────▶ Node 1: OK ✓                 ├────▶ Node 1: v=42 (stale)
     ├────▶ Node 2: OK ✓                 ├────▶ Node 2: v=43 (fresh) ← выбираем
     └────▶ Node 3: timeout X            └────▶ Node 3: timeout X
            (2 из 3 — достаточно)               (2 из 3 — достаточно)

   W + R > N → гарантия, что хотя бы
   одна реплика вернёт актуальные данные

Кворумы: W, R и N

Ключевая идея leaderless-систем — кворумы (quorums).

• N — общее число реплик
• W — число реплик, которые должны подтвердить запись (write quorum)
• R — число реплик, с которых читается ответ (read quorum)

Правило: если W + R > N, то чтение гарантированно увидит последнюю запись (при условии отсутствия concurrent writes).

Варианты кворумов (N=3):

   W=2, R=2 (стандартный):
   ┌───────┐  ┌───────┐  ┌───────┐
   │ Node1 │  │ Node2 │  │ Node3 │
   │  W ✓  │  │  W ✓  │  │       │   Write OK (2/3)
   │  R ✓  │  │       │  │  R ✓  │   Read OK (2/3)
   └───────┘  └───────┘  └───────┘
   Пересечение: Node1 — гарантированно видим свежие данные.

   W=1, R=3 (быстрая запись, медленное чтение):
   ┌───────┐  ┌───────┐  ┌───────┐
   │ Node1 │  │ Node2 │  │ Node3 │
   │  W ✓  │  │       │  │       │   Write OK (1/3)
   │  R ✓  │  │  R ✓  │  │  R ✓  │   Read OK (3/3)
   └───────┘  └───────┘  └───────┘
   Быстрая запись, но чтение всегда с трёх нод.

   W=3, R=1 (медленная запись, быстрое чтение):
   ┌───────┐  ┌───────┐  ┌───────┐
   │ Node1 │  │ Node2 │  │ Node3 │
   │  W ✓  │  │  W ✓  │  │  W ✓  │   Write OK (3/3)
   │  R ✓  │  │       │  │       │   Read OK (1/3)
   └───────┘  └───────┘  └───────┘
   Любая нода гарантированно имеет свежие данные.

   W=1, R=1 (быстро, но нет гарантий):
   W + R = 2 ≤ N=3 → возможны stale reads.
   Допустимо для некритичных данных (счётчики просмотров).

Sloppy Quorum и Hinted Handoff

Что происходит, если нужные узлы недоступны? Строгий кворум вернёт ошибку. Sloppy quorum позволяет записать данные на «чужие» узлы, которые не являются штатными владельцами ключа.

Sloppy Quorum:

   Штатные владельцы ключа K: [Node1, Node2, Node3]

   Node3 недоступен. Запись (W=2):

   Строгий кворум:
   Node1: OK ✓
   Node2: OK ✓
   Node3: X (но W=2 достигнут — ОК)

   Sloppy quorum (Node3 недоступен полностью, Node1 тоже):
   Node2: OK ✓
   Node4: OK ✓  ← Node4 не штатный владелец K!
                   Он хранит запись временно (hint).

   Когда Node3 возвращается:
   Node4 ──── hinted handoff ────▶ Node3
   (передаёт данные законному владельцу и удаляет у себя)

Sloppy quorum повышает доступность записи, но ослабляет гарантии чтения: даже при W + R > N может быть stale read, потому что данные записаны на узел за пределами штатного набора.

Anti-entropy и Read Repair

В leaderless-системах реплики могут рассинхронизироваться. Два механизма для восстановления:

Read Repair — при чтении с нескольких реплик клиент замечает stale данные и отправляет обновление:

Read Repair:

   Клиент читает (R=2):
   Node1: version=5, value='Alice'  ← stale
   Node2: version=7, value='Bob'    ← fresh

   Клиент:
   1. Возвращает 'Bob' (version=7) как результат
   2. Отправляет Node1: "обновись до version=7, value='Bob'"

   Node1 обновляется. Данные снова синхронны.

Anti-entropy process — фоновый процесс, который постоянно сравнивает данные между репликами и устраняет расхождения. Использует Merkle trees для эффективного поиска различий.

Merkle Tree для anti-entropy:

   Node A:                      Node B:
   Root: hash=abc123            Root: hash=abc456  ← корни разные!
    ├── Left: hash=def789        ├── Left: hash=def789  ← совпадает
    │   ├── Key1: hash=...       │   ├── Key1: hash=...
    │   └── Key2: hash=...       │   └── Key2: hash=...
    └── Right: hash=ghi012       └── Right: hash=ghi999  ← разные!
        ├── Key3: hash=...           ├── Key3: hash=...  ← совпадает
        └── Key4: hash=jkl345        └── Key4: hash=jkl678  ← РАЗНЫЕ!

   Вместо сравнения всех ключей (миллионы),
   дерево позволяет найти расхождения за O(log N) шагов.

Реальные реализации leaderless

---

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

Ключевой выбор при проектировании системы репликации — когда операция записи считается завершённой: когда лидер записал к себе, или когда подтвердили реплики?

Синхронная репликация:

   Клиент          Leader          Replica 1        Replica 2
     │── write ───▶│                   │                │
     │             │── replicate ─────▶│                │
     │             │── replicate ──────────────────────▶│
     │             │◀── ACK ───────────│                │
     │             │◀── ACK ────────────────────────────│
     │◀── OK ──────│                   │                │
     │                                                  │
   Клиент ждёт подтверждения от ВСЕХ реплик.
   Гарантия: данные точно на всех узлах.
   Цена: латенси = max(latency до каждой реплики).

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

   Клиент          Leader          Replica 1        Replica 2
     │── write ───▶│                   │                │
     │◀── OK ──────│                   │                │
     │             │── replicate ─────▶│                │
     │             │── replicate ──────────────────────▶│
     │             │                   │                │
   Клиент получает OK сразу после записи на лидере.
   Реплики получат данные «когда-нибудь».
   Гарантия: никакой. Данные могут быть потеряны при отказе лидера.
   Выигрыш: минимальная латенси записи.

Сравнение

Полусинхронная репликация (semi-synchronous)

Компромиссный подход: одна реплика синхронная, остальные — асинхронные.

Semi-synchronous (PostgreSQL synchronous_standby_names):

   Клиент          Leader          Sync Replica     Async Replica
     │── write ───▶│                   │                │
     │             │── replicate ─────▶│                │
     │             │── replicate ──────────────────────▶│
     │             │◀── ACK ───────────│                │
     │◀── OK ──────│                   │                │
     │             │                   │                │
   Ждём ACK только от sync-реплики.
   Если sync-реплика упадёт → одна из async промоутится в sync.

   Гарантия: данные как минимум на 2 узлах (leader + 1 sync replica).
   Баланс: разумная латенси + разумная durability.

Replication Lag и его последствия

При асинхронной репликации между лидером и репликой всегда есть задержка (replication lag). В нормальных условиях это миллисекунды, но при пиковой нагрузке или проблемах сети — секунды или даже минуты.

Аномалии при replication lag:

1. Stale reads (чтение устаревших данных)
   → Решение: read-after-write consistency

2. Moving backward in time
   Пользователь читает с Replica A (lag=1s): видит комментарий
   Следующий запрос попадает на Replica B (lag=5s): комментарий исчез!
   → Решение: monotonic reads (sticky sessions)

3. Causality violation
   Пользователь 1: "Какой сегодня курс доллара?"
   Пользователь 2: "85 рублей"  (ответ на вопрос)

   Реплика может показать ответ раньше вопроса!
   → Решение: consistent prefix reads

# Мониторинг replication lag в PostgreSQL
# Запрос для проверки lag на реплике:
REPLICATION_LAG_QUERY = """
SELECT
    client_addr,
    state,
    sent_lsn,
    write_lsn,
    flush_lsn,
    replay_lsn,
    pg_wal_lsn_diff(sent_lsn, replay_lsn) AS replay_lag_bytes,
    reply_time,
    now() - reply_time AS reply_lag
FROM pg_stat_replication;
"""

# Мониторинг через Prometheus metric
# pg_replication_lag_seconds — ключевая метрика для alerting
# Alert: если lag > 30 секунд — warning, > 5 минут — critical

Цепочка репликации (cascading replication)

Для уменьшения нагрузки на лидера реплики могут получать данные не от лидера напрямую, а от других реплик:

Cascading replication:

   ┌──────────┐
   │  Leader  │──────────▶ Replica 1 ──────────▶ Replica 3
   │          │                                      │
   │          │──────────▶ Replica 2             Replica 5
   └──────────┘                │
                           Replica 4

   Лидер отдаёт лог только двум репликам вместо пяти.
   Недостаток: увеличивается replication lag для «дальних» реплик.

---

5. Стратегии разрешения конфликтов (Conflict Resolution)

Конфликты неизбежны в multi-leader и leaderless системах. Два (или более) узла одновременно модифицируют одни и те же данные, и после синхронизации результаты расходятся.

Типы конфликтов

Типы конфликтов:

1. Write-write conflict (самый частый):
   Узел A: SET x = 'foo'
   Узел B: SET x = 'bar'
   → Какое значение правильное?

2. Delete-update conflict:
   Узел A: DELETE x
   Узел B: UPDATE x SET value = 'new'
   → Что делать: удалить или обновить?

3. Uniqueness conflict:
   Узел A: INSERT user (email='alice@example.com')
   Узел B: INSERT user (email='alice@example.com')  ← другой пользователь!
   → Нарушен unique constraint.

4. Causality conflict:
   Узел A: INSERT INTO comments (parent_id=42, text='reply')
   Узел B: DELETE FROM comments WHERE id=42
   → Ответ на удалённый комментарий.

Стратегии разрешения

1. Last Write Wins (LWW)

Самая простая стратегия: побеждает запись с наибольшим timestamp.

Last Write Wins:

   Узел A: SET x = 'foo'  (timestamp=100)
   Узел B: SET x = 'bar'  (timestamp=101)

   Результат: x = 'bar' (timestamp 101 > 100)

   Проблемы:
   - Часы на разных узлах могут расходиться (clock skew)
   - Потеря данных: запись 'foo' молча отбрасывается
   - Concurrent writes: если оба timestamp одинаковы, выбор произвольный

LWW используется в Cassandra (по умолчанию) и DynamoDB (для скалярных значений). Подходит, когда потеря одной из concurrent записей допустима (например, обновление sensor data, last-seen timestamp).

# LWW реализация с Lamport timestamps
class LWWRegister:
    def __init__(self):
        self.value = None
        self.timestamp = 0
        self.node_id = None

    def write(self, value, timestamp, node_id):
        if timestamp > self.timestamp or \
           (timestamp == self.timestamp and node_id > self.node_id):
            self.value = value
            self.timestamp = timestamp
            self.node_id = node_id

    def merge(self, other: 'LWWRegister'):
        """Merge two replicas — larger timestamp wins."""
        if other.timestamp > self.timestamp or \
           (other.timestamp == self.timestamp and other.node_id > self.node_id):
            self.value = other.value
            self.timestamp = other.timestamp
            self.node_id = other.node_id

2. Multi-Value (Siblings)

Вместо выбора одного победителя система сохраняет все конфликтующие версии и отдаёт их клиенту для разрешения.

Multi-value (Riak siblings):

   Узел A: SET cart = ['яблоко', 'молоко']     (vclock: {A:1})
   Узел B: SET cart = ['яблоко', 'хлеб']       (vclock: {B:1})

   При чтении клиент получает оба значения (siblings):
   [
     {value: ['яблоко', 'молоко'], vclock: {A:1}},
     {value: ['яблоко', 'хлеб'],   vclock: {B:1}}
   ]

   Клиент разрешает конфликт:
   → Merged: ['яблоко', 'молоко', 'хлеб']
   → Записывает обратно с объединённым vclock: {A:1, B:1}

Используется в Riak и CouchDB (revision tree).

3. CRDTs (Conflict-free Replicated Data Types)

CRDTs — структуры данных, математически гарантирующие сходимость при любом порядке применения операций. Подробнее о них рассказывалось в главе 12.

Пример: G-Counter (grow-only counter)

   Node A: increment()  → state = {A: 1, B: 0, C: 0}
   Node B: increment()  → state = {A: 0, B: 1, C: 0}
   Node B: increment()  → state = {A: 0, B: 2, C: 0}

   Merge: max по каждому узлу:
   {A: max(1,0,0), B: max(0,2,0), C: max(0,0,0)} = {A:1, B:2, C:0}

   Value = sum = 1 + 2 + 0 = 3 ✓

   Порядок мержей не важен — результат всегда одинаковый!

Основные типы CRDT:

# PN-Counter CRDT реализация
class PNCounter:
    """Positive-Negative Counter: supports increment and decrement."""

    def __init__(self, node_id: str):
        self.node_id = node_id
        self.positive = {}  # node_id -> count
        self.negative = {}  # node_id -> count

    def increment(self):
        self.positive[self.node_id] = self.positive.get(self.node_id, 0) + 1

    def decrement(self):
        self.negative[self.node_id] = self.negative.get(self.node_id, 0) + 1

    def value(self) -> int:
        return sum(self.positive.values()) - sum(self.negative.values())

    def merge(self, other: 'PNCounter'):
        """Merge is commutative, associative, and idempotent."""
        for node_id, count in other.positive.items():
            self.positive[node_id] = max(
                self.positive.get(node_id, 0), count
            )
        for node_id, count in other.negative.items():
            self.negative[node_id] = max(
                self.negative.get(node_id, 0), count
            )

4. Application-level resolution

Для сложных бизнес-правил конфликты разрешаются на уровне приложения.

Application-level conflict resolution:

   Пример: бронирование отелей

   DC-EU: Забронировать комнату 101 для клиента Alice
   DC-US: Забронировать комнату 101 для клиента Bob

   Автоматическое разрешение (LWW) неприемлемо!
   Нельзя молча отменить бронирование.

   Application-level:
   1. Обнаружить конфликт (обе записи бронируют одну комнату)
   2. Уведомить оператора или обоих клиентов
   3. Предложить альтернативу (комната 102)
   4. Применить бизнес-правило (VIP-клиент имеет приоритет)

Сравнение стратегий

---

6. Практические паттерны и рекомендации

Выбор модели репликации

Дерево принятия решений:

   Запись только в одном регионе?
   ├── ДА → Single-leader
   │        ├── Нужна strong consistency? → Synchronous replication
   │        └── Допустим eventual? → Async + read-after-write
   └── НЕТ → Запись в нескольких регионах
             ├── Конфликты маловероятны? → Multi-leader
             │   └── Какой тип данных?
             │       ├── Простые (счётчики, флаги) → CRDTs
             │       └── Сложные (документы) → App-level resolution
             └── Конфликты частые? → Leaderless + кворумы
                 └── Нужна тюнинг consistency? → Cassandra/Riak

Типичные конфигурации в production

Мониторинг репликации

Ключевые метрики:

Метрики репликации:

1. Replication Lag (секунды или байты)
   - PostgreSQL: pg_stat_replication, replay_lag
   - MySQL: Seconds_Behind_Master
   - Cassandra: не применимо (leaderless)
   Alert: > 30s warning, > 5m critical

2. Replication Throughput (MB/s)
   - Объём данных, передаваемых репликам в секунду
   Alert: падение > 50% от baseline

3. Replication Connection Status
   - Реплика подключена к лидеру?
   Alert: disconnected > 10s

4. Write Conflicts (для multi-leader)
   - Количество конфликтов в единицу времени
   Alert: рост > 10x от baseline

5. Anti-entropy Repair Rate (для leaderless)
   - Процент ключей, требующих ремонта
   Alert: > 1% ключей inconsistent

---

7. Сравнение моделей репликации

Спектр trade-offs:

   Strong consistency                              High availability
   Low write latency (single DC)                   Low write latency (global)
   Simple                                          Complex

   ◀────────────────────────────────────────────────────────────────▶
   │                    │                          │                │
   Single-leader     Single-leader              Multi-leader    Leaderless
   (sync)            (async)                                    (W=1)

---

8. Вопросы для самопроверки

1. В чём принципиальная разница между single-leader и multi-leader репликацией? Когда каждая из них предпочтительнее?

2. Объясните формулу W + R > N. Почему она гарантирует, что клиент увидит свежие данные? При каких условиях эта гарантия нарушается?

3. Что такое sloppy quorum? Почему он повышает доступность, но ослабляет гарантии согласованности?

4. Опишите три аномалии, которые возникают при replication lag: stale reads, moving backward in time, causality violation. Как каждая из них решается?

5. Почему Last Write Wins (LWW) может приводить к потере данных? В каких сценариях это допустимо?

6. Чем CRDTs лучше application-level conflict resolution? В каких случаях CRDTs недостаточно?

7. Что такое split-brain в контексте single-leader репликации? Как fencing (STONITH) решает эту проблему?

8. Объясните разницу между read repair и anti-entropy. Когда какой механизм более эффективен?

9. Вы проектируете систему бронирования отелей с дата-центрами в Европе и США. Какую модель репликации выберете и почему? Как будете разрешать конфликты?

10. PostgreSQL использует WAL-based streaming replication, а MongoDB — oplog. В чём концептуальная разница между этими подходами? Какие trade-offs у каждого?

---

9. Дополнительные ресурсы

Papers

• Dynamo: Amazon's Highly Available Key-value Store (DeCandia et al., 2007) — основополагающая работа по leaderless репликации, кворумам и vector clocks.
• Conflict-free Replicated Data Types (Shapiro et al., 2011) — формализация CRDTs и доказательство сходимости.
• Designing Data-Intensive Applications, Chapter 5 (Martin Kleppmann, 2017) — лучшее объяснение репликации в литературе.
• Chain Replication for Supporting High Throughput and Availability (van Renesse, Schneider, 2004) — альтернативная модель репликации с цепочной топологией.

Блоги и документация

• PostgreSQL Replication Documentation — streaming replication, logical replication, synchronous_standby_names.
• Cassandra Architecture Documentation — tunable consistency, hinted handoff, read repair.
• Jepsen.io (Kyle Kingsbury) — тестирование гарантий согласованности реальных распределённых систем. Обязательно к прочтению.
• CockroachDB Blog: Living without Atomic Clocks — как CockroachDB реализует serializable consistency без атомных часов (в отличие от Spanner).

Talks

• "Transactions: myths, surprises, and opportunities" — Martin Kleppmann (Strange Loop 2015) — развенчание мифов о транзакциях и репликации.
• "CRDTs and the Quest for Distributed Consistency" — Martin Kleppmann (QCon London 2018) — доступное введение в CRDTs.
• "Turning the database inside-out" — Martin Kleppmann (Strange Loop 2014) — новый взгляд на репликацию через event sourcing и change data capture.