Database Internals — выпуск 4

Первая из трёх сегодняшних глав небольшая: broadcast, анти-энтропия и слухи. Broadcast автор даже не иллюстрирует — нода рассылает соседям сообщение, которое может и потеряться; один из гостей замечает, что энтропия — мера беспорядка, а гасят её эпидемические процессы, в которых за пару лет все стали экспертами. Деревья Меркла: листья хешируются, хеши склеиваются снизу вверх, и сравнение двух корней за логарифм показывает, расходятся ли наборы и какие листья синхронизировать; один из гостей добавляет, что такие сверки живут не только в базах данных: их собственные сервисы так же сравнивают данные и досылают друг другу обновления. Hinted handoff Александр объясняет на Cassandra: если при записи на кворум одна нода недоступна, сосед сохраняет подсказку и позже доносит запись адресату. Bitmap version vectors Сергей ковырял два дня и советует статью, которая ведёт к dotted version vectors через happened-before, векторные часы и передачу только релевантных событий; в книге, по его подсчёту, две-три сотни ссылок на внешние источники.

Read repair Виталий описывает по Dynamo-подобным базам: в DynamoDB конфликты между репликами разрешает клиент, в Cassandra и Scylla побеждает последняя запись, а само разрешение откладывается до момента чтения реальным клиентом — с оптимизацией, когда с одной реплики берут данные, а с остальных дайджесты; недостаток очевиден: что не прочитали, то не синхронизировали. Участники раскладывают механизмы по масштабу: деревья Меркла и version vectors уменьшают объём сверки на уровне всего датасета, а hinted handoff и read repair работают точечно — там, где прямо сейчас идёт активность; на остальное можно махнуть рукой, как на редкий функционал, который работает и никого не беспокоит. Сплетни — фирменная черта Cassandra: наивный вариант, где каждый пересылает всем, порождает лавину сообщений, поэтому строят spanning tree или ограничивают число соседей, а списки периодически актуализируют; Александр вспоминает, что ту же математику видел в описании сетей, и ощущение дежавю от книги возникает постоянно.

Двухфазный коммит: координатор спрашивает участников, готовы ли они, и по единодушному «да» командует коммит; главная проблема — отказ координатора, после которого участники остаются в неопределённости и ждут его восстановления. Виталий вспоминает первую встречу с 2PC — Microsoft DTC, где все статьи по траблшутингу начинались с «переустановите». Зритель спрашивает, что будет, если нода пообещала и не применила, — Александр отвечает: по протоколу она сломалась, и починить это можно репликацией участников, а если координатор врёт — это уже византийский отказ. Сергей делает тонкое замечание: коммит не мгновенен, и в транзакции «сообщение в очередь плюс строка в базу» читатель может увидеть сообщение раньше строки. Трёхфазный коммит добавляет фазу и часть проблем решает, но требует железобетонных допущений, которых в жизни нет, — в дикой природе его никто из чата не встречал.

Calvin — детерминированные транзакции: Сергей объясняет, что ключевое там не план, а sequencer — логический порядок применения транзакций фиксируется заранее, батчами по десять миллисекунд, и дальше узлы исполняют его по scheduler без координации; Александру эта идея когда-то щёлкнула — договориться не во время, а до, — а один из гостей ценит, что упавшая нода после подъёма накатывает тот же план; подход используется в YDB, о чём есть статья на Хабре, хотя в оригинале нужно заранее знать read/write set. Сергей проводит параллель с Aurora, где единая точка секвенирования упорядочивает WAL и хранилище масштабируется без консенсуса, — ценой того, что sequencer может стать узким местом. Spanner: Paxos-группы с долгоживущими лидерами по наборам данных, 2PC между группами через lock table, TrueTime с интервалами вместо точного времени; YugabyteDB идёт по его стопам с отдельным хранилищем для распределённых транзакций, где латентность заметно выше локальной. Шардирование, консистентное хеширование и ещё один подход к snapshot isolation клуб оставляет на самостоятельное чтение.

Консенсус — договориться о значении, которое предложил один из участников, и завершить процесс; перед ним автор вводит atomic broadcast: все живые процессы доставляют одни сообщения в одном порядке, и это эквивалентно консенсусу — Александр признаёт, что понял, почему это broadcast, только перечитав треть книги. Собственный протокол ZooKeeper участники разбирают через эксплуатацию: пропускная способность держится на одном лидере, а настройка таймингов — баланс между чувствительностью к потере лидера и долгим восстановлением; эпохи, синхронизация с доведением дел прошлого лидера, и не зря Kafka уходит от ZooKeeper. Paxos: proposers, acceptors, learners; статья Лампорта про какой-то греческий остров, где читатель чувствует себя археологом; Сергей пересказывает алгоритм через вечеринку с громкой музыкой, где договариваются, в какой бар идти, — и ему тут же отвечают, что он достойный последователь Лампорта, который потом посыпал голову пеплом за попытку объяснять распределённые алгоритмы через метафоры.

Александру щёлкнуло на номерах предложений: получив больший номер, ты не предлагаешь своё значение, а присоединяешься к уже принятому, и так значение фиксируется. Single-decree Paxos дорог на каждое решение, поэтому Multi-Paxos бронирует за лидером право предлагать, пока ему хорошо. Raft авторы делали понятным: выборы лидера, который потом всем сообщает, что он ещё жив, репликация лога, реализация-эталон и куча иллюстраций; при проблемах с лидером Raft подвисает, а Multi-Paxos сваливается в single-decree с несколькими претендентами — Сергей считает возможные конфликты на выборах фичей, «игральной костью» вместо сложного детерминизма. Византийские отказы: PBFT переживает f неверных узлов при 3f+1, но, по осторожной оценке одного из гостей, который признаётся, что понял алгоритм поверхностно, ловит лишь тех, чьи хеши сообщений не сходятся. Итог по книге: один из гостей предложил бы вариацию, где алгоритмов нет вовсе, а есть только «зачем»; другой сравнивает её с собственной коллекцией white papers и признаёт, что глубины местами не хватило — с ней книга была бы не триста страниц, а шестьсот или тысяча; Александр читал её три-четыре месяца и называет это настоящим трудом, но как каркас для дальнейшего чтения книга хороша.