rushed-reflections

What's an event loop anyways?

Event loops are a paradigm for processing events different than your typical single-threaded or multi-threaded application. Your request gets broken down into async "events" that are executed in a loop to improve performance and minimize synchronization across threads. It is famously used by Node.js as the backbone of their event processing and also by several other technologies like Redis and Nginx.

In this article I'll explain the reason for why this paradigm was created and what it tries to optimize. By the end you'll come out a little wiser, and know more than just "don't block the event loop" :).

Motiviation - why event loops?

To understand why we need event loops we will explore a simple but key example. Take this straightforward HTTP request code, which sends a request and then tries to read the response from the socket:

def send_http_request_GET(domain: str, request: str) -> HttpResponse:
    socket_fd = get_socket_for_domain(domain)
    write_res = os.write(socket_fd, request)
    data = os.read(socket_fd, 1024)
    return HttpResponse(data)

We do two things in this call - write data out and read data in. Both of these actions will end up triggering syscalls through the kernel that write and fetch data. In terms of time spent on the CPU, this is relatively inexpensive; sending out packets takes very little time, and eventually reading the response will also take very little CPU time. The key time lost is from waiting on the server to respond to us. os.read will block this thread until the response is available, meaning that the thread cannot be used for any other processing during this time.

If our service is single-threaded, this means that we can't make any requests in parallel and are stuck waiting on any previous requests to finish. But of course, most services are not single-threaded, so this isn't a huge problem? Let's continue with the example code, imagining that instead we are processing these requests with multiple threads pulling from a request_queue.

class RequestQueue:
    queue: list[tuple[str, str]]
    lock: threading.Lock

def do_work(request_queue: RequestQueue):
    while len(request_queue.queue) > 0:
        domain = None
        request = None
        with request_queue.lock:
            if len(request_queue.queue) > 0:
                domain, request = request_queue.queue.popleft()
        
        if domain and request:
            send_http_request_GET(domain, request)

def send_http_request_GET(domain: str, request: str) -> HttpResponse:
    socket_fd = get_socket_for_domain(domain)
    write_res = os.write(socket_fd, request)
    data = os.read(socket_fd, 1024)
    return HttpResponse(data)

def process_requests(requests: list[tuple[str, str]]):
    queue = RequestQueue(queue=requests)
    threads = []
    for _ in range(10):
        thread = threading.Thread(target=do_work, args=(queue))
        threads.append(thread)
        thread.start()

    for thread in threads:
        thread.join()

Alright now we're cooking! We have multiple threads processing the list of requests, and we have 10X'ed our throughput, amazing. But we weren't here to just create yet another multi-threaded setup, so what is the problem here? Well, one major problem is that we are now managing 10 threads, which all have to be synchronized to get work from request_queue. Synchronization via locks can add a lot of overhead, slowing down our program (so we probably didn't actually get 10x gains here... unlucky). Another problem is that our throughput has a defined upper bound - 10 requests. We could solve that by bumping the number of threads. Let's say I want 10k requests as my throughput - I'll just increase it to 10k and things will be fine, right? Not quite. Aside from the increased sync overhead, we also have some additional issues that come up (as the saying goes, there is no such thing as a free lunch..):

  1. Extra memory to manage each thread (linear scaling)
  2. Coordination with every other thread -> latency (quadratic scaling)
  3. More context switches for the CPU. These are not free and can be a drag on latency at high concurrency.
  4. More threads == more CPU cache line thrashing!

We didn't have all these problems with our single-threaded program, so maybe we can tackle this problem in a different way. Let's see if we can get back that single-thread magic and start processing in parallel!

Enter the event loop

As you might have guessed, our event loop will be single threaded. So how are we going to avoid the blocking call that we saw earlier? Two things - a paradigm shift and a bit of help from the kernel.

Paradigm shift: working with Events

Now that we can't call read directly in our user code, we need to instead return something to express our intent to read as well as a way to continue executing our code. Let's call that "something" an Event. Concretely, an event describes the intent to do a syscall like read or write and a pointer to the code that should handle the result of that syscall. Putting that into code, the Event class would look something like this:

class Action(enum):
    READ = "read"
    WRITE = "write"

class Event:
    file_descriptor: int
    action: Action
    continuation: Callable[Event, Event]
    input: Any
    user_data: Any
    result: Any

Breaking it down, our event class contains:

  1. A file_descriptor to say which fd we want to perform the action on
  2. An action that we intend to execute
  3. A continuation that describes what to call with the result of the event
  4. input for the action
  5. user_data to allow passing along extra data we need to continuation
  6. result which will be read in the continuation

With this class we have created a bit of indirection between event processing and the start of processing. This enables us to defer execution of read until we are confident that there is actually data available to be read, which we will touch on in the next section. Before we get there though, we need to modify our code to actually talk in terms of events:

def on_read_finish(read_event: Event) -> Event:
    request_context = read_event.user_data
    return request_context.finish(HttpResponse(read_event.data))

