Уровень: Middle / Senior разработчик Предварительные знания: основы баз данных, распределённые системы, хэш-функции Время изучения: 2–3 часа Смотрите также: Глава 4 (типы баз данных), Глава 12 (согласованность), Глава 13 (шардирование), Глава 14 (репликация)

Введение

Реляционные базы данных — мощный инструмент, но у них есть фундаментальное ограничение: вертикальное масштабирование упирается в потолок. Когда Amazon столкнулся с тем, что их корзины покупок обслуживались БД с latency в сотни миллисекунд при праздничных пиках, они поняли: нужна система, которая гарантированно отвечает за миллисекунды при любой нагрузке.

В 2007 году Amazon опубликовал легендарную статью "Dynamo: Amazon's Highly Available Key-Value Store" — она определила архитектуру целого класса систем: DynamoDB, Cassandra, Riak, Voldemort.

Когда Key-Value Store — правильный выбор

Полная классификация типов баз данных (реляционные, документные, колоночные, графовые, KV) — в Главе 4: Хранение данных: типы баз данных.

Key-Value Store — это осознанный отказ от гибкости SQL ради трёх вещей: предсказуемая latency, горизонтальная масштабируемость и высокая доступность.

1. Требования

1.1 Функциональные требования

Базовый API:

put(key, value)          → записать или обновить
get(key)                 → прочитать значение
delete(key)              → удалить

Расширенный API (DynamoDB-стиль):

put(key, value, condition)           → conditional write (запись если version == X)
get(key, consistency_level)          → eventually consistent | strongly consistent
batch_get([key1, key2, ...])         → до 100 ключей за раз
batch_write([items])                 → до 25 записей за раз
query(partition_key, sort_key_range) → диапазонный запрос по sort key
scan(filter)                         → полный скан таблицы (дорого!)

Ограничения:

• Размер ключа: до 2048 байт
• Размер значения: до 400 КБ (DynamoDB) или до нескольких МБ (другие системы)
• TTL: автоматическое удаление элементов по истечении срока

1.2 Нефункциональные требования

Формальное определение доступности (девятки), latency percentiles (P99) и fault tolerance — в Главе 2: Ключевые характеристики распределённых систем.

2. Оценка масштаба

Рассчитаем для системы уровня DynamoDB:

Операций чтения:           10 000 000 ops/sec (пик)
Операций записи:           2 000 000 ops/sec (пик)
Средний размер элемента:   1 КБ
Суммарный объём данных:    100 ТБ (и растёт)
Количество таблиц:         100 000+
Количество узлов:          10 000+

Write throughput:          2M × 1 КБ = 2 ГБ/сек
Хранилище за год:          2 ГБ/сек × 86400 × 365 ≈ 63 ПБ (до компакции и TTL)

Эти числа диктуют:

• Данные обязаны быть распределены по тысячам узлов → нужно consistent hashing
• Каждый узел хранит только свой фрагмент → нужно партиционирование
• Отказ узла не должен терять данные → нужна репликация
• Запись не должна блокироваться → нужна eventual consistency как default

Методика back-of-envelope оценок — в Главе 1: Введение в проектирование систем.

3. Высокоуровневая архитектура

                    Client SDK / API
                            │
                            ▼
    ┌────────────────────────────────────────────────┐
    │                 Request Router                 │
    │    (определяет, какой узел отвечает за ключ)   │
    └─────────────┬────────────────────┬─────────────┘
                  │                    │
           ┌──────▼──────┐       ┌─────▼───────┐
           │ Coordinator │       │ Coordinator │     ... (N координаторов)
           │   Node A    │       │   Node B    │
           └──────┬──────┘       └─────┬───────┘
                  │                    │
    ┌─────────────▼───────────-────────▼──────────────┐
    │        Storage Ring (Consistent Hashing)        │
    │                                                 │
    │   ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐   │
    │   │Node1│  │Node2│  │Node3│  │Node4│  │Node5│   │
    │   │Part │  │Part │  │Part │  │Part │  │Part │   │
    │   │A,F  │  │B,G  │  │C,A' │  │D,B' │  │E,C' │   │
    │   └─────┘  └─────┘  └─────┘  └─────┘  └─────┘   │
    │        (каждый узел хранит свои партиции        │
    │               + реплики соседних)               │
    └─────────────────────────────────────────────────┘

