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

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

如何應(yīng)對(duì)此類題目呢？在正式介紹基礎(chǔ)知識(shí)之前，首先列舉幾個(gè)常見的系統(tǒng)設(shè)計(jì)相關(guān)的面試、筆試題。

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

題目2：有N臺(tái)機(jī)器，M個(gè)文件，文件可以以任意方式存放到任意機(jī)器上，文件可任意分割成若干塊。假設(shè)這N臺(tái)機(jī)器的宕機(jī)率小于33%，要想在宕機(jī)時(shí)可以從其他未宕機(jī)的機(jī)器中完整導(dǎo)出這M個(gè)文件，求最好的存放與分割策略。

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

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

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

題目6：有25TB的log（query-＞queryinfo），log在不斷地增長(zhǎng)，設(shè)計(jì)一個(gè)方案，給出一個(gè)query能快速返回queryinfo。

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

在Google這些技術(shù)還未出現(xiàn)之前，企業(yè)界在設(shè)計(jì)大規(guī)模分布式系統(tǒng)時(shí)，采用的架構(gòu)往往是DataBase+Sharding+Cache，現(xiàn)在很多網(wǎng)站（比如淘寶網(wǎng)、新浪微博）仍采用這種架構(gòu)。在這種架構(gòu)中，仍有很多問題值得探討。如采用哪種數(shù)據(jù)庫(kù)，是SQL界的MySQL還是NoSQL界的Redis/TFS，兩者有何優(yōu)劣？采用什么方式Sharding（數(shù)據(jù)分片），是水平分片還是垂直分片？據(jù)網(wǎng)上資料顯示，淘寶網(wǎng)和新浪微博圖片存儲(chǔ)中曾采用的架構(gòu)是Redis/MySQL/TFS+Sharding+Cache，該架構(gòu)解釋如下：前端Cache是為了提高響應(yīng)速度，后端數(shù)據(jù)庫(kù)則用于數(shù)據(jù)永久存儲(chǔ)，防止數(shù)據(jù)丟失，而Sharding是為了在多臺(tái)機(jī)器間分?jǐn)傌?fù)載。最前端由大塊的Cache組成，要保證至少99%（淘寶網(wǎng)圖片存儲(chǔ)模塊是真實(shí)的）的訪問數(shù)據(jù)落在Cache中，這樣可以保證用戶訪問速度，減少后端數(shù)據(jù)庫(kù)的壓力。此外，為了保證前端Cache 中的數(shù)據(jù)與后端數(shù)據(jù)庫(kù)中的數(shù)據(jù)一致，需要有一個(gè)中間件異步更新數(shù)據(jù)（為什么使用異步？理由是，同步代價(jià)太高），新浪有個(gè)開源軟件叫Memcachedb（整合了Berkeley DB和Memcached），正是用于完成此功能。另外，為了分?jǐn)傌?fù)載壓力和海量數(shù)據(jù)，會(huì)將用戶微博信息經(jīng)過分片后存放到不同節(jié)點(diǎn)上（稱為“Sharding”）。

這種架構(gòu)優(yōu)點(diǎn)非常明顯：簡(jiǎn)單，在數(shù)據(jù)量和用戶量較小時(shí)完全可以勝任。但缺點(diǎn)是擴(kuò)展性和容錯(cuò)性太差，維護(hù)成本非常高，尤其是數(shù)據(jù)量和用戶量暴增之后，系統(tǒng)不能通過簡(jiǎn)單地增加機(jī)器解決該問題。

鑒于此，新的架構(gòu)應(yīng)運(yùn)而生。新的架構(gòu)仍然采用Google公司的架構(gòu)模式與設(shè)計(jì)思想，以下將分別就此內(nèi)容進(jìn)行分析。

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

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

BigTable 俗稱“大表”，是用來(lái)存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)的。編者認(rèn)為，BigTable開源實(shí)現(xiàn)最多，包括HBase、Cassandra和levelDB等，使用也非常廣泛。

除了Google的這“三駕馬車”以外，還有其他一些技術(shù)可供學(xué)習(xí)與使用。

Dynamo 亞馬遜的key-value 模式的存儲(chǔ)平臺(tái)，可用性和擴(kuò)展性都很好，采用DHT （Distributed Hash Table）對(duì)數(shù)據(jù)分片，解決單點(diǎn)故障問題，在Cassandra中也借鑒了該技術(shù)，在BT和電驢這兩種下載引擎中，也采用了類似算法。

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

node1：0～1000000

node2：1000001～2000000

……

這樣，當(dāng)添加一個(gè)新的節(jié)點(diǎn)時(shí)，只需將每個(gè)節(jié)點(diǎn)上部分?jǐn)?shù)據(jù)移動(dòng)給新節(jié)點(diǎn)，同時(shí)修改一下該表即可。

Thrift Thrift 是一個(gè)跨語(yǔ)言的RPC框架。RPC是遠(yuǎn)程過程調(diào)用，其使用方式與調(diào)用一個(gè)普通函數(shù)一樣，但執(zhí)行體發(fā)生在遠(yuǎn)程機(jī)器上；跨語(yǔ)言是指不同語(yǔ)言之間進(jìn)行通信，例如C/S架構(gòu)中，Server端采用C++編寫，Client端采用PHP編寫，要在兩者之間通信，Thrift是一種很好的方式。

本篇最前面的幾道題均可以映射到以上幾個(gè)系統(tǒng)的某個(gè)模塊中。

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

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

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