~ $ cd research/one-lock-at-a-time && cat README.md

One lock at a time

For a year I worked inside a database engine. It was not mine — everything that makes it a database was there when I arrived — and I worked all over it. This page is about one part of that year: making its core concurrent. It ran under one global lock, and that is worse than it sounds.

What follows is about the techniques, which are anybody's, and about what each one bought, which I measured. How the engine is made inside is its owners' business, and is not here.

Where it started

The benchmark was a standard one: twenty queries, run by 1, 2, 4, 8 and 16 threads at once, three times each after a warm-up. Every figure on this page is a speed-up against the same thing: the original engine, doing the same work with one thread.

Below one, all the way. Eight threads finished the work in a quarter more time than one thread would have needed. A global lock does not merely fail to help: the threads spend their time handing it to each other.

Measure the locks, not the program

A profiler says where the time goes. It does not say who was waiting for whom. So I put counters inside the locks themselves: how many times each was taken, and how many of those found it already held.

The answer was not spread out. One lock was taken 93 million times in a run, and 6.6% of those collided; every other lock sat near zero. That redirected the whole effort.

The steps, and what each one bought

Every step lived on a branch of its own and was run through the same benchmark, so each has a number. Speed-up with eight threads:

Six techniques, and none of them is exotic.

Thread-local scratch space

What every operation scribbles on while it works stops being shared. On its own it bought nothing, because nothing could run side by side yet to fight over it; it had to be there before anything else could work.

A shared/exclusive lock

Queries read and rarely write, so the one lock becomes shared for readers and exclusive for writers, swapped in a critical section at a time.

Atomic counters

Where a lock only protected a count going up and down, the count becomes atomic and the lock goes.

A lock-free hot path

The operation every query performs thousands of times is rewritten around compare-and-swap: read the state, compute the new one, swap only if nobody moved it, and undo if a second thing it depends on changed meanwhile.

Finer granularity

What is left of that lock is split: one lock for each part of the structure instead of one for all of it, so that two threads collide only when they want the same part.

Positional I/O, and ordered locking

Files read and written by position, so that a file needs no lock just to keep its cursor still; and whenever several locks must be held at once, they are taken in order of memory address, which is the whole of deadlock avoidance when you can do it.

The bar that went the wrong way

The marked bar is the one worth the page. Letting readers in together was the right change, and it made everything twice as slow.

Why would letting readers in be slower than making them queue? Because of what is underneath. With one exclusive lock at the door, a thread waits once, and then finds every lock inside free: they are all taken and released with nobody else asking, which costs almost nothing. Open the door and the readers meet at every one of those inner locks instead, many times an operation, and a thread that finds a lock taken gives up the processor and has to be woken again. My notes of the time say it in a line: each conflict means losing the CPU. One long queue had been traded for thousands of short ones, each with a sleep in it.

The next bar says which lock it was. Replacing one inner lock by atomic counters, and nothing else, took the same benchmark from 0.36 to 2.41. Nearly every query had slowed down by the same factor under the shared lock, and nearly every one came back with that single change.

A concurrent program is only as wide as its narrowest lock, and widening any other makes the queue at that one longer. Coarse to fine is the right direction, and the first step along it can cost you, until the last of the narrow places is gone.

Which lock

Which primitive, too, mattered more than I expected. I timed some twenty combinations of mutex and lock — POSIX's, spins, futexes, condition variables, with priority for readers or without — and on the same query with eight threads the slowest took eight times as long as the fastest.

The lock I ended with has five states. Readers see three of them, and the one called closing is where its fairness is: once a writer has asked, no new reader gets in, so a stream of readers cannot starve it.

Writers see the other two, and the same idea the other way round: whoever asks while a writer is inside is remembered, and woken when it leaves.

Write it down first

Before writing the lock-free path I wrote it down: every atomic step numbered, each with its precondition and postcondition, under the invariants of the whole, and drew its states. A first attempt, without that, had been thrown away for its bugs. No test finds the interleaving that happens once a week; an invariant does.

Where it ended

The same benchmark, the same machine, at the end of the year:

Faster than the original even with a single thread: a lock nobody contends for still costs something, and most of them were gone.

From 0.78 to 4.39 at eight threads. The queries that mostly read went further: 7.0 for the best of them, and above 6 for three more. One query of the twenty never scaled at all: 0.83 at sixteen threads.

Sixteen threads added nothing over eight. And it was not finished when I left: the most advanced version still had bugs open.

The other half: tasks

Making an engine safe for threads is no use to someone who cannot write threads. So its programming interface got a small framework of tasks: serial, parallel and for-each, with cancellation, and exceptions that arrive where the task was started. The benchmark's queries were rewritten on it to see whether it held.

It is the same idea as my thesis, which it sat in the middle of, and as the recipe I used for Raft four years later: the machine being parallel is the easy part.