Сайт Романа ПарпалакаБлог20240709

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

9 июля 2024 года, 11:11

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

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

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

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

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

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

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

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

За публикацию комментария, находящегося на рассмотрении, отвечала та же кнопка, которая ранее управляла флагом 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}$$

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

Последний пункт особенно важно осознать: значения 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 таблицы, если для определения статуса нужно взять не просто значение из колонки, а доставать записи из соседней таблицы и находить последнюю из них? Действительно, чтобы понимать статус в ходе обработки документа, нужно провести дополнительные операции при выполнении и вообще потратить время на их программирование. С другой стороны мы будем хранить все исходные данные о событиях в системе. Есть и другие положительные моменты:

Поделиться

Можно ли надежно определить, по какому адресу открыли сайт? Ctrl

Читайте также

Управление зависимостями на примере composer
Недавно я объяснял Илье Бирману, как инструменты управления зависимостями помогают разрабатывать программное обеспечение. С его разрешения публикую адаптированный вариант.
2016

Оставьте свой комментарий


Формулы на латехе: $$f(x) = x^2-\sqrt{x}$$ превратится в $$f(x) = x^2-\sqrt{x}$$.
Выделение текста: [i]курсивом[/i] или [b]жирным[/b].
Цитату оформляйте так: [q = имя автора]цитата[/q] или [q]еще цитата[/q].
Других команд или HTML-тегов здесь нет.

Записи