问一道system design的题 - 未名空间MITBBS历史存档

c*t2016-09-22 07:09

1 楼

onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
time。到了那个时间就把消息发出去。
我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
请问大侠这个应该怎么设计？

R*i2016-09-22 07:09

2 楼

我感觉你不能直接把到点的message从db里取出来就发。应该放进一个queue里，有一个
service一直在扫描这个queue，如果是空，当然不发，如果太多，就连发。

m*n2016-09-22 07:09

3 楼

you can fail it when creating the message, and let users set
another "future time"

【在 c********t 的大作中提到】

: onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
: time。到了那个时间就把消息发出去。
: 我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
: 分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
: 怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
: 没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
: 。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
: 11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
: 量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
: 请问大侠这个应该怎么设计？

j*r2016-09-22 07:09

4 楼

DB is for storage/backup purpose. The messages should be kept in a priority
queue in memory based on schedule, at least for those that will be sent in
next N
minutes, and you can load up every N minutes.
A master handler can distribute the messages to a worker cluster, if the
messages are big, message id can be passed instead, and worker cluster can
call back DB to get the message payload. Using async requests, a single node
can easily send 10s of thousands of messages per second, usually enough for
this kind of app. And if it's not enough, nothing stops you from vertically
partition your messages and front multiple such groups with a load balancer.
You can use monitoring and leader election to avoid single point failure on
master handler.

【在 c********t 的大作中提到】

: onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
: time。到了那个时间就把消息发出去。
: 我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
: 分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
: 怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
: 没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
: 。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
: 11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
: 量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
: 请问大侠这个应该怎么设计？

s*32016-09-22 07:09

5 楼

所以是像throttling 限制总量吗?

c*t2016-09-22 07:09

6 楼

我当时是想到了queue,但是资源限制的话，queue会keep growing. MQ主要是能async,
但在thread并没有被hold的情况下, 没什么帮助啊，也并不能增加server的处理

【在 R*****i 的大作中提到】

: 我感觉你不能直接把到点的message从db里取出来就发。应该放进一个queue里，有一个
: service一直在扫描这个queue，如果是空，当然不发，如果太多，就连发。

c*t2016-09-22 07:09

7 楼

再让user重新选时间应该不行。

【在 m******n 的大作中提到】

: you can fail it when creating the message, and let users set
: another "future time"

j*r2016-09-22 07:09

8 楼

你应该问的是什么资源的限制。每种不同限制处理的办法不同。像这种消息之间没有依
赖性，完全不会有scale的问题。

,

【在 c********t 的大作中提到】

: 我当时是想到了queue,但是资源限制的话，queue会keep growing. MQ主要是能async,
: 但在thread并没有被hold的情况下, 没什么帮助啊，也并不能增加server的处理

c*t2016-09-22 07:09

9 楼

多谢，你这个设计确实好。
面试官确实说了每个消息可以很大，甚至可以有大附件，所以我第一反应是要DB存，我
说了DB design，他也默许了。不过我没有想可以把多长时间以内的存在memory，他反
复两次说用时间query DB不work。估计是像你说的，他想要的答案是preload next N
minutes message into memory. 三哥真应该给我一个方向提示，提示我处理速度受到
query DB的限制。还有我提到Server cluster, 和multi clusters, 他也没搭理，只是
说再多的server也有处理限制。给我的感觉就是无所谓server数量。把我问住了，我只
好说发不出去的留到下一分钟再发。我感觉你这个设计用master 和 work很好，master
不用处理历史未发送的，可以提前把下N分钟要发的 message ids分配给work clusters
, work server preload messages into memory from DB, 并定时发送。再加上你说的
multi clusters/ Data centers with load balancer, 应该差不多了。三哥面试官一
点都不给提示，只是说query不能work, 实在让我没头绪，不明白他要什么。

priority
node
for
vertically
balancer.

【在 j**********r 的大作中提到】

