FSM（有限状态机） server的实现

wishel

很多server，比如淘宝之类的网站，是需要保持服务的状态的，也就是需要一个FSM逻辑。比如双方成交->买方付款->付款完成(银行扣款成功)->卖方确认收款->发货->买方收货。中间可能还有一些其他的事件和状态，比如付款失败，买方退货，卖方退款等等。
因此，需要设计一个应用层协议来支持这个FSM。据我了解，淘宝的通信层好像是用的ICE。

wishel

那么用ACE怎么样实现这样的FSM server比较好呢？查了一些有关FSM实现技术的资料，大概有以下几种方法：
1.        嵌套switch case方式。例如
event(int event) {
    switch (state) {
    case state1:
      switch (event) {
        case event1:
          state = state2;
          action1();
          break;
        case event2:
           action3();
           break;
        case event3:
           state = state2;
           break;
        }
      case state2:
      …….
      }
}
优点：对于简单的fsm，这种实现简单优雅而且高效。
缺点：但是如果fsm较大，维护较长的嵌套switch/case语句是非常困难且容易出错的。而且，很难将fsm的逻辑和action的代码进行比较好的隔离，本例中的action比较干净，但实际应用中action的实现很难抽取出这样简单清晰的表达方式。
2.        状态迁移表(transiton table)。例如：
addTransition(st1, event1 , st2, action1());
addTransition(st1, event2 , st1, action2());
addTransition(st2, event1 , st2, action2());
addTransition(st2, event2 , st1, NULL);
……
event(int event) {
  for (int i=0; i<transitions.size(); ++i) {
    Transition transition = transitions;
    if (state == transition.currentState && event== transition.event) {
      state = transition.newState();
      transition.action();
    }
  }
}
优点：FSM逻辑非常清晰，且和action的实现代码分离。特别好的一点是，可以在运行时动态修改fsm的逻辑。也可以预先创建多个table，在运行时再根据情况具体指定使用哪个。
缺点：主要短板是性能。当fsm比较大的时候，线性遍历整个table很花时间，可能难以接受。另外，支持这个table的代码量也不少，需要较多辅助函数。
3.        设计模式中的State pattern。这一模式综合了嵌套switch/case的高效率和状态迁移表的灵活性。《设计模式》上讲的很详细，就不赘述了。State pattern看起来和Strategy pattern很像，其实State是Strategy的一个特例。在State pattern中，concrete State有一个指向context类的reference，因为它需要访问context类中的方法。在Stragey pattern中则不需要这种关系。
优点：
1）        fsm逻辑和action的实现代码分离。Fsm逻辑分布于State的各子类中，action则在context类中实现。
2）        效率很高（多态调用虚函数）。性能基本与嵌套switch/case方式相同。
缺点：
1）        写各concrete State类的代码很枯燥乏味，尤其是状态比较多的时候，很容易让人头晕心烦。
2）        Fsm的逻辑分布于各子类中，不是集中在一处方便一览全貌。这样维护起来比较麻烦，有些类似switch/case方式。
4.        FSM编译器。
这个比较强悍。是在3的基础上，写一个编译器自动生成各concrete state类的代码。用户只要把fsm的table写好输入即可。这种技术比较高阶，暂时打算以后有机会再研究了。。。
优点：具备了State pattern的全部优点，又避免了State pattern的全部缺点。优雅，高效，且需要的编码量最少。
缺点：如果自己实现编译器，有一定的技术门槛。不过貌似有别人写好的，我见过java的，用起来相当简便。不过还是自己能写最好，用别人的工具一旦特别需要某个特定的功能它却没有，就只能很无奈很遗憾了。

[ 本帖最后由 wishel 于 2009-11-5 17:08 编辑 ]

wishel

再说下我对server的想法。
ACEr都知道，并发server主要有几种模型：reactor，proactor，多进程，多线程。
做server主要考虑核心价值是性能，当然其他价值点也很重要，比如可靠性，安全，公平等等，但这里暂时不管这些，专注于性能这一点。
那么这几种模型，谁的性能最好呢？有很多误解我觉得需要澄清一下，当然我说的也不一定对，如果有问题请各位坚决指正，不要客气。
注意performance和scalability的关系。常见的说法就是proactor比reactor性能好，异步嘛，性能当然要好于同步。其实这是错误的。
在多线程，同步，异步三种模式中，性能最好的是同步模式。
1.
线程管理需要占用系统资源，线程切换需要开销，同步和异步方式都没有这个缺点，所以多线程模式（不是指专为考虑利用多cpu而引入的多线程）性能最差。
2.
异步模式完成一个io需要两步：首先发起io，并生成一个result结构；然后等结束时填写该result结构，通知发起者io完成。而同步io则没有这些中间的损耗。
另外，proactor为了追求统一的处理，在异步io的时候，即使可以不阻塞立刻进行同步io，也会走上面这两步异步形式，而不是直接发起同步io。
那么为什么会有proactor性能好于reactor的说法呢，关键在于reactor的实现一般基于select，而select的算法复杂度是线性的（线性遍历fd set），当要处理的handle很多时，性能下降明显。而proactor的复杂度是常量的。也就是说proactor有较好的scalability，当并发量比较大的时候，要好于reactor。
所以说，“proactor性能好于reactor”的说法是有条件的，就是当并发量较大的时候。门槛是多少呢？我个人觉得如果不想实测就当64吧，因为windows就这么处理的，WFMO超过64就不支持了。Linux可以适当放宽些。
但是就算这个有条件的说法，也是有条件的，那就是reactor的实现是线性算法，当这个条件不成立的时候，一切都推翻了。比如linux上新的epoll，performance和scalability都极好，因此成了目前构建高性能高并发服务器的最佳模式。
3.
多线程模式的优点在于其逻辑是顺序逻辑，编程方便（指较少互斥访问共享资源时）。但是其performance和scalability都不是太好。尤其是线程数过多时，切换损耗非常高。
4.
此外也要注意公平性，也就是对一个连接（client）的处理，不能starve其他client。也就是说proactor或reactor的event处理时间不可过长，否则会造成其他client的envet处理长时间排队。如果实在无法避免，只能牺牲一些性能来换取公平，用多线程方式，由os的scheduler来公平的为每个线程调度执行时间。
5.
以上说的多线程模式不是指专为多cpu而引入的多线程。为充分利用多cpu server的处理能力，reactor和proactor也可以多线程的跑，但线程数与cpu数相关，不追求完美的话，设成2倍于cpu数量就可以了。最新版的《windows via c/c++》介绍完成端口的部分对这点有详细的分析，还提供了一个启发式算法。

