d********w
发帖数: 363 | 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? |
c*****e
发帖数: 737 | 2 这玩意，好像就是用个timer call back func，没啥技术含量的。你也可以用个queue
来存放req。
交易系统也有类似的控制，比如每分钟某股票交易次数要小于某个值，代码我看过就是
这么干的。 |
c*****e
发帖数: 737 | 3 简单点，1秒钟reset一个counter，然后每个request increase这个count，如果count>
10k，那么就drop request。虽然不是很完美，但花街的系统检查股票交易频率就是这
么干的，用了快10年没人抱怨么。 |
d********w
发帖数: 363 | 4 还是不太确定，大牛能指点一下么
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。
: 交易系统也有类似的控制，比如每分钟某股票交易次数要小于某个值，代码我看过就是
: 这么干的。
|
c*****e
发帖数: 737 | 5 你那个效率太低了，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)
|
H***e
发帖数: 476 | 6 这样有个问题旧式，如果上一秒的后半秒来了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)
|
c*****e
发帖数: 737 | 7 是的呀，不过nobody cares。
【在 H***e 的大作中提到】
: 这样有个问题旧式，如果上一秒的后半秒来了10k,
: 然后这一秒的前半秒来了10k,这样也会通过的， 但是却在一秒内总共有20k..
|
H***e
发帖数: 476 | 8 面试官cares吧
【在 c*****e 的大作中提到】
: 是的呀，不过nobody cares。
|
d********w
发帖数: 363 | 9 你说的有道理，但怎么避免呢
【在 H***e 的大作中提到】
: 这样有个问题旧式，如果上一秒的后半秒来了10k,
: 然后这一秒的前半秒来了10k,这样也会通过的， 但是却在一秒内总共有20k..
|
s*****n
发帖数: 162 | 10 用queue/circular array记录每个request的timestamp。 |
|
|
c*****e
发帖数: 737 | 11 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吧
|
d********w
发帖数: 363 | 12 谢谢指点，确实是问道分布式了，一台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掉，然后把新的加进去。
|
z****u
发帖数: 104 | 13 如果所有的 reques t都通过 master，那可不可以把总的 request 次数存在 master？
由 master 来决定具体的操作是哪个 slave 来完成的。而对用户来说，这个系统是透
明的。
【在 d********w 的大作中提到】
: 谢谢指点，确实是问道分布式了，一台master，n台slaves，不是考虑1分钟，而是总体
: 判断是否超过阈值。我大致设想是client发到master请求，master去收集各台机器的数
: 据，可以并发的去做，有个全局变量，每个线程等待，只要当前求和大于那个阈值，立
: 即返回false，而最坏情况是等待所有的slave返回结果。
: 这个还是要写代码的，我都忘了当时怎么写的了。
|
H***e
发帖数: 476 | 14 感谢大牛。。
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掉，然后把新的加进去。
|
w****x
发帖数: 2483 | 15 你看能不能这样设计
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 |
w****x
发帖数: 2483 | 16
给个不精确的办法:
假设有10台机器, 允许的误差范围是1000个request.那个每台机器在收到90个request
后update一个public file. master机器每隔一段时间读取这个值 .....
【在 d********w 的大作中提到】
: 谢谢指点，确实是问道分布式了，一台master，n台slaves，不是考虑1分钟，而是总体
: 判断是否超过阈值。我大致设想是client发到master请求，master去收集各台机器的数
: 据，可以并发的去做，有个全局变量，每个线程等待，只要当前求和大于那个阈值，立
: 即返回false，而最坏情况是等待所有的slave返回结果。
: 这个还是要写代码的，我都忘了当时怎么写的了。
|
