Нужны ли FSM синхронные вызовы?

TL;DR: Нет, не нужны.

Текст ниже — иллюстрация к тексту «Этот мир — асинхронный, и что вы ему сделаете», раскрывающая реализацию конечного автомата на полностью асинхронной акторной модели.

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

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

Просто поясню, за чем именно я гнался, на примерах из параллельного (в смысле не пересекающегося со мной) мира.

FSM в Java Spring

Простота в использовании

Вот что нам предлагают в качестве третьего примера (первые два — совсем вырожденные) в документации по Spring State Machine. За спойлером, конечно,

я чту психическое здоровье читателей:

Это описание состояний, их всего восемь

Это пока не всё, надо же

переходы еще описа́ть:

Шрифт пришлось уменьшить, чтоб на экран влезло, но у вас же хорошее зрение, да?

Вот этих вот нечитаемых полотнищ хотелось бы избежать.

Горизонтальное масштабирование

Для этого просто придется сразу проектировать библиотеку так, чтобы на каждый «экземпляр» автомата запускался процесс где-нибудь в кластере, а не строго локально. Для повторяемого размазывания процессов по кластеру идеально подходит консистентный детерминированный HashRing, лучшую имплементацию которого в BEAM принес Пол Шёнфельдер.

Доказанная консистентность

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

Изменение состояния — никаким способом, кроме инициированного ивентом перехода из предыдущего состояния, — достигнуто быть не может.

Реализация

Определение (описание) состояний и переходов

Я решил велосипедов не изобретать, и совместить приятное с полезным: меньше кода, больше смысла. Язык описания конечных автоматов существует, называется PlantUML. После анонса первой версии библиотеки в сообществе, мне посоветовали заодно поддержать Mermaid и синтаксис flowchart вместе со state diagram. Mermaid хорош тем, что его можно отрисовать прямо в документации джаваскриптом, а flowchart — в некоторых случаях выразительнее. В общем, получилось вот что:

defmodule Turnstile do
  @fsm """
  idle --> |on!| locked
  locked --> |coin| unlocked
  locked --> |off| down
  unlocked --> |push| locked
  unlocked --> |coin| unlocked
  """

  use Finitomata, @fsm, auto_terminate: true

  @impl Finitomata
  def on_transition(:locked, :coin, _, state_payload) do
    {:ok, :unlocked, state_payload}
  end

  def on_transition(:unlocked, :coin, _event_payload, _state_payload) do
    Logger.info("Thanks, this coin will be donated to the animal shelter!")
    {:error, :unexpected_coin}
  end
end

Это пока не готовый к выкатке в продакшн код. Я всего лишь хотел продемонстрировать как выглядит полнофункциональный конечный автомат в простейшем виде. Хендлер для приёма жетона в закрытом состоянии тоже можно убрать, я его привел только в качестве примера. Хендлер для приема жетона в состоянии «открыто» — уместнее превратить в увеличение «оплаченных поездок» во внутреннем стейте state_payload. Если пара «состояние, ивент» однозначно определяет целевое состояние (и изменение внутреннего стейта не требуется) — хендлер можно опустить (см. {:unlocked, :push}, например).

Если же хендлер требуется, то ваш LSP покажет в вашем редакторе (даже в убогом, типа IDEA) соответствующую

диагностику

Предупреждение LSP: переход нуждается в эксплицитном резолвере

Ивенты с восклицательным знаком на конце выполняются автоматически, а еще можно завести таймер, или настроить количество попыток перейти в указанное целевое состояние.

Но для экспериментов достаточно и простейшей реализации.

Поиграемся

Для того, чтобы полюбоваться на работу этой штуки вживую, нам потребуются несколько терминалов. Запускаем две ноды (если это будут две разные машины — ничего не изменится) и запускаем FSM (из правого терминала; HashRing определил процесс на первую ноду — левый терминал):

кластер в школе или дома

Вызывающий код даже не знает, на какой ноде запущен процесс

Давайте попробуем запустить 10К процессов, а потом узнать внутренний стейт у какого-нибудь из них.

iex(n2@am-victus)6> Enum.each(2..10_000, # Т1 мы уже запустили выше
...(n2@am-victus)6>  &Infinitomata.start_fsm(T, "T#{&1}", Turnstile, %{id: &1}))

iex(n2@am-victus)7> :timer.tc(fn -> Infinitomata.state(T, "T5000") end)
{99, # ⇐ это микросекунды
 #Finitomata<[
   name: {Finitomata.T.Registry, "T5000"},
   pids: [self: #PID<0.2718.0>, parent: #PID<0.194.0>],
   state: [current: :locked, previous: :idle, payload: %{id: 5000}],
   internals: [errored?: false, persisted?: false, timer: false]
 ]>}

Это долгоживущий процесс, мы можем про него забыть, пока нам не понадобится обработать приём монеты в 5000-ом турникете. Также безопасно можно попробовать запустить FSM повторно:

