Really cool stuff... Andrew, I realized half way through reviewing that I'm not sure whether you'd prefer reviewers to review in "atomic commits" or "full PR" style. Looks like you're going for the latter which I'm fine with but just checking.

Reviewed 7 of 7 files at r1, 3 of 3 files at r2, 7 of 7 files at r3, 3 of 3 files at r4, 3 of 3 files at r5.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @ajwerner, @lucy-zhang, and @spaskob)

pkg/kv/kvserver/client_replica_test.go, line 3142 at r1 (raw file):

}

func TestProposalOverhead(t *testing.T) {

Mind adding a comment on the purpose of this test?

pkg/kv/kvserver/replica_write.go, line 573 at r1 (raw file):

	batch := r.store.Engine().NewBatch()
	var opLogger *storage.OpLoggerBatch
	if r.isSystemRange() || RangefeedEnabled.Get(&r.store.cfg.Settings.SV) {

Nice, this will improve my situation for LISTEN/NOTIFY as well.

pkg/sql/lease.go, line 895 at r3 (raw file):

//
// TODO(ajwerner): This really just needs to acquire a lease on the ID newer
// than something. Not necessarily newer than

nit: this is an incomplete comment.

pkg/sql/lease.go, line 1795 at r3 (raw file):

	// we don't know if rangefeeds are enabled. Grr. I guess the deal is that when
	// it gets enabled then we flip the switch? We don't want to force the nodes
	// to restart to get the goodness. We also want to be able to stop gossipping.

I'm not sure but I think these comments might be your internal brainstorming.

pkg/sql/lease.go, line 1919 at r3 (raw file):

			// change occurred.
			const withDiff = false
			log.Infof(ctx, "starting rangefeed from %v on %v", m.initialTimestamp, span)

This might want to be a VEventf, but if not, you should probably say "starting lease rangefeed" to make it more clear.

pkg/sql/lease.go, line 1940 at r3 (raw file):

		var descriptor sqlbase.Descriptor
		if err := ev.Value.GetProto(&descriptor); err != nil {
			log.Fatalf(ctx, "%s: unable to unmarshal descriptor %v", ev.Key, ev.Value)

I don't think this should be a Fatal. A corrupted descriptor would be bad, but I'd prefer not to see an unrecoverable crashloop from it.

pkg/sql/lease.go, line 1961 at r3 (raw file):

		}
		if log.V(0) {
			log.Infof(ctx, "%s: refreshing lease table: %d (%s), version: %d, dropped: %t",

Should this be V(1)?

pkg/sql/lease.go, line 1977 at r3 (raw file):

			case e := <-eventCh:
				if e.Checkpoint != nil {
					log.Infof(ctx, "got checkpoint %v", e.Checkpoint)

V() it?

pkg/sql/lease.go, line 2106 at r5 (raw file):

) chan struct{} {
	// TODO(ajwerner): Add a callback to notify about version changes.
	// Checking is pretty cheap but really this should be a callback.

Isn't there a cluster setting that gets changed when a version is finalized? Cluster settings have callbacks attached to them, could you use that?

pkg/sql/lease_test.go, line 2161 at r3 (raw file):

				},
				Server: &server.TestingKnobs{
					// TODO(ajwerner): A

☝️

pkg/sql/lease_test.go, line 2172 at r3 (raw file):

	db := tc.ServerConn(0)
	tdb := sqlutils.MakeSQLRunner(db)
	tdb.Exec(t, "SET CLUSTER SETTING kv.closed_timestamp.target_duration = '100ms';")

Why does this need to be set?

pkg/sql/lease_test.go, line 2229 at r3 (raw file):

	require.NoError(t, txA.Rollback())

	const extremelyLongTime = 100 * time.Second

This is going to be kind of annoying in CI if it starts failing, can it be less than 100 secs?

Can we get ahead of the testing game here by writing a mixed logical version test? I'm not sure what parts we'd want to specifically stress, but just wanted to float the general idea.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @ajwerner, @jordanlewis, @lucy-zhang, and @spaskob)

pkg/sql/lease.go, line 1940 at r3 (raw file):

You can use log.ReportOrPanic.

pkg/sql/lease.go, line 1866 at r13 (raw file):

				}

			case <-s.ShouldStop():

Should this be ShouldQuiesce? I've had some trouble with servers hanging when they dont' quit until the Stop signal. It's possible I dont' fully understand when to use which.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @lucy-zhang, and @spaskob)

pkg/sql/lease.go, line 1940 at r3 (raw file):

Done.

pkg/sql/lease.go, line 1866 at r13 (raw file):

I used ShouldStop here because the old loop used ShouldStop. It seems like there are two possibilities:

1. We have some code that wants to run unimpeded and complete a schema change cleanly while we're quiescing (seems unlikely)
2. This uses ShouldStop for no reason (seems likely)

Given the is 2015 code I was cargo culting, I'm going to go with 2).

Done.

Can we get ahead of the testing game here by writing a mixed logical version test? I'm not sure what parts we'd want to specifically stress, but just wanted to float the general idea.

The mixed-version schema change tests that @spaskob has been working on should stress this quite a bit. I'm not sure what more I would want than that.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @lucy-zhang, and @spaskob)

Reviewed 1 of 16 files at r6, 1 of 15 files at r12, 9 of 12 files at r13, 6 of 8 files at r14, 1 of 3 files at r15, 2 of 2 files at r16.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @ajwerner, @jordanlewis, and @spaskob)

pkg/sql/lease.go, line 732 at r15 (raw file):

		// acquisition finishes but indicate that that new lease is expired are not
		// ignored.
		acquisitionsInProgress int

This is fixing a pre-existing race condition, right?

pkg/sql/lease.go, line 1823 at r16 (raw file):

// leases for tables received in the latest system configuration via gossip or
// rangefeeds. This function must be passed a non-nil gossip if
// VersionRangefeeedLeases is not active.

nit: Rangefeed

pkg/sql/lease.go, line 1855 at r16 (raw file):

				// Try to refresh the table lease to one >= this version.
				if err := purgeOldVersions(

I might log at level 2 or 3 somewhere around here indicating we got a new version.

pkg/sql/lease.go, line 1899 at r16 (raw file):

			// Note: It's okay that the cancelation of gossip watching is
			// asynchronous. At worst we'd get duplicate updates or stale updates.
			// Both of those are handled.

Would you mind briefly commenting on why we're guaranteed to not miss any updates when we switch over? If we pass the last seen timestamp that we got from gossip to the rangefeed, are we guaranteed to get all updates since that timestamp?

pkg/sql/lease_test.go, line 220 at r16 (raw file):

			t.cfg,
		)
		mgr.PeriodicallyRefreshSomeLeases(context.Background())

Maybe add a log tag?

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @lucy-zhang, and @spaskob)

pkg/sql/lease.go, line 1866 at r13 (raw file):

Done.

pkg/sql/lease.go, line 732 at r15 (raw file):

Correct.

pkg/sql/lease.go, line 1823 at r16 (raw file):

Done.

pkg/sql/lease.go, line 1855 at r16 (raw file):

Done.

pkg/sql/lease.go, line 1899 at r16 (raw file):

are we guaranteed to get all updates since that timestamp?

Indeed.
Done.

pkg/sql/lease_test.go, line 220 at r16 (raw file):

Done.