一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1714|回复: 14
收起左侧

[系统设计/OOD] 问一道经典系统设计题

[复制链接] |试试Instant~ |关注本帖
ningchris 发表于 2015-12-15 00:29:13 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
有一个网站 会log 所有访问过该网站的ip address (streaming data)   有什么方法是可以弹出top 10 ip address (real time)?

我想到的方法是 用hash map记录所有的ip address 的发生次数 然后把所有东西都丢进heap 里边 然后可以弹出top 10
但是 解决不了 real time
就是说我每次都要建一个new heap

请问大家有什么方法?
staycrazy 发表于 2016-2-2 07:16:02 | 显示全部楼层
如果真的是system design的话,说把所有信息都放在一个heap或者map里面的这种解决方案会让面试官觉得你缺少实际的工程经验,除非这个面试官也是从网上道听途说这样一个题目的junior engineer.

作为一个严肃的可以操作的系统,你需要考虑这么几个方面:
1. 数据持久化(persistent) (历史数据的查询,以及服务器crash之后的重新恢复)
2. 可扩展性(extensibility)
3. 实时性(realtime) 与误差的trade off
4. 稳定性(stability)
5. 可用性(availability)
6. scalability - 这点存疑一下,因为需求并不明确

先考虑最原始但是可用的方法以及其中的几个关键点。

考虑到availability和stability,首先你不能有single point of failure。你要有一个分布式的队列服务,即使你的后端服务器crash,也不会丢失现在正在产生的数据。在你的服务器重新上线之后,可以继续处理在队列中累积的数据。这里的队列服务可用kafka或者kinesis.

persistent layer,因为我们这里先讲最原始的办法,我们只考虑用relational database。把所有data都存在一个地方显然是比较蠢的办法。比较理性的做法是按照IP hash,然后无论你是partition也好,还是干脆就分不同的table也好(因为IP的key空间是钉死的),把他们分到不同的服务器上去均衡负载。你的database server要有备份。要有slave,当master下线时slave仍然可以提供只读服务。

你的服务层要有redundancy, 一台机器因故下线了还可以有其它的顶住。

查询时从每个database查询top 10然后一个heap来merge result就好了。

上面这个解决方案是基本可行的,基于ip address的空间并不是很大,Oracle的db可以支持上G的table问题不大,你partition个四五次就还可以支持。

当然也有问题,比如说,写操作会很频繁,我们需要cache多次访问记录然后batch update,这里就涉及到了稳定性问题,因为你在什么地方cache这个中间结果,什么地方就有可能出问题,出了问题你就会丢数据。而在cache和真正写之间,也会有accuracy的问题。

所以如果要处理非常大的数据两,需要稍微fancy一点的解决方案。

比如说后端数据库,可以换用任何一种key-value store,或者推到极致,我们只需要raw访问记录。

然后将访问记录持久化到我们的分布式文件系统中,比如HDFS。这里能解决的是后端数据库的scale问题。我们需要周期性地在这个文件系统上跑Map-Reduce job,以获得更新的记录。然而要注意的是MR是非常慢的一个过程,通过MR sort算出来的结果往往是几个小时之前的了。Anyway到这个point,我们能够获得一个几小时前的访问频率的排名。

然后近几个小时中的访问频率,我们可以用apache storm来做stream处理,在服务层和之前MR预处理过的结果combine起来(一共才4G个条目,这里因为我们所有的历史结果都已经persistent,所以顶楼提到的内存处理方法是可行的——可以用数台机器,每台返回其上的前10,最后combine),得到最终的结果。

上面这种表述才是一个基本的system design。

评分

1

查看全部评分

回复 支持 3 反对 1

使用道具 举报

readman 发表于 2015-12-15 03:17:55 | 显示全部楼层
top k frequent items is the one of fundamental problem in data streaming.

LoosyCounting | Spacesaving   are two basic approaches

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-12-18 10:30:33 | 显示全部楼层
不需要把所有的IP放入heap,只要放前10个就行(即heap.size() == 10)。在heap中的就是top 10,不在的就是不是。

每次新得到一个IP,先在hash map中将其出现次数+1,然后看其是否已经在heap中:

如果在的话,则调整其在heap中的位置(re-heapify)即可。因为既然它本来就是top 10,那么增加1以后它一定还是top 10,而其他top 9也依然一定还在top 10中;
如果不在heap中,那么有可能因为增加了1以后使其能够进入top 10. 这时只要拿这个IP的出现次数和heap.top()比较,如果前者较大,那么就删除heap.top(),把新出现的这个IP插入heap即可,否则不做任何操作。

