admission: reduce over-admission into the goroutine scheduler for latency isolation

sumeerbhola commented 1 year ago

(The issue described here will make things better for storage servers in multi-tenant settings. To improve things where user-facing SQL runs in the same node as KV and storage, we additionally need to address https://github.com/cockroachdb/cockroach/issues/85471)

The goal of kvSlotAdjuster is to achieve close to 100% CPU utilization (work-conserving) while not forming long queues of runnable goroutines in the goroutine scheduler (since the scheduler is not able to differentiate between work the way the admission control WorkQueue can). As discussed in https://docs.google.com/document/d/16RISoB3zOORf24k0fQPDJ4tTCisBVh-PkCZEit4iwV8/edit#heading=h.t3244p17un83, changing the scheduler to integrate admission and CPU scheduling would be the ideal solution, but that is not an option.

The current heuristic is to adjust work concurrency (slot count) by +1 or -1 based on whether the runnable queue length is below or above a threshold, defined by admission.kv_slot_adjuster.overload_threshold, which defaults to 32. This metric is sampled every 1ms, in order to be able to adjust quickly. Despite this high sampling, the heuristic is not performing well: we have noticed, while experimenting with the elastic tokens scheme, that the runnable=>running wait time histograms of goroutines show significant queuing delay in the goroutine scheduler with this heuristic. This suggests that the current heuristic over-admits. In the early days of admission control, there were some experiments with lower values of admission.kv_slot_adjuster.overload_threshold, both 16 and 8, which resulted in the CPU being idle despite the WorkQueue having waiting work. We should confirm this behavior.

The other avenue we can pursue to reduce over-admission is to use a different metric than mean runnable queue length sampled every 1ms (though whatever we choose will probably need to also be sampled at 1000Hz). Some rough initial ideas:

For all BatchRequests that finish in the last 1ms, compute the sum-runnable-time and sum-running-time. If the former is “high”, we may be over-admitting. Note that “high” is hard to define. Even the perfect scheduler-doing-admission scheme can have very high sum-runnable-time in order to be work-conserving. For example: 1 P and each work immediately blocks after admission. The scheduler will keep admitting since there is an idle P. Then after admitting a 100 requests, all become runnable, so sum-runnable-time will be high. So this approach does not seem viable.
Change the scheduler to count the number of times (or total time that the Ps were idle), and do the following at 1000Hz:
- Under: Compute an indicator of under-admittance, which is the predicate: idle-P-count > 0 AND WorkQueue length > 0.
- Over: Compute an indicator of over-admittance: idle-P-count == 0 AND sum-runnable-time >= sum-running-time.
- Right: Compute an indicator of right-admittance and admission backlog: idle-P-count == 0 AND sum-runnable-time < sum-running-time AND WorkQueue length > 0.
- When Under, increase slot count by 1. When Over, decrease slot count by 1. When Right, increase slot count by 1 with probability 0.5.

Jira issue: CRDB-21309

Epic CRDB-25469

sumeerbhola commented 12 months ago

Here is an approach for fixing both (a) this over-admission problem and (b) the priority inversion problem for SQLKVResponseWork and SQLSQLResponseWork https://github.com/cockroachdb/cockroach/issues/85471.

We eliminate the notion of slots and with every sample decide how many to admit until the next sample.

Sample the goroutine scheduler (runnable_goroutines, idle_procs) at high frequency, say every 20us.
Use a * P - runnable_goroutines + b * (idle_procs - runnable_goroutines) to decide the exact number of new work to admit, where P is the number of procs and a and b are constants we can tune. The idea here is that
- a * P is our goal of how many runnable goroutines we are willing to tolerate. If a is too low we can have idle P's, but we are able to tolerate a lower a because we are sampling at high frequency. A low a reduces the goroutine scheduling latency.
- a * P - runnable_goroutines is the number to admit to get closer to the goal. We clamp this to >= 0.
- idle_procs - runnable_goroutines represents idleness that can be explained by having too few runnable goroutines. Ideally this should be <= 0, but when it becomes > 0, b is the multiplier to admit a burst.

By sampling at high frequency and deciding exactly how many to admit (until the next sample) the feeback loop is tighter, compared to adjusting a slot count. Also, we don't need to know whether some admitted work is completed, since there is no slot count. So an admission request is simply grabbing a "token", therefore KV, SQKVResponse, SQLSQLResponse can share the same WorkQueue.

On linux, nanosleep along with chrt --rr 99 to run with high priority and SCHED_RR allows us to fairly accurately run with a 20us sleep. Here is a run with nanosleep with the histogram of observerd sleep times.

Total duration: 10.50457843s, Histogram:
[0s,16.383µs): 5
[16.384µs,32.767µs): 398145
[32.768µs,49.151µs): 1140
[49.152µs,65.535µs): 477
[65.536µs,81.919µs): 163
[81.92µs,98.303µs): 45
[98.304µs,114.687µs): 17
[114.688µs,131.071µs): 5
[131.072µs,147.455µs): 2

And a run with time.Ticker, which is much worse (causes are discussed in https://github.com/golang/go, issue 44343).

Total duration: 799.794795ms, Histogram:
[0s,16.383µs): 1296
[16.384µs,32.767µs): 1608
[32.768µs,49.151µs): 312
[49.152µs,65.535µs): 65
[65.536µs,81.919µs): 6
[81.92µs,98.303µs): 2
[524.288µs,540.671µs): 1
[901.12µs,917.503µs): 1
[933.888µs,950.271µs): 7
[950.272µs,966.655µs): 17
[966.656µs,983.039µs): 20
[983.04µs,999.423µs): 19
[999.424µs,1.015807ms): 33
[1.015808ms,1.032191ms): 296
[1.032192ms,1.048575ms): 225
[1.048576ms,1.064959ms): 66
[1.06496ms,1.081343ms): 20
[1.081344ms,1.097727ms): 4
[1.114112ms,1.130495ms): 1

A hacked up prototype of this is in https://github.com/sumeerbhola/cockroach/tree/ac_cpu

kv95 achieves 86% cpu utilization on a single node cluster. kv95 has tiny batches, so this is probably close to a worst case. The sampling callbacks were running at 33 KHz, so slightly slower than the configured 50 KHz (NB: if the callback is delayed because no CPU is available, it is relatively harmless since the work done in the callback is necessary only to prevent CPU becoming idle). On an unloaded machine they run at 40 KHz.

99th percentile of goroutine scheduling delay was ~750us which is low (very desirable).

In comparison, the current slot mechanism achieves 95% cpu utilization, but with a goroutine scheduling latency p99 pf 17ms (see plot below 19:01-19:04). Decreasing admission.kv_slot_adjuster.overload_threshold to 2 (from 19:04 onwards), gives us 81% cpu utilization and 4ms goroutine scheduling latency which are strictly worse than the 86% cpu utilization and 750us goroutine scheduling latency with this prototype.

The CPU overhead of this approach is modest. 0.83% of the 8 cpu machine is spent in the nanosleep.

sumeerbhola commented 12 months ago

32 node looks good too. Running at ~94% utilization

sumeerbhola commented 11 months ago

There is instability with 64 CPUs. Especially when concurrency of the workload is very high. When the WorkQueue queue length is high, the goschedstats frequency drops, sometimes as low as 1500 Hz. I suspect this is because the callback is trying to admit a lot of work. Increasing the b constant from 20 to 100 did not help. However, since the runnable goroutines were low (0.4 versus the target specified by a=2), I tried increasing a. At a=10, the queue length dropped and goschedstats callback frequency rose to 30 KHz. A simple feedback loop that adjusts a to get closer to the runnable goroutine goal (as long as there are waiting requests in the WorkQueue) may be sufficient.