a**d
发帖数: 85 | 1 之前面的一个题，现在又重新看了一下。之前有大神说用network的leaky bucket.试着
写了一个简单的，这样合理吗？
interface RateLimit {
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
boolean allowThisRequest();
}
brief example:
server instantiates your object, calls setQPS(1)
at at time t, user1 makes a request, allowThisRequest() returns true
at time t+0.01 sec, user2 makes a request, allowThisRequest() returns false
at at time t+1, user4 makes a request, allowThisRequest() returns true
at time t+5 sec, user3 makes a request, allowThisRequest() returns true
For 1. This is my solution:
class R implements RateLimit {
long previous_time;
int previous_count;
int qps;
void setQPS(int qps) {
this.qps = qps;
}
boolean allowThisRequest() {
if (qps <= 0) return false;
long now = System.currentTimeMillis();
if (now - previous_time < 1000) {
if (previous_count == qps)
return false;
else {
previous_time = now;
previous_count += 1;
return true;
}
}
else {
previous_time = now;
previous_count = 1;
return true;
}
}
}
Is this reasonable? Also, if for supporting multi-thread request, is it ok
to just add 'synchronized' for the allowThisRequest()?
Thx a lot. | s*w
发帖数: 729 | 2 显然是错了，没有把过期的count给减掉
比如 qps rate 是２ per second, 你的query 发生在 0.1, 0.9, 1.2 秒, 都应该接
受；你的程序会 reject 第三个， 以为 count=2
【在 a**d 的大作中提到】
: 之前面的一个题，现在又重新看了一下。之前有大神说用network的leaky bucket.试着
: 写了一个简单的，这样合理吗？
: interface RateLimit {
: /** Sets the rate, from 1 to 1000000 queries per second */
: void setQPS(int qps);
: /** accept or reject a request, called when request is received */
: boolean allowThisRequest();
: }
: brief example:
: server instantiates your object, calls setQPS(1)
| a**d
发帖数: 85 | 3 谢谢。
用一个list去保存之前的Node(field:time, count),然后如果当前时间比list最后一个
大于1秒，把list清空，把当前加入。
如果小于1秒，从头开始过一遍list，把Node.time和当前时间差别大于1的remove掉，
然后记录remove了多少个，然后把后面不要remove的Node.count相应减去过期的时间个
数。
【在 s*w 的大作中提到】
: 显然是错了，没有把过期的count给减掉
: 比如 qps rate 是２ per second, 你的query 发生在 0.1, 0.9, 1.2 秒, 都应该接
: 受；你的程序会 reject 第三个， 以为 count=2
|
|
