Generalization of Deferred Execution in Python

Glyph Lefkowitz

Overview

A deceptively simple architectural challenge faced by many multi-tasking applications is gracefully doing nothing. Systems that must wait for the results of a long-running process, network message, or database query while continuing to perform other tasks must establish conventions for the semantics of waiting. The simplest of these is blocking in a thread, but it has significant scalability problems. In asynchronous frameworks, the most common approach is for long-running methods to accept a callback that will be executed when the command completes. These callbacks will have different signatures depending on the nature of the data being requested, and often, a great deal of code is necessary to glue one portion of an asynchronous networking system to another. Matters become even more complicated when a developer wants to wait for two different events to complete, requiring the developer to "juggle" the callbacks and create a third, mutually incompatible callback type to handle the final result.

This paper describes the mechanism used by the Twisted framework for waiting for the results of long-running operations. This mechanism, the Deferred, handles the often-neglected problems of error handling, callback juggling, inter-system communication and code readability.

In a framework like Twisted, the ability to glue two existing components together with a minimum of mediating code is paramount. Considering that the vast majority of the code in Twisted is asynchronous I/O handling, it is imperative that the mechanism for relaying the data between the output from one system into the input of another be competitive with the simplicity of passing the return value of one method to the argument of another. It was also important to use only no new syntax to avoid confusing programmers who already have experience with Python, and establish no dependencies on anything which would break compatibility with existing Python code or C / Java extensions.

Other Popular Approaches

There are several traditional approaches to handling concurrency that have been taken by application frameworks in the past. Each has its own drawbacks.

Threads

The problems with using threads for concurrency in systems that need to scale is fairly well-documented. However, many systems that use asynchronous multiplexing for I/O and system-level tasks, but run application code in a thread. Zope's threaded request handling is a good example of this model.

It is optimal, however, to avoid requiring threads for any part of a framework. Threading has a significant cost, especially in Python. The global interpreter lock destroys any performance benefit that threading may yield on SMP systems, and introduces significant complexity into both framework and application code that needs to be thread-safe.

A full discussion of the pros and cons of threads is beyond the scope of this paper, however, using threads merely for blocking operations is clearly overkill. Since each thread represents some allocation of resources, all of those resources are literally sitting idle if they are doing nothing but waiting for the results from a blocking call.

In a fairly traditional networking situation, where the server is asynchronously multiplexed, this waste of resources may be acceptable for special-purpose, simple client programs, since only a few will be run at a time. To create a generic system, however, one must anticipate cases when the system in question is not only a multi-user server or a single-user client, but also a multi-user hybrid client/server.

A good example of this is a high-volume web spider. A spider may have a server for administrative purposes, but must also be able to spawn many requests at once and wait for them all to return without allocating undue resources for each request. The non-trivial overhead of threads, in addition to sockets, would be a very serious performance problem.

Callback Conventions

At some level, any system for handling asynchronous results in Python will be based on callback functions. The typical way to present this to the application programmer is to have all asynchronous methods accept a callback as one of their arguments.

This approach is usually standardized by giving the callback having a standard name ("callback") or a particular position (first argument, last argument). Even systems which rigorously adhere to such standardization run into problems, however.

This approach does work for a variety of events. It is unwieldy when one is attempting to write asynchronous "conversations" that involve multiple stages. The first problem that we notice is the lack of error-handling. If an error occurs in normal Python code, Exception handling provides clean and powerful semantics for handling it.

class DocumentProcessor:
    def __init__(self):
        self.loadDocuments(self.callback, mySrv, "hello")

    def loadDocuments(callback, server, keyword):
        "Retrieve a set of documents!"
        ...

    def callback(self, documents):
        try:
            for document in documents:
                process(document)
        finally:
            self.cleanup()

    def cleanup(self):
        ...

In an asynchronous method such as the one given above, traditional exceptions fall short. What if an error occurs retrieving the documents from storage? Do we call the callback with an error rather than a result?

Language Modifications

Other languages handle this by associating different semantics with threading, or providing different constructs altogether for concurrency. This has the disadvantage that these languages aren't Python. Even Stackless Python is problematic because it lacks integration with the wide variety of libraries that Python provides access to.

The design of Deferred draws upon some of these other languages, and this section will cover several languages and their impact.

In particular, the following list of languages were influential:

• Erlang
• Mozart/Oz
• E
• Scheme
• Smalltalk

