Saturday, May 05, 2007

Implementing Workflow with Persistent Iterators

Why do workflow tools use diagrams and XML instead of regular programming languages? It’s a good question. When it comes to the core programming tasks - looping, conditionals and abstractions - XML does a lousy job. (As Koz’s post on BPEL explains.) As for workflow diagrams, they're just a visual representation of the XML.

So why are smart people writing workflows in XML instead of Ruby, C# or Java? If we ignore marketing, hype and that fact that XML is "just so darn cool" , we’re left with one good reason. It is the "showstopper" that prevents workflow development in ordinary languages.

In this post, I’m going to describe that showstopper. I’m also going to solve it. With the solution presented here, workflows really can be written in ordinary languages.

By the way, the solution presented here is in C#. As far as I can tell it is not possible in Java. It might be possible in Python or Ruby...

The Problem

The problem is simple: workflows have really big pauses in them. The execution of a workflow may be paused for days, weeks or even months waiting for some external event. Normal programming languages don’t handle this well. Imagine a long routine which represented the logic for a particular workflow. You can’t suspend the method at the half way point, wait for three weeks (maybe even rebooting the machine while you wait), and then have it pick up exactly where it left off – resuming at the exact line where it paused, with all local variables exactly as they where before.

Update 3 Jun 08: This Microsoft posting confirms big pauses as the key driver behind the development of their Windows Workflow product.

Here’s a simplified example of the problem:

public void ReviewDocument()
WaitForReviewersReply(); // might take weeks
How do get the method to resume at the right place when the reviewer finally replies? You can’t just call the method again, since if you do it will start again from the beginning.

I believe this is why smart people are writing workflows in XML instead of real languages. They construct a representation of the logic in XML, and write a workflow engine which can (re)serialize that representation (complete with its internal state) at each pause in the workflow. When the wait is over, everything gets deserialized and it resumes where it left off.

Ironically, all this XML stuff is unnecessary in C# 2.0 and later – which leads us to the solution...

Solution: Part 1 – Persistent Iterators

In C# 2.0 and later, you really can get a method to stop and then resume where it left off. The secret is the new "yield" keyword. In .NET, a method with one or more "yields" in it is called an iterator.

Here’s an example. It returns "One" the first time it is called, "Two" the second, and "Three" the third:

public IEnumerable<string> Foo()
yield return "One";
yield return "Two";
yield return "Three";
C# makes this possible with some special behind-the-scenes magic. But there’s a catch, all that magic happens in memory. It’s no use if we want a 3-week pause complete with system reboots.

To achieve our goal we have to serialize all that magic out to disk. We call the method once, serialize the iterator state to disk, then three weeks later we deserialize the iterator state and make the next call to the method.

That might sound difficult, but as it turns out, it’s not. Thanks to Microsoft’s implementation of "yield" (and the flexibility of .NET serialization) it only takes a few lines of code. Here it is in action:

Note that I ran the program three times. Each time it got the next value from the sample method. That confirms that state is being persisted outside the process, which means it can cope with arbitrarily long delays. You could run it today, and have it yield "One". Then you can reboot overnight and still have it yield "Two" when you run it tomorrow.

(Download source code.)

