Web API 速率限制（二）- 令牌桶算法简介

实施策略

如果你想要建立一个限速系统，首先要确保限速系统不会增加API的响应时间。为了保证高性能和横向扩展性，很多人都会采用像Redis一样的内存数据存储来做限速器。因为Redis的读写速度很快，并且善于用作计数器。

限速

算法

限速算法有很多，这个系列文章将会介绍如下三种限速算法：

令牌桶固定窗口计数器滑动窗口计数器

今天介绍第一种：令牌桶算法。

令牌桶算法

令牌桶算法，英文是Token Bucket。令牌桶算法可以保持稳定的流量上限，同时也允许偶尔的流量爆发。

我们可以通过下面这个类比来进行解释，有一个容量有限的桶，令牌以固定的速率添加到这个桶里面。由于桶的容量是有限的，所以不可能无限制的往里面添加令牌，如果令牌到达桶的时候，桶是满的，那么这个令牌就被抛弃了。每次请求，n个数量的令牌从桶里面被移除，如果桶里面的令牌数少于n，那么该请求就会被拒绝。

举个例子

比如说你想把API的速率限制到每分钟20次，同时允许偶尔的流量爆发，最大不超过每分钟50次。那么你可以使用一个Key-Value的内存数据存储，例如Redis，然后：

用户的第一次请求时，初始化一个桶，它能装50个令牌，把请求的时间戳和令牌的数量存在Redis里，使用用户ID作为Key。在后续的请求里，按照预定的固定速率和上次请求后经过的时间向桶里面填充新的令牌。然后从桶里面删除一个令牌，并把时间戳更新为现在的时间。最后，如果可用的令牌数为0，那么拒绝请求。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！