iex(n2@am-victus)8> Infinitomata.start_fsm(T, "T1", Turnstile, %{})
{:error, {:already_started, {:"n1@am-victus", #PID<23819.224.0>}}}

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

Когда нужен синхронный вызов?

Давайте сначала разберемся, как устроен жизненный цикл процесса в BEAM. У процесса есть внутреннее состояние и т. н. mailbox, куда виртуальная машина складывает сообщения. Переключение между процессами практически бесплатное, потому что процесс не экспонирует наружу никакие данные, его внутреннее состояние — его личное достояние, никто его не может изменить, кроме самого процесса, поэтому мы можем отвлечься от переключения между процессами и считать, что он выполняется в вакууме. Да, виртуальная машина может его остановить в любой момент, а потом продолжить выполнение с той же точки, но это будет именно что та же самая точка. Как заснул — так и проснулся, ничего специального для подготовки переключения делать не нужно. Как режим «гибернация» в компьютере.

Итак, процесс запускается и начинает проверять свой mailbox. Если он пуст, процесс тут же отдает управление обратно виртуальной машине. Если нет, вызывается функция обработки сообщения, которая получает на вход само сообщение и внутреннее состояние. Результатом её работы будет (без потери общности) — новое внутреннее состояние, которое виртуальная машина перезапишет у себя в куче. Проще пареной репы.

Вот пример такой функции для счетчика, атомарное увеличение на единицу:

def handle_info(:inc, state), do: {:noreply, state + 1}

Благодаря наличию mailbox’а, никакой гонки здесь быть не может: сообщения выстраиваются в очередь, и, пока предыдущее не обработано, следующее просто ждёт вызова. Поэтому изменения внутреннего состояния никогда не нужно делать синхронными; мы можем смело вернуть управление вызывающему процессу (тому, который отправил сообщение) сразу — после 10 сообщений :inc, внутренний счетчик увеличится на 10, без вариантов.

Но иногда окружающему миру может потребоваться узнать внутренний стейт того, или иного процесса (как я это сделал в строке iex(n2@am-victus)7> REPL’a). Иначе мы получим процесс Шрёдингера в интерпретации Канта: что-то там мяучит, жрёт процессорное время, но толку от него — ноль (это не совсем правда, конечно, потому что процесс может сам слать сообщения, ему позволены всякие сайд-эффекты, и т. д.). Но запросить внутреннее состояние иногда выглядит довольно осмысленным действием. И для этого (только для этого) потребуется синхронное сообщение (такое, которое остановит вызывающий процесс до получения ответа, или до наступления таймаута). В эрланге можно узнать внутреннее состояние процесса и напрямую, через :sys.get_state/1, но так делать не нужно. Просто создайте свой синхронный хендлер (синхронность вызова здесь — достигается при помощи абстракции :gen_server из OTP, на уровне виртуальной машины — все сообщения асинхронны).

@impl GenServer
def handle_call(:state, :from, state), do: {:reply, state}

Эта функция будет вызвана только когда в очереди сообщений — первым окажется :state, а значит — если до этого был асинхронный запрос на увеличение нашего счетчика (:inc) — то сначала счетчик увеличится, а потом — вернется.

Таким образом, мы никогда не окажемся в ситуации гонки, тут всё железно: first in → first out. Для высоконагруженных сильно конкурентных систем, впрочем, получение внутреннего состояния всегда окажется между какими-то двумя инкрементами, поэтому хотя то внутреннее состояние, которое вернется из прямого запроса, всегда будет актуальным на то время, когда был оно было запрошено, с точки зрения реального мира — смысла в нём будет не так много.

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

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

Например: тестирование

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

❯ mix finitomata.generate.test --module Turnstile

* creating test/finitomata/turnstile_test.exs
* Turnstile.Test has been created for Turnstile, do not forget to:
  ▹ amend assertions to fit your business logic
  ▹ add `listener: :mox` (or actual listener) to `Finitomata` declaration

Сгенерируется несколько тестов, каждый из которых проверит свой «путь» автомата, включая циклы, но исключая повторы, используя DSL, предоставляемый библиотекой. Их всего три, для данного автомата (код целиком показан для самого короткого, чтобы не загромождать текст):

defmodule Turnstile.Test do
  use ExUnit.Case
  import Finitomata.ExUnit
  import Mox

  @moduletag :finitomata

  describe "↝‹:* ↦ :idle ↦ :locked ↦ :unlocked ↦ :locked ↦ :down ↦ :*›" do
    # …
    test_path "path #0", %{finitomata: %{}, parent: _} = _ctx do
      # …
    end
  end

  describe "↝‹:* ↦ :idle ↦ :locked ↦ :unlocked ↦ :unlocked ↦ :locked ↦ :down ↦ :*›" do
    # …
    test_path "path #1", %{finitomata: %{}, parent: _} = _ctx do
      # …
    end
  end

  describe "↝‹:* ↦ :idle ↦ :locked ↦ :down ↦ :*›" do
    setup_finitomata do
      parent = self()
      [
        fsm: [
          implementation: Turnstile,
          payload: %{parent: parent},
          options: [transition_count: 4]
        ],
        context: [parent: parent]
      ]
    end

    test_path "path #2", %{finitomata: %{}, parent: _} = _ctx do
      :* ->
        # these validations allow `assert_payload/2` calls only
        #
        # also one might pattern match to entry events with payloads directly
        # %{finitomata: %{auto_init_msgs: [idle: :foo, started: :bar]} = _ctx
        assert_state(:idle)

        assert_state :locked do
          # assert_payload %{}
        end

      {:off, nil} ->
        assert_state :down do
          # assert_payload %{foo: :bar}
        end

        assert_state :* do
          assert_payload do
            # foo.bar.baz ~> ^parent
          end
        end
    end
  end
end

Остаётся только добавить свои business-specific проверки, и voilà — тест готов. Если он пройдет здесь, он пройдет в любой высоконкурентной среде, потому что данный процесс вообще никак не зависит от остальных процессов, а сам по себе тест — полностью асинхронный.

Вот, как-то так мы и живем на одних сообщениях, без прямых вызовов функций, и вообще без методов.

Удачного сообщения!