: DB is for storage/backup purpose. The messages should be kept in a priority
: queue in memory based on schedule, at least for those that will be sent in
: next N
: minutes, and you can load up every N minutes.
: A master handler can distribute the messages to a worker cluster, if the
: messages are big, message id can be passed instead, and worker cluster can
: call back DB to get the message payload. Using async requests, a single node
: can easily send 10s of thousands of messages per second, usually enough for
: this kind of app. And if it's not enough, nothing stops you from vertically
: partition your messages and front multiple such groups with a load balancer.

c*t2016-09-22 07:09

10 楼

我问了，他解释的限制就是server处理速度的限制，并不是具体到cpu, thread,
memory, 而是就是一分钟最多发送N个消息。

【在 j**********r 的大作中提到】

: 你应该问的是什么资源的限制。每种不同限制处理的办法不同。像这种消息之间没有依
: 赖性，完全不会有scale的问题。
:
: ,

s*g2016-09-22 07:09

11 楼

如果面试官表示无论你什么solution都会遇到超越resource的情况
你确定让user重选时间不行？也不能扔request？
持续peak期间handle不过来，后面的request就会越来越delay，还不如直接拒绝过多的
request

【在 c********t 的大作中提到】

: 再让user重新选时间应该不行。

c*t2016-09-22 07:09

12 楼

你说的也有道理，如果无论如何都有限制，需要throttling。

【在 s**********g 的大作中提到】

: 如果面试官表示无论你什么solution都会遇到超越resource的情况
: 你确定让user重选时间不行？也不能扔request？
: 持续peak期间handle不过来，后面的request就会越来越delay，还不如直接拒绝过多的
: request

w*z2016-09-22 07:09

13 楼

怎么处理定时发送？总是要有个scheduler 吧。

priority
node
for
vertically
balancer.

【在 j**********r 的大作中提到】

: DB is for storage/backup purpose. The messages should be kept in a priority
: queue in memory based on schedule, at least for those that will be sent in
: next N
: minutes, and you can load up every N minutes.
: A master handler can distribute the messages to a worker cluster, if the
: messages are big, message id can be passed instead, and worker cluster can
: call back DB to get the message payload. Using async requests, a single node
: can easily send 10s of thousands of messages per second, usually enough for
: this kind of app. And if it's not enough, nothing stops you from vertically
: partition your messages and front multiple such groups with a load balancer.

w*z2016-09-22 07:09

14 楼

throttle 是一招。你也应该设计考虑如何可以scale out，这在实际中更重要。楼上古
德霸的设计不错，可以 scale workers. 工作中很常用的手法。

【在 c********t 的大作中提到】

: 你说的也有道理，如果无论如何都有限制，需要throttling。

j*r2016-09-22 07:09

15 楼

各种cron scheduler都是现成的，比如quartz. 只要你单结点load 不大，咋整不行。

【在 w**z 的大作中提到】

: 怎么处理定时发送？总是要有个scheduler 吧。
:
: priority
: node
: for
: vertically
: balancer.

l*w2016-09-22 07:09

16 楼

设计个load balancer不就好了？简单的round robin就可以啊

c*t2016-09-22 07:09

17 楼

原来是霸哥啊，你也要换工作了？

【在 j**********r 的大作中提到】

: 各种cron scheduler都是现成的，比如quartz. 只要你单结点load 不大，咋整不行。

w*z2016-09-22 07:09

18 楼

霸哥提携晚辈。

【在 c********t 的大作中提到】

: 原来是霸哥啊，你也要换工作了？

e*s2016-09-22 07:09

19 楼

这种东西不能放db里吧. db的存取延迟怎么估计...
怎么保证能再发送之前一定取得出来
据说系统设计最重要的环节是把要求和限制问清楚?

【在 c********t 的大作中提到】

: onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
: time。到了那个时间就把消息发出去。
: 我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
: 分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
: 怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
: 没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
: 。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
: 11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
: 量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
: 请问大侠这个应该怎么设计？

e*s2016-09-22 07:09

20 楼

不错不错

priority
node
for
vertically
balancer.

【在 j**********r 的大作中提到】

: DB is for storage/backup purpose. The messages should be kept in a priority
: queue in memory based on schedule, at least for those that will be sent in
: next N
: minutes, and you can load up every N minutes.
: A master handler can distribute the messages to a worker cluster, if the
: messages are big, message id can be passed instead, and worker cluster can
: call back DB to get the message payload. Using async requests, a single node
: can easily send 10s of thousands of messages per second, usually enough for
: this kind of app. And if it's not enough, nothing stops you from vertically
: partition your messages and front multiple such groups with a load balancer.

