proposal: x/time/rate: Add Sliding window, Fixed window, and Leaky bucket rate limiters

[deefdragon]

Is your feature request related to a problem? Please describe.
When interacting with an external API that has a rate limiter implemented, it is important to have a matching rate limiter so that requests aren't unintentionally triggering that rate limit.

Describe the solution you'd like
Implementation of

• Sliding window
• Fixed Window
• Leaky Bucket
• (Other?)

rate limiting algorithms.

Describe alternatives you've considered
Some of these algorithms exist under external repositories

• uber-go/ratelimit (leaky bucket)
• RussellLuo/slidingwindow
• glycerine/go-sliding-window

but the ideal would be for a common interface and location for these algorithms

Additional context
I requested the creation of a common interface in #43003 but I put the cart before the horse.
As with any request, the initial goal is to determine which, if any of these are worth implementing, and in what form.

[ajwerner]

There are a lot of different features you may or may not want in a rate limiter. Features come with tradeoffs like dependencies or memory usage etc. The x/time/rate limiter is hardly a panacea. Features one might want are:

• Fairness (or arbitrary queuing behavior)
• Metrics integration
• Different burst behavior (getting an error or truncating to the burst size can be very painful, a "debt" concept can be good)

My feeling is that this proposal would carry more weight if:

(A) It proposed a uniform interface.
(B) Explained why this interface should be centralized as opposed to just another library.

I'd think you should start with (A).

[deefdragon]

As part of the examination of x/time/rate that I did for 43003, I moved several things around to learn about it, and created an interface that could be a starting point. Looking back at it, I believe that my original suggestion was OK, but could be better. I also see several things that could be improved in general, but would go in the opposite direction norms wise.

as such I have two options as starting points, The first

type Limiter interface {
	AllowN(now time.Time, n int) bool
	ReserveN(now time.Time, n int) Reservation
	WaitN(ctx context.Context, n int) error
}

type Reservation interface {
	CancelAt(now time.Time)
	DelayFrom(now time.Time) time.Duration
	OK() bool
}

Is effectively a slimmed down version of the current implementation, and really only differs in what it removes from my original messing around in that it removes the helpers.

The second is a much more radical change to the way Reservation works, but which I think cleans up the interfaces. I suggest this only because it is an x package, and the creation of a Limiter interface would be a backwards incompatible change requiring renaming of the current Limiter to TokenBucketLimiter anyway.

type Limiter interface {
	Allow(time.Time, int) bool
	Reserve(time.Time, int) Reservation
}

type Reservation interface {
	Cancel(context.Context)
	Ready() <-chan bool
	ExpectedDelay(time.Time) time.Duration
	Delay(time.Time) time.Duration
	OK() bool
}

Allow could be argued to be redundant to Reserve, but I believe the ability to check the limiter internally in a safe way outweighs the increase in interface complexity.

From smallest to largest, the other changes are as follows

• The names for most methods were shortened from their N forms to increase the readability of the interface.
• The change of Cancel from a time.Time to a context.Context, to allow for a broader ability to cancel the reservation.
• The creation of Ready, which returns a channel that outputs true when the reservation is ready, (and possibly false if it was canceled/changed).
  • This allows for updating reservations without worrying about how external timers may be affected.
  • ExpectedDelay returns the time that, assuming nothing is canceled, the reservation will be ready at.
  • Delay returns the same, however it locks the reservation at it's current time.