白洁血战Node.js并发编程 01 状态机

摘要：状态机状态机是模型层面的概念，与编程语言无关。状态机具有良好的可实现性和可测试性。在代码里，这是一个，但是我们在状态机模型中要把他理解为事件。

这一篇是这个系列的开篇，没有任何高级内容，就讲讲状态机。

状态机是模型层面的概念，与编程语言无关。它的目的是为对象行为建模，属于设计范畴。它的基础概念是状态（state）和事件（event）。

对象的内部结构描述为一组状态S1, S2, ... Sn，它的行为的trigger，包括内部的和外部的，描述成为一组事件E1, E2, ... En，在任何状态下，任何事件到来，对象状态的改变用Sx -> Sy的状态迁移（State Transition）来描述，这个状态迁移就是对象的行为（behavior）。

对对象行为的完备定义就是{ S } x { E }的矩阵，如果存在(Sx, Ey)的组合未定义行为，这个对象行为模型在设计层面上就不完备，当然实际的代码不可能没有行为，这往往就是错误发生的地方。

状态机具有良好的可实现性和可测试性。完备定义的状态机很容易写出对应的代码，也很容易遍历全部的状态迁移过程完成测试，当然这只意味着代码实现和设计（模型）相符，并不意味着设计是正确的。

设计的正确性是一个复杂的多的话题，严格的定义是设计符合Specification。什么是符合Specification？要去看Robin Milner, Tony Hoare, Leslie Lamport等人的书了，老实说我也不懂，所以就此打住。

这篇文章不会详细介绍状态机，网上有非常多的资料，四人帮的书上有State Pattern - OO语言下的状态机实现，UML有State Diagram，是非常好的图示工具；这里只给出一个代码例子，对照这个实例帮助理解状态机模型的代码实现。

假定我们要解决这样一个任务：我们有一个模块是为了存储（save）一个文件，写状态机的目的是为了解决并发操作时排队存储的请求，因为请求是并发的，如果写入文件的io操作也是并发的话，这个文件可能被损坏。这是一个非常常见的应用场景。

这个模块定义有三种状态：

Idle， 这是不工作的状态；

Pending，这是等待工作的状态，等待的目的是为了，如果在很短的时间内出现连续多次的写入请求，我们只写入最后一个，减少io操作的次数；

Working，该状态下在执行写入操作，如果在执行io操作的时候收到写入请求，我们把请求内容保存在一个临时的位置；

Idle状态没有任何特殊资源，只有一个save请求事件；当有save请求时，它迁移到Pending状态。

Pending状态具有的特殊资源是一个timer，它可能有两个事件：来自外部的save请求，和来自内部的timeout。在JavaScript代码里，这是一个callback，但是我们在状态机模型中要把他理解为事件。在Pending状态中如果有save请求，不发生状态迁移，新的请求数据会覆盖旧的版本，原来的timer会被清除，重新开始新的timer。在timeout发生时，迁移到Working状态。

Working状态在进入时会启动存储文件的操作，它可能有两个事件：来自外部的save请求，和来自内部的保存文件操作的异步返回，同样的，它也被理解为一个（内部）事件。当外部的save请求到来时，该请求被保存在内部的next变量里；当文件操作返回时：

如果操作成功

如果存在next，向Pending状态迁移

如果不存在next，向Idle状态迁移

如果操作失败

如果存在next，向Pending状态迁移，用next作为数据

如果不存在next，也向Pending状态迁移，仍然使用当前数据，相当于等待后retry

我偷个懒，没给出图示，实际上这样的语言描述不如State Diagram来得直观。下面的表格是上述语言描述的归纳，史称状态迁移表（State Transition Table），有了State Diagram或者State Transition Table，任何人写出来的代码都一样。为了表述清晰，表中把Working状态的文件操作返回分成了两个事件：success和error。

下面是代码，首先有个base class，三个状态都继承自这个base class：

class State {

  constructor(ctx) {
    this.ctx = ctx
  }

  setState(nextState, ...args) {
    this.exit()
    this.ctx.state = new nextState(this.ctx, ...args)
  }

  exit() {}
}

在状态机的代码实现上，标志性的方法名称是setState，它负责状态迁移；其次是enter和exit，分别对应进入该状态和离开该状态。

状态机模式（State Pattern）的一个显著的编程收益是：每个状态都有自己的资源，在迁入该状态的时候建立资源，在离开该状态的时候释放资源，这很容易保证资源的正确使用。

