Generators and Back Again

August 4th 2010

The code snippets in this entry are all Python-esque pseudocode, unless otherwise noted

I’ve long held an interest in asynchronous I/O frameworks for Python.

I started out playing around with asyncore/asynchat circa 2001. I spent some time in Twisted, and made some small contributions to that community. Then, I started tinkering with a few micro-frameworks of my own. At my last job, I wrote a slightly-more-complete framework called “eventful” to build a number of tools we ran server side, like a key/value database system and a deployment system.

Over the years, I’ve realized a lot of the evolution the various frameworks underwent was devoted to—somehow—achieve a more “natural” flow than callback style typically permits.

Allow me to explain.

Typically, your code is invoked by an asynchronous framework when some data is available to process:

def handle_read(self, data):
    # do stuff with data

Then, some data-dependent dispatching happens:

def handle_read(self, data):
    if is_put_command(data):
        self.handle_put(data)
    else:
        self.handle_get(data)

And who knows, the framework might provide tools to facilitate dispatching at this level.

Now, let’s concentrate on our get event handler:

def handle_get(self, data):
    resource = parse_get_stuff(data)
    return get_resource(resource)

Note that in our fictional framework here, the handler returns the data to be written back onto the connected socket. So far, so good.

But now, let’s pretend that get_resource(..) involves a call to a database or something. Since we’re in an async I/O framework, everything is running in a single thread. Our handler cannot block, or the main I/O loop will not be scheduled to handle events related to other sockets. So, get_resource itself must be asynchronous. That means it needs the event loop to do I/O on its behalf—so, we need our handler to return some request that indicates more stuff needs to be done by the event loop, then the results of that operation need to be passed back into some continuation to finally arrive at the real “return value” of the handle_get handler.

Callbacks are the way this is classically achieved:

def handle_get(self, data):
    resource = parse_get_stuff(data)
    io_request = get_resource(resource)

    def transform_database_data(db_result):
        return db_result['user_id']
    io_request.add_callback(transform_database_data)

    return io_request

But this kinda sucks for a few reasons:

  • The logic appears out of order. The final transformation of the data appears in code before the “first stage” of the handler is actually finished

  • Traditional exception handling isn’t possible. You need to add an “error callback” handler to every io_request in case an exception occurs in the operation the event loop does on your behalf

  • You either need to pass through any data calculated at early stages of the callback chain or rely on closure scoping, which works but gets pretty ugly when your callback chain gets longer than a few links

But really, the most decisive reason this is ugly is that people don’t usually code this way.

I think, lacking better metrics, a decent way to evaluate the elegance of a given approach in a particular problem domain is: “if the constraints of this particular domain were removed, would people still code it this way?”

Ask yourself, would you ever write this function?

def print_in_uppercase(phrase):
    def print_it(up):
        print up

    op_request = do_for_me(phrase.upper)
    op_request.callback(print_it)
    return op_request

The Solution

Let’s be honest. This is what we want:

def handle_get(self, data):
    resource = parse_get_stuff(data)
    db_result = get_resource(resource)
    return db_result['user_id']

The challenge is get_resource, we need the event loop to take control of the thread again. But the event loop is “up the stack”—it called you!

A first answer might be “well, let’s just call back to it!”. In “normal” Python (and most other languages), however, we have at least two problems with that:

  1. Every time we call over to the event loop, we’re making the stack deeper. We’ll stack overflow eventually.
  2. There is no good way to “resume” our handler when the I/O is done. Heck, the stack might have other frames on it related to other sockets—so we can’t just have the event loop “return” data back up to our handle_get frame.

Generators to the Rescue?

Python async I/O developers' collective ears perked up when generators were introduced in Python 2.2. When a generator yields, it sort of freezes the stack frame and lets the caller do other work—including scheduling other generators. Then, when .next() is called on that generator, the frame is resumed right where it left off. This allows for cooperative multitasking patterns, sometimes called coroutines, like this (this is runnable code, not pseudocode):

def one_g():
    for x in xrange(3):
        print "one!"
        yield 

def two_g():
    while True:
        print "two!"
        yield

def scheduler(loops):
    for x in xrange(3):
        for l in loops:
            l.next()
scheduler([one_g(), two_g()])

Output:

one!
two!
one!
two!
one!
two!

All that was missing was the ability to pass something back into a generator; then, you could have one generator affect the behavior of another.

Fortunately, that was added in Python 2.5 when generators grew a .send() method that took an argument that would be the return value of the last yield statement. So, now we can start to put something together that acheives our handle_get goals:

def handle_get(data):
    resource = parse_get_stuff(data)
    db_result = yield get_resource(resource) # returns control to the scheduler
    yield response(db_result['user_id'])

def do_db_work(request):
    # io stuff

