一、简介

Rate limiting is an imperative technique to prepare your API for scale and establish high availability and reliability of your service. But also, this technique comes with a whole bunch of different options of how to handle a detected limits surplus, or what type of requests you want to limit. You can simply decline this over limit request, or build a queue to execute them later or combine these two approaches in some way。

占位-令牌桶算法实现

二、核心流程

工作过程包括3个阶段：生产令牌、预留令牌、等待令牌。

技术小剧场：餐馆吃饭，厨师按照固定速率做饭，要吃饭得排队取号。

1、生产令牌：周期性的以固定速率往令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已满，则丢弃多余的令牌。
RateLimiter - 图1RateLimiter 将从 epoch 到当前的总时间（纳秒）按 大小 limitRefreshPeriod 分割成一个个周期，在每个周期开始时，往令牌桶中放入 limitForPeriod 个有效令牌 。

2、预订令牌：

3、等待令牌：

三、设计要点

1、AtomicRateLimiter

1.1、生产令牌

要点1、计算当前可用令牌数：请求驱动，当前令牌数量为实时计算，而不是定时刷新。
image.png

1.2、预订令牌

要点1、计算等待时间
image.png
要点2、预留令牌：在不超时的前提下，预留所需令牌数
image.png

去餐馆吃饭，一般会有一个排队心里预期，合适的话就取号，不合适就走人。

1.3、等待令牌

要点1、明明等不到，还让死等，这不是欺骗消费者么？
image.png

1.4、其他

要点1、CAS 优化
image.png

2、SemaphoreBasedRateLimiter

2.1、生产令牌

要点1、基于信号量 Semaphore 周期性刷新令牌数。
image.png

2.2、取号等待

image.png