| 1 |
/* |
| 2 |
Copyright 2021 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 |
"fmt" |
| 21 |
"sync" |
| 22 |
"testing" |
| 23 |
"time" |
| 24 |
|
| 25 |
testingclock "k8s.io/utils/clock/testing" |
| 26 |
) |
| 27 |
|
| 28 |
func TestDroppedRequestsTracker(t *testing.T) { |
| 29 |
fakeClock := testingclock.NewFakeClock(time.Now()) |
| 30 |
tracker := newDroppedRequestsTracker(fakeClock.Now) |
| 31 |
|
| 32 |
// The following table represents the list over time of: |
| 33 |
// - seconds elapsed (as computed since the initial time) |
| 34 |
// - requests that will be recorded as dropped in a current second |
| 35 |
steps := []struct { |
| 36 |
secondsElapsed int |
| 37 |
// droppedRequests is the number of requests to drop, after |
| 38 |
// secondsElapsed. |
| 39 |
droppedRequests int |
| 40 |
// retryAfter is the expected retryAfter after all dropped |
| 41 |
// requests are recorded via RecordDroppedRequest. |
| 42 |
retryAfter int64 |
| 43 |
}{ |
| 44 |
{secondsElapsed: 0, droppedRequests: 5, retryAfter: 1}, |
| 45 |
{secondsElapsed: 1, droppedRequests: 11, retryAfter: 2}, |
| 46 |
// Check that we don't bump immediately after despite |
| 47 |
// multiple dropped requests. |
| 48 |
{secondsElapsed: 2, droppedRequests: 1, retryAfter: 2}, |
| 49 |
{secondsElapsed: 3, droppedRequests: 11, retryAfter: 4}, |
| 50 |
{secondsElapsed: 4, droppedRequests: 1, retryAfter: 4}, |
| 51 |
{secondsElapsed: 7, droppedRequests: 1, retryAfter: 8}, |
| 52 |
{secondsElapsed: 11, droppedRequests: 1, retryAfter: 8}, |
| 53 |
{secondsElapsed: 15, droppedRequests: 1, retryAfter: 7}, |
| 54 |
{secondsElapsed: 17, droppedRequests: 1, retryAfter: 6}, |
| 55 |
{secondsElapsed: 21, droppedRequests: 14, retryAfter: 5}, |
| 56 |
{secondsElapsed: 22, droppedRequests: 1, retryAfter: 10}, |
| 57 |
} |
| 58 |
|
| 59 |
for i, step := range steps { |
| 60 |
secondsToAdvance := step.secondsElapsed |
| 61 |
if i > 0 { |
| 62 |
secondsToAdvance -= steps[i-1].secondsElapsed |
| 63 |
} |
| 64 |
fakeClock.Step(time.Duration(secondsToAdvance) * time.Second) |
| 65 |
|
| 66 |
// Record all droppeded requests and recompute retryAfter. |
| 67 |
for r := 0; r < step.droppedRequests; r++ { |
| 68 |
tracker.RecordDroppedRequest("pl") |
| 69 |
} |
| 70 |
if retryAfter := tracker.GetRetryAfter("pl"); retryAfter != step.retryAfter { |
| 71 |
t.Errorf("Unexpected retryAfter: %v, expected: %v", retryAfter, step.retryAfter) |
| 72 |
} |
| 73 |
|
| 74 |
} |
| 75 |
} |
| 76 |
|
| 77 |
func TestDroppedRequestsTrackerPLIndependent(t *testing.T) { |
| 78 |
fakeClock := testingclock.NewFakeClock(time.Now()) |
| 79 |
tracker := newDroppedRequestsTracker(fakeClock.Now) |
| 80 |
|
| 81 |
// Report single dropped requests in multiple PLs. |
| 82 |
// Validate if RetryAfter isn't bumped next second. |
| 83 |
for i := 0; i < 10; i++ { |
| 84 |
tracker.RecordDroppedRequest(fmt.Sprintf("pl-%d", i)) |
| 85 |
} |
| 86 |
fakeClock.Step(time.Second) |
| 87 |
for i := 0; i < 10; i++ { |
| 88 |
tracker.RecordDroppedRequest(fmt.Sprintf("pl-%d", i)) |
| 89 |
retryAfter := tracker.GetRetryAfter(fmt.Sprintf("pl-%d", i)) |
| 90 |
if retryAfter != 1 { |
| 91 |
t.Errorf("Unexpected retryAfter for pl-%d: %v", i, retryAfter) |
| 92 |
} |
| 93 |
} |
| 94 |
|
| 95 |
// Record few droped requests on a single PL. |
| 96 |
// Validate that RetryAfter is bumped only for this PL. |
| 97 |
for i := 0; i < 5; i++ { |
| 98 |
tracker.RecordDroppedRequest("pl-0") |
| 99 |
} |
| 100 |
fakeClock.Step(time.Second) |
| 101 |
for i := 0; i < 10; i++ { |
| 102 |
tracker.RecordDroppedRequest(fmt.Sprintf("pl-%d", i)) |
| 103 |
retryAfter := tracker.GetRetryAfter(fmt.Sprintf("pl-%d", i)) |
| 104 |
switch i { |
| 105 |
case 0: |
| 106 |
if retryAfter != 2 { |
| 107 |
t.Errorf("Unexpected retryAfter for pl-0: %v", retryAfter) |
| 108 |
} |
| 109 |
default: |
| 110 |
if retryAfter != 1 { |
| 111 |
t.Errorf("Unexpected retryAfter for pl-%d: %v", i, retryAfter) |
| 112 |
} |
| 113 |
} |
| 114 |
} |
| 115 |
// Validate also PL for which no dropped requests was recorded. |
| 116 |
if retryAfter := tracker.GetRetryAfter("other-pl"); retryAfter != 1 { |
| 117 |
t.Errorf("Unexpected retryAfter for other-pl: %v", retryAfter) |
| 118 |
} |
| 119 |
} |
| 120 |
|
| 121 |
func BenchmarkDroppedRequestsTracker(b *testing.B) { |
| 122 |
b.StopTimer() |
| 123 |
|
| 124 |
fakeClock := testingclock.NewFakeClock(time.Now()) |
| 125 |
tracker := newDroppedRequestsTracker(fakeClock.Now) |
| 126 |
|
| 127 |
startCh := make(chan struct{}) |
| 128 |
wg := sync.WaitGroup{} |
| 129 |
numPLs := 5 |
| 130 |
// For all `numPLs` priority levels, create b.N workers each |
| 131 |
// of which will try to record a dropped request every 100ms |
| 132 |
// with a random jitter. |
| 133 |
for i := 0; i < numPLs; i++ { |
| 134 |
plName := fmt.Sprintf("priority-level-%d", i) |
| 135 |
for i := 0; i < b.N; i++ { |
| 136 |
wg.Add(1) |
| 137 |
go func() { |
| 138 |
defer wg.Done() |
| 139 |
<-startCh |
| 140 |
|
| 141 |
for a := 0; a < 5; a++ { |
| 142 |
tracker.RecordDroppedRequest(plName) |
| 143 |
time.Sleep(25 * time.Millisecond) |
| 144 |
} |
| 145 |
}() |
| 146 |
} |
| 147 |
} |
| 148 |
// Time-advancing goroutine. |
| 149 |
stopCh := make(chan struct{}) |
| 150 |
timeWg := sync.WaitGroup{} |
| 151 |
timeWg.Add(1) |
| 152 |
go func() { |
| 153 |
defer timeWg.Done() |
| 154 |
for { |
| 155 |
select { |
| 156 |
case <-stopCh: |
| 157 |
return |
| 158 |
case <-time.After(25 * time.Millisecond): |
| 159 |
fakeClock.Step(time.Second) |
| 160 |
} |
| 161 |
} |
| 162 |
}() |
| 163 |
|
| 164 |
b.StartTimer() |
| 165 |
close(startCh) |
| 166 |
wg.Wait() |
| 167 |
|
| 168 |
close(stopCh) |
| 169 |
timeWg.Wait() |
| 170 |
} |