A Complete Guide to Lock Convoys | Dave Kilian's Blog

Dave Kilian's Blog

About

Blog

CV

GitHub

A Complete Guide to Lock Convoys

November 2022

Table of Contents

What’s a convoy?

Why do locks convoy?

What can I do about all this?

The caravan carries me onward<br>On my way at last, on my way at last!

Picture This

You’ve poured hours of blood, sweat, tears and keystrokes (mostly keystrokes) into your shiny new high throughput, low latency, ultra fast thing. Excitedly, you fire up your favorite benchmark and watch your new code rip through requests like a hot knife through butter. For a while, your code continues along at a brisk clip.

Then all of a sudden, throughput tanks. No matter how long you wait, it never improves again.

Oh well. Disappointing, but not wholly unexpected; this is new code after all! After confirming this was no fluke, you fire up your metrics system and get to work. But what you see is weird. No resource pools are being exhausted. No data structures are getting large. Heap activity looks nominal. Background work is proceeding normally. Internal timings look fine. In fact, no one part of the code seems to be at fault.

Throughput just collapses part of the way through your benchmark, and there’s no clear reason why.

Then you find something even weirder: you can sort of ‘fix’ the problem by stopping your benchmark workload and then starting it again. You don’t have to do anything else to your server — it fixes itself as soon as you stop pushing traffic! But run a little longer and, voomp, throughput drops again. Stop and restart the benchmark? Everything is fine! Until a minute later, when throughput collapses, again. What could possibly cause something like this?

You’re probably dealing with a lock convoy.

Part 1: What's a convoy?

Lock convoys were so named in a memo published by IBM researchers in the late 1970s. Despite being nearly 50 years old, the paper could describe the same phenomenon in modern computing systems almost word-for-word. Yep, convoys have been plauguing us for nigh on 50 years!

For a problem that has been causing headaches for so long, convoys seem to be little known and poorly understood, even among developers who work on the exact kinds of systems they tend to crop up in: high-performance multithreaded networked systems like databases and web servers. Why is that?

Well for one, lock convoys are a very in-the-weeds kind of problem. They arise from the interplay between the designs of your code, your CPU, your operating system kernel, and the way your locks are implemented in software. (The traffic your server is handling plays a major role too.) Most people have a murky understanding of things that go on inside CPUs and operating systems, so the details of lock convoys are murky too.

Let’s do something about that!

In this post, I’m going to do a deep dive into lock convoys: what they are, how they happen, and what you can do about them. Along the way, we’ll need to talk about things like CPU interrupts and operating system kernels. I’ll keep it as high-level as I can, but we really do need to go into some detail to understand all of what’s going on. If you want to get the most out of this post, prior familiarity with these topics would be helpful. If you want some background reading, I recommend

Operating Systems: Three Easy Pieces, a wonderful (and free!) online e-textbook on operating systems and the hardware interfaces underneath.

The Art of Multiprocessor Programming, a textbook that dives deep on lock design.

Let’s get started!

A ‘Request Convoy’

Let’s start by looking at a situation that’s very similar to a lock convoy, but doesn’t involve locks at all. This will help us build intuition around how a convoy behaves, without us having to dive into locks, interrupts and kernel traps just yet.

For this thought experiment, imagine you have some kind of server that accepts requests from the Internet. This server is single-threaded: it can only process one request at a time. Any other requests that arrive concurrently must wait in a request queue.

For the next step, I’m going to need some audience participation 🙂. I need you to set up a beat of some sort. You could snap your fingers in a rhythm, or tap your foot on the floor, or whatever you want to do. Just pick a good, steady rhythm, about 1-2 beats per second.

Are you snapping, tapping, drumming along now? Good!

Each time you snap your fingers, two things happen in very quick succession:

A request goes out . The server finishes the request it was working on

A request comes in . A new request arrives on the network, and the server starts working on it

The timings are unrealistically exact, for sure, but now we have a system that satisfies two key properties:

The request queue is always empty . New requests only arrive when the server is idle

The system is highly utilized . There is almost no idle time between requests

So far, timings in this system look pretty good: the turnaround...