综合以上，个人认为，高并发server的设计，在windows平台，最好用proactor（完成端口），在linux平台最好用reactor（epoll），在AIX和Solaris等有比较好的aio库的平台，也最好用proactor。其他平台不了解，不敢随便置评。

[ 本帖最后由 wishel 于 2009-11-5 17:05 编辑 ]

wishel

以下是我用State pattern + proactor实现的一个简单FSM server模型，欢迎大家评论交流。
下一步打算再做一个State + Reactor(epoll et)的，不过下周开始会比较忙了，可能会做的比较慢。
实现的过程中发现还是很不容易的，因为FSM的语义是同步的顺序的，而proactor的语义是异步并发，大异于人类的正常思维，每一个动作都分解成两步，两步都成功才能算成功，而第二步的完成通知是异步的（Proactor是魔鬼，非必不得以，千万不要放它出来。。。）。目前的想法是把2步都合成为同一个状态，但这2步又各作为这个状态的子状态。这种设计虽然不完美，但是目前我能想到的最好方式了，如果大家想到更好的方法，欢迎提出建议。
简介一下协议：
1)
State1：Server接受client连接后，读取client发来的请求。请求用一个字节表述，因此可以支持256种。目前只支持’r’，就是下载文件。如果请求合法（’r’），向client应答一个字节’y’，转为state2。否则应答’n’，状态不变，继续等待请求。
2)
State2：这时client（已收到应答’y’）需发送请求的文件名，约定最大长度为MAX_PATH的c字符串。Server收到后，判断是否存在该文件，是则应答’y’，进入state3，开始传送文件，否的话就应答’n’，返回state1，等待新请求。
3)
State3：传送文件，结束后关闭连接。出错也关闭连接，不再返回state1。

模型比较简单，其实可以修改下把传文件功能用ACE_Asynch_Transmit_File来做。可以修改交互命令协议，不是用一个字节，而是类似ftp，http之类的用一行来表示。还可加简单断点续传功能。这些就留在下一版本来做了。Linux + epoll reactor + sendfile + 命令行协议 + 断点续传。
测试我用的是gtest，真的是好东西。先写测试代码再开发实现，有利于提高设计的质量。Linux下有个工具nc是测试网络程序的好东东，不知道windows下面有没有类似的东西。

[ 本帖最后由 wishel 于 2009-11-12 20:24 编辑 ]

winston

好帖，加精华。
异步就比同步好，是不准确的。说epoll就比select好，其实也不准确。一切都要看条件。
技术要在合适的条件下，才能产生最大的效果。

wishel

原帖由 winston 于 2009-11-5 17:46 发表
好帖，加精华。
异步就比同步好，是不准确的。说epoll就比select好，其实也不准确。一切都要看条件。
技术要在合适的条件下，才能产生最大的效果。 ...

呵呵，确实select在特定条件下好于epoll。这个话题比较有趣。

当绝大多数连接都是活的时候，这时候随机访问n个event和顺序访问n个event已经没什么区别，相反顺序访问可能更有效率。就像磁带io和磁盘io的关系，如果只是顺序读写文件，磁带的性能要好于磁盘。

wishel

Epoll reactor + sendfile的做完了。命令行协议和断点续传没多大新意，就不做了。

Gtest代码和楼上的一样

[ 本帖最后由 wishel 于 2009-11-15 18:23 编辑 ]

wishel

现在还剩下2个遗憾：
1）        无法跨平台。在windows下的proactor转到linux下后性能很差，换epoll要换架构。
2）        Epoll reactor目前没有支持多线程。


所以下一步的有意义的工作是：
1）        修改linux下ACE_Asynch_Read_Stream，ACE_Asynch_Write_Stream，ACE_Asynch_Transmit_File。以epoll + sendfile来模拟实现。
2）        实现支持epoll reactor的leader/follower 线程池

wishel

配合新做的Epoll Proactor测试，FSMP做了个ACE_Asynch_Transmit_File版的。原来用的ACE_Asynch_Read_File，现在Epoll Proactor还不支持。