讨论两道L家的设计题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

讨论两道L家的设计题

讨论两道L家的设计题# JobHunting - 待字闺中

y*s2015-10-19 07:10

1 楼

1. Design IP black List
- 这个题乍看一下感觉就是一个HashSet就可以解决了,最多一个HashSet放不下，就用
模除法shard到多个server，这里可以扯一下load balancer和consistent hashing啥的
。还能想到的一点改进是，如果是IPv4的话，所有的地址可以用一个1GB大小的bitmap
放下。但是在IPv6就不可以了。
不知道还有什么注意点吗？
2. Design log monitor system: 好多机器，每个都有log,内容包括exception和error
等，设计一个系统检测这些错误，然后找出之前一段时间最多的错误等。
- 这个题我觉得有点像Top K URLs。我能想到的是：在机器端，根据错误的种类，分块
LOG，比如Error_1 都放在Log_1中，Error_2都放在Log_2中。有另外的一些server，比
如Server_1从所有的机器中读取Log_1，然后汇总报告。
不知道还能改进吗？
多谢~

h*02015-10-19 07:10

2 楼

第一题 nosql ＋ cache不可以吗？
第二题为什么要monitor log？用airbrake这类的不行吗？如果非要监测的log的话
，那么就multiple clients ＋ central server。 client发现exception，发给
central server， server count exception。这样就可以了把。

m*32015-10-19 07:10

3 楼

第二题能用mapreduce不？

y*s2015-10-19 07:10

4 楼

第二个，要是机器太多，一个centralserver来不及呢？

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

: 第一题 nosql ＋ cache不可以吗？
: 第二题为什么要monitor log？用airbrake这类的不行吗？如果非要监测的log的话
: ，那么就multiple clients ＋ central server。 client发现exception，发给
: central server， server count exception。这样就可以了把。

g*d2015-10-19 07:10

5 楼

第一题我觉得要看对方是否问你具体场景吧。如果仅仅就是单纯一个黑名单，自然是不
难。但是考虑到应用场景，一个简单的ip black list不是一个非常好的解决方案，具
体原因就是IP经常是动态的，而且IP经常是共用的。比如说某个用户干坏事，IP上了黑
名单，但是下一次可能是别的用户刚好被分配了这个IP，那个用户就没法用了不是。
IP黑名单可能要有相应的机制来把被列进来的IP再去掉，比如过了一定时间间隔之类。
还有就是结合其他一些技术来过滤掉恶意用户，保证正常用户不受影响。
上次去T面试时候刚好遇到一个面试官是他们家应对假帐号的，所以就聊了一些相关的
东西。

s*32015-10-19 07:10

6 楼

re

bitmap
error

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

: 1. Design IP black List
: - 这个题乍看一下感觉就是一个HashSet就可以解决了,最多一个HashSet放不下，就用
: 模除法shard到多个server，这里可以扯一下load balancer和consistent hashing啥的
: 。还能想到的一点改进是，如果是IPv4的话，所有的地址可以用一个1GB大小的bitmap
: 放下。但是在IPv6就不可以了。
: 不知道还有什么注意点吗？
: 2. Design log monitor system: 好多机器，每个都有log,内容包括exception和error
: 等，设计一个系统检测这些错误，然后找出之前一段时间最多的错误等。
: - 这个题我觉得有点像Top K URLs。我能想到的是：在机器端，根据错误的种类，分块
: LOG，比如Error_1 都放在Log_1中，Error_2都放在Log_2中。有另外的一些server，比

p*62015-10-19 07:10

7 楼

第二题考你会不会用kafka和某流处理的工具，老题了

d*w2015-10-19 07:10

8 楼

IP black list很多时候你要ban掉一个range ，使用172.16.8.0/24这样的方式表达的
。显然美版用hashset啊，除非你预处理时把所有的ip range都用单个IP表达出来。问
题是，ipv6有128位，你这样怎么玩？

bitmap
error

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

p*62015-10-19 07:10

9 楼

第一题的follow up要考你夸data center的解决办法

y*s2015-10-19 07:10

10 楼

多谢回复，学习了

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

: 第一题我觉得要看对方是否问你具体场景吧。如果仅仅就是单纯一个黑名单，自然是不
: 难。但是考虑到应用场景，一个简单的ip black list不是一个非常好的解决方案，具
: 体原因就是IP经常是动态的，而且IP经常是共用的。比如说某个用户干坏事，IP上了黑
: 名单，但是下一次可能是别的用户刚好被分配了这个IP，那个用户就没法用了不是。
: IP黑名单可能要有相应的机制来把被列进来的IP再去掉，比如过了一定时间间隔之类。
: 还有就是结合其他一些技术来过滤掉恶意用户，保证正常用户不受影响。
: 上次去T面试时候刚好遇到一个面试官是他们家应对假帐号的，所以就聊了一些相关的
: 东西。