Coordinator pattern: клиент обращается к любому узлу — тот становится координатором запроса. Координатор:

1. Определяет, на каких узлах лежит ключ (через consistent hashing)
2. Отправляет запрос на эти узлы параллельно
3. Собирает ответы, разрешает конфликты
4. Возвращает результат клиенту

Паттерны балансировки запросов между узлами — в Главе 8: Балансировка нагрузки.

4. Consistent Hashing

4.1 Почему hash mod N ломается

Наивный подход: node = hash(key) % N, где N — количество узлов.

3 узла: hash("user:123") % 3 = 1  → Node 1
        hash("user:456") % 3 = 0  → Node 0
        hash("user:789") % 3 = 2  → Node 2

Добавили Node 3 (теперь N=4):
        hash("user:123") % 4 = 3  → Node 3  ← ПЕРЕЕХАЛ!
        hash("user:456") % 4 = 0  → Node 0  ← остался
        hash("user:789") % 4 = 1  → Node 1  ← ПЕРЕЕХАЛ!

При добавлении одного узла ~75% ключей переезжают. При миллиардах ключей это катастрофа.

4.2 Хэш-кольцо

Consistent Hashing помещает и узлы, и ключи на одно хэш-кольцо (0 ... 2^32-1). Ключ обслуживается первым узлом по часовой стрелке от его позиции.

                        0
                   ╭────┬────╮
                 /      │      \
               /   Node A(30)   \
              │                  │
         270──┤    HASH RING     ├──90
              │                  │
               \   Node C(200)  /
                 \      │      /
                   ╰────┴────╯
                       180
                   Node B(150)

Key "user:123" → hash = 80  → ближайший по часовой: Node A (90)? Нет, 
                                если A=30, B=150, C=200:
                                80 > 30, 80 < 150 → идёт на Node B

При добавлении Node D (100):
  Ключи между 30 и 100 переезжают с Node B на Node D
  Остальные ключи НЕ ЗАТРОНУТЫ (только ~K/N ключей перемещается)

4.3 Виртуальные узлы (vnodes)

Проблема: при малом числе узлов данные распределяются неравномерно. Решение — каждый физический узел создаёт 150–256 виртуальных узлов на кольце.

import hashlib
from bisect import bisect_right

class ConsistentHashRing:
    def __init__(self, nodes: list[str], vnodes_per_node: int = 150):
        self.ring: dict[int, str] = {}  # position → physical_node
        self.sorted_positions: list[int] = []
        self.vnodes_per_node = vnodes_per_node

        for node in nodes:
            self.add_node(node)

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16) % (2**32)

    def add_node(self, node: str):
        for i in range(self.vnodes_per_node):
            vnode_key = f"{node}:vnode{i}"
            position = self._hash(vnode_key)
            self.ring[position] = node
        self.sorted_positions = sorted(self.ring.keys())

    def remove_node(self, node: str):
        positions_to_remove = [
            pos for pos, n in self.ring.items() if n == node
        ]
        for pos in positions_to_remove:
            del self.ring[pos]
        self.sorted_positions = sorted(self.ring.keys())

    def get_node(self, key: str) -> str:
        if not self.ring:
            raise Exception("Ring is empty")
        h = self._hash(key)
        idx = bisect_right(self.sorted_positions, h)
        if idx == len(self.sorted_positions):
            idx = 0  # wrap around
        return self.ring[self.sorted_positions[idx]]

    def get_preference_list(self, key: str, n: int = 3) -> list[str]:
        """Возвращает N уникальных физических узлов для репликации."""
        if not self.ring:
            return []
        h = self._hash(key)
        idx = bisect_right(self.sorted_positions, h)
        nodes = []
        seen = set()
        for i in range(len(self.sorted_positions)):
            pos = self.sorted_positions[(idx + i) % len(self.sorted_positions)]
            node = self.ring[pos]
            if node not in seen:
                nodes.append(node)
                seen.add(node)
            if len(nodes) == n:
                break
        return nodes