a*02016-09-22 07:09

21 楼

这题你错在要按1 min的时间间隔发送，面试官是要考你的是每个消息只在其固定的
future time被发送出去。

c*t2016-09-22 07:09

22 楼

请问这样该如何设计？

【在 a*********0 的大作中提到】

: 这题你错在要按1 min的时间间隔发送，面试官是要考你的是每个消息只在其固定的
: future time被发送出去。

c*32016-09-22 07:09

23 楼

我咋感觉建立一个link加一个Queue就行
一个是按照时间线设置的link，可以每分钟或者每秒一个子link head，下面挂接这个
时间需要发送的消息
然后按照当前时间扫描该link，把整个子link都扔到发送queue去，只要这个queue不空
就连续发送

c*t2016-09-22 07:09

24 楼

onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
time。到了那个时间就把消息发出去。
我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
请问大侠这个应该怎么设计？

R*i2016-09-22 07:09

25 楼

我感觉你不能直接把到点的message从db里取出来就发。应该放进一个queue里，有一个
service一直在扫描这个queue，如果是空，当然不发，如果太多，就连发。

m*n2016-09-22 07:09

26 楼

you can fail it when creating the message, and let users set
another "future time"

【在 c********t 的大作中提到】

: onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
: time。到了那个时间就把消息发出去。
: 我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
: 分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
: 怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
: 没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
: 。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
: 11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
: 量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
: 请问大侠这个应该怎么设计？

j*r2016-09-22 07:09

27 楼

DB is for storage/backup purpose. The messages should be kept in a priority
queue in memory based on schedule, at least for those that will be sent in
next N
minutes, and you can load up every N minutes.
A master handler can distribute the messages to a worker cluster, if the
messages are big, message id can be passed instead, and worker cluster can
call back DB to get the message payload. Using async requests, a single node
can easily send 10s of thousands of messages per second, usually enough for
this kind of app. And if it's not enough, nothing stops you from vertically
partition your messages and front multiple such groups with a load balancer.
You can use monitoring and leader election to avoid single point failure on
master handler.

【在 c********t 的大作中提到】

: onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
: time。到了那个时间就把消息发出去。
: 我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
: 分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
: 怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
: 没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
: 。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
: 11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
: 量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
: 请问大侠这个应该怎么设计？

s*32016-09-22 07:09

28 楼

所以是像throttling 限制总量吗?

c*t2016-09-22 07:09

29 楼

我当时是想到了queue,但是资源限制的话，queue会keep growing. MQ主要是能async,
但在thread并没有被hold的情况下, 没什么帮助啊，也并不能增加server的处理

【在 R*****i 的大作中提到】

: 我感觉你不能直接把到点的message从db里取出来就发。应该放进一个queue里，有一个
: service一直在扫描这个queue，如果是空，当然不发，如果太多，就连发。

c*t2016-09-22 07:09

30 楼

再让user重新选时间应该不行。

【在 m******n 的大作中提到】

: you can fail it when creating the message, and let users set
: another "future time"

j*r2016-09-22 07:09

31 楼

你应该问的是什么资源的限制。每种不同限制处理的办法不同。像这种消息之间没有依
赖性，完全不会有scale的问题。

,

【在 c********t 的大作中提到】

: 我当时是想到了queue,但是资源限制的话，queue会keep growing. MQ主要是能async,
: 但在thread并没有被hold的情况下, 没什么帮助啊，也并不能增加server的处理

c*t2016-09-22 07:09

32 楼