y*s2015-10-19 07:10

11 楼

能再具体说说吗？多谢
没有用过kafka。。。

【在 p****6 的大作中提到】

: 第二题考你会不会用kafka和某流处理的工具，老题了

y*s2015-10-19 07:10

12 楼

说的有道理，那觉得用trie怎么样，空间一定，还很小。还是你觉得这题就是完全考其
他的地方？

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

: IP black list很多时候你要ban掉一个range ，使用172.16.8.0/24这样的方式表达的
: 。显然美版用hashset啊，除非你预处理时把所有的ip range都用单个IP表达出来。问
: 题是，ipv6有128位，你这样怎么玩？
:
: bitmap
: error

y*s2015-10-19 07:10

13 楼

这夸center怎么办啊？能再说说吗？

【在 p****6 的大作中提到】

: 第一题的follow up要考你夸data center的解决办法

p*62015-10-19 07:10

14 楼

只能去看了。。。这L的infra track高频题。夸data center最简单的办法就是async
的replication,。
[在 yimingts (小人物) 的大作中提到：]
：能再具体说说吗？多谢
：
：...........

y*s2015-10-19 07:10

15 楼

多谢回复！现在就去看看。

【在 p****6 的大作中提到】

: 只能去看了。。。这L的infra track高频题。夸data center最简单的办法就是async
: 的replication,。
: [在 yimingts (小人物) 的大作中提到：]
: ：能再具体说说吗？多谢
: ：
: ：...........

h*02015-10-19 07:10

16 楼

h*02015-10-19 07:10

17 楼

central server 可以scale up 啊

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

: 第二个，要是机器太多，一个centralserver来不及呢？

m*32015-10-19 07:10

18 楼

scale up不是一个好的设计啊，应该是scale out, central server应该是一个cluster
,否则你会有single point failure问题啊
不过我还是觉得楼上说的要去看kafka是正解

m*32015-10-19 07:10

19 楼

scale up不是一个好的设计啊，应该是scale out, central server应该是一个cluster
,否则你会有single point failure问题啊
不过我还是觉得楼上说的要去看kafka是正解

d*w2015-10-19 07:10

20 楼

一般就是用这个做。不过要不要你写code? 貌似在白板上把prefix tree给写出来还是
挺难的。

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

: 说的有道理，那觉得用trie怎么样，空间一定，还很小。还是你觉得这题就是完全考其
: 他的地方？

g*g2015-10-19 07:10

21 楼

2. pull is too long. push to a Kafka Q and use a dedicated cluster to
process. You can leverage Storm Spark etc.

m*32015-10-19 07:10

22 楼

不懂kafka,打算去看看了解一下。不过我理解好虫你的意思是说，server(producer)把
产生的log直接丢到Kafka Q里面，然后有一个dedicated cluster(consumer)不断的从
queue里面取出log然后processing, 这个用来处理log的工具可以Storm or Spark,对么
？

b*52015-10-19 07:10

23 楼

yes, lots of big data processing follows this template. some signal. in
this case, errors, generated and got put on kafka. storm/spark processes,
and whatever got processed then got put into Nosql database

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

: 不懂kafka,打算去看看了解一下。不过我理解好虫你的意思是说，server(producer)把
: 产生的log直接丢到Kafka Q里面，然后有一个dedicated cluster(consumer)不断的从
: queue里面取出log然后processing, 这个用来处理log的工具可以Storm or Spark,对么
: ？

y*s2015-10-19 07:10

24 楼

多谢楼上各位大牛的建议，学习到了很多

g*g2015-10-19 07:10

25 楼

扔进C*，最多上面再加一层memcache/redis就是了。

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

: 这夸center怎么办啊？能再说说吗？

h*02015-10-19 07:10

26 楼

我二逼了。。说错了。。就是cluster的意思。。

cluster

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

: scale up不是一个好的设计啊，应该是scale out, central server应该是一个cluster
: ,否则你会有single point failure问题啊
: 不过我还是觉得楼上说的要去看kafka是正解

o*02015-10-19 07:10

27 楼

如果工作中没用到过kafka,redis, storm/spark之类的热门东西，面试design题时，说
要用它们解决，能行吗？问深了，会不会露馅？

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

: 扔进C*，最多上面再加一层memcache/redis就是了。