Distributed Systems — выпуск 5

Физические часы расходятся из-за неточности осцилляторов, а сеть добавляет переменную и часто асимметричную задержку. Поэтому синхронизация бывает внутренней, когда важна близость часов узлов друг к другу, и внешней, когда их привязывают к эталонному времени. NTP оценивает одновременно смещение и сетевую задержку, организуя источники в страты с разной точностью. В выпуске также появляются Reference Broadcast Synchronization для беспроводных сетей и Google TrueTime в Spanner: оба примера показывают, что протокол использует свойства своей среды, а не устраняет неопределённость магически.

Многим алгоритмам нужна не календарная отметка, а согласованный порядок. Отношение happens-before Лесли Лэмпорта фиксирует причинно наблюдаемую последовательность событий, а логические часы позволяют построить порядок сообщений. Это используется, например, в totally ordered multicast и репликации конечного автомата, где реплики выполняют одинаковые команды в одинаковой очередности. Однако сравнение значений часов Лэмпорта само по себе не доказывает причинность. Векторные часы сохраняют больше информации и различают зависимые и конкурентные события. Попытка полностью спрятать порядок в middleware ломается там, где только приложение знает нужную семантику доставки.

Взаимное исключение требуется, когда несколько процессов могут повредить общий ресурс одновременным доступом. Глава сравнивает семейства алгоритмов и затем связывает абстракцию с практическими сервисами. В ZooKeeper блокировку можно представить через создание узла в иерархическом пространстве: только один претендент успешно получает право владения, а остальные координируются через состояние сервиса. В качестве промышленного родственника обсуждается Chubby от Google. Главный вопрос при выборе не сводится к скорости: нужно понимать, где находится координационная власть и как система обнаруживает, что прежний владелец больше не может выполнять роль.

Выбор лидера решает похожую, но более общую задачу: некоторым алгоритмам нужен координатор, хотя не принципиально, какой именно процесс им станет. В выпуске сопоставляются bully algorithm, кольцевой алгоритм, выбор лидера в ZooKeeper и Raft. У каждого решения свои предпосылки о членстве, идентификаторах, доставке сообщений и обнаружении отказа. Эти предпосылки особенно заметны в беспроводных сетях, где нельзя полагаться ни на надёжную доставку, ни на стабильную топологию. Permissionless-блокчейны с proof of work и proof of stake показывают ещё один класс выбора: участники заранее не образуют доверенную фиксированную группу.

Gossip-based coordination распространяет локально известные изменения через обмен между соседями. Такой подход подходит задачам, где важны масштабирование и постепенное достижение общего знания, а мгновенный глобальный порядок не требуется. Он меняет характер гарантии: вместо одного арбитра система получает повторяющееся распространение сведений и должна терпеть временно разные представления. Поэтому gossip нельзя выбирать только за внешнюю простоту. Нужно заранее определить, какое расхождение допустимо, как обнаруживается сходимость и что произойдёт, если решение требует строгой очередности или единственного владельца.

Distributed event matching показывает тот же выбор на примере publish-subscribe. Проверку соответствия события подписке можно централизовать и масштабировать, распределить селективной маршрутизацией либо разнести через gossip; защищённый поиск добавляет отдельную задачу, для которой рассматривается PEKS. Последняя тема — locality. Физические координаты GPS, позиционирование по Wi‑Fi и логические координаты overlay-сети нужны потому, что близким процессам часто выгоднее взаимодействовать друг с другом. Общий вывод выпуска практичен: сначала определить требуемое отношение — точность времени, причинность, исключительность, сходимость или близость — и лишь затем выбирать протокол координации.