llmdocsсправочник разработчика

Распределённые системы

Материал из llmdocs — справочник разработчика
Портал: Основы CS
Распределённые системы
Определениенесколько узлов, общающихся сообщениями, без общей памяти и общих часов
Ключевые проблемычастичные сбои, ненадёжная сеть, отсутствие глобального времени
КонсенсусPaxos (1989), Raft (2014)
Основные работыЛэмпорт — «Time, Clocks…» (1978); FLP (1985)
Книги«Designing Data-Intensive Applications» (Клеппман)
ПримерыKubernetes, etcd, Kafka, Cassandra, Spanner

Распределённая система — набор независимых компьютеров (узлов), которые общаются только сообщениями по сети и вместе решают одну задачу так, что для пользователя они выглядят как единое целое. Почти любой современный сервис распределён: веб-приложение с базой данных и кэшем, кластер Kubernetes, реплицированная база, очередь сообщений, CDN. Распределение нужно ради масштабирования, отказоустойчивости и близости к пользователям, но приносит фундаментальные трудности, которых нет в программе на одном компьютере.

Почему это трудно

В одном процессе вызов функции либо выполняется, либо программа падает целиком. В распределённой системе возможны частичные сбои: один узел работает, другой завис, сеть между ними теряет пакеты. Отправив запрос и не получив ответа, узел не может отличить три ситуации — запрос потерялся, получатель упал, или ответ потерялся по дороге, а действие уже выполнено.

Известный список заблуждений распределённых вычислений (Питер Дойч и коллеги из Sun, 1990-е) перечисляет ложные предположения новичков:[5]

  1. сеть надёжна;
  2. задержка равна нулю;
  3. пропускная способность бесконечна;
  4. сеть безопасна;
  5. топология не меняется;
  6. администратор один;
  7. передача данных бесплатна;
  8. сеть однородна.

Время и порядок

У узлов нет общих часов: системное время расходится, синхронизация по NTP даёт точность в миллисекунды, а часы могут прыгать назад. Поэтому нельзя надёжно упорядочить события по меткам времени с разных машин. Лесли Лэмпорт в работе 1978 года предложил логические часы — счётчики, отражающие причинно-следственный порядок «произошло раньше» без физического времени.[1] Развитие идеи — векторные часы и гибридные логические часы. Google Spanner решает задачу иначе — атомными часами и GPS с явной оценкой погрешности (TrueTime).

Репликация

Хранение копий данных на нескольких узлах обеспечивает отказоустойчивость и масштабирование чтения (см. Репликация баз данных):

Схема Как работает Компромисс
Лидер — последователи записи идут на лидера, реплики копируют просто; при отказе лидера нужно переключение
Несколько лидеров запись в любом дата-центре конфликты одновременных изменений
Без лидера (Dynamo-стиль) запись и чтение кворумом из N узлов гибко; согласованность в конечном счёте

Синхронная репликация гарантирует, что данные не потеряются, но медленнее и зависит от доступности реплик; асинхронная быстрее, но при отказе лидера последние записи могут пропасть. Выбор между согласованностью и доступностью при сбоях сети формализует CAP-теорема. Для данных, которые не помещаются на один узел, применяют шардирование.

Консенсус

Многие задачи — выбор лидера, распределённые блокировки, атомарная фиксация, хранение конфигурации — сводятся к консенсусу: несколько узлов должны договориться об одном значении, даже если часть из них отказала. Теорема FLP (1985) доказывает, что в полностью асинхронной сети детерминированный консенсус невозможен даже при одном сбое;[3] практические алгоритмы обходят это с помощью тайм-аутов и гарантируют безопасность всегда, а продвижение — когда сеть ведёт себя разумно.

  • Paxos (Лэмпорт) — классический алгоритм, известный сложностью понимания.
  • Raft (2014) — создан специально понятным: выбор лидера по срокам (terms), репликация журнала, большинство голосов.[2] Используется в etcd (хранилище Kubernetes), Consul, CockroachDB, Kafka (KRaft).

Кластер из 2f + 1 узлов переживает отказ f узлов: из трёх — одного, из пяти — двух. Поэтому кластеры консенсуса имеют нечётный размер.

Надёжная работа с сетью

  • Тайм-ауты на каждый сетевой вызов — без них один зависший сервис останавливает всю цепочку.
  • Повторы с экспоненциальной задержкой и случайным разбросом (jitter), чтобы не создать лавину запросов.
  • Идемпотентность — повторный запрос не должен списать деньги дважды; используют ключи идемпотентности.
  • Автоматический выключатель (circuit breaker) — перестать вызывать сервис, который явно не работает.
  • Асинхронный обмен через очереди и журналы событий (Kafka, RabbitMQ) — развязывает сервисы по времени.
  • Семантика доставки: «не более одного раза», «хотя бы один раз», а «ровно один раз» на практике достигается сочетанием повторов и идемпотентной обработки.

Многие из этих механизмов вынесены в инфраструктуру — Service mesh, балансировщики и клиентские библиотеки.

Наблюдаемость и тестирование

Отладка распределённой системы требует распределённой трассировки и сквозных идентификаторов запросов. Для проверки поведения при сбоях используют хаос-инжиниринг (намеренное отключение узлов и внесение задержек), тесты в духе Jepsen и формальную верификацию алгоритмов — например, на языке TLA+, который разработал Лэмпорт и применяют AWS и другие компании.

Литература

Основное современное введение — книга Мартина Клеппмана «Designing Data-Intensive Applications» («Высоконагруженные приложения»).[4] Классические работы — статьи Лэмпорта, работа FLP и статья о Raft вместе с его интерактивной визуализацией.[6]

См. также

Источники

  1. Lamport — Time, Clocks, and the Ordering of Events in a Distributed System (1978)
  2. Ongaro, Ousterhout — In Search of an Understandable Consensus Algorithm (Raft, 2014)
  3. Fischer, Lynch, Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)
  4. Kleppmann — Designing Data-Intensive Applications (O'Reilly)
  5. Deutsch et al. — Fallacies of Distributed Computing
  6. Raft — визуализация и реализации
Категории: