Stacktrace#09meta/rocksdb

RocksDB Keeps Score on Whether to Spin or Sleep

Pause for 1 microsecond, yield for up to 100, then sleep. Which of those a writer tries is learned at runtime, one write in 256 at a time.

Nov 2, 20269 min read

written byKarn

Every write in RocksDB that has to wait for another write runs the same little function. It spins, then it yields, then it gives up and sleeps. The interesting part is that the middle step is a bet, and RocksDB keeps a running score of whether the bet is paying off.

Writers wait for each other a lot

RocksDB is the LSM storage engine under a big chunk of the database world: MyRocks, CockroachDB's old storage layer, TiKV, Kafka Streams state stores, and plenty more. Its write path has a design that makes waiting a very hot operation.

When several threads call Put at once, they don't each grab a lock and write. They line up. The first one in becomes the group leader, collects the batches of everyone queued behind it, writes them all to the WAL in one go, and then tells the followers they're done (or tells them to apply their own memtable inserts in parallel). Followers spend their time in one place: JoinBatchGroup, waiting for the leader to flip their state.

That wait is usually short. A leader writing a WAL record and handing out work is microseconds of work. So the question "how should a thread wait for a few microseconds?" isn't academic here. It's on the path of every concurrent write.

All of it funnels into one function, WriteThread::AwaitState in db/write_thread.cc.

Step one: 200 pauses

The function opens with its whole plan written as a three-line comment, then the first step:

// 1. Busy loop using "pause" for 1 micro sec
// 2. Else SOMETIMES busy loop using "yield" for 100 micro sec (default)
// 3. Else blocking wait
 
// On a modern Xeon each loop takes about 7 nanoseconds (most of which
// is the effect of the pause instruction), so 200 iterations is a bit
// more than a microsecond.  This is long enough that waits longer than
// this can amortize the cost of accessing the clock and yielding.
for (uint32_t tries = 0; tries < 200; ++tries) {
  state = w->state.load(std::memory_order_acquire);
  if ((state & goal_mask) != 0) {
    return state;
  }
  port::AsmVolatilePause();
}

Look at the reasoning in that comment. It isn't "spin 200 times because 200 felt right". It's: a pause loop iteration costs about 7ns, so 200 of them is about a microsecond, and a microsecond is roughly what it costs to read the clock and call yield. Spin for as long as the next step would cost you anyway, then move on. Cheap waits never touch the clock at all.

Notice the word SOMETIMES in capitals on step 2. That's where it gets fun.

Why not just sleep on a mutex?

Because waking up a sleeping thread is slow. The author measured it, and left the numbers in the comment:

// If we're only going to end up waiting a short period of time,
// it can be a lot more efficient to call std::this_thread::yield()
// in a loop than to block in StateMutex().  For reference, on my 4.0
// SELinux test server with support for syscall auditing enabled, the
// minimum latency between FUTEX_WAKE to returning from FUTEX_WAIT is
// 2.7 usec, and the average is more like 10 usec.  That can be a big
// drag on RockDB's single-writer design.  Of course, spinning is a
// bad idea if other threads are waiting to run or if we're going to
// wait for a long time.  How do we decide?

10 microseconds on average from "wake up" to "awake", when the thing you're waiting for might take 5. So spinning with sched_yield is tempting. But spinning on a busy machine steals the core from someone who has real work, possibly the very leader you're waiting on.

The comment that follows splits waits into three kinds: short and uncontended (spin, obviously), long (sleep, obviously), and short but contended (depends). And then it says the clever bit out loud: you can tell whether the core is contended by timing your own yield. If nobody else wants the core, sched_yield comes straight back, well under a microsecond. If it takes longer, some other thread actually ran. A slow yield is the signal (lines 98-129).

"Slow" is a tunable, write_thread_slow_yield_usec, default 3 microseconds. The yield phase is capped by write_thread_max_yield_usec, default 100 (options.h). Three slow yields in one wait and the thread stops spinning and goes to sleep. One isn't enough, the comment says, because "solitary slow yields are pretty common (low-priority small jobs ready to run)".

The SOMETIMES: a running score per wait site

Here is the gate in front of the yield loop, with the lines that set it up:

yield_credit is a single std::atomic<int32_t> inside an AdaptationContext. There's one context per place in the code that waits, declared static right above the function that uses it, like static WriteThread::AdaptationContext jbg_ctx("JoinBatchGroup"); (line 403). So every thread in the process that waits in JoinBatchGroup shares one score.

The rule:

