| 1 |
/* |
| 2 |
Copyright 2019 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 queueset |
| 18 |
|
| 19 |
import ( |
| 20 |
"context" |
| 21 |
"errors" |
| 22 |
"fmt" |
| 23 |
"math" |
| 24 |
"os" |
| 25 |
"reflect" |
| 26 |
"sort" |
| 27 |
"strings" |
| 28 |
"sync" |
| 29 |
"sync/atomic" |
| 30 |
"testing" |
| 31 |
"time" |
| 32 |
|
| 33 |
"k8s.io/apimachinery/pkg/util/sets" |
| 34 |
"k8s.io/utils/clock" |
| 35 |
|
| 36 |
"k8s.io/apiserver/pkg/authentication/user" |
| 37 |
genericrequest "k8s.io/apiserver/pkg/endpoints/request" |
| 38 |
"k8s.io/apiserver/pkg/util/flowcontrol/counter" |
| 39 |
"k8s.io/apiserver/pkg/util/flowcontrol/debug" |
| 40 |
fq "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing" |
| 41 |
"k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing/promise" |
| 42 |
test "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing/testing" |
| 43 |
testeventclock "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing/testing/eventclock" |
| 44 |
testpromise "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing/testing/promise" |
| 45 |
"k8s.io/apiserver/pkg/util/flowcontrol/metrics" |
| 46 |
fcrequest "k8s.io/apiserver/pkg/util/flowcontrol/request" |
| 47 |
"k8s.io/klog/v2" |
| 48 |
) |
| 49 |
|
| 50 |
// fairAlloc computes the max-min fair allocation of the given |
| 51 |
// capacity to the given demands (which slice is not side-effected). |
| 52 |
func fairAlloc(demands []float64, capacity float64) []float64 { |
| 53 |
count := len(demands) |
| 54 |
indices := make([]int, count) |
| 55 |
for i := 0; i < count; i++ { |
| 56 |
indices[i] = i |
| 57 |
} |
| 58 |
sort.Slice(indices, func(i, j int) bool { return demands[indices[i]] < demands[indices[j]] }) |
| 59 |
alloc := make([]float64, count) |
| 60 |
var next int |
| 61 |
var prevAlloc float64 |
| 62 |
for ; next < count; next++ { |
| 63 |
// `capacity` is how much remains assuming that |
| 64 |
// all unvisited items get `prevAlloc`. |
| 65 |
idx := indices[next] |
| 66 |
demand := demands[idx] |
| 67 |
if demand <= 0 { |
| 68 |
continue |
| 69 |
} |
| 70 |
// `fullCapacityBite` is how much more capacity would be used |
| 71 |
// if this and all following items get as much as this one |
| 72 |
// is demanding. |
| 73 |
fullCapacityBite := float64(count-next) * (demand - prevAlloc) |
| 74 |
if fullCapacityBite > capacity { |
| 75 |
break |
| 76 |
} |
| 77 |
prevAlloc = demand |
| 78 |
alloc[idx] = demand |
| 79 |
capacity -= fullCapacityBite |
| 80 |
} |
| 81 |
for j := next; j < count; j++ { |
| 82 |
alloc[indices[j]] = prevAlloc + capacity/float64(count-next) |
| 83 |
} |
| 84 |
return alloc |
| 85 |
} |
| 86 |
|
| 87 |
func TestFairAlloc(t *testing.T) { |
| 88 |
if e, a := []float64{0, 0}, fairAlloc([]float64{0, 0}, 42); !reflect.DeepEqual(e, a) { |
| 89 |
t.Errorf("Expected %#+v, got #%+v", e, a) |
| 90 |
} |
| 91 |
if e, a := []float64{42, 0}, fairAlloc([]float64{47, 0}, 42); !reflect.DeepEqual(e, a) { |
| 92 |
t.Errorf("Expected %#+v, got #%+v", e, a) |
| 93 |
} |
| 94 |
if e, a := []float64{1, 41}, fairAlloc([]float64{1, 47}, 42); !reflect.DeepEqual(e, a) { |
| 95 |
t.Errorf("Expected %#+v, got #%+v", e, a) |
| 96 |
} |
| 97 |
if e, a := []float64{3, 5, 5, 1}, fairAlloc([]float64{3, 7, 9, 1}, 14); !reflect.DeepEqual(e, a) { |
| 98 |
t.Errorf("Expected %#+v, got #%+v", e, a) |
| 99 |
} |
| 100 |
if e, a := []float64{1, 9, 7, 3}, fairAlloc([]float64{1, 9, 7, 3}, 21); !reflect.DeepEqual(e, a) { |
| 101 |
t.Errorf("Expected %#+v, got #%+v", e, a) |
| 102 |
} |
| 103 |
} |
| 104 |
|
| 105 |
type uniformClient struct { |
| 106 |
hash uint64 |
| 107 |
nThreads int |
| 108 |
nCalls int |
| 109 |
// duration for a simulated synchronous call |
| 110 |
execDuration time.Duration |
| 111 |
// duration for simulated "other work". This can be negative, |
| 112 |
// causing a request to be launched a certain amount of time |
| 113 |
// before the previous one finishes. |
| 114 |
thinkDuration time.Duration |
| 115 |
// padDuration is additional time during which this request occupies its seats. |
| 116 |
// This comes at the end of execution, after the reply has been released toward |
| 117 |
// the client. |
| 118 |
// The evaluation code below does not take this into account. |
| 119 |
// In cases where `padDuration` makes a difference, |
| 120 |
// set the `expectedAverages` field of `uniformScenario`. |
| 121 |
padDuration time.Duration |
| 122 |
// When true indicates that only half the specified number of |
| 123 |
// threads should run during the first half of the evaluation |
| 124 |
// period |
| 125 |
split bool |
| 126 |
// initialSeats is the number of seats this request occupies in the first phase of execution |
| 127 |
initialSeats uint64 |
| 128 |
// finalSeats is the number occupied during the second phase of execution |
| 129 |
finalSeats uint64 |
| 130 |
} |
| 131 |
|
| 132 |
func newUniformClient(hash uint64, nThreads, nCalls int, execDuration, thinkDuration time.Duration) uniformClient { |
| 133 |
return uniformClient{ |
| 134 |
hash: hash, |
| 135 |
nThreads: nThreads, |
| 136 |
nCalls: nCalls, |
| 137 |
execDuration: execDuration, |
| 138 |
thinkDuration: thinkDuration, |
| 139 |
initialSeats: 1, |
| 140 |
finalSeats: 1, |
| 141 |
} |
| 142 |
} |
| 143 |
|
| 144 |
func (uc uniformClient) setSplit() uniformClient { |
| 145 |
uc.split = true |
| 146 |
return uc |
| 147 |
} |
| 148 |
|
| 149 |
func (uc uniformClient) setInitWidth(seats uint64) uniformClient { |
| 150 |
uc.initialSeats = seats |
| 151 |
return uc |
| 152 |
} |
| 153 |
|
| 154 |
func (uc uniformClient) pad(finalSeats int, duration time.Duration) uniformClient { |
| 155 |
uc.finalSeats = uint64(finalSeats) |
| 156 |
uc.padDuration = duration |
| 157 |
return uc |
| 158 |
} |
| 159 |
|
| 160 |
// uniformScenario describes a scenario based on the given set of uniform clients. |
| 161 |
// Each uniform client specifies a number of threads, each of which alternates between thinking |
| 162 |
// and making a synchronous request through the QueueSet. |
| 163 |
// The test measures how much concurrency each client got, on average, over |
| 164 |
// the initial evalDuration and tests to see whether they all got about the fair amount. |
| 165 |
// Each client needs to be demanding enough to use more than its fair share, |
| 166 |
// or overall care needs to be taken about timing so that scheduling details |
| 167 |
// do not cause any client to actually request a significantly smaller share |
| 168 |
// than it theoretically should. |
| 169 |
// expectFair indicate whether the QueueSet is expected to be |
| 170 |
// fair in the respective halves of a split scenario; |
| 171 |
// in a non-split scenario this is a singleton with one expectation. |
| 172 |
// expectAllRequests indicates whether all requests are expected to get dispatched. |
| 173 |
// expectedAverages, if provided, replaces the normal calculation of expected results. |
| 174 |
type uniformScenario struct { |
| 175 |
name string |
| 176 |
qs fq.QueueSet |
| 177 |
clients []uniformClient |
| 178 |
concurrencyLimit int |
| 179 |
evalDuration time.Duration |
| 180 |
expectedFair []bool |
| 181 |
expectedFairnessMargin []float64 |
| 182 |
expectAllRequests bool |
| 183 |
evalInqueueMetrics, evalExecutingMetrics bool |
| 184 |
rejectReason string |
| 185 |
clk *testeventclock.Fake |
| 186 |
counter counter.GoRoutineCounter |
| 187 |
expectedAverages []float64 |
| 188 |
expectedEpochAdvances int |
| 189 |
seatDemandIntegratorSubject fq.Integrator |
| 190 |
dontDump bool |
| 191 |
} |
| 192 |
|
| 193 |
func (us uniformScenario) exercise(t *testing.T) { |
| 194 |
uss := uniformScenarioState{ |
| 195 |
t: t, |
| 196 |
uniformScenario: us, |
| 197 |
startTime: us.clk.Now(), |
| 198 |
execSeatsIntegrators: make([]fq.Integrator, len(us.clients)), |
| 199 |
seatDemandIntegratorCheck: fq.NewNamedIntegrator(us.clk, us.name+"-seatDemandCheck"), |
| 200 |
executions: make([]int32, len(us.clients)), |
| 201 |
rejects: make([]int32, len(us.clients)), |
| 202 |
} |
| 203 |
for _, uc := range us.clients { |
| 204 |
uss.doSplit = uss.doSplit || uc.split |
| 205 |
} |
| 206 |
uss.exercise() |
| 207 |
} |
| 208 |
|
| 209 |
type uniformScenarioState struct { |
| 210 |
t *testing.T |
| 211 |
uniformScenario |
| 212 |
startTime time.Time |
| 213 |
doSplit bool |
| 214 |
execSeatsIntegrators []fq.Integrator |
| 215 |
seatDemandIntegratorCheck fq.Integrator |
| 216 |
failedCount uint64 |
| 217 |
expectedInqueueReqs, expectedInqueueSeats, expectedExecuting, expectedConcurrencyInUse string |
| 218 |
executions, rejects []int32 |
| 219 |
} |
| 220 |
|
| 221 |
func (uss *uniformScenarioState) exercise() { |
| 222 |
uss.t.Logf("%s: Start %s, doSplit=%v, clk=%p, grc=%p", uss.startTime.Format(nsTimeFmt), uss.name, uss.doSplit, uss.clk, uss.counter) |
| 223 |
if uss.evalInqueueMetrics || uss.evalExecutingMetrics { |
| 224 |
metrics.Reset() |
| 225 |
} |
| 226 |
for i, uc := range uss.clients { |
| 227 |
uss.execSeatsIntegrators[i] = fq.NewNamedIntegrator(uss.clk, fmt.Sprintf("%s client %d execSeats", uss.name, i)) |
| 228 |
fsName := fmt.Sprintf("client%d", i) |
| 229 |
uss.expectedInqueueReqs = uss.expectedInqueueReqs + fmt.Sprintf(` apiserver_flowcontrol_current_inqueue_requests{flow_schema=%q,priority_level=%q} 0%s`, fsName, uss.name, "\n") |
| 230 |
uss.expectedInqueueSeats = uss.expectedInqueueSeats + fmt.Sprintf(` apiserver_flowcontrol_current_inqueue_seats{flow_schema=%q,priority_level=%q} 0%s`, fsName, uss.name, "\n") |
| 231 |
for j := 0; j < uc.nThreads; j++ { |
| 232 |
ust := uniformScenarioThread{ |
| 233 |
uss: uss, |
| 234 |
i: i, |
| 235 |
j: j, |
| 236 |
nCalls: uc.nCalls, |
| 237 |
uc: uc, |
| 238 |
execSeatsIntegrator: uss.execSeatsIntegrators[i], |
| 239 |
fsName: fsName, |
| 240 |
} |
| 241 |
ust.start() |
| 242 |
} |
| 243 |
} |
| 244 |
if uss.doSplit { |
| 245 |
uss.evalTo(uss.startTime.Add(uss.evalDuration/2), false, uss.expectedFair[0], uss.expectedFairnessMargin[0]) |
| 246 |
} |
| 247 |
uss.evalTo(uss.startTime.Add(uss.evalDuration), true, uss.expectedFair[len(uss.expectedFair)-1], uss.expectedFairnessMargin[len(uss.expectedFairnessMargin)-1]) |
| 248 |
uss.clk.Run(nil) |
| 249 |
uss.finalReview() |
| 250 |
} |
| 251 |
|
| 252 |
type uniformScenarioThread struct { |
| 253 |
uss *uniformScenarioState |
| 254 |
i, j int |
| 255 |
nCalls int |
| 256 |
uc uniformClient |
| 257 |
execSeatsIntegrator fq.Integrator |
| 258 |
fsName string |
| 259 |
} |
| 260 |
|
| 261 |
func (ust *uniformScenarioThread) start() { |
| 262 |
initialDelay := time.Duration(90*ust.j + 20*ust.i) |
| 263 |
if ust.uc.split && ust.j >= ust.uc.nThreads/2 { |
| 264 |
initialDelay += ust.uss.evalDuration / 2 |
| 265 |
ust.nCalls = ust.nCalls / 2 |
| 266 |
} |
| 267 |
ust.uss.clk.EventAfterDuration(ust.genCallK(0), initialDelay) |
| 268 |
} |
| 269 |
|
| 270 |
// generates an EventFunc that does call k |
| 271 |
func (ust *uniformScenarioThread) genCallK(k int) func(time.Time) { |
| 272 |
return func(time.Time) { |
| 273 |
ust.callK(k) |
| 274 |
} |
| 275 |
} |
| 276 |
|
| 277 |
func (ust *uniformScenarioThread) callK(k int) { |
| 278 |
if k >= ust.nCalls { |
| 279 |
return |
| 280 |
} |
| 281 |
maxWidth := float64(uint64max(ust.uc.initialSeats, ust.uc.finalSeats)) |
| 282 |
ust.uss.seatDemandIntegratorCheck.Add(maxWidth) |
| 283 |
returnSeatDemand := func(time.Time) { ust.uss.seatDemandIntegratorCheck.Add(-maxWidth) } |
| 284 |
ctx := context.Background() |
| 285 |
username := fmt.Sprintf("%d:%d:%d", ust.i, ust.j, k) |
| 286 |
ctx = genericrequest.WithUser(ctx, &user.DefaultInfo{Name: username}) |
| 287 |
req, idle := ust.uss.qs.StartRequest(ctx, &fcrequest.WorkEstimate{InitialSeats: ust.uc.initialSeats, FinalSeats: ust.uc.finalSeats, AdditionalLatency: ust.uc.padDuration}, ust.uc.hash, "", ust.fsName, ust.uss.name, []int{ust.i, ust.j, k}, nil) |
| 288 |
ust.uss.t.Logf("%s: %d, %d, %d got req=%p, idle=%v", ust.uss.clk.Now().Format(nsTimeFmt), ust.i, ust.j, k, req, idle) |
| 289 |
if req == nil { |
| 290 |
atomic.AddUint64(&ust.uss.failedCount, 1) |
| 291 |
atomic.AddInt32(&ust.uss.rejects[ust.i], 1) |
| 292 |
returnSeatDemand(ust.uss.clk.Now()) |
| 293 |
return |
| 294 |
} |
| 295 |
if idle { |
| 296 |
ust.uss.t.Error("got request but QueueSet reported idle") |
| 297 |
} |
| 298 |
if (!ust.uss.dontDump) && k%100 == 0 { |
| 299 |
insistRequestFromUser(ust.uss.t, ust.uss.qs, username) |
| 300 |
} |
| 301 |
var executed bool |
| 302 |
var returnTime time.Time |
| 303 |
idle2 := req.Finish(func() { |
| 304 |
executed = true |
| 305 |
execStart := ust.uss.clk.Now() |
| 306 |
atomic.AddInt32(&ust.uss.executions[ust.i], 1) |
| 307 |
ust.execSeatsIntegrator.Add(float64(ust.uc.initialSeats)) |
| 308 |
ust.uss.t.Logf("%s: %d, %d, %d executing; width1=%d", execStart.Format(nsTimeFmt), ust.i, ust.j, k, ust.uc.initialSeats) |
| 309 |
ust.uss.clk.EventAfterDuration(ust.genCallK(k+1), ust.uc.execDuration+ust.uc.thinkDuration) |
| 310 |
ust.uss.clk.Sleep(ust.uc.execDuration) |
| 311 |
ust.execSeatsIntegrator.Add(-float64(ust.uc.initialSeats)) |
| 312 |
ust.uss.clk.EventAfterDuration(returnSeatDemand, ust.uc.padDuration) |
| 313 |
returnTime = ust.uss.clk.Now() |
| 314 |
}) |
| 315 |
now := ust.uss.clk.Now() |
| 316 |
ust.uss.t.Logf("%s: %d, %d, %d got executed=%v, idle2=%v", now.Format(nsTimeFmt), ust.i, ust.j, k, executed, idle2) |
| 317 |
if !executed { |
| 318 |
atomic.AddUint64(&ust.uss.failedCount, 1) |
| 319 |
atomic.AddInt32(&ust.uss.rejects[ust.i], 1) |
| 320 |
returnSeatDemand(ust.uss.clk.Now()) |
| 321 |
} else if now != returnTime { |
| 322 |
ust.uss.t.Errorf("%s: %d, %d, %d returnTime=%s", now.Format(nsTimeFmt), ust.i, ust.j, k, returnTime.Format(nsTimeFmt)) |
| 323 |
} |
| 324 |
} |
| 325 |
|
| 326 |
func insistRequestFromUser(t *testing.T, qs fq.QueueSet, username string) { |
| 327 |
qsd := qs.Dump(true) |
| 328 |
goodRequest := func(rd debug.RequestDump) bool { |
| 329 |
return rd.UserName == username |
| 330 |
} |
| 331 |
goodSliceOfRequests := SliceMapReduce(goodRequest, or) |
| 332 |
if goodSliceOfRequests(qsd.QueuelessExecutingRequests) { |
| 333 |
t.Logf("Found user %s among queueless requests", username) |
| 334 |
return |
| 335 |
} |
| 336 |
goodQueueDump := func(qd debug.QueueDump) bool { |
| 337 |
return goodSliceOfRequests(qd.Requests) || goodSliceOfRequests(qd.RequestsExecuting) |
| 338 |
} |
| 339 |
if SliceMapReduce(goodQueueDump, or)(qsd.Queues) { |
| 340 |
t.Logf("Found user %s among queued requests", username) |
| 341 |
return |
| 342 |
} |
| 343 |
t.Errorf("Failed to find request from user %s", username) |
| 344 |
} |
| 345 |
|
| 346 |
func (uss *uniformScenarioState) evalTo(lim time.Time, last, expectFair bool, margin float64) { |
| 347 |
uss.clk.Run(&lim) |
| 348 |
uss.clk.SetTime(lim) |
| 349 |
if uss.doSplit && !last { |
| 350 |
uss.t.Logf("%s: End of first half of scenario %q", uss.clk.Now().Format(nsTimeFmt), uss.name) |
| 351 |
} else { |
| 352 |
uss.t.Logf("%s: End of scenario %q", uss.clk.Now().Format(nsTimeFmt), uss.name) |
| 353 |
} |
| 354 |
demands := make([]float64, len(uss.clients)) |
| 355 |
averages := make([]float64, len(uss.clients)) |
| 356 |
for i, uc := range uss.clients { |
| 357 |
nThreads := uc.nThreads |
| 358 |
if uc.split && !last { |
| 359 |
nThreads = nThreads / 2 |
| 360 |
} |
| 361 |
sep := uc.thinkDuration |
| 362 |
demands[i] = float64(nThreads) * float64(uc.initialSeats) * float64(uc.execDuration) / float64(sep+uc.execDuration) |
| 363 |
averages[i] = uss.execSeatsIntegrators[i].Reset().Average |
| 364 |
} |
| 365 |
fairAverages := uss.expectedAverages |
| 366 |
if fairAverages == nil { |
| 367 |
fairAverages = fairAlloc(demands, float64(uss.concurrencyLimit)) |
| 368 |
} |
| 369 |
for i := range uss.clients { |
| 370 |
expectedAverage := fairAverages[i] |
| 371 |
var gotFair bool |
| 372 |
if expectedAverage > 0 { |
| 373 |
relDiff := (averages[i] - expectedAverage) / expectedAverage |
| 374 |
gotFair = math.Abs(relDiff) <= margin |
| 375 |
} else { |
| 376 |
gotFair = math.Abs(averages[i]) <= margin |
| 377 |
} |
| 378 |
|
| 379 |
if gotFair != expectFair { |
| 380 |
uss.t.Errorf("%s client %d last=%v expectFair=%v margin=%v got an Average of %v but the expected average was %v", uss.name, i, last, expectFair, margin, averages[i], expectedAverage) |
| 381 |
} else { |
| 382 |
uss.t.Logf("%s client %d last=%v expectFair=%v margin=%v got an Average of %v and the expected average was %v", uss.name, i, last, expectFair, margin, averages[i], expectedAverage) |
| 383 |
} |
| 384 |
} |
| 385 |
if uss.seatDemandIntegratorSubject != nil { |
| 386 |
checkResults := uss.seatDemandIntegratorCheck.GetResults() |
| 387 |
subjectResults := uss.seatDemandIntegratorSubject.GetResults() |
| 388 |
if float64close(subjectResults.Duration, checkResults.Duration) { |
| 389 |
uss.t.Logf("%s last=%v got duration of %v and expected %v", uss.name, last, subjectResults.Duration, checkResults.Duration) |
| 390 |
} else { |
| 391 |
uss.t.Errorf("%s last=%v got duration of %v but expected %v", uss.name, last, subjectResults.Duration, checkResults.Duration) |
| 392 |
} |
| 393 |
if got, expected := float64NaNTo0(subjectResults.Average), float64NaNTo0(checkResults.Average); float64close(got, expected) { |
| 394 |
uss.t.Logf("%s last=%v got SeatDemand average of %v and expected %v", uss.name, last, got, expected) |
| 395 |
} else { |
| 396 |
uss.t.Errorf("%s last=%v got SeatDemand average of %v but expected %v", uss.name, last, got, expected) |
| 397 |
} |
| 398 |
if got, expected := float64NaNTo0(subjectResults.Deviation), float64NaNTo0(checkResults.Deviation); float64close(got, expected) { |
| 399 |
uss.t.Logf("%s last=%v got SeatDemand standard deviation of %v and expected %v", uss.name, last, got, expected) |
| 400 |
} else { |
| 401 |
uss.t.Errorf("%s last=%v got SeatDemand standard deviation of %v but expected %v", uss.name, last, got, expected) |
| 402 |
} |
| 403 |
} |
| 404 |
} |
| 405 |
|
| 406 |
func (uss *uniformScenarioState) finalReview() { |
| 407 |
if uss.expectAllRequests && uss.failedCount > 0 { |
| 408 |
uss.t.Errorf("Expected all requests to be successful but got %v failed requests", uss.failedCount) |
| 409 |
} else if !uss.expectAllRequests && uss.failedCount == 0 { |
| 410 |
uss.t.Errorf("Expected failed requests but all requests succeeded") |
| 411 |
} |
| 412 |
if uss.evalInqueueMetrics { |
| 413 |
e := ` |
| 414 |
# HELP apiserver_flowcontrol_current_inqueue_requests [BETA] Number of requests currently pending in queues of the API Priority and Fairness subsystem |
| 415 |
# TYPE apiserver_flowcontrol_current_inqueue_requests gauge |
| 416 |
` + uss.expectedInqueueReqs |
| 417 |
err := metrics.GatherAndCompare(e, "apiserver_flowcontrol_current_inqueue_requests") |
| 418 |
if err != nil { |
| 419 |
uss.t.Error(err) |
| 420 |
} else { |
| 421 |
uss.t.Log("Success with" + e) |
| 422 |
} |
| 423 |
|
| 424 |
e = ` |
| 425 |
# HELP apiserver_flowcontrol_current_inqueue_seats [ALPHA] Number of seats currently pending in queues of the API Priority and Fairness subsystem |
| 426 |
# TYPE apiserver_flowcontrol_current_inqueue_seats gauge |
| 427 |
` + uss.expectedInqueueSeats |
| 428 |
err = metrics.GatherAndCompare(e, "apiserver_flowcontrol_current_inqueue_seats") |
| 429 |
if err != nil { |
| 430 |
uss.t.Error(err) |
| 431 |
} else { |
| 432 |
uss.t.Log("Success with" + e) |
| 433 |
} |
| 434 |
} |
| 435 |
expectedRejects := "" |
| 436 |
for i := range uss.clients { |
| 437 |
fsName := fmt.Sprintf("client%d", i) |
| 438 |
if atomic.LoadInt32(&uss.executions[i]) > 0 { |
| 439 |
uss.expectedExecuting = uss.expectedExecuting + fmt.Sprintf(` apiserver_flowcontrol_current_executing_requests{flow_schema=%q,priority_level=%q} 0%s`, fsName, uss.name, "\n") |
| 440 |
uss.expectedConcurrencyInUse = uss.expectedConcurrencyInUse + fmt.Sprintf(` apiserver_flowcontrol_request_concurrency_in_use{flow_schema=%q,priority_level=%q} 0%s`, fsName, uss.name, "\n") |
| 441 |
} |
| 442 |
if atomic.LoadInt32(&uss.rejects[i]) > 0 { |
| 443 |
expectedRejects = expectedRejects + fmt.Sprintf(` apiserver_flowcontrol_rejected_requests_total{flow_schema=%q,priority_level=%q,reason=%q} %d%s`, fsName, uss.name, uss.rejectReason, uss.rejects[i], "\n") |
| 444 |
} |
| 445 |
} |
| 446 |
if uss.evalExecutingMetrics && len(uss.expectedExecuting) > 0 { |
| 447 |
e := ` |
| 448 |
# HELP apiserver_flowcontrol_current_executing_requests [BETA] Number of requests in initial (for a WATCH) or any (for a non-WATCH) execution stage in the API Priority and Fairness subsystem |
| 449 |
# TYPE apiserver_flowcontrol_current_executing_requests gauge |
| 450 |
` + uss.expectedExecuting |
| 451 |
err := metrics.GatherAndCompare(e, "apiserver_flowcontrol_current_executing_requests") |
| 452 |
if err != nil { |
| 453 |
uss.t.Error(err) |
| 454 |
} else { |
| 455 |
uss.t.Log("Success with" + e) |
| 456 |
} |
| 457 |
} |
| 458 |
if uss.evalExecutingMetrics && len(uss.expectedConcurrencyInUse) > 0 { |
| 459 |
e := ` |
| 460 |
# HELP apiserver_flowcontrol_request_concurrency_in_use [ALPHA] Concurrency (number of seats) occupied by the currently executing (initial stage for a WATCH, any stage otherwise) requests in the API Priority and Fairness subsystem |
| 461 |
# TYPE apiserver_flowcontrol_request_concurrency_in_use gauge |
| 462 |
` + uss.expectedConcurrencyInUse |
| 463 |
err := metrics.GatherAndCompare(e, "apiserver_flowcontrol_request_concurrency_in_use") |
| 464 |
if err != nil { |
| 465 |
uss.t.Error(err) |
| 466 |
} else { |
| 467 |
uss.t.Log("Success with" + e) |
| 468 |
} |
| 469 |
} |
| 470 |
if uss.evalExecutingMetrics && len(expectedRejects) > 0 { |
| 471 |
e := ` |
| 472 |
# HELP apiserver_flowcontrol_rejected_requests_total [BETA] Number of requests rejected by API Priority and Fairness subsystem |
| 473 |
# TYPE apiserver_flowcontrol_rejected_requests_total counter |
| 474 |
` + expectedRejects |
| 475 |
err := metrics.GatherAndCompare(e, "apiserver_flowcontrol_rejected_requests_total") |
| 476 |
if err != nil { |
| 477 |
uss.t.Error(err) |
| 478 |
} else { |
| 479 |
uss.t.Log("Success with" + e) |
| 480 |
} |
| 481 |
} |
| 482 |
e := "" |
| 483 |
if uss.expectedEpochAdvances > 0 { |
| 484 |
e = fmt.Sprintf(` # HELP apiserver_flowcontrol_epoch_advance_total [ALPHA] Number of times the queueset's progress meter jumped backward |
| 485 |
# TYPE apiserver_flowcontrol_epoch_advance_total counter |
| 486 |
apiserver_flowcontrol_epoch_advance_total{priority_level=%q,success=%q} %d%s`, uss.name, "true", uss.expectedEpochAdvances, "\n") |
| 487 |
} |
| 488 |
err := metrics.GatherAndCompare(e, "apiserver_flowcontrol_epoch_advance_total") |
| 489 |
if err != nil { |
| 490 |
uss.t.Error(err) |
| 491 |
} else { |
| 492 |
uss.t.Logf("Success with apiserver_flowcontrol_epoch_advance_total = %d", uss.expectedEpochAdvances) |
| 493 |
} |
| 494 |
} |
| 495 |
|
| 496 |
func TestMain(m *testing.M) { |
| 497 |
klog.InitFlags(nil) |
| 498 |
os.Exit(m.Run()) |
| 499 |
} |
| 500 |
|
| 501 |
// TestNoRestraint tests whether the no-restraint factory gives every client what it asks for |
| 502 |
// even though that is unfair. |
| 503 |
// Expects fairness when there is no competition, unfairness when there is competition. |
| 504 |
func TestNoRestraint(t *testing.T) { |
| 505 |
metrics.Register() |
| 506 |
testCases := []struct { |
| 507 |
concurrency int |
| 508 |
margin float64 |
| 509 |
fair bool |
| 510 |
name string |
| 511 |
}{ |
| 512 |
{concurrency: 10, margin: 0.001, fair: true, name: "no-competition"}, |
| 513 |
{concurrency: 2, margin: 0.25, fair: false, name: "with-competition"}, |
| 514 |
} |
| 515 |
for _, testCase := range testCases { |
| 516 |
t.Run(testCase.name, func(t *testing.T) { |
| 517 |
now := time.Now() |
| 518 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 519 |
nrc, err := test.NewNoRestraintFactory().BeginConstruction(fq.QueuingConfig{}, newGaugePair(clk), newExecSeatsGauge(clk), fq.NewNamedIntegrator(clk, "TestNoRestraint")) |
| 520 |
if err != nil { |
| 521 |
t.Fatal(err) |
| 522 |
} |
| 523 |
nr := nrc.Complete(fq.DispatchingConfig{}) |
| 524 |
uniformScenario{name: "NoRestraint/" + testCase.name, |
| 525 |
qs: nr, |
| 526 |
clients: []uniformClient{ |
| 527 |
newUniformClient(1001001001, 5, 15, time.Second, time.Second), |
| 528 |
newUniformClient(2002002002, 2, 15, time.Second, time.Second/2), |
| 529 |
}, |
| 530 |
concurrencyLimit: testCase.concurrency, |
| 531 |
evalDuration: time.Second * 18, |
| 532 |
expectedFair: []bool{testCase.fair}, |
| 533 |
expectedFairnessMargin: []float64{testCase.margin}, |
| 534 |
expectAllRequests: true, |
| 535 |
clk: clk, |
| 536 |
counter: counter, |
| 537 |
dontDump: true, |
| 538 |
}.exercise(t) |
| 539 |
}) |
| 540 |
} |
| 541 |
} |
| 542 |
|
| 543 |
func TestBaseline(t *testing.T) { |
| 544 |
metrics.Register() |
| 545 |
now := time.Now() |
| 546 |
|
| 547 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 548 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 549 |
qCfg := fq.QueuingConfig{ |
| 550 |
Name: "TestBaseline", |
| 551 |
DesiredNumQueues: 9, |
| 552 |
QueueLengthLimit: 8, |
| 553 |
HandSize: 3, |
| 554 |
} |
| 555 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, "seatDemandSubject") |
| 556 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 557 |
if err != nil { |
| 558 |
t.Fatal(err) |
| 559 |
} |
| 560 |
qs := qsComplete(qsc, 1) |
| 561 |
|
| 562 |
uniformScenario{name: qCfg.Name, |
| 563 |
qs: qs, |
| 564 |
clients: []uniformClient{ |
| 565 |
newUniformClient(1001001001, 1, 21, time.Second, 0), |
| 566 |
}, |
| 567 |
concurrencyLimit: 1, |
| 568 |
evalDuration: time.Second * 20, |
| 569 |
expectedFair: []bool{true}, |
| 570 |
expectedFairnessMargin: []float64{0}, |
| 571 |
expectAllRequests: true, |
| 572 |
evalInqueueMetrics: true, |
| 573 |
evalExecutingMetrics: true, |
| 574 |
clk: clk, |
| 575 |
counter: counter, |
| 576 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 577 |
}.exercise(t) |
| 578 |
} |
| 579 |
|
| 580 |
func TestExampt(t *testing.T) { |
| 581 |
metrics.Register() |
| 582 |
for concurrencyLimit := 0; concurrencyLimit <= 2; concurrencyLimit += 2 { |
| 583 |
t.Run(fmt.Sprintf("concurrency=%d", concurrencyLimit), func(t *testing.T) { |
| 584 |
now := time.Now() |
| 585 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 586 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 587 |
qCfg := fq.QueuingConfig{ |
| 588 |
Name: "TestBaseline", |
| 589 |
DesiredNumQueues: -1, |
| 590 |
QueueLengthLimit: 2, |
| 591 |
HandSize: 3, |
| 592 |
} |
| 593 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, "seatDemandSubject") |
| 594 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 595 |
if err != nil { |
| 596 |
t.Fatal(err) |
| 597 |
} |
| 598 |
qs := qsComplete(qsc, concurrencyLimit) |
| 599 |
uniformScenario{name: qCfg.Name, |
| 600 |
qs: qs, |
| 601 |
clients: []uniformClient{ |
| 602 |
newUniformClient(1001001001, 5, 20, time.Second, time.Second).setInitWidth(3), |
| 603 |
}, |
| 604 |
concurrencyLimit: 1, |
| 605 |
evalDuration: time.Second * 40, |
| 606 |
expectedFair: []bool{true}, // "fair" is a bit odd-sounding here, but it "expectFair" here means expect `expectedAverages` |
| 607 |
expectedAverages: []float64{7.5}, |
| 608 |
expectedFairnessMargin: []float64{0.00000001}, |
| 609 |
expectAllRequests: true, |
| 610 |
evalInqueueMetrics: false, |
| 611 |
evalExecutingMetrics: true, |
| 612 |
clk: clk, |
| 613 |
counter: counter, |
| 614 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 615 |
}.exercise(t) |
| 616 |
}) |
| 617 |
} |
| 618 |
} |
| 619 |
|
| 620 |
func TestSeparations(t *testing.T) { |
| 621 |
flts := func(avgs ...float64) []float64 { return avgs } |
| 622 |
for _, seps := range []struct { |
| 623 |
think, pad time.Duration |
| 624 |
finalSeats, conc, nClients int |
| 625 |
exp []float64 // override expected results |
| 626 |
}{ |
| 627 |
{think: time.Second, pad: 0, finalSeats: 1, conc: 1, nClients: 1}, |
| 628 |
{think: time.Second, pad: 0, finalSeats: 1, conc: 2, nClients: 1}, |
| 629 |
{think: time.Second, pad: 0, finalSeats: 2, conc: 2, nClients: 1}, |
| 630 |
{think: time.Second, pad: 0, finalSeats: 1, conc: 1, nClients: 2}, |
| 631 |
{think: time.Second, pad: 0, finalSeats: 1, conc: 2, nClients: 2}, |
| 632 |
{think: time.Second, pad: 0, finalSeats: 2, conc: 2, nClients: 2}, |
| 633 |
{think: 0, pad: time.Second, finalSeats: 1, conc: 1, nClients: 1, exp: flts(0.5)}, |
| 634 |
{think: 0, pad: time.Second, finalSeats: 1, conc: 2, nClients: 1}, |
| 635 |
{think: 0, pad: time.Second, finalSeats: 2, conc: 2, nClients: 1, exp: flts(0.5)}, |
| 636 |
{think: 0, pad: time.Second, finalSeats: 1, conc: 1, nClients: 2, exp: flts(0.25, 0.25)}, |
| 637 |
{think: 0, pad: time.Second, finalSeats: 1, conc: 2, nClients: 2, exp: flts(0.5, 0.5)}, |
| 638 |
{think: 0, pad: time.Second, finalSeats: 2, conc: 2, nClients: 2, exp: flts(0.25, 0.25)}, |
| 639 |
{think: time.Second, pad: time.Second / 2, finalSeats: 1, conc: 1, nClients: 1}, |
| 640 |
{think: time.Second, pad: time.Second / 2, finalSeats: 1, conc: 2, nClients: 1}, |
| 641 |
{think: time.Second, pad: time.Second / 2, finalSeats: 2, conc: 2, nClients: 1}, |
| 642 |
{think: time.Second, pad: time.Second / 2, finalSeats: 1, conc: 1, nClients: 2, exp: flts(1.0/3, 1.0/3)}, |
| 643 |
{think: time.Second, pad: time.Second / 2, finalSeats: 1, conc: 2, nClients: 2}, |
| 644 |
{think: time.Second, pad: time.Second / 2, finalSeats: 2, conc: 2, nClients: 2, exp: flts(1.0/3, 1.0/3)}, |
| 645 |
{think: time.Second / 2, pad: time.Second, finalSeats: 1, conc: 1, nClients: 1, exp: flts(0.5)}, |
| 646 |
{think: time.Second / 2, pad: time.Second, finalSeats: 1, conc: 2, nClients: 1}, |
| 647 |
{think: time.Second / 2, pad: time.Second, finalSeats: 2, conc: 2, nClients: 1, exp: flts(0.5)}, |
| 648 |
{think: time.Second / 2, pad: time.Second, finalSeats: 1, conc: 1, nClients: 2, exp: flts(0.25, 0.25)}, |
| 649 |
{think: time.Second / 2, pad: time.Second, finalSeats: 1, conc: 2, nClients: 2, exp: flts(0.5, 0.5)}, |
| 650 |
{think: time.Second / 2, pad: time.Second, finalSeats: 2, conc: 2, nClients: 2, exp: flts(0.25, 0.25)}, |
| 651 |
} { |
| 652 |
caseName := fmt.Sprintf("think=%v,finalSeats=%d,pad=%v,nClients=%d,conc=%d", seps.think, seps.finalSeats, seps.pad, seps.nClients, seps.conc) |
| 653 |
t.Run(caseName, func(t *testing.T) { |
| 654 |
metrics.Register() |
| 655 |
now := time.Now() |
| 656 |
|
| 657 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 658 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 659 |
qCfg := fq.QueuingConfig{ |
| 660 |
Name: "TestSeparations/" + caseName, |
| 661 |
DesiredNumQueues: 9, |
| 662 |
QueueLengthLimit: 8, |
| 663 |
HandSize: 3, |
| 664 |
} |
| 665 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, caseName+" seatDemandSubject") |
| 666 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 667 |
if err != nil { |
| 668 |
t.Fatal(err) |
| 669 |
} |
| 670 |
qs := qsComplete(qsc, seps.conc) |
| 671 |
uniformScenario{name: qCfg.Name, |
| 672 |
qs: qs, |
| 673 |
clients: []uniformClient{ |
| 674 |
newUniformClient(1001001001, 1, 25, time.Second, seps.think).pad(seps.finalSeats, seps.pad), |
| 675 |
newUniformClient(2002002002, 1, 25, time.Second, seps.think).pad(seps.finalSeats, seps.pad), |
| 676 |
}[:seps.nClients], |
| 677 |
concurrencyLimit: seps.conc, |
| 678 |
evalDuration: time.Second * 24, // multiple of every period involved, so that margin can be 0 below |
| 679 |
expectedFair: []bool{true}, |
| 680 |
expectedFairnessMargin: []float64{0}, |
| 681 |
expectAllRequests: true, |
| 682 |
evalInqueueMetrics: true, |
| 683 |
evalExecutingMetrics: true, |
| 684 |
clk: clk, |
| 685 |
counter: counter, |
| 686 |
expectedAverages: seps.exp, |
| 687 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 688 |
}.exercise(t) |
| 689 |
}) |
| 690 |
} |
| 691 |
} |
| 692 |
|
| 693 |
func TestUniformFlowsHandSize1(t *testing.T) { |
| 694 |
metrics.Register() |
| 695 |
now := time.Now() |
| 696 |
|
| 697 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 698 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 699 |
qCfg := fq.QueuingConfig{ |
| 700 |
Name: "TestUniformFlowsHandSize1", |
| 701 |
DesiredNumQueues: 9, |
| 702 |
QueueLengthLimit: 8, |
| 703 |
HandSize: 1, |
| 704 |
} |
| 705 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, "seatDemandSubject") |
| 706 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 707 |
if err != nil { |
| 708 |
t.Fatal(err) |
| 709 |
} |
| 710 |
qs := qsComplete(qsc, 4) |
| 711 |
|
| 712 |
uniformScenario{name: qCfg.Name, |
| 713 |
qs: qs, |
| 714 |
clients: []uniformClient{ |
| 715 |
newUniformClient(1001001001, 8, 20, time.Second, time.Second-1), |
| 716 |
newUniformClient(2002002002, 8, 20, time.Second, time.Second-1), |
| 717 |
}, |
| 718 |
concurrencyLimit: 4, |
| 719 |
evalDuration: time.Second * 50, |
| 720 |
expectedFair: []bool{true}, |
| 721 |
expectedFairnessMargin: []float64{0.01}, |
| 722 |
expectAllRequests: true, |
| 723 |
evalInqueueMetrics: true, |
| 724 |
evalExecutingMetrics: true, |
| 725 |
clk: clk, |
| 726 |
counter: counter, |
| 727 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 728 |
}.exercise(t) |
| 729 |
} |
| 730 |
|
| 731 |
func TestUniformFlowsHandSize3(t *testing.T) { |
| 732 |
metrics.Register() |
| 733 |
now := time.Now() |
| 734 |
|
| 735 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 736 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 737 |
qCfg := fq.QueuingConfig{ |
| 738 |
Name: "TestUniformFlowsHandSize3", |
| 739 |
DesiredNumQueues: 8, |
| 740 |
QueueLengthLimit: 16, |
| 741 |
HandSize: 3, |
| 742 |
} |
| 743 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 744 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 745 |
if err != nil { |
| 746 |
t.Fatal(err) |
| 747 |
} |
| 748 |
qs := qsComplete(qsc, 4) |
| 749 |
uniformScenario{name: qCfg.Name, |
| 750 |
qs: qs, |
| 751 |
clients: []uniformClient{ |
| 752 |
newUniformClient(400900100100, 8, 30, time.Second, time.Second-1), |
| 753 |
newUniformClient(300900200200, 8, 30, time.Second, time.Second-1), |
| 754 |
}, |
| 755 |
concurrencyLimit: 4, |
| 756 |
evalDuration: time.Second * 60, |
| 757 |
expectedFair: []bool{true}, |
| 758 |
expectedFairnessMargin: []float64{0.03}, |
| 759 |
expectAllRequests: true, |
| 760 |
evalInqueueMetrics: true, |
| 761 |
evalExecutingMetrics: true, |
| 762 |
clk: clk, |
| 763 |
counter: counter, |
| 764 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 765 |
}.exercise(t) |
| 766 |
} |
| 767 |
|
| 768 |
func TestDifferentFlowsExpectEqual(t *testing.T) { |
| 769 |
metrics.Register() |
| 770 |
now := time.Now() |
| 771 |
|
| 772 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 773 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 774 |
qCfg := fq.QueuingConfig{ |
| 775 |
Name: "DiffFlowsExpectEqual", |
| 776 |
DesiredNumQueues: 9, |
| 777 |
QueueLengthLimit: 8, |
| 778 |
HandSize: 1, |
| 779 |
} |
| 780 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 781 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 782 |
if err != nil { |
| 783 |
t.Fatal(err) |
| 784 |
} |
| 785 |
qs := qsComplete(qsc, 4) |
| 786 |
|
| 787 |
uniformScenario{name: qCfg.Name, |
| 788 |
qs: qs, |
| 789 |
clients: []uniformClient{ |
| 790 |
newUniformClient(1001001001, 8, 20, time.Second, time.Second), |
| 791 |
newUniformClient(2002002002, 7, 30, time.Second, time.Second/2), |
| 792 |
}, |
| 793 |
concurrencyLimit: 4, |
| 794 |
evalDuration: time.Second * 40, |
| 795 |
expectedFair: []bool{true}, |
| 796 |
expectedFairnessMargin: []float64{0.01}, |
| 797 |
expectAllRequests: true, |
| 798 |
evalInqueueMetrics: true, |
| 799 |
evalExecutingMetrics: true, |
| 800 |
clk: clk, |
| 801 |
counter: counter, |
| 802 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 803 |
}.exercise(t) |
| 804 |
} |
| 805 |
|
| 806 |
// TestSeatSecondsRollover checks that there is not a problem with SeatSeconds overflow. |
| 807 |
func TestSeatSecondsRollover(t *testing.T) { |
| 808 |
metrics.Register() |
| 809 |
now := time.Now() |
| 810 |
|
| 811 |
const Quarter = 91 * 24 * time.Hour |
| 812 |
|
| 813 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 814 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 815 |
qCfg := fq.QueuingConfig{ |
| 816 |
Name: "TestSeatSecondsRollover", |
| 817 |
DesiredNumQueues: 9, |
| 818 |
QueueLengthLimit: 8, |
| 819 |
HandSize: 1, |
| 820 |
} |
| 821 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 822 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 823 |
if err != nil { |
| 824 |
t.Fatal(err) |
| 825 |
} |
| 826 |
qs := qsComplete(qsc, 2000) |
| 827 |
|
| 828 |
uniformScenario{name: qCfg.Name, |
| 829 |
qs: qs, |
| 830 |
clients: []uniformClient{ |
| 831 |
newUniformClient(1001001001, 8, 20, Quarter, Quarter).setInitWidth(500), |
| 832 |
newUniformClient(2002002002, 7, 30, Quarter, Quarter/2).setInitWidth(500), |
| 833 |
}, |
| 834 |
concurrencyLimit: 2000, |
| 835 |
evalDuration: Quarter * 40, |
| 836 |
expectedFair: []bool{true}, |
| 837 |
expectedFairnessMargin: []float64{0.01}, |
| 838 |
expectAllRequests: true, |
| 839 |
evalInqueueMetrics: true, |
| 840 |
evalExecutingMetrics: true, |
| 841 |
clk: clk, |
| 842 |
counter: counter, |
| 843 |
expectedEpochAdvances: 8, |
| 844 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 845 |
}.exercise(t) |
| 846 |
} |
| 847 |
|
| 848 |
func TestDifferentFlowsExpectUnequal(t *testing.T) { |
| 849 |
metrics.Register() |
| 850 |
now := time.Now() |
| 851 |
|
| 852 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 853 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 854 |
qCfg := fq.QueuingConfig{ |
| 855 |
Name: "DiffFlowsExpectUnequal", |
| 856 |
DesiredNumQueues: 9, |
| 857 |
QueueLengthLimit: 6, |
| 858 |
HandSize: 1, |
| 859 |
} |
| 860 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 861 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 862 |
if err != nil { |
| 863 |
t.Fatal(err) |
| 864 |
} |
| 865 |
qs := qsComplete(qsc, 3) |
| 866 |
|
| 867 |
uniformScenario{name: qCfg.Name, |
| 868 |
qs: qs, |
| 869 |
clients: []uniformClient{ |
| 870 |
newUniformClient(1001001001, 4, 20, time.Second, time.Second-1), |
| 871 |
newUniformClient(2002002002, 2, 20, time.Second, time.Second-1), |
| 872 |
}, |
| 873 |
concurrencyLimit: 3, |
| 874 |
evalDuration: time.Second * 20, |
| 875 |
expectedFair: []bool{true}, |
| 876 |
expectedFairnessMargin: []float64{0.01}, |
| 877 |
expectAllRequests: true, |
| 878 |
evalInqueueMetrics: true, |
| 879 |
evalExecutingMetrics: true, |
| 880 |
clk: clk, |
| 881 |
counter: counter, |
| 882 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 883 |
}.exercise(t) |
| 884 |
} |
| 885 |
|
| 886 |
func TestDifferentWidths(t *testing.T) { |
| 887 |
metrics.Register() |
| 888 |
now := time.Now() |
| 889 |
|
| 890 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 891 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 892 |
qCfg := fq.QueuingConfig{ |
| 893 |
Name: "TestDifferentWidths", |
| 894 |
DesiredNumQueues: 64, |
| 895 |
QueueLengthLimit: 13, |
| 896 |
HandSize: 7, |
| 897 |
} |
| 898 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 899 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 900 |
if err != nil { |
| 901 |
t.Fatal(err) |
| 902 |
} |
| 903 |
qs := qsComplete(qsc, 6) |
| 904 |
uniformScenario{name: qCfg.Name, |
| 905 |
qs: qs, |
| 906 |
clients: []uniformClient{ |
| 907 |
newUniformClient(10010010010010, 13, 10, time.Second, time.Second-1), |
| 908 |
newUniformClient(20020020020020, 7, 10, time.Second, time.Second-1).setInitWidth(2), |
| 909 |
}, |
| 910 |
concurrencyLimit: 6, |
| 911 |
evalDuration: time.Second * 20, |
| 912 |
expectedFair: []bool{true}, |
| 913 |
expectedFairnessMargin: []float64{0.155}, |
| 914 |
expectAllRequests: true, |
| 915 |
evalInqueueMetrics: true, |
| 916 |
evalExecutingMetrics: true, |
| 917 |
clk: clk, |
| 918 |
counter: counter, |
| 919 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 920 |
}.exercise(t) |
| 921 |
} |
| 922 |
|
| 923 |
func TestTooWide(t *testing.T) { |
| 924 |
metrics.Register() |
| 925 |
now := time.Now() |
| 926 |
|
| 927 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 928 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 929 |
qCfg := fq.QueuingConfig{ |
| 930 |
Name: "TestTooWide", |
| 931 |
DesiredNumQueues: 64, |
| 932 |
QueueLengthLimit: 35, |
| 933 |
HandSize: 7, |
| 934 |
} |
| 935 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 936 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 937 |
if err != nil { |
| 938 |
t.Fatal(err) |
| 939 |
} |
| 940 |
qs := qsComplete(qsc, 6) |
| 941 |
uniformScenario{name: qCfg.Name, |
| 942 |
qs: qs, |
| 943 |
clients: []uniformClient{ |
| 944 |
newUniformClient(40040040040040, 15, 21, time.Second, time.Second-1).setInitWidth(2), |
| 945 |
newUniformClient(50050050050050, 15, 21, time.Second, time.Second-1).setInitWidth(2), |
| 946 |
newUniformClient(60060060060060, 15, 21, time.Second, time.Second-1).setInitWidth(2), |
| 947 |
newUniformClient(70070070070070, 15, 21, time.Second, time.Second-1).setInitWidth(2), |
| 948 |
newUniformClient(90090090090090, 15, 21, time.Second, time.Second-1).setInitWidth(7), |
| 949 |
}, |
| 950 |
concurrencyLimit: 6, |
| 951 |
evalDuration: time.Second * 225, |
| 952 |
expectedFair: []bool{true}, |
| 953 |
expectedFairnessMargin: []float64{0.33}, |
| 954 |
expectAllRequests: true, |
| 955 |
evalInqueueMetrics: true, |
| 956 |
evalExecutingMetrics: true, |
| 957 |
clk: clk, |
| 958 |
counter: counter, |
| 959 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 960 |
}.exercise(t) |
| 961 |
} |
| 962 |
|
| 963 |
// TestWindup exercises a scenario with the windup problem. |
| 964 |
// That is, a flow that can not use all the seats that it is allocated |
| 965 |
// for a while. During that time, the queues that serve that flow |
| 966 |
// advance their `virtualStart` (that is, R(next dispatch in virtual world)) |
| 967 |
// more slowly than the other queues (which are using more seats than they |
| 968 |
// are allocated). The implementation has a hack that addresses part of |
| 969 |
// this imbalance but not all of it. In this test, flow 1 can not use all |
| 970 |
// of its allocation during the first half, and *can* (and does) use all of |
| 971 |
// its allocation and more during the second half. |
| 972 |
// Thus we expect the fair (not equal) result |
| 973 |
// in the first half and an unfair result in the second half. |
| 974 |
// This func has two test cases, bounding the amount of unfairness |
| 975 |
// in the second half. |
| 976 |
func TestWindup(t *testing.T) { |
| 977 |
metrics.Register() |
| 978 |
testCases := []struct { |
| 979 |
margin2 float64 |
| 980 |
expectFair2 bool |
| 981 |
name string |
| 982 |
}{ |
| 983 |
{margin2: 0.26, expectFair2: true, name: "upper-bound"}, |
| 984 |
{margin2: 0.1, expectFair2: false, name: "lower-bound"}, |
| 985 |
} |
| 986 |
for _, testCase := range testCases { |
| 987 |
t.Run(testCase.name, func(t *testing.T) { |
| 988 |
now := time.Now() |
| 989 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 990 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 991 |
qCfg := fq.QueuingConfig{ |
| 992 |
Name: "TestWindup/" + testCase.name, |
| 993 |
DesiredNumQueues: 9, |
| 994 |
QueueLengthLimit: 6, |
| 995 |
HandSize: 1, |
| 996 |
} |
| 997 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 998 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 999 |
if err != nil { |
| 1000 |
t.Fatal(err) |
| 1001 |
} |
| 1002 |
qs := qsComplete(qsc, 3) |
| 1003 |
|
| 1004 |
uniformScenario{name: qCfg.Name, qs: qs, |
| 1005 |
clients: []uniformClient{ |
| 1006 |
newUniformClient(1001001001, 2, 40, time.Second, -1), |
| 1007 |
newUniformClient(2002002002, 2, 40, time.Second, -1).setSplit(), |
| 1008 |
}, |
| 1009 |
concurrencyLimit: 3, |
| 1010 |
evalDuration: time.Second * 40, |
| 1011 |
expectedFair: []bool{true, testCase.expectFair2}, |
| 1012 |
expectedFairnessMargin: []float64{0.01, testCase.margin2}, |
| 1013 |
expectAllRequests: true, |
| 1014 |
evalInqueueMetrics: true, |
| 1015 |
evalExecutingMetrics: true, |
| 1016 |
clk: clk, |
| 1017 |
counter: counter, |
| 1018 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 1019 |
}.exercise(t) |
| 1020 |
}) |
| 1021 |
} |
| 1022 |
} |
| 1023 |
|
| 1024 |
func TestDifferentFlowsWithoutQueuing(t *testing.T) { |
| 1025 |
metrics.Register() |
| 1026 |
now := time.Now() |
| 1027 |
|
| 1028 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 1029 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 1030 |
qCfg := fq.QueuingConfig{ |
| 1031 |
Name: "TestDifferentFlowsWithoutQueuing", |
| 1032 |
DesiredNumQueues: 0, |
| 1033 |
} |
| 1034 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, "seatDemandSubject") |
| 1035 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 1036 |
if err != nil { |
| 1037 |
t.Fatal(err) |
| 1038 |
} |
| 1039 |
qs := qsComplete(qsc, 4) |
| 1040 |
|
| 1041 |
uniformScenario{name: qCfg.Name, |
| 1042 |
qs: qs, |
| 1043 |
clients: []uniformClient{ |
| 1044 |
newUniformClient(1001001001, 6, 10, time.Second, 57*time.Millisecond), |
| 1045 |
newUniformClient(2002002002, 4, 15, time.Second, 750*time.Millisecond), |
| 1046 |
}, |
| 1047 |
concurrencyLimit: 4, |
| 1048 |
evalDuration: time.Second * 13, |
| 1049 |
expectedFair: []bool{false}, |
| 1050 |
expectedFairnessMargin: []float64{0.20}, |
| 1051 |
evalExecutingMetrics: true, |
| 1052 |
rejectReason: "concurrency-limit", |
| 1053 |
clk: clk, |
| 1054 |
counter: counter, |
| 1055 |
seatDemandIntegratorSubject: seatDemandIntegratorSubject, |
| 1056 |
}.exercise(t) |
| 1057 |
} |
| 1058 |
|
| 1059 |
// TestContextCancel tests cancellation of a request's context. |
| 1060 |
// The outline is: |
| 1061 |
// 1. Use a concurrency limit of 1. |
| 1062 |
// 2. Start request 1. |
| 1063 |
// 3. Use a fake clock for the following logic, to insulate from scheduler noise. |
| 1064 |
// 4. The exec fn of request 1 starts request 2, which should wait |
| 1065 |
// in its queue. |
| 1066 |
// 5. The exec fn of request 1 also forks a goroutine that waits 1 second |
| 1067 |
// and then cancels the context of request 2. |
| 1068 |
// 6. The exec fn of request 1, if StartRequest 2 returns a req2 (which is the normal case), |
| 1069 |
// calls `req2.Finish`, which is expected to return after the context cancel. |
| 1070 |
// 7. The queueset interface allows StartRequest 2 to return `nil` in this situation, |
| 1071 |
// if the scheduler gets the cancel done before StartRequest finishes; |
| 1072 |
// the test handles this without regard to whether the implementation will ever do that. |
| 1073 |
// 8. Check that the above took exactly 1 second. |
| 1074 |
func TestContextCancel(t *testing.T) { |
| 1075 |
metrics.Register() |
| 1076 |
metrics.Reset() |
| 1077 |
now := time.Now() |
| 1078 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 1079 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 1080 |
qCfg := fq.QueuingConfig{ |
| 1081 |
Name: "TestContextCancel", |
| 1082 |
DesiredNumQueues: 11, |
| 1083 |
QueueLengthLimit: 11, |
| 1084 |
HandSize: 1, |
| 1085 |
} |
| 1086 |
seatDemandIntegratorSubject := fq.NewNamedIntegrator(clk, qCfg.Name) |
| 1087 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), seatDemandIntegratorSubject) |
| 1088 |
if err != nil { |
| 1089 |
t.Fatal(err) |
| 1090 |
} |
| 1091 |
qs := qsComplete(qsc, 1) |
| 1092 |
counter.Add(1) // account for main activity of the goroutine running this test |
| 1093 |
ctx1 := context.Background() |
| 1094 |
pZero := func() *int32 { var zero int32; return &zero } |
| 1095 |
// counts of calls to the QueueNoteFns |
| 1096 |
queueNoteCounts := map[int]map[bool]*int32{ |
| 1097 |
1: {false: pZero(), true: pZero()}, |
| 1098 |
2: {false: pZero(), true: pZero()}, |
| 1099 |
} |
| 1100 |
queueNoteFn := func(fn int) func(inQueue bool) { |
| 1101 |
return func(inQueue bool) { atomic.AddInt32(queueNoteCounts[fn][inQueue], 1) } |
| 1102 |
} |
| 1103 |
fatalErrs := []string{} |
| 1104 |
var errsLock sync.Mutex |
| 1105 |
expectQNCount := func(fn int, inQueue bool, expect int32) { |
| 1106 |
if a := atomic.LoadInt32(queueNoteCounts[fn][inQueue]); a != expect { |
| 1107 |
errsLock.Lock() |
| 1108 |
defer errsLock.Unlock() |
| 1109 |
fatalErrs = append(fatalErrs, fmt.Sprintf("Got %d calls to queueNoteFn%d(%v), expected %d", a, fn, inQueue, expect)) |
| 1110 |
} |
| 1111 |
} |
| 1112 |
expectQNCounts := func(fn int, expectF, expectT int32) { |
| 1113 |
expectQNCount(fn, false, expectF) |
| 1114 |
expectQNCount(fn, true, expectT) |
| 1115 |
} |
| 1116 |
req1, _ := qs.StartRequest(ctx1, &fcrequest.WorkEstimate{InitialSeats: 1}, 1, "", "fs1", "test", "one", queueNoteFn(1)) |
| 1117 |
if req1 == nil { |
| 1118 |
t.Error("Request rejected") |
| 1119 |
return |
| 1120 |
} |
| 1121 |
expectQNCounts(1, 1, 1) |
| 1122 |
var executed1, idle1 bool |
| 1123 |
counter.Add(1) // account for the following goroutine |
| 1124 |
go func() { |
| 1125 |
defer counter.Add(-1) // account completion of this goroutine |
| 1126 |
idle1 = req1.Finish(func() { |
| 1127 |
executed1 = true |
| 1128 |
ctx2, cancel2 := context.WithCancel(context.Background()) |
| 1129 |
tBefore := clk.Now() |
| 1130 |
counter.Add(1) // account for the following goroutine |
| 1131 |
go func() { |
| 1132 |
defer counter.Add(-1) // account completion of this goroutine |
| 1133 |
clk.Sleep(time.Second) |
| 1134 |
expectQNCounts(2, 0, 1) |
| 1135 |
// account for unblocking the goroutine that waits on cancelation |
| 1136 |
counter.Add(1) |
| 1137 |
cancel2() |
| 1138 |
}() |
| 1139 |
req2, idle2a := qs.StartRequest(ctx2, &fcrequest.WorkEstimate{InitialSeats: 1}, 2, "", "fs2", "test", "two", queueNoteFn(2)) |
| 1140 |
if idle2a { |
| 1141 |
t.Error("2nd StartRequest returned idle") |
| 1142 |
} |
| 1143 |
if req2 != nil { |
| 1144 |
idle2b := req2.Finish(func() { |
| 1145 |
t.Error("Executing req2") |
| 1146 |
}) |
| 1147 |
if idle2b { |
| 1148 |
t.Error("2nd Finish returned idle") |
| 1149 |
} |
| 1150 |
expectQNCounts(2, 1, 1) |
| 1151 |
} |
| 1152 |
tAfter := clk.Now() |
| 1153 |
dt := tAfter.Sub(tBefore) |
| 1154 |
if dt != time.Second { |
| 1155 |
t.Errorf("Unexpected: dt=%d", dt) |
| 1156 |
} |
| 1157 |
}) |
| 1158 |
}() |
| 1159 |
counter.Add(-1) // completion of main activity of goroutine running this test |
| 1160 |
clk.Run(nil) |
| 1161 |
errsLock.Lock() |
| 1162 |
defer errsLock.Unlock() |
| 1163 |
if len(fatalErrs) > 0 { |
| 1164 |
t.Error(strings.Join(fatalErrs, "; ")) |
| 1165 |
} |
| 1166 |
if !executed1 { |
| 1167 |
t.Errorf("Unexpected: executed1=%v", executed1) |
| 1168 |
} |
| 1169 |
if !idle1 { |
| 1170 |
t.Error("Not idle at the end") |
| 1171 |
} |
| 1172 |
} |
| 1173 |
|
| 1174 |
func countingPromiseFactoryFactory(activeCounter counter.GoRoutineCounter) promiseFactoryFactory { |
| 1175 |
return func(qs *queueSet) promiseFactory { |
| 1176 |
return func(initial interface{}, doneCtx context.Context, doneVal interface{}) promise.WriteOnce { |
| 1177 |
return testpromise.NewCountingWriteOnce(activeCounter, &qs.lock, initial, doneCtx.Done(), doneVal) |
| 1178 |
} |
| 1179 |
} |
| 1180 |
} |
| 1181 |
|
| 1182 |
func TestTotalRequestsExecutingWithPanic(t *testing.T) { |
| 1183 |
metrics.Register() |
| 1184 |
metrics.Reset() |
| 1185 |
now := time.Now() |
| 1186 |
clk, counter := testeventclock.NewFake(now, 0, nil) |
| 1187 |
qsf := newTestableQueueSetFactory(clk, countingPromiseFactoryFactory(counter)) |
| 1188 |
qCfg := fq.QueuingConfig{ |
| 1189 |
Name: "TestTotalRequestsExecutingWithPanic", |
| 1190 |
DesiredNumQueues: 0, |
| 1191 |
} |
| 1192 |
qsc, err := qsf.BeginConstruction(qCfg, newGaugePair(clk), newExecSeatsGauge(clk), fq.NewNamedIntegrator(clk, qCfg.Name)) |
| 1193 |
if err != nil { |
| 1194 |
t.Fatal(err) |
| 1195 |
} |
| 1196 |
qs := qsComplete(qsc, 1) |
| 1197 |
counter.Add(1) // account for the goroutine running this test |
| 1198 |
|
| 1199 |
queue, ok := qs.(*queueSet) |
| 1200 |
if !ok { |
| 1201 |
t.Fatalf("expected a QueueSet of type: %T but got: %T", &queueSet{}, qs) |
| 1202 |
} |
| 1203 |
if queue.totRequestsExecuting != 0 { |
| 1204 |
t.Fatalf("precondition: expected total requests currently executing of the QueueSet to be 0, but got: %d", queue.totRequestsExecuting) |
| 1205 |
} |
| 1206 |
if queue.dCfg.ConcurrencyLimit != 1 { |
| 1207 |
t.Fatalf("precondition: expected concurrency limit of the QueueSet to be 1, but got: %d", queue.dCfg.ConcurrencyLimit) |
| 1208 |
} |
| 1209 |
|
| 1210 |
ctx := context.Background() |
| 1211 |
req, _ := qs.StartRequest(ctx, &fcrequest.WorkEstimate{InitialSeats: 1}, 1, "", "fs", "test", "one", func(inQueue bool) {}) |
| 1212 |
if req == nil { |
| 1213 |
t.Fatal("expected a Request object from StartRequest, but got nil") |
| 1214 |
} |
| 1215 |
|
| 1216 |
panicErrExpected := errors.New("apiserver panic'd") |
| 1217 |
var panicErrGot interface{} |
| 1218 |
func() { |
| 1219 |
defer func() { |
| 1220 |
panicErrGot = recover() |
| 1221 |
}() |
| 1222 |
|
| 1223 |
req.Finish(func() { |
| 1224 |
// verify that total requests executing goes up by 1 since the request is executing. |
| 1225 |
if queue.totRequestsExecuting != 1 { |
| 1226 |
t.Fatalf("expected total requests currently executing of the QueueSet to be 1, but got: %d", queue.totRequestsExecuting) |
| 1227 |
} |
| 1228 |
|
| 1229 |
panic(panicErrExpected) |
| 1230 |
}) |
| 1231 |
}() |
| 1232 |
|
| 1233 |
// verify that the panic was from us (above) |
| 1234 |
if panicErrExpected != panicErrGot { |
| 1235 |
t.Errorf("expected panic error: %#v, but got: %#v", panicErrExpected, panicErrGot) |
| 1236 |
} |
| 1237 |
if queue.totRequestsExecuting != 0 { |
| 1238 |
t.Errorf("expected total requests currently executing of the QueueSet to be 0, but got: %d", queue.totRequestsExecuting) |
| 1239 |
} |
| 1240 |
} |
| 1241 |
|
| 1242 |
func TestFindDispatchQueueLocked(t *testing.T) { |
| 1243 |
const G = 3 * time.Millisecond |
| 1244 |
qs0 := &queueSet{estimatedServiceDuration: G} |
| 1245 |
tests := []struct { |
| 1246 |
name string |
| 1247 |
robinIndex int |
| 1248 |
concurrencyLimit int |
| 1249 |
totSeatsInUse int |
| 1250 |
queues []*queue |
| 1251 |
attempts int |
| 1252 |
beforeSelectQueueLocked func(attempt int, qs *queueSet) |
| 1253 |
minQueueIndexExpected []int |
| 1254 |
robinIndexExpected []int |
| 1255 |
}{ |
| 1256 |
{ |
| 1257 |
name: "width1=1, seats are available, the queue with less virtual start time wins", |
| 1258 |
concurrencyLimit: 1, |
| 1259 |
totSeatsInUse: 0, |
| 1260 |
robinIndex: -1, |
| 1261 |
queues: []*queue{ |
| 1262 |
{ |
| 1263 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 200*time.Second), |
| 1264 |
requestsWaiting: newFIFO( |
| 1265 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 1})}, |
| 1266 |
), |
| 1267 |
requestsExecuting: sets.New[*request](), |
| 1268 |
}, |
| 1269 |
{ |
| 1270 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 100*time.Second), |
| 1271 |
requestsWaiting: newFIFO( |
| 1272 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 1})}, |
| 1273 |
), |
| 1274 |
}, |
| 1275 |
}, |
| 1276 |
attempts: 1, |
| 1277 |
minQueueIndexExpected: []int{1}, |
| 1278 |
robinIndexExpected: []int{1}, |
| 1279 |
}, |
| 1280 |
{ |
| 1281 |
name: "width1=1, all seats are occupied, no queue is picked", |
| 1282 |
concurrencyLimit: 1, |
| 1283 |
totSeatsInUse: 1, |
| 1284 |
robinIndex: -1, |
| 1285 |
queues: []*queue{ |
| 1286 |
{ |
| 1287 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 200*time.Second), |
| 1288 |
requestsWaiting: newFIFO( |
| 1289 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 1})}, |
| 1290 |
), |
| 1291 |
requestsExecuting: sets.New[*request](), |
| 1292 |
}, |
| 1293 |
}, |
| 1294 |
attempts: 1, |
| 1295 |
minQueueIndexExpected: []int{-1}, |
| 1296 |
robinIndexExpected: []int{0}, |
| 1297 |
}, |
| 1298 |
{ |
| 1299 |
name: "width1 > 1, seats are available for request with the least finish R, queue is picked", |
| 1300 |
concurrencyLimit: 50, |
| 1301 |
totSeatsInUse: 25, |
| 1302 |
robinIndex: -1, |
| 1303 |
queues: []*queue{ |
| 1304 |
{ |
| 1305 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 200*time.Second), |
| 1306 |
requestsWaiting: newFIFO( |
| 1307 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 50})}, |
| 1308 |
), |
| 1309 |
requestsExecuting: sets.New[*request](), |
| 1310 |
}, |
| 1311 |
{ |
| 1312 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 100*time.Second), |
| 1313 |
requestsWaiting: newFIFO( |
| 1314 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 25})}, |
| 1315 |
), |
| 1316 |
requestsExecuting: sets.New[*request](), |
| 1317 |
}, |
| 1318 |
}, |
| 1319 |
attempts: 1, |
| 1320 |
minQueueIndexExpected: []int{1}, |
| 1321 |
robinIndexExpected: []int{1}, |
| 1322 |
}, |
| 1323 |
{ |
| 1324 |
name: "width1 > 1, seats are not available for request with the least finish R, queue is not picked", |
| 1325 |
concurrencyLimit: 50, |
| 1326 |
totSeatsInUse: 26, |
| 1327 |
robinIndex: -1, |
| 1328 |
queues: []*queue{ |
| 1329 |
{ |
| 1330 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 200*time.Second), |
| 1331 |
requestsWaiting: newFIFO( |
| 1332 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 10})}, |
| 1333 |
), |
| 1334 |
requestsExecuting: sets.New[*request](), |
| 1335 |
}, |
| 1336 |
{ |
| 1337 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 100*time.Second), |
| 1338 |
requestsWaiting: newFIFO( |
| 1339 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 25})}, |
| 1340 |
), |
| 1341 |
requestsExecuting: sets.New[*request](), |
| 1342 |
}, |
| 1343 |
}, |
| 1344 |
attempts: 3, |
| 1345 |
minQueueIndexExpected: []int{-1, -1, -1}, |
| 1346 |
robinIndexExpected: []int{1, 1, 1}, |
| 1347 |
}, |
| 1348 |
{ |
| 1349 |
name: "width1 > 1, seats become available before 3rd attempt, queue is picked", |
| 1350 |
concurrencyLimit: 50, |
| 1351 |
totSeatsInUse: 26, |
| 1352 |
robinIndex: -1, |
| 1353 |
queues: []*queue{ |
| 1354 |
{ |
| 1355 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 200*time.Second), |
| 1356 |
requestsWaiting: newFIFO( |
| 1357 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 10})}, |
| 1358 |
), |
| 1359 |
requestsExecuting: sets.New[*request](), |
| 1360 |
}, |
| 1361 |
{ |
| 1362 |
nextDispatchR: fcrequest.SeatsTimesDuration(1, 100*time.Second), |
| 1363 |
requestsWaiting: newFIFO( |
| 1364 |
&request{workEstimate: qs0.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 25})}, |
| 1365 |
), |
| 1366 |
requestsExecuting: sets.New[*request](), |
| 1367 |
}, |
| 1368 |
}, |
| 1369 |
beforeSelectQueueLocked: func(attempt int, qs *queueSet) { |
| 1370 |
if attempt == 3 { |
| 1371 |
qs.totSeatsInUse = 25 |
| 1372 |
} |
| 1373 |
}, |
| 1374 |
attempts: 3, |
| 1375 |
minQueueIndexExpected: []int{-1, -1, 1}, |
| 1376 |
robinIndexExpected: []int{1, 1, 1}, |
| 1377 |
}, |
| 1378 |
} |
| 1379 |
|
| 1380 |
for _, test := range tests { |
| 1381 |
t.Run(test.name, func(t *testing.T) { |
| 1382 |
qs := &queueSet{ |
| 1383 |
estimatedServiceDuration: G, |
| 1384 |
seatDemandIntegrator: fq.NewNamedIntegrator(clock.RealClock{}, "seatDemandSubject"), |
| 1385 |
robinIndex: test.robinIndex, |
| 1386 |
totSeatsInUse: test.totSeatsInUse, |
| 1387 |
qCfg: fq.QueuingConfig{Name: "TestSelectQueueLocked/" + test.name}, |
| 1388 |
dCfg: fq.DispatchingConfig{ |
| 1389 |
ConcurrencyLimit: test.concurrencyLimit, |
| 1390 |
}, |
| 1391 |
queues: test.queues, |
| 1392 |
} |
| 1393 |
|
| 1394 |
t.Logf("QS: robin index=%d, seats in use=%d limit=%d", qs.robinIndex, qs.totSeatsInUse, qs.dCfg.ConcurrencyLimit) |
| 1395 |
|
| 1396 |
for i := 0; i < test.attempts; i++ { |
| 1397 |
attempt := i + 1 |
| 1398 |
if test.beforeSelectQueueLocked != nil { |
| 1399 |
test.beforeSelectQueueLocked(attempt, qs) |
| 1400 |
} |
| 1401 |
|
| 1402 |
var minQueueExpected *queue |
| 1403 |
if queueIdx := test.minQueueIndexExpected[i]; queueIdx >= 0 { |
| 1404 |
minQueueExpected = test.queues[queueIdx] |
| 1405 |
} |
| 1406 |
|
| 1407 |
minQueueGot, reqGot := qs.findDispatchQueueToBoundLocked() |
| 1408 |
if minQueueExpected != minQueueGot { |
| 1409 |
t.Errorf("Expected queue: %#v, but got: %#v", minQueueExpected, minQueueGot) |
| 1410 |
} |
| 1411 |
|
| 1412 |
robinIndexExpected := test.robinIndexExpected[i] |
| 1413 |
if robinIndexExpected != qs.robinIndex { |
| 1414 |
t.Errorf("Expected robin index: %d for attempt: %d, but got: %d", robinIndexExpected, attempt, qs.robinIndex) |
| 1415 |
} |
| 1416 |
|
| 1417 |
if (reqGot == nil) != (minQueueGot == nil) { |
| 1418 |
t.Errorf("reqGot=%p but minQueueGot=%p", reqGot, minQueueGot) |
| 1419 |
} |
| 1420 |
} |
| 1421 |
}) |
| 1422 |
} |
| 1423 |
} |
| 1424 |
|
| 1425 |
func TestFinishRequestLocked(t *testing.T) { |
| 1426 |
tests := []struct { |
| 1427 |
name string |
| 1428 |
workEstimate fcrequest.WorkEstimate |
| 1429 |
}{ |
| 1430 |
{ |
| 1431 |
name: "request has additional latency", |
| 1432 |
workEstimate: fcrequest.WorkEstimate{ |
| 1433 |
InitialSeats: 1, |
| 1434 |
FinalSeats: 10, |
| 1435 |
AdditionalLatency: time.Minute, |
| 1436 |
}, |
| 1437 |
}, |
| 1438 |
{ |
| 1439 |
name: "request has no additional latency", |
| 1440 |
workEstimate: fcrequest.WorkEstimate{ |
| 1441 |
InitialSeats: 10, |
| 1442 |
}, |
| 1443 |
}, |
| 1444 |
} |
| 1445 |
|
| 1446 |
metrics.Register() |
| 1447 |
for _, test := range tests { |
| 1448 |
t.Run(test.name, func(t *testing.T) { |
| 1449 |
metrics.Reset() |
| 1450 |
|
| 1451 |
now := time.Now() |
| 1452 |
clk, _ := testeventclock.NewFake(now, 0, nil) |
| 1453 |
qs := &queueSet{ |
| 1454 |
clock: clk, |
| 1455 |
estimatedServiceDuration: time.Second, |
| 1456 |
reqsGaugePair: newGaugePair(clk), |
| 1457 |
execSeatsGauge: newExecSeatsGauge(clk), |
| 1458 |
seatDemandIntegrator: fq.NewNamedIntegrator(clk, "seatDemandSubject"), |
| 1459 |
} |
| 1460 |
queue := &queue{ |
| 1461 |
requestsWaiting: newRequestFIFO(), |
| 1462 |
requestsExecuting: sets.New[*request](), |
| 1463 |
} |
| 1464 |
r := &request{ |
| 1465 |
qs: qs, |
| 1466 |
queue: queue, |
| 1467 |
workEstimate: qs.completeWorkEstimate(&test.workEstimate), |
| 1468 |
} |
| 1469 |
rOther := &request{qs: qs, queue: queue} |
| 1470 |
|
| 1471 |
qs.totRequestsExecuting = 111 |
| 1472 |
qs.totSeatsInUse = 222 |
| 1473 |
queue.requestsExecuting = sets.New(r, rOther) |
| 1474 |
queue.seatsInUse = 22 |
| 1475 |
|
| 1476 |
var ( |
| 1477 |
queuesetTotalRequestsExecutingExpected = qs.totRequestsExecuting - 1 |
| 1478 |
queuesetTotalSeatsInUseExpected = qs.totSeatsInUse - test.workEstimate.MaxSeats() |
| 1479 |
queueRequestsExecutingExpected = sets.New(rOther) |
| 1480 |
queueSeatsInUseExpected = queue.seatsInUse - test.workEstimate.MaxSeats() |
| 1481 |
) |
| 1482 |
|
| 1483 |
qs.finishRequestLocked(r) |
| 1484 |
|
| 1485 |
// as soon as AdditionalLatency elapses we expect the seats to be released |
| 1486 |
clk.SetTime(now.Add(test.workEstimate.AdditionalLatency)) |
| 1487 |
|
| 1488 |
if queuesetTotalRequestsExecutingExpected != qs.totRequestsExecuting { |
| 1489 |
t.Errorf("Expected total requests executing: %d, but got: %d", queuesetTotalRequestsExecutingExpected, qs.totRequestsExecuting) |
| 1490 |
} |
| 1491 |
if queuesetTotalSeatsInUseExpected != qs.totSeatsInUse { |
| 1492 |
t.Errorf("Expected total seats in use: %d, but got: %d", queuesetTotalSeatsInUseExpected, qs.totSeatsInUse) |
| 1493 |
} |
| 1494 |
if !queueRequestsExecutingExpected.Equal(queue.requestsExecuting) { |
| 1495 |
t.Errorf("Expected requests executing for queue: %v, but got: %v", queueRequestsExecutingExpected, queue.requestsExecuting) |
| 1496 |
} |
| 1497 |
if queueSeatsInUseExpected != queue.seatsInUse { |
| 1498 |
t.Errorf("Expected seats in use for queue: %d, but got: %d", queueSeatsInUseExpected, queue.seatsInUse) |
| 1499 |
} |
| 1500 |
}) |
| 1501 |
} |
| 1502 |
} |
| 1503 |
|
| 1504 |
func TestRequestSeats(t *testing.T) { |
| 1505 |
qs := &queueSet{estimatedServiceDuration: time.Second} |
| 1506 |
tests := []struct { |
| 1507 |
name string |
| 1508 |
request *request |
| 1509 |
expected int |
| 1510 |
}{ |
| 1511 |
{ |
| 1512 |
name: "", |
| 1513 |
request: &request{workEstimate: qs.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 3, FinalSeats: 3})}, |
| 1514 |
expected: 3, |
| 1515 |
}, |
| 1516 |
{ |
| 1517 |
name: "", |
| 1518 |
request: &request{workEstimate: qs.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 1, FinalSeats: 3})}, |
| 1519 |
expected: 3, |
| 1520 |
}, |
| 1521 |
{ |
| 1522 |
name: "", |
| 1523 |
request: &request{workEstimate: qs.completeWorkEstimate(&fcrequest.WorkEstimate{InitialSeats: 3, FinalSeats: 1})}, |
| 1524 |
expected: 3, |
| 1525 |
}, |
| 1526 |
} |
| 1527 |
|
| 1528 |
for _, test := range tests { |
| 1529 |
t.Run(test.name, func(t *testing.T) { |
| 1530 |
seatsGot := test.request.MaxSeats() |
| 1531 |
if test.expected != seatsGot { |
| 1532 |
t.Errorf("Expected seats: %d, got %d", test.expected, seatsGot) |
| 1533 |
} |
| 1534 |
}) |
| 1535 |
} |
| 1536 |
} |
| 1537 |
|
| 1538 |
func TestRequestWork(t *testing.T) { |
| 1539 |
qs := &queueSet{estimatedServiceDuration: 2 * time.Second} |
| 1540 |
request := &request{ |
| 1541 |
workEstimate: qs.completeWorkEstimate(&fcrequest.WorkEstimate{ |
| 1542 |
InitialSeats: 3, |
| 1543 |
FinalSeats: 50, |
| 1544 |
AdditionalLatency: 70 * time.Second, |
| 1545 |
}), |
| 1546 |
} |
| 1547 |
|
| 1548 |
got := request.totalWork() |
| 1549 |
want := fcrequest.SeatsTimesDuration(3, 2*time.Second) + fcrequest.SeatsTimesDuration(50, 70*time.Second) |
| 1550 |
if want != got { |
| 1551 |
t.Errorf("Expected totalWork: %v, but got: %v", want, got) |
| 1552 |
} |
| 1553 |
} |
| 1554 |
|
| 1555 |
func newFIFO(requests ...*request) fifo { |
| 1556 |
l := newRequestFIFO() |
| 1557 |
for i := range requests { |
| 1558 |
requests[i].removeFromQueueLocked = l.Enqueue(requests[i]) |
| 1559 |
} |
| 1560 |
return l |
| 1561 |
} |
| 1562 |
|
| 1563 |
func newGaugePair(clk clock.PassiveClock) metrics.RatioedGaugePair { |
| 1564 |
return metrics.RatioedGaugeVecPhasedElementPair(metrics.PriorityLevelConcurrencyGaugeVec, 1, 1, []string{"test"}) |
| 1565 |
} |
| 1566 |
|
| 1567 |
func newExecSeatsGauge(clk clock.PassiveClock) metrics.RatioedGauge { |
| 1568 |
return metrics.PriorityLevelExecutionSeatsGaugeVec.NewForLabelValuesSafe(0, 1, []string{"test"}) |
| 1569 |
} |
| 1570 |
|
| 1571 |
func float64close(x, y float64) bool { |
| 1572 |
x0 := float64NaNTo0(x) |
| 1573 |
y0 := float64NaNTo0(y) |
| 1574 |
diff := math.Abs(x0 - y0) |
| 1575 |
den := math.Max(math.Abs(x0), math.Abs(y0)) |
| 1576 |
return den == 0 || diff/den < 1e-10 |
| 1577 |
} |
| 1578 |
|
| 1579 |
func uint64max(a, b uint64) uint64 { |
| 1580 |
if b > a { |
| 1581 |
return b |
| 1582 |
} |
| 1583 |
return a |
| 1584 |
} |
| 1585 |
|
| 1586 |
func float64NaNTo0(x float64) float64 { |
| 1587 |
if math.IsNaN(x) { |
| 1588 |
return 0 |
| 1589 |
} |
| 1590 |
return x |
| 1591 |
} |
| 1592 |
|
| 1593 |
func qsComplete(qsc fq.QueueSetCompleter, concurrencyLimit int) fq.QueueSet { |
| 1594 |
concurrencyDenominator := concurrencyLimit |
| 1595 |
if concurrencyDenominator <= 0 { |
| 1596 |
concurrencyDenominator = 1 |
| 1597 |
} |
| 1598 |
return qsc.Complete(fq.DispatchingConfig{ConcurrencyLimit: concurrencyLimit, ConcurrencyDenominator: concurrencyDenominator}) |
| 1599 |
} |