The token bucket

The limit is the average inflow rate. The token bucket algorithm can exceed the limit in the case of a burst. It is an improved version of the leaky bucket, which can prevent a certain degree of flow burst. If the burst traffic is larger than the generation rate but smaller than the capacity of the bucket, it is acceptable.

Principle:

  • A token bucket holds a certain number of tokens (a token bucket contains tokens, not traffic), and each request that passes consumes one token. Without a token in the bucket, no data can pass through.
  • In order for the interface to be able to pass data, you need to add tokens to the bucket. Increasing the speed of the token determines the speed at which traffic passes, similar to leaking buckets.
  • When traffic enters the token bucket, it needs the corresponding number of tokens to pass. If no, the request is rejected.
  • Due to the amount of token buckets, a certain amount of traffic burst can be prevented, as long as the average rate is within a reasonable range of control.

implementation

parameter

  • Token generation rate
  • Update time (used to calculate the number of tokens generated)
  • Bucket capacity
  • Current number of tokens
// Token generation rate
    private int speed = 1;

    // Update time
    private long updateTime;

    / / bucket capacity
    private int capacity = 100;

    // The current number of tokens
    public int num;
Copy the code

methods

When traffic enters, the number of tokens at the current time is first updated. If the number of tokens is sufficient, the tokens are consumed and passed.

public String filter(int permit) {
/* The number of tokens to settle first */
long now = System.currentTimeMillis();
// The upper limit is the capacity of the bucket. If the capacity exceeds the threshold, the bucket is discarded
long time = (now -this.updateTime) / 1000;
this.num = Math.toIntExact(Math.min(capacity,this.num + time * speed));
this.updateTime = now;
String message = "Current number of tokens:"+this.num+", the number of tokens required"+permit;
if(this.num < permit) {
        String error = message+", request declined ================";
        System.out.println(message);
return error;
    }
else{
        System.out.println(message);
this.num =this.num - permit;
return message;
    }
Copy the code

Comparison with a leaky bucket

To store objects

  1. The leaky bucket stores the request volume. When the request rate is greater than the pass rate, the excess requests are stored in the leaky bucket.
  2. The token bucket stores the amount of tokens, and the generated tokens will be consumed in the token bucket. If the number of tokens is full, the excess tokens are discarded.

Limit method

  1. Limit the flow at the outgoing rate. The restricted flow is kept in a leaky bucket for smooth passage. If the bucket is full, excess traffic will be rejected.
  2. Limit traffic by token generation rate. Traffic needs to consume the corresponding number of tokens to pass through. In this case, the rate generated by tokens is smaller than the rate of traffic passing through, so traffic can be restricted. Excess traffic (with no tokens to consume) is cached or discarded.