gsharma / state-machine

An FSM framework for creating Automaton

Finite State Machine

An implementation of a simple FSM framework that allows both forward and backwards state transitions. At the moment, idempotency of state transitions is completely ignored. This could change and the machine could be enhanced to handle retries for idempotent state transitions.

The FSM framework does not limit users choice between a Mealy or a Moore type of FSM. In the practical sense, most machines are Mealy machines in that the transitions between states are a function of both the from-state as well as the inputs accompanying the transition. The TransitionFunctor is deliberately written in a way to afford this choice to users.

FSM Usage Manual

Core Concepts

1. State

State is used to model a point in time/snapshot state of a system. The FSM works to transition between states.

2. Transition

State transitions are available via extending the transition functor to provide a tuple of {fromState, toState} and the business logic that will allow the FSM to transition either forward or backward between them.

3. Flow

A flow can and does typically represent a thread of execution. The idea being that you set up a type of FSM once (when the process starts up and before the FSM should do any useful work) with all its states and transitions between them. Every thread of execution can then be modeled as a synchronous or asynchronous flow that spans the life of the application thread. At the end of this thread's request lifecycle, the flow can be stopped. The FSM itself is still setup to be used by other flows.

4. Flow Mode

Flows can be configured to operate in one of 3 modes: a. AUTO_ASYNC: auto progress through transitions asynchronously on a thread different from the caller thread. Note that AUTO_ASYNC automatically calls Flow.stopFlow() b. AUTO_CALLER_THREAD: auto progress through transitions on the caller thread. c. MANUAL: manually progress through transition.

5. Rewind Mode

Failure cases during state transitions present the FSM with options to rewind and proceed in the opposite direction. 3 rewind modes are available: a. ONE_STEP: rewind backwards one step only b. ALL_THE_WAY_STEP_WISE: rewind backwards all the way to INIT state but transition step-wise c. ALL_THE_WAY_HARD_RESET: rewind backwards all the way abruptly without trying to transition between individual states; effectively reset to INIT in one shot

6. Hysteresis

In order to avoid additional complexity, Hysteresis is not explicitly baked into the FSM and is left as a responsibility of the Transition implementers.

7. Flows & Epochs

It is worth mentioning that a flow does not correspond to an epoch. Modeling an epoch is left to the users of the FSM based on what events they consider significant enough to tick an epoch.

Modes of Operation

1. Manual Sync mode

This function illustrates how the FSM can be manually transitioned through its states. This mode provides total control over all transitions.

public void manualSyncMode() throws StateMachineException {
  // helper code for states and transitions is farther down
  // op1. prep transitions
  final TransitionNotStartedVsA toA = new TransitionNotStartedVsA();
  final TransitionAVsB AtoB = new TransitionAVsB();
  final TransitionBVsC BtoC = new TransitionBVsC();

  // op2. load up the fsm with all its transitions
  final StateMachineConfiguration config = StateMachineConfigurationBuilder.newBuilder()
      .flowMode(FlowMode.MANUAL).rewindMode(RewindMode.ALL_THE_WAY_HARD_RESET)
      .resetMachineToInitOnFailure(true).flowExpirationMillis(0).build();
  final StateMachine machine = StateMachineBuilder.newBuilder().config(config).transitions()
      .next(toA).next(AtoB).next(BtoC).build();
  
  // res2. check that fsm should be alive
  System.out.println(String.format("fsm is alive: %s", machine.alive()));

  // op3. start a flow
  final String flowId = machine.startFlow();

  // res3. check that fsm is in INIT
  System.out.println(String.format("fsm is in %s state", machine.readCurrentState(flowId)));

  // op4a. execute a flow transition: INIT->A
  boolean transitioned = machine.transitionTo(flowId, toA.getToState());

  // res4a. check that fsm is in A state
  System.out.println(String.format("fsm is in %s state", machine.readCurrentState(flowId)));

  // op4b. execute a flow transition: A->B
  transitioned = machine.transitionTo(flowId, AtoB.getToState());

  // res4b. check that fsm is in B state
  System.out.println(String.format("fsm is in %s state", machine.readCurrentState(flowId)));

  // op4c. execute a flow transition: B->C
  transitioned = machine.transitionTo(flowId, BtoC.getToState());

  // res4c. check that fsm is in C state
  System.out.println(String.format("fsm is in %s state", machine.readCurrentState(flowId)));

  // op5. stop the flow
  System.out.println(String.format("fsm flowId: %s is stopped: %s", flowId, machine.stopFlow(flowId)));

  // op6. stop the fsm
  System.out.println(String.format("fsm is alive: %s", machine.alive()));
  machine.demolish();
  System.out.println(String.format("fsm is alive: %s", machine.alive()));
}

