简单的工作流引擎的设计

最近工作中有几个项目因为逻辑太复杂,工作流比较复杂,如果手写工作量太大。而又因为不会用微软自家的工作量引擎,也感觉它的功能太多太复杂,觉得出了问题凭我刚学的C#水平不一定HOLD得住,所以设计并开发了一个简单的工作流引擎。

首先,我把这个工作量引擎定义为一个状态机。为了在工作流中持久的保存数据,不因一次请求没有让工作量执行结束或者系统停止而消失,在每个工作流的实例中持有一个存储空间UserSpace,用来存放数据(键值对)。一个工作流有许多个状态,其中有一个开始状态(Start)和若干个结束状态(Final, Error, Timeout等)。一类工作流包含了多个Task,每个Task有自己的依赖条件(状态依赖,请求参数依赖,工作量存储内容的依赖等等)和结束状态。每次要执行工作流时,要构造一个请求传给工作流的实例,工作量引擎判断出在Tasks中满足依赖的所有Task,根据一定规则(状态依赖,优先级等)挑选出一个Task来执行(如果有的话),执行完这个Task之后把请求重新抛给工作流,循环,知道工作流达到结束状态或者没有Task可执行。如果工作流的状态没有到结束状态的话,下次还可以接收请求并继续执行。

又因为工作流接收请求的时间不确定,这段时间可能发生各种事情,包括系统重启等,所以工作流肯定是不能放内存中的,需要序列化(字节流序列化,XML序列化或者其它方式)存储。每次Task执行后都要更新存储一次。第一次创建工作流之后,如果没有执行任何Task,也要存储一次(应该在创建并初始化工作流设置之后)。为了避免无意义的存储和安全考虑,在存储之前要去除掉工作流的UserSpace中的一些内容,比如user/request/response(自定义,这是我在web应用中用到的),如果有的话。

因为工作流是一个状态机循环,一个请求在被一个Task处理之后又会重新抛入状态机循环,为了避免原本只需要被一次处理的参数被多次使用,甚至造成死循环等后果,最好在Task执行结尾清理掉这些参数(要判断是否request参数和workflow的UserSpace中是否都要删除)。当然,Task也可以把数据存入workflow的UserSpace。

为了封装多个Task中可能的类似的行为,将Task的行为(处理函数还有各种事件回调机制)封装成IOperation接口,在这些方法中都是调用IOperation接口的实现类。

每个Task有一个FinalState属性,表示Task正常完成之后工作流的当前状态会改成的属性。如果Task中没错处理,正常执行完成,则workflow的CurrentState就会改成这个值。但考虑到在业务中有类似审核时拒绝,打回编辑状态,或者跳过某些阶段的情况,在Task中,也可以通过ReDispatch(workflow, request, state)手动控制状态跳转。调用了这个函数后就不会发生自动把workflow当前状态修改成当前task的FinalState的情况了。不过要注意的是,这个函数调用后并不会直接去把request重新抛给工作流,执行其他task,而是会简单处理后立刻返回,后面代码马上就好执行的。

顺便说一句,为了增加可扩展性,也方便在需要的时刻做处理,在工作流和Task的各个执行阶段(BeforeRequest, AfterRequst, BeforeProcessTask, OnFailRequirementsCheck等)都有事件回调,通过覆盖方法或注册处理函数的方式可以在这些时刻调用自定义的代码。

再来说下Task的requirements,包含多种条件,比如对状态的依赖(多个中只要满足一个就通过,后面其他的条件是都要满足才可),request参数依赖(string键),workflow的UserSpace内容的依赖(string键),对request的依赖(一个函数(request) => bool),对workflow的UserSpace的依赖(一个函数(request) => bool)。为了方便代码生成已经避免修改Task的定义,将其中函数形式的依赖的值放在一个类Conditions(自定义)中(这个类的静态方法)