This is the first part of our solution: persist state between yields. (Update: See Microsoft's comments here).

Solution: Part 2 – Yield "When to Call Me Back"

Let's recap on what we've got. We now have a way to call a method, have it stop part way through, pause for a reeeeeealy long time, and then have it resume where it left off. That’s exactly what we need to solve our workflow problem.

There is only one more thing we need to figure out: what should the method return when it yields? Assuming that the method will be called by some hypothetical workflow engine, it should return something which tells the engine when to make the next call.

  • For instance, if the method needs to pause until 7:30 am, it should yield an object which says "Call me back at 7:30".
  • If the method needs to pause until data is updated for customer number 123, it should yield an object which says, "Call me back when customer #123 is updated".

This lets us write our workflow as a perfectly ordinary method, yielding only when a long pause is required.

There must be a degree of polymorphism in the yielded objects – since some of them represent a delay until a fixed time, some represent a delay until certain data is updated, and others may represent delays until users reply to system-generated emails and so on. There’ll also need to be some "smarts" in the engine to interpret theses objects appropriately – roughly equivalent to the logic in an ordinary XML workflow engine, although different in the implementation details.

At this point I must apologize, because I have not had time to put together a working example. If there is enough interest in this post, I’ll try to publish one in the future. In the meantime, here’s how you might write a simple workflow:

public IEnumerator<EventToWaitFor> Foo()

// Ask the engine to call back in 5 hours
yield return new TimeDelayEvent(new TimeSpan(5, 0, 0));

To make this really workable, a little syntactic sugar may help. Therefore, in the next example, I have introduced a method called "Until", just to make things read more smoothly. Again, I must apologize for not having more time to explain this example, so please leave a comment below if I have failed to explain it properly.

public IEnumerator<EventToWaitFor> ApproveDocument(Document doc)
// Initiate a review and yield (i.e. wait) until it is complete
ReviewAction review = new ReviewAction("", doc);
yield return Until(review.Completed);  // might take weeks

// (omitted) ... email original author to notify them
// of review outcome ...

} while (!review.DocumentIsAcceptable);

// Yield (i.e. wait) until scheduled publication date
yield return Until(doc.PublicationDate);  // might take days
This is the second part of our solution: yield for large pauses, returning an object which says when to resume.


Modern programming languages express logic far better than XML. With persistent iterators, they can also handle the long pauses required in workflows.

At present, there is no production-quality workflow engine which supports this model. But perhaps there might be soon...

Update: see this - Microsoft may change implementation details that affect this approach. But they recognise the usefulness of the technique, so hopefully it will be a case of changing it, rather than breaking it.


Blogger John Rusk said...

A quick footnote with some of the geeky details:

As I mentioned above, two things make it possible for us to persist state between yields.

The first is the way Microsoft implemented the "yield" keyword. It is all done by compiler magic. When the complier processes a method containing "yield" statements, it transforms the method into a hidden class that implements a state machine. (This much easier than writing a state machine yourself. Writing a state machine yourself if another alternative to the traditional XML solution, but it’s not as easy – or as readable – as the solution described on this page.)

Details of the state machine can be found here (some minor details have changed, since the page was based on beta of 2.0) and here. You can also examine the generated code using Reflector.

Conveniently for us, all the state of the iteration is contained in the hidden class. All we need to do is serialize it. Which brings us to the second key aspect: customizing the serialization process. We have to customize the serialization process because the compiler-generated class is not marked as serializable. To serialize it, we have to implement ISurrogateSelector and ISerialization surrogate. We can do so in a general-purpose way, capable of serializing the state of any iterator (even iterators that call other iterators).

This solution should apply to other languages where "yield" is implemented by a hidden class, as long as you can find a way to serialize the state. As for languages that implement "yield" by other means, I don’t know...

Sat May 05, 09:51:00 PM PDT  
Anonymous Srdjan said...

Would be nice if you continue with a couple of more posts, extending on workflow engine...
but even without that, thanks!

Wed May 23, 07:39:00 AM PDT  
Blogger John Rusk said...

Will see what I can do (when I find the time, which won't be right now, sorry ;-)

I have just posted this related feature request to Microsoft:

Fri May 25, 03:08:00 AM PDT  
Anonymous jdn said...

This is awesome. Would love to see more.

Wed Jun 20, 12:37:00 PM PDT  
Anonymous Anonymous said...

I am actually working on creating a persistable programming language that sits on top of the CLR (a non declarative version). It could be considered another Workflow implementation, but right now that is just one of the side effects. That being said I would like to see more (when you get a chance) on your persistance example.

Sat Aug 25, 07:19:00 AM PDT  
Blogger John Rusk said...

Interesting. (Post a link here when it's ready :-)

Sat Aug 25, 04:49:00 PM PDT  
Blogger John Rusk said...

I haven't had time to take this example any further (yet) but Chris Khoo had a go here:

Sat Nov 17, 01:01:00 AM PST  
Blogger John Rusk said...

PS I should also mention that if you follow the link to the Microsoft feedback submission (see prior comment) you'll see a comment from Microsoft that they do intend to make compiler changes which may affect the approach I've outlined here.

Sat Nov 17, 01:05:00 AM PST  

Links to this post:

Create a Link

<< Home