Mitigate wind-up problem in AP&F: prevent queue virtualStart lag

[yue9944882]

NONE

here is simpler simulation how the max-min fairness issue happens for the wind-up test where the global virtual time proceeds 1.5/s because rate = ConcurrencyLimit/NEQ hence 1.5 = 3/2 and at the beginning of the test Q1 demands 2/s and Q2 demands 1/s, at the middle of test, we double the demand for Q2 to 2/s:

# VS(queue) = virtual start for the queue,  VSE(queue) = virtual start for the queue excluding the estimated service time
# GVT = global virtual time, or per-queue-set virtual time, RT = real world time

(before this PR)
---------------------------------------------------------------------
| RT      |  1  |  2  |  3  | ... | 20 |  21  | 22 |  23  | ...| 40 | 
---------------------------------------------------------------------
| VSE(Q1) |  2  |  4  |  6  | ... | 40 |  41  | 42 |  43  | ...| 60 | 
---------------------------------------------------------------------
| VSE(Q2) |  1  |  2  |  3  | ... | 20 |  22  | 24 |  26  | ...| 60 |
---------------------------------------------------------------------
| GVT     | 1.5 |  3  | 4.5 | ... | 30 | 31.5 | 33 | 34.5 | ...| 60 |
---------------------------------------------------------------------
                                    ^                               ^
        (we double the throughput for Q2 at this point)         (VSE reaches equal for Q1 and Q2 at this point)                                                            



(after this PR)
------------------------------------------------------------------------------------
| RT      |  1  |  2  |  3  | ... | 20 |  21  | 22 |  23  | ...| 30 |  31  | ...| 40 |
------------------------------------------------------------------------------------
| VSE(Q1) |  2  |  4  |  6  | ... | 40 |  41  | 42 |  43  | ...| 50 | 51.5 | ...| 65 | 
------------------------------------------------------------------------------------
| VSE(Q2) | 1.5 |  3  | 4.5 | ... | 30 |  32  | 34 |  36  | ...| 50 | 51.5 | ...| 65 |
------------------------------------------------------------------------------------
| GVT     | 1.5 |  3  | 4.5 | ... | 30 | 31.5 | 33 | 34.5 | ...| 45 | 46.5 | ...| 60 |
------------------------------------------------------------------------------------
                                    ^                               ^
        (we double the throughput for Q2 at this point)         (VSE reaches equal for Q1 and Q2 at this point)                

then let's generalize the ratio of demanding concurrency of Q1:Q2 from 2:1 to n:1, if the credit accumulates for a period of real time T, then Q2 will take T/n real time to catch up with Q1's VSE. hence the bigger burst of credit accumulation we have, the shorter period of time it takes to ease the burst.

btw the tests are adjusted to introduce a margin value for evaluating fairness.

[yue9944882]

@lavalamp @deads2k @MikeSpreitzer @ahg-g @adtac @tkashem

[yue9944882]

/retest

[roycaihw]

/assign @lavalamp
/triage accepted

[MikeSpreitzer]

This is a partial mitigation of the problem (#95979). This mitigation addresses one of the two sides of the imbalance. This is better than nothing.

The other side of the imbalance is that queues using more than the even allocation build up a disadvantage in their virtualStart. Such a queue keeps its accumulated disadvantage until that queue becomes empty. This is a disadvantage relative to queues using less than the even allocation --- including empty queues. Thus, a queue that transitions from empty to non-empty starts with a relative advantage compared to the queues that have a built-up disadvantage.

[MikeSpreitzer]

How about changing the title of this PR from speaking about a "fix" to speaking about "mitigation"? Perhaps something like "Mitigate wind-up problem in API Priority and Fairness"? Or perhaps something more specific, such as "Prevent queue virtualStart lag in API Priority and Fairness"?

[ahg-g]

/milestone v1.20

[MikeSpreitzer]

/LGTM

[lavalamp]

/approve

[k8s-ci-robot]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: lavalamp, yue9944882

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Needs approval from an approver in each of these files:

• staging/src/k8s.io/apiserver/OWNERS [lavalamp]

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

[MikeSpreitzer]

/kind bug

[MikeSpreitzer]

/priority important-soon