r*******h 发帖数: 315 | 1 要求设计一个Rate Limiter。突然想起来了,供大家讨论一下吧。 |
p*****p 发帖数: 379 | 2 这就没了?
流量是多少
ip/cookie/session based?
服务器架构是怎么样的?
这东西准备放在哪里?
有些什么现成的东西(memcached/redis...)?
【在 r*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要求设计一个Rate Limiter。突然想起来了,供大家讨论一下吧。
|
p*****2 发帖数: 21240 | 3 大牛说说一般怎么设计
【在 p*****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这就没了? : 流量是多少 : ip/cookie/session based? : 服务器架构是怎么样的? : 这东西准备放在哪里? : 有些什么现成的东西(memcached/redis...)?
|
m********t 发帖数: 13072 | 4 不是大牛,随便说两句
rate limiter,不管是哪里的,都围绕一个核心,就是limiter
数据结构上,必须设置threshold
功能上,必须设置flow control和traffic management,prevent traffic jam
还有相关的设置,比如monitoring,time interval
既然是limiter,你要guarantee每时每刻进行纠错处理,比如amount突然增加,就可以
进行routine alerts
而不能等到已经overly,才开始修复,那样效率在平均每秒上大大减低
所以,还要有个efficiency estimation和experimental的instant dual data
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛说说一般怎么设计
|
p*****2 发帖数: 21240 | 5 你说的更像是需求
具体应该怎么设计呢?
比如你提到数据结构 但是到底应该用什么数据结构呢
【在 m********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是大牛,随便说两句 : rate limiter,不管是哪里的,都围绕一个核心,就是limiter : 数据结构上,必须设置threshold : 功能上,必须设置flow control和traffic management,prevent traffic jam : 还有相关的设置,比如monitoring,time interval : 既然是limiter,你要guarantee每时每刻进行纠错处理,比如amount突然增加,就可以 : 进行routine alerts : 而不能等到已经overly,才开始修复,那样效率在平均每秒上大大减低 : 所以,还要有个efficiency estimation和experimental的instant dual data
|
m********t 发帖数: 13072 | 6 所以 最初的prototype的functions大概建立如下:
核心是prevent reaching to limit:
alerts
maintenance
monitoring
efficiency
flow detection
flow control
instant repair
threshold detection
其他相关的数据结构围绕相应的数据采集,就很好设置了
这只是我眼下能想得到的,估计也不是很对。。。 |
q********c 发帖数: 1774 | 7 这是我的口德. 基本原理就这样,再讨论一下scalability, concurrency, 就差不多了。
void RateLimit() {
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) {
Thread.sleep(diff);
return ;
}
else
return ;
}
【在 r*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要求设计一个Rate Limiter。突然想起来了,供大家讨论一下吧。
|
p*****2 发帖数: 21240 | 8 你这个貌似跟月光是两个极端呀
了。
【在 q********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我的口德. 基本原理就这样,再讨论一下scalability, concurrency, 就差不多了。 : void RateLimit() { : 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) { : Thread.sleep(diff); : return ;
|
m********t 发帖数: 13072 | 9 这么简单? 我考虑问题总是前前后后都想个遍。。。
凭我直觉,面试的出发点是考量你的设计思路和循序渐进的一个逻辑过程
我甚至都不认为coding在这里算是重点了
project最开始的核心定位和相应参数的设置,极为关键,这个跟盖楼打地基是一样的
crucial
一开始没定位好地基的模型,后来的人没法跟,也就是上面的floors就很难reliable打
下去了
会出现半途而废,然后重头开始的低效
不过,可能你是对的,我也就是瞎说自己的感觉
了。
【在 q********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我的口德. 基本原理就这样,再讨论一下scalability, concurrency, 就差不多了。 : void RateLimit() { : 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) { : Thread.sleep(diff); : return ;
|
m********t 发帖数: 13072 | 10 他可能是高手吧,我倒是什么都不懂,也许真是他对的
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个貌似跟月光是两个极端呀 : : 了。
|
|
|
p*****2 发帖数: 21240 | 11 先写code再谈scalability 肯定有问题
scale不同设计会大不一样
【在 m********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这么简单? 我考虑问题总是前前后后都想个遍。。。 : 凭我直觉,面试的出发点是考量你的设计思路和循序渐进的一个逻辑过程 : 我甚至都不认为coding在这里算是重点了 : project最开始的核心定位和相应参数的设置,极为关键,这个跟盖楼打地基是一样的 : crucial : 一开始没定位好地基的模型,后来的人没法跟,也就是上面的floors就很难reliable打 : 下去了 : 会出现半途而废,然后重头开始的低效 : 不过,可能你是对的,我也就是瞎说自己的感觉 :
|
q********c 发帖数: 1774 | 12 我这是基本原理,限制rate, 就看相邻两个request之间时间间隔,如果小于最小间隔
,就sleep, 就这样。月光堆一堆名词,看不懂。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个貌似跟月光是两个极端呀 : : 了。
|
m********t 发帖数: 13072 | 13 我想问题,经常复杂化,可能你是对的,面试官可能需要这种简单而直接的solution
【在 q********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我这是基本原理,限制rate, 就看相邻两个request之间时间间隔,如果小于最小间隔 : ,就sleep, 就这样。月光堆一堆名词,看不懂。
|
p*****2 发帖数: 21240 | 14 大牛还是继续吧
你现在还处在pm阶段
下一步怎么做呢?
【在 m********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想问题,经常复杂化,可能你是对的,面试官可能需要这种简单而直接的solution
|
N*****m 发帖数: 42603 | 15 这题说得不清楚,没法设计
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛还是继续吧 : 你现在还处在pm阶段 : 下一步怎么做呢?
|
p*****2 发帖数: 21240 | 16 月光已经说的够多得了吧
【在 N*****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题说得不清楚,没法设计
|
N*****m 发帖数: 42603 | 17 单就一个rate就没说清楚
一个机器的rate,一个系统的rate,一个account跨区的rate;
再说什么rate?流量,CPU,内存还是硬盘?
然后怎么limit?hard limit还是soft?
任何一个组合就是一种solution,这个题目啥都没说,设计个头。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 月光已经说的够多得了吧
|
m********t 发帖数: 13072 | 18 现在,眼下这个时代,rate limit都要走load balancing路线,只不过方法不同,要么
并行多几条virtual lanes,要么是按时间去做queuing, 只有这样才可以避免各种
collision的发生,这只是理想状态,而真实状态,这样也还出现很多故障。
你就把这道题当成高速上的limit去考虑就行了,真到了塞车或撞车的时候,已经太晚
了,人均的前进效率也就是流量其实是很低的, 所以提前的各项措施,很有必要
这个题目我估计是跟google cloud data center的资源分布有点关系。
瞎猜的啊,不一定对
【在 N*****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 单就一个rate就没说清楚 : 一个机器的rate,一个系统的rate,一个account跨区的rate; : 再说什么rate?流量,CPU,内存还是硬盘? : 然后怎么limit?hard limit还是soft? : 任何一个组合就是一种solution,这个题目啥都没说,设计个头。
|
m********t 发帖数: 13072 | 19 这种设计需要很多细节部分,仔细想一想,包括相关的参数和变量,
我上午要给一个tech talk, 还要复查一下ppt
晚点才能有空了
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛还是继续吧 : 你现在还处在pm阶段 : 下一步怎么做呢?
|
r*******h 发帖数: 315 | 20 抱歉,之前是临时想起来就贴上了。当时先是讨论了一个一般性的模型,后来要求
coding一个method based,就是怎么控制一定时间内对一个method或者function的调用数
【在 p*****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这就没了? : 流量是多少 : ip/cookie/session based? : 服务器架构是怎么样的? : 这东西准备放在哪里? : 有些什么现成的东西(memcached/redis...)?
|
|
|
y**********a 发帖数: 824 | 21 我在 Guava 里面找到了一个叫 Ratelimiter 的类。
干的是类似 lock 的事情。有点像 Semaphore,不过不是控制 Thread 的数量,
而是控制一段时间里面的流量。 |
m********t 发帖数: 13072 | 22 你还真的去找外面资料了?这里的题目,我从来没翻过书或者google过
既然是面试题目,这个前提就是你不能在现场找书和找笔记了吧?
我是根据自己对rate和limit的应用的理解来回答的,错了也没关系了
问题是,这道题你能找到,再给一道你没见过的,比如写一个电表监视的系统,那不还
是不会吗?
其实,面试是考察你的思维效率,这东西是平时长期潜移默化的training,不是一夜之
间就突飞猛进的
【在 y**********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我在 Guava 里面找到了一个叫 Ratelimiter 的类。 : 干的是类似 lock 的事情。有点像 Semaphore,不过不是控制 Thread 的数量, : 而是控制一段时间里面的流量。
|
p*****2 发帖数: 21240 | 23
用数
是什么method?
【在 r*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 抱歉,之前是临时想起来就贴上了。当时先是讨论了一个一般性的模型,后来要求 : coding一个method based,就是怎么控制一定时间内对一个method或者function的调用数
|
p***y 发帖数: 637 | 24 用sleep不妥
了。
"" ;="" :="" ...................="">
【在 q********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我的口德. 基本原理就这样,再讨论一下scalability, concurrency, 就差不多了。 : void RateLimit() { : 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) { : Thread.sleep(diff); : return ;
|
p***y 发帖数: 637 | 25 貌似多了很多assumptions
【在 m********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是大牛,随便说两句 : rate limiter,不管是哪里的,都围绕一个核心,就是limiter : 数据结构上,必须设置threshold : 功能上,必须设置flow control和traffic management,prevent traffic jam : 还有相关的设置,比如monitoring,time interval : 既然是limiter,你要guarantee每时每刻进行纠错处理,比如amount突然增加,就可以 : 进行routine alerts : 而不能等到已经overly,才开始修复,那样效率在平均每秒上大大减低 : 所以,还要有个efficiency estimation和experimental的instant dual data
|
r*******h 发帖数: 315 | 26 任意一个供外部调用的方法或者函数,比如打包成web services的
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 用数 : 是什么method?
|
p*****2 发帖数: 21240 | 27 那不考虑scale吗
【在 r*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任意一个供外部调用的方法或者函数,比如打包成web services的
|
m*****k 发帖数: 731 | 28 Thread.sleep(minInterval - diff); 吧?
了。
【在 q********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我的口德. 基本原理就这样,再讨论一下scalability, concurrency, 就差不多了。 : void RateLimit() { : 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) { : Thread.sleep(diff); : return ;
|
C*******n 发帖数: 193 | 29 看了看
是sleep处理的。
概念上不难 挺清晰的。
【在 y**********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我在 Guava 里面找到了一个叫 Ratelimiter 的类。 : 干的是类似 lock 的事情。有点像 Semaphore,不过不是控制 Thread 的数量, : 而是控制一段时间里面的流量。
|
p*****2 发帖数: 21240 | 30 sleep是线程阻塞的吧 除非用go
【在 C*******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看了看 : 是sleep处理的。 : 概念上不难 挺清晰的。
|
|
|
C*******n 发帖数: 193 | 31 public double acquire()
Acquires a single permit from this RateLimiter, blocking until the request
can be granted. Tells the amount of time slept, if any.
This method is equivalent to acquire(1).
Returns:
time spent sleeping to enforce rate, in seconds; 0.0 if not rate-limited
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : sleep是线程阻塞的吧 除非用go
|
p*****2 发帖数: 21240 | 32 并发性太差了
limited
【在 C*******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : public double acquire() : Acquires a single permit from this RateLimiter, blocking until the request : can be granted. Tells the amount of time slept, if any. : This method is equivalent to acquire(1). : Returns: : time spent sleeping to enforce rate, in seconds; 0.0 if not rate-limited
|
g**e 发帖数: 6127 | 33 SOA下就直接扔异常啦 常见的rate limiter要先决定支不支持burst,throttle limit
和recover limit经常是不同的
这个题很好,回去翻一下AWS API throttling是咋设计的再来分享
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 并发性太差了 : : limited
|
p*****2 发帖数: 21240 | 34 好 多谢大牛
limit
【在 g**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : SOA下就直接扔异常啦 常见的rate limiter要先决定支不支持burst,throttle limit : 和recover limit经常是不同的 : 这个题很好,回去翻一下AWS API throttling是咋设计的再来分享
|
p***y 发帖数: 637 | 35 用sleep就不用谈scale了
【在 C*******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看了看 : 是sleep处理的。 : 概念上不难 挺清晰的。
|
M*******a 发帖数: 1633 | 36 仅仅限制间隔时间应该太简化了
应该是要考虑burst的情况的。
感觉这个题目更哪个什么过去一分钟一小时一天的request数量的题目有关系。
就是给定一段固定的时间控制这段时间里面最大可能的request数量。
如果要精确解就要保持一个request queue,不要精确解就把固定一段时间分成比如100
份记录每份时间里面的request数量。 |
p***y 发帖数: 637 | 37 好像有好几个贴子讨论这个问题了。奇怪。
100
【在 M*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 仅仅限制间隔时间应该太简化了 : 应该是要考虑burst的情况的。 : 感觉这个题目更哪个什么过去一分钟一小时一天的request数量的题目有关系。 : 就是给定一段固定的时间控制这段时间里面最大可能的request数量。 : 如果要精确解就要保持一个request queue,不要精确解就把固定一段时间分成比如100 : 份记录每份时间里面的request数量。
|
g**e 发帖数: 6127 | 38 终极答案 http://en.wikipedia.org/wiki/Token_bucket
AWS不同的产品throttling的实现有差别,不过基本都是基于上面这个。所以说,本科
学的网络通信还是有用的啊...
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好 多谢大牛 : : limit
|
p*****2 发帖数: 21240 | 39 先顶后看
【在 g**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 终极答案 http://en.wikipedia.org/wiki/Token_bucket : AWS不同的产品throttling的实现有差别,不过基本都是基于上面这个。所以说,本科 : 学的网络通信还是有用的啊...
|
g**e 发帖数: 6127 | 40 Andrew Tanenbaum的Computer Networks在大部分学校都是教材,书到用时方恨少啊
本科
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先顶后看
|
|
|
d**e 发帖数: 6098 | 41 大牛,不如把我收了吧?
【在 g**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Andrew Tanenbaum的Computer Networks在大部分学校都是教材,书到用时方恨少啊 : : 本科
|