Гарантийное обслуживание конечных автоматов

Я много и часто говорю о том, что есть принципиальное различие между конечным автоматом и полем «state» в базе данных. Я даже уже отчасти писал про это, но акценты в том тексте были на другом, поэтому я решил посвятить целые полчаса собственной жизни кристаллизации тезисов о правильных конечных автоматах и их реализации в CS.

Так повелось, что математики ограничились применением конечных автоматов к алфавитам, а прикладники тем временем увидели знакомое слово «состояние» и со свойственным всем нам верхоглядством решили, что набор «состояний» и «переходов» — это и есть конечный автомат. Всем, наверное, доводилось видеть такой код:

void transition(state, event) {
  switch(state) {
    case IDLE:
      this.state = WORKING;
      doWork(event);
      this.state = DONE;
      break;
    case DONE:
      doReset();
      this.state = IDLE;
      break;
    default:
      terminate();
  }
}

Не «Рождение Венеры» Ботичелли, конечно, но функцию свою выполняет. Выполняет ведь? А кто может указать на одну архитектурную и одну критическую ошибку, которая завтра испортит тот объект, который этот автомат обслуживает?

Один переход — одно состояние

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

На самом деле нет. Представьте себе, что рядом с вами работает умный ленивый человек, который решил втайне от вас сохранять состояние в базу. Естественно, он не станет лезть в ваш код и высылать вам на ревью PR с [phone]. Он прикрутит аспект на изменение состояния. Который обновит в базе state каждый раз, когда он устанавливается в новое значение в коде.

Если однажды doWork упадёт, то в базе останется значение состояния «WORKING», и код выше для данного объекта теперь всегда будет выходить в terminate. Если вы считаете, что от таких досадных недоразумений должен защищаться программист — мне вас жаль. Переложите такие задачи на компилятор — и у вас высвободится вагон свободного времени, чтобы собственноручно писать код, а не делегировать это развлечение LLM-ке.

Вообще говоря, рассчитывать на то, что правильный работоспособный код будет получаться стараниями разработчика — глупость, граничащая с преступлением. Вон даже создатели раста это понимают.

Гонка

Как бы мы ни стремились замедлить прогресс созданием однопоточного кода, мир отвоёвывает своё. Когда я вкатывался в профессию, понятие thread-safe в прикладном программировании было известно нескольким фрикам, и то — понаслышке. Когда я стал писать более-менее внятный код, все без исключения сторонние библиотеки тщательно оговаривались в README: «вот тут thread-safe, тут — не thread-safe, а тут — рыбу заворачивали». Сегодня писать не thread-safe код — фактически саботаж.

Код выше, будучи вызван в конкурентной среде, может передать управление другому потоку между строками 4 и 5. Вот тут:

      this.state = WORKING;
      // что-то я устал, перекур, давайте пока без меня 
      doWork(event);

А другой поток — может запросто инициировать переход на этом же объекте. Хоба! — и второй поток проник в switch, состояние (установленное первым потоком) — WORKING, — и вот второй поток уже вызывает terminate. Тут город засыпает, и просыпается маф^W первый поток. Хоба! И мы вызываем doWork на терминированном объекте. Буквально на ровном месте, причем.

У этого кода есть и третий, чуть менее явный огрех.

Состояние может изменяться только переходами

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

void prepareReport() {
    State state = this.state;
    // «буквально на секундочку сделаем эту дорогу двусторонней», —
    //   как говорил мой дядька, сворачивая под кирпич
  
    this.state = WORKING; // чтобы правильно посчитались суммы
    … // do a report
    this.state = state;
}

Хоба! И наша сущность на час (это небыстрый отчет) переходит во временное состояние WORKING.

Я утрирую, конечно. Общеизвестно, что мы, разработчики, крайне ответственно относимся к контрактам, добавляем код только корректным, правильным образом — и вообще никогда не допускаем ошибок. Поэтому мы выставим мьютексы, будем определять состояния только переходами, никогда не станем менять внутренний стейт ad-hoc, и понапишем корректных тестов на любой случай, предусмотрев все возможные и невозможные сценарии.

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

Как всего этого избежать?

