title: Конспект материала 32 — лекции Martin Kleppmann «Distributed Systems» (Cambridge, плейлист) source: https://www.youtube.com/playlist?list=PLeKd45zvjcDFUEv_ohr_HdUFe97RItdiB author: Martin Kleppmann (автор DDIA) — University of Cambridge, курс Concurrent and Distributed Systems, часть 2 (2020) конспект: подготовлено 2026-09-18, TASK-45.36; все 23 лекции (~6.5 ч) — субтитры скачаны и прочитаны полностью; связь с главами DDIA — по карте ddia-map.md (45.10), номера даны «1-е изд. / 2-е изд.» статус: теоретический фундамент под часть II DDIA — не «ещё один набор кейсов» (их закрыли 45.16–45.31), а уровень «почему это работает»: системные модели, причинность, иерархия broadcast-протоколов, полный Raft, 2PC и его отказоустойчивый вариант, ABD, лестница консистентности по допущениям, механика TrueTime. Это материал для ответов на уточняющие вопросы этапов 4–6; на секцию берём не лекции, а маркеры из §4–§5

Материал 32: лекции Kleppmann «Distributed Systems» — ключевые темы и связь с DDIA

Единственный в подборке академический курс и единственный от автора DDIA: 8 разделов × 23 лекции по 8–38 минут (~6.5 ч суммарно), каждая лекция = 1 тема из части II книги, но в разговорном видеоформате с демонстрациями (Wireshark, NTP-логи, Google Docs оффлайн-демо, кейс leap second 2012). Курс закрывает вопрос «откуда в KB формулировки»: почти каждый тезис §7–§9 базы знаний — это сжатая лекция отсюда. Уникальный слой, которого нет ни в DDIA в таком виде, ни в остальных конспектах: последовательное построение системы моделей и лестницы допущений (лекция 2.3 + итог 7.3) — «какое минимальное допущение нужно, чтобы решить задачу X». Именно это — язык ответов на вопросы-ловушки «а что если упадёт», «а какая консистентность и чем платим».

1. Карта курса: 23 лекции → темы → DDIA → KB/бриф

Нумерация лекций — плейлистная (раздел.лекция). DDIA: слева номер по 1-му изд. (рус. перевод), справа — 2-е изд. (см. ddia-map.md §0). Бриф — разделы из 12-разделного каркаса (articles/00-overview.md).

2. Сквозные идеи курса (то, что склеивает лекции в одну линию)

1. Message passing — единственный примитив. Всё остальное (RPC, broadcast, репликация, консенсус) — надстройки над «нодa отправила сообщение ноде». Отсюда язык секции: «фактически у нас граф асинхронных сообщений» вместо магии слов «синхронизация».
2. Модель системы = договор о допущениях. Прежде чем решать задачу, фиксируем три оси: сеть (fair-loss→reliable через retry+dedup; arbitrary→fair-loss через TLS), узлы (crash-recovery — реалистичный выбор ДЦ), тайминг (partially synchronous — единственный честный). Ошибка в допущении = мёртвый алгоритм: «если предположили синхронность, а система ушла в асинхронность на 10 секунд — все гарантии отменяются».
3. Каузальность — единственный «бесплатный» порядок. Физические часы его не дают (скью > задержки), NTP не спасает. Lamport даёт порядок, согласованный с причинностью; векторные часы — ещё и детект параллельности; всё это без часов вообще.
4. Лог — центральная абстракция. State machine replication = TOB + детерминированное применение; commit log лидера = TOB; блокчейн = TOB; Raft-лог = сам TOB. Совпадает с The Log (Kreps, 45.31) и KB §5/§8 — три источника, одна идея.
5. Консенсус ≡ TOB ≡ линейзуемый CAS. Три формулировки одной задачи (лекции 6.1, 7.2) — и все три требуют кворума + частичной синхронности. Отсюда же иерархия «лестницы» (§5 ниже).
6. Safety vs liveness. У консенсуса safety (не решаем два разных значения) не зависит от тайминга; таймауты влияют только на прогресс. Формулировка для секции: «при деградации сети мы не будем врать про данные — максимум, замрём».
7. Каждое усиление гарантии — это деньги. 2PC — блокировка всех; консенсус — кворум; линейзуемость — ~2 RTT и недоступность без кворума; eventual — бесплатно, но конфликты и потеря LWW. Курс систематически показывает цену каждого этажа.