考虑到工作流的使用场景非常可能有很多自定义的情况,所有Workflow,Conditions, Operation(s), WorkflowInitor(在workflow初始化和反序列化之后调用),以及工作流的持久化方式等都做成可扩展的形式,根据具体项目需求可以通过继承类或接口来改变实现方式,在workflow的持久化上,使用了策略模式,通过定义新策略可以定义新的序列号和反序列化的方式,比如我们项目中就采用了sql存储(本工作流系统中内置了内存和redis的支持),并且sql存储的表结构也可以自定义。

描述一下工作流的使用场景。 比如在创建一条记录的时候,先创建一个工作流的实例,构造一个请求request,把各种来源的需要的参数(比如HTTP请求参数,session内容,当前用户等)放入request.Parameters中,然后把这个request传给工作流workflow:

var workflow = new Workflow();
var request = new Request();
request.Parameters.Set("user", user);
// ......
var result = workflow.PostRequest(request);

这样工作流引擎就好自动执行状态机了。 每个工作流实例默认都有一个唯一的ID,但如果有特别需求的话,比如工作流ID需要与在CreateTask中创建的记录的ID有关联的话,可以在这个CreateTask的代码中,手动根据新记录ID修改workflow的ID值,只要确保在工作流第一次持久化之前修改ID就好了(从这个角度讲,要控制工作流的持久化是在真正需要时才持久化,如果工作流创建后会执行task的话,不应该多余的持久化,在本工作流引擎中已经这样做了)。

可以看到,这里有一个返回值result。但在状态机中怎么返回值呢,已经返回哪个task的值呢(如果执行了多个task的话)? 在task中有一个属性result,每次执行前都会清空,在Task的处理代码中可以设置这个result属性,里面存放了返回值,这个返回值会传给工作流并最终返回。

工作流的超时机制很简单,就不说了。

最后,关于工作流和Task的定义,如果每次自己手写代码就不方便了。所以采用了代码生成的方式,通过配置xml文件(本来设计了一套类似ruby的语法了,不过写得时候觉得太麻烦,就先用xml了, 将来可能改掉),生产Workflow和Tasks的代码,里面包含各状态的定义,工作流的定义,采用的配置(持久化策略,WorkflowInitor类,继承的Workflow类等,包含的Task列表),各Task的依赖和FinalState等。 然后我们只需要根据生产的代码在编译时报的错写Conditions, Operations(Task的行为), WorkflowInitor等等就好了。

在初步使用了本工作流引擎后,一个很复杂的多级审核(审核人构成也比较复杂),并且有比较多的打回之前阶段的业务,除XML配置之外,主要代码变得只有两块:创建和审核(并且这个审核只需要写一次通用化的代码,用到多个审核中,甚至可以用到其他类似业务中),开发和维护方便多了。

关于最小公倍数

求最大公约数的算法众所周知,使用辗转取余法(辗转相除法)

但怎么求n个数的最小公倍数呢,

常规解法有两种,

