Применение конечных автоматов в программировании

Когда мы пишем программы, часто управляем состоянием каких-либо сущностей. Набор состояний имеет место даже в простейших случаях: кнопка нажата или отпущена, комментарий опубликован или скрыт.

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

Проблемы в примере без конечных автоматов

Когда-то давно комментарии в S2 имели всего два состояния, закодированных флагом shown. Комментарий создавался сразу опубликованным (shown = 1), и позднее его можно было скрыть (shown = 0).

Зачем вообще скрывать комментарии, если их можно удалить? Я сделал комментарии скрываемыми, чтобы можно было передумать, а также чтобы анализировать комментарии со спамом для борьбы с ним. Например, если с какого-то IP-адреса будет много спама, этот адрес можно забанить.

Потом я решил добавить модерацию — предварительную проверку комментариев перед публикацией. Сделал по аналогии еще один флаг sent, который хранит информацию о том, был ли разослан этот комментарий подписавшимся авторам предыдущих комментариев.

Если режим предварительной проверки выключен, набор состояний остается таким же:

• shown=1, sent=1 — комментарий опубликован и разослан сразу в момент создания;
• shown=0, sent=1 — комментарий скрыт.

А в режиме с включенной предварительной проверкой появляется новое состояние:

• shown=0, sent=0 — комментарий в момент создания только записан в БД, его должен одобрить модератор;
• shown=1, sent=1 — комментарий опубликован модератором, в момент публикации он рассылается;
• shown=0, sent=1 — комментарий скрыт после публикации.

За публикацию комментария, находящегося на рассмотрении, отвечала та же кнопка, которая ранее управляла флагом shown. В обработчик ее нажатия добавилось только одно условие: если в момент изменения shown с 0 на 1 комментарий еще не разослан, он рассылался. Таким образом, переходы между этими состояниями можно отобразить в виде такой диаграммы:

