Leader promotions exceed default timeout values when etcd is holding many leases

[cosgroveb]

Hey folks,

This is a bit of a follow-up to the issue @mgates opened around improving lease performance #9418.

While testing out a cluster tracking many leases (millions) we noticed that if a leader election occurred, it would endlessly time out and fail to elect a leader leaving the cluster in an unhealthy state. After digging in and adding benchmarks to lessor.go it became apparent that the problem lies in the Promote method and, specifically, is another O(n) problem much like #9418.

Specifically, lessor iterates through the entire lease map several times and even sorts them (unsafeLeases).

These benchmarks show the effect pretty clearly:

func BenchmarkLessorPromote1(b *testing.B) { benchmarkLessorPromote(1, b) }                    
func BenchmarkLessorPromote10(b *testing.B) { benchmarkLessorPromote(10, b) }                  
func BenchmarkLessorPromote100(b *testing.B)  { benchmarkLessorPromote(100, b) }               
func BenchmarkLessorPromote1000(b *testing.B)  { benchmarkLessorPromote(1000, b) }             
func BenchmarkLessorPromote10000(b *testing.B)  { benchmarkLessorPromote(10000, b) }           
func BenchmarkLessorPromote100000(b *testing.B)  { benchmarkLessorPromote(100000, b) }         
}  
                                                                                               
func benchmarkLessorPromote(size int, b *testing.B) {                                          
  be, tmpPath := backend.NewDefaultTmpBackend()                                                
  le := newLessor(be, minLeaseTTL)                                                             
  defer le.Stop()                                                                              
  defer cleanup(be, tmpPath)                                                                   
  for i := 0; i < size; i++ {                                                                  
    le.Grant(LeaseID(i), int64(100+i))                                                         
  }                                                                                            
  b.ResetTimer()                                                                               
  for i := 0; i < b.N; i++ {                                                                   
    le.Promote(0)                                                                              
  }                                                                                            
}                                                                                              

Results:

goos: linux                                                              
goarch: amd64                                                            
BenchmarkLessorPromote1-16              10000000               142 ns/op 
BenchmarkLessorPromote10-16               100000             12679 ns/op 
BenchmarkLessorPromote100-16               10000            136276 ns/op 
BenchmarkLessorPromote1000-16               1000           1404405 ns/op 
BenchmarkLessorPromote10000-16                 3         401482438 ns/op 
BenchmarkLessorPromote100000-16                1        5157859968 ns/op 
PASS                                                                     
ok      _/home/pair/etcd/lease  16.093s                                  

Obviously, we can take stabs at some improvements but given the complexity of this routine, we're not really confident that we understand the intent of every part of it.

We observed that a workaround does exist in making the leaseRevokeRate unusually large. Is it possible to make anything configurable here or perhaps feature switch this off? If not, can you folks provide some guidance that could help us make some performance improvements with confidence?

cc @mgates @jcalvert

[gyuho]

Revoke rate is there to prevent spikes in Raft proposals.

We observed that a workaround does exist in making the leaseRevokeRate unusually large. Is it possible to make anything configurable here or perhaps feature switch this off?

Let's address slow revoke routine with #9418 first, and investigate further what's the next performance bottleneck.

Thanks!

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed after 21 days if no further activity occurs. Thank you for your contributions.