Excellent work!

Reviewed 4 of 4 files at r1, 4 of 4 files at r2.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten and @tbg)

pkg/kv/kvserver/raftentry/cache.go, line 381 at r2 (raw file):

		}
		if i != 0 && e.Term < prevTerm {
			err := errors.Errorf("term regression idx %d: %d -> %d", prevIndex, e.Term, prevTerm)

I think e.Term and prevTerm should be swapped here.

Excellent sleuthing. Some drive-by comments because I was curious about this. I'm not at all familiar with this code.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten and @tbg)

pkg/kv/kvserver/raftentry/ring_buffer.go, line 75 at r2 (raw file):

			// (say the buf is idx=[100, 101, 102] and `lo` is 99),
			// we need to truncate everything.
			it, ok = iterateFrom(b, first(b).index(b))

first(b) is an iterator, which you're retrieving the index of to create another iterator that is at the index of first(b). I think it == first(b) unless I'm totally misunderstanding something. Which means you can simplify this to:

if f := first(b); f.index(b) > lo {
  it, ok = f, true
}

The semantics of iterateFrom are a bit surprising. I would think it would always return an iterator if there are any entries >= index. Did you consider putting this logic in iterateFrom? Would doing so break other use cases. It looks like ringBuf.get would need to be fixed, but this would fix ringBuf.scan.

Reviewed 4 of 4 files at r1, 4 of 4 files at r2.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @erikgrinaker, @petermattis, and @tbg)

pkg/kv/kvserver/raftentry/cache.go, line 187 at r1 (raw file):

	}
	if truncate {
		// Note that if !add, ents[0].Index may not even be in the cache

I think there's still an odd case here where add = true, truncate = true but we are attempting to insert a set of non-overlapping, earlier entries. In that case, it appears that ringBuf.add will be a no-op because it can't allow gaps. By definition, this is a case where truncating from the first index in ents will be equivalent to truncating from the last entry in ents - both broken before this PR, both fixed after it.

However, even after this PR, I think this will lead to the cache being empty instead of the higher-index entries being truncated and replaced by the lower-index entries. So we'll immediately miss the cache next time we try to query for those new entries.

Do you mind trying to create this scenario in a test? It will be something like add([10, 11, 12], true), add([4, 5, 6], true). We should end up with [4, 5, 6], but I suspect we'll end up with [].

This subtle interaction leads me to believe that we should be truncating before adding. We should probably also remove the Some entries were already overwritten branch to avoid the truncate operation's correctness depending on the add operation doing something that it doesn't always promise to do - overwriting every entry.

pkg/kv/kvserver/raftentry/cache.go, line 381 at r2 (raw file):

I agree.

pkg/kv/kvserver/raftentry/cache_test.go, line 196 at r1 (raw file):

	// Cache has entries 4, 5. Offer an oversize entry at index 3 (which is
	// notably before 4) and request truncation. This should clear all entries
	//>= 3, i.e. everything.

nit: spacing at beginning of line.

pkg/kv/kvserver/raftentry/ring_buffer.go, line 75 at r2 (raw file):

Which means you can simplify this to

+1 I also find this easier to understand, but we may want to make it even more clearly max(lo, first). How about something like:

it, ok := iterateFrom(b, max(lo, first(b).index(b)))

but this would fix ringBuf.scan

I'm not sure that it would. The contract of Scan is "If any entries are returned for the specified indices, they will start with index lo and proceed sequentially without gaps". So we seem to prefer returning nothing over skipping the lower bound index and returning other entries.

pkg/kv/kvserver/raftentry/ring_buffer.go, line 91 at r2 (raw file):

		if b.len > 0 {
			if lastIdx := last(b).index(b); lastIdx >= lo {
				err := errors.Errorf(

nit: why the separate variable definition?

Thanks for the reviews! Feedback addressed (all in a new commit). Appreciate another close look before I merge this.

Dismissed @erikgrinaker and @nvanbenschoten from a discussion.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @erikgrinaker, @nvanbenschoten, and @petermattis)

pkg/kv/kvserver/raftentry/cache.go, line 187 at r1 (raw file):

👍 thanks, this is a good simplification. Test case is added and passes now (it did not originally, just like you suspected).

pkg/kv/kvserver/raftentry/ring_buffer.go, line 75 at r2 (raw file):

Done.

Dismissed @petermattis from a discussion.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @erikgrinaker, @nvanbenschoten, and @petermattis)

pkg/kv/kvserver/raftentry/ring_buffer.go, line 75 at r2 (raw file):

Done.

LGTM, though I'm too distant from this code to give it a real stamp of approval.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @erikgrinaker and @nvanbenschoten)

Reviewed 5 of 5 files at r3.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @tbg)

pkg/kv/kvserver/raftentry/cache.go, line 184 at r3 (raw file):

	var bytesAdded, entriesAdded, bytesRemoved, entriesRemoved int32
	// We truncate (if requested) before adding. This can lead to "wasted"
	// work we're were zeroing out entries we would repopulate anyway, but

s/we're were/where we're/

pkg/kv/kvserver/raftentry/cache_test.go, line 104 at r3 (raw file):

		act = append(act, it.index(b))
		if len(act) > 1000 {
			panic("x")

Did you mean to say something here?

pkg/kv/kvserver/raftentry/ring_buffer.go, line 76 at r3 (raw file):

		// (say the buf is idx=[100, 101, 102] and `lo` is 99),
		// we need to truncate everything and need to use the
		// first index that gives us a valid iterator back.

I would point out explicitly that iterateFrom returns !ok if given an index below the first index in the buffer.

pkg/kv/kvserver/raftentry/ring_buffer.go, line 80 at r3 (raw file):

	}
	it, ok := iterateFrom(b, lo)
	if !ok {

Do we need this early return? The rest of the method works without it, which is probably an indication that we shouldn't add unnecessary branching which could eventually hide a bug.

pkg/kv/kvserver/raftentry/ring_buffer_test.go, line 17 at r3 (raw file):

	"github.com/stretchr/testify/require"
)

Think it's worth adding testing for each of the methods in the ringBuf's external interface (those in rangeCache)? These may be a bit redundant with the testing we already have for Cache, but given how much difficulty we seem to be having with getting this to be correct, tests at a few layers may not be a bad idea.

Or maybe we could have someone with fresh eyes (and a bit less on their plate at the moment) come and add some tests here.

TFTRs!

bors r=nvanbenschoten,erikgrinaker

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @erikgrinaker and @nvanbenschoten)

pkg/kv/kvserver/raftentry/cache_test.go, line 104 at r3 (raw file):

Oops, this is leftover debugging from fixing the bug where an iter on the empty buf accidentally ended up always valid. Removed.

pkg/kv/kvserver/raftentry/ring_buffer.go, line 80 at r3 (raw file):

We don't, good call.

pkg/kv/kvserver/raftentry/ring_buffer_test.go, line 17 at r3 (raw file):

Or maybe we could have someone with fresh eyes (and a bit less on their plate at the moment) come and add some tests here.

Heh, that'll never happen. I wrote unit tests. They didn't turn up anything, but it's nice to have them.