Применение конечных автоматов в программировании
Когда мы пишем программы, часто управляем состоянием
Для управления состоянием полезно иметь представление о конечных автоматах. Конечный автомат — это математическая модель, состоящая из конечного набора состояний, переходов между этими состояниями и действий, выполняемых при этих переходах. Посмотрим, как можно применить идеи из теории конечных автоматов на примере системы комментариев в блоге.
Проблемы в примере без конечных автоматов
shown
. Комментарий создавался сразу опубликованным (shown = 1
), и позднее его можно было скрыть (shown = 0
).
Зачем вообще скрывать комментарии, если их можно удалить? Я сделал комментарии скрываемыми, чтобы можно было передумать, а также чтобы анализировать комментарии со спамом для борьбы с ним. Например, если с
Потом я решил добавить модерацию — предварительную проверку комментариев перед публикацией. Сделал по аналогии еще один флаг 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'
.
Сходу программисту может быть непонятно, какой набор значений должен быть у поля «статус». Но это не значит, что у моделируемых объектов нет набора состояний и возможных переходов между ними. Если их не выявить, код окажется более сложным и запутанным, чем мог бы быть. А если статус выделен правильно, получаем такие преимущества:
- проверка статуса простая, в ней нет дополнительных проверок других свойств;
- добавление новых состояний и переходов упрощается и не требует значительных изменений имеющегося кода;
бизнес-логика прозрачная, состояния моделируемых объектов и самих моделей имеют прямое соответствие.
Польза для общения с бизнесом
Последний пункт имеет отдельную ценность и требует дополнительного объяснения. Важным элементом в разработке проектов является общий язык. Статусы сущностей — это часть общего языка, на котором должны разговаривать не только разработчики, но и заказчики со стороны бизнеса. Не бойтесь использовать статусы при объяснении того, как работает система сейчас и как она будет работать после внесения изменений.
На этой фотографии пример того, как я рисовал конечный автомат заявок на выплаты во время проработки задачи с заказчиком. Видно, что у заявок много статусов, за разные переходы отвечают пользователи с разными ролями. По мере проработки задачи мы поняли, что одного нового статуса мало, нам нужен еще один дополнительный статус.
Состояния в больших системах
В крупных системах невозможно хранить информацию о состоянии обрабатываемых сущностей в одной колонке одной таблицы базы данных, как это было в примере выше.
Для примера представьте, что вы отправляете заявку на ипотечный кредит через личный кабинет на сайте банка. Пока вы заполняете анкету, фотографируете и прикрепляете документы, заявка находится в статусе «черновик». При отправке заявки вы переводите ее в статус «на проверке». Одни сервисы начинают выполнять автоматические проверки. В других сервисах происходит ручная проверка прикрепленных фотографий. Личный кабинет скорее всего не будет знать о таких мельчайших подробностях, как состояние запроса в ФНС на получение вашего ИНН (запрос еще не отправлен, ожидается ответ, ответ получен). Но если в ходе проверки были выявлены проблемы, личный кабинет их отобразит. Например, если паспорт прошел проверку, а справка по форме
Таким образом, за одним значением статуса
Состояния в append-only системах
На первый взгляд кажется, что для сохранения меняющегося статуса нужно делать UPDATE
записи в базе данных. Однако это несовместимо с иммутабельными объектами и с логическим продолжением принципа иммутабельности — с таблицами, в которых данные не изменяются, а только дописываются.
В
Зачем вообще делать
- Если записи в таблице никогда не обновляются, не нужно дополнительно программировать и хранить историю изменений. Вся история будет в основных таблицах с данными.
- Базы данных любят, когда данные в таблицах не обновляются, а только дописываются. Например, в PostgreSQL
UPDATE
— это на самом деле комбинацияDELETE
иINSERT
. Удаленные версии строккакое-то время хранятся на диске, их потом нужно дополнительно вычищать. Происходитчто-то вроде фрагментации, когда дисковое пространство используется неэффективно. Кроме того, в огромныхappend-only таблицах на поля вроде времени создания можно повесить эффективный и компактный индекс BRIN. - Не нужно заботиться об инвалидации закешированных строк из базы данных. Например, в кеше второго уровня в Доктрине из коробки лучше всего работает режим READ_ONLY. Инвалидация кеша приложения становится особенно проблематичной в системах с несколькими копиями приложения на разных серверах: когда один сервер делает
UPDATE
, другие об этом просто так не узнают и продолжат использовать старую версию из кеша.
Оставьте свой комментарий