多谢，你这个设计确实好。
面试官确实说了每个消息可以很大，甚至可以有大附件，所以我第一反应是要DB存，我
说了DB design，他也默许了。不过我没有想可以把多长时间以内的存在memory，他反
复两次说用时间query DB不work。估计是像你说的，他想要的答案是preload next N
minutes message into memory. 三哥真应该给我一个方向提示，提示我处理速度受到
query DB的限制。还有我提到Server cluster, 和multi clusters, 他也没搭理，只是
说再多的server也有处理限制。给我的感觉就是无所谓server数量。把我问住了，我只
好说发不出去的留到下一分钟再发。我感觉你这个设计用master 和 work很好，master
不用处理历史未发送的，可以提前把下N分钟要发的 message ids分配给work clusters
, work server preload messages into memory from DB, 并定时发送。再加上你说的
multi clusters/ Data centers with load balancer, 应该差不多了。三哥面试官一
点都不给提示，只是说query不能work, 实在让我没头绪，不明白他要什么。

priority
node
for
vertically
balancer.

【在 j**********r 的大作中提到】

: DB is for storage/backup purpose. The messages should be kept in a priority
: queue in memory based on schedule, at least for those that will be sent in
: next N
: minutes, and you can load up every N minutes.
: A master handler can distribute the messages to a worker cluster, if the
: messages are big, message id can be passed instead, and worker cluster can
: call back DB to get the message payload. Using async requests, a single node
: can easily send 10s of thousands of messages per second, usually enough for
: this kind of app. And if it's not enough, nothing stops you from vertically
: partition your messages and front multiple such groups with a load balancer.

c*t2016-09-22 07:09

33 楼

我问了，他解释的限制就是server处理速度的限制，并不是具体到cpu, thread,
memory, 而是就是一分钟最多发送N个消息。

【在 j**********r 的大作中提到】

: 你应该问的是什么资源的限制。每种不同限制处理的办法不同。像这种消息之间没有依
: 赖性，完全不会有scale的问题。
:
: ,

s*g2016-09-22 07:09

34 楼

如果面试官表示无论你什么solution都会遇到超越resource的情况
你确定让user重选时间不行？也不能扔request？
持续peak期间handle不过来，后面的request就会越来越delay，还不如直接拒绝过多的
request

【在 c********t 的大作中提到】

: 再让user重新选时间应该不行。

c*t2016-09-22 07:09

35 楼

你说的也有道理，如果无论如何都有限制，需要throttling。

【在 s**********g 的大作中提到】

: 如果面试官表示无论你什么solution都会遇到超越resource的情况
: 你确定让user重选时间不行？也不能扔request？
: 持续peak期间handle不过来，后面的request就会越来越delay，还不如直接拒绝过多的
: request

w*z2016-09-22 07:09

36 楼

怎么处理定时发送？总是要有个scheduler 吧。

priority
node
for
vertically
balancer.

【在 j**********r 的大作中提到】

: DB is for storage/backup purpose. The messages should be kept in a priority
: queue in memory based on schedule, at least for those that will be sent in
: next N
: minutes, and you can load up every N minutes.
: A master handler can distribute the messages to a worker cluster, if the
: messages are big, message id can be passed instead, and worker cluster can
: call back DB to get the message payload. Using async requests, a single node
: can easily send 10s of thousands of messages per second, usually enough for
: this kind of app. And if it's not enough, nothing stops you from vertically
: partition your messages and front multiple such groups with a load balancer.

w*z2016-09-22 07:09

37 楼

throttle 是一招。你也应该设计考虑如何可以scale out，这在实际中更重要。楼上古
德霸的设计不错，可以 scale workers. 工作中很常用的手法。

【在 c********t 的大作中提到】

: 你说的也有道理，如果无论如何都有限制，需要throttling。

j*r2016-09-22 07:09

38 楼

各种cron scheduler都是现成的，比如quartz. 只要你单结点load 不大，咋整不行。

【在 w**z 的大作中提到】

: 怎么处理定时发送？总是要有个scheduler 吧。
:
: priority
: node
: for
: vertically
: balancer.

l*w2016-09-22 07:09

39 楼

设计个load balancer不就好了？简单的round robin就可以啊

c*t2016-09-22 07:09

40 楼

原来是霸哥啊，你也要换工作了？

【在 j**********r 的大作中提到】

: 各种cron scheduler都是现成的，比如quartz. 只要你单结点load 不大，咋整不行。

w*z2016-09-22 07:09

41 楼

霸哥提携晚辈。