2. Auto Async mode

The auto async mode enables automatic transition of the FSM through its states but in a background thread.

public void autoAsyncMode() throws Exception {
  // op1. prep transitions
  final TransitionNotStartedVsA toA = new TransitionNotStartedVsA();
  final TransitionAVsB AtoB = new TransitionAVsB();
  final TransitionBVsC BtoC = new TransitionBVsC();

  // op2. load up the fsm with all its transitions
  final StateMachineConfiguration config = StateMachineConfigurationBuilder.newBuilder()
      .flowMode(FlowMode.AUTO_ASYNC).rewindMode(RewindMode.ALL_THE_WAY_HARD_RESET)
      .resetMachineToInitOnFailure(true).flowExpirationMillis(0).build();
  final StateMachine machine = StateMachineBuilder.newBuilder().config(config).transitions()
      .next(toA).next(AtoB).next(BtoC).build();

  // res2. check that fsm should be alive
  System.out.println(String.format("fsm is alive: %s", machine.alive()));

  // op3. start a flow
  final String flowId = machine.startFlow();

  // op4. give it a lil breather to finish running
  Thread.sleep(10L);

  // op5. stop the fsm, flow will auto-stop
  System.out.println(String.format("fsm is alive: %s", machine.alive()));
  machine.demolish();
  System.out.println(String.format("fsm is alive: %s", machine.alive()));
}

There is another option to allow doing it on the caller thread itself via the FlowMode.AUTO_CALLER_THREAD

public void testStateMachineFlowAutoCallerThread() throws Exception {
  // op1. prep transitions
  final TransitionNotStartedVsA toA = new TransitionNotStartedVsA();
  final TransitionAVsB AtoB = new TransitionAVsB();
  final TransitionBVsC BtoC = new TransitionBVsC();

  // op2. load up the fsm with all its transitions
  final StateMachineConfiguration config = StateMachineConfigurationBuilder.newBuilder()
      .flowMode(FlowMode.AUTO_CALLER_THREAD).rewindMode(RewindMode.ALL_THE_WAY_HARD_RESET)
      .resetMachineToInitOnFailure(true).flowExpirationMillis(0).build();
  final StateMachine machine = StateMachineBuilder.newBuilder().config(config).transitions()
      .next(toA).next(AtoB).next(BtoC).build();

  // res2. check that fsm should be alive
  System.out.println(String.format("fsm is alive: %s", machine.alive()));

  // op3. start a flow
  final String flowId = machine.startFlow();

  // op4. stop the flow
  System.out.println(String.format("fsm flowId: %s is stopped: %s", flowId, machine.stopFlow(flowId)));

  // op5. stop the fsm, flow will auto-stop
  System.out.println(String.format("fsm is alive: %s", machine.alive()));
  machine.demolish();
  System.out.println(String.format("fsm is alive: %s", machine.alive()));
}

