Невозможность Фишера-Линча-Патерсона

— Вот если бы все связи были бы асинхронными… — Нет, это не решит проблему. — Почему?

Действительно, давайте разберемся.

Мне предстояло сделать очередную интеграцию. Требования рядовые: к публичному API обращается конечный пользователь, но обработка запроса происходит с обязательным участием внешней системы – крайне нестабильной и медленной, – от которой нужно дождаться положительный ответ для продолжения действий. При этом важны и атомарность, и производительность…

В этот момент начинается анализ требований и ограничений, в голове перебираются возможные варианты решений: от самых простых до самых сложных. Наш мозг пытается найти компромисс. В мыслях промелькивают ACID, гарантии доставки, transactional outbox, saga, request/response over async и много всего… Ведь никто в здравом уме не хочет включать внешний вызов в транзакцию БД; все хотят делать долгую работу асинхронно. И может возникнуть мысль: “А если бы все связи были асинхронными?!”

Ответ на этот вопрос нашли в уже далёком 1985 три учёных, которые доказали теорему “FLP Impossibility”:

В полностью асинхронной распределённой системе, где нет верхней границы на задержку сообщений и скорость процессов, никакой детерминированный протокол консенсуса, рассчитанный хотя бы на один crash-отказ, не может гарантировать, что все исправные процессы примут решение за конечное время. (M.J. Fischer, N.A. Lynch, M.S. Paterson)

Это самый известный, но не единственный результат научного трио. Ключевые статьи прикреплю в виде файлов ниже, а здесь попробуем взять из этой теории практический максимум. Итак, в распределённых системах:

• Нет безусловных гарантий, есть только компромиссы. Узлы не могут гарантированно судить о состоянии друг друга. Ожидая ответ, неясно, существует ли удалённый процесс или он просто работает очень медленно. Поэтому гарантии консенсуса могут быть даны только в условиях принятых предположений.
• Корректность функционирования должна рассматриваться только в контексте предусмотренных уровней прочности, надёжности и устойчивости. Следовательно, задача не имеет надежного решения без дополнительных предположений о вычислительной среде и ограничений на допустимые типы сбоев.
• Частичная синхронность и рандомизация – два классических способа обойти ограничения FLP. Именно поэтому на практике появляются таймауты, heartbeat, retry, jitter, deadline propagation и прочие техники, которые позволяют обнаруживать отсутствие прогресса и обходить последствия сбоев.

Между тем, FLP – это теорема о задаче консенсуса, т.е. когда все участники должны выбрать одно и то же значение. Это в первую очередь задачи, которые решают разработчики распределённых БД, протоколы Paxos/Raft/Zab. А что с этого тем, кто не решает подобные проблемы, а просто пилит микросервисы?

Для простых смертных есть ещё одна полезная эвристика:

В принятой модели отказов приходится выбирать, чем жертвовать: корректностью функционирования (safety) или вычислительным прогрессом (liveness).

• Выбираем корректность. При сбое система останавливается, вместо того чтобы функционировать неправильно. Например, лучше зависший заказ (потеря прогресса), чем двойное списание денег (потеря корректности).
• Выбираем прогресс. При сбое результат работы может деградировать, т.к. недоступность обходится дороже. Например, системы нечеткого поиска, рекомендательные системы, реклама.

Теперь у нас есть ещё один вариант обоснования архитектурного решения и понимание, что асинхронность не плоха сама по себе, но заставляет явно формулировать предположения о времени и сбоях.

Дополнительная литература

• Impossibility of Distributed Consensus with One Faulty
• Easy Impossibility Proofs for Distributed Consensus Problems