Consistent hashing — ключевая концепция шардирования. Альтернативные стратегии (range-based, directory-based) и их trade-offs — в Главе 13: Шардирование и партиционирование.

5. Партиционирование данных

5.1 Partition Key и Sort Key

DynamoDB использует двухуровневый ключ:

Partition Key (PK):  определяет, на какой узел попадёт запись
Sort Key (SK):       опционален, определяет порядок внутри партиции

Примеры:
┌────────────────────────────────────────────────────┐
│ PK (user_id)    │ SK (order_date)  │ value         │
├─────────────────┼──────────────────┼───────────────┤
│ user:alice      │ 2024-01-15       │ {order: ...}  │
│ user:alice      │ 2024-02-20       │ {order: ...}  │
│ user:alice      │ 2024-03-10       │ {order: ...}  │
│ user:bob        │ 2024-01-20       │ {order: ...}  │
└─────────────────┴──────────────────┴───────────────┘

get(PK="user:alice")                    → все заказы Alice
get(PK="user:alice", SK > "2024-02")    → заказы Alice с февраля

Partition Key хэшируется для распределения по кольцу. Sort Key хранится отсортированным внутри одной партиции — это позволяет делать range queries.

5.2 Hot Partitions и Write Sharding

Проблема: если один ключ получает непропорционально много запросов (например, счётчик просмотров популярного поста), один узел перегружается.

# Плохо: один горячий ключ
put("post:viral_video:views", count)  # весь трафик → один узел

# Хорошо: write sharding — распределяем по N суб-ключам
import random

def increment_counter(key: str, shards: int = 10):
    shard_id = random.randint(0, shards - 1)
    shard_key = f"{key}:shard:{shard_id}"
    dynamodb.update_item(
        Key={'pk': shard_key},
        UpdateExpression='ADD #count :inc',
        ExpressionAttributeNames={'#count': 'count'},
        ExpressionAttributeValues={':inc': 1}
    )

def get_counter(key: str, shards: int = 10) -> int:
    total = 0
    for i in range(shards):
        item = dynamodb.get_item(Key={'pk': f"{key}:shard:{i}"})
        total += item.get('count', 0)
    return total

Scatter-gather на чтение (10 запросов) — это цена за равномерное распределение записи.

6. Репликация

6.1 Replication Factor и Preference List

Каждый ключ реплицируется на N узлов (обычно N=3). Preference list — это упорядоченный список узлов, отвечающих за ключ.

Хэш-кольцо с 5 узлами, N=3:

                    Node A
                   ╱      ╲
            Node E         Node B
                   ╲      ╱
                    Node D ── Node C

Ключ K хэшируется на позицию между A и B.
Preference list для K: [B, C, D]
  B = primary replica
  C = secondary replica
  D = tertiary replica

6.2 Sloppy Quorum и Hinted Handoff

В классическом кворуме если один из N узлов недоступен — запись блокируется. Sloppy quorum решает это:

Нормальная ситуация:
  Ключ K → запись на [B, C, D] (все 3 доступны)

Node C упал:
  Strict quorum:  запись на [B, D], ждём пока C вернётся — БЛОКИРОВКА
  Sloppy quorum:  запись на [B, D, E]  ← E — «заместитель» C
                  E хранит подсказку (hint): "это данные для C"

C вернулся:
  E отправляет данные обратно на C (hinted handoff)
  E удаляет свою копию

Sloppy quorum повышает доступность ценой временной потери строгой согласованности. Это ключевое решение Dynamo: availability > consistency.

Подробнее о CAP-теореме, моделях согласованности (eventual, strong, causal) и trade-offs — в Главе 12: Согласованность в распределённых системах. Стратегии репликации (master-replica, multi-master, leaderless) — в Главе 14: Репликация данных.

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

