l****o
发帖数: 135 | 1 设计一个类来限制query，如1000qps，或者说每秒钟只能发10封邮件
给定的API，now()返回当前milliseconds
实现类的函数allowRequest()，如果当前还有request剩余true,否则返回false |
q********c
发帖数: 1774 | 2 类似于rate limiter吗？试了下：
boolean allowRequest() {
int minInterval = 1000/N; // N is the max rate
int current = now();
int diff = current-last;
last = current; //last would be a class private member
if(diff < minInterval)
return false;
else
return true;
} |
l*****a
发帖数: 14598 | 3 牛，先晒offer吧
这种晒一堆面经的最后都有大offer压阵
【在 l****o 的大作中提到】
: 设计一个类来限制query，如1000qps，或者说每秒钟只能发10封邮件
: 给定的API，now()返回当前milliseconds
: 实现类的函数allowRequest()，如果当前还有request剩余true,否则返回false
|
l*********8
发帖数: 4642 | 4 每秒钟十次，不等于每100毫秒一次吧？
【在 q********c 的大作中提到】
: 类似于rate limiter吗？试了下：
: boolean allowRequest() {
: int minInterval = 1000/N; // N is the max rate
:
: int current = now();
: int diff = current-last;
: last = current; //last would be a class private member
: if(diff < minInterval)
: return false;
: else
|
q********c
发帖数: 1774 | 5 每秒钟十次是指rate吧，比如10rqs/sec,是速度的概念，不是次数。
【在 l*********8 的大作中提到】
: 每秒钟十次，不等于每100毫秒一次吧？
|
p***y
发帖数: 637 | 6 有点模糊
如果在23：00：00.000-23：00：00.500之间没有请求， 23:00:00.500和23：00：01.
000之间来了1000个请求，23:00:01.000和23：00：01.500之间又来了1000个请求，随
后的半秒内无请求。那么算1000qps还是算2000qps?
按整秒算，正好1000qps. 如果把采样区间放到00.500 - 01.500之间，是2000qps.
如果固定1秒周期采样，比较容易实现。如果要求没有特定采样周期，感觉很复杂，只
能搞非常短的周期，算法很复杂。
【在 l****o 的大作中提到】
: 设计一个类来限制query，如1000qps，或者说每秒钟只能发10封邮件
: 给定的API，now()返回当前milliseconds
: 实现类的函数allowRequest()，如果当前还有request剩余true,否则返回false
|
p***y
发帖数: 637 | 7 好办法，我还真没想到。
不过实现细节上问题挺多
1000是magic number,而且这个数字有点随意。
另外1000/N会有误差。例如：N>1000时候minInterval ==0.
此外每次调用都计算除法造成冗余。
另外now()返回int，这个int值是什么含义，assume int是多少位的整数，最好加个注
解说明。一般认为int是32位有符号整数，如果那样的话，int的最大值用在这里有点力
不从心。当然你可以假定int是64位的。
最后就是是否允许突发，像一整秒基本没请求，但中间有100毫秒一下来了1000个，这
个算法会全部过滤掉（因为两两请求的间隔极小），如果允许突发则应该都放进来。
【在 q********c 的大作中提到】
: 类似于rate limiter吗？试了下：
: boolean allowRequest() {
: int minInterval = 1000/N; // N is the max rate
:
: int current = now();
: int diff = current-last;
: last = current; //last would be a class private member
: if(diff < minInterval)
: return false;
: else
|
p***y
发帖数: 637 | 8 这个需要clarify
是1秒里最多10个，还是瞬时的rate折合为10rps.
【在 q********c 的大作中提到】
: 每秒钟十次是指rate吧，比如10rqs/sec,是速度的概念，不是次数。
|
m*****k
发帖数: 731 | 9 class QueryLimiter{
private long started = 0;
private int count = 0;
private int maxRate ;
public QueryLimiter(int m){
maxRate = m;
}
public boolean allowRequest(){
long now = SomeAPI.now();
if(now - started > 1000 //1sec ){
started = now;
count = 0;
}
return count
}
public void query(Object param){
count++;
//. ...query/email,whatever...
}
}
assuming this class is used in single thread scenario, and called like this:
QueryLimiter ql = new QueryLimiter(1000);
if(ql.allowRequest()){
ql.query(...);
} |
m******s
发帖数: 1469 | 10 Zan
【在 l****o 的大作中提到】
: 设计一个类来限制query，如1000qps，或者说每秒钟只能发10封邮件
: 给定的API，now()返回当前milliseconds
: 实现类的函数allowRequest()，如果当前还有request剩余true,否则返回false
|
