機械工程師英語面試
應屆生在面試的時候，大公司偶爾也會遇到一些系統設計題，而這些題目往往只是考一下你的知識面，或者對系統架構方面的瞭解，不會涉及編碼。很多人感覺難以應對這樣的題目，也不知道從何說起，在本文中，總結了回答這類題目需要哪些基礎知識，以及怎樣使用這些知識回答這些問題。
在正式介紹基礎知識之前，先羅列幾個常見的系統設計相關的筆試面試題：
(1)(百度)要求設計一個DNS的Cache結構，要求能夠滿足每秒5000以上的查詢，滿足IP資料的快速插入，查詢的速度要快。(題目還給出了一系列的資料，比如：站點數總共為5000萬，IP地址有1000萬，等等)
解決方案：DNS伺服器實現域名到IP地址的轉換。
每個域名的平均長度為25個位元組(在域名的命名標準中，對於域名長度是有明顯限制的。其中，中國國家域名不得超過20個字元，國際通用域名不得超過26個字元)，每個IP為4個位元組，所以Cache的每個條目需要大概30個位元組。
總共50M個條目，所以需要1.5G個位元組的空間。可以放置在記憶體中。(考慮到每秒5000次操作的限制，也只能放在記憶體中。)
可以考慮的資料結構包括hash_map，字典樹，紅黑樹等等。
我覺得比較好的解決方法是，將每一個URL字串轉化為MD5值，作為key，建立最大或最小堆，這樣插入和查詢的效率都是O(log(n))。
MD5是128bit的大整數也就是16byte，比直接存放URL要節省的多。
具體可應用方法：每秒5000的查詢不算高啊，最土的方法使用MySQL+Memcached架構應該都能滿足吧?
資料結構建議以域名的md5值為主鍵來儲存，值可以只儲存目標IP就行。Memcached使用者支撐前端查詢，MySQL使用者儲存資料，還要看總數量會有多大，如果不是特別大，直接使用MyISAM引擎來儲存就行，更新插入都非常快，如果超千萬，可以使用InnoDB來儲存，每次有新資料插入時直接使用replace into table就行，Memcached資料的更新直接使用set。
Memcached隨便用得好些，每秒上萬次的get是容易達到的，MySQL你別小看，在有的測試裡，以主鍵查詢的測試，一臺普通的伺服器上，MySQL/InnoDB 5.1伺服器上獲得了750000+QPS的成績。
總結：關於高併發系統設計。主要有以下幾個關鍵技術點：快取，索引，資料分片，鎖粒度儘可能小。。
(2)有N臺機器，M個檔案，檔案可以以任意方式存放到任意機器上，檔案可任意分割成若干塊。假設這N臺機器的宕機率小於1/3，想在宕機時可以從其他未宕機的機器中完整匯出這M個檔案，求最好的存放與分割策略。
解決方案：涉及到現在通用的分散式檔案系統的副本存放策略。一般是將大檔案切分成小的block(如64MB)後，以block為單位存放三份到不同的節點上，這三份資料的位置需根據網路拓撲結構配置，一般而言，如果不考慮跨資料中心，可以這樣存放：兩個副本存放在同一個機架的不同節點上，而另外一個副本存放在另一個機架上，這樣從效率和可靠性上，都是最優的(這個google公佈的文件中有專門的證明，有興趣的可參閱一下。)。如果考慮跨資料中心，可將兩份存在一個數據中心的不同機架上，另一份放到另一個數據中心。
(3)假設有三十臺伺服器，每個上面都存有上百億條資料(有可能重複)，如何找出這三十臺機器中，根據某關鍵字，重複出現次數最多的前100條?要求用Hadoop來做。
方案：針對每一臺機器有100億，類似100萬時的處理方法，對資料進行切片，可以都切為100萬的記錄，對100萬、取最前100，不同在於這前100也存入hash，如果key相同則合併value，顯然100億的資料分割完後的處理結果也要再進行類似的處理，hash表不能過長，原理其實也就是map和reduce。然後合併這30臺機器的結果。
(4)設計一個系統，要求寫速度儘可能高，說明設計原理。
解決方案：涉及到BigTable的模型。主要思想是將隨機寫轉化為順序寫，進而大大提高寫速度。具體是：由於磁碟物理結構的獨特設計，其併發的隨機寫(主要是因為磁碟尋道時間長)非常慢，考慮到這一點，在BigTable模型中，首先會將併發寫的大批資料放到一個記憶體表(稱為“memtable”)中，當該表大到一定程度後，會順序寫到一個磁碟表(稱為“SSTable”)中，這種寫是順序寫，效率極高。說到這，可能有讀者問，隨機讀可不可以這樣優化?答案是：看情況。通常而言，如果讀併發度不高，則不可以這麼做，因為如果將多個讀重新排列組合後再執行，系統的響應時間太慢，使用者可能接受不了，而如果讀併發度極高，也許可以採用類似機制。
(5)設計一個高併發系統，說明架構和關鍵技術要點。
方案：分散式系統中的核心的伺服器的實現。可以是http伺服器，快取伺服器，分散式檔案系統等的內部實現。下邊主要從一個高併發的大型網站出發，看一個高併發系統的設計。下邊是一個高併發系統的邏輯結構：
1)快取系統：快取是每一個高併發，高可用系統不可或缺的模組。常見的快取系統：Squid(前端快取)、Ehcache(物件快取系統)，動態頁面靜態化(頁面快取)
2)負載均衡系統：負載均衡策略有隨機分配，平均分配，分散式一致性hash等。軟體負載均衡有：基於DNS的負載均衡、基於LVS的負載均衡和基於lptables的負載均衡。硬體負載均衡：路由上配置nat實現負載均衡、對萬網一個虛擬ip，內網對映幾個內網ip。資料庫負載均衡：資料庫叢集等。
(6)有25T的log(query->queryinfo)，log在不段的增長，設計一個方案，給出一個query能快速返回queryinfo?
方案：1)建立適當索引;2)優化sql語句;3)實現小資料量和海量資料的通用分頁顯示儲存過程;4)合理選擇聚集索引
以上所有問題中凡是不涉及高併發的，基本可以採用google的三個技術解決，分別為：GFS，MapReduce，Bigtable，這三個技術被稱為“google三駕馬車”，google只公開了論文而未開原始碼，開源界對此非常有興趣，仿照這三篇論文實現了一系列軟體，如：Hadoop、HBase、HDFS、Cassandra等。
在google這些技術還未出現之前，企業界在設計大規模分散式系統時，採用的架構往往是database+sharding+cache，現在很多公司(比如taobao，)仍採用這種架構。在這種架構中，仍有很多問題值得去探討。如採用什麼資料庫，是SQL界的MySQL還是NoSQL界的`Redis/TFS，兩者有何優劣? 採用什麼方式sharding(資料分片)，是水平分片還是垂直分片?據網上資料顯示，和taobao圖片儲存中曾採用的架構是Redis/MySQL/TFS+sharding+cache，該架構解釋如下：前端cache是為了提高響應速度，後端資料庫則用於資料永久儲存，防止資料丟失，而sharding是為了在多臺機器間分攤負載。最前端由大塊大塊的cache組成，要保證至少99%(該資料在架構中的是自己猜的，而taobao圖片儲存模組是真實的)的訪問資料落在cache中，這樣可以保證使用者訪問速度，減少後端資料庫的壓力，此外，為了保證前端cache中資料與後端資料庫中資料一致，需要有一箇中間件非同步更新(為啥非同步?理由簡單：同步代價太高。非同步有缺定，如何彌補?)資料，這個有些人可能比較清楚，新浪有個開源軟體叫memcachedb(整合了Berkeley DB和Memcached)，正是完成此功能。另外，為了分攤負載壓力和海量資料，會將使用者微博資訊經過片後存放到不同節點上(稱為“sharding”)。
這種架構優點非常明顯：簡單，在資料量和使用者量較小的時候完全可以勝任。但缺定早晚一天暴露出來，即：擴充套件性和容錯性太差，維護成本非常高，尤其是資料量和使用者量暴增之後，系統不能通過簡單的增加機器解決該問題。
於是乎，新的架構便出現了。主要還是google的那一套東西，下面分別說一下：
GFS是一個可擴充套件的分散式檔案系統，用於大型的、分散式的、對大量資料進行訪問的應用。它運行於廉價的普通硬體上，提供容錯功能。現在開源界有HDFS(Hadoop Distributed File System)，該檔案系統雖然彌補了資料庫+sharding的很多缺點，但自身仍存在一些問題，比如：由於採用master/slave架構，因而存在單點故障問題;元資料資訊全部存放在master端的記憶體中，因而不適合儲存小檔案，或者說如果儲存的大量小檔案，那麼儲存的總資料量不會太大。
MapReduce是針對分散式並行計算的一套程式設計模型。他最大的優點是：程式設計介面簡單，自動備份(資料預設情況下會自動備三份)，自動容錯和隱藏跨機器間的通訊。在Hadoop中，MapReduce作為分佈計算框架，而HDFS作為底層的分散式儲存系統，但MapReduce不是與HDFS耦合在一起的，你完全可以使用自己的分散式檔案系統替換掉HDFS。當前MapReduce有很多開源實現，如Java實現Hadoop MapReduce，C++實現Sector/sphere等，甚至有些資料庫廠商將MapReduce整合到資料庫中了。
BigTable俗稱“大表”，是用來儲存結構化資料的，個人覺得，BigTable在開源界最火爆，其開源實現最多，包括：HBase，Cassandra，levelDB等，使用也非常廣泛。
除了google的這三家馬車，還有其他一些技術：
Dynamo：亞馬遜的key-value模式的儲存平臺，可用性和擴充套件性都很好，採用DHT(Distributed Hash Table)對資料分片，解決單點故障問題，在Cassandra中，也借鑑了該技術，在BT和電驢的中，也採用了類似演算法。
虛擬節點技術：該技術常用於分散式資料分片中。具體應用場景是：有一大坨資料(maybe TB級或者PB級)，我們需按照某個欄位(key)分片儲存到幾十(或者更多)臺機器上，同時想盡量負載均衡且容易擴充套件。傳統的做法是：Hash(key) mod N，這種方法最大缺點是不容易擴充套件，即：增加或者減少機器均會導致資料全部重分佈，代價忒大。於是乎，新技術誕生了，其中一種是上面提到的DHT，現在已經被很多大型系統採用，還有一種是對“Hash(key) mod N”的改進：假設我們要將資料分不到20臺機器上，傳統做法是hash(key) mod 20，而改進後，N取值要遠大於20，比如是20000000，然後我們採用額外一張表記錄每個節點儲存的key的模值，比如：
node1：0~1000000
node2：1000001~2000000
。。。。。。
這樣，當新增一個新的節點時，只需將每個節點上部分資料移動給新節點，同時修改一下這個表即可。
Thrift：Thrift是一個跨語言的RPC框架，分別解釋一下“RPC”和“跨語言”，RPC是遠端過程呼叫，其使用方式與呼叫一個普通函式一樣，但執行體發生在遠端機器上。跨語言是指不同語言之間進行通訊，比如c/s架構中，server端採用C++編寫，client端採用PHP編寫，怎樣讓兩者之間通訊，thrift是一種很好的方式。
