Database Internals — выпуск 4

Финальный выпуск Database Internals начинается с anti-entropy. Участники сравнивают broadcast, Merkle trees для поиска расхождений, hinted handoff для недоступной реплики и version vectors для истории версий. Read repair откладывает разрешение конфликта до чтения, а gossip распространяет состояние эпидемически.

В распределённых транзакциях разбирается two-phase commit: участники сначала обещают выполнить запись, затем coordinator объявляет решение. Его потеря блокирует работу, репликация маскирует лишь часть отказов, а three-phase commit редко применяют. Calvin через sequencer заранее упорядочивает транзакции и исполняет общий план.

Spanner сочетает Paxos внутри групп реплик с two-phase commit между шардами. Для глобального порядка Google использует TrueTime: он возвращает интервал, а не точную отметку. Обсуждаются цена распределённых операций, локальные и межшардовые пути и базы, следующие идеям Spanner.

Финальная глава посвящена consensus, validity, termination и эквивалентности atomic broadcast. В Paxos роли proposer, acceptor и learner разделены, а номера предложений защищают выбранное значение. Multi-Paxos экономит повторные выборы, Raft фиксирует модель лога и лидера. Для Byzantine failures разбирается порог 3f + 1.