limit req may be not strictly accurate under certain circumstances

[y123456yz]

ngx_http_limit_req_lookup()
{
...............
ms = (ngx_msec_int_t) (now - lr->last);
excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
...........
}

if there have several connections(For example 10 connections ) in a millimeter, ms = (ngx_msec_int_t) (now - lr->last) will return 0, then excess +=1000, So excess is larger than the actual value , for example, 10000 requests in a millisecon.

I think the unit of max Token bucket should be ms.it will be More accurate

[hongxiaolong]

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

maybe you can consider excess as the total request nums in the limit queue

so, we can get as follows:

nums in queue now = nums in queue before - nums can be processed in passed ms + this request

/* no requests in the limit queue, so reset to 0 */
if (excess < 0) {
    excess = 0;
}

...

/* now nums in queue > burst, we can not process this request, so return NGX_BUSY  */
if ((ngx_uint_t) excess > limit_req->burst) {
    return NGX_BUSY;
}

...

/* this request still can be processed, return NGX_AGAIN */
if (excess) {
    return NGX_AGAIN;
}

therefore, we do not need to consider "ms = (ngx_msec_int_t) (now - lr->last) will return 0"

wish to be helpful

[y123456yz]

@hongxiaolong 兄弟，才看到你的评论。

这个算法应该属于令牌桶算法，应该是存在误差的，假设以下场景：
假设配置限速大小为10000每秒，配置worker工作进程就为1，则令牌桶允许最大容量令牌数为10000 * 1000，同时每毫秒自动从令牌桶中删除的令牌数为10000。如果在1秒钟时间段的第500ms的时候，已经接受了10000个连接，则令牌桶中令牌数为：10000 * 1000-500 * 1000，也就是令牌桶还可以扔500 * 1000个令牌才能达到最大容量，这样下一个1ms(也就是500ms到501ms这1ms内)可以接受500个请求。501ms到后，又会删除10000个令牌，又可以接收10个请求，依次继续循环下去。

在高并发请求的情况下，配置限速为10000，实际上可能达到20000。

这种可能后端业务系统就会被压死，引起一系列崩溃。

我的意思是可以通过限制每ms令牌桶最大容量，而不是每秒令牌桶最大容量来解决这个问题。

阿里的兄弟也来讨论下这个问题吧

[hongxiaolong]

可能你对令牌桶算法的理解有一点偏差，摘一段维基百科解释如下：

令牌桶：

1、每秒将 r 个令牌放入令牌桶，或者说，每过 1/r 秒桶中增加一个令牌；
2、令牌桶中最多存放 b 个令牌，如果桶满了，新放入的令牌会被丢弃；
3、当一个 n 字节的数据包到达时，消耗 n 个令牌，然后发送该数据包；
4、如果桶中可用令牌小于 n，则该数据包将被缓存或丢弃；

而且，NGINX中的限流算法更准确地说其实是漏桶和令牌桶算法思想的结合：

漏桶算法能够强行限制数据的传输速率；

令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

---

在没有设置"burst"时，用漏桶可能更易理解；

在设置"burst"允许一定量的突发时，令牌桶的思想可能更贴切。

---

还是直接上代码解释一下最开始的回答：

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

• excess：当前时刻队列请求数；

• lr->excess：上一时刻队列已有请求数；

• ctx->rate * ngx_abs(ms) / 1000：间隔时间（当前时刻 - 上一次时刻）内计算可得的请求数；

• 1000：当前请求，即请求数：1

剩下的很容易理解，当前时刻队列请求数即左值excess：

• 小于0：说明已间隔较长时间，重置队列；

• 大于"burst"：即请求量过大，已超过允许突发上限，限流；

• 小于"burst"但仍大于0：说明流量未达上限，有待继续；

不知这样解答是否可以有帮助

如有兴趣，后续我也可以汇总一下NGINX官方的限流模块及其算法，到时候可以贴出来一起讨论

多谢

[y123456yz]

@hongxiaolong
3Q，刚刚重新简单走读了下代码，这个限流过程是没问题的。
之前我误解的原因是: 把burst看成了限流配置了，所以感觉可能会有很大的误差在里面。
实际上配置中rate才表示限流值，burst表示允许的突发流量。