【在 c********t 的大作中提到】

: 原来是霸哥啊，你也要换工作了？

e*s2016-09-22 07:09

42 楼

这种东西不能放db里吧. db的存取延迟怎么估计...
怎么保证能再发送之前一定取得出来
据说系统设计最重要的环节是把要求和限制问清楚?

【在 c********t 的大作中提到】

: onsite被问设计一个定时发送消息的系统，就是当create message时，给一个future
: time。到了那个时间就把消息发出去。
: 我给出的设计是当create时，存入DB. 然后有一个scheduler每分钟query db, 把这一
: 分钟需要发送的消息发出去。面试官问消息太多，如果server不能发完这一分钟的消息
: 怎么办。我说scheduler 除了发这一分钟的，也可以发送历史留下未发出的，这一分钟
: 没发出，下一分钟数量少了就可以发出。或者单独有一个thread专门发送历史未发出的
: 。面试官说server就是有资源限制，不管几个thread只能一分钟发10个，如果每分钟有
: 11个消息怎么办？我说加server，面试官说不管加多少server, 总有限制，如果消息数
: 量超过限制怎么办？他说我的design不work. 我就傻了,不太明白他要什么了。
: 请问大侠这个应该怎么设计？

e*s2016-09-22 07:09

43 楼

不错不错

priority
node
for
vertically
balancer.

【在 j**********r 的大作中提到】

: DB is for storage/backup purpose. The messages should be kept in a priority
: queue in memory based on schedule, at least for those that will be sent in
: next N
: minutes, and you can load up every N minutes.
: A master handler can distribute the messages to a worker cluster, if the
: messages are big, message id can be passed instead, and worker cluster can
: call back DB to get the message payload. Using async requests, a single node
: can easily send 10s of thousands of messages per second, usually enough for
: this kind of app. And if it's not enough, nothing stops you from vertically
: partition your messages and front multiple such groups with a load balancer.

a*02016-09-22 07:09

44 楼

这题你错在要按1 min的时间间隔发送，面试官是要考你的是每个消息只在其固定的
future time被发送出去。

c*t2016-09-22 07:09

45 楼

请问这样该如何设计？

【在 a*********0 的大作中提到】

: 这题你错在要按1 min的时间间隔发送，面试官是要考你的是每个消息只在其固定的
: future time被发送出去。

c*32016-09-22 07:09

46 楼

我咋感觉建立一个link加一个Queue就行
一个是按照时间线设置的link，可以每分钟或者每秒一个子link head，下面挂接这个
时间需要发送的消息
然后按照当前时间扫描该link，把整个子link都扔到发送queue去，只要这个queue不空
就连续发送

C*92016-09-22 07:09

47 楼

你面的是Nest lab？当年我在那边被三哥问了个一样的题，我怎么说他都说不work

c*t2016-09-22 07:09

48 楼

正是啊，握手！三哥不给任何hint, 光说不work. 你当时怎么答的？

【在 C********9 的大作中提到】

: 你面的是Nest lab？当年我在那边被三哥问了个一样的题，我怎么说他都说不work

c*t2016-09-22 07:09

49 楼

queue数据累计，有延迟，不能按时发送怎么办？我现在想想面试官可能是要必须准时
发送，(可是他为什么没说呢？）那么估计是要用timer schedule下一分钟要发的email。
我当时用间隔一分钟的scheduler。他的原话是，如果server一分钟只能处理10个，那
一分钟却有11个的话，你就不能按时发最后一个，所以不work. 我就扯multi thread,
multi server, distrubute, 他就说不管怎么多的server,还是有限制，如果你的
request超过limit就不work.我就没词了。可能他想要的是throttling？三哥的心思很
难猜。什么hint都不给。走的时候也不说他的思路。
不管怎样，霸哥的解决方案+throttling应该可以了。

【在 c******3 的大作中提到】

: 我咋感觉建立一个link加一个Queue就行
: 一个是按照时间线设置的link，可以每分钟或者每秒一个子link head，下面挂接这个
: 时间需要发送的消息
: 然后按照当前时间扫描该link，把整个子link都扔到发送queue去，只要这个queue不空
: 就连续发送