在上述代码中，constructor充当了enter逻辑的角色，所以没有提供独立的enter方法；JavaScript Class是一个语法糖，没有和constructor相对应的destructor，所以我们这里写一个exit函数，如果继承类里没有exit逻辑，这个基类上的方法就是一个fallback。

ctx是一个外部容器，相当于所有状态对象的上下文（context），它同时具有一个叫做state的成员，该成员是一个Idle，Pending，或者Working类的实例；无论ctx.state是哪个状态，ctx都把save方法forward到state上，这样写是一个很标准的State Pattern。

setState的实现有点tricky，是JavaScript的特色。它首先调用当前类的exit函数迁出状态，然后使用new来构造下一个类，这意味着第一个参数nextState是一个构造函数；后面的参数使用了spread operator，把这些参数传入了构造函数，同时把新对象安装到了ctx，即把自己替换了；这不是唯一的做法，是比较简洁的一种写法。

Idle类的实现非常简单，在save的时候用data作为参数构造了Pending对象。

class Idle extends State{

  save(data) {
    this.setState(Pending, data)
  }
}

Pending类的save方法里保存了data和启动timer。它的构造函数重用了save方法。因为JavaScript的clearTimeout方法是安全的，这样写没什么问题。

exit函数实际上没有必要，但这样书写是推荐的，它确保资源清理，如果未来设计变更出现其他的状态迁出逻辑，这个代码就有用了。

timeout时Pending向Working状态迁移。

class Pending extends State {

  constructor(ctx, data) {
    super(ctx)
    this.save(data)
  }

  save(data) {
    clearTimeout(this.timer)
    this.data = data 
    this.timer = setTimeout(() => {
      this.setState(Working, this.data) 
    }, this.ctx.delay)
  }

  exit() {
    clearTimeout(this.timer)
  }
}

Working代码稍微多点，但是对照状态迁移表很容易读懂。不赘述每个方法了。保存文件的操作采用了先写入临时文件然后重命名的做法，这是保证文件完整性的常规做法，系统即使断电也不会损坏磁盘文件。

class Working extends State {

  constructor(ctx, data) { 
    super(ctx)
    this.data = data 

    // console.log("start saving data", data)
    let tmpfile = path.join(this.ctx.tmpdir, UUID.v4())
    fs.writeFile(tmpfile, JSON.stringify(this.data), err => {

      if (err) return this.error(err)
      fs.rename(tmpfile, this.ctx.target, err => {

        // console.log("finished saving data", data, err)
        if (err) return this.error(err)
        this.success()
      }) 
    })
  } 

  error(e) {
    // console.log("error writing persistent file", e)
    if (this.next)    
      this.setState(Pending, this.next)
    else
      this.setState(Pending, this.data)
  }

  success() {
    if (this.next)
      this.setState(Pending, this.next)
    else 
      this.setState(Idle)
  }

  save(data) {
    // console.log("Working save", data)
    this.next = data
  }
}

最后是ctx，我们在实际项目中称之为Persistence。它初始化时设置state为Idle状态；把所有的save操作都forward到内部对象state上。

class Persistence {

  constructor(target, tmpdir, delay) {
    this.target = target 
    this.tmpdir = tmpdir
    this.delay = delay || 500
    this.state = new Idle(this) 
  }

  save(data) {
    this.state.save(data)
  }
}

这一篇粗略的讲了两个问题：状态机模型和状态机模式（State Pattern）。他们两个不是一回事。

状态机模式是一种写法，上述写法不唯一；不使用Class，仅仅在Persistence类中使用（枚举）变量表示状态也是可以的，使用Class则相当于用变量类型来代表状态。

状态机模式的显著优点在于：

不同状态的资源和行为逻辑分开

在setState, enter, exit等标志性方法中不需要使用if / then或switch语句

在对象行为定义发生变化时，修改容易，不易犯错误；感谢enter和exit的封装，它强制了资源回收逻辑

状态机模型的意义对后面的内容更为重要。上面的例子具有这样几个特征：

状态具有显式定义

事件内外有别

外部事件对所有状态成立，因此Persistence类的使用非常简单，从外部其实看不到内部有什么状态定义，黑盒意义上说，Persistence是无态的，这对使用便利性来说极为重要；

内部事件仅仅对某些状态成立，所有异步函数的返回都理解为事件，而且是唯一的内部事件；