E, Smalltalk, and Scheme proved particularly influential. In E's, there is a sharp distinction between objects which are synchronously accessible and those which are asynchronously accessible. The original use for Deferreds was to represent results from Perspective Broker method calls. E was interesting in that the entire execution environment had assumptions about networking built in. E's "eventually" operator [stiegler] is what originally inspired the distinction between "a method which returns X" and "a method which returns a Deferred that fires X".

Smalltalk was influential in that its syntax for closures provided some precedent for thinking about the continuation of a "conversation" of execution as itself an object with methods. The original thought-experiment that lead to Deferreds was an attempt to write some Squeak code that looked like this:

(object callRemote: "fooBar") andThen: [ result |
        Transcript show: result.
    ] orElse: [ failure |
        failure printTraceback.
    ]

It was challenging to write enough Smalltalk code to make anything interesting happen with this paradigm, but within the existing framework of Twisted, it was easy to convert several request/response idioms to use this sort of object. Now that Twisted has dropped python 1.5.2 compatibility, and 2.1 is the baseline version, we can use nested_scopes[hylton] and anonymous functions to make the code look similar to this original model.

Scheme, of course, provides call-with-current-continuation (or call/cc), the mind-bending control structure which has been a subject of much debate in language-design circles. call/cc may have provided more a model of things to avoid than a real inspiration, though. While it is incredibly powerful, it creates almost as many problems as it solves. In particular, the interaction between continuations and try:finally: is undefined [pitman], since it is impossible to determine the final time the protected code will be run. The strongest lesson from call/cc was to only take as much state in the Deferred as necessary, and to avoid playing tricks with implicit context.

The mechanisms that these languages use, however, often rely upon deeper abstractions that make their interpreters less amenable than Python's to convenient, idiomatic integration with C and UNIX. Scheme's call/cc requires a large amount of work and creativity to integrate with "C" language libraries, as C. Tismer's work in Stackless Python Python has shown. [tismer]

Basics of Deferreds

After several months of working with Twisted's callback-based request/response mechanisms, it became apparent that something more was necessary. Often, errors would silently cause a particular process to halt. The syntax for a multi-stage asynchronous process looked confusing, because multiple different interfaces were being invoked, each of which taking multiple callbacks. The complexity of constructing these stages was constantly being exposed to the application developer, when it shouldn't really concern them.

In order to make gluing different request/response systems together easy, we needed to create a more uniform way of having them communicate than a simple convention. In keeping with that goal, we reduced several conventions into one class, Deferred, so that the request system could return a Deferred as output and the responder could accept a Deferred as input.. Deferreds are objects which represent the result of a request that is not yet available. It is suggested that any methods which must perform long-running calculations or communication with a remote host return a Deferred.

This is similar to the Promise pattern, or lazy evaluation, except that it is a promise that will not be resolved synchronously. The terminology usually used to describe a Deferred is "a Deferred that will fire" a particular result.

Deferreds have a small interface, which boils down to these five methods, plus convenience methods that call them:

• addCallbacks(self, callback, errback=None, callbackArgs=None, callbackKeywords=None, errbackArgs=None, errbackKeywords=None)
• callback(result)
• errback(result)
• pause()
• unpause()

In general, code that initially returns Deferreds will be framework code, such as a web request or a remote method call. This means that code that uses the framework will call addCallbacks on the Deferred that is returned by the framework. When the result is ready, the callback will be triggered and the client code can process the result. Usually the utility methods addCallback and addErrback are used.

Using addCallbacks has slightly different semantics than using addCallback followed by addErrback; addCallbacks places the callback and the errback "in parallel", meaning if there is an error in your callback, your errback will not be called. Thus using addCallbacks has either/or semantics; either the callback or the errback will be called, but not both.

def prettyRequest(server, requestName):
    return server.makeRequest(requestName
                              ).addCallback(
        lambda result: ', '.join(result.asList())
        ).addErrback(
        lambda failure: failure.printTraceback())

The example given shows a method which returns a Deferred that will fire a formatted string of the result of a given request. The return value of each callback is passed to the first argument of the next.

Generalized Error Handling

As described above in the section on using callbacks for asynchronous result processing, one of the most common application-level problems in an asynchronous framework is an error that causes a certain task to stop executing. For example, if an exception is raised while hashing a user's password, the entire log-in sequence might be halted, leaving the connection in an inconsistent state.

One way that Twisted remedies this is to have reasonable default behavior in circumstances such as this: if an uncaught exception is thrown while in the dataReceived callback for a particular connection, the connection is terminated. However, for multi-step asynchronous conversations, this is not always adequate.