Мне неизвестен способ изящнее, чем запускать легковесный процесс (гринтред, корутину, горутину) на каждый экземпляр конечного автомата и обрабатывать входящие запросы — как сообщения в акторной модели. Этого можно добиться и вне акторной модели: тогда на функции/методе transition просто должен висеть мьютекс (наподобие synchronised в джаве). Это, правда, не спасет от непреднамеренного саботажа — от установки поля вручную в обход синхронизированного метода. В акторной модели — вам не придется об этом даже думать. Процесс не может обрабатывать больше одного сообщения одновременно. Там очередь. А внутреннее состояние процесса невозможно изменить извне. Поэтому гарантии консистентности вы получаете просто из коробки.

Вообще говоря, на этом подарки, которые мог бы преподнести разработчику компилятор, — не заканчиваются. Можно было бы проверять такие мелочи, как наличие начального состояния, обязательного для конечного автомата, хотя бы одного конечного, отсутствие сирот… Можно было бы сообщить обо всех циклических «путях», о кратчайших путях достижения конечного состояния, а еще можно было бы нарисовать mermaid-диаграмму и прицепить её к документации. И это всё вполне может сделать компилятор. Я уже рассказывал про свою библиотеку Finitomata, в которой все эти плюшки реализованы. Сейчас я просто на пальцах покажу, как добиться всех тех же гарантий можно на чистых процессах.

Процесс в эрланге — готовый конечный автомат

Директива use GenServer превращает код модуля в процесс, который умеет отвечать на синхронные и асинхронные сообщения — для этого всего лишь надо реализовать соответствующие колбэки. Вот пример (упрощенный) для турникета.

```

defmodule Turnstile do
  use GenServer

  @impl GenServer
  def init(_), do: {:ok, {:closed, 0}}

  @impl GenServer
  def handle_cast(:coin, {_, coins}),
    do: {:noreply, {:open, coins + 1}}

  def handle_cast(:walk, {:open, 1}),
    do: {:noreply, {:closed, 0}}

  def handle_cast(:walk, {:open, coins}),
    do: {:noreply, {:open, coins - 1}}

  def handle_cast(action, {state, coins}) do
    require Logger
    Logger.error("Prohibited action ‹#{action}› in state ‹#{state}›")
    {:noreply, {state, coins}}
  end
end

Всё. Паттерн-матчинг в трёх clauses одной и той же функции разруливает любые действия. Тут немного кода, попробуйте сами проверить, не напортачил ли я с логикой.

Вот так это выглядит в iex (REPL):

iex|🌢|2 ▶ {:ok, pid} = GenServer.start_link(Turnstile, :ok)
{:ok, #PID<0.115.0>}
iex|🌢|3 ▶ GenServer.cast(pid, :walk)
16:59:10.631 [error] Prohibited action ‹walk› in state ‹closed›
iex|🌢|4 ▶ GenServer.cast(pid, :coin)
iex|🌢|5 ▶ GenServer.cast(pid, :walk)
iex|🌢|6 ▶ GenServer.cast(pid, :coin)
iex|🌢|7 ▶ GenServer.cast(pid, :coin)
iex|🌢|8 ▶ GenServer.cast(pid, :coin)
iex|🌢|9 ▶ :sys.get_state(pid)
{:open, 3}

Один у вас процесс, или их миллион — ничего не изменится. Обработка сообщений из mailbox — будет производиться последовательно, одно за другим. Состояние всегда будет консистентным.

Но что будет, если процесс упадёт? Его перезапустит его супервизор, с начальным состоянием, что нормально для 99% случаев. Но если он упадёт сразу после того, как щедрый Вася отгрузил в монетоприёмник 10 жетонов, Вася может расстроиться. Есть три распространенных варианта решения этой проблемы: ① использовать мою библиотеку peeper, ② хранить состояние в ETS с правильно установленным heir (здесь это немного выходит за рамки темы текста, в библиотеке выше есть реализация), или ③ писать в базу.

Последний вариант — скорее всего необходим для жетонов стоимостью с крыло боинга каждый, но в случае метро — обычно лучше обойтись одним из первых двух.

Удачного конечного автоматизирования!