\begin{aosachapter}{A Web Crawler With asyncio Coroutines}{s:crawler}{A. Jesse Jiryu Davis and Guido van Rossum}

Classical computer science emphasizes efficient algorithms that complete

computations as quickly as possible. But many networked programs spend

their time not computing, but holding open many connections that are

slow, or have infrequent events. These programs present a very different

challenge: to wait for a huge number of network events efficiently. A

contemporary approach to this problem is asynchronous I/O, or ``async''.

This chapter presents a simple web crawler. The crawler is an archetypal

async application because it waits for many responses, but does little

computation. The more pages it can fetch at once, the sooner it

completes. If it devotes a thread to each in-flight request, then as the

number of concurrent requests rises it will run out of memory or other

thread-related resource before it runs out of sockets. It avoids the

need for threads by using asynchronous I/O.

We present the example in three stages. First, we show an async event

loop and sketch a crawler that uses the event loop with callbacks: it is

very efficient, but extending it to more complex problems would lead to

unmanageable spaghetti code. Second, therefore, we show that Python

coroutines are both efficient and extensible. We implement simple

coroutines in Python using generator functions. In the third stage, we

use the full-featured coroutines from Python's standard ``asyncio''

library\footnote{Guido introduced the standard asyncio library, called

``Tulip'' then, at PyCon 2013.}, and coordinate them using an async

queue.

\aosasecti{The Task}\label{the-task}

A web crawler finds and downloads all pages on a website, perhaps to

archive or index them. Beginning with a root URL, it fetches each page,

parses it for links to pages it has not seen, and adds the new links to

a queue. When it fetches a page with no unseen links and the queue is

empty, it stops.

We can hasten this process by downloading many pages concurrently. As

the crawler finds new links, it launches simultaneous fetch operations

for the new pages on separate sockets. It parses responses as they

arrive, adding new links to the queue. There may come some point of

diminishing returns where too much concurrency degrades performance, so

we cap the number of concurrent requests, and leave the remaining links

in the queue until some in-flight requests complete.

\aosasecti{The Traditional Approach}\label{the-traditional-approach}

How do we make the crawler concurrent? Traditionally we would create a

thread pool. Each thread would be in charge of downloading one page at a

time over a socket. For example, to download a page from xkcd.com:

\begin{verbatim}

\end{verbatim}

By default, socket operations are \emph{blocking}: when the thread calls

a method like \texttt{connect} or \texttt{recv}, it pauses until the