7.1 Quorum: R + W > N

KV-store предлагает tunable consistency через параметры:

N = количество реплик (обычно 3)
W = количество подтверждений при записи
R = количество ответов при чтении

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

N=3, W=2, R=2:   Strong consistency (2+2 > 3)
  Запись: ждём подтверждения от 2 из 3 узлов
  Чтение: читаем с 2 из 3 узлов, берём свежее

N=3, W=1, R=1:   Eventual consistency (1+1 < 3)
                 Быстро, но можем прочитать устаревшие данные

N=3, W=3, R=1:   Strong consistency, fast reads, slow writes
N=3, W=1, R=3:   Strong consistency, fast writes, slow reads

7.2 Реализация кворумного чтения

import asyncio
from dataclasses import dataclass
from typing import Optional

@dataclass
class VersionedValue:
    value: bytes
    version: int  # vector clock или timestamp
    node_id: str

async def quorum_read(
    key: str,
    preference_list: list[str],
    r: int = 2,
    timeout_ms: int = 50
) -> Optional[bytes]:
    """Кворумное чтение: отправляем запрос на N реплик, ждём R ответов."""
    tasks = [
        asyncio.create_task(read_from_node(node, key))
        for node in preference_list
    ]

    responses: list[VersionedValue] = []
    for coro in asyncio.as_completed(tasks, timeout=timeout_ms / 1000):
        try:
            result = await coro
            if result is not None:
                responses.append(result)
            if len(responses) >= r:
                break
        except (asyncio.TimeoutError, ConnectionError):
            continue

    if len(responses) < r:
        raise QuorumNotReached(f"Got {len(responses)}/{r} responses")

    # Возвращаем значение с наибольшей версией
    latest = max(responses, key=lambda v: v.version)

    # Read repair: если не все реплики имеют свежую версию — обновляем
    stale_nodes = [
        r.node_id for r in responses if r.version < latest.version
    ]
    if stale_nodes:
        asyncio.create_task(read_repair(key, latest, stale_nodes))

    return latest.value

7.3 DynamoDB: два режима чтения

DynamoDB упрощает кворум для пользователя:

Eventually Consistent Read — чтение с любой реплики (fast). Strongly Consistent Read — чтение с leader-реплики (медленнее, но гарантированно свежее).

8. Разрешение конфликтов

8.1 Когда возникают конфликты

При eventual consistency два клиента могут одновременно записать разные значения для одного ключа на разные реплики:

t=0:  key="cart:alice" = {items: [A, B]}  (на всех репликах)
t=1:  Client 1 → Replica 1: {items: [A, B, C]}   (добавил C)
t=2:  Client 2 → Replica 2: {items: [A, B, D]}   (добавил D)
t=3:  Репликация: Replica 1 и 2 имеют РАЗНЫЕ значения — КОНФЛИКТ

8.2 Vector Clocks

Vector Clock — структура данных для отслеживания причинно-следственных связей между версиями.

from collections import defaultdict

class VectorClock:
    def __init__(self):
        self.clock: dict[str, int] = defaultdict(int)

    def increment(self, node_id: str) -> 'VectorClock':
        """Узел node_id произвёл событие."""
        new = VectorClock()
        new.clock = dict(self.clock)
        new.clock[node_id] = self.clock[node_id] + 1
        return new

    def merge(self, other: 'VectorClock') -> 'VectorClock':
        """Слияние двух vector clocks (берём max по каждому узлу)."""
        merged = VectorClock()
        all_nodes = set(self.clock.keys()) | set(other.clock.keys())
        for node in all_nodes:
            merged.clock[node] = max(
                self.clock.get(node, 0),
                other.clock.get(node, 0)
            )
        return merged

    def is_ancestor_of(self, other: 'VectorClock') -> bool:
        """self ≤ other (все компоненты self ≤ соответствующих в other)."""
        for node, count in self.clock.items():
            if count > other.clock.get(node, 0):
                return False
        return True

    def is_concurrent_with(self, other: 'VectorClock') -> bool:
        """Ни self ≤ other, ни other ≤ self → конфликт."""
        return not self.is_ancestor_of(other) and not other.is_ancestor_of(self)

