Debian Codegraph @

pkg/util/flowcontrol/fairqueuing/queueset/queueset_test.go

raw
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 }