機械工程師英語面試

應(yīng)屆生在面試的時候，大公司偶爾也會遇到一些系統(tǒng)設(shè)計題，而這些題目往往只是考一下你的知識面，或者對系統(tǒng)架構(gòu)方面的了解，不會涉及編碼。很多人感覺難以應(yīng)對這樣的題目，也不知道從何說起，在本文中，總結(jié)了回答這類題目需要哪些基礎(chǔ)知識，以及怎樣使用這些知識回答這些問題。

在正式介紹基礎(chǔ)知識之前，先羅列幾個常見的系統(tǒng)設(shè)計相關(guān)的筆試面試題：

(1)(百度)要求設(shè)計一個DNS的Cache結(jié)構(gòu)，要求能夠滿足每秒5000以上的查詢，滿足IP數(shù)據(jù)的快速插入，查詢的速度要快。(題目還給出了一系列的數(shù)據(jù)，比如：站點數(shù)總共為5000萬，IP地址有1000萬，等等)

解決方案：DNS服務(wù)器實現(xiàn)域名到IP地址的轉(zhuǎn)換。

每個域名的平均長度為25個字節(jié)(在域名的命名標準中，對于域名長度是有明顯限制的。其中，中國國家域名不得超過20個字符，國際通用域名不得超過26個字符)，每個IP為4個字節(jié)，所以Cache的每個條目需要大概30個字節(jié)。

總共50M個條目，所以需要1.5G個字節(jié)的空間。可以放置在內(nèi)存中。(考慮到每秒5000次操作的限制，也只能放在內(nèi)存中。)

可以考慮的數(shù)據(jù)結(jié)構(gòu)包括hash_map，字典樹，紅黑樹等等。

我覺得比較好的解決方法是，將每一個URL字符串轉(zhuǎn)化為MD5值，作為key，建立最大或最小堆，這樣插入和查找的效率都是O(log(n))。

MD5是128bit的大整數(shù)也就是16byte，比直接存放URL要節(jié)省的多。

具體可應(yīng)用方法：每秒5000的查詢不算高啊，最土的方法使用MySQL+Memcached架構(gòu)應(yīng)該都能滿足吧?

數(shù)據(jù)結(jié)構(gòu)建議以域名的md5值為主鍵來存儲，值可以只存儲目標IP就行。Memcached用戶支撐前端查詢，MySQL用戶存儲數(shù)據(jù)，還要看總數(shù)量會有多大，如果不是特別大，直接使用MyISAM引擎來存儲就行，更新插入都非常快，如果超千萬，可以使用InnoDB來存儲，每次有新數(shù)據(jù)插入時直接使用replace into table就行，Memcached數(shù)據(jù)的更新直接使用set。

Memcached隨便用得好些，每秒上萬次的get是容易達到的，MySQL你別小看，在有的測試里，以主鍵查詢的測試，一臺普通的服務(wù)器上，MySQL/InnoDB 5.1服務(wù)器上獲得了750000+QPS的成績。

總結(jié)：關(guān)于高并發(fā)系統(tǒng)設(shè)計。主要有以下幾個關(guān)鍵技術(shù)點：緩存，索引，數(shù)據(jù)分片，鎖粒度盡可能小。。

(2)有N臺機器，M個文件，文件可以以任意方式存放到任意機器上，文件可任意分割成若干塊。假設(shè)這N臺機器的宕機率小于1/3，想在宕機時可以從其他未宕機的機器中完整導(dǎo)出這M個文件，求最好的存放與分割策略。

解決方案：涉及到現(xiàn)在通用的分布式文件系統(tǒng)的副本存放策略。一般是將大文件切分成小的block(如64MB)后，以block為單位存放三份到不同的節(jié)點上，這三份數(shù)據(jù)的位置需根據(jù)網(wǎng)絡(luò)拓撲結(jié)構(gòu)配置，一般而言，如果不考慮跨數(shù)據(jù)中心，可以這樣存放：兩個副本存放在同一個機架的不同節(jié)點上，而另外一個副本存放在另一個機架上，這樣從效率和可靠性上，都是最優(yōu)的(這個google公布的文檔中有專門的證明，有興趣的可參閱一下。)。如果考慮跨數(shù)據(jù)中心，可將兩份存在一個數(shù)據(jù)中心的不同機架上，另一份放到另一個數(shù)據(jù)中心。

(3)假設(shè)有三十臺服務(wù)器，每個上面都存有上百億條數(shù)據(jù)(有可能重復(fù))，如何找出這三十臺機器中，根據(jù)某關(guān)鍵字，重復(fù)出現(xiàn)次數(shù)最多的前100條?要求用Hadoop來做。

方案：針對每一臺機器有100億，類似100萬時的處理方法，對數(shù)據(jù)進行切片，可以都切為100萬的記錄，對100萬、取最前100，不同在于這前100也存入hash，如果key相同則合并value，顯然100億的數(shù)據(jù)分割完后的處理結(jié)果也要再進行類似的處理，hash表不能過長，原理其實也就是map和reduce。然后合并這30臺機器的結(jié)果。

