The question
A thread pool needs a rule for which thread gets the next connection. The simple rule is round robin into mutex-protected queues. The usual alternative is work stealing: each worker owns a lock-free deque, and idle workers take work from busy ones. I wanted to measure whether stealing is worth its complexity in a small file server, and which steal policy works best.
The server
I wrote an HTTP/1.1 static file server in C from scratch. It uses epoll in edge-triggered mode for I/O and sendfile() for zero-copy transfers. The scheduler is pluggable, and four schedulers share the rest of the code:
- Round robin (RR): a mutex-protected FIFO queue per worker, with a condition variable. This is the baseline.
- Random steal (RS): a Chase-Lev lock-free deque per worker. An idle worker picks a random victim. This is the classic Cilk policy.
- Longest-queue steal (LQS): the idle worker reads every deque size and steals from the longest one.
- Adaptive steal (AS): each worker keeps a moving average of its p99 latency and steals sooner when latency goes above a target.
Each worker pops new work from the bottom of its own deque. A worker with nothing to do picks a random victim and steals the oldest connection from the top.
A toy simulation of the balancing idea, with the same arrivals in both modes. It does not model the benchmark. In the real runs, round robin also lost to its single accept thread and queue mutexes.
Random steal
Each worker pops new work from the bottom of its own deque. A worker with nothing to do picks a random victim and steals the oldest connection from the top.
Round robin
Each worker only reads its own mutex queue. When a big request lands in one queue, other workers sit idle while connections wait.
The deque owner pushes and pops at the bottom without locks. A thief takes from the top with one compare-and-swap on a versioned index, which prevents the ABA problem.
Measuring it
The server records latency in a log2-bucketed histogram, which gives p50, p95, p99, and p99.9 without storing every sample. Each deque also counts failed compare-and-swap operations, so the cost of contention is visible.
A Python script ran 48 benchmarks with wrk: 4 schedulers, at 1, 2, 4, and 8 threads, with 3 runs each of 15 seconds. A second script made the throughput, speedup, and scaling plots.
Results at 8 threads
| Scheduler | Requests/s | vs RR | p99 latency |
|---|---|---|---|
| Round robin | 2,998 | 1.00x | 349 µs |
| Random steal | 10,528 | 3.51x | 175 µs |
| Longest-queue steal | 7,993 | 2.67x | 175 µs |
| Adaptive steal | 5,609 | 1.87x | 524 µs |
- Random steal won. It had the highest throughput and a low p99 at every thread count. Picking a victim costs one modulo operation.
- Longest-queue steal only helped at 2 threads. There, the scan is one comparison. At 4 and 8 threads, reading every deque size cost more than the better balance gained.
- Adaptive steal lost to both simpler policies. The p99 signal is noisy, the moving average lags, and the controller overcorrects. It had the worst tail latency.
- Round robin collapsed as threads increased. The single accept thread and the queue mutexes became the bottleneck.
One limit: the load generator ran on the same 4-core machine as the server. That lowers absolute throughput at high thread counts, so the numbers above are best read as a comparison between schedulers, not as the server's maximum.
What I would do next
Accept connections on every worker with SO_REUSEPORT to remove the serial accept loop, and run the load generator on a separate machine. I wrote the full study as an IEEE-format paper, which is in the repository.