經(jīng)驗技巧6 如何回答系統(tǒng)設(shè)計題？

應屆生在面試的時候，偶爾也會遇到一些系統(tǒng)設(shè)計題，這些題目往往只是測試一下求職者的知識面，或者測試求職者對系統(tǒng)架構(gòu)方面的了解，一般不會涉及具體的編碼工作。雖然如此，對于此類問題，很多人還是感覺難以應對，也不知道從何說起。

如何應對此類題目呢？在正式介紹基礎(chǔ)知識之前，首先羅列幾個常見的系統(tǒng)設(shè)計相關(guān)的面試筆試題，如下所示：

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

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

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

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

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

6．有25TB的日志(query->queryinfo)，大小在不斷增長，設(shè)計一個方案，給出一個query能快速返回queryinfo。

以上所有問題中凡是不涉及高并發(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)在很多公司（例如淘寶、weibo.com）仍采用這種架構(gòu)。在這種架構(gòu)中，仍有很多問題值得探討。如采用什么數(shù)據(jù)庫，是SQL界的MySQL還是NoSQL界的Redis/TFS，兩者有何優(yōu)劣？采用什么方式 sharding（數(shù)據(jù)分片），是水平分片還是垂直分片？據(jù)網(wǎng)上資料顯示，weibo.com和淘寶圖片存儲中曾采用的架構(gòu)是Redis/MySQL/TFS+sharding+cache，該架構(gòu)解釋如下：前端cache是為了提高響應速度，后端數(shù)據(jù)庫則用于數(shù)據(jù)永久存儲，防止數(shù)據(jù)丟失，而sharding是為了在多臺計算機間分攤負載。最前端由大塊大塊的cache組成，要保證至少99%的訪問數(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)應運而生。新的架構(gòu)仍然采用Google 公司的架構(gòu)模式與設(shè)計思想，以下將分別就此內(nèi)容進行分析。

GFS是一個可擴展的分布式文件系統(tǒng)，用于大型的、分布式的、對大量數(shù)據(jù)進行訪問的應用。它運行于廉價的普通硬件上，提供容錯功能。現(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。當前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ù)分片中。具體應用場景是：有一大塊數(shù)據(jù)（可能TB級或者PB級），需按照某個字段（key）分片存儲到幾十（或者更多）臺計算機上，同時想盡量負載均衡且容易擴展。傳統(tǒng)的做法是：Hash(key) mod N，這種方法最大的缺點是不容易擴展，即增加或者減少計算機均會導致數(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

……

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

Thrift：Thrift是一個跨語言的RPC框架。RPC是遠程過程調(diào)用，其使用方式與調(diào)用一個普通函數(shù)一樣，但執(zhí)行體發(fā)生在遠程計算機上?？缯Z言是指不同語言之間進行通信，例如C/S架構(gòu)中，Server端采用C++編寫，Client端采用PHP編寫，怎樣讓兩者之間通信，Thrift是一種很好的方式。

最前面的幾道題均可以映射到以上幾個系統(tǒng)的某個模塊中，如：

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

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