def scheduler(loops):
    next_get = wait_for_get()
    getter = handle_get(next_get)
    val = getter.next()
    if val is get_resource:
        result = do_db_work(val)
        val = getter.send(result)
    assert val is response
    send_to_socket(val)

The rough idea is, the framework does the heavy lifting to make generators look like near-seamless coroutines to application code.

Diesel is Born

In Summer 2009 I was building a web app with a couple of friends. We were doing all sorts of Comet-y and event-y stuff, and I decided to gather up my decade of callback scars, my Python 2.5 generators, and take a stab at putting together something cool.

So we started the Diesel project. Take a look at the docs to see lots of examples—but in a nutshell, it let you do very cool stuff, written in an intuitive, blocking style, with minimal code.

Here’s a basic echo server, for example:

def echo(remote_addr):
    their_message = yield until_eol()
    yield "you said: %s\r\n" % their_message.strip()

Diesel managed huge bunches of these generators, and looked for specific tokens, like until_eol, which gave it (ie., the event loop) instructions on what kind of I/O to conduct, or how long to wait to resume the loop, or what “event” to wait on.

And it worked pretty well… but it wasn’t all wine and roses.

Degenerate Generators

As we’ve long known: the world is not flat.

For programmers, the world is nested. And these nestings are the building blocks for generality, encapsulation, etc. Functions and objects and methods allow us to adhere to the policy of “Don’t Repeat Yourself”.

But these constructs are problematic for something like Diesel:

def get_user(uname):
    do()
    several()
    io()
    things()

def handler(username):
    if username is not None:
        user = get_user(username)
    else:
        user = get_user('default')

    yield user.to_string()

The fundamental problem is Diesel must be the “caller” of the generator—the parent frame—in order to process tokens destined for it.

The call pattern we all know and love:

Diesel calls handler
handler calls get_user
get_user returns to handler
handler returns to Diesel

…will not work! If get_user does any IO, Diesel needs to be the recipient of the tokens being yielded to the caller. Once again, the issue is the event loop needs to be in control.

This puts Diesel in the business of “faking the call stack”. This convoluted mess is what’s required:

Diesel calls handler
handler yields another generator (get_user) to diesel
diesel pushes get_user onto the stack and calls .next() on it
get_user does IO, yielding signals to Diesel
eventually, get_user yields a "return value"
Diesel pops get_user off the stack 
Diesel calls .send(..) on handler, passing in the return value from get_user
handler resumes with the result of get_user
eventually, handler yields a "return value"

Oy! Where do I begin?

This code is ugly and hard to get right. It’s slow (compared to native function calls, which are relatively slow in Python already). Exception handling being raised “up the stack” (of generators) is near impossible to do right and imposes un-pythonic things on the application code. A funky token needs to be yielded that approximates the behavior of the keyword “return”—push something up to the caller in the generator stack and end the frame’s execution. And it’s very easy to make mistakes in your application about when you’re yielding generators vs. calling regular functions, and hard to refactor one into the other.

The Greenlet Kool-Aid

We’ve been busy at Bump writing new backend systems that power version 2.0 of our iPhone app. We had 10k+ lines written on Diesel and generators, and things were mostly working… but we were fatigued of running into the aforementioned complications. We wanted regular function calls, regular tracebacks, and regular exception handling.

So I started investigating using the greenlet library as an alternative to generators.

The greenlet library uses some assembly trickery to do true coroutines in Python. This means you can “call over” into another user-space microthread without going deeper in the stack, and then resume the caller later on.

Here’s an example from the greenlet website:

from py.magic import greenlet

def test1():
    print 12
    gr2.switch()
    print 34

def test2():
    print 56
    gr1.switch()
    print 78

gr1 = greenlet(test1)
gr2 = greenlet(test2)
gr1.switch()

That switch() call is the magic—jumping between arbitrary call stacks at will!

Diesel 2

One furious night of coding later, I had a branch of Diesel ported to use greenlet at its core instead of generators. In the process, I removed hundreds of lines of code full of edge cases, and the result was a codebase with fewer bugs (even though it was younger) that was much faster to boot.

We’ve been running millions of users on Diesel 2 at bump for the last few weeks since the launch of the Bump 2.0 app, and everything is going along swimmingly.

Here’s our contrived application, Diesel 2 style (using MongoDB):

def get_user(uname):
    client = MongoClient()
    return client.myapp.users.find({'username' : uname}).one()

def handler(username):
    if username is not None:
        user = get_user(username)
    else:
        user = get_user('default')

    return user

I feel somewhat conflicted, because the generator approach, with yields aplenty, was the a key characteristic of Diesel when we launched the project; but I eventually had to concede that the decision to use the greenlet library instead of generators for the basis of Diesel was, practically, the right call.

Try out Diesel 2: GitHub

blog comments powered by Disqus