dubbo的TPS限流模块在运行时系统时间发生变化的情况下限流不能正常工作

[edtenz]

• I have searched the issues of this repository and believe that this is not a duplicate.
• I have checked the FAQ of this repository and believe that this is not a duplicate.

Environment

• Dubbo version: 2.6.3

Step to reproduce this issue

1. 配置限流过滤器；
2. 运行时修改系统时间；
3. 时间差范围内的正常请求全部被拒；

原因描述

过滤器org.apache.dubbo.rpc.filter.TpsLimitFilter 通过调用 org.apache.dubbo.rpc.filter.tps.StatItem实现TPS限流。类org.apache.dubbo.rpc.filter.tps.StatItem实现了令牌桶算法，

https://github.com/apache/incubator-dubbo/blob/f720ccb965d490e6cc328af8d3e9820cb6eaf8f7/dubbo-rpc/dubbo-rpc-api/src/main/java/org/apache/dubbo/rpc/filter/tps/StatItem.java#L42-L46

上面的实现通过原子计数器token来记录可用令牌数量，在能取到令牌的情况下，每次调用对令牌数的自减。令牌桶重置（重新设置为最大值）的条件：当前系统时间 > 上次重置令牌的时间 + 时间间隔。

该实现对系统时间具有依赖性：
以rate=5000，interval=1000ms（即限流5000TPS），实际访问量为1000TPS为例，应用原来的时钟与标准时间同步，在运行过程中系统时钟发生了偏差（可能因为应用服务器同步了错误的NTP服务导致）：

• 当系统时钟比标准时间慢（假设慢15分钟），则从差错时间点开始，当前系统时间重新变回到了15分钟前，而上次令牌重置时间并不会马上发生变化，导致 lastResetTime > now （相差约15分钟），条件now > lastResetTime + interval 在接下来的15分钟之内不再满足。意味着5000个令牌在1000TPS的实际访问量情况下5秒钟即被用完后，后续的14分钟55秒的时间段内，所有的请求由于取不到令牌全部被拒，直到15分钟后满足令牌桶重置的条件，才能恢复业务。

• 当系统时间比标准时间快（假设快15分钟），当前系统时间和上次令牌桶重置时间的关系为： now > lastResetTime（相差约15分钟），此时满足令牌桶重置的条件，限流可以正常工作。但是，在系统时间恢复至标准时间时，lastResetTime会比标准时间提前约15分钟，这时同样会导致系统时间恢复的15分钟后续的请求全部被拒绝，直到15钟后满足令牌通重置的条件。

Expected Result

在运行时系统时间发生变化，限流仍能正常发挥作用。

Actual Result

运行过程中系统时间发生变化，导致限流不能正确执行，更严重的是在时间差范围内，请求会错误地全部被拒绝。

[xiaguangme]

可以采用“倒计时”的方式解决这个问题，每一次开始重置时，做一个interval时间的等待，等待结束后重置。这样就不依赖于系统时间了。有访问时启动等待，无访问时，无需启动等待。
另：

在运行过程中系统时钟发生了偏差（可能因为应用服务器同步了错误的NTP服务导致）

是您猜测的系统时间不对的原因。 也有那种测试时确实需要修改系统时间的，如银行的测试环境，会有针对某个特定过去日期测试，此时不能停服务。

[edtenz]

该限流算法的实现导致拒绝请求不是猜测，为真实地在生产环境中碰到的场景。
修复如下：

class StatItem {

	private String name;
	private long interval;
	private int rate;
	private final AtomicInteger token;
	private final ScheduledExecutorService scheduler;

	public StatItem(String name, int rate, long interval) {
		this.name = name;
		this.rate = rate;
		this.interval = interval;
		this.token = new AtomicInteger(rate);
		this.scheduler = Executors
				.newSingleThreadScheduledExecutor(new NamedThreadFactory("token-schedule"));
		this.scheduler.scheduleAtFixedRate(() -> {
			resetToken(this.rate);
		}, 0, this.interval, TimeUnit.MILLISECONDS);

	}

	private void resetToken(int rate) {
		this.token.set(rate);
	}

	public boolean isAllowable() {
		return token.decrementAndGet() >= 0;
	}

}

修复：采用一个异步线程定期（interval间隔）去重置令牌桶，而不再依赖于系统时间。但增加了一个线程的开销。

[hupuxiaojun]

