由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - g家一道设计题
相关主题
问一个system design的题,看看大家怎么想的。为什么说semaphore是一种进程间的通信方式。
面google,看来读熟guava很有好处阿亚麻面经
问个Google的面试题failed bloomberg phone interview
攒rp,发个G家面经g电面
新鲜电面经Dropbox 电面
Seattle 码工 position问一道g的题
帮马鬃国人经理收SDE简历M 家电话难题
U店面Turn was acquired
相关话题的讨论汇总
话题: rate话题: diff话题: 设计话题: limiter
进入JobHunting版参与讨论
1 (共1页)
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 的大作中提到】
: 你这个貌似跟月光是两个极端呀
:
: 了。

相关主题
Seattle 码工 position为什么说semaphore是一种进程间的通信方式。
帮马鬃国人经理收SDE简历亚麻面经
U店面failed bloomberg phone interview
进入JobHunting版参与讨论
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...)?

相关主题
g电面M 家电话难题
Dropbox 电面Turn was acquired
问一道g的题亚特兰大Manager Position (CS)
进入JobHunting版参与讨论
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处理的。
: 概念上不难 挺清晰的。

相关主题
问几道Google onsite 的问题面google,看来读熟guava很有好处阿
下一轮startup是不是mobile为主?问个Google的面试题
问一个system design的题,看看大家怎么想的。攒rp,发个G家面经
进入JobHunting版参与讨论
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 的大作中提到】
: 先顶后看
相关主题
攒rp,发个G家面经帮马鬃国人经理收SDE简历
新鲜电面经U店面
Seattle 码工 position为什么说semaphore是一种进程间的通信方式。
进入JobHunting版参与讨论
d**e
发帖数: 6098
41
大牛,不如把我收了吧?

【在 g**e 的大作中提到】
: Andrew Tanenbaum的Computer Networks在大部分学校都是教材,书到用时方恨少啊
:
: 本科

1 (共1页)
进入JobHunting版参与讨论
相关主题
Turn was acquired新鲜电面经
亚特兰大Manager Position (CS)Seattle 码工 position
问几道Google onsite 的问题帮马鬃国人经理收SDE简历
下一轮startup是不是mobile为主?U店面
问一个system design的题,看看大家怎么想的。为什么说semaphore是一种进程间的通信方式。
面google,看来读熟guava很有好处阿亚麻面经
问个Google的面试题failed bloomberg phone interview
攒rp,发个G家面经g电面
相关话题的讨论汇总
话题: rate话题: diff话题: 设计话题: limiter