operation completes.\footnote{Even calls to \texttt{send} can block, if

the recipient is slow to acknowledge outstanding messages and the

system's buffer of outgoing data is full.} Consequently to download

many pages at once, we need many threads. A sophisticated application

amortizes the cost of thread-creation by keeping idle threads in a

thread pool, then checking them out to reuse them for subsequent tasks;

it does the same with sockets in a connection pool.

And yet, threads are expensive, and operating systems enforce a variety

of hard caps on the number of threads a process, user, or machine may

have. On Jesse's system, a Python thread costs around 50k of memory, and

starting tens of thousands of threads causes failures. If we scale up to

tens of thousands of simultaneous operations on concurrent sockets, we

run out of threads before we run out of sockets. Per-thread overhead or

system limits on threads are the bottleneck.

In his influential article ``The C10K problem''\footnote{\url{http://www.kegel.com/c10k.html}},

Dan Kegel outlines the limitations of multithreading for I/O

concurrency. He begins,

\begin{quote}

It's time for web servers to handle ten thousand clients simultaneously,

don't you think? After all, the web is a big place now.

\end{quote}

Kegel coined the term ``C10K'' in 1999. Ten thousand connections sounds

dainty now, but the problem has changed only in size, not in kind. Back

then, using a thread per connection for C10K was impractical. Now the

cap is orders of magnitude higher. Indeed, our toy web crawler would

work just fine with threads. Yet for very large scale applications, with

hundreds of thousands of connections, the cap remains: there is a limit

beyond which most systems can still create sockets, but have run out of

threads. How can we overcome this?

\aosasecti{Async}\label{async}

Asynchronous I/O frameworks do concurrent operations on a single thread.

Let us find out how.

Async frameworks use \emph{non-blocking} sockets. In our async crawler,

we set the socket non-blocking before we begin to connect to the server:

\begin{verbatim}

\end{verbatim}

Irritatingly, a non-blocking socket throws an exception from

\texttt{connect}, even when it is working normally. This exception

replicates the irritating behavior of the underlying C function, which

sets \texttt{errno} to \texttt{EINPROGRESS} to tell you it has begun.

Now our crawler needs a way to know when the connection is established,

so it can send the HTTP request. We could simply keep trying in a tight

loop:

\begin{verbatim}

\end{verbatim}

This method not only wastes electricity, but it cannot efficiently await

events on \emph{multiple} sockets. In ancient times, BSD Unix's solution

to this problem was \texttt{select}, a C function that waits for an

event to occur on a non-blocking socket or a small array of them.

Nowadays the demand for Internet applications with huge numbers of

connections has led to replacements like \texttt{poll}, then

\texttt{kqueue} on BSD and \texttt{epoll} on Linux. These APIs are

similar to \texttt{select}, but perform well with very large numbers of

connections.

Python 3.4's \texttt{DefaultSelector} uses the best \texttt{select}-like

function available on your system. To register for notifications about

network I/O, we create a non-blocking socket and register it with the

default selector:

\begin{verbatim}

\end{verbatim}

We disregard the spurious error and call \texttt{selector.register},

passing in the socket's file descriptor and a constant that expresses

what event we are waiting for. To be notified when the connection is

established, we pass \texttt{EVENT\_WRITE}: that is, we want to know

when the socket is ``writable''. We also pass a Python function,

\texttt{connected}, to run when that event occurs. Such a function is

known as a \emph{callback}.

We process I/O notifications as the selector receives them, in a loop:

\begin{verbatim}

\end{verbatim}

The \texttt{connected} callback is stored as \texttt{event\_key.data},

which we retrieve and execute once the non-blocking socket is connected.

Unlike in our fast-spinning loop above, the call to \texttt{select} here

pauses, awaiting the next I/O events. Then the loop runs callbacks that

are waiting for these events. Operations that have not completed remain

pending until some future tick of the event loop.

What have we demonstrated already? We showed how to begin an operation

and execute a callback when the operation is ready. An async

\emph{framework} builds on the two features we have shown---non-blocking

sockets and the event loop---to run concurrent operations on a single

thread.

We have achieved ``concurrency'' here, but not what is traditionally

called ``parallelism''. That is, we built a tiny system that does

overlapping I/O. It is capable of beginning new operations while others

are in flight. It does not actually utilize multiple cores to execute

computation in parallel. But then, this system is designed for I/O-bound

problems, not CPU-bound ones.\footnote{Python's global interpreter lock

prohibits running Python code in parallel in one process anyway.

Parallelizing CPU-bound algorithms in Python requires multiple

processes, or writing the parallel portions of the code in C. But that

is a topic for another day.}

So our event loop is efficient at concurrent I/O because it does not

devote thread resources to each connection. But before we proceed, it is

important to correct a common misapprehension that async is

\emph{faster} than multithreading. Often it is not---indeed, in Python,

an event loop like ours is moderately slower than multithreading at

serving a small number of very active connections. In a runtime without

a global interpreter lock, threads would perform even better on such a

workload. What asynchronous I/O is right for, is applications with many

slow or sleepy connections with infrequent events.\footnote{Jesse listed

indications and contraindications for using async in ``What Is Async,

How Does It Work, And When Should I Use It?'', available at

pyvideo.org.}\footnote{Mike Bayer compared the throughput of asyncio

and multithreading for different workloads in his ``Asynchronous

Python and Databases'':

http://techspot.zzzeek.org/2015/02/15/asynchronous-python-and-databases/}

\aosasecti{Programming With Callbacks}\label{programming-with-callbacks}

With the runty async framework we have built so far, how can we build a

web crawler? Even a simple URL-fetcher is painful to write.

We begin with global sets of the URLs we have yet to fetch, and the URLs

we have seen:

\begin{verbatim}

\end{verbatim}

The \texttt{seen\_urls} set includes \texttt{urls\_todo} plus completed

URLs. The two sets are initialized with the root URL ``/''.

Fetching a page will require a series of callbacks. The

\texttt{connected} callback fires when a socket is connected, and sends

a GET request to the server. But then it must await a response, so it

registers another callback. If, when that callback fires, it cannot read

the full response yet, it registers again, and so on.

Let us collect these callbacks into a \texttt{Fetcher} object. It needs

a URL, a socket object, and a place to accumulate the response bytes:

\begin{verbatim}

\end{verbatim}

We begin by calling \texttt{Fetcher.fetch}:

\begin{verbatim}

\end{verbatim}

The \texttt{fetch} method begins connecting a socket. But notice the

method returns before the connection is established. It must return

control to the event loop to wait for the connection. To understand why,

imagine our whole application was structured so:

\begin{verbatim}

\end{verbatim}

All event notifications are processed in the event loop when it calls

\texttt{select}. Hence \texttt{fetch} must hand control to the event

loop, so that the program knows when the socket has connected. Only then

does the loop run the \texttt{connected} callback, which was registered

at the end of \texttt{fetch} above.

Here is the implementation of \texttt{connected}:

\begin{verbatim}

\end{verbatim}

The method sends a GET request. A real application would check the

return value of \texttt{send} in case the whole message cannot be sent

at once. But our request is small and our application unsophisticated.

It blithely calls \texttt{send}, then waits for a response. Of course,

it must register yet another callback and relinquish control to the

event loop. The next and final callback, \texttt{read\_response},

processes the server's reply:

\begin{verbatim}

\end{verbatim}

The callback is executed each time the selector sees that the socket is

``readable'', which could mean two things: the socket has data or it is

closed.

The callback asks for up to four kilobytes of data from the socket. If

less is ready, \texttt{chunk} contains whatever data is available. If

there is more, \texttt{chunk} is four kilobytes long and the socket

remains readable, so the event loop runs this callback again on the next

tick. When the response is complete, the server has closed the socket

and \texttt{chunk} is empty.

The \texttt{parse\_links} method, not shown, returns a set of URLs. We

start a new fetcher for each new URL, with no concurrency cap. Note a

nice feature of async programming with callbacks: we need no mutex

around changes to shared data, such as when we add links to

\texttt{seen\_urls}. There is no preemptive multitasking, so we cannot

be interrupted at arbitrary points in our code.

We add a global \texttt{stopped} variable and use it to control the

loop:

\begin{verbatim}

\end{verbatim}

Once all pages are downloaded the fetcher stops the global event loop

and the program exits.

This example makes async's problem plain: spaghetti code.

We need some way to express a series of computations and I/O operations,

and schedule multiple such series of operations to run concurrently. But

without threads, a series of operations cannot be collected into a

single function: whenever a function begins an I/O operation, it

explicitly saves whatever state will be needed in the future, then

returns. You are responsible for thinking about and writing this

state-saving code.

Let us explain what we mean by that. Consider how simply we fetched a

URL on a thread with a conventional blocking socket:

\begin{verbatim}

\end{verbatim}

What state does this function remember between one socket operation and

the next? It has the socket, a URL, and the accumulating

\texttt{response}. A function that runs on a thread uses basic features

of the programming language to store this temporary state in local

variables, on its stack. The function also has a ``continuation''---that

is, the code it plans to execute after I/O completes. The runtime

remembers the continuation by storing the thread's instruction pointer.

You need not think about restoring these local variables and the

continuation after I/O. It is built in to the language.

But with a callback-based async framework, these language features are

no help. While waiting for I/O, a function must save its state

explicitly, because the function returns and loses its stack frame

before I/O completes. In lieu of local variables, our callback-based

example stores \texttt{sock} and \texttt{response} as attributes of

\texttt{self}, the Fetcher instance. In lieu of the instruction pointer,

it stores its continuation by registering the callbacks

\texttt{connected} and \texttt{read\_response}. As the application's

features grow, so does the complexity of the state we manually save

across callbacks. Such onerous bookkeeping makes the coder prone to

migraines.

Even worse, what happens if a callback throws an exception, before it

schedules the next callback in the chain? Say we did a poor job on the

\texttt{parse\_links} method and it throws an exception parsing some

HTML:

\begin{verbatim}

\end{verbatim}

The stack trace shows only that the event loop was running a callback.

We do not remember what led to the error. The chain is broken on both

ends: we forgot where we were going and whence we came. This loss of

context is called ``stack ripping'', and in many cases it confounds the

investigator. Stack ripping also prevents us from installing an

exception handler for a chain of callbacks, the way a ``try / except''

block wraps a function call and its tree of descendents.\footnote{For a

complex solution to this problem, see

\url{http://www.tornadoweb.org/en/stable/stack_context.html}}

So, even apart from the long debate about the relative efficiencies of

multithreading and async, there is this other debate regarding which is

more error-prone: threads are susceptible to data races if you make a

mistake synchronizing them, but callbacks are stubborn to debug due to

stack ripping.

\aosasecti{Coroutines}\label{coroutines}

We entice you with a promise. It is possible to write asynchronous code

that combines the efficiency of callbacks with the classic good looks of

multithreaded programming. This combination is achieved with a pattern

called ``coroutines''. Using Python 3.4's standard asyncio library, and

a package called ``aiohttp'', fetching a URL in a coroutine is very

direct\footnote{The \texttt{@asyncio.coroutine} decorator is not

magical. In fact, if it decorates a generator function and the

\texttt{PYTHONASYNCIODEBUG} environment variable is not set, the

decorator does practically nothing. It just sets an attribute,

\texttt{\_is\_coroutine}, for the convenience of other parts of the

framework. It is possible to use asyncio with bare generators not

decorated with \texttt{@asyncio.coroutine} at all.}:

\begin{verbatim}

\end{verbatim}

It is also scalable. Compared to the 50k of memory per thread and the

operating system's hard limits on threads, a Python coroutine takes

barely 3k of memory on Jesse's system. Python can easily start hundreds

of thousands of coroutines.

The concept of a coroutine, dating to the elder days of computer

science, is simple: it is a subroutine that can be paused and resumed.

Whereas threads are preemptively multitasked by the operating system,

coroutines multitask cooperatively: they choose when to pause, and which

coroutine to run next.

There are many implementations of coroutines; even in Python there are

several. The coroutines in the standard ``asyncio'' library in Python

3.4 are built upon generators, a Future class, and the ``yield from''

statement. Starting in Python 3.5, coroutines will be a native feature

of the language itself\footnote{Python 3.5's built-in coroutines are

described in \href{https://www.python.org/dev/peps/pep-0492/}{PEP

492}, ``Coroutines with async and await syntax.'' At the time of this

writing, Python 3.5 was in beta, due for release in September 2015.};

however, understanding coroutines as they were first implemented in

Python 3.4, using pre-existing language facilities, is the foundation to

tackle Python 3.5's native coroutines.

To explain Python 3.4's generator-based coroutines, we will engage in an

exposition of generators and how they are used as coroutines in asyncio,

and trust you will enjoy reading it as much as we enjoyed writing it.

Once we have explained generator-based coroutines, we shall use them in

our async web crawler.

\aosasecti{How Python Generators Work}\label{how-python-generators-work}

Before you grasp Python generators, you have to understand how regular

Python functions work. Normally, when a Python function calls a

subroutine, the subroutine retains control until it returns, or throws

an exception. Then control returns to the caller:

\begin{verbatim}

\end{verbatim}

The standard Python interpreter is written in C. The C function that

executes a Python function is called, mellifluously,

\texttt{PyEval\_EvalFrameEx}. It takes a Python stack frame object and

evaluates Python bytecode in the context of the frame. Here is the

bytecode for \texttt{foo}:

\begin{verbatim}

\end{verbatim}

The \texttt{foo} function loads \texttt{bar} onto its stack and calls

it, then pops its return value from the stack, loads \texttt{None} onto

the stack, and returns \texttt{None}.

When \texttt{PyEval\_EvalFrameEx} encounters the \texttt{CALL\_FUNCTION}

bytecode, it creates a new Python stack frame and recurses: that is, it

calls \texttt{PyEval\_EvalFrameEx} recursively with the new frame, which

is used to execute \texttt{bar}.

\aosafigure[240pt]{crawler-images/function-calls.png}{Function Calls}{500l.crawler.functioncalls}

It is crucial to understand that Python stack frames are allocated in

heap memory! The Python interpreter is a normal C program, so its stack

frames are normal stack frames. But the \emph{Python} stack frames it

manipulates are on the heap. Among other surprises, this means a Python

stack frame can outlive its function call. To see this interactively,

save the current frame from within \texttt{bar}:

\begin{verbatim}

\end{verbatim}

The stage is now set for Python generators, which use the same building

blocks---code objects and stack frames---to marvelous effect.

This is a generator function:

\begin{verbatim}

\end{verbatim}

When Python compiles \texttt{gen\_fn} to bytecode, it sees the

\texttt{yield} statement and knows that \texttt{gen\_fn} is a generator

function, not a regular one. It sets a flag to remember this fact:

\begin{verbatim}

\end{verbatim}

When you call a generator function, Python sees the generator flag, and

it does not actually run the function. Instead, it creates a generator:

\begin{verbatim}

\end{verbatim}

A Python generator encapsulates a stack frame plus a reference to some

code, the body of \texttt{gen\_fn}:

\begin{verbatim}

\end{verbatim}

All generators from calls to \texttt{gen\_fn} point to this same code.

But each has its own stack frame. This stack frame is not on any actual

stack, it sits in heap memory waiting to be used:

\aosafigure[240pt]{crawler-images/generator.png}{Generators}{500l.crawler.generators}

The frame has a ``last instruction'' pointer, the instruction it

executed most recently. In the beginning, the last instruction pointer

is -1, meaning the generator has not begun:

\begin{verbatim}

\end{verbatim}

When we call \texttt{send}, the generator reaches its first

\texttt{yield}, and pauses. The return value of \texttt{send} is 1,

since that is what \texttt{gen} passes to the \texttt{yield} expression:

\begin{verbatim}

\end{verbatim}

The generator's instruction pointer is now 3 bytecodes from the start,

part way through the 56 bytes of compiled Python:

\begin{verbatim}

\end{verbatim}

The generator can be resumed at any time, from any function, because its

stack frame is not actually on the stack: it is on the heap. Its

position in the call hierarchy is not fixed, and it need not obey the

first-in, last-out order of execution that regular functions do. It is

liberated, floating free like a cloud.

We can send the value ``hello'' into the generator and it becomes the

result of the \texttt{yield} expression, and the generator continues

until it yields 2:

\begin{verbatim}

\end{verbatim}

Its stack frame now contains the local variable \texttt{result}:

\begin{verbatim}

\end{verbatim}

Other generators created from \texttt{gen\_fn} will have their own stack

frames and their own local variables.

When we call \texttt{send} again, the generator continues from its

second \texttt{yield}, and finishes by raising the special

\texttt{StopIteration} exception:

\begin{verbatim}

\end{verbatim}

The exception has a value, which is the return value of the generator:

the string ``done''.

\aosasecti{Building Coroutines With

Generators}\label{building-coroutines-with-generators}

So a generator can pause, and it can be resumed with a value, and it has

a return value. Sounds like a good primitive upon which to build an

async programming model, without spaghetti callbacks! We want to build a

``coroutine'': a routine that is cooperatively scheduled with other

routines in the program. Our coroutines will be a simplified version of

those in Python's standard ``asyncio'' library. As in asyncio, we will

use generators, futures, and the ``yield from'' statement.

First we need a way to represent some future result that a coroutine is

waiting for. A stripped-down version:

\begin{verbatim}

\end{verbatim}

A future is initially ``pending''. It is ``resolved'' by a call to

\texttt{set\_result}.\footnote{This future has many deficiencies. For

example, once this future is resolved, a coroutine that yields it

should resume immediately instead of pausing, but with our code it

does not. See asyncio's Future class for a complete implementation.}

Let us adapt our fetcher to use futures and coroutines. Review how we

wrote \texttt{fetch} with a callback:

\begin{verbatim}

\end{verbatim}

The \texttt{fetch} method begins connecting a socket, then registers the

callback, \texttt{connected}, to be executed when the socket is ready.

Now we can combine these two steps into one coroutine:

\begin{verbatim}

\end{verbatim}

Now \texttt{fetch} is a generator function, rather than a regular one,

because it contains a \texttt{yield} statement. We create a pending

future, then yield it to pause \texttt{fetch} until the socket is ready.

The inner function \texttt{on\_connected} resolves the future.

But when the future resolves, what resumes the generator? We need a

coroutine \emph{driver}. Let us call it ``task'':

\begin{verbatim}

\end{verbatim}

The task starts the \texttt{fetch} generator by sending \texttt{None}

into it. Then \texttt{fetch} runs until it yields a future, which the

task captures as \texttt{next\_future}. When the socket is connected,

the event loop runs the callback \texttt{on\_connected}, which resolves

the future, which calls \texttt{step}, which resumes \texttt{fetch}.

\aosasecti{Factoring Coroutines With

\texttt{yield from}}\label{factoring-coroutines-with-yield-from}

Once the socket is connected, we send the HTTP GET request and read the

server response. These steps need no longer be scattered among

callbacks; we gather them into the same generator function:

\begin{verbatim}

\end{verbatim}

This code, which reads a whole message from a socket, seems generally

useful. How can we factor it from \texttt{fetch} into a subroutine? Now

Python 3's celebrated \texttt{yield from} takes the stage. It lets one

generator \emph{delegate} to another.

To see how, let us return to our simple generator example:

\begin{verbatim}

\end{verbatim}

To call this generator from another generator, delegate to it with

\texttt{yield from}:

\begin{verbatim}

\end{verbatim}

The \texttt{caller} generator acts as if it were \texttt{gen}, the

generator it is delegating to:

\begin{verbatim}

\end{verbatim}

While \texttt{caller} yields from \texttt{gen}, \texttt{caller} does not

advance. Notice that its instruction pointer remains at 15, the site of

its \texttt{yield from} statement, even while the inner generator

\texttt{gen} advances from one \texttt{yield} statement to the

next.\footnote{In fact, this is exactly how ``yield from'' works in

CPython. A function increments its instruction pointer before

executing each statement. But after the outer generator executes

``yield from'', it subtracts 1 from its instruction pointer to keep

itself pinned at the ``yield from'' statement. Then it yields to

\emph{its} caller. The cycle repeats until the inner generator throws

\texttt{StopIteration}, at which point the outer generator finally

allows itself to advance to the next instruction.} From our

perspective outside \texttt{caller}, we cannot tell if the values it

yields are from \texttt{caller} or from the generator it delegates to.

And from inside \texttt{gen}, we cannot tell if values are sent in from

\texttt{caller} or from outside it. The \texttt{yield from} statement is

a frictionless channel, through which values flow in and out of

\texttt{gen} until it \texttt{gen} completes.

A coroutine can delegate work to a sub-coroutine with

\texttt{yield from} and receive the result of the work. Notice, above,

that \texttt{caller} printed ``return value of yield-from: done''. When

\texttt{gen} completed, its return value became the value of the

\texttt{yield from} statement in \texttt{caller}:

\begin{verbatim}

\end{verbatim}

Earlier, when we criticized callback-based async programming, our most

strident complaint was about ``stack ripping'': when a callback throws

an exception, the stack trace is typically useless. It only shows that

the event loop was running the callback, not \emph{why}. How do

coroutines fare?

\begin{verbatim}

\end{verbatim}

This is much more useful! The stack trace shows \texttt{caller\_fn} was

delegating to \texttt{gen\_fn} when it threw the error. Even more

comforting, we can wrap the call to a sub-coroutine in an exception

handler, the same is with normal subroutines:

\begin{verbatim}

\end{verbatim}

So we factor logic with sub-coroutines just like with regular

subroutines. Let us factor some useful sub-coroutines from our fetcher.

We write a \texttt{read} coroutine to receive one chunk:

\begin{verbatim}