(4)設(shè)計一個系統(tǒng)，要求寫速度盡可能高，說明設(shè)計原理。

解決方案：涉及到BigTable的模型。主要思想是將隨機寫轉(zhuǎn)化為順序?qū)懀�進而大大提高寫速度。具體是：由于磁盤物理結(jié)構(gòu)的獨特設(shè)計，其并發(fā)的隨機寫(主要是因為磁盤尋道時間長)非常慢，考慮到這一點，在BigTable模型中，首先會將并發(fā)寫的大批數(shù)據(jù)放到一個內(nèi)存表(稱為“memtable”)中，當(dāng)該表大到一定程度后，會順序?qū)懙揭粋�磁盤表(稱為“SSTable”)中，這種寫是順序?qū)懀�效率極高。說到這，可能有讀者問，隨機讀可不可以這樣優(yōu)化?答案是：看情況。通常而言，如果讀并發(fā)度不高，則不可以這么做，因為如果將多個讀重新排列組合后再執(zhí)行，系統(tǒng)的響應(yīng)時間太慢，用戶可能接受不了，而如果讀并發(fā)度極高，也許可以采用類似機制。

(5)設(shè)計一個高并發(fā)系統(tǒng)，說明架構(gòu)和關(guān)鍵技術(shù)要點。

方案：分布式系統(tǒng)中的核心的服務(wù)器的實現(xiàn)。可以是http服務(wù)器，緩存服務(wù)器，分布式文件系統(tǒng)等的內(nèi)部實現(xiàn)。下邊主要從一個高并發(fā)的大型網(wǎng)站出發(fā)，看一個高并發(fā)系統(tǒng)的設(shè)計。下邊是一個高并發(fā)系統(tǒng)的邏輯結(jié)構(gòu)：

1)緩存系統(tǒng)：緩存是每一個高并發(fā)，高可用系統(tǒng)不可或缺的模塊。常見的緩存系統(tǒng)：Squid(前端緩存)、Ehcache(對象緩存系統(tǒng))，動態(tài)頁面靜態(tài)化(頁面緩存)

2)負載均衡系統(tǒng)：負載均衡策略有隨機分配，平均分配，分布式一致性hash等。軟件負載均衡有：基于DNS的負載均衡、基于LVS的負載均衡和基于lptables的負載均衡。硬件負載均衡：路由上配置nat實現(xiàn)負載均衡、對萬網(wǎng)一個虛擬ip，內(nèi)網(wǎng)映射幾個內(nèi)網(wǎng)ip。數(shù)據(jù)庫負載均衡：數(shù)據(jù)庫集群等。

(6)有25T的log(query->queryinfo)，log在不段的增長，設(shè)計一個方案，給出一個query能快速返回queryinfo?

方案：1)建立適當(dāng)索引;2)優(yōu)化sql語句;3)實現(xiàn)小數(shù)據(jù)量和海量數(shù)據(jù)的通用分頁顯示存儲過程;4)合理選擇聚集索引

以上所有問題中凡是不涉及高并發(fā)的，基本可以采用google的三個技術(shù)解決，分別為：GFS，MapReduce，Bigtable，這三個技術(shù)被稱為“google三駕馬車”，google只公開了論文而未開源代碼，開源界對此非常有興趣，仿照這三篇論文實現(xiàn)了一系列軟件，如：Hadoop、HBase、HDFS、Cassandra等。

在google這些技術(shù)還未出現(xiàn)之前，企業(yè)界在設(shè)計大規(guī)模分布式系統(tǒng)時，采用的架構(gòu)往往是database+sharding+cache，現(xiàn)在很多公司(比如taobao，weibo.com)仍采用這種架構(gòu)。在這種架構(gòu)中，仍有很多問題值得去探討。如采用什么數(shù)據(jù)庫，是SQL界的MySQL還是NoSQL界的Redis/TFS，兩者有何優(yōu)劣? 采用什么方式sharding(數(shù)據(jù)分片)，是水平分片還是垂直分片?據(jù)網(wǎng)上資料顯示，weibo.com和taobao圖片存儲中曾采用的架構(gòu)是Redis/MySQL/TFS+sharding+cache，該架構(gòu)解釋如下：前端cache是為了提高響應(yīng)速度，后端數(shù)據(jù)庫則用于數(shù)據(jù)永久存儲，防止數(shù)據(jù)丟失，而sharding是為了在多臺機器間分攤負載。最前端由大塊大塊的cache組成，要保證至少99%(該數(shù)據(jù)在weibo.com架構(gòu)中的是自己猜的，而taobao圖片存儲模塊是真實的)的訪問數(shù)據(jù)落在cache中，這樣可以保證用戶訪問速度，減少后端數(shù)據(jù)庫的壓力，此外，為了保證前端cache中數(shù)據(jù)與后端數(shù)據(jù)庫中數(shù)據(jù)一致，需要有一個中間件異步更新(為啥異步?理由簡單：同步代價太高。異步有缺定，如何彌補?)數(shù)據(jù)，這個有些人可能比較清楚，新浪有個開源軟件叫memcachedb(整合了Berkeley DB和Memcached)，正是完成此功能。另外，為了分攤負載壓力和海量數(shù)據(jù)，會將用戶微博信息經(jīng)過片后存放到不同節(jié)點上(稱為“sharding”)。

