Design Rate Limiter做限流

Traffic Shape: 流量整形

解法1：Time-bucket with Database

Acquire()
   s = GetCurrentSecond();
   counter = Database.Get(s);
   if(counter == null && counter >=5)
     return false
   else
     Database.increase(s,1);
     Database.expire(s,1);
     return true;

解法2：Leaky Bucket一种简单实现

 private class LeakyBucketLimiter {
    private int numDropsInBucket = 0;
    private Date timeOfLastDropLeak = null;
    private final int _BUCKET_SIZE_IN_DROPS = 20;
    private final long _MS_BETWEEN_DROP_LEAKS = 1000 * 60 * 60; // 1 hour

    public synchronized boolean addDropToBucket() {
        Date now = new Date();
        // first of all, let the bucket leak by the appropriate amount
        if (timeOfLastDropLeak != null) {
            long deltaT = now.getTime() - timeOfLastDropLeak.getTime();
            // note round down as part of integer arithmetic
            long numberToLeak = deltaT / _MS_BETWEEN_DROP_LEAKS;
            if (numberToLeak > 0) { //now go and do the leak
                if (numDropsInBucket <= numberToLeak) {
                    numDropsInBucket = 0;
                } else {
                    numDropsInBucket -= (int) numberToLeak;
                }
                timeOfLastDropLeak = now;
            }
        }

        if (numDropsInBucket < _BUCKET_SIZE_IN_DROPS) {
            numDropsInBucket++;
            return true; // drop added
        }

        return false; // overflow
    }
}

References

1. Guava RateLimiter在Web应用中的使用

2 Rate Limiter

3 Rate Limiting Decorator with Redis

4 Token Bucket Java Implementation

5 LeetCode: Rate Limiter