Python's basic exception handling provides a good example for an error-handling mechanisms. If the programmer fails to account for an error, an uncaught exception stops the program and produces information to help track it down. Well-written python code never has to manually detect whether an error has occurred or not: code which depends on the previous steps being successful will not be run if they are not. It is easy to provide information about an error by using attributes of exception objects. It is also easy to relay contextual information between successful execution and error handlers, because they execute in the same scope.

Deferred attempts to mimic these properties as much as possible in an asynchronous context.

Reasonable Defaults

When something unexpected goes wrong, the program should emit some debugging information and terminate the asynchronous chain of processing as gracefully as possible.

Python exceptions do this very gracefully, with no effort required on the part of the developer at all.

x = 1 + 3
raise Exception("I can't go on!")
print x

Deferreds provide a symmetrical facility, where the developer may register a callback but then forego any error processing.

from deferexex import adder

def blowUp(result):
    raise Exception("I can't go on!")

def onSuccess(result):
    print result + 3

adder.callRemote("add", 1, 2).addCallback(blowUp).addCallback(onSuccess)

In this example, the onSuccess callback will never be run, because the blowUp callback creates an error condition which is not handled.

No Ambiguity about Failure

It is impossible to provide a reasonable default behavior if failure is ambiguous. Code should never have to manually distinguish between success and failure. An error-processing callback has a distinct signature to a result-processing callback.

Forcing client code to manually introspect on return values creates a common kind of error; when the success of a given long-running operation is assumed, it appears to work, and it is easier (and less code) to write a callback that only functions properly in a successful case, and creates bizarre errors in a failure case. A simple example:.

def successCallback(result):
    myResult = result + 1
    print myResult
    return myResult

...

adder.callRemote("add", 1, 1).addCallback(successCallback)

In this example, when the remote call to add the two numbers succeeds, everything looks fine. However, when it fails, result will be an exception and not an integer: therefore the printed traceback will say something unhelpful, like:

TypeError: unsupported operand types for +: 'instance' and 'int'

Rich Information about Errors

It should be easy for developers to distinguish between fatal and non-fatal errors. With Python exceptions, you can do this by specifying exception classes, which is a fairly powerful technique.

class MyExc(Exception):
    "A sample exception."

try:
    x = 1 + 3
    raise MyExc("I can't go on!")
    x = x + 1
    print x
except MyExc, me:
    print 'error (',me,').  x was:', x
except:
    print 'fatal error! abort!'

With Deferred, we planned to have a syntactically simple technique for accomplishing something similar. The resulting code structure is tends to be a bit more expansive than the synchronous equivalent, due to the necessity of giving explicit names to the functions involved, but it can be just as easy to follow.

from deferexex import adder

class MyExc(Exception):
    "A sample exception"

class MyObj:

    def blowUp(self, result):
        self.x = result
        raise MyExc("I can't go on!")

    def trapIt(self, failure):
        failure.trap(MyExc)
        print 'error (', failure.getErrorMessage(), '). x was:', self.x
        return self.x

    def onSuccess(self, result):
        print result + 3

    def whenTrapped(eslf, result):
        print 'Finally, result was', result

    def run(self, o):
        o.callRemote("add", 1, 2).addCallback(
            self.blowUp).addCallback(
            self.onSuccess).addErrback(
            self.trapIt).addCallback(
            self.whenTrapped)

MyObj().run(adder)

In this example, we have a callback chain that begins with the result of a remote method call of 3. We then encounter a MyExc error raised in blowUp, which is caught by the errback trapIt. The 'trap' method will re-raise the current failure unless its class matches the given argument, so the error will continue to propagate if it doesn't match, much like an except: clause.

Easy Propagation of Context

While it is dangerous to implicitly propagate too much context (leading to problems similar to those with threads), we wanted to make sure that it is easy to move context from one callback to the next, and to convert information in errors into successful results after the errors have been handled.

Both addCallback and addErrback have the signature callable, *args, **kw. The additional arguments are passed through to the registered callback when it is invoked. This allows us to easily send information about the current call to the error-handler in the same way as the success callback.

Patterns of Usage

Since Deferred is designed for a fairly specific class of problems, most places it is used tend to employ certain idioms.

Request-ID Dictionary

If you are implementing a symmetric, message-oriented protocol, you will typically need to juggle an arbitrary number of outstanding requests at once. The normal pattern for doing this is to create a dictionary mapping a request number to a Deferred, and firing a Deferred when a response with a given request-ID associated with it arrives.

A good example of this pattern is the Perspective Broker protocol. Each method call has a request, but it is acceptable for the peer to make calls before answering requests. Few protocols are as extensively permissive about execution order as PB, but any full-fledged RPC or RMI protocol will enable similar interactions. The MSN protocol implementation in Twisted also uses something similar.

