Why developers should be force-fed state machines

This post is meant to create more awareness about state machines in the web application developer crowd. If you don’t know what state machines are, please read up on them first. Wikipedia is a good place to start, as always.

State machines are awesome

The main reason for using state machines is to help the design process. It is much easier to figure out all the possible edge conditions by drawing out the state machine on paper. This will make sure that your application will have less bugs and less undefined behavior. Also, it clearly defines which parts of the internal state of your object are exposed as external API.

Moreover, state machines have decades of math and CS research behind them about analyzing them, simplifying them, and much more. Once you realize that in management state machines are called business processes, you'll find a wealth of information and tools at your disposal.

Recognizing the state machine pattern

Most web applications contain several examples of state machines, including accounts and subscriptions, invoices, orders, blog posts, and many more. The problem is that you might not necessarily think of them as state machines while designing your application. Therefore, it is good to have some indicators to recognize them early on. The easiest way is to look at your data model:

  • Adding a state or status field to your model is the most obvious sign of a state machine.
  • Boolean fields are usually also a good indication, like published, or paid. Also timestamps that can have a NULL value like published_at and paid_at are a usable sign.
  • Finally, having records that are only valid for a given period in time, like subscriptions with a start and end date.

When you decide that a state machine is the way to go for your problem at hand, there are many tools available to help you implement it. For Ruby on Rails, we have the excellent gem state_machine which should cover virtually all of your state machine needs.

Keeping the transition history

Now that you are using state machines for modelling, the next thing you will want to do is keeping track of all the state transitions over time. When you are starting out, you may be only interested in the current state of an object, but at some point the transition history will be an invaluable source of information. It allows you to answer all kinds of questions, like: “How long on average does it take for an account to upgrade?”, “How long does it take to get a draft blog post published?”, or “Which invoices are waiting for an initial payment the longest?”. In short, it gives you great insight on your users' behavior.

When your state machine is acyclic (i.e. it is not possible to return to a previous state) the simplest way to keep track of the transitions is to add a timestamp field for every possible state (e.g. confirmed_atpublished_atpaid_at). Simply set these fields to the current time whenever a transition to the given state occurs.

However, it is often possible to revisit the same state multiple times. In that case, simply adding fields to your model won’t do the trick because you will be overwriting them. Instead, add a log table in which all the state transitions will be logged. Fields that you probably want to include are the timestamp, the old state, the new state, and the event that caused the transition.

For Ruby and Rails, Jesse Storimer and I have developed the Ruby gem state_machine-audit_trail to track this history for you. It can be used in unison with the state_machine gem.

Deleting records?

In some cases, you may be tempted to delete state machine records from your database. However, you should never do this. For accountability and completeness of your history alone, it is a good practice to never delete records. Instead of removing it, add an error state for any reason you would have wanted to delete a record. A spam account? Don’t delete, set to the spam state. A fraudulent order? Don’t delete, set to the fraud state.

This allows you to keep track of these problems over time, like: how many accounts are spam, or how long it takes on average to see that an order is fraudulent.

In conclusion

Hopefully, reading this text has made you more aware of state machines and you will be applying them more often when developing a web application. Disclaimer: like any technique, state machines can be overused. Developer discretion is advised.