3. Выжимки ядерных блоков

3.1 Системные модели и отказоустойчивость (2.1–2.4)

Выжимка. Two generals доказывает: по lossy-сети нельзя достичь уверенности «событие А произошло iff событие Б» — любая конечная цепочка ACK оставляет окно неопределённости (нет common knowledge). Практический вывод Клеппмана: реальные системы выкручиваются обратимыми действиями (charge → refund) и сверкой состояния после восстановления связи, а не «более надёжной доставкой». Byzantine добавляет врущих узлов: нужно 3f+1, подписи сужают проблему, но не убирают; в ДЦ считаем узлы честными, валидируем вход. Итог — таблица моделей: reliable/fair-loss/arbitrary × crash-stop/crash-recovery/Byzantine × sync/partial/async. Failure detector по таймауту в partial-sync модели — eventually perfect: и ложные подозрения, и запаздывание, но сходится к истине; этого достаточно для практических алгоритмов.

Что брать на секцию. - Маркер зрелости на «что если сеть моргнёт»: «мы в модели partial synchronous + crash-recovery; таймаут не отличает потерю от паузы, поэтому операции идемпотентны, а редкие ложные подозрения лидера переживаем выборами» — одна фраза покрывает лекции 2.3–2.4 и стыкуется с KB §9. - «Отгрузить iff списать нельзя» — готовый ответ на вопрос про платежи/заказы: обратимые действия (refund/сторно) + сверка, а не 2PC через полмира. - 3f+1 и «Byzantine вне охвата датацентров» (KB §9) — на уточнение «а если нода начнёт врать»: checksums, валидация входа, а протокол не меняем.

3.2 Время: физическое, синхронизация, причинность, логические часы (3.1–3.3, 4.1)

Выжимка. Кварцевые часы дрейфуют на десятки ppm (температура!), UTC держится на leap seconds, и софт исторически падает на них (livelock ядра 30.06.2012; лечится smearing). NTP даёт миллисекунды в хорошем ДЦ, но: скью после шага (stepping), паника при большом рассинхроне, и главная ловушка — измерять интервалы по time-of-day нельзя: только monotonic clock (nanoTime/CLOCK_MONOTONIC). Даже с идеальным NTP таймстампы ломают причинность (скью может превышать одностороннюю задержку) → happens-before как частичный порядок → Lamport (порядок с причинностью, tie-break по ноде — total order) → vector clocks (iff-соответствие happens-before; incomparable = concurrent; вектор = множество «себя + всё, что до»). Клеппман подчёркивает: векторные часы — это алгоритмическое вычисление причинности, а не картинка на бумаге.

Что брать на секцию. - «Интервалы — только по monotonic clock, wall clock — только для календаря» — бесплатный маркер production-зрелости (KB §9: LWW по wall clock теряет данные). - Spanner-логика «почему нельзя верить часам» (лекция 8.2) — той же линии: если таймстампы решают порядок, они обязаны быть согласованы с причинностью. - Векторные часы vs Lamport в одной фразе: «Lamport даёт порядок, вектор — детект параллельности; платим размером метаданных» (уже в KB §7, здесь — источник).

3.3 Broadcast-протоколы (4.2–4.3)

Выжимка. Broadcast-абстракции — иерархия гарантий доставки: reliable (все доставят, порядок любой) → FIFO (порядок от одного отправителя) → causal (порядок по happens-before, параллельные — как повезёт) → total (все доставляют в одном и том же порядке) → FIFO total (строго сильнее causal). Реализация: надёжность — eager re-broadcast (O(n²)) или gossip (fanout ~3, ~log N раундов, устойчив к потерям и падениям); FIFO — (sender, seq) + delivered-вектор + holdback-буфер; causal — вектор зависимостей, доставляем когда dependencies ≤ delivered; total — sequencer-лидер (умер лидер → стоп, нужен консенсус) или Lamport-порядок (нужно знать, что сообщение с меньшим таймстампом не придёт; одна упавшая нода стопит всех). Вывод: fault-tolerant total order broadcast — это уже консенсус, лекция 4.3 специально подводит к 6.1.