Sometimes Synchronous Interface

When writing interfaces that application programmers will be implementing frequently, it is often convenient to allow them to either return either a Deferred or a synchronous result. A good example of this is Twisted's Woven, a dynamic web content system.

The processing of any XML node within a page may be deferred until some results are ready, be they results of a database query, a remote method call, an authentication request, or a file upload. Many methods that may return Nodes may also return Deferreds, so that in either case the application developer need return the appropriate value. No wrapping is required if it is synchronous, and no manual management of the result is required if it is not.

This is the best way to assure that an application developer will never need to care whether a certain method's results are synchronous or not. The first usage of this was in Perspective Broker, to allow easy transparent forwarding of method calls. If a Deferred is returned from a remotely accessible method, the result will not be sent to the caller until the Deferred fires.

from twisted.spread import pb

class LocalForwarder(flavors.Referenceable):
    def remote_foo(self):
        return str(self.local.baz())

class RemoteForwarder(flavors.Referenceable):
    def remote_foo(self):
        return self.remote.callRemote("baz").addCallback(str)

callRemote

Ideally, all interactions between communicating systems would be modeled as asynchronous method calls. Twisted Words, the Twisted chat server, treats any asynchronous operation as a subset of the functionality of Perspective Broker, using the same interface. Eventually, the hope is to make greater use of this pattern, and abstract asynchronous conversations up another level, by having the actual mechanism of message transport wrapped so that client code is only aware of what asynchronous interface is being invoked.

Advanced Features

The first "advanced" feature of Deferreds is actually used quite frequently. As discussed previously, each Deferred has not one, but a chain of callbacks, each of which is passed the result from the previous callback. However, the mechanism that invokes each callback is itself an implementor of the previously-discussed "Sometimes Synchronous Interface" pattern - a callback may return either a value or a Deferred.

For example, if we have a Deferred A, which has 2 callbacks: X, which returns a deferred B, that fires the result to X in 2 seconds, and Y, which prints its result, we will see the string "hello" on the screen in 2 seconds. While it may sound complex, this style of coding one Deferred which depends on another looks very natural.

from twisted.internet import reactor, defer

A = defer.Deferred()
def X(result):
    B = defer.Deferred()
    reactor.callLater(2, B.callback, result)
    return B
def Y(result):
    print result
A.addCallback(X)
A.addCallback(Y)
A.callback("hello world")
reactor.run()

In this way, any asynchronous conversation may pause to wait for an additional request, without knowing in advance of running the first request what all the requests will be.

The other advanced feature of Deferreds is not terribly common, but is still useful on occasion. We have glossed over the issue of "pre-executed"Deferreds so far, e.g. Deferreds which have already been called with a callback value before client code adds callbacks to them. The default behavior, which works in almost every situation, is simply to call the callback immediately (synchronously) as it is added. However, there are rare circumstances where race conditions can occur when this naive approach is taken.

For this reason, Deferred provides pause and unpause methods, allowing you to put a Deferred into a state where it will stop calling its callbacks as they are added; this will allow you to set up a series of communicating Deferreds without having anything execute, complete your setup work, and then unpause the process.

In this way, you can create centralized choke-points for caring about whether a process is synchronous or not, and completely ignore this problem in your application code. For example, in the now-obsolete Twisted Web Widgets system (a dynamic web content framework that predates woven), it was necessary to make sure that certain Deferreds were always called in order, so the page would render from top to bottom. However, the user's code did not need to concern itself with this, because any Deferreds for which synchronous callback execution would have been an issue were passed to user code paused.

Conclusion

Deferreds are a powerful abstraction for dealing with asynchronous results. Having a uniform approach to asynchronous conversations allows Twisted APIs to provide a level of familiarity and flexibility for network programmers that approaches that of domain-specific languages, but still provides access to all of Python's power.

Acknowledgements

I would like to thank the entire Twisted team, for making me realize what a good idea I had hit upon with Deferreds.

Special thanks go to Andrew Bennetts and Moshe Zadka, for implementing the portion of Twisted used to generate this, and other, papers, and to Ying Li and Donovan Preston for last-minute editorial assistance..

References

1. Marc Stiegler, The E Language in a Walnut, erights.org
2. Jeremy Hylton, PEP 227, "Statically Nested Scopes"
3. Kent Pitman, UNWIND-PROTECT vs. Continuations, Kent Pitman's Personal FAQ
4. Christian Tismer, Continuations and Stackless Python, Proceedings of the Sixth International Python Conference