注意这里的heap是min-heap。
回复 支持 1 反对 0

使用道具 举报

 楼主| ningchris 发表于 2015-12-15 03:35:18 | 显示全部楼层
readman 发表于 2015-12-15 03:17
top k frequent items is the one of fundamental problem in data streaming.

LoosyCounting | Spacesa ...

thank you thank you thank you!!!!
回复 支持 反对

使用道具 举报

 楼主| ningchris 发表于 2015-12-19 00:47:02 | 显示全部楼层
stellari 发表于 2015-12-18 10:30
不需要把所有的IP放入heap,只要放前10个就行(即heap.size() == 10)。在heap中的就是top 10,不在的就是 ...

我当时回答的思路大概是这样 但是考官就说 you are still storing in the hash map. given millions of ip address, what are you going to do?
回复 支持 反对

使用道具 举报

readman 发表于 2015-12-19 00:49:46 | 显示全部楼层
ningchris 发表于 2015-12-19 00:47
我当时回答的思路大概是这样 但是考官就说 you are still storing in the hash map. given millions of i ...

不能都存的..所以要用support来表示"我们关注的数据"
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-12-19 02:31:33 | 显示全部楼层
readman 发表于 2015-12-19 00:49
不能都存的..所以要用support来表示"我们关注的数据"

什么是support
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-12-19 02:39:56 | 显示全部楼层
readman 发表于 2015-12-15 03:17
top k frequent items is the one of fundamental problem in data streaming.

LoosyCounting | Spacesa ...

能不能说说这个题具体应该怎么做呢  谢谢
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-20 03:32:31 | 显示全部楼层
readman 发表于 2015-12-15 03:17
top k frequent items is the one of fundamental problem in data streaming.

LoosyCounting | Spacesa ...

这两个应该都是approximate的算法,如果面试data scientist估计可以,面试码农的话,我还是会坚持我的approach。
我觉得这种topk就是维护两个bst,一个是key到出现次数的映射,另一个是出现次数到key的映射,所以第二个是multimap,允许出现相同的key,这样的话,每次update一个key的count,只需要分别在两个map里面找到各自的位置,分别update。
如果用heap来维护,问题关键在于没法update一个key,搜索起来太麻烦,但是bst都是保证lgN。
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-20 03:38:34 | 显示全部楼层
stellari 发表于 2015-12-18 10:30
不需要把所有的IP放入heap,只要放前10个就行(即heap.size() == 10)。在heap中的就是top 10,不在的就是 ...

这个方法最大的问题是,有些面试题貌似会问如何expire data,比如,它让你求最近10分钟的top10,也就是说,先前的东西需要expire,意味着要减去一些count,如果在hash表里面减去count的话,拿去和heap比较,heap可能也就不再是维护10个top了,这个怎么处理呢?
回复 支持 反对

使用道具 举报

readman 发表于 2015-12-21 12:54:59 | 显示全部楼层
returning 发表于 2015-12-20 03:32
这两个应该都是approximate的算法,如果面试data scientist估计可以,面试码农的话,我还是会坚持我的app ...

近似算法现在越来越重要了吧..为什么码农就不行了..本来存map就很容易溢出..
回复 支持 反对

使用道具 举报

hszz88 发表于 2016-1-23 16:36:21 | 显示全部楼层
returning 发表于 2015-12-20 03:32
这两个应该都是approximate的算法,如果面试data scientist估计可以,面试码农的话,我还是会坚持我的app ...

IP address 不能按 三位 三位 来分map吗。。。 类似于 trie
回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-25 09:07:31 | 显示全部楼层
hszz88 发表于 2016-1-23 16:36
IP address 不能按 三位 三位 来分map吗。。。 类似于 trie

IPv4的话,一个int就装下了。如果不要求“IP前缀查询”这种功能,把IP拆成三位一段没有什么实际意义吧。
回复 支持 反对

使用道具 举报

hszz88 发表于 2016-1-28 15:22:44 | 显示全部楼层
stellari 发表于 2016-1-25 09:07
IPv4的话,一个int就装下了。如果不要求“IP前缀查询”这种功能,把IP拆成三位一段没有什么实际意义吧。

MAP不能开太大 但是你可以开好几个map
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 18:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表