41 comments

  • Jake Gordon
    Jake Gordon
    June 13 2011, 11:39AM

    Nice post.

    State machines are great, although I have to admit, sometimes it takes me a while before I recognize that I should be using one… but once I re-factor it usually cleans up a lot of code and makes for a much simpler design.

    If your web app is javascript intensive, you can also use state machines on the client. I happened to build a small (and simple) javascript state machine library just last week for a game

    http://codeincomplete.com/posts/2011/6/1/javascript_state_machine/

  • Alex
    Alex
    June 13 2011, 11:55AM

    Anybody else read the title of this post as meaning developers should be replaced with state machines which are force-fed, rather than meaning that human developers should study state machines…? :-P

  • Tom
    Tom
    June 13 2011, 12:28PM

    Alex: yes!

  • Rachel 'Groby' Blum
    Rachel 'Groby' Blum
    June 13 2011, 01:22PM

    It might be the education snob in me, but it reads like another reason why developers should have a CS degree. State machines are one of the basic tools in every devs toolkit, and I’m always amazed that there are (supposedly) people out there who don’t know about them.

    That’s not to detract from the awesome work folks like you do to make state machines easier to use – they always feel like a whole truckload of boilerplate, so help using them is always appreciated.

  • will
    will
    June 13 2011, 02:04PM

    anybody else feel this didnt do a good job of…anything?

  • @Shopify Willem van Bergen
    Willem van Bergen
    June 13 2011, 02:12PM

    Rachel: Yes, I agree that state machine theory is one of the most important and useful parts in a CS eduction.

    However, the problem is recognizing when you should be using a state machine, because it is very easy to miss opportunities to apply the technique. It’s easy to just at a “published_at” field to your blog post model. What I hope to achieve with this post is a trigger in a developer’s mind to consider using a state machine instead.

  • @Shopify Willem van Bergen
    Willem van Bergen
    June 13 2011, 02:22PM

    Alex, Tom: I would like to see a state machine that accurately describes a developer. Maybe “Programming → Eating pizza → Drinking coke → Programming” with an error state of “Sleeping” thrown in? ;)

  • @Shopify Willem van Bergen
    Willem van Bergen
    June 13 2011, 02:23PM

    Will: anything specific that you’re missing from the article?

  • @Shopify Willem van Bergen
    Willem van Bergen
    June 13 2011, 02:27PM

    Jake Gordon: awesome work. We’re doing more and more with Javascript at Shopify, so I’m sure that a good javascript state machine library will come in handy.

  • Luke vdH
    Luke vdH
    June 13 2011, 02:49PM

    Have you guys seen https://rubygems.org/gems/paper_trail? It’s not quite state machine, but it captures a lot of that state-change tracking type info.

  • Kevin Sookocheff
    Kevin Sookocheff
    June 13 2011, 03:21PM

    Great stuff Willem, I’ve used state machines for parsing MP3 data to go from a huge case statement to a handful of distinct states. So satisfying!

  • Rein Henrichs
    Rein Henrichs
    June 13 2011, 03:36PM

    While I agree that an understanding of state machines is important, the state machine described here is really a bastardization of the computer scientific and mathematical definition of a state machine (FSM). State machines aren’t just used to describe the current state of your blog post.

    Automata theory has uses ranging from formal languages to communication protocol design to hardware design. Perhaps a better place to start when explaining state machines would be their use in deciding regular languages in the Chomsky hierarchy (and therefore how they are related to regular expressions). By reducing the concept to a way to describe the state of a blog post, you are (imo) missing out on most of its beauty and elegance. An insufficiently deep explanation also tends to turn profound concepts into ready-made crystal hammers and invites cargo-culting.

  • Ryan Oberholzer
    Ryan Oberholzer
    June 13 2011, 05:16PM

    State machines are awesome. I wrote one a while ago – http://rubygems.org/gems/stateflow – We use in extensively in all our projects.

    Check it out, and let me know what you think! :)

  • Willem van Bergen
    Willem van Bergen
    June 13 2011, 07:14PM

    Rein Henrichs: You’re absolutely right that this post doesn’t cover the topic of state machines completely; I point to Wikipedia for a more complete description.

    What I try to accomplish is that developer learn how to recognize the state machine pattern in their apps so they can apply it. Talking about regular expressions or network protocols will make it seem that state machines are not applicable when designing something like blog posts, which is the exact oppositie of what I want to achieve. This is why I left off most of the complex stuff, even though it makes the theory so elegant.

  • Pete
    Pete
    June 13 2011, 09:40PM

    I agree with Rachel – state machines are one of the things you learn about in school; too many self-taught folks never learn about them until too late.
    personally, I see FSMs more places than not – it’s harder to NOT use one than the reverse.

  • Jim Roepcke
    Jim Roepcke
    June 13 2011, 11:26PM

    Check out webmachine by Basho (makers of Riak). It’s a web framework that’s literally modelled on HTTP’s state machine.

    http://webmachine.basho.com/

    It was ported to node.js (nodemachine), and that works great too.

    The GoF’s State Pattern is a great way to introduce state machines into classic OO software.

  • oldprogrammer
    oldprogrammer
    June 13 2011, 11:34PM

    Jesus, I am old. Have any of you diaper wearing “youngsters” ever heard of Knuth? Anyway noobs, PLEASE read http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming before your further degrade our already beat down industry rep.

  • Pete Forde
    Pete Forde
    June 13 2011, 11:48PM

    Thanks for the great article, Willem! I’m a very minor contributor to the state_machine gem, and I am pleased as punch to see you building upon it.

    There’s a lot of trolls commenting on this post, and I’m honestly curious what you’d have a single post do? It would seem like you’d prefer the content body to read “I was going to write a nice summary post about how to get started using state machines in your code, but I decided to insult you into reading an entire fucking book in the most patronizing way possible with no further direction given. KTHXBYE!”

    I’m a self-taught developer that learned to love state machines not a moment too soon, but realistically after about a decade of professional development. It’s not that I wasn’t using them before — it’s hard not to. I just didn’t recognize them as a general abstraction. Now I start designing my state machines in the early concept stage of my projects.

    At the same time, I’m not planning to apologize for not using them sooner, nor do I feel like going to get a CS degree would have been the best course of action for me given the arc of my career. Different paths to happiness for different folks! All of you haters should chill out.

  • kodeninja
    kodeninja
    June 14 2011, 04:12AM

    Great blog.

    On a related note, I think it would be invaluable for noobs if someone could create a screencast of how he took an existing piece of code (something non-trivial, but not too big either) that didn’t use FSM but was a possible candidate, refactored it using FSM concepts and how the end result improved the overall design.

    Just an idea.

  • Oliver
    Oliver
    June 14 2011, 08:06AM

    +1 Pete. If you’re the kind of person who thinks the best introduction to state machines is “regular languages in the Chomsky hierarchy”, then you are clearly NOT the target audience of this post. While the CS applications might be elegant and fascinating, they’re not for everyone. You don’t get a child interested in engineering by explaining the equations that keep forces in balance on a skyscraper; you give them a tub of Duplo, let them build their own skyscraper and watch it fall over. Then they wonder “why did that happen?” “What can I do to stop it?” “That works, but it uses too many blocks. How can I do this better?” The next time they need to stop something falling over, they’ll be ready.

    If you’re the type that gets turned on by CS theory, you’ll have your own way of doing things. I’m studying software engineering, have been coding a few years, and am absolutely in love with it, but CS feels too mystical sometimes. The most approachable way to teach me a new concept is to make it instantly applicable to the kind of things I work on, and allow me to scale out my knowledge on more advanced topics that interest me. If you can teach me how to see a state machine pattern, that will be more valuable than any Chomsky hierarchy in making me use it. Eventually I’ll rub up against Chomsky in a more advanced blog post.

    Interestingly, one of the subjects I’m studying introduced state modelling a couple of months ago, and I have an exam on it in 36 hours. Wasting time surfing the Web and reading friendly articles is helping me study! I’ve read GoF, but the state pattern struck me as something that kinda always fitted into a design, rather than the core of the design itself. This subject opened my eyes a little more.

    We all need different perspectives, so thank you Willem.

  • Oliver Ponder
    Oliver Ponder
    June 14 2011, 04:35PM

    Those of you intrigued by the concept and looking to learn more: http://video.google.com/videoplay?docid=-5837841629284334824&hl=en#

    This vid from a CS lecture from Shai Simonson really helped things click in my mind.

  • brandonc
    brandonc
    June 15 2011, 01:13PM

    Feeling inspired by your post, I wrote a generic state machine class in c#:

    https://github.com/brandonc/statemachine

  • Rein Henrichs
    Rein Henrichs
    June 15 2011, 03:39PM

    My point, which seems to have gotten lost, is that a blog post could be in is really not a state machiine. A state machine is a very specific computer scientific concept and this post does very little to actually introduce or explain it.

    This is a lot like saying that atoms are the fundamental building blocks of matter, and then going on to describe the atomic theory of the ancient Greeks (Democritus, et al.). Sure, you get across the most basic concept of the “atom”, but you really don’t explain that much about atomic theory.

    If this blog post does make people interested in the concept and that then causes them to learn it more deeply, that would make me happy. If it leads people to think that “state machine == list of states”, that makes me sad.

    In any event, I don’t think that saying this makes me a troll. I think calling someone a troll for rationally expressing a differing point of view is by far a worse offense.

  • Rein Henrichs
    Rein Henrichs
    June 15 2011, 03:40PM

    Sorry, I somehow deleted some important words while editing. I meant to say, “My point, which seems to have gotten lost, is that a list of states that a blog post could be in is really not a state machine”.

  • umlcat
    umlcat
    June 16 2011, 01:21PM

    I read about state-machines in my compiler classes, and found that could be used to solve other problems. But, its thru, they are a design pattern that many developers aren’t aware of it.

  • VolkerG
    VolkerG
    September 01 2011, 11:26AM

    I love state machines, they always make code clearer, more stable and even simpler to debug.
    For most cases (simple state machines) you need a enumeration (in c: enum {sIDLE, sHUNT, sPAYED, …} my_states; I start all my states with a lowercase ‘s’) and a switch() case: construct and you are almost there.
    If you put it in a function, you can log entry and exit conditions what makes debug easy.

  • Mike Holly
    Mike Holly
    September 01 2011, 02:21PM

    That state_machine gem looks rad. Thanks for the tip!

  • samwyse
    samwyse
    September 02 2011, 07:32AM

    Found this article via http://www.skorks.com/2011/09/why-developers-never-use-state-machines/ and wanted to add a quick testimonial: State machines are great! Just this week, I needed to write a command line tool to split out subsections from large documents. Once the Python grew to a particular size, it got buggy and I couldn’t easily see why. I grabbed a sheet of paper, drew my state diagram, rearranged my code, and it worked on the first run.

  • John Haugeland
    John Haugeland
    September 02 2011, 12:29PM

    This is basically a bunch of cheerleading for Ruby’s state machine gem. There’s no technical content here; if someone already knows what a state machine is, you’re preaching to the choir, and if they don’t, they sure aren’t going to learn from this.

    Will’s right: this article didn’t do a good job of anything.

  • John Haugeland
    John Haugeland
    September 02 2011, 12:31PM

    Rein: the reason they’re calling you a troll is that this blog post has promised them a magic bean, and in trying to bring realism to the excitement, instead of seeing you as the guy who’s going to save them a bunch of wasted work and frustration, they see you as the troll who’s trying to destroy their magic beans.

  • Steve Caine
    Steve Caine
    September 02 2011, 02:05PM

    And for those toiling in the iOS vineyard:

    http://matt-greer.com/blog/2009/05/state-machines-and-objective-c/

  • Bill Kress
    Bill Kress
    September 06 2011, 11:48AM

    A while ago I wrote what is essentially a state machine DSL in Java. It’s more OO than most and allows you to translate from your paper state transition table more-or-less straight into code (The data is defined in the format of a transition table). You may optionally add states through code, but the table ends up being pretty easy to maintain and I don’t think it costs anything in terms of performance.

    The problem with state machine “Libraries” is that it’s pretty tough to really centralize all the redundant parts of a state machine, you are generally better off hand coding them.

    This was just for fun but it works and might inspire anyone trying to code a FSM without all the boilerplate/redundant code. It may seem a little strange at first, but I think the model is good.

    http://code.google.com/p/state-machine/

  • Anonymous coward
    Anonymous coward
    September 22 2011, 03:06PM

    Suppose you have a light sensor, watching the ambient light, and a relay which turns light on and off, with a delay of let’s say one hour. These two work together.

    The states for this state machine would be darkOutsideLightOff, darkOutsideLightOn, darkOutsideLightOn, lightOutsideLightOn, lightOutsideLightOff. The state would be also accompanied by a timestamp recording the last state change, so the light switch relay can know when to act.

    How is this simpler to implement than a system using two booleans – darkOutside and lightOn?

    I have used state machines in many LOB apps, I can’t think of how a compiler could be implemented without one, and in general I agree that they are highly useful – for the right type of problems.

    But using state machines in cases where the states don’t have an immediate, primary natural meaning from a business point of view (like above – the states are actually predicates on two domain-specific variables), or when there is a simpler alternate representation of the state, is IMO a mistake.

    IMO, the state machine approach lends itself well to solving problems which you are most comfortable with modelling from the start as state diagrams. If such a model seems artificial and unnatural for your problem, probably a state machine isn’t the right solution.

  • jeux mahjong gratuit
    jeux mahjong gratuit
    March 18 2012, 11:54AM

    This video post is really fantastic, the echo feature and the picture feature of this film post is actually awesome.

  • Kenny
    Kenny
    December 24 2012, 06:09PM

    Every time you declare a boolean variable to remember that you already did something, for example, you are using state machine, you just don’t know it. So it’s not that we need to use state machine more, we’re already using it everywhere, we just do not define our states clearly as combination of our adhoc variable values, and more importantly don’t make a clear distinction between application state and application data. This I think is still the biggest distinction that we often fail to make.

    The MVC pattern applied to web application, for example, often has very clear separation between state (how things are presented) and data (what gets presented). But MVC frameworks do not seem to make this distinction clear, they lump everything into the model.

  • Sean Zhang
    Sean Zhang
    December 30 2012, 02:03AM

    Hi, Willem,

    This is an awesome post, thanks for sharing your idea.

    I have a question about using state machine to model a ordering workflow. Assume the workflow looks like this:

    1. Call fraud detection service, which returns PASS/FAIL
    2. Call payment processor to reserve a fund, which returns PASS/DECLINE_BUT_PLEASE_RETRY/DECLINE_DO_NOT_RETRY
    3. Ship the item, which could success or fail

    But for certain customers, the workflow is
    1. Call fraud detection service, which returns PASS/FAIL
    2. Ship the item, which could success or fail
    3. Call payment processor to reserve a fund, which returns PASS/DECLINE_BUT_PLEASE_RETRY/DECLINE_DO_NOT_RETRY

    I think there are 3 state variables:
    FraudStatus, ReservedStatus and FulfillStatus.

    Should I create a state for each possible combination of the 3 state variables? Or there should be 3 state machines, one for each state variable?

    The problem with the first approach (one state for each valid combination) is that there could be a large number of states, especially if the number of state variables increases. In this simplified example, there could be 5 states.

  • @Shopify Willem van Bergen
    Willem van Bergen
    January 04 2013, 10:47AM

    Hi Sean,

    In your example, you have 3 state variables to describe 3 different processes, but these processes do have overlap.

    State machines are a great way to reason about your system to reduce bugs. However, the rigor of reasoning only works if you model it as one state machine. This way you can see how the different processes could possibly overlap, and decide what you want to allow or not allow. I usually prefer to draw the state machine out on paper, because that’s the easiest way to see how the different processes could interact.

    However, combining these 3 processes into one may lead to an explosion in the number of states like you mentioned. For clarity, you may decide to implement it using 3 different state machines anyway, and implement the overlap cases that need special handling outside of the state machine. By doing the analysis as one state machine beforehand, you will at least know what overlap between the state machines you should account for.

    In Shopify, we have split out the order checkout/fulfillment process is several state machines for that exact reason.

    Hope this helps,
    Willem

  • Ken Krauss
    Ken Krauss
    March 25 2013, 06:48PM

    I am a CISSP-certified website developer who has been handcoding websites since 1998 and I am writing a paper for publication right now about how to use state machine diagrams to conceptualize and model websites. I wanted to point out that state machines are great at modeling user interfaces, and every website is a user interface, thus all websites can be modeled as state machines. Many website developers use flowcharts to model websites, and state machines are similar except they include the concepts of input vocabulary and grammar in the transitions from one state to the next. If you don’t have forms that process data on your site, any model of your website will be more of a directed graph (also a formal concept of math theory) not a state machine. Every URL on your website is a state (or node in a directed graph) and may be several states depending on whether or not your pages have dynamic logic. State machines can be described in both graph and chart form and can be mathematically proven which makes me believe it may someday soon be possible to prove your website’s security when these concepts really grab hold in the webdev community. Model Based Development (MBD) uses state machine diagrams as blueprints for software code. HS Lahman says state machines offer many of the same benefits object oriented code does: encapsulation, implementation hiding, and peer-to-peer collaboration. Lahman and myself prefer Moore models but the UML standard is derived from Harel. State machines can also be used to describe business processes so if you’re making an app to replicate an existing business process, you can start coding off the same state machine diagram if you wanted to. State machine diagrams are also reducible and divisible which allows you to make your diagram with the appropriate level of detail for the problem, or break off sections of the model for closer inspection. As long as all entries and exits to the system are accounted for, your state machine diagram should be accurate at multiple levels of detail. Knowing that 6 × 8 can also be described as (2 × 3) x (2 × 2 × 2) is similar to breaking down a large state machine diagram into smaller parts, and knowing that a map of your city showing only major streets and a map of your neighborhood showing all major and minor streets are both accurate maps even though they show different things are similar to the concepts of reducing and dividing up state machines. Hope this helps!

  • Leo
    Leo
    August 28 2013, 07:49PM

    Ken Krauss; Did you ever write that paper? Can one read it anywhere, online or so?

  • Jared
    Jared
    February 18 2014, 07:18PM

    Willem’s comment is interesting. I frequently want to model system tests as multiple state machines, but the tools for easily generating the tests that would result don’t really exist. Testing has a long way to go still…

  • rainy day
    rainy day
    November 08 2014, 03:48PM

    Whatever gem you use (state_machine or stateflow), please do not throw it in the model.

    Good OOP practices dictate separation of concerns: a model should be responsible of validation and persistence, and that’s a lot. Logic is too much responsibility.

    Keep your business logic in a service object.

Leave a comment ...