状态机

本文源自《谈谈状态机》。

我经常在工作中听到状态机的概念，尤其是我们公司的支付系统，订单状态在接收到某个事件后需要从一个状态迁移到另一个状态。目前公司内的通用写法是定义一系列DAO，在需要状态迁移的时候调用这些DAO来改变状态。说实话，这种方式把状态的迁移分散在代码的各个角落里，很难搜索出来；为此开发常常会画一些状态转移的图来辅助编码，但缺点是文档不会经常更新，常常与代码不符，而且大多数文档的状态图也不规范。

我深感状态机是业务的重要组成部分，如果能在代码里把状态的转移聚集在一起，会对开发人员和维护人员带来极大的方便，我也因此听说过“状态模式”以及DSL(陆滔滔公司发明的语言)，来把状态相关代码放在一起的方法。但是在谈这个状态机的时候，如果没有相关概念，那谈不上用这些方法来解决问题。

本文是我读《谈谈状态机》的学习笔记，如果理解了状态机，那么即使不在编码时上用，就算在文档里面画个状态图也会顺手很多，理解也会深刻些，姑且不论文字的严谨性，我就是摘录些重要的文字，并加入我的一点看法。

在谈论一般意义的状态机时，我们先看看有限状态机，Finite State Machine，简称 FSM。

FSM 是一切的基础，也是能力最为有限的机器。在其能力之上是 CFL（Context Free Language），然后是 Turing Machine。

FSM 解决一个输入序列，经过 FSM，最终停留在什么状态这样一个问题。对于一个字符串是否以 \0 结尾（C 语言的字符串结构），FSM 可以给出答案。

CFL 是一切编程语言的基础。你写的一段 python 代码是否语法正确，CFL 能够给出答案。

Turing Machine 就是我们日常用各种算法写代码解决各种问题的基础。不较真地说，JVM 就是一个 Turing Machine。

再往上，就是未知的世界 —— Turing Machine 也解决不了的问题。

一个 FSM 首先有一系列的状态（state）。根据输入的不同，FSM 从一个状态切换到另一个状态。在这些状态中，有一些状态是特殊的状态 —— 接受状态（accept state）。如果输入处理完毕，FSM 停留在接受状态，那么 FSM 处理成功，否则失败。

我们看个例子。请听题：写一个状态机，验证一串二进制bit，包含偶数个 0 和奇数个 1。

合法的输入有：1，100，10101

不合法的输入有：10，00，1100

我们知道，写一段程序，搞定数据结构，就搞定了 80%。开发一个 FSM 也是一样，选取合适的状态是最最关键的。确定了状态之后，剩下的只是辛苦活。

对于这个简单的问题，大家一眼都能看出，可能存在四种状态。二进制串包含：

偶数个 0 和偶数个 1（记作 EE）
偶数个 0 和奇数个 1（记作 EO）
奇数个 0 和偶数个 1（记作 OE）
奇数个 0 和奇数个 1（记作 OO）

FSM 初始化的状态是 EE，一个 bit 都没处理，0 和 1 都是偶数个。FSM 的接受状态是 EO。如果最终到达这个状态，那么处理成功。

我们很容易能画出这样的状态机：

在构建 FSM 的过程中，不管你做了多少运算，为这个过程付出了多少脑力，最终，你得到的是一个：在 x 状态下，输入 a，得到 y 状态这样一个字典。这是 FSM 很多时候是最高效算法的原因：你已经把最艰难的部分编译进了 FSM，剩下的就是查表的操作。

以上描述的 FSM 是 DFA（Deterministic Finite Automaton），确定有限自动机。就是 给定一个状态，和一个输入，你总能确定地转换到下一个状态。

FSM 的应用主要是在 event based processing。一般如果系统在某个状态下，接收某些信息，处理后产生一个新的状态，都可以用 FSM 的思路来实现。最典型的使用场景是 network protocol，比如 OSPF（rfc2328 的主要篇幅就是在描述各种场景下状态的变化），再比如 TCP 3 way handshake，FTP 的建连和各种 command 的处理。

还有些场景涉及到具体的业务，比如用户的养成体系（用户从 注册用户 -> 已验证用户 -> 资料完整用户 -> 核心用户 的迁移），支付系统，预订系统也有 FSM 的影子。

完全是复制的，就这样吧O(∩_∩)O~