# Пример:
vc1 = VectorClock()
vc1 = vc1.increment("node_A")  # {A: 1}
vc1 = vc1.increment("node_A")  # {A: 2}

vc2 = VectorClock()
vc2.clock = {"node_A": 1}
vc2 = vc2.increment("node_B")  # {A: 1, B: 1}

print(vc1.is_concurrent_with(vc2))  # True — конфликт!
# vc1 = {A:2}, vc2 = {A:1, B:1} — ни один не «потомок» другого

8.3 Last-Writer-Wins (LWW)

Самая простая стратегия: каждая запись получает timestamp, при конфликте побеждает последний по времени. DynamoDB использует LWW по умолчанию.

Проблема LWW: если клиент 1 добавил товар C, а клиент 2 добавил D —
LWW сохранит только одну из корзин, вторая потеряна.

Решение Amazon Dynamo Paper: вернуть ОБА конфликтующих значения
клиенту и дать приложению разрешить конфликт (application-level merge).
Корзина: merge = {A, B, C, D} — объединение.

9. Хранение данных на узле: LSM-Tree

9.1 Зачем нужен LSM-Tree

Традиционный B-Tree (PostgreSQL, MySQL) оптимизирован для чтения: каждая запись обновляет дерево на месте (random I/O). При высоком write throughput это становится узким местом.

LSM-Tree (Log-Structured Merge-Tree) оптимизирован для записи: все записи последовательные (sequential I/O), что на порядок быстрее.

9.2 Как работает LSM-Tree

WRITE PATH:
                                               ┌─────────────────┐
  put(K, V) ──→ WAL (Write-Ahead Log) ──→      │    Memtable     │
                на диск, append-only           │   (in-memory,   │
                для durability                 │   sorted tree)  │
                                               └────────┬────────┘
                                                        │ когда полная
                                                        │ (~64 МБ)
                                                        ▼
                                               ┌─────────────────┐
                                               │    SSTable L0   │
                                               │  (Sorted String │
                                               │ Table, на диске)│
                                               └────────┬────────┘
                                                        │ compaction
                                               ┌────────▼────────┐
                                               │   SSTable L1    │
                                               │(merged, sorted) │
                                               └────────┬────────┘
                                                        │ compaction
                                               ┌────────▼────────┐
                                               │    SSTable L2   │
                                               │  (ещё крупнее)  │
                                               └─────────────────┘

READ PATH:
  get(K) ──→ Memtable (проверить в памяти)
         ──→ Bloom Filter L0 (есть ли ключ в SSTable L0?)
         ──→ SSTable L0 (binary search)
         ──→ Bloom Filter L1
         ──→ SSTable L1
         ──→ ... (от новых к старым)

9.3 Bloom Filter: вероятностный ускоритель чтения

Без Bloom Filter каждое чтение потенциально проходит по всем SSTable. Bloom Filter — это битовая структура, которая гарантированно говорит «ключа точно нет» или вероятностно «ключ может быть».

import mmh3  # MurmurHash3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size: int = 1_000_000, hash_count: int = 7):
        self.size = size
        self.hash_count = hash_count
        self.bits = bitarray(size)
        self.bits.setall(0)

    def add(self, key: str):
        for seed in range(self.hash_count):
            idx = mmh3.hash(key, seed) % self.size
            self.bits[idx] = 1

    def might_contain(self, key: str) -> bool:
        """False = точно нет. True = вероятно есть (false positive ~1%)."""
        for seed in range(self.hash_count):
            idx = mmh3.hash(key, seed) % self.size
            if self.bits[idx] == 0:
                return False  # гарантированно нет
        return True  # вероятно есть

# Bloom filter для каждого SSTable:
#   ~10 бит на ключ → false positive rate ~1%
#   1 млн ключей → 1.25 МБ памяти на фильтр

