logo
Redian新闻
>未名空间
>EB23 - 劳工卡
>
TSC的服务器表忘记偶啊。。。。
avatar
TSC的服务器表忘记偶啊。。。。# EB23 - 劳工卡
d*w
1 楼
Implement rate limiting for an API so that we rate limit if the same
developer makes > 10K req/sec. What would the logic be? What would the
structure be? Where would you store this structure?
avatar
s*y
2 楼
难道要天天T2请安
天天上版问会不会没有名额了
攒人品和吓唬老天的路线，用哪个？纠结了。。。
avatar
c*e
3 楼
这玩意，好像就是用个timer call back func，没啥技术含量的。你也可以用个queue
来存放req。
交易系统也有类似的控制，比如每分钟某股票交易次数要小于某个值，代码我看过就是
这么干的。
avatar
l*n
4 楼
打T2吧。 免得在版上引起公愤
avatar
c*e
5 楼
简单点，1秒钟reset一个counter，然后每个request increase这个count，如果count>
10k，那么就drop request。虽然不是很完美，但花街的系统检查股票交易频率就是这
么干的，用了快10年没人抱怨么。
avatar
s*2
6 楼
攒人品吧，bless楼主分分钟绿！tsc很快的
avatar
d*w
7 楼
还是不太确定，大牛能指点一下么
cur_second = get_seconds_from_now(cur_time)
boolean checkTraffic(int developId) {
if (map.containsKay(developId))
last_time, last_count = map.get(developId)
if last_time != cur_time:
map.put(developId, new pair)
else {
last_count++;
if (last_count > 10K)
return false;
map.put(developId, new pair)
}
return true;
}

queue

【在 c*****e 的大作中提到】
: 这玩意，好像就是用个timer call back func，没啥技术含量的。你也可以用个queue
: 来存放req。
: 交易系统也有类似的控制，比如每分钟某股票交易次数要小于某个值，代码我看过就是
: 这么干的。
avatar
s*y
8 楼
那我可以在版上自问自答，把Q&A都遍历一遍么？

【在 l*******n 的大作中提到】
: 打T2吧。 免得在版上引起公愤
avatar
c*e
9 楼
你那个效率太低了，handleRequest要快要简单。
开一个线程，每秒reset那个count，可能不需要加锁。
bool handleRequest(int id)
{
// some readers lock here
return map[id] <= 10000;
}