@EdgarTeng 这种方式好像也是有问题的，限流的时间窗口是一个滑动(sliding window)窗口(最近60秒)，不是一个翻滚（Tumbling window）窗口（0-60,60-120）。
假设interval=60,rate=5000
你这个线程是固定周期重置，极端情况下，59秒的时候，进来4999个请求，都放行了，然后第60秒，你重置了rate，然后第61秒又进来4999个请求，这时候由于已经重置，所以这4999个请求仍然可以通行。
结果就是你的服务在3秒内就收到了4999*2个请求，远大于你设置的1分钟5000的rate。

[imloki]

滑动窗口来限流天然就存在毛刺的问题，可以扩展漏桶或者令牌桶来做~~

[xiaguangme]

@EdgarTeng 其实我搜了下 除了限流依赖系统时间之外，还有好多地方都依赖系统时间，比如一些dump日志的地方，但或许多业务影响不大吧

[edtenz]

@hupuxiaojun 上面的修复通过调度去定期重置令牌桶，确实存在不是任意时间窗口请求量都是设定的值的问题，会存在毛刺。其实dubbo本身的令牌桶实现也同样存在这样的毛刺。

假设interval=60s,rate=5000

意味着1分钟最多能接受5000次请求。假设在10:00:00时刻令牌桶被重置了（即lastResetTime=10:00:00.000），根据if (now > lastResetTime + interval) 的条件，最早需要在10:01:00.001时刻令牌桶才被重新重置（“最早”是因为重置令牌为有请求进来且满足时间条件，被动策略），在极端情况，在10:00:01 ~ 10:00:59这段时间没有请求，在第59秒有4999个请求，然后第60秒又1毫秒接受了一个新的请求 由于满足了： 当前系统时间 > 上次重置时间 + 时间间隔 被重置了rate，然后第61秒又进来4999个请求，那么在10:00:59 ~ 10:01:02这3秒收到了4999*2个请求，也是远大于设定的5000。

因此，对令牌桶算法的实现，无论是dubbo自己的实现方式还是通过调度的方式，并不能保证任意时间窗口处理的请求数是设定的值。因为令牌桶算法的特点之一是允许某种程度的突发传输，如果要实现任意1秒内限制5000请求，一是可以通过设定interval=500ms，rate=2500，这样可以准确地保证任意2个interval之内，能够处理的总量最大是2*rate；二是采用漏桶算法，该算法可以实现处理请求速率的均匀。

[edtenz]

@xiaguangme 由于很多应用系统（或中间件）都会使用系统时间这一属性作为控制条件，系统时间的准确性差不多是很多软件系统能够正确运行的基本前提，这也是准确NTP服务非常非常的重要原因。至于系统时间的偏差对业务造成的影响有多大，需要根据不同的业务场景来做评判。如果是记录应用日志，有几分钟的时间偏差，在大部分情况下还是属于可接受范围之内吧。像限流这样的场景，如果因系统时间偏差而拒绝了所有的正常交易，是难以接受的。（难以接受的场景还包括：在做请求有效性验证时，以当前系统时间和客户端发送过来的时间戳进行对比，如果偏差大于某一阈值，则验证不通过）。因此，对系统时间的依赖可能也是在做算法和软件设计时需要考虑的。

[edtenz]

一种对源码修改更小的方式：

 long now = System.currentTimeMillis(); 
 if (Math.abs(now - lastResetTime) > interval) { 
     token.set(rate); 
     lastResetTime = now; 
 } 

修改后，令牌桶的重置条件：当前系统时间 与 上次重置时间的偏差 > 时间间隔。

[hupuxiaojun]

@EdgarTeng 所以你可能陷入了一个思维怪圈，一直在纠结这个时间问题，我想阿里为什么没有考虑这个问题？是因为时间同步是运维标准化的东西，你举的极端案例，时间同步差了那么多。。。
问题是出在时间同步上，是运维的锅，把自身运维做好就能避免这个问题。
当然dubbo自身实现也不完美，所以这个Filter都没放在默认扩展里面.
或许可以采用guava的RateLimiter实现单实例限流。如果要全局限流，可以通过RateLimiter的Redis实现(springboot2里面有)

[edtenz]

@hupuxiaojun 嗯，谢谢，您后面给的建议很中肯。确实，系统时间是一个基本的服务，如果时间都错了，很多服务都不能正常运转。当然，至于阿里有没有想到这个问题我不能冒昧揣测，只能说很多情况下软件的容错性是需要考虑的（常见的像是硬盘故障、内存故障、网络闪断等），并不能完全说是运维的锅，真的出现极端的场景，软件设计如果考虑到这些情况，即便不能完全的解决问题，能尽量减少黑天鹅带来的损失，并具有相应的兜底方案，对于可用率要求很高的系统，这种努力也是值得的。

[carryxyh]

Hi,
I will close this issue. Reopen it if there are still some problems with it.