9.4 Compaction: слияние SSTable

Со временем SSTable накапливаются. Compaction — процесс слияния нескольких SSTable в одну, удаляя устаревшие версии и tombstone'ы.

Size-Tiered Compaction:

• SSTable группируются по размеру
• Когда в одном тире накопилось N таблиц — сливаются в одну большую
• Плюс: хорошо для write-heavy нагрузок
• Минус: временно требует 2x дискового пространства

Leveled Compaction:

• SSTable организованы по уровням (L0, L1, L2...)
• Каждый уровень в 10x больше предыдущего
• Плюс: ограниченный space amplification, предсказуемое чтение
• Минус: больше операций compaction (write amplification)

9.5 LSM-Tree vs B-Tree

10. Failure Detection

10.1 Gossip Protocol

В децентрализованной системе нет единого «мониторинга». Каждый узел должен сам определять, какие соседи живы. Gossip protocol — это «сарафанное радио» между узлами:

Каждую секунду каждый узел:
  1. Выбирает случайного соседа
  2. Обменивается списком известных ему узлов с heartbeat-счётчиками
  3. Обновляет свой список на основе полученных данных

Если heartbeat узла X не обновлялся > T секунд → X считается подозрительным
Если > 2T → X считается мёртвым

Пример:
  t=0: Node A знает: {A: ❤️42, B: ❤️41, C: ❤️40, D: ❤️39}
  t=1: A → B: обмен → оба узнают свежие heartbeats
  t=2: B → D: обмен → информация распространяется
  t=3: D не отвечает — его heartbeat не обновляется
  t=10: Все узлы: "D не обновлялся 10 сек → подозрительный"

Свойство: информация распространяется за O(log N) раундов — экспоненциально быстро.

10.2 Merkle Trees для Anti-Entropy Repair

Со временем реплики расходятся (из-за hinted handoff, сетевых задержек). Merkle tree позволяет быстро найти различия между репликами:

Merkle Tree — хэш-дерево, где:
  Листья = хэши отдельных ключей
  Внутренние узлы = хэши от конкатенации дочерних хэшей

Node A:                       Node B:
      H(root)                       H(root)*
      /     \                       /     \
    H(L)    H(R)                 H(L)    H(R)*
    / \     / \                  / \      / \
   h1  h2  h3  h4              h1   h2   h3  h4*

Сравнение:
  H(root) != H(root)* → различие есть
  H(L) == H(L) → левая половина совпадает, не проверяем
  H(R) != H(R)* → различие в правой половине
  h3 == h3, h4 != h4* → нашли конкретный ключ с расхождением!

Вместо передачи всех данных (ГБ) — сравниваем O(log N) хэшей.

Gossip protocol используется во многих распределённых системах. Подробнее о протоколах обнаружения сбоев и membership — в Главе 2: Ключевые характеристики распределённых систем.

11. DynamoDB: Secondary Indexes

11.1 Global Secondary Index (GSI)

GSI — это отдельная таблица с другим partition key, которая автоматически синхронизируется с основной.

Основная таблица (PK = user_id):
  user:alice | order:2024-01-15 | {email: "alice@mail.com", total: 150}
  user:bob   | order:2024-01-20 | {email: "bob@mail.com",   total: 250}

GSI (PK = email):
  alice@mail.com | user:alice | order:2024-01-15 | ...
  bob@mail.com   | user:bob   | order:2024-01-20 | ...

Теперь можно: get(GSI, PK="alice@mail.com") → найти пользователя по email

Trade-off: GSI — это eventually consistent (асинхронная репликация из основной таблицы). GSI имеет свою пропускную способность и стоит денег.

11.2 Local Secondary Index (LSI)

LSI использует тот же partition key, но другой sort key. Хранится на тех же узлах — поддерживает strongly consistent reads.

Основная таблица (PK=user_id, SK=order_date):
  user:alice | 2024-01-15 | {total: 150, status: "delivered"}
  user:alice | 2024-02-20 | {total: 250, status: "pending"}

