系統(tǒng)設(shè)計題
系統(tǒng)設(shè)計題(30分)
某流量監(jiān)控系統(tǒng)每天生成大量的數(shù)據(jù)記錄，每條記錄 包括url,訪問IP,時間，這些數(shù)據(jù)記錄需要進(jìn)行存儲和維護(hù)，并提供查詢，
系統(tǒng)設(shè)計題
。請設(shè)計一個系統(tǒng)能夠存儲和維護(hù)1000億條數(shù)據(jù)，實現(xiàn)實時監(jiān)控，并能支持一下兩種查詢：1.指定任意一個時間段(精確到分鐘)和某個ip,查出該時段內(nèi)該ip的總訪問量。
2.指定任意一個時間段(精確到分鐘)和某個url,查出該時段內(nèi)對該url的總訪問量。下面是當(dāng)時筆試的一些思路，具體細(xì)節(jié)不太記得了。
1.很多地方都見到這道題，extern “c”是指將該段代碼以C語言形式進(jìn)行編譯、鏈接。由于C不支持函數(shù)重載，C與C++對于同一函數(shù)進(jìn)行編譯后在符號表中保存的函數(shù)名存在差異，故當(dāng)進(jìn)行C、C++混編時會出現(xiàn)一些問題。
2.記得上學(xué)期還特意去借了一本《設(shè)計模式》書來看，翻是翻了幾下，結(jié)果啥也沒記住，這題直接空了。對于設(shè)計模式記得最深的一句就是“過分在意設(shè)計模式會阻礙你的創(chuàng)新思維”。
3.前段時間騰訊筆試時有道選擇題也是考TCP的幾個狀態(tài)，當(dāng)時做錯了�；貋砗罂戳讼耇CP的'連接和釋放，這次還真用上了。time_wait是TCP釋放四次握手中的一個狀態(tài)，當(dāng)?shù)谌挝帐滞瓿蓵r，即客戶端收到來自服務(wù)器的FIN后，再發(fā)送一個ACK,客戶便開始了time_wait狀態(tài)。
同時一個記時器開始記時，當(dāng)達(dá)到2倍一個報文段在因特網(wǎng)中最大的生存期時代表超時。如果在超時前客戶端再次收到FIN，則表示是服務(wù)器重發(fā)的FIN,客戶端需重發(fā)送ACK。
4.依題目得知是求有向圖的一個拓?fù)湫蛄小?/p>
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.海量數(shù)據(jù)處理題，當(dāng)時花了很長時間在想這兩題，感覺沒有想到什么好的思路，
資料共享平臺
《系統(tǒng)設(shè)計題》(http://www.msguai.com)。這樣的系統(tǒng)應(yīng)當(dāng)是實時性優(yōu)先吧，在時間空間上首先考慮時間。a、建個二維映射Map[time].bitset\, time代表某一時間點，將時間點表示為
時間秒差數(shù)字作為映射索引。第二維考慮bitset的方式, 建立一個2^32(整型的最大位數(shù))的數(shù)組(bitset),每一個bit位0或1代表該位上代表的IP整數(shù)是否訪問過. 統(tǒng)計時枚舉每個時間點，再按位和indexIP進(jìn)行與運算進(jìn)行統(tǒng)計，時間效率應(yīng)該不差。以保存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進(jìn)行字符串hash，再進(jìn)行枚舉統(tǒng)計。
這兩題如果做成兩維映射，內(nèi)存吃不消，既然兩題中的一維是已經(jīng)指定的，變化的只是時間段，因此可以用一維表示，先預(yù)處理，再進(jìn)行統(tǒng)計。
【系統(tǒng)設(shè)計題】相關(guān)文章：
1.數(shù)據(jù)系統(tǒng)系統(tǒng)判斷題
4.設(shè)計題