幾個典型場景的系統設計解決方案

（1）gfs一緻性模型

gfs一緻性模型是一個可擴充的分布式檔案系統，用于大型的、分布式的、對大量資料進行通路的應用。

它運作于廉價的普通硬體上，提供容錯功能。現在開源界有hdfs(hadoop distributed file system)。

（2）mapreduce

mapreduce是針對分布式并行計算的一套程式設計模型。最大的優點是程式設計接口簡單，自動備份（資料預設情況下會自動備三份），自動容錯和隐藏跨機器間的通信。在hadoop中，mapreduce作為分布計算架構，而hdfs作為底層的分布式存儲系統，但mapreduce不是與hdfs耦合在一起的，完全可以使用自己的分布式檔案系統替換掉hdfs。目前mapreduce有很多開源實作，如java實作hadoop mapreduce，c++實作sector/sphere等。

（3）bigtable

bigtable是用來存儲結構化資料的，是非關系型資料庫，是一個稀疏的、分布式的、持久化存儲的多元度排序map。bigtable的設計目的是快速且可靠地處理pb級别的資料，并且能夠部署到上千台機器上。實作包括hbase，cassandra，leveldb等，使用也非常廣泛。

1.設計一個系統，要求寫速度盡可能高，說明設計原理。

解決方案：涉及到bigtable的模型。主要思想是将随機寫轉化為順序寫，進而大大提高寫速度。

由于磁盤實體結構的獨特設計，其并發的随機寫（主要是因為磁盤尋道時間長）非常慢，考慮到這一點，在bigtable模型中，首先會将并發寫的大批資料放到一個記憶體表（稱為“memtable”）中，當該表大到一定程度後，會順序寫到一個磁盤表（稱為“sstable”）中，這種寫是順序寫，效率極高。

随機讀可不可以這樣優化？

通常而言，如果讀并發度不高，則不可以這麼做，因為如果将多個讀重新排列組合後再執行，系統的響應時間太慢，使用者可能接受不了，而如果讀并發度極高，也許可以采用類似機制。

2.有25t的log(query->queryinfo)，log在不段的增長，設計一個方案，給出一個query能快速傳回queryinfo？

解決方案：

（1）建立适當索引

（2）優化sql語句

（3）實作小資料量和海量資料的通用分頁顯示存儲過程

（4）合理選擇聚集索引

3.每個城市的ip段是固定的，有十萬個ip段，輸入ip，如何快速找出它是哪個城市的，設計并實作。

4.設計相應的資料結構和算法，盡量高效的統計一篇英文文章（總單詞數目）裡出現的所有英文單詞，按照在文章中首次出現的順序列印輸出該單詞和它的出現次數。

5.有幾百億的整數，分布的存儲到幾百台通過網絡連接配接的計算機上，能否開發出一個算法和系統，找出這幾百億資料的中值？

就是在一組排序好的資料中居于中間的數。由于實體記憶體限制，一台機器裝不下所有的資料，并且盡量少用網絡帶寬，減少機器間網絡傳輸。

6.假設已有10萬個敏感詞，現給你50個單詞，查詢這50個單詞中是否有敏感詞。

解決方案：要判斷這50個單詞是否存在那10萬個敏感詞庫裡，明顯是字元串比對，由于是判斷多個單詞不是一個，屬于多模式字元串比對問題，

多模式字元串比對問題的算法包括kmp、hash、trie、ac自動機等。

選擇哪種算法需要根據題目的應用場景而定。

10萬 + 50，如果允許誤差的話，可以考慮使用布隆過濾器；否則，隻查一次的話，可能hash最快，但hash消耗空間大，考慮tire樹的話，可以針對這10萬個敏感詞建立trie樹，然後對那50個單詞搜尋這棵10萬敏感詞建構的tire樹，但用tire樹同樣耗費空間。

7.假設某個網站每天有超過10億次的頁面通路量，出于安全考慮，網站會記錄通路用戶端通路的ip位址和對應的時間，如果現在已經記錄了1000億條資料，想統計一個指定時間段内的區域ip位址通路量，那麼這些資料應該按照何種方式來組織，才能盡快滿足上面的統計需求呢？

設計完方案後，并指出該方案的優缺點，比如在什麼情況下，可能會非常慢？

解決方案：用b+樹來組織，非葉子節點存儲（某個時間點，頁面通路量），葉子節點是通路的ip位址。

