經驗技巧4 如何回答系統設計題

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

如何應對此類題目呢?在正式介紹基礎知識之前，首先羅列幾個常見的系統設計相關的面試筆試題，如下所示：

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

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

3）假設有30臺服務器，每臺服務器上面都存有上百億條數據（有可能重復），如何找出這30臺機器中，根據某關鍵字，重復出現次數最多的前100條?要求使用Hadoop來實現。

4）設計一個系統，要求寫速度盡可能快，并說明設計原理。

5）設計一個高并發系統，說明架構和關鍵技術要點。

6）有25TB的log（query->queryinfo)，log在不斷地增長，設計一個方案，給出一個query能快速返回queryinfo。

以上所有問題中凡是不涉及高并發的，基本可以采用谷歌（Google）公司的三個技術解決，即GFS、MapReduce和BigTable，這三個技術被稱為“Google三駕馬車”，Google公司只公開了論文而未開源代碼，開源界對此非常有興趣，仿照這三篇論文實現了一系列軟件，如Hadoop、HBase、HDFS及Cassandra等。

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

這種架構優點非常明顯：簡單，在數據量和用戶量較小的時候完全可以勝任；缺點是擴展性和容錯性太差，維護成本非常高，尤其是數據量和用戶量暴增之后，系統不能通過簡單地增加機器解決該問題。

鑒于此，“Google三駕馬車”應運而生。新的架構仍然采用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和電驢兩種下載引擎中，也采用了類似算法。

虛擬結點技術：該技術常用于分布式數據分片中。具體應用場景是：有一大塊數據（可能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是遠程過程調用，其使用方式與調用一個普通函數一樣，但執行體發生在遠程機器上；跨語言是指不同語言之間進行通信，比如C/S架構中，Server端采用C++編寫，Client端采用PHP編寫，怎樣讓兩者之間通信，Thrift是一種很好的方式。

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

1）關于高并發系統設計，主要有以下幾個關鍵技術點：緩存、索引、數據分片及鎖粒度盡可能小。

2）題目2涉及現在通用的分布式文件系統的副本存放策略。一般是將大文件切分成小的塊（block）（如64MB）后，以block為單位存放三份到不同的結點上，這三份數據的位置需根據網絡拓撲結構配置。一般而言，如果不考慮跨數據中心，可以這樣存放：兩個副本存放在同一個機架的不同結點上，而另外一個副本存放在另一個機架上，這樣從效率和可靠性上，都是最優的（這個Google公布的文檔中有專門的證明，有興趣的可參閱一下）。如果考慮跨數據中心，可將兩份存在一個數據中心的不同機架上，另一份放到另一個數據中心。

3）題目4涉及BigTable的模型。主要思想是將隨機寫轉化為順序寫，進而大大提高寫速度。具體做法是：由于磁盤物理結構的獨特設計，其并發的隨機寫（主要是因為磁盤尋道時間長）非常慢，考慮到這一點，在BigTable模型中，首先會將并發寫的大批數據放到一個內存表（稱為“memtable”）中，當該表大到一定程度后，會順序寫到一個磁盤表（稱為“SSTable”）中，這種寫是順序寫，效率極高。此時可能有讀者會問，隨機讀可不可以優化?答案是：看情況。通常而言，如果讀并發度不高，則不可以這么做，因為如果將多個讀重新排列組合后再執行，系統的響應時間太慢，用戶可能接受不了，而如果讀并發度極高，也許可以采用類似機制。