从并发角度说，Persistence类是一个同步器（Synchronizer），即并发的save操作在这里被排序执行了；当然我们没有设计更复杂的逻辑，例如任务队列，但显然那不是很难；

纯粹的状态机（automata）对于并发编程是无力的，这是一种共识，因为并发带来的状态组合会迅速爆炸状态空间，我们要找到办法对付这个问题，此其一。

其二，实际的程序模块组合时常见包含关系，用经典的状态机模型会产生组合状态机（Hierarchical State Machine），它的代码书写远比上述例子的Flat State Machine难写，除非在语言一级或者有类库支持，否则可读性和可维护性都很差，设计变更时代码改动幅度非常大，不是解决常见问题的好办法，虽然在一些特殊应用领域卓有建树，例如嵌入式设备的通讯协议栈。

事件(Event)和线程(Thread)是形式上对立，但是数学上对等，的两个编程方式。两者各有利弊，战争也是古老的，你在网络上很容易搜索到Why Event (Model) is Evil或者Why Thread (Model) is Evil的学术文章，都有大量的支持者。

Node.js的与众不同之处在于它的强制non-blocking i/o设计。这给习惯Thread编程的开发者制造了麻烦，所以在过去的几年里新的过程原语被发明出来解决这个问题，包括promise，generator，async/await。bluebird的使用者越来越多，而caolan的曾经很流行的async库用户越来越少。

但是众所周知JavaScript语言是事件模型的。在基础特性上寻求类thread编程形式去解决一切问题本身就是表里不一的，而且promise和async/await的实现本身也有很多不尽人意的地方。

这让我们倒回来思考两个问题：

寻求各种CPS（Continuation Passing Style）是解决non-blocking i/o的必经之路吗？

事件和状态机模型真的没有办法写规模化的并发程序吗？

Node原作者Ryan Dahl最近在一次访谈里说了他对Node的看法。他说在最初的两三年中他是狂热的支持Node的强制non-blocking i/o设计的，达到那种认为“原来我们都做错了”的程度，但是慢慢的他的态度发生了转变，尤其是在接触了Go语言之后；现在他的看法是，最初他以为Node可以做到是end-all或者for-all的，但是现在他没那么有信心了，在并发编程上他认为Go可能是更好的设计。

我的个人观点，谈Node必谈callback hell的开发者，并不熟悉在Event Model下的并发编程技术，promise和async/await本质上，绝大多数情况下是在serialize过程，如果只是serialize，那么结果和blocking i/o的编程并不会有区别。Promise对parallel的支持很有限，它只是在serial的过程序列上偶尔撒一点parallel的flavor。而且如果你喜欢的就是Thread Model，那么就应该选择对它有良好支持的编程语言或环境，例如Go或者fibjs。

如果你像我一样，喜欢JavaScript语言的简单，喜欢Event Model的简单，而不只是因为Node有良好的生态圈和海量的npm包可用而选择了Node——如果你只是因为这两点选择了Node，你肯定会后悔的——那么摆在我们面前的问题就是：事件模型，显式状态，non-blocking i/o，我们能不能找到一种办法，一种end-all和for-all的办法，最好能够直接体现在代码形式上，或者至少体现在一个简单、直觉、不易错、同时保持经典状态机模型的完备性的Mental Model上，能够为复杂的并发编程问题建模和书写代码？

在这里经典状态机模式可以给我们一个简单启迪：我们不仅可以用值来表示状态，我们也可以用对象类型表示状态，而且有明显的收益。同样的，在事件模型下解决并发问题的关键，就是把这个设计继续向前推进一步，我们还可以用结构来表示状态。具体怎么写和怎么思考建模，则是这个系列文章的主旨。

这在数学层面上非常容易理解：所谓并发编程，它就是在structure过程（Rob Pike）。函数或者类函数，包括promise，async function，generator，coroutine，他们是Thread Model下的（黑盒）原语和原语组合，对应的，我们要找到事件模型下的显式状态方法来应对这个问题，如果能做到这一点，我们就可以回到纯粹的事件模型下编写程序。

这个结果并不难，但是，它也确实有一段路要走，我们需要仔细梳理过程原语的优点缺点，梳理并发编程的本质，梳理常见问题的各种编程方式，最后回到我们的事件模型和状态机上来。等这个系列写完，你也读完，我向你保证，你再次看到callback函数时会觉得原来它那么简单且美。

下一篇我们开始谈并发编程，敬请期待。