Distributed Systems — выпуск 5

«Синхронизация — это выполнение правильной задачи в нужное время», — с этого определения из книги ведущие начинают разговор. Первый пример — сборка через make: на одной машине лежит исходник с таймстампом, на другой работает компилятор, часы разъезжаются — и в сборку попадает объектный файл, который никто не проверял. Дальше авторы уходят в историю измерения времени: оборот Земли вокруг оси — сутки, вокруг Солнца — год, обычная секунда как осциллятор недостаточно точна, поэтому в середине XX века появились атомные часы, а расхождение гасят вставкой секунд. Участники разделяют внутреннюю синхронизацию, когда часы группы процессов сводят друг к другу, и внешнюю, когда их привязывают к эталону: если каждый узел выровнен с точностью до альфы, внутри группы расхождение уже две альфы. NTP разбирают по картинке с четырьмя отметками T0–T3: протокол копит восемь пар значений и берёт минимальную задержку как лучшую оценку.

Страты сравнивают с DNS: сверху дорогие точные часы, ниже подключённые к ним напрямую узлы, дальше уровни через сеть, где точность падает до десятков, а в плохие моменты и сотен миллисекунд. Проговаривают, что время не может идти назад: вместо скачка растягивают такты, и вместо десяти секунд отсчитывают одиннадцать, иначе снова пострадает компиляция. Один из участников признаётся, что работал в хостинге, но внутрь NTP не заглядывал, и удивился, насколько просто протокол пересылает локальные засечки. Тему уводят в физику: участник вспоминает книгу про рождественские лекции Королевского института Великобритании, которые читают почти двести лет, и опыт с часами, улетевшими на самолёте, — они не отстали, а ушли вперёд, потому что гравитационная поправка перевесила поправку на скорость. Отсюда возвращаются к инженерии: в TrueTime и Spanner Google смешивает GPS и атомные часы ради точной оценки, а в беспроводных сетях, где берегут батарейку и ставят отметку на сетевом уровне, привычный алгоритм в духе NTP просто не полетит.

Логические часы начинают с идеи Лэмпорта: важно не «во сколько», а что событие A предшествует B, и если C после B, то C после A. В примере процессы тикают с разным шагом — на шесть, восемь и десять пунктов, — и сообщение, ушедшее из P2 в момент 64, приходит в P1 в момент 54, чего быть не может; правило заставляет получателя подтянуть счётчик выше метки сообщения. Причинность объясняют банковским примером: реплики в Сан-Франциско и Нью-Йорке, клиент кладёт сто долларов на счёт с тысячей, а банк в тот же момент начисляет процент по депозиту — от порядка зависит итог. Векторные часы добавляют по позиции на процесс и позволяют быстро увидеть конфликт, но фиксируют лишь потенциальную причинность: сказанное в одной комнате мимо канала связи в вектор не попадёт, а middleware не знает, использовало ли приложение полученные данные. Любимый пример одного из участников — двое в чате читают счёт матча с разных реплик, и на «классный гол» второй смотрит со старым счётом.

Эксклюзивные блокировки начинают с централизованного варианта: процесс берёт лок, как семафор в локальном программировании, сообщений нужно два-три, зато масштабировать тяжело. Распределённые алгоритмы заставляют процессы договариваться сигналами, и трафик растёт; в кольце право на блокировку даёт токен, но чем длиннее круг, тем дольше ожидание, а восстановление после потери узла оказывается самым сложным — поэтому, отмечают участники, на практике чаще живёт понятный централизованный подход. Один из участников напоминает, что Google в своё время решил не встраивать координацию в каждую систему, а сделал централизованный сервис блокировок Chubby, на котором строятся остальные. Снаружи это простой интерфейс, внутри — распределённый отказоустойчивый сервис с собственными выборами; масштабировать его можно шардами, заведя по лок-серверу на домен, десять-двадцать на систему. Токен-ринг вспоминают как сетевую древность: протокол на считанные мегабиты в секунду, придуманный, по словам участника, в середине восьмидесятых, проиграл коммутируемым сетям.

Выбор лидера в книге сведён к двум крайностям — bully и кольцевому алгоритму: в первом побеждает наибольший доступный идентификатор, во втором сообщение обходит круг, собирая список кандидатов. Между ними, добавляет один из участников, лежит куча оптимизаций вроде заранее назначенного преемника — как король объявляет наследника при жизни. Общая беда — раскол: если группа разъедется на части, в каждой появится свой лидер, поэтому нужен мажоритарный кворум, а фолловеры узнают о смерти координатора по отдельному каналу сигналов. Raft разбирают подробнее: византийские сбои он не решает, состав кластера известен, внутри журнал транзакций, узел бывает фолловером, кандидатом или лидером, таймеры перевыборов разведены сдвигом. Клиенту Raft виден как атомарное хранилище: ответа нет, пока запись не разойдётся по живым узлам, а при расколе три на два меньшинство остаётся без кворума. Книга и рекомендации Consul сходятся на пяти-семи узлах: на сотнях будет лишний трафик и постоянные перевыборы, а смена состава кластера потребовала промежуточной конфигурации в свежих версиях.

Для сетей, где кворум не собрать, Илья показывает блокчейн: в proof of work претенденты подбирают строку, чтобы хеш начинался с пяти или десяти нулей, сложность крутят числом нулей, и один из участников замечает, что из-за минут подбора криптовалютой не расплатишься, как картой. В proof of stake лидера определяет публичная случайная функция по токенам — и участники честно говорят, что не поняли, как она устроена и почему её нельзя перебрать. Gossip предлагают понимать не как офисные сплетни, а как эпидемию: случайная встреча — и информация передана; хранить всех соседей на тысяче узлов дорого, поэтому держат частичную выборку и обновляют её обменом. В матчинге событий подписки либо реплицируют на все узлы, либо рассылают события всем; в selective routing фильтры живут на брокерах, а gossip собирает кружки по интересам — как этот книжный клуб. Финал — позиционирование: GPS с атомными часами на спутниках, Wi-Fi по силе сигнала там, где спутник не ловится, и рассказ Даниила о том, как по идентификаторам устройств искали общий интерес ста машин на дороге, чтобы показать им одну рекламу.