This change is 

To expand on the note about auxiliary reasons for prioritizing this change, this is a WIP of what I picture back-pressuring writes on splits looking like. It relies on the changes to baseQueue we make here, including maintaining a handle to replicaItem through replica processing. An interesting test for that branch will be to watch how it behaves with a very small split size.

I did some testing of the impact parallelizing splits will have on workloads that
stress the split queue. While doing so, I also tested out my WIP branch
to backpressure writes on splits to see how it would impact these workloads.

To do this, I first dropped the range_max_bytes down to 4MB. I then spun up
kv --min-block-bytes=70000 --max-block-bytes=80000 --splits=0 --concurrency=16,
which was good at forcing lots of splits. With these relative sizes, it only
took about 50 writes to fully populate a range and push it over the max range
size. I then did some experimentation with the splitQueue, varying the level
of concurrency we gave it.

range_max_bytes=4MB split_concurrency=1

range_max_bytes=4MB split_concurrency=4

As the test shows, at a concurrency of 1, the split queue was unable to keep up
with the load and the number of ranges that needed to split grew at an unbounded
rate. When I increased the concurrency to 4, the split queue was able to keep up
and it never got stuck. As would be expected, there seemed to be a critical
level of concurrency necessary to keep up with the load. If the queue operated
below this level of concurrency, it would fail to keep up and would never catch up*. If
the queue operated above this level of concurrency, it would be able to keep up
and never get behind. For this test, that crossover point seemed to be between permitting
1 and 4 splits concurrently.

* it might eventually once the range count grew large enough that the load was sufficiently
spread out, but I suspect that this would have taken a long time

I then dropped the range_max_bytes from 4MB to 2MB, meaning that only
about 25 writes were required to fill up a range. I ran the tests again, this time,
keeping track of the largest range size over the course of the runs.

range_max_bytes=2MB split_concurrency=1

Nathans-MBP:cockroach$ curl http://nathans-mbp:8080/_status/ranges/local 2>/dev/null |\
  jq '[.ranges | .[] | {keyBytes: .state.state.stats.keyBytes | tonumber, valBytes: .state.state.stats.valBytes | tonumber } | .keyBytes + .valBytes] | max' |\
  awk '{print $1/1000000 "MB"}'

59.4194MB

~30x the range max bytes

range_max_bytes=2MB split_concurrency=4

Nathans-MBP:cockroach$ curl http://nathans-mbp:8080/_status/ranges/local 2>/dev/null |\
  jq '[.ranges | .[] | {keyBytes: .state.state.stats.keyBytes | tonumber, valBytes: .state.state.stats.valBytes | tonumber } | .keyBytes + .valBytes] | max' |\
  awk '{print $1/1000000 "MB"}'

6.43333MB

~3x the range max bytes

I also tried the second config with my WIP backpressure feature on. The graph looked
similar to range_max_bytes=2MB split_concurrency=4, but the max range size only
got up to 4.91065MB, ~2.5x the range max bytes. The backpressuring didn't put a
hard bound on the range size, but it did seem to help.

Finally, I dropped the range_max_bytes down all the way to 1MB. Here, none of the
graphs looked very good:

range_max_bytes=1MB split_concurrency=1

So bad I stopped testing right away.

range_max_bytes=1MB split_concurrency=4 with and without backpressure

While the graphs looked about the same for concurrency=4 with and without
backpressure enabled, there was a pretty clear distinction between the maximum
range size seen between these two test cases. Without it enabled, I saw ranges
get as large as 8.01927MB, ~8x the range max bytes. With it enabled, I saw
ranges grow to 3.59608MB, ~4x the range max bytes. However, the improved
effectiveness at bounding range size came at the clear expense of
99th-percentile latency. I'll continue the exploration of backpressure when I
actually push the change for review, but this is all in line with what we'd
expect.

Finally, I ran an experiment with a much larger amount of split concurrency. Even
with a range size of 1MB, the split queue was able to keep up. This demonstrates
that we may want to consider dynamically increasing the split concurrency when the
splitQueue is struggling to keep up.

range_max_bytes=1MB split_concurrency=16 with backpressure

Nice writeup!

Finally, I ran an experiment with a much larger amount of split concurrency. Even
with a range size of 1MB, the split queue was able to keep up. This demonstrates
that we may want to consider dynamically increasing the split concurrency when the
splitQueue is struggling to keep up.

Dynamically increasing split concurrency sounds a bit much. Splits are quick with these small ranges because the stats computation is so fast. With larger ranges increased concurrency might be a problem. Or maybe not. Rather than dynamically adjusting the concurrency, I think a cluster setting plus the back pressure mechanism would be sufficient in the near term.

Dynamically increasing split concurrency sounds a bit much.

Agreed. When would a dynamic adjustment be better than just a higher constant concurrency?

Review status: 0 of 12 files reviewed at latest revision, 2 unresolved discussions, all commit checks successful.

pkg/storage/queue.go, line 288 at r2 (raw file):

	processSem := make(chan struct{}, semCount)
	for i := 0; i < semCount; i++ {
		processSem <- struct{}{}

The semaphore pattern we use elsewhere (e.g. Stopper.RunLimitedAsyncTask) has the channel initially empty (and then we "acquire" by sending to the channel and "release" by receiving)

pkg/storage/queue.go, line 803 at r2 (raw file):

					// Lock processing so that we don't race with the
					// main process loop.
					defer bq.lockProcessing()()

This smells bad to me. Why do we need to shut down everything instead of just locking bq.mu?

Comments from Reviewable

TFTR!

When would a dynamic adjustment be better than just a higher constant concurrency?

That's a good point, we might as well just increase the max concurrency to start with. Based on the experiments I ran above and on Peter's point about larger ranges being more resource intensive, I think a concurrency of 4 for the splitQueue is still a good level for now.

Review status: 0 of 12 files reviewed at latest revision, 2 unresolved discussions, some commit checks pending.

pkg/storage/queue.go, line 288 at r2 (raw file):

Done.

pkg/storage/queue.go, line 803 at r2 (raw file):

Good point, we only needed to acquire from the semaphore once, since we were only running one task at a time. Done.

Comments from Reviewable

Reviewed 6 of 9 files at r1, 2 of 3 files at r2, 1 of 1 files at r4, 3 of 3 files at r5.
Review status: all files reviewed at latest revision, 2 unresolved discussions, all commit checks successful.

Comments from Reviewable

nit: this would have benefited from a release note mentioning the performance improvement.

@knz good point. I just opened a related change (#21673), so I put the release note there. The release note may be slightly misattributed, but I don't think that's a huge deal.