storage: batch Raft entry application across ready struct

[nvanbenschoten]

Old prototype: #15648.

The Raft proposal pipeline currently applies Raft entries one-by-one to our storage engine in handleRaftReadyRaftMuLocked. We've seen time and time again that batching writes to RocksDB provides a sizable speedup, so this is a perfect candidate for batching. This will come with three concrete wins:

1. batching the writes reduces the total amount of work incident on the system
2. batching the writes reduces the number of cgo calls performed by Raft processing
3. batching the writes should speed up a single iteration of handleRaftReadyRaftMuLocked, allowing the Range to schedule and run the next iteration sooner

Put together, this should be a nice win to the amount of concurrency supported by the Raft proposal pipeline.

Implementation notes

To make this change we will need to transpose the order of operations in the committed entries loop and in processRaftCommand. Instead of the control flow looking like:

for each entry:
    check if failed
    if not:
        apply to engine
    ack client, release latches

it will look something like

for each entry:
    check if failed
    if not:
        apply to batch
commit batch
for each entry:
    ack client, release latches

Care will be needed around handling in-memory side effects of Raft entries correctly.

Predicted win

The improvement on single-range throughput as predicted by rafttoy is:

name                        old time/op    new time/op    delta
Raft/conc=256/bytes=256-16    15.6µs ± 5%    14.6µs ±15%  -6.87%  (p=0.046 n=16+20)

name                        old speed      new speed      delta
Raft/conc=256/bytes=256-16  16.4MB/s ± 5%  17.7MB/s ±17%  +8.30%  (p=0.043 n=16+20)

It's worth noting that rafttoy is using pebble instead of RocksDB. Writing to pebble doesn't incur a cgo call, which means that batching writes isn't quite as critical. This means that it's reasonable to expect the improvement to throughput in Cockroach will be even greater than this prediction.

[nvanbenschoten]

An optimization that falls out cleanly from this is that we can write the RangeAppliedStateKey (the combination of the RaftAppliedIndex, LeaseAppliedIndex, and RangeStats) only once per batch of committed entries instead of once per committed entry.

[ajwerner]

If a key is re-written many times in the same batch, do all of those writes end up in the memtable when the batch gets committed?

[nvanbenschoten]

do all of those writes end up in the memtable when the batch gets committed?

Yes. According to @ajkr they don't get collapsed until the memtable is compacted into L0.

[petermattis]

Yes. According to @ajkr they don't get collapsed until the memtable is compacted into L0.

Yep. I was just about to say the same thing.

[nvanbenschoten]

I've also seen lock contention here in Replica.handleReplicatedEvalResult interact poorly with above-Raft processing. If we were to move this work to once-per-Raft ready iteration instead of once-per-committed entry, I'm guessing we'd see some movement on workloads with single-Range hotspots.

[ajwerner]

I started typing this yesterday and there are some complications for which I want to propose a minor alteration.

The logic inside of Replica.handleReplicatedEvalResult() expects on-disk state to mirror in-memory state and also expects that the in-memory state reflects the on-disk state exactly upon application of the current command. In order to avoid majorly changing the existing logic I propose that we only batch commands which have a "trivial" ReplicatedEvalResult This is roughly the set of commands for which shouldAssert in handleReplicatedEvalResult false. This would excludes splits, merges, lease transfers, replica changes, any changes to the descriptor, etc.

This way all that needs to be accumulated as far as in-memory state goes should be the stats and and the index values which can be accumulated and then set atomically in the replica state when the batch commits and provides a clear location to write the RangeAppliedState. Commands which have a non-trivial ReplicatedEvalResult can be applied in their own "batch". These commands ought to be rare so this should provide roughly all of the win with less complexity. Sound reasonable?

[nvanbenschoten]

Discussed in person. This SGTM.