這個方案的優點是查詢某個時間段内的ip通路量很快，但是要統計某個ip的通路次數或是上次通路時間就不得不周遊整個樹的葉子節點。

或者可以建立二級索引，分别是時間和地點來建立索引。

8.給你10台機器，每個機器2個cpu和2gb記憶體，現在已知在10億條記錄的資料庫裡執行一次查詢需要5秒，問用什麼方法能讓90%的查詢能在100毫秒以内傳回結果。

解決方案：将10億條記錄排序，然後分到10個機器中，分的時候是一個記錄一個記錄的輪流分，確定每個機器記錄大小分布差不多，每一次查詢時，同時送出給10台機器，同時查詢，因為記錄已排序，可以采用二分法查詢。

如果無排序，隻能順序查詢，那就要看記錄本身的機率分布，否則不可能實作。畢竟一個機器2個cpu未必能起到作用，要看這兩個cpu能否并行存取記憶體，取決于系統架構。

9.搜尋關鍵詞智能提示

搜尋框中，輸入“北京”，搜尋框下面會以北京為字首，展示“北京愛情故事”、“北京公交”、“北京醫院”等等搜尋詞，

請問，如何設計此系統，使得空間和時間複雜度盡量低。

解決方案：簡單直接的方法是：用trie樹存儲大量字元串，當字首固定時，存儲相對來說比較熱的字尾。

然後用hashmap+堆，統計出如10個近似的熱詞，也就是說，隻存與關鍵詞近似的比如10個熱詞。

10.某伺服器流量統計器，每天有1000億的通路記錄資料，包括時間、url、ip。設計系統實作記錄資料的儲存、管理、查詢。要求能實作以下功能：

計算在某一時間段（精确到分）時間内的，某url的所有通路量。

計算在某一時間段（精确到分）時間内的，某ip的所有通路量。

11.有n個伺服器，為了友善使用者的通路會在伺服器上緩存資料，是以使用者每次通路的時候最好能保持同一台伺服器。

已有的做法是根據serveripindex[num%n]得到請求的伺服器，這種方法很友善将使用者分到不同的伺服器上去。但是如果一台伺服器死掉了，那麼n就變為了n-1，那麼serveripindex[num%n]與serveripindex[num%(n-1)]基本上都不一樣了，是以大多數使用者的請求都會轉到其他伺服器，這樣會發生大量通路錯誤。

如何改進或者換一種方法，使得：

一台伺服器死掉後，不會造成大面積的通路錯誤，

原有的通路基本還是停留在同一台伺服器上；

盡量考慮負載均衡。

12.類似九宮格鍵盤，上面有1到9個數字，每個數字都代表幾個字母（比如1代表abc三個字母，z代表wxyz等等），現在要求設計當輸入某幾個數字的組合時，查找出通訊錄中的人名及電話号碼。

13.http伺服器會在使用者通路某一個檔案的時候，記錄下該檔案被通路的日志，管理者都會去統計每天每檔案被通路的次數。程式設計實作周遊整個日志檔案，計算出每個檔案被通路的通路次數。

14.線上推送服務，同時為10萬個使用者提供服務，對于每個使用者服務從10萬首歌的曲庫中為他們随機選擇一首，同一使用者不能推送重複的，設計方案，記憶體盡可能小，寫出資料結構與算法。

15.請設計一個排隊系統，類似的應用場景非常多，能夠讓每個進入隊伍的使用者都能看到自己在隊列中所處的位置和變化，隊伍可能随時有人加入和退出；當有人退出影響到使用者的位置排名時需要及時回報到使用者。

16.設計一種使用者登入驗證手段，例如銀行登入系統，這個裝置顯示6位數字，每60秒變一次，再經過伺服器認證，通過則允許登入，如何設計和實作。

系統設計思路？伺服器端為何能有效認證動态密碼的正确性？

如果是千萬量級永固，給出系統設計圖示或說明，要求子功能子產品劃厘清晰，給出關鍵的資料結構或資料庫表結構。 考慮使用者量級的影響和擴充性，使用者密碼的随機性等，如果設計系統以支援這幾個因素：

系統算法更新時，伺服器端和裝置端可能都要有所修改，如何設計系統，能夠使得更新過程（包括可能的裝置替換或重設）盡量平滑？