backoff_test.go

Documentation: k8s.io/client-go/util/flowcontrol

     1  /*
     2  Copyright 2015 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package flowcontrol
    18  
    19  import (
    20  	"testing"
    21  	"time"
    22  
    23  	testingclock "k8s.io/utils/clock/testing"
    24  )
    25  
    26  func TestSlowBackoff(t *testing.T) {
    27  	id := "_idSlow"
    28  	tc := testingclock.NewFakeClock(time.Now())
    29  	step := time.Second
    30  	maxDuration := 50 * step
    31  
    32  	b := NewFakeBackOff(step, maxDuration, tc)
    33  	cases := []time.Duration{0, 1, 2, 4, 8, 16, 32, 50, 50, 50}
    34  	for ix, c := range cases {
    35  		tc.Step(step)
    36  		w := b.Get(id)
    37  		if w != c*step {
    38  			t.Errorf("input: '%d': expected %s, got %s", ix, c*step, w)
    39  		}
    40  		b.Next(id, tc.Now())
    41  	}
    42  
    43  	//Now confirm that the Reset cancels backoff.
    44  	b.Next(id, tc.Now())
    45  	b.Reset(id)
    46  	if b.Get(id) != 0 {
    47  		t.Errorf("Reset didn't clear the backoff.")
    48  	}
    49  
    50  }
    51  
    52  func TestBackoffReset(t *testing.T) {
    53  	id := "_idReset"
    54  	tc := testingclock.NewFakeClock(time.Now())
    55  	step := time.Second
    56  	maxDuration := step * 5
    57  	b := NewFakeBackOff(step, maxDuration, tc)
    58  	startTime := tc.Now()
    59  
    60  	// get to backoff = maxDuration
    61  	for i := 0; i <= int(maxDuration/step); i++ {
    62  		tc.Step(step)
    63  		b.Next(id, tc.Now())
    64  	}
    65  
    66  	// backoff should be capped at maxDuration
    67  	if !b.IsInBackOffSince(id, tc.Now()) {
    68  		t.Errorf("expected to be in Backoff got %s", b.Get(id))
    69  	}
    70  
    71  	lastUpdate := tc.Now()
    72  	tc.Step(2*maxDuration + step) // time += 11s, 11 > 2*maxDuration
    73  	if b.IsInBackOffSince(id, lastUpdate) {
    74  		t.Errorf("expected to not be in Backoff after reset (start=%s, now=%s, lastUpdate=%s), got %s", startTime, tc.Now(), lastUpdate, b.Get(id))
    75  	}
    76  }
    77  
    78  func TestBackoffHighWaterMark(t *testing.T) {
    79  	id := "_idHiWaterMark"
    80  	tc := testingclock.NewFakeClock(time.Now())
    81  	step := time.Second
    82  	maxDuration := 5 * step
    83  	b := NewFakeBackOff(step, maxDuration, tc)
    84  
    85  	// get to backoff = maxDuration
    86  	for i := 0; i <= int(maxDuration/step); i++ {
    87  		tc.Step(step)
    88  		b.Next(id, tc.Now())
    89  	}
    90  
    91  	// backoff high watermark expires after 2*maxDuration
    92  	tc.Step(maxDuration + step)
    93  	b.Next(id, tc.Now())
    94  
    95  	if b.Get(id) != maxDuration {
    96  		t.Errorf("expected Backoff to stay at high watermark %s got %s", maxDuration, b.Get(id))
    97  	}
    98  }
    99  
   100  func TestBackoffGC(t *testing.T) {
   101  	id := "_idGC"
   102  	tc := testingclock.NewFakeClock(time.Now())
   103  	step := time.Second
   104  	maxDuration := 5 * step
   105  
   106  	b := NewFakeBackOff(step, maxDuration, tc)
   107  
   108  	for i := 0; i <= int(maxDuration/step); i++ {
   109  		tc.Step(step)
   110  		b.Next(id, tc.Now())
   111  	}
   112  	lastUpdate := tc.Now()
   113  	tc.Step(maxDuration + step)
   114  	b.GC()
   115  	_, found := b.perItemBackoff[id]
   116  	if !found {
   117  		t.Errorf("expected GC to skip entry, elapsed time=%s maxDuration=%s", tc.Since(lastUpdate), maxDuration)
   118  	}
   119  
   120  	tc.Step(maxDuration + step)
   121  	b.GC()
   122  	r, found := b.perItemBackoff[id]
   123  	if found {
   124  		t.Errorf("expected GC of entry after %s got entry %v", tc.Since(lastUpdate), r)
   125  	}
   126  }
   127  
   128  func TestIsInBackOffSinceUpdate(t *testing.T) {
   129  	id := "_idIsInBackOffSinceUpdate"
   130  	tc := testingclock.NewFakeClock(time.Now())
   131  	step := time.Second
   132  	maxDuration := 10 * step
   133  	b := NewFakeBackOff(step, maxDuration, tc)
   134  	startTime := tc.Now()
   135  
   136  	cases := []struct {
   137  		tick      time.Duration
   138  		inBackOff bool
   139  		value     int
   140  	}{
   141  		{tick: 0, inBackOff: false, value: 0},
   142  		{tick: 1, inBackOff: false, value: 1},
   143  		{tick: 2, inBackOff: true, value: 2},
   144  		{tick: 3, inBackOff: false, value: 2},
   145  		{tick: 4, inBackOff: true, value: 4},
   146  		{tick: 5, inBackOff: true, value: 4},
   147  		{tick: 6, inBackOff: true, value: 4},
   148  		{tick: 7, inBackOff: false, value: 4},
   149  		{tick: 8, inBackOff: true, value: 8},
   150  		{tick: 9, inBackOff: true, value: 8},
   151  		{tick: 10, inBackOff: true, value: 8},
   152  		{tick: 11, inBackOff: true, value: 8},
   153  		{tick: 12, inBackOff: true, value: 8},
   154  		{tick: 13, inBackOff: true, value: 8},
   155  		{tick: 14, inBackOff: true, value: 8},
   156  		{tick: 15, inBackOff: false, value: 8},
   157  		{tick: 16, inBackOff: true, value: 10},
   158  		{tick: 17, inBackOff: true, value: 10},
   159  		{tick: 18, inBackOff: true, value: 10},
   160  		{tick: 19, inBackOff: true, value: 10},
   161  		{tick: 20, inBackOff: true, value: 10},
   162  		{tick: 21, inBackOff: true, value: 10},
   163  		{tick: 22, inBackOff: true, value: 10},
   164  		{tick: 23, inBackOff: true, value: 10},
   165  		{tick: 24, inBackOff: true, value: 10},
   166  		{tick: 25, inBackOff: false, value: 10},
   167  		{tick: 26, inBackOff: true, value: 10},
   168  		{tick: 27, inBackOff: true, value: 10},
   169  		{tick: 28, inBackOff: true, value: 10},
   170  		{tick: 29, inBackOff: true, value: 10},
   171  		{tick: 30, inBackOff: true, value: 10},
   172  		{tick: 31, inBackOff: true, value: 10},
   173  		{tick: 32, inBackOff: true, value: 10},
   174  		{tick: 33, inBackOff: true, value: 10},
   175  		{tick: 34, inBackOff: true, value: 10},
   176  		{tick: 35, inBackOff: false, value: 10},
   177  		{tick: 56, inBackOff: false, value: 0},
   178  		{tick: 57, inBackOff: false, value: 1},
   179  	}
   180  
   181  	for _, c := range cases {
   182  		tc.SetTime(startTime.Add(c.tick * step))
   183  		if c.inBackOff != b.IsInBackOffSinceUpdate(id, tc.Now()) {
   184  			t.Errorf("expected IsInBackOffSinceUpdate %v got %v at tick %s", c.inBackOff, b.IsInBackOffSinceUpdate(id, tc.Now()), c.tick*step)
   185  		}
   186  
   187  		if c.inBackOff && (time.Duration(c.value)*step != b.Get(id)) {
   188  			t.Errorf("expected backoff value=%s got %s at tick %s", time.Duration(c.value)*step, b.Get(id), c.tick*step)
   189  		}
   190  
   191  		if !c.inBackOff {
   192  			b.Next(id, tc.Now())
   193  		}
   194  	}
   195  }
   196  
   197  func TestBackoffWithJitter(t *testing.T) {
   198  	id := "_idJitter"
   199  	tc := testingclock.NewFakeClock(time.Now())
   200  
   201  	// test setup: we show 11 iterations, series of delays we expect with
   202  	// a jitter factor of zero each time:
   203  	// 100ms  200ms  400ms  800ms  1.6s  3.2s  06.4s  12.8s  25.6s  51.2s  1m42s
   204  	// and with jitter factor of 0.1 (max) each time:
   205  	// 110ms  231ms  485ms  1.0s   2.1s  4.4s  09.4s  19.8s  41.6s  1m27s  2m6s
   206  	//
   207  	// with the following configuration, it is guaranteed that the maximum delay
   208  	// will be reached even though we are unlucky and get jitter factor of zero.
   209  	// This ensures that this test covers the code path for checking whether
   210  	// maximum delay has been reached with jitter enabled.
   211  	initial := 100 * time.Millisecond
   212  	maxDuration := time.Minute
   213  	maxJitterFactor := 0.1
   214  	attempts := 10
   215  
   216  	b := NewFakeBackOffWithJitter(initial, maxDuration, tc, maxJitterFactor)
   217  
   218  	assert := func(t *testing.T, factor int, prevDelayGot, curDelayGot time.Duration) {
   219  		low := time.Duration((float64(prevDelayGot) * float64(factor)))
   220  		high := low + time.Duration(maxJitterFactor*float64(prevDelayGot))
   221  		if !((curDelayGot > low && curDelayGot <= high) || curDelayGot == maxDuration) {
   222  			t.Errorf("jittered delay not within range: (%s - %s], but got %s", low, high, curDelayGot)
   223  		}
   224  	}
   225  
   226  	delays := make([]time.Duration, 0)
   227  	next := func() time.Duration {
   228  		tc.Step(initial)
   229  		b.Next(id, tc.Now())
   230  
   231  		delay := b.Get(id)
   232  		delays = append(delays, delay)
   233  		return delay
   234  	}
   235  
   236  	if got := b.Get(id); got != 0 {
   237  		t.Errorf("expected a zero wait durtion, but got: %s", got)
   238  	}
   239  
   240  	delayGot := next()
   241  	assert(t, 1, initial, delayGot)
   242  
   243  	prevDelayGot := delayGot
   244  	for i := 0; i < attempts; i++ {
   245  		delayGot = next()
   246  		assert(t, 2, prevDelayGot, delayGot)
   247  
   248  		prevDelayGot = delayGot
   249  	}
   250  
   251  	t.Logf("exponentially backed off jittered delays: %v", delays)
   252  }
   253
View as plain text