Helper code for examples

  public static final class States {
    public static State aState, bState, cState, dState;
    static {
      try {
        aState = new State(Optional.of("A"));
        bState = new State(Optional.of("B"));
        cState = new State(Optional.of("C"));
        dState = new State(Optional.of("D"));
      } catch (StateMachineException e) {
      }
    }
  }

  public static class TransitionNotStartedVsA extends TransitionFunctor {
    public TransitionNotStartedVsA() throws StateMachineException {
      super(StateMachineImpl.notStartedState, States.aState);
    }

    @Override
    public TransitionResult progress() {
      logger.info(StateMachineImpl.notStartedState.getName() + "->" + States.aState.getName());
      return new TransitionResult(true, null, null);
    }

    @Override
    public TransitionResult regress() {
      logger.info(States.aState.getName() + "->" + StateMachineImpl.notStartedState.getName());
      return new TransitionResult(true, null, null);
    }
  }

  public static class TransitionAVsB extends TransitionFunctor {
    public TransitionAVsB() throws StateMachineException {
      super(States.aState, States.bState);
    }

    @Override
    public TransitionResult progress() {
      logger.info(States.aState.getName() + "->" + States.bState.getName());
      return new TransitionResult(true, null, null);
    }

    @Override
    public TransitionResult regress() {
      logger.info(States.bState.getName() + "->" + States.aState.getName());
      return new TransitionResult(true, null, null);
    }
  }

  public static class TransitionBVsC extends TransitionFunctor {
    public TransitionBVsC() throws StateMachineException {
      super(States.bState, States.cState);
    }

    @Override
    public TransitionResult progress() {
      logger.info(States.bState.getName() + "->" + States.cState.getName());
      return new TransitionResult(true, null, null);
    }

    @Override
    public TransitionResult regress() {
      logger.info(States.cState.getName() + "->" + States.bState.getName());
      return new TransitionResult(true, null, null);
    }
  }

  public static class TransitionCVsD extends TransitionFunctor {
    public TransitionCVsD() throws StateMachineException {
      super(States.cState, States.dState);
    }

    @Override
    public TransitionResult progress() {
      logger.info(States.cState.getName() + "->" + States.dState.getName());
      return new TransitionResult(false, null, new StateMachineException(Code.TRANSITION_FAILURE));
    }

    @Override
    public TransitionResult regress() {
      logger.info(States.cState.getName() + "->" + States.bState.getName());
      return new TransitionResult(false, null, new StateMachineException(Code.TRANSITION_FAILURE));
    }
  }

FSM as a library

Add mvn dependency:

<dependency>
  <groupId>com.github.statemachine</groupId>
  <artifactId>statemachine</artifactId>
  <version>1.0-SNAPSHOT</version>
</dependency>

state-machine's Issues

User docs for FSM

Create a user manual for FSM. Reading a testcase is not the best option to do this.

Profile fsm

Profile and do away sloppiness (some of which is already known).

Flow should be able to run in AUTO or MANUAL modes

Add support to fully wire a flow and run it in AUTO mode without external intervention of a user having to call transitionTo()

Track time elapsed in a state

Improve internal lock contention

FSM State Persistence

Allow the FSM to have pluggable backend state persistence storage. The idea is to not do a full-fledged replicated state machine but just to allow a resume-able state machine that can survive process deaths and/or reallocation to different machines. This will involve a degree of rework of the stateFlowStack or a suitable representation of it in a safe storage format like protobuf.

Ensure fsm correctness even when proc recv signals

fsm should handle signals gracefully and not screw the underlying state in weird ways.

Thread light fsm instances for concurrent use

Enhance the FSM to allow many user threads to use different instances of the same FSM - meaning setup FSM once during proc startup and tear down once at the end but during the lifetime of the proc, allow many threads to concurrently "use" the same FSM without having to pay the price of setting up the same set of transitions (when the thread begins to use the machine) and then tearing down the machine at the end of a thread's lifetime. Note that this does make it slightly trickier to track lifetimes of thread "local" machine state.

fsm explicit configuration

Make an FSMConfig as a first class object instead of pushing in config in pieces.

Expose machine and flow stats to users

Currently, e'thing runs in dark mode. Allow basic stat querying ability without indulging in obj creation hell.