最近遇到一个场景，在每分钟错误计数达到250时发送消息。这里的每分钟并不是说整点的几分，有可能是现在16：16：16到16：17：16。
我了解到周围有人是用分钟的定时器来近似实现的，首先这样就限制了是整点的分秒，其次只限于对时间不敏感的场景，第三不能精确到秒，比如要求1次每秒的限制，因为定时器中任务执行很可能超过1s，而且还有并发的副作用。
那么直接在每次错误后向前扫描数量的笨方法呢？明显效率太低。
个人对于这个问题进一步分析，认为这个属于请求速率限制问题，并且找到的合适的关键字rate limit之后去google。发现stackoverflow有关于这类问题的讨论。在阅读了诸多资料之后，自己了解到两种专门针对请求速率限制的算法：Leaky Bucket和Token Bucket。下面简单介绍一下两种算法。
Leaky Bucket的思想是认为有一个会漏水的桶，水以恒定速率滴出，上方会有水滴（请求）进入水桶。显然，如果上方水滴进入速率超过水滴出的速率，那么水桶就会溢出，这里的溢出就是traffic shaping和traffic policing的条件，即执行某个过载任务的时候。
Token Bucket的思想是同样有一个桶，令牌以恒定速率放入桶，桶内的令牌数有上限，每个请求会acquire一个令牌，如果某个请求来到而桶内没有令牌了，请说明这个请求是过载的。和Lecky Bucket不同的是，Token Bucket存在burst rate。比如当前令牌放入速率4个每秒，桶的令牌上限是8，第一秒内没有请求，第二秒实际就可以处理8个请求！虽然平均速率还是4个每秒，但是爆发速率是8个每秒。
两个算法的实现上，Leaky Bucket还分meter和queue，meter看起来需要定时器辅助，queue不太符合我的需求。Token Bucket虽然有burst rate，但是只要调整为和rate一样就可以了，而且实现起来不需要定时器。
Token Bucket的实现原理是计算请求时间和上一次请求时间之间内增加的令牌数放入桶，比较桶内的令牌数是否足够用于请求，如果不够就认为过载，否则减去响应令牌，设置上一次请求时间为本次请求时间。注意下面的take方法实现，虽然只有不到十行，但准确地解决了请求速度限制问题。
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) {
capacity = tokensPerSeconds = (int) (tokensPerUnit / unit.toSeconds(1L));
}
public boolean take() {
long now = System.currentTimeMillis();
tokens += (int) ((now - timestamp) * tokensPerSeconds / 1000);
if (tokens > capacity) tokens = capacity;
timestamp = now;
if (tokens < 1) return false;
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());
}
}
运行上述程序的话可以看到4次允许，1次失败，4次允许，1次失败的样子，因为250/分约等于4/秒。
另外调整burst rate和rate的方式从之前的4个每秒的例子中隐约看到了，如果桶的大小等于每秒的令牌数的话，那么每秒的burst rate就是rate。TokenBucket的构造函数也是这么做的。
true true true true false true true true true false
参考文档