• Credit is zero or positive: yielding has been working lately. Everyone tries the yield loop.
• Credit is negative: yielding has been a waste. Skip it, go straight from the 200 pauses to the mutex.
• Either way, 1 wait in 256 is sampled (OneIn(256), a thread-local RNG). A sampled wait runs the yield loop even when the credit says don't, and its outcome gets written back.

That last bullet is what keeps it from getting stuck. If the score went negative during a noisy minute and nobody ever yielded again, it would stay negative forever. The sampled 1-in-256 waits keep testing the road not taken. If you've seen an epsilon-greedy bandit, it's that, in about ten lines of C++.

There's one more way the score gets updated: a wait that hits three slow yields sets update_ctx = true on the spot, sampled or not (lines 175-180). Bad news is reported immediately, good news only on a sample.

The update is one line

After the wait finishes, a thread that's supposed to report does this:

v = v - (v / 1024) + (would_spin_again ? 1 : -1) * 131072;

would_spin_again is true only if the leader released us during the yield loop. Timed out, or bailed after three slow yields, and it's false.

So each report shaves 1/1024 off the old score and then adds or subtracts 2^17. That's an exponential moving average of +1 / -1 outcomes in fixed point, all integer math, no floats. The sign is all the gate reads: positive means more recent samples said "yielding worked" than "it didn't". The comment above it does the overflow math: the score can't drift past 2^17 x 2^10 = 2^27, comfortably inside an int32 (lines 196-203).

And it's racy on purpose. Load, compute, store, with relaxed atomics, no CAS loop. Two threads updating at once means one update is lost. The code says so: "Since our update is sample based, it is ok if a thread overwrites the updates by other threads" (lines 193-194). A lost vote in a running average is noise. A CAS loop on a counter every waiter hammers would be the contention you were trying to avoid.

The decay that grew

That v - (v / 1024) has a history. The adaptive yield came in with concurrent memtable writes in 2015 (7d87f02, off by default then; enable_write_thread_adaptive_yield defaults to true today). In 2017 the undefined behavior sanitizer in RocksDB's crash test flagged a signed integer overflow in exactly this spot, -2147471630 + -16384 (issue 2559).

Here is that spot in the fix's own diff (58410ae):

A plus where the minus should be. The "decay" grew the score by 0.1% on every update instead of shrinking it, so whichever way it leaned, it leaned harder each time until it ran off the end of an int32. The fix flipped the sign, bumped the step to 2^17 and wrote the 2^27 bound into the comment.

What it teaches

• Spin for as long as the next step costs. 200 pauses is about a microsecond, about the cost of a clock read plus a yield. That's the whole justification, and it's in the comment.
• Measure contention with the thing you're already doing. No getrusage, no scheduler stats. A yield that takes 3 microseconds or more means someone else ran.
• An adaptive heuristic needs exploration. Without the 1-in-256 samples, one bad stretch could switch yielding off for good.
• A sloppy counter is fine when it's a vote. Lost updates to a moving average don't matter. Contention on it would.
• Sanitizers find math bugs, not just memory bugs. A sign error in a heuristic doesn't crash anything. It just quietly makes decisions. UBSan only noticed because the number finally overflowed.

The whole thing is about 150 lines, more than half of them comments, and the comments are the best part. Someone measured futex wake latency on their test server, wrote it down, and built a tiny learning loop around it.

Sources:

• meta/rocksdb db/write_thread.cc, the three-step plan and the pause loop (L68-L82)
• meta/rocksdb db/write_thread.cc, futex wake latency comment (L88-L96)
• meta/rocksdb db/write_thread.cc, short/long and slow yield reasoning (L98-L131)
• meta/rocksdb db/write_thread.cc, the gate and sampling (L133-L147)
• meta/rocksdb db/write_thread.cc, yield loop and slow yield bailout (L151-L190)
• meta/rocksdb db/write_thread.cc, the credit update (L192-L206)
• meta/rocksdb db/write_thread.cc, static AdaptationContext for JoinBatchGroup (L403)
• meta/rocksdb db/write_thread.h, AdaptationContext (L305-L310)
• meta/rocksdb include/rocksdb/options.h, adaptive yield defaults (L1473-L1505)
• meta/rocksdb commit 7d87f02, support for concurrent adds to memtable (2015)
• meta/rocksdb issue 2559, UBSan signed integer overflow in write_thread.cc
• meta/rocksdb commit 58410ae, fix the overflow bug in AwaitState (2017)

RocksDB is dual licensed under GPLv2 and Apache 2.0; excerpts above are quoted from the source with credit.