【在 d********w 的大作中提到】
: 还是不太确定，大牛能指点一下么
: cur_second = get_seconds_from_now(cur_time)
: boolean checkTraffic(int developId) {
: if (map.containsKay(developId))
: last_time, last_count = map.get(developId)
: if last_time != cur_time:
: map.put(developId, new pair)
: else {
: last_count++;
: if (last_count > 10K)
avatar
H*e
10 楼
这样有个问题旧式，如果上一秒的后半秒来了10k,
然后这一秒的前半秒来了10k,这样也会通过的， 但是却在一秒内总共有20k..

【在 d********w 的大作中提到】
: 还是不太确定，大牛能指点一下么
: cur_second = get_seconds_from_now(cur_time)
: boolean checkTraffic(int developId) {
: if (map.containsKay(developId))
: last_time, last_count = map.get(developId)
: if last_time != cur_time:
: map.put(developId, new pair)
: else {
: last_count++;
: if (last_count > 10K)
avatar
c*e
11 楼
是的呀，不过nobody cares。

【在 H***e 的大作中提到】
: 这样有个问题旧式，如果上一秒的后半秒来了10k,
: 然后这一秒的前半秒来了10k,这样也会通过的， 但是却在一秒内总共有20k..
avatar
H*e
12 楼
面试官cares吧

【在 c*****e 的大作中提到】
: 是的呀，不过nobody cares。
avatar
d*w
13 楼
你说的有道理，但怎么避免呢

【在 H***e 的大作中提到】
: 这样有个问题旧式，如果上一秒的后半秒来了10k,
: 然后这一秒的前半秒来了10k,这样也会通过的， 但是却在一秒内总共有20k..
avatar
s*n
14 楼
用queue/circular array记录每个request的timestamp。
avatar
c*e
15 楼
1s要10k个数量级的request，那么差不多1个request要在100 microseconds以下处理完
，你用list啊，queue啊，每次处理都要去truncate那些过期的request，还要存入新的
request，还是很慢的。
类似的东西stock exchange也有，叫market impact，检查1秒钟内交易的频次，就是用
个timer call back做的。
当然如果要求不是1秒钟，而是检查1个小时内的request数量，那么你可以搞个list或
者queue，每次handle的时候把container里的request清理一遍。举个例里，阿三的证
券交易所有这个要求，某一小时内某股票的交易数量不能超过X。那么做法就是把(
timestamp, request)存放到一个list里，每次handleRequest的时候，先检查list里有
没有1小时以前的，把那些remove掉，然后把新的加进去。
这个问题还可以扩展一下，假设server是分布式的有很多个，要求用户某段时间内发给
所有server的request在某个limit下面，该怎么做？你可以把这个问题扔给g公司的面
试馆，保证可以烤焦他。

【在 H***e 的大作中提到】
: 面试官cares吧
avatar
d*w
16 楼
谢谢指点，确实是问道分布式了，一台master，n台slaves，不是考虑1分钟，而是总体
判断是否超过阈值。我大致设想是client发到master请求，master去收集各台机器的数
据，可以并发的去做，有个全局变量，每个线程等待，只要当前求和大于那个阈值，立
即返回false，而最坏情况是等待所有的slave返回结果。
这个还是要写代码的，我都忘了当时怎么写的了。

【在 c*****e 的大作中提到】
: 1s要10k个数量级的request，那么差不多1个request要在100 microseconds以下处理完
: ，你用list啊，queue啊，每次处理都要去truncate那些过期的request，还要存入新的
: request，还是很慢的。
: 类似的东西stock exchange也有，叫market impact，检查1秒钟内交易的频次，就是用
: 个timer call back做的。
: 当然如果要求不是1秒钟，而是检查1个小时内的request数量，那么你可以搞个list或
: 者queue，每次handle的时候把container里的request清理一遍。举个例里，阿三的证
: 券交易所有这个要求，某一小时内某股票的交易数量不能超过X。那么做法就是把(
: timestamp, request)存放到一个list里，每次handleRequest的时候，先检查list里有
: 没有1小时以前的，把那些remove掉，然后把新的加进去。
avatar
z*u
17 楼
如果所有的 reques t都通过 master，那可不可以把总的 request 次数存在 master？
由 master 来决定具体的操作是哪个 slave 来完成的。而对用户来说，这个系统是透
明的。

【在 d********w 的大作中提到】
: 谢谢指点，确实是问道分布式了，一台master，n台slaves，不是考虑1分钟，而是总体
: 判断是否超过阈值。我大致设想是client发到master请求，master去收集各台机器的数
: 据，可以并发的去做，有个全局变量，每个线程等待，只要当前求和大于那个阈值，立
: 即返回false，而最坏情况是等待所有的slave返回结果。
: 这个还是要写代码的，我都忘了当时怎么写的了。
avatar
H*e
18 楼
感谢大牛。。
timer call back
这是什么啊？找了半天没找着。。。

【在 c*****e 的大作中提到】
: 1s要10k个数量级的request，那么差不多1个request要在100 microseconds以下处理完
: ，你用list啊，queue啊，每次处理都要去truncate那些过期的request，还要存入新的
: request，还是很慢的。
: 类似的东西stock exchange也有，叫market impact，检查1秒钟内交易的频次，就是用
: 个timer call back做的。
: 当然如果要求不是1秒钟，而是检查1个小时内的request数量，那么你可以搞个list或
: 者queue，每次handle的时候把container里的request清理一遍。举个例里，阿三的证
: 券交易所有这个要求，某一小时内某股票的交易数量不能超过X。那么做法就是把(
: timestamp, request)存放到一个list里，每次handleRequest的时候，先检查list里有
: 没有1小时以前的，把那些remove掉，然后把新的加进去。
avatar
w*x
19 楼
你看能不能这样设计
bool FreqControl(TIME_SLOT_DEQUE& tsDeque);
TIME_SLOT_DEQUE 是一个双端队列, 就是说把一秒的时间按需要切分成许多个time
slot, 每一个time slot做为一个element存储在双端队列里,一个time solt对应一个
number, 就是在那个time slot里call这个api的次数.
每次我call这个API一次:
1. 从双端队列队头开始扫描, 移除一秒以前的time slot
2. 新增一个time slot节点或update最后一个time slot节点的call api number
3. 一直maintain一个total number.
4. return total number <= limit
avatar
w*x
20 楼

给个不精确的办法:
假设有10台机器, 允许的误差范围是1000个request.那个每台机器在收到90个request
后update一个public file. master机器每隔一段时间读取这个值 .....

【在 d********w 的大作中提到】
: 谢谢指点，确实是问道分布式了，一台master，n台slaves，不是考虑1分钟，而是总体
: 判断是否超过阈值。我大致设想是client发到master请求，master去收集各台机器的数
: 据，可以并发的去做，有个全局变量，每个线程等待，只要当前求和大于那个阈值，立
: 即返回false，而最坏情况是等待所有的slave返回结果。
: 这个还是要写代码的，我都忘了当时怎么写的了。
相关阅读
485的RFE USCIS online通知否？最好的情况其实是一点点进！拿到卡了，原来的I94还要留吗？到现在还没出来呢，孟买的绿印印PD1/25/2008H1b renew以后能申请办理代签么？我这种情况如何操作啊？ (转载)又多出一个E-2法案专门给以色列人族裔的。。。关于结婚，waiver，申绿卡等的时间问题 (转载)昨晚求的大家的祝福。今天就绿了。EB3 散尽家财求祝福。weird 485 interviewXXSL....FP --律师的回答。。真头大！！借noles 的佛面春风，绿了(TSC) UPDATE：包子发完了。这Demand Data完全搞笑呀急，怎么发包子，从来没发过重庆官方：王立军正在休假式治疗为啥这个页面还是“coming soon”？ead/ap 批注了，但是fingerprint还没有被约看来是10年后人不大多了
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。