Что брать на секцию. - Термин holdback queue — точное слово для «мы получили событие, но доставим в приложение позже, когда придёт предыдущее» (fan-out ленты, Kafka-партиции). - Gossip — ответ на «как раскатать изменения/узнать о живых нодах без центра»: ~log N раундов, деградирует мягко. - Лестница гарантий доставки = готовый ответ на «какие гарантии даёт ваша шина»: at-least-once (reliable) ≠ порядок ≠ общий порядок, и каждый уровень стоит координации.

3.4 Репликация и кворумы (5.1–5.3)

Выжимка. Изменяемые данные — вся сложность. Потерянный ack + retry = двойной инкремент (реальный кейс: у Твитера счётчик following уходил в −20). Инструменты: идемпотентные операции (set-add вместо counter; exactly-once = at-least-once + идемпотентность/дедуп) — но идемпотентности мало, когда операции конфликтуют (retry лайка после анлайка восстанавливает лайк: f;g;f ≠ f;g — нужен причинный контекст). Отсюда tombstone (не удаляем, помечаем) + таймстамп на каждую запись + anti-entropy (реплики сравнивают таймстампы и сходятся). Параллельные записи: LWW по Lamport — тотален, но произволен и теряет данные; vector clocks — детектят параллельность, отдают клиенту обе версии (Dynamo). Кворумы: W+R>N гарантирует пересечение, majority-кворумы терпят f падений; read repair — читатель, увидевший свежайшую версию, возвращает её отставшим (с исходным таймстампом — это не новая запись). State machine replication: TOB + детерминированное применение; leader/follower-репликация БД = тот же принцип (commit log фолловерам); при causal broadcast достаточно коммутативности параллельных операций, при reliable — всех.

Что брать на секцию. - «Ретраи только для идемпотентного» получает фундамент: retry должен нести idempotency key и причинный контекст, иначе восстановит отменённое (лайк после анлайка) — стыкуется с KB §7 (идемпотентность) и outbox (45.31). - LWW vs векторные часы — готовый трейдофф для «как разрешаете конфликты реплик»: теряем данные vs отдаём конфликт клиенту. - Read repair с исходным таймстампом — деталь, отличающая «знаю Dynamo» от «знаю, почему это работает».

3.5 Консенсус и Raft (6.1–6.2)

Выжимка. Автоматический failover = консенсус. Консенсус (все выбрали одно из предложенных) формально эквивалентен TOB (эквивалентен линейзуемому CAS). Модель: partially synchronous + crash-recovery; FLP запрещает детерминированное завершение в чисто async системе — поэтому таймауты (failure detector) неизбежны, но они влияют только на liveness, safety держится всегда. Механика Raft: term + один голос за term → максимум один лидер на терм; выборы по мажоритарному кворуму с проверкой актуальности лога (кандидат с устаревшим логом не получит голосов); два лидера в разных термах — штатно (партиция), защита в том, что решение валидирует кворум: каждое сообщение коммитится только при ack большинства. Полный разбор лекции 6.2 (38 мин): стабильные переменные (term, votedFor, log, commitLength), лог-записи (message, term), Log Matching invariant (одинаковый term на одном индексе ⇒ идентичные префиксы), prefix/suffix-репликация, усечение некоммиченного хвоста от старого лидера, коммит по большинству acks, деградация sentLength при несовпадении префикса.

Что брать на секцию. - «Почему не будет split brain»: не «мы умные», а «каждое решение подписано термом и подтверждено мажоритарным кворумом; отставший лидер не может закоммитить» — точная формулировка KB §7 (два голосования). - «Выборы ≠ мгновенные»: во время партиции меньшинство недоступно на запись — это цена консистентности, честно назвать (бриф 08/09). - Уровень детализации для секции — термы, кворум, лог; внутренности выборов (таймауты, рандомизация) — не рисуем (совпадает с «Чего не надо» из ddia-map §2).