$$\usetikzlibrary{arrows} \begin{tikzpicture}[node distance=4cm,font=\sffamily] \tikzset{ mynode/.style={rectangle,rounded corners,draw=black,thick, inner sep=0.7em, text width=7em,text centered}, myarrow/.style={->, >=latex', shorten >=1pt, shorten <=2pt,thick} } \node[mynode,fill=yellow!10] (moder) {\shortstack{На проверке\\\tt shown=0\\\tt sent=0}}; \node[mynode, right of=moder,fill=green!10] (pub) {\shortstack{Опубликован\\\tt shown=1\\\tt sent=1}}; \node[mynode, right of=pub,fill=gray!10] (hidden) {\shortstack{Скрыт\\\tt shown=0\\\tt sent=1}}; \draw[myarrow] (moder) to[in=130,out=50] node[above] {рассылка} (pub); \draw[myarrow] (pub) to[in=130,out=50] (hidden); \draw[myarrow] (hidden) to[in=-50,out=-130] (pub); \end{tikzpicture}$$

Если присмотреться к этой диаграмме, можно заметить недостаток: из состояния «на проверке» можно перейти только в состояние «опубликован», при этом комментарий будет разослан авторам предыдущих комментариев. Но что делать, если комментарий проверку не прошел? Спам хотелось бы отправить напрямую в состояние «скрыт», минуя состояние «опубликован».

Когда я увидел на практике необходимость такого перехода, то запрограммировал новую кнопку «оставить скрытым и не рассылать», которая (внимание!) изменяла значение флага sent с 0 на 1 без фактической рассылки комментариев. Таким образом, поменялся смысл флага sent: раньше он указывал на то, что комментарий был разослан, а теперь указывает на отсутствие необходимости разослать комментарий.

$$\usetikzlibrary{arrows} \begin{tikzpicture}[node distance=4cm,font=\sffamily] \tikzset{ mynode/.style={rectangle,rounded corners,draw=black,thick, inner sep=0.7em, text width=7em,text centered}, myarrow/.style={->, >=latex', shorten >=1pt, shorten <=2pt,thick} } \node[mynode,fill=yellow!10] (moder) {\shortstack{На проверке\\\tt shown=0\\\tt sent=0}}; \node[mynode, right of=moder,fill=green!10] (pub) {\shortstack{Опубликован\\\tt shown=1\\\tt sent=1}}; \node[mynode, right of=pub,fill=gray!10] (hidden) {\shortstack{Скрыт\\\tt shown=0\\\tt sent=1}}; \draw[myarrow] (moder) to[in=140,out=40] node[above] {\shortstack{Одобрить\\ (+рассылка)}} (pub); \draw[myarrow] (moder) to[in=-120,out=-60] node[below] {Оставить скрытым и не рассылать} (hidden); \draw[myarrow] (pub) to[in=140,out=40] node[above] {Скрыть} (hidden); \draw[myarrow] (hidden) to[in=-40,out=-140] node[below,pos=0.7] {Опубликовать} (pub); \end{tikzpicture}$$

В итоге мы получили следующие проблемы:

• состояние комментария определяется косвенно по набору значений отдельных признаков show и sent;
• признак sent потерял свой первоначальный смысл, его значение уже не говорит о том, произошла ли рассылка комментария;
• признаки, по которым определяется состояние, не могут меняться независимо: например, набор значений shown=1 и sent=0 не имеет смысла.

Последний пункт особенно важно осознать: значения shown=1 и sent=0 можно получить либо в результате ошибки в коде, либо прямым редактированием базы данных. Выходит, такая модель данных может кодировать несуществующее состояние, и это свидетельствует об ошибке проектирования.

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

Как хранить и обрабатывать статусы

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

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

$$\usetikzlibrary{arrows,positioning} \begin{tikzpicture}[font=\sffamily] \tikzset{ block/.style={rectangle,rounded corners,draw=black,thick, inner sep=0.7em, text width=8em,text centered}, myarrow/.style={->, >=latex', shorten >=1pt, shorten <=2pt,thick} } \node[block,fill=yellow!10] (moder) {\shortstack{На проверке\\\tt status=pending}}; \node[block, above right=0cm and 3cm of moder,fill=green!10] (pub) {\shortstack{Опубликован\\\tt status=published}}; \node[block, below right=0cm and 3cm of moder,fill=gray!10] (hidden) {\shortstack{Скрыт\\\tt status=hidden}}; \draw[myarrow] (moder) to[in=180,out=30] node[above] {\shortstack{Одобрить\\ (+рассылка)}} (pub); \draw[myarrow] (moder) to[in=180,out=-30] node[below] {Отклонить} (hidden); \draw[myarrow] (pub) to[in=120,out=-120] node[left] {Скрыть} (hidden); \draw[myarrow] (hidden) to[in=-60,out=60] node[right] {Опубликовать} (pub); \end{tikzpicture}$$

После этого везде в коде вместо проверки двух разных свойств shown и sent нужно проверять значение одного свойства status. Например, в запросе для вывода комментариев читателям блога нужно писать не WHERE shown=1, а WHERE status='published'.

Сходу программисту может быть непонятно, какой набор значений должен быть у поля «статус». Но это не значит, что у моделируемых объектов нет набора состояний и возможных переходов между ними. Если их не выявить, код окажется более сложным и запутанным, чем мог бы быть. А если статус выделен правильно, получаем такие преимущества:

• проверка статуса простая, в ней нет дополнительных проверок других свойств;
• добавление новых состояний и переходов упрощается и не требует значительных изменений имеющегося кода;
• бизнес-логика прозрачная, состояния моделируемых объектов и самих моделей имеют прямое соответствие.

Польза для общения с бизнесом

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

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

Состояния в больших системах

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

Для примера представьте, что вы отправляете заявку на ипотечный кредит через личный кабинет на сайте банка. Пока вы заполняете анкету, фотографируете и прикрепляете документы, заявка находится в статусе «черновик». При отправке заявки вы переводите ее в статус «на проверке». Одни сервисы начинают выполнять автоматические проверки. В других сервисах происходит ручная проверка прикрепленных фотографий. Личный кабинет скорее всего не будет знать о таких мельчайших подробностях, как состояние запроса в ФНС на получение вашего ИНН (запрос еще не отправлен, ожидается ответ, ответ получен). Но если в ходе проверки были выявлены проблемы, личный кабинет их отобразит. Например, если паспорт прошел проверку, а справка по форме 2-НДФЛ — нет, вы увидите это на сайте с дальнейшими инструкциями. Вся заявка перейдет в статус «на доработке» с ожиданием ваших действий.

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

Состояния в append-only системах

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

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

Зачем вообще делать append-only таблицы, если для определения статуса нужно взять не просто значение из колонки, а доставать записи из соседней таблицы и находить последнюю из них? Действительно, чтобы понимать статус в ходе обработки документа, нужно провести дополнительные операции при выполнении и вообще потратить время на их программирование. С другой стороны мы будем хранить все исходные данные о событиях в системе. Есть и другие положительные моменты:

• Если записи в таблице никогда не обновляются, не нужно дополнительно программировать и хранить историю изменений. Вся история будет в основных таблицах с данными.
• Базы данных любят, когда данные в таблицах не обновляются, а только дописываются. Например, в PostgreSQL UPDATE — это на самом деле комбинация DELETE и INSERT. Удаленные версии строк какое-то время хранятся на диске, их потом нужно дополнительно вычищать. Происходит что-то вроде фрагментации, когда дисковое пространство используется неэффективно. Кроме того, в огромных append-only таблицах на поля вроде времени создания можно повесить эффективный и компактный индекс BRIN.
• Не нужно заботиться об инвалидации закешированных строк из базы данных. Например, в кеше второго уровня в Доктрине из коробки лучше всего работает режим READ_ONLY. Инвалидация кеша приложения становится особенно проблематичной в системах с несколькими копиями приложения на разных серверах: когда один сервер делает UPDATE, другие об этом просто так не узнают и продолжат использовать старую версию из кеша.