Rate limiter （请求速率限制问题）

http://blog.gssxgss.me/not-a-simple-problem-rate-limiting/

The solution is Token Bucket.
Token Bucket is a bucket which has a fixed capacity. We put tokens into the token with a fixed rate. When a request comes, if there is no token in the bucket, the request will be denied. Otherwise, the request will be approved and the number of tokens in the bucket decrease by one.


static class TokenBucket {

  private final int capacity;
  private final int tokensPerSeconds;
  private int tokens = 0;
  private long timestamp = System.currentTimeMillis();

  public TokenBucket(int tokensPerUnit, TimeUnit unit) {
    //set capacity and rate
    capacity = tokensPerSeconds = (int) (tokensPerUnit / unit.toSeconds(1L));
  }

  public boolean take() {
    //calc the # of tokens added into bucket since last request time
    long now = System.currentTimeMillis();
    tokens += (int) ((now - timestamp) * tokensPerSeconds / 1000);
 
    //cannot overflow the capacity
    if (tokens > capacity) tokens = capacity;
 
    //if no token, won't reply to the request
    if (tokens < 1) return false;
    //if having enough token, reply
    else{
         timestamp = now;
         tokens--;
         return true;
    }
  }

}

public static void main(String[] args) throws InterruptedException {
  TokenBucket bucket = new TokenBucket(250, TimeUnit.MINUTES);
  Thread.sleep(1000L);
  for (int i = 0; i < 5; i++) {
    System.out.println(bucket.take());
  }
  Thread.sleep(1000L);
  for (int i = 0; i < 5; i++) {
    System.out.println(bucket.take());
  }
}