一种是质因数分解,设每个出现过的质因数 p[i]所出现的最大次数为a[i],则把所有Math.pow(p[i], a[i[)相乘即可,不过这种方法局限于

正整数

还有一种是假设两数分别为a, b,求出最大公约数gcd[0], a[1] = a/gcd[0], b[1] = b/gcd[0] ,再把a[i], b[i]这样处理直到a[i], b[i]互质为止,这是把所有的gcd[k] (k

(defn lcm [& nums]
  (let [index-of (fn [v l] 
    (loop [i 0] 
      ; get the index of value v in sequence l. assume v is in l
      (if (= (nth l i) v)
        i 
        (recur (inc i)))) ) 
    lcm-help (fn [now-nums origin-nums]
                (if (apply = now-nums)
                  (first now-nums)
                  (let [min-value (apply min now-nums)
                        min-value-index (index-of min-value now-nums)
                        origin-val (nth origin-nums min-value-index)
                        new-val (+ min-value origin-val)
                        now-nums-vector (vec now-nums)
                        new-now-nums-vector (assoc now-nums-vector 
                                              min-value-index new-val)
                        new-now-nums (seq new-now-nums-vector)]
                    (recur new-now-nums origin-nums))))]
      (lcm-help nums nums)))

(println (lcm 7 5/7 2 3/5))
(println (lcm 3/4 1/6))

输出结果为210, 3/2

PHP与Java中运行时获取调用类方法(静态方法)的类名的方法

因为看不惯FengOffice中的ORM框架(好像是Zend中的,不过没用过Zend,不清楚),觉得太繁琐,所以打算自己用PHP实现一个轻量级,方便,尤其要容易写Model和容易使用。

参考了Yii的orm框架的使用方式,或者说是ActiveRecord的使用方式,写了一个简单的orm,在实现的时候因为要在父类Model类中的静态方法中,动态获取调用它的是哪个类,从而知道使用的是Model的哪个子类。刚开始不清楚怎样获得,后来在一位学弟的提醒下知道了有get_called_class()这个方法可以动态获取调用者是哪个类,从而解决了这个问题。

果然,百度是百度不出什么东西的啊。这个orm框架在稍作完善后再放到github(zoowii)上吧,先不管这个。

因为学校学的主要语言是Java,所以想到Java中怎么解决这个问题,经过百度(因为十八大,谷哥不方便),找到了一篇帖子:
http://hi.baidu.com/kittopang/item/a04c9ed12ff32aefb2f77711

因为这篇帖子中的情况是获取当前类,而不是运行时使用父类的静态方法,在这个父类的静态方法中动态获取它的调用者的类名,两者情况还是不一样的。所以我写了点Java代码测试了一下。

// Test3.java
public class Test3 {
  // output the current class name of the source file, so always output Test3
  public static void f1() {
    String className = new Object() {
      public String getClassName() {
        String nm = this.getClass().getName();
        return nm.substring(0, nm.lastIndexOf(‘$’));
      }
    }.getClassName();
    System.out.println(className);
  }

  // also output Test3
  public static void f2() {
    String className = new SecurityManager() {
      public String getClassName() {
        return getClassContext()[1].getName();
      }
    }.getClassName();
    System.out.println(className);
  }

  public static void f3() {
    String clsName = new Throwable().getStackTrace()[1].getClassName();
    System.out.println(clsName);
  }

}
// Test4.java
public class Test4 extends Test3 {
  public static void main(String[] args) {
    f1();
    f2();
    f3();
  }
}

编译后执行java Test4后得到输出结果:

Test3

Test3

Test4

可见,只有第三种方法可以达到目的,也就是通过新建一个Throwable对象,调用getStackTrace()获取调用栈信息,对其中的第二个对象调用getClassName()方法。这种通过异常栈的方法获取信息的方法虽然能够达到目的,而且可以获取的信息很多,但到底不优雅,而且性能很差,但在不知道其他解决方案的情况下也只能这样了。如果有人知道其他方法的,请告诉我,谢谢。

Java执行机制

Java 源码编译—–javac将java源码编译为class

java源文件(.java)=>分析和输入到符号表=>注解(annotation)处理=>语义分析和生成class文件

class文件的内容

class文件的内容如下:

  • 结构信息:class文件格式版本号等信息=>所以高版本的jdk生成的.class文件低版本的jre无法运行,反之可以运行
  • 元数据:类继承、接口实现、属性和方法的声明、常量池等信息
    *方法信息:Java源文件中语句、表达式对应的信息,包括:字节码、异常处理器表、求值栈与局部变量区大小、求值栈的类型记录、调试用符号信息

例子:

// Hello.java
public class Hello {
    public static void sayHi() {
        System.out.println("Hello World!");
    }
    public static int add(int x, int y) {
        return x + y;
    }
    public static void main(String[] args) {
        sayHi();
        System.out.println(add(4, 5));
    }
}

使用javac -g Hello.java(使用javac Hello.java也可,但调试信息更少)产生Hello.class文件

再使用javap -c Hello可以反编译字节码,输出如下:

// Compiled from "Hello.java"
public class Hello {
public Hello();
    Code:
       0: aload_0
       1: invokespecial #1
       // Method java/lang/Object."":()V
       4: return        

  public static void sayHi();
    Code:
       0: getstatic     #2
       // Field java/lang/System.out:Ljava/io/PrintStream;
       3: ldc           #3
       // String Hello World!
       5: invokevirtual #4
       // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       8: return        

  public static int add(int, int);
    Code:
       0: iload_0
       1: iload_1
       2: iadd
       3: ireturn       

  public static void main(java.lang.String[]);
    Code:
       0: invokestatic  #5
       // Method sayHi:()V
       3: getstatic     #2
       // Field java/lang/System.out:Ljava/io/PrintStream;
       6: iconst_4
       7: iconst_5
       8: invokestatic  #6
       // Method add:(II)I
      11: invokevirtual #7
      // Method java/io/PrintStream.println:(I)V
      14: return
}

类执行机制

  • 字节码解释执行
    jvm有一套中间码,如invokestatic(调用static方法)、invokevirtual(调用对象实例方法)、invokeinterface(调用接口的方法)和invokespecial(调用private方法和方法)等。
    因此,jvm可以把这写中间码的指令解释执行,就像类似于脚本语言执行。只不过脚本语言执行的源文件是可读的文本文件,
    而jvm解释执行执行的是不可读的.class文件。

  • 字节码编译执行
    解释执行效率低,所以jvm可以在运行时把.class文件编译成机器码执行,这就是JIT编译。
    所谓的Hotspot 就是执行时对执行频率高的代码编译执行,执行频率低的代码解释执行。

关于Java对象占用内存大小

附加:以下内容很多错误,Java对象中还有很多其他内容, 比如指向类的指针,Flags(哈希值等),形状(是否是数组),如果是数组还有数组长度。后面才是正文内容。并且如果是String对象的话,String对象的正文部分是一个指向char[]的指针,这个char[]数组本身也有上面说的类型,Flags,形状,数组大小等基本信息和实际内容。并且在32bit和64bit的JVM上Java对象的基本结构占用内存也是不同的

昨天面试有一道题是关于Java内存占用的。题目是求出new String("a")Map map = new HashMap(); map.put("a", "a");

回来之后我检测了一下,通过观察创建对象前后(创建大量一样的对象求均值)的已使用堆(runtime.totalMemory() - runtime.freeMemory())内存大小的变化来计算Java对象的内存占用情况 。

代码是网上找来的:

import java.util.HashMap;
import java.util.Map;
public class Test5 {
    public static void main(String[] args) throws Exception {
        // Warm up all classes/methods we will use
        runGC();
        usedMemory();
        // Array to keep strong references to allocated objects
        final int count = 100000;
        Object[] objects = new Object[count];
        long heap1 = 0;
        // Allocate count+1 objects, discard the first one
        for (int i = -1; i < count; ++i) {
            Object object = null;
            // Instantiate your data here and assign it to object
            // object = new Object();
            // object = new Integer (i);
            // object = new Long (i);
            // object = new String ("a");
            Map object1 = new HashMap();
            object1.put("a", "a");
            // object1.put(new String("a"), new String("a"));
            // object = new byte [128][1]
            if (i >= 0)
                objects[i] = object1;
            else {
                object1 = null; // Discard the warm up object
                runGC();
                heap1 = usedMemory(); // Take a before heap snapshot
            }
        }
        runGC();
        long heap2 = usedMemory(); // Take an after heap snapshot:
        final int size = Math.round(((float) (heap2 - heap1)) / count);
        System.out.println("'before' heap: " + heap1 + ", 'after' heap: "
                            + heap2);
        System.out.println("heap delta: " + (heap2 - heap1) + ", {"
                            + objects[0].getClass() + "} size = " + size + " bytes");
        for (int i = 0; i < count; ++i)
            objects[i] = null;
            objects = null;
        }

    private static void runGC() throws Exception {
        // It helps to call Runtime.gc()
        // using several method calls:
        for (int r = 0; r < 4; ++r)
            _runGC();
    }

    private static void _runGC() throws Exception {
        long usedMem1 = usedMemory(), usedMem2 = Long.MAX_VALUE;
        for (int i = 0; (usedMem1 < usedMem2) && (i < 500); ++i) {
            s_runtime.runFinalization();
            s_runtime.gc();
            Thread.currentThread().yield();
            usedMem2 = usedMem1;
            usedMem1 = usedMemory();
        }
    }

    private static long usedMemory() {
        return s_runtime.totalMemory() - s_runtime.freeMemory();
    }

    private static final Runtime s_runtime = Runtime.getRuntime();
}

运行结果表明:

  • new String(“a”)占用24Bytes,
  • Map map = new HashMap(); map.put(“a”, “a”); 占用168Bytes,
  • Map map = new HashMap(); map.put(new String(“a”), new String(“a”));占用216Bytes.

原理:Java 的String 对象有四个属性:

privatefinalcharvalue[];
/** The offset is the first index of the storage that is used. */
privatefinalintoffset;
/** The count is the number of characters in the String. */
privatefinalintcount;
/** Cache the hash code for the string */
private inthash;// Default to 0

再考虑Java对象的8字节对齐,java采用utf16编码,每个char 占用2个字节, 另外,java对象有两个字(每个字2字节) 的头部,分别表示垃圾收集、hash码信息以及指向对象的类,即占有4个字节。 24字节应该还是差不多的。

不过网上还有种说法是一个空字符串都占用40个字节,长为1的字符串也是占用40个字节,不清楚怎么算的,昨天面试官说的也是大概这个数据。

引用:http://www.javaworld.com/javaworld/javatips/jw-javatip130.html?page=1

浏览器中的Scheme解释器

前两天用javascript写了一个scheme解释器,已经可以运行在node.js和浏览器中。代码放在github上了。
http://github.com/zoowii/SchemeScript

Features

  • 另外,http://aboutzoowii.duapp.com/app/js/SchemeScript 中可以在线演示
  • 支持自然数,布尔值(true, false),字符串(“…”),变量定义
  • 可以定义函数了,并调用自定义函数,可以嵌套。示例中有求斐波那契数列的
  • 有list, cons, car, cdr, list-len, n-th, typeof, +, -, *, /等函数
  • 支持lambda表达式,柯里化
  • 所有合法的标识符都可以被重定义,包括内置函数名
  • 控制结构有if, cond[else],都是作为内置函数实现的,可以赋给其他标识符,也可以重定义为其他值;cond控制结构的每一个条件分支都可以是多个form,执行时依次执行并返回最后一个form的值
  • 定义变量用define,定义函数用defn,也可以用define+lambda表达式定义函数

关于我的web服务器nodejsws

之前,因为闲得无聊,用NodeJS写了一个web服务器,叫nodejsws(https://github.com/zoowii/nodejsws)

这几天把这个项目稍微做了一下,不过以前是以提供少量动态内容的静态资源服务器为目的的,现在编程了一个PHP的web服务器,已经成功的在nodejs上安装并运行wordpress了。
nodejs采用nodejs编写,使用php-cgi提供动态服务,不过因为不知道如何在php-cgi运行一次后不自动退出,又不打算使用php-fpm等开源项目(想自己造轮子),没有使用fastcgi,所以还是cgi模式,效率比较低,有空打算把nginx的fastcgi模块的源码看一下。另外nodejsws有空用其他语言改写,觉得nodejs和python一样,写写原型或者一些特定领域的应用比较好,其他的还是用其他语言吧。
nodejsws还有很多的BUG,有空再解决吧。暂时告一段落。