实际上允许的连接应该是rate+burst。刚好实现了限流，和分析的一致。

[hongxiaolong]

好的，你的问题应该已完结，

我关闭了该issue，如果有问题可以再打开

[y123456yz]

@hongxiaolong
今天我又扫了一下这个算法，觉得还是有点不妥。
rate表示每秒的速度，burst应该是允许的突发流量，那么如果为配置rate=10000 r/s, burst=1,那么一秒钟内期望允许的请求最大应该为10001，但是从如下代码层面看，如果burst配置为1，那么最多1ms内能放过去1到2个请求，也就是实际上每秒放行的流量在1000到2000之间，但是我们期望的应该是10001，差距有点大。
if ((ngx_uint_t) excess > limit->burst) {
return NGX_BUSY;
}

我觉得，如果rata / 1000 > limit->burst，应该改为如下：
if ((ngx_uint_t) excess > ctx->rate / 1000) {
return NGX_BUSY;
}

或者在检查配置的时候，如果配置rata > 1000，则burst 必须大于rate/1000

@hongxiaolong
期待回复哈。

[hongxiaolong]

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

我们还是继续来分析一下这段代码，或者说是公式。

以你说的rate=10000r/s，burst=1为例子：

0ms： excess = 0 - 10000000 * 1 / 1000 + 1000 = -9000

可以看到，我们得到的excess为一个很大的负数，而且在这里我们已经假设ms这个值很小为1的情况，实际情况会更大。

if ((ngx_uint_t) excess > limit->burst) {
    return NGX_BUSY;
}

上面这段代码，如果要条件成立，起码excess要超过0，这样的情况，起码

lr->excess这个队列中已经存在很多的请求，见

if (excess < 0) {
    excess = 0;
}

综上，各种条件其实还是满足限流算法的思想的：

首先，限流队列中已经有很多请求，且在这样的情况下，单位时间内还是超过了burst的上限，才会被限流。

wish to be helpful, thanks

[y123456yz]

@hongxiaolong
谢谢回复哈，你上面的
now = (ngx_msec_t) (tp->sec * 1000 + tp->msec);
ms = (ngx_msec_int_t) (now - lr->last);
如果在1ms内有很多请求过来，例如双11零点瞬间，可能1ms内就会有很多请求，假设我们放大一下，1ms内来了10000个请求，那么这10000个请求，两两之间的时间差计算是通过ms = (ngx_msec_int_t) (now - lr->last);得到，now的时间精度为ms，那么任意两个请求之间的时间差ms = (ngx_msec_int_t) (now - lr->last)，这样算下来ms=0。
第一个请求：excess = 0 - 10000000 * 1 / 1000 + 1000 = -900 if (excess < 0) { excess = 0; } 走到这里后会置0，也就是第一个请求后，excess=0
第二个请求：excess = 0- 10000000 * 0 / 1000 + 1000 = 1000
低三个请求：excess = 1000 - 10000000 * 0 / 1000 + 1000 = 2000
.........

这里的时间精度单位为ms，如果请求在1ms内全部过来，ms = (ngx_msec_int_t) (now - lr->last) = 0

上周四晚上我司做全链路压测，我专门搭了一套环境，配置rate=10000, burst=1, 压测情况下，放行的请求数为每秒1000左右，和我上面的分析一致，单我本来预期放行的请求数十10000左右。

@hongxiaolong
我觉得burst配置的有所限制，如果配置rata > 1000，则burst 必须大于rate/1000
或者ms = (ngx_msec_int_t) (now - lr->last) ，这里计算时间精度采用us级别，可能会更好。

[hongxiaolong]

@y123456yz 赞思路和测试

我觉得我们已经讨论了两个维度：

1、NGINX现在的限流算法是否合理；

NGINX的限流算法代码分析后，现在的限流算法是合理的，它的配置项rate、burst都很好地支持着流量的限流，符合预期，而且NGINX限流默认的时间维度是毫秒级，也就是说rate的指标换算成毫秒级的数量后，NGINX可以很精确地进行限流。

