系统设计题(30分)
某流量监控系统每天生成大量的数据记录，每条记录 包括url,访问IP,时间，这些数据记录需要进行存储和维护，并提供查询。请设计一个系统能够存储和维护1000亿条数据，实现实时监控，并能支持一下两种查询：
1.指定任意一个时间段(精确到分钟)和某个ip,查出该时段内该ip的总访问量。
2.指定任意一个时间段(精确到分钟)和某个url,查出该时段内对该url的总访问量。下面是当时笔试的一些思路，具体细节不太记得了。
1.很多地方都见到这道题，extern "c"是指将该段代码以C语言形式进行编译、链接。由于C不支持函数重载，C与C++对于同一函数进行编译后在符号表中保存的函数名存在差异，故当进行C、C++混编时会出现一些问题。
2.记得上学期还特意去借了一本《设计模式》书来看，翻是翻了几下，结果啥也没记住，这题直接空了。对于设计模式记得最深的一句就是"过分在意设计模式会阻碍你的创新思维"。
3.前段时间腾讯笔试时有道选择题也是考TCP的几个状态，当时做错了。回来后看了下TCP的连接和释放，这次还真用上了。time_wait是TCP释放四次握手中的一个状态，当第三次握手完成时，即客户端收到来自服务器的FIN后，再发送一个ACK,客户便开始了time_wait状态。
同时一个记时器开始记时，当达到2倍一个报文段在因特网中最大的生存期时代表超时。如果在超时前客户端再次收到FIN，则表示是服务器重发的FIN,客户端需重发送ACK。
4.依题目得知是求有向图的一个拓扑序列。
5.直接扫描一遍。
int count_prefect_sentence(string str) { int i = 0, cnt = 0, hasOneLetter = 0; while(str[i]) { if(str[i] == '.') { if(hasOneLetter) cnt++; hasOneLetter = 0; } else if(isalpha(str[i])) hasOneLetter = 1; i++; } return cnt; }
6.海量数据处理题，当时花了很长时间在想这两题，感觉没有想到什么好的思路。这样的系统应当是实时性优先吧，在时间空间上首先考虑时间。
a、建个二维映射Map[time].bitset\, time代表某一时间点，将时间点表示为
时间秒差数字作为映射索引。第二维考虑bitset的方式, 建立一个2^32(整型的最大位数)的数组(bitset),每一个bit位0或1代表该位上代表的IP整数是否访问过. 统计时枚举每个时间点，再按位和indexIP进行与运算进行统计，时间效率应该不差。以保存30天为例，空间为(30*24*3600)*(2^32)bit = 2^50B = 1000TB = 1PB
b、时间以分钟为单位，第二维直接为IP, 映射值为该分钟访问量。(30*24*60)*(2^32)B= 2^50B = 1000TB = 1PB
7、映射Map[url][time],将url进行字符串hash，再进行枚举统计。
这两题如果做成两维映射，内存吃不消，既然两题中的一维是已经指定的，变化的只是时间段，因此可以用一维表示，先预处理，再进行统计。
Read full article from 系统设计题
No comments:
Post a Comment