Repository: kubernetes
Issue: Improve behaviour when immediately adding work items to a rate-limited or delaying workqueue.
Labels: kind/bug,sig/api-machinery,triage/accepted

### What happened?

## Background

Whilst investigating an issue affecting one of our production kubernetes clusters, I had to take a look at the *“AvailableConditonController”s* that run as part of the kube-aggregator, and implements a rate limited workqueue for scheduling health checks of api extensions that live externally to the apiserver, out in the cluster. (https://github.com/kubernetes/kubernetes/issues/111890).   At the heart of our issue seemed to be a scheduling of far more checks than anticipated (rather a lot).  In looking at the issue with this controller, it led me to taking a closer look at what the workqueue is doing.

## There is a disconnect between Add() and AddAfter() / AddRateLimited()

Delayed and RateLimited workqueues provided by client-go/util/workqueue support the re-adding of entries back into the queue with a delay but also an immediate priority add.  The delaying functionality is provided by new methods AddAfter() and AddRateLimited() which had the behaviour around delays, but the immediate add is serviced by the core queue Add() function and this function has no knowledge and pays no regards to delayed items.  We can think of a delayed queue as a regular queue with an additional "waiting" area tacked on.

It is common for controllers to implement workqueue Add()'s in response informer events and use AddAfter() or AddRateLimited() for re-queuing items that fail and need to be retried.  

Because the Add() functionality has no relation to the delaying implementation it performs a very basic add of an item which results in a couple of surprising behaviours to users of the work queue's who do not have a detailed knowledge of their implementation.

### Extra Reconcile Upon Success

When immediate work queue adds are being through *Add()*, there isn’t a check to see if the same work item is already in the “waiting” queue.  As a result, the work item being reconciled can be successfully reconciled only for it to be performed again (presumably as a NO-OP) as the item is popped off the waiting queue back into the active queue.

Here is an example of the extra reconcile scenario: -

![image](https://user-images.githubusercontent.com/1453938/189152745-08798e38-795d-450c-b4df-b4239889cb46.png)

1. The first event for work item X arrives and is queued by a call to Add()
2. X1 is dequeued and processed.
3. The processing failed and the item is returned to the waiting queue via AddAfter() (called from AddRateLimited())
4. Another event for the same work item X arrives and is immediately added by Add(), so X is now both in the dirty set (X2)  and the waiting queue (X1).
5. X2 is dequeued and processed.
6. This time it succeeds, and so the work item is discarded (and it is forgotten  by the rate-limiter).
7. X1 was left in the waiting queue and is now promoted back into the dirty queue.
8. X1 is dequeued and processed.
9. X1 succeeds and likely a NOOP given the earlier X2 success for the same object X.

The disconnect between the two queues feels quite apparent.  When X2 comes along and warrants immediate processing then why do we keep X1 in the waiting queue?  If the reprocessing of the work item isn't a NO-OP (because the client doesn't have the logic to resolve that) then the superfluous additional check could waste resources.  When considering the number of workqueues based on this code active in a kubernetes cluster at any one time then this wastage adds up.  I think that it makes a lot more sense when we request the immediate queing of a an item to a delayed queue type that we either:

* drop the new X and promote X out of the waiting queue.
* or immediately queue the new X and remove X from the “waiting” queue (if it is present).

Because the new and old X are exactly the same, it does not matter which of the above we do.  In the example, when X2 comes along, we could immediately queue it so that it is executed as soon as possible, but we should also remove X1 from the waiting queue.  We know that if X2 fails it will be returned to the “waiting” queue with the appropriate delay.

### Non Exponential Failure Retry Periods

By choosing a *Rate Limited queue* with an *Exponential Failure Rate Limiter*, we might expect failures to follow the delay set fourth by the rate limiting algorithm, but adding items with *Add()* means extra retries which do not obey the rate-limiter.  This is by design, but its worth highlighting this behaviour as it will undoubtedly catch people (like me) out: -

![image](https://user-images.githubusercontent.com/1453938/189153038-4e0b081d-a82f-4053-81a3-9d489bb21cab.png)
1. The first event for work item X arrives and is queued by a call to Add()
2. X1 is dequeued and processed.
3. The processing failed and the item is returned to the waiting queue via AddAfter() (called from AddRateLimited())
4. Another event for the same work item X arrives and is immediately added by Add(), so X is now both in the dirty set (X2)  and the waiting queue (X1).
5. X2 is dequeued and processed.
6. The processing fails again and so the work item X is returned to the waiting queue, whilst adding it we see that X is already waiting in the form of X1 and this MUST have a shorter wait time so we drop X2.
7. X1 is promoted from the “waiting queue” to the dirty set.
8. X1 is dequeued and processed (again).

The point here is that we have a rate limiting queue which rate limits failures, but in the example above, the failures are not being rate limited, X2 is queued and executed without any regard for the rate limited failure already “waiting” in to be re-queued.  For some use cases of a rate limiting queue it might be desirable to strictly rate limit failures in order to protect the failing resource.  In the case of the AvailableConditionController. each work item is an API request to a HTTPS backend service and backing-off, giving the service some space is the more appropriate choice over the fastest possible time to recovery (we noticed the rate limiting having very little impact during our incident because all of the calls to Add() were preempting the rate limit and forcing the workitem to be reprocessed at a far greater rate).




### What did you expect to happen?

* I would like to see the default behaviour of rate-limited queues change so that when you request the immediate queuing of work item X, it removes X from the waiting area (like promoting it out of waiting).
* I would like to see a new rate limited queue type that is more strict about enforcing the rate limits of reconciles for objects that are erroring (at present a new Add() will skip over any rate limiting).

### How can we reproduce it (as minimally and precisely as possible)?

You just need to add an item to the queue with a delay and then try and add the same item again with an Add() and inspect the state of the queues.  I have written a couple of tests in a PR which I will be linking to this issue which captures

### Anything else we need to know?

_No response_

### Kubernetes version

<details>

```console
$ kubectl version
WARNING: This version information is deprecated and will be replaced with the output from kubectl version --short.  Use --output=yaml|json to get the full version.
Client Version: version.Info{Major:"1", Minor:"25", GitVersion:"v1.25.0", GitCommit:"a866cbe2e5bbaa01cfd5e969aa3e033f3282a8a2", GitTreeState:"clean", BuildDate:"2022-08-23T17:36:43Z", GoVersion:"go1.19", Compiler:"gc", Platform:"darwin/arm64"}
Kustomize Version: v4.5.7
Server Version: version.Info{Major:"1", Minor:"19+", GitVersion:"v1.19.13-REDACTED", GitCommit:"69a0abf33c45fadd7d943341e385204a5c1631b3", GitTreeState:"archive", BuildDate:"2022-01-14T00:59:48Z", GoVersion:"go1.15.14", Compiler:"gc", Platform:"linux/amd64"}
WARNING: version difference between client (1.25) and server (1.19) exceeds the supported minor version skew of +/-1
```

</details>


### Cloud provider

<details>

</details>


### OS version

<details>

```console
# On Linux:
$ cat /etc/os-release
# paste output here
$ uname -a
# paste output here

# On Windows:
C:\> wmic os get Caption, Version, BuildNumber, OSArchitecture
# paste output here
```

</details>


### Install tools

<details>

</details>


### Container runtime (CRI) and version (if applicable)

<details>

</details>


### Related plugins (CNI, CSI, ...) and versions (if applicable)

<details>

</details>