2、NGINX现在的限流算法是否可以优化，或者说符合更大流量的需求场景；

Linux的系统调用gettimeofday的时间维度是精确到微秒级的，NGINX是基于该系统调用来更新时间的：

void
ngx_time_update(void)
{
    ...

    ngx_gettimeofday(&tv);

    sec = tv.tv_sec;
    msec = tv.tv_usec / 1000;

    ...
}

可以看到，NGINX是在微秒级上再除以1000来得到其默认的时间维度毫秒级。

所以你的推算也是符合预期的，即在1毫秒内进来10000个请求，NGINX实际放过去的请求量是每毫秒burst=1，也就是每秒1000左右。

那么，如果我们把维度提升到微秒级，理论上NGINX可以提升限流性能上千倍，但是，我们来考虑另一个角度，我们限流的主要目的还是保持服务可用，NGINX的每个连接内存占用在1K左右，10万连接在1G左右，如果可以提升一千倍性能，短时间内连接数激增，内存占用会在百倍千倍量级去提升，现在的硬件条件估计无法满足，而且epoll在这种短时间内的性能下降估计也会很可观。

综上，一定程度上NGINX现有的限流算法会丧失一些精度，不知道当时NGINX作者在默认时间维度为毫秒时是否已经提前考虑到其它的综合情况，而且估计到了这个量级，可能一般公司更多会去注重总系统而不是单机的性能瓶颈，推荐你可以NGINX mailist里邮件问问，可以互相探讨学习~

多谢

[y123456yz]

@hongxiaolong
ngx_time_update()在高并发情况下，一般是通过epoll_wait 事件触发返回的，然后执行ngx_time_update()。只要这里能获取到us级别就行，系统调用次数应该是一样的，不管是获取ms级别还是us级别。

我觉得取us作为时间精度的话，突发流量会压到us时间段内，系统应该会处理不过来，应该就是你的分析，作者估计也会考虑到这个。

另外：
我觉得即使不调整时间精度，配置的时候只要burst大于rate / 1000，问题就可以解决。

就如上面我分析的，如配置rate=10000，burst=1，那么OK的请求数只能为1000左右，感觉这个是个bug。我觉得不调整时间精度，可以做如下修改，同样可以满足限速要求，并且每秒突发最多为burst:

法1：
if(limit->burst >=1 && limit->burst < ctx->rate / 1000)
limit->burst = ctx->rate / 1000;
if ((ngx_uint_t) excess > limit->burst) {
return NGX_BUSY;
}

法2：
或者在检查配置的时候做下限制，如果burst>1，并且rate / 1000 > burst，则直接报错。

如果可以解决，法2相对比较好。

抽空我发发邮件到nginx mailist，问下他们的想法。

[hongxiaolong]

@y123456yz

回去看了一眼NGINX对这两个配置项变量的注释，如下：

typedef struct {
    ngx_http_limit_req_shctx_t  *sh;
    ngx_slab_pool_t             *shpool;
    /* integer value, 1 corresponds to 0.001 r/s */
    ngx_uint_t                   rate;
    ngx_http_complex_value_t     key;
    ngx_http_limit_req_node_t   *node;
} ngx_http_limit_req_ctx_t;


typedef struct {
    ngx_shm_zone_t              *shm_zone;
    /* integer value, 1 corresponds to 0.001 r/s */
    ngx_uint_t                   burst;
    ngx_uint_t                   nodelay; /* unsigned  nodelay:1 */
} ngx_http_limit_req_limit_t;

感觉原作者可能想表达的是，在没有设置burst时rate在0.001r/s，如果设置了burst，那么burst优先生效，还是蛮符合漏桶的思想的。

当然，我感觉你的思路未尝也是一种不错的方案，我的如上阅读理解你可以参考，希望有所帮助。

多谢

[huifeidexingyuner]

@y123456yz
不明白，为什么要优化成微秒？
配置如下：
rate=10000, burst=1

假如：双11零点瞬间，1ms内来了10000个请求，发行请求每秒1000请求，没有问题，因为漏桶和令牌的消耗是成比例的，为什么会预期是几十万请求？

可以在nginx官网Report a Bug里讨论，用你的github账号登录。