3.6 Транзакции и линейзуемость (7.1–7.2)

Выжимка. 2PC ≠ консенсус: атомарный коммит требует единогласия («да» от всех участников) и потому не терпит ни одного отказа, консенсусу хватает кворума. 2PC: prepare = обещание уметь коммитить (записали на диск, держим локи) → решение координатора; если координатор упал между prepare и решением — in-doubt: участники заморожены с локами до его восстановления. Клеппман даёт изящный отказоустойчивый вариант: голоса участников рассылаются через total order broadcast, решение — детерминированная функция от первого голоса каждой реплики (suspected-реплике соседи «голосуют abort» от её имени; гонку реального и подставного голоса TOB снимает общим порядком доставки). Линейзуемость: система неотличима от одной копии; это не serializability (свежесть операции, а не изоляция транзакций); порядок задаёт real-time (перекрывающиеся операции — любой порядок). Важно: кворумные чтения/записи НЕ линейзуемы (контрпример: последовательные чтения из разных кворумов видят регрессию); фикс — read repair до возврата результата (алгоритм ABD, полностью асинхронный, без таймеров). Линейзуемый CAS+get строят через TOB — и это эквивалент консенсуса (потому требует частичной синхронности).

Что брать на секцию. - «Кворум W+R>N даёт свежесть» — неверно, и это вопрос-ловушка (KB §7 уже фиксирует «кворумы не дают линейзуемости»); лекция даёт контрпример, который можно пересказать в одну фразу. - 2PC: называть цену точно — «in-doubt транзакции с локами при падении координатора; поэтому у нас саги + outbox» (KB §7; стыкуется с брифом 09). - «2PL/2PC + Paxos + MVCC» как стек Spanner (следующая лекция) — показывает, что 2PC не отменён, а обложен консенсусом (NewSQL, KB §7).

3.7 Eventual consistency, CAP, CRDT/OT (7.3, 8.1)

Выжимка. Цена линейзуемости: латентность (~2 RTT), масштаб (всё через лидера), и главное — без кворума недоступна даже запись одной ноды. Демо календаря: оффлайн-редактирование двух устройств → конфликт → LWW молча съедает правку заголовка. CAP при партиции: каждая нода выбирает — ждать кворум (недоступна) или отвечать локально (риск нарушения линейзуемости). Eventual: если обновления прекращаются, реплики сходятся; strong eventual: одинаковое множество обновлений в любом порядке → одинаковое состояние. Операции не ждут сеть → быстры и работают при партиции; плата — конфликты и их разрешение. CRDT: op-based (рассылаем операции, нужен reliable broadcast, коммутативность) vs state-based (рассылаем состояние, merge-функция коммутативна/ассоциативна/идемпотентна, терпит потери и дубли, дружит с anti-entropy, но жирные сообщения). Для текста: OT (трансформация индексов, требует TOB) vs CRDT с позиционными идентификаторами (дроби между соседями + tie-break по ноде; delete по уникальному ID через causal broadcast — удаление каузально следует за вставкой). Это исследовательская тема самого Клеппмана; для секции — уровень «назвать трейдофф».

