background

Comparison of common traffic limiting algorithms

accuracy Output jitter Instantaneous peak flow performance
The single window insufficient frequent support high
The sliding window The more Windows, the more accurate frequent support high
funnel High, depending on the number of barrels There is no Does not support Request queuing causes RT to increase
The token bucket High, depending on the number of barrels Supports instantaneous peak traffic, without jitter support high

Golang standard library has its own implementation of the traffic limiting algorithm based on Token Bucket.

Construct

// NewLimiter returns a new Limiter that allows events up to rate r and permits
// bursts of at most b tokens.
func NewLimiter(r Limit, b int) *Limiter {
	return &Limiter{
		limit: r,
		burst: b,
	}
}
Copy the code

The standard library provides a constructor with two inputs:

  1. The first parameterr LimitRepresents the number of tokens generated in the Token Bucket per second.LimitOverride of type FLOAT64.
  2. Second parameterb intIs the number of tokens in the bucket in the initial state.

If we want to create a token Bucket with an initial size of 10 that then produces 5 tokens per second, we can do the following:

limiter :=rate.NewLimiter(5.10)
Copy the code

A special case

  • rate.Every

    Time /rate provides the Every method in addition to the constructor. Such as: 
    limiter := rate.Every(time.Second)
Copy the code

    Creates a token Bucket that generates one token per second.

  • b= = 0

    It is allowed to declare a Token Bucket with a capacity of 0, in which case all requests will be rejected.
  • Inf

    The time/rate package also declares an Inf constant, which is defined as follows: 
    // Inf is the infinite rate limit; it allows all events (even if burst is zero).
const Inf = Limit(math.MaxFloat64)
Copy the code

    与b== 0 is the opposite. By definition, if the parameterLimitInf will allow all requests, even ifb= = 0.

Wait/WaitN

func (lim *Limiter) Wait(ctx context.Context) (err error)
func (lim *Limiter) WaitN(ctx context.Context, n int) (err error)
Copy the code
  1. Wait(CTX) is equivalent to WaitN(CTX, 1)
  2. If the Token Bucket does not satisfy the consumption condition (less than N), this method blocks until the condition is met or times out.
  3. The Wait method can be controlled by the type of context (DeadLine, TimeOut), for example. 
     ctx, cancel := context.WithTimeout(context.Background(), time.Second*5)
 defer cancel()
 err := limiter.WaitN(ctx, 2)
Copy the code

Allow/AllowN

func (lim *Limiter) Allow(a) bool
func (lim *Limiter) AllowN(now time.Time, n int) bool
Copy the code

Allow(time.now ()) = AllowN(time.now (), 1)

  1. This method returns false if the tokens in the Token Bucket do not satisfy the consumption criteria (less than N), and true otherwise.
  2. In production scenarios, if the rate is too high, the request is directly lost.

Reserve/ResrveN

func (lim *Limiter) Reserve(a) *Reservation
func (lim *Limiter) ReserveN(now time.Time, n int) *Reservation
Copy the code

Reserve(time.now ()) equivalent to ResrveN(time.now (), 1)

  1. The call returns one regardless of whether the consumption condition is satisfied*ReservationObject.
  2. This method determines whether limit can provide N tokens at a specified time.
  3. Reservatio.OK()If false is returned, it indicates that the wait duration cannot be calculated and the wait duration is directly enteredCancel()Cancel the operation and return the token used.
  4. Reservatio.OK()If true is returned, it indicates that the token can be obtained after a period of timeDelay()Method returns the amount of time to wait.

Dynamic Adjustment

func (lim *Limiter) SetLimit(newLimit Limit) 
Copy the code

This method can dynamically change the rate at which tokens are placed