需求和场景
场景比较简单，就是用户可以设置哪些API，的在多少时间内最多访问多少次。
用户会收到发送请求太频繁了。这个可以用HTTP 状态429返回给用户。
这个系统必须高可用，因为它是挡在前面的保护层。
同时这个系统不能引入额外的延迟影响用户体验。
三种不同的限制
硬限制：API请求的数量不能超过限制。
软限制：在此类型中，我们可以将API请求限制设置为超过特定百分比。 例如，如果我们每分钟有100条消息的速率限制，超过10％的限制。 我们的速率限制器每分钟最多允许110条消息。
弹性或动态限制：在弹性限制下，如果系统有一些可用资源，请求数可能会超出阈值。 例如，如果用户每分钟只允许100条消息，如果系统中有可用的免费资源，我们可以让用户每分钟发送100条以上的消息。
服务的算法
一般限制分为2类，一种是固定的窗口，比图1秒限制3条信息。
我们可以这样定义，0-1,1-2,2-3.。。。这几个窗口里。最多只能有2条信息。
还有一种窗口是滑动的，也就是1.5-2.5,1.6-2.6 这种都要考虑，最多只能有2条信息。
下面这个架构的含义就是，用户发一个请求，WEBSERVER 会先去问RATELIMIT是否超过限制，如果没超过限制，再去调对应的API。
固定窗口算法。
要求：限定每个用户每分钟最多发3次请求。
我们会存KEY，就是那个用户ID。
VALUE:{次数，开始时间}
用户每发一次请求，我们都会把这个时间向下取整到最近的分钟。然后拿数据库里的KEY，找到VALUE，如果START TIME一直，CNT++。
如果不一致，就删除旧的，创建新的。
如果CNT>=3，则拒绝请求。
这种算法有2个问题。
第一个一个用户可以在前一分钟的后半段，和后一分钟的前半段，累计一共可以在这个60秒内，获得6次请求的效果。
另外一个是原子性的问题。在分布式环境中，读后写会创造竞态条件。可以打破3次的限制，如下
这里如果我们用的是REDIS，我们可以使用REDIS LOCK 来解决原子性的问题。不过这将降低来自同一用户的并发请求和引入新的复杂性为大家。
如果我们使用CONCURRENT HASHMAP，可以最大程度缩小锁的粒度。
如果要把算法改成滑动窗口的话，我们就只维护最近1分钟内的时间，也就是一个新时间进来的时候，把之前所有小于一分钟的都丢了。然后看CNT。
如果既要限制每分钟不能超过3个请求，每小时不能超过10个请求，可以用CNT来集合。
这里的每分钟是固定窗口了。
如何优化使得每分钟也是滑动窗口呢
那么我们可能需要另外一个HASH映射，按照分钟的滑动走。然后同时把这个也计算到这个小时的HASH映射上。也就是一个分组的思想发。
我们先看下误差是怎么产生的，如果限制是每天访问10次。只累加小时数的时候，就会是上面那个范围。
如果要滑动窗口的话，我们还需要统计昨天0点的后半段。所以就看这个漏掉那一段时间数据重不重要。
存的时候存3次。
还有一种做法，就是存进队列。如果一天之内只能有100个，我们就去看前100个，那个TIMESTAMP 和现在的时间相减，是否大于24小时。
优化
我们可以根据USERID 来SHARDING，那么这个用户的请求都会分配到同一个SERVER来处理。
用IP来限制的坏处有，网吧和公共场所共用一个IP，还有就是一个就是IPV6非常多。
用user token来限制的坏处。如何限制使用LOGIN API本身呢？如果用用户名的话，还有攻击者可以使用一个USER，疯狂的错误登陆，来让那个用户本身无法登陆。
所以我们可以按需来结合上面2种策略。