LSI (PK=user_id, SK=status):
  user:alice | delivered | {date: 2024-01-15, total: 150}
  user:alice | pending   | {date: 2024-02-20, total: 250}

Запрос: "все pending заказы Alice" — через LSI эффективно

12. DynamoDB Streams

DynamoDB Streams — это Change Data Capture (CDC): каждое изменение в таблице публикуется как событие в упорядоченный поток.

Таблица: users
  put(user:alice, {name: "Alice", age: 30})
       │
       ▼
DynamoDB Stream:
  { eventName: "INSERT",
    newImage: {pk: "user:alice", name: "Alice", age: 30},
    sequenceNumber: "100001" }
       │
       ├──→ AWS Lambda: обновить поисковый индекс в Elasticsearch
       ├──→ AWS Lambda: отправить event в Kafka для аналитики
       └──→ AWS Lambda: инвалидировать кэш в Redis

Event-driven архитектура поверх Change Data Capture — мощный паттерн. Подробнее — в Главе 7: Очереди сообщений и Event-Driven архитектура.

13. Автомасштабирование

Provisioned vs On-Demand

Provisioned + Auto-Scaling: CloudWatch мониторит utilization → при превышении порога увеличивает RCU/WCU → при снижении — уменьшает. Реакция: 1-2 минуты.

Adaptive Capacity: DynamoDB автоматически перераспределяет ёмкость между партициями. Если одна партиция «горячая» — она получает больше throughput за счёт холодных.

Burst Capacity: Неиспользованная ёмкость накапливается (до 5 минут) и может быть использована при кратковременном spike.

14. Масштабирование и надёжность

14.1 Добавление узлов без даунтайма

Текущее состояние: 4 узла, кольцо разделено на 4 сегмента

Добавляем Node E между B и C:
  1. E объявляет о себе через gossip
  2. E получает позицию на кольце (виртуальные узлы)
  3. Ключи из сегмента C, которые теперь принадлежат E, стримятся на E
  4. После завершения переноса: E начинает обслуживать запросы
  5. C удаляет перенесённые ключи

Во время миграции: запросы обслуживаются как обычно
(новые ключи пишутся на E, старые читаются с C или E)

14.2 Global Tables (Multi-Region)

DynamoDB Global Tables — active-active multi-region replication:

us-east-1:  Table "users" (primary in US)
eu-west-1:  Table "users" (replica, active)
ap-south-1: Table "users" (replica, active)

Запись в любом регионе → асинхронная репликация в остальные
Типичная задержка: < 1 секунда между регионами
Конфликты: last-writer-wins по timestamp

Мультирегиональная репликация и active-active паттерн — в Главе 14: Репликация данных.

15. Компромиссы и ограничения

15.1 KV Store vs Relational vs Document

15.2 CAP-выбор

DynamoDB (default):     AP — availability + partition tolerance
                        Eventually consistent reads, sloppy quorum

DynamoDB (strong read): CP — consistency + partition tolerance
                        Strongly consistent reads через leader

Cassandra:              AP (tunable к CP через QUORUM)
Redis:                  AP (single-node) или CP (Redis Cluster с WAIT)
etcd:                   CP (Raft consensus)

15.3 Latency vs Durability

DynamoDB гарантирует durability при подтверждении записи: данные на 3 узлах в 3 AZ (Availability Zones).

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

Уровень 1: Базовые концепции

1. Почему hash(key) % N не подходит для распределения данных по узлам? Что происходит при добавлении узла?

2. Объясните разницу между partition key и sort key в DynamoDB. Зачем нужен sort key?

3. Что такое SSTable и почему данные в ней отсортированы?

4. Что гарантирует Bloom Filter? Что такое false positive и false negative в его контексте?

5. Объясните формулу кворума R + W > N. Какие значения R и W дают eventually consistent чтение?

Уровень 2: Архитектурные решения

6. Как виртуальные узлы (vnodes) решают проблему неравномерного распределения данных? Сколько vnodes обычно создают на физический узел?