def send_http_request_GET(domain: str, request: str, request_context: RequestContext) -> Event:
    socket_fd = get_socket_for_domain(domain)
    write_res = os.write(socket_fd, request)

    return create_read_event(socket_fd, 1024, continuation=on_read_finish, user_data=request_context)

Now we create an Event to express our intent to read, provide a pointer to our continuation, and some additional data we care about. Our code looks very different and has some extra boilerplate, but we are now in a position to execute the reads at the right time.

Waiting for data: the select syscall

Here's where the kernel comes in to help us build our event loop. The kernel provides a syscall called select which allows for asking to be notified when a set of file descriptors are ready for reading or writing. The key here is that select allows for waiting on multiple descriptors at the same time, enabling us to:

  1. gather a list of events that we are waiting on data for (i.e. need to call read with)
  2. start executing again when any of those events is ready for processing

This is the crux of event-based processing. We gather together as many pending events that we can, and then process them once they are ready. Rather than blocking for one single event to finish, we can continously make progress and add to the list of events that we are deferring until the data is available.

Putting it together

With our code returning Event objects and knowledge of the select syscall, we can now build our "async" event loop. The basic flow is this:

  1. Gather all pending events from previous continuations
  2. Call select on the list of associated file_descriptors
  3. Execute the list of events associated with the list of file_descriptors returned by select (read/write)
  4. Execute any continuations from the events in the previous step
  5. Save any new events
  6. Loop

And that flow in python would look something like this:

def execute_event(event: Event):
    result: int = -1
    if event.action == Action.READ:
        # execute read...
    elif event.action == Action.WRITE:
        # execute write...

    event.result = result

def event_loop():
    event_store = {}
    while True:
        pending_event_fds = [event.file_descriptor for event in event_store.values()]
        select_result = select.select(pending_event_fds, [], [])

        for fd in select_result[0]:
            event = event_store[fd]
            event_store.remove(fd)

            execute_event(event)
            if event.continuation:
                new_event = event.continuation(event)
                event_store[new_event.file_descriptor] = new_event

In an actual implementation we would need to add some initial events to get the loop started, for example by adding an event that periodically calls accept to accept new connections and start processing requests. After that we would just loop and execute the current events that we have.

A quick performance comparison

At this point we have two small implementations, one of multi-threaded event processing and another for event loop based processing. Let's put them to the test with a quick profile.

We will test both implementations with three separate workloads:

  1. high concurrency IO requests
  2. high concurrency high CPU requests
  3. high concurrency contentious requests (set a key in a collection)

In these workloads we expect the event loop to generally perform better in IO / contention contexts, where a thread pool will usually do better when there is majority CPU work as it can utilize multiple CPU cores.

IO Experiment

throughput latency
throughput_io latency_io

In the IO experiment we can see that the event loop matches the maximum request rate reached by the 256 thread thread pool. That is pretty amazing results for only using a single thread! In the chart on the right we can also see the P50, P95, and P99 latencies compared with each thread pool configuration. The latency improves for the thread pool as more threads are added, but generally it always underperforms the event loop (especially when tasks are longer).

CPU Experiment

throughput latency
throughput_cpu latency_cpu

In the CPU experiment the event loop struggle a lot. In this case I can't event plot all of the throughput values for the different work lengths because the latency grows insanely fast. Thread pool definitely wins here by being able to chop through that work efficiently, and generally more threads is better up to ~256. It is probably better to stick to a lower number of threads when you start getting diminishing returns, as threads add memory overhead and context switch costs.

Contention Experiment (setting a key in a shared dictionary)

throughput latency
image latency_image

The contention workload is another place where the event loop shines. This time around I just kept the # of threads static at 256, as modifying a single collection is a simple piece of work. We can see that as the request rate grows, lock contention becomes the dominating factor and the throughput of the thread pool stabilizes at ~25k requests/second. The event loop reaches 140k requests/second before leveling off. Naturally we see that the latency is much better with the event loop as well.

Benefits of event loops

Event loops have some unique performance characteristics that give them a unique advantage over the traditional thread pool for certain workflows. The primary advantages are:

  1. Great performance on IO workloads
  2. Single-threaded code means no need for synchronization and locking
  3. Simpler programming model due to no synchronization

Drawbacks of event loops

The achilles heel of the event loop is obviously the ability to block the loop with heavy CPU work. There are also some other disadvantages:

  1. Less clear programming model. Now we have to code in Events, which is less ergonomic than normal declarative programming.
  2. Not all types of code can be converted to an Event, meaning it does not work well for all workloads (e.g. GPU interaction)

It is worth noting though that Event style programming can be made better. The commonly supported async model is another representation of Event style programming, where we use the preprocessor / compiler to generate the indirect code for us.

Conclusion

We explored how to create a simple event loop and did some profiling. Event loops are a great illustration of the tradeoffs that can be taken when it comes to different workloads, so keep it in mind for your next project!

Thanks for reading!