Что брать на секцию. - «При партиции выбираем на уровне операции: корзина покупок — консистентность (ждём кворум), лайки/просмотры — доступность (пишем локально, сходимся)» — живая формулировка CAP вместо заученной (бриф 09). - OT vs CRDT — одной строкой (статьи 11, 45.35 #16): «Google Docs — OT поверх общего порядка; CRDT не требует общего порядка, платим метаданными».

3.8 Google Spanner и TrueTime (8.2)

Выжимка. Требования: серилизуемость + линейзуемость + шардирование + атомарность между шардами. Стек — классика: Paxos (SMR внутри шарда), 2PL (серилизуемость), 2PC (атомарность между шардами). Новизна — read-only транзакции без локов: MVCC (каждая версия помечена таймстампом коммита; reader берёт снапшот-таймстамп и читает последнюю версию ≤ него). Для каузально-консистентных снапшотов нужны таймстампы, согласованные с причинностью: Lamport не работает, потому что каузальность идёт через пользователя (посмотрел результат T1 на реплике А, совершил действие → T2 на реплике B; между репликами сообщений не было — часы не «узнают» о причинности). Решение — TrueTime: физические часы с честным интервалом неопределённости [early, late]; коммит ждёт ширину интервала (commit wait) → интервалы не пересекаются → таймстампы не переставляются. Инженерия: атомные часы + GPS в каждом ДЦ, синхронизация каждые 30 с с локальным time-сервером (RTT <1 мс → неопределённость ~1 мс), рост 200 ppm → ~6 мс к концу цикла, «пила», в среднем commit wait ≈ 4 мс — дёшево на фоне межконтинентального RTT.

Что брать на секцию. - Spanner = «strict serializability» (KB §7) — теперь с механикой: MVCC-снапшоты + commit wait по TrueTime. - Кейс «почему Lamport недостаточно» (каузальность через пользователя, cross-channel) — красивый ответ на «зачем вам физические часы, если есть логические» (бриф 09, этап 4+). - Принцип «платим 4 мс ожидания — получаем лок-фри чтения на бэкапах» — пример честного трейдоффа вместо «мы всё закешировали».

4. Лестница допущений: фирменный итог курса (лекция 7.3)

Клеппман завершает разбором «сколько стоит каждая гарантия» — от самой дорогой к бесплатной. Это готовая структура ответа на «какая консистентность вам нужна и чем платите»:

Чтение снизу вверх — «как удешевить», сверху вниз — «как усилить». На секции называем этаж для каждой части схемы отдельно (заказы — верх, лайки — низ), а не одну метку на всю систему.

5. Как смотреть: порядок под слоты

Не подряд (6.5 ч не вписываются в подготовку к 18–22.09). С учётом того, что KB §7–§9 уже сжали курс в формулы, видео закрывают три задачи: (а) понять то, что в KB осталось формулой; (б) набрать демонстрации и кейсы для ответов; (в) освежить формулировки перед слотом.

• Ядро (~2 ч), если смотреть только перед слотом: 2.3 (system models) → 5.2 (quorums) → 6.1 (consensus) → 7.2 (linearizability) → 7.3 (eventual + итоговая лестница, последние 5 мин лекции) → 8.2 (Spanner TrueTime как вишенка для ответов про консистентность).
• Второй круг (после первой секции, под этапы 4–6): 3.2 (NTP/monotonic) → 4.1 (logical time) → 5.1 (репликация, кейсы лайков/Твитера) → 6.2 (Raft по шагам — 38 мин, смотреть с конспектом KB §7) → 7.1 (2PC + отказоустойчивый вариант).
• Опционально / после секций (staff-уровень): 1.1–1.3 (вводные — понятно и так), 2.1–2.2 (two/Byzantine generals — достаточно пересказа выше), 4.2–4.3 (broadcast — полезен для ответов «как это устроено внутри»), 8.1 (CRDT/OT — вне брифа).
• Каждая лекция = 10–38 мин; смотреть на 1.5× с субтитрами; после каждой — пересказ тезисов у доски ≤2 мин (тот же протокол, что для глав DDIA в ddia-map §1).

6. Связанные документы

• materials/ddia-map.md (45.10) — карта глав DDIA, обеих редакций; связь «лекция ↔ глава» — таблица §1 выше
• knowledge-base.md §5 (репликация), §7 (консистентность/консенсус), §9 (отказоустойчивость) — сюда ложится почти весь курс; §12 — сжатая карта DDIA
• articles/09-consistency.md, articles/08-fault-tolerance.md — прикладной слой тех же тем под бриф
• materials/lsd-interviewready-resources.md (45.31, The Log Крепса) и materials/lsd-awesome-distributed-systems.md (45.32, Raft-визуализации) — та же линия «лог + консенсус» с другой стороны
• materials/lsd-sd-algorithms.md (45.35, п. 16 Operational transformation) и articles/11-*.md — коллаборативное редактирование
• Задача-сателлит: 45.37 (jepsen.io) — следующая ступень той же темы: как консистентность реальных БД проверяют сломом