7. Опишите механизм hinted handoff. Какую проблему он решает? Каковы его ограничения?

8. Как Merkle trees ускоряют anti-entropy repair? Какова сложность обнаружения расхождений?

9. Чем Global Secondary Index отличается от Local Secondary Index? Какие ограничения у каждого?

10. Объясните разницу между size-tiered и leveled compaction. Для каких нагрузок лучше подходит каждая стратегия?

Уровень 3: Компромиссы

11. Пользователь жалуется на «throttling» в DynamoDB, хотя provisioned capacity не исчерпана. Назовите возможную причину и решение.

12. Два клиента одновременно обновили корзину покупок (один добавил товар A, другой — товар B). При LWW один товар потеряется. Предложите решение без vector clocks.

13. DynamoDB Global Tables используют LWW для разрешения конфликтов. Почему это приемлемо? Когда это может привести к потере данных?

14. Сравните trade-offs: WAL + 3 реплики (DynamoDB) vs WAL + 1 реплика + async backup. Когда второй вариант допустим?

15. Объясните, почему DynamoDB ограничивает размер value 400 КБ. Что делать, если нужно хранить документы по 5 МБ?

Уровень 4: Задачи на проектирование

16. Спроектируйте счётчик лайков для поста с 10 млн лайков/сек. Как реализовать write sharding и агрегацию?

17. У вас таблица с 100 миллиардами записей. 99% запросов — за последние 7 дней. Предложите стратегию TTL + tiered storage.

18. Спроектируйте distributed cache поверх KV-store: read-through, write-through, cache invalidation. Как обеспечить consistency?

19. Как реализовать optimistic locking в DynamoDB (conditional writes)? Напишите pseudocode для compare-and-swap.

20. Вам нужно мигрировать 50 ТБ данных из PostgreSQL в DynamoDB без даунтайма. Опишите стратегию миграции (dual-write, backfill, cutover).

Ответы на ключевые вопросы

import boto3
from botocore.exceptions import ClientError

dynamodb = boto3.resource('dynamodb')
table = dynamodb.Table('products')

def update_price_optimistic(product_id: str, new_price: float) -> bool:
    """Compare-and-swap: обновить цену только если версия не изменилась."""
    # 1. Прочитать текущую версию
    item = table.get_item(Key={'pk': product_id})['Item']
    current_version = item['version']

    try:
        # 2. Записать с условием: version == current_version
        table.update_item(
            Key={'pk': product_id},
            UpdateExpression='SET price = :p, version = :v',
            ConditionExpression='version = :cv',
            ExpressionAttributeValues={
                ':p': new_price,
                ':v': current_version + 1,
                ':cv': current_version
            }
        )
        return True
    except ClientError as e:
        if e.response['Error']['Code'] == 'ConditionalCheckFailedException':
            return False  # кто-то другой обновил — retry
        raise

17. Что читать дальше

Связанные главы книги

Внешние ресурсы

• "Dynamo: Amazon's Highly Available Key-Value Store" (2007) — оригинальная статья, описывающая все основные концепции: consistent hashing, sloppy quorum, vector clocks, Merkle trees
• "Bigtable: A Distributed Storage System for Structured Data" (Google, 2006) — LSM-tree и SSTable в масштабе Google
• "Cassandra — A Decentralized Structured Storage System" (Facebook, 2009) — Dynamo + Bigtable
• "Designing Data-Intensive Applications" (Martin Kleppmann) — главы 5 (репликация), 6 (партиционирование), 7 (транзакции)
• AWS DynamoDB Developer Guide — официальная документация по DynamoDB

Эта глава рассмотрела проектирование Key-Value Store — одной из фундаментальных абстракций хранения данных. Ключевые идеи: consistent hashing для партиционирования, кворум для tunable consistency, LSM-Tree для высокого write throughput, и gossip protocol для децентрализованного обнаружения сбоев. В следующей Главе 87 мы рассмотрим противоположный подход — CP-систему с сильной линеаризуемостью: Distributed Lock Service.