r*******h
发帖数: 315 | 1 要求设计一个Rate Limiter。突然想起来了，供大家讨论一下吧。 |
p*****p
发帖数: 379 | 2 这就没了？
流量是多少
ip/cookie/session based?
服务器架构是怎么样的？
这东西准备放在哪里？
有些什么现成的东西（memcached/redis...）？
【在 r*******h 的大作中提到】
: 要求设计一个Rate Limiter。突然想起来了，供大家讨论一下吧。
|
p*****2
发帖数: 21240 | 3 大牛说说一般怎么设计
【在 p*****p 的大作中提到】
: 这就没了？
: 流量是多少
: 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 的大作中提到】
: 大牛说说一般怎么设计
|
p*****2
发帖数: 21240 | 5 你说的更像是需求
具体应该怎么设计呢？
比如你提到数据结构 但是到底应该用什么数据结构呢
【在 m********t 的大作中提到】
: 不是大牛，随便说两句
: 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 的大作中提到】
: 要求设计一个Rate Limiter。突然想起来了，供大家讨论一下吧。
|
p*****2
发帖数: 21240 | 8 你这个貌似跟月光是两个极端呀
了。
【在 q********c 的大作中提到】
: 这是我的口德. 基本原理就这样，再讨论一下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 的大作中提到】
: 这是我的口德. 基本原理就这样，再讨论一下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 的大作中提到】
: 你这个貌似跟月光是两个极端呀
:
: 了。
|
|
|
p*****2
发帖数: 21240 | 11 先写code再谈scalability 肯定有问题
scale不同设计会大不一样
【在 m********t 的大作中提到】
: 这么简单？ 我考虑问题总是前前后后都想个遍。。。
: 凭我直觉，面试的出发点是考量你的设计思路和循序渐进的一个逻辑过程
: 我甚至都不认为coding在这里算是重点了
: project最开始的核心定位和相应参数的设置，极为关键，这个跟盖楼打地基是一样的
: crucial
: 一开始没定位好地基的模型，后来的人没法跟，也就是上面的floors就很难reliable打
: 下去了
: 会出现半途而废，然后重头开始的低效
: 不过，可能你是对的，我也就是瞎说自己的感觉
:
|
q********c
发帖数: 1774 | 12 我这是基本原理，限制rate, 就看相邻两个request之间时间间隔，如果小于最小间隔
，就sleep, 就这样。月光堆一堆名词，看不懂。
【在 p*****2 的大作中提到】
: 你这个貌似跟月光是两个极端呀
:
: 了。
|
m********t
发帖数: 13072 | 13 我想问题，经常复杂化，可能你是对的，面试官可能需要这种简单而直接的solution
【在 q********c 的大作中提到】
: 我这是基本原理，限制rate, 就看相邻两个request之间时间间隔，如果小于最小间隔
: ，就sleep, 就这样。月光堆一堆名词，看不懂。
|
p*****2
发帖数: 21240 | 14 大牛还是继续吧
你现在还处在pm阶段
下一步怎么做呢？
【在 m********t 的大作中提到】
: 我想问题，经常复杂化，可能你是对的，面试官可能需要这种简单而直接的solution
|
N*****m
发帖数: 42603 | 15 这题说得不清楚，没法设计
【在 p*****2 的大作中提到】
: 大牛还是继续吧
: 你现在还处在pm阶段
: 下一步怎么做呢？
|
p*****2
发帖数: 21240 | 16 月光已经说的够多得了吧
【在 N*****m 的大作中提到】
: 这题说得不清楚，没法设计
|
N*****m
发帖数: 42603 | 17 单就一个rate就没说清楚
一个机器的rate，一个系统的rate，一个account跨区的rate；
再说什么rate？流量，CPU，内存还是硬盘？
然后怎么limit？hard limit还是soft？
任何一个组合就是一种solution，这个题目啥都没说，设计个头。
【在 p*****2 的大作中提到】
: 月光已经说的够多得了吧
|
m********t
发帖数: 13072 | 18 现在，眼下这个时代，rate limit都要走load balancing路线，只不过方法不同，要么
并行多几条virtual lanes，要么是按时间去做queuing， 只有这样才可以避免各种
collision的发生，这只是理想状态，而真实状态，这样也还出现很多故障。
你就把这道题当成高速上的limit去考虑就行了，真到了塞车或撞车的时候，已经太晚
了，人均的前进效率也就是流量其实是很低的， 所以提前的各项措施，很有必要
这个题目我估计是跟google cloud data center的资源分布有点关系。
瞎猜的啊，不一定对
【在 N*****m 的大作中提到】
: 单就一个rate就没说清楚
: 一个机器的rate，一个系统的rate，一个account跨区的rate；
: 再说什么rate？流量，CPU，内存还是硬盘？
: 然后怎么limit？hard limit还是soft？
: 任何一个组合就是一种solution，这个题目啥都没说，设计个头。
|
m********t
发帖数: 13072 | 19 这种设计需要很多细节部分，仔细想一想，包括相关的参数和变量，
我上午要给一个tech talk, 还要复查一下ppt
晚点才能有空了
【在 p*****2 的大作中提到】
: 大牛还是继续吧
: 你现在还处在pm阶段
: 下一步怎么做呢？
|
r*******h
发帖数: 315 | 20 抱歉，之前是临时想起来就贴上了。当时先是讨论了一个一般性的模型，后来要求
coding一个method based，就是怎么控制一定时间内对一个method或者function的调用数
【在 p*****p 的大作中提到】
: 这就没了？
: 流量是多少
: 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 的大作中提到】
: 我在 Guava 里面找到了一个叫 Ratelimiter 的类。
: 干的是类似 lock 的事情。有点像 Semaphore，不过不是控制 Thread 的数量，
: 而是控制一段时间里面的流量。
|
p*****2
发帖数: 21240 | 23
用数
是什么method？
【在 r*******h 的大作中提到】
: 抱歉，之前是临时想起来就贴上了。当时先是讨论了一个一般性的模型，后来要求
: coding一个method based，就是怎么控制一定时间内对一个method或者function的调用数
|
p***y
发帖数: 637 | 24 用sleep不妥
了。
"" ;="" :="" ...................="">
【在 q********c 的大作中提到】
: 这是我的口德. 基本原理就这样，再讨论一下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 的大作中提到】
: 不是大牛，随便说两句
: 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 的大作中提到】
:
: 用数
: 是什么method？
|
p*****2
发帖数: 21240 | 27 那不考虑scale吗
【在 r*******h 的大作中提到】
: 任意一个供外部调用的方法或者函数，比如打包成web services的
|
m*****k
发帖数: 731 | 28 Thread.sleep(minInterval - diff); 吧？
了。
【在 q********c 的大作中提到】
: 这是我的口德. 基本原理就这样，再讨论一下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 的大作中提到】
: 我在 Guava 里面找到了一个叫 Ratelimiter 的类。
: 干的是类似 lock 的事情。有点像 Semaphore，不过不是控制 Thread 的数量，
: 而是控制一段时间里面的流量。
|
p*****2
发帖数: 21240 | 30 sleep是线程阻塞的吧 除非用go
【在 C*******n 的大作中提到】
: 看了看
: 是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 的大作中提到】
: sleep是线程阻塞的吧 除非用go
|
p*****2
发帖数: 21240 | 32 并发性太差了
limited
【在 C*******n 的大作中提到】
: 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 的大作中提到】
: 并发性太差了
:
: limited
|
p*****2
发帖数: 21240 | 34 好 多谢大牛
limit
【在 g**e 的大作中提到】
: SOA下就直接扔异常啦 常见的rate limiter要先决定支不支持burst，throttle limit
: 和recover limit经常是不同的
: 这个题很好，回去翻一下AWS API throttling是咋设计的再来分享
|
p***y
发帖数: 637 | 35 用sleep就不用谈scale了
【在 C*******n 的大作中提到】
: 看了看
: 是sleep处理的。
: 概念上不难 挺清晰的。
|
M*******a
发帖数: 1633 | 36 仅仅限制间隔时间应该太简化了
应该是要考虑burst的情况的。
感觉这个题目更哪个什么过去一分钟一小时一天的request数量的题目有关系。
就是给定一段固定的时间控制这段时间里面最大可能的request数量。
如果要精确解就要保持一个request queue，不要精确解就把固定一段时间分成比如100
份记录每份时间里面的request数量。 |
p***y
发帖数: 637 | 37 好像有好几个贴子讨论这个问题了。奇怪。
100
【在 M*******a 的大作中提到】
: 仅仅限制间隔时间应该太简化了
: 应该是要考虑burst的情况的。
: 感觉这个题目更哪个什么过去一分钟一小时一天的request数量的题目有关系。
: 就是给定一段固定的时间控制这段时间里面最大可能的request数量。
: 如果要精确解就要保持一个request queue，不要精确解就把固定一段时间分成比如100
: 份记录每份时间里面的request数量。
|
g**e
发帖数: 6127 | 38 终极答案 http://en.wikipedia.org/wiki/Token_bucket
AWS不同的产品throttling的实现有差别，不过基本都是基于上面这个。所以说，本科
学的网络通信还是有用的啊...
【在 p*****2 的大作中提到】
: 好 多谢大牛
:
: limit
|
p*****2
发帖数: 21240 | 39 先顶后看
【在 g**e 的大作中提到】
: 终极答案 http://en.wikipedia.org/wiki/Token_bucket
: AWS不同的产品throttling的实现有差别，不过基本都是基于上面这个。所以说，本科
: 学的网络通信还是有用的啊...
|
g**e
发帖数: 6127 | 40 Andrew Tanenbaum的Computer Networks在大部分学校都是教材，书到用时方恨少啊
本科
【在 p*****2 的大作中提到】
: 先顶后看
|
|
|
d**e
发帖数: 6098 | 41 大牛,不如把我收了吧?
【在 g**e 的大作中提到】
: Andrew Tanenbaum的Computer Networks在大部分学校都是教材，书到用时方恨少啊
:
: 本科
|