這種架構(gòu)優(yōu)點非常明顯：簡單，在數(shù)據(jù)量和用戶量較小的時候完全可以勝任。但缺定早晚一天暴露出來，即：擴展性和容錯性太差，維護成本非常高，尤其是數(shù)據(jù)量和用戶量暴增之后，系統(tǒng)不能通過簡單的增加機器解決該問題。

于是乎，新的架構(gòu)便出現(xiàn)了。主要還是google的那一套東西，下面分別說一下：

GFS是一個可擴展的分布式文件系統(tǒng)，用于大型的、分布式的、對大量數(shù)據(jù)進行訪問的應(yīng)用。它運行于廉價的普通硬件上，提供容錯功能。現(xiàn)在開源界有HDFS(Hadoop Distributed File System)，該文件系統(tǒng)雖然彌補了數(shù)據(jù)庫+sharding的很多缺點，但自身仍存在一些問題，比如：由于采用master/slave架構(gòu)，因而存在單點故障問題;元數(shù)據(jù)信息全部存放在master端的內(nèi)存中，因而不適合存儲小文件，或者說如果存儲的大量小文件，那么存儲的總數(shù)據(jù)量不會太大。

MapReduce是針對分布式并行計算的一套編程模型。他最大的優(yōu)點是：編程接口簡單，自動備份(數(shù)據(jù)默認情況下會自動備三份)，自動容錯和隱藏跨機器間的通信。在Hadoop中，MapReduce作為分布計算框架，而HDFS作為底層的分布式存儲系統(tǒng)，但MapReduce不是與HDFS耦合在一起的，你完全可以使用自己的分布式文件系統(tǒng)替換掉HDFS。當(dāng)前MapReduce有很多開源實現(xiàn)，如Java實現(xiàn)Hadoop MapReduce，C++實現(xiàn)Sector/sphere等，甚至有些數(shù)據(jù)庫廠商將MapReduce集成到數(shù)據(jù)庫中了。

BigTable俗稱“大表”，是用來存儲結(jié)構(gòu)化數(shù)據(jù)的，個人覺得，BigTable在開源界最火爆，其開源實現(xiàn)最多，包括：HBase，Cassandra，levelDB等，使用也非常廣泛。

除了google的這三家馬車，還有其他一些技術(shù)：

Dynamo：亞馬遜的key-value模式的存儲平臺，可用性和擴展性都很好，采用DHT(Distributed Hash Table)對數(shù)據(jù)分片，解決單點故障問題，在Cassandra中，也借鑒了該技術(shù)，在BT和電驢的中，也采用了類似算法。

虛擬節(jié)點技術(shù)：該技術(shù)常用于分布式數(shù)據(jù)分片中。具體應(yīng)用場景是：有一大坨數(shù)據(jù)(maybe TB級或者PB級)，我們需按照某個字段(key)分片存儲到幾十(或者更多)臺機器上，同時想盡量負載均衡且容易擴展。傳統(tǒng)的做法是：Hash(key) mod N，這種方法最大缺點是不容易擴展，即：增加或者減少機器均會導(dǎo)致數(shù)據(jù)全部重分布，代價忒大。于是乎，新技術(shù)誕生了，其中一種是上面提到的DHT，現(xiàn)在已經(jīng)被很多大型系統(tǒng)采用，還有一種是對“Hash(key) mod N”的改進：假設(shè)我們要將數(shù)據(jù)分不到20臺機器上，傳統(tǒng)做法是hash(key) mod 20，而改進后，N取值要遠大于20，比如是20000000，然后我們采用額外一張表記錄每個節(jié)點存儲的key的模值，比如：

node1：0~1000000

node2：1000001~2000000

。。。。。。

這樣，當(dāng)添加一個新的節(jié)點時，只需將每個節(jié)點上部分數(shù)據(jù)移動給新節(jié)點，同時修改一下這個表即可。

Thrift：Thrift是一個跨語言的RPC框架，分別解釋一下“RPC”和“跨語言”，RPC是遠程過程調(diào)用，其使用方式與調(diào)用一個普通函數(shù)一樣，但執(zhí)行體發(fā)生在遠程機器上。跨語言是指不同語言之間進行通信，比如c/s架構(gòu)中，server端采用C++編寫，client端采用PHP編寫，怎樣讓兩者之間通信，thrift是一種很好的方式。

[機械工程師英語面試]

【機械工程師英語面試】相關(guān)文章：

職場面試機械工程師英語對話08-04

機械工程師面試經(jīng)驗08-04

機械工程師面試技巧07-05

機械工程師面試問題10-05

機械工程師面試自我介紹09-08

職場面試機械工程師對話10-09

職場口語應(yīng)聘機械工程師英語10-28

軟件工程師英語面試題09-07

軟件測試工程師英語面試題08-04

軟件工程師面試英語自我介紹范文09-21