在Microsoft和Facebook擔(dān)任高級(jí)軟件工程師和面試官的10年中，我與數(shù)百名申請(qǐng)人一起工作，因?yàn)樗麄兘鉀Q了不同的系統(tǒng)設(shè)計(jì)問(wèn)題。

開發(fā)人員傾向于解決SDI問(wèn)題，因?yàn)樗鼈兪侨绱碎_放，并且通常需要一種在其他編碼面試挑戰(zhàn)中沒(méi)有實(shí)踐的批判性思維。

盡管SDI問(wèn)題隨著時(shí)間而變化，但其中一些問(wèn)題在各種頂級(jí)公司的訪談中仍然很受歡迎。

今天，我們將探討最常見的10個(gè)系統(tǒng)設(shè)計(jì)面試問(wèn)題，每個(gè)問(wèn)題中必須解決的常見問(wèn)題以及一些可以幫助您完成此任務(wù)的工具。

[[398993]]

有關(guān)任何SDI問(wèn)題的提示

通過(guò)陳述您所知道的問(wèn)題來(lái)開始每個(gè)問(wèn)題：列出系統(tǒng)的所有必需功能，此類系統(tǒng)可能遇到的常見問(wèn)題以及系統(tǒng)希望處理的流量。列出過(guò)程使面試官可以在開始解決方案之前查看您的計(jì)劃技能并糾正任何可能的誤解。

敘述任何權(quán)衡：每個(gè)系統(tǒng)設(shè)計(jì)選擇都很重要。在每個(gè)決策點(diǎn)，至少列出該選擇的正面和負(fù)面影響。

請(qǐng)您的面試官澄清：大多數(shù)系統(tǒng)設(shè)計(jì)問(wèn)題是故意含糊的。提出澄清問(wèn)題，向面試官展示您如何看待問(wèn)題以及對(duì)系統(tǒng)需求的了解。

討論新興技術(shù)：在每個(gè)問(wèn)題的結(jié)尾都概述了系統(tǒng)如何以及在何處可以從機(jī)器學(xué)習(xí)中受益。這將表明您不僅為當(dāng)前的解決方案做好了準(zhǔn)備，而且還為將來(lái)的解決方案做好了準(zhǔn)備。

[[398994]]

 

1.設(shè)計(jì)一個(gè)全球聊天服務(wù)，例如Facebook Messenger或WhatsApp

對(duì)于這個(gè)問(wèn)題，您將設(shè)計(jì)一種服務(wù)，允許用戶通過(guò)Internet彼此聊天。對(duì)話可以是一對(duì)一的對(duì)話，也可以是與許多成員進(jìn)行的群聊。對(duì)話中包含的消息只能訪問(wèn)這些消息。

必備功能：

• 消息必須通過(guò)互聯(lián)網(wǎng)發(fā)送和接收。
• 服務(wù)必須支持一對(duì)一和群聊。
• 消息應(yīng)存儲(chǔ)以供以后查看。
• 用戶應(yīng)該能夠發(fā)送圖片和視頻以及短信。
• 郵件在傳輸過(guò)程中應(yīng)被加密。
• 消息應(yīng)該以最小的延遲可見。

常見問(wèn)題：

• 如果在沒(méi)有互聯(lián)網(wǎng)連接的情況下發(fā)送郵件會(huì)怎樣?恢復(fù)連接后是否發(fā)送?
• 如何在不增加延遲的情況下加密和解密消息?
• 用戶如何接收通知?
• 是將消息從設(shè)備中拉出(如果服務(wù)器正在等待發(fā)送消息，服務(wù)器會(huì)定期提示設(shè)備)還是將消息推送到服務(wù)器(設(shè)備會(huì)提示服務(wù)器有消息要發(fā)送)?

需要考慮的工具：

• 將數(shù)據(jù)庫(kù)模式分為多個(gè)表：用戶表(具有用戶ID和聯(lián)系人)，聊天表(具有聊天ID和參與的用戶ID列表)和消息表(過(guò)去的消息帶有對(duì)聊天ID的引用)。
• 使用WebSocket在設(shè)備和服務(wù)器之間進(jìn)行雙向連接。
• 使用推式通知來(lái)通知成員，即使他們處于脫機(jī)狀態(tài)。

[[398995]]

 

2. 設(shè)計(jì)類似Uber或Lyft的拼車服務(wù)

該問(wèn)題要求您創(chuàng)建一種將用戶與附近駕駛員匹配的乘車共享服務(wù)。用戶可以輸入目的地并發(fā)送其當(dāng)前位置，并在幾秒鐘內(nèi)通知附近的駕駛員。

然后，該應(yīng)用程序會(huì)跟蹤駕駛員和用戶當(dāng)前位置之間的路線，然后再跟蹤從用戶位置到目的地的路線。

必備功能：

• 系統(tǒng)必須跟蹤所有用戶和驅(qū)動(dòng)程序的當(dāng)前位置。
• 在運(yùn)輸過(guò)程中，用戶和駕駛員必須接收更新的旅行信息。
• 必須在此過(guò)程中的各個(gè)階段支持成千上萬(wàn)的用戶，并相應(yīng)地?cái)U(kuò)展規(guī)模。
• 驅(qū)動(dòng)程序和用戶必須始終連接到服務(wù)器。

常見問(wèn)題：

• 您如何在繁忙時(shí)段保持較低的延遲?
• 驅(qū)動(dòng)程序如何與用戶配對(duì)?迭代所有駕駛員以找到歐幾里得距離將是低效的。
• 如果驅(qū)動(dòng)程序或用戶失去連接會(huì)怎樣?
• 您如何存儲(chǔ)所有緩存的位置數(shù)據(jù)?

需要考慮的工具：

• 使用S2Geometry庫(kù)將位置拆分為單元格。僅使用與用戶位于同一單元格中的駕駛員來(lái)計(jì)算駕駛員距離。
• 使用分布式存儲(chǔ)來(lái)存儲(chǔ)所有用戶的位置，每個(gè)用戶的位置數(shù)據(jù)大約只有1Kb。
• 如果位置數(shù)據(jù)暫停，則設(shè)備在等待重新連接時(shí)會(huì)繼續(xù)報(bào)告其先前的位置。
• 提示最近的駕駛員出行后，請(qǐng)留一個(gè)緩沖區(qū)。如果他們拒絕，請(qǐng)轉(zhuǎn)到下一個(gè)驅(qū)動(dòng)程序。

[[398996]]

3. 設(shè)計(jì)URL短服務(wù)，例如TinyURL或 bit.ly

這個(gè)問(wèn)題要求您創(chuàng)建一個(gè)程序來(lái)縮短長(zhǎng)網(wǎng)址，例如TinyURL或bit.ly。這些程序采用一個(gè)長(zhǎng)URL并生成一個(gè)新的唯一的短URL。他們還可以輸入縮短的URL并返回原始的完整URL。

必備功能：

• 返回比原始網(wǎng)址短的網(wǎng)址
• 必須存儲(chǔ)原始URL
• 新生成的URL必須能夠鏈接到存儲(chǔ)的原始URL
• 縮短的網(wǎng)址應(yīng)允許重定向
• 必須支持自定義短網(wǎng)址
• 必須一次支持許多請(qǐng)求

常見問(wèn)題：

• 如果兩個(gè)用戶輸入相同的自定義URL，該怎么辦?
• 如果用戶數(shù)量超出預(yù)期怎么辦?
• 數(shù)據(jù)庫(kù)如何調(diào)節(jié)存儲(chǔ)空間?

需要考慮的工具：

• 使用哈希鏈接原始和新URL
• 使用REST API負(fù)載均衡高流量并處理前端客戶端通信
• 使用多線程一次處理多個(gè)請(qǐng)求
• 使用NoSQL數(shù)據(jù)庫(kù)存儲(chǔ)原始URL(存儲(chǔ)的URL之間沒(méi)有關(guān)系)

[[398997]]

4. 設(shè)計(jì)一個(gè)大眾社交媒體服務(wù)，例如Facebook，Twitter或Instagram

對(duì)于這個(gè)問(wèn)題，您將設(shè)計(jì)一個(gè)供Instagram之類的十萬(wàn)用戶使用的社交媒體服務(wù)。用戶應(yīng)該能夠查看帶有跟隨者帖子的新聞提要，并建議用戶喜歡的新內(nèi)容。

采訪者通常希望聽到您深入討論新聞源。

必備功能：

• 強(qiáng)大的新聞源和推薦系統(tǒng)
• 用戶可以發(fā)表公開帖子
• 其他用戶可以評(píng)論或頂帖子
• 必須一次舒適地容納許多用戶
• 系統(tǒng)必須高度可用

常見問(wèn)題：

• 知名用戶將擁有數(shù)百萬(wàn)個(gè)關(guān)注者，與普通用戶相比，他們將如何處理?
• 系統(tǒng)如何按年齡分配體重?與新帖子相比，舊帖子的瀏覽可能性較小。
• 節(jié)點(diǎn)read與write集中節(jié)點(diǎn)的比率是多少?是否可能會(huì)有更多的讀取請(qǐng)求(用戶正在查看帖子)或?qū)懭胝?qǐng)求(用戶正在創(chuàng)建帖子)?
• 您如何增加可用性?系統(tǒng)如何更新?如果節(jié)點(diǎn)發(fā)生故障會(huì)怎樣?
• 您如何有效地存儲(chǔ)帖子和圖像?

需要考慮的工具：

• 使用滾動(dòng)更新和副本節(jié)點(diǎn)來(lái)最大化可用性。
• 使用訓(xùn)練有素的機(jī)器學(xué)習(xí)算法來(lái)推薦帖子。
• 創(chuàng)建一個(gè)數(shù)據(jù)庫(kù)架構(gòu)，分別存儲(chǔ)名人和用戶。
• 使用社交圖譜進(jìn)一步追蹤以下習(xí)慣

[[398998]]

5. 設(shè)計(jì)一個(gè)社交網(wǎng)絡(luò)和留言板服務(wù)，例如Quora，Reddit或HackerNews

對(duì)于這個(gè)問(wèn)題，您將設(shè)計(jì)一個(gè)類似于論壇的系統(tǒng)，用戶可以在其中發(fā)布問(wèn)題和鏈接。

其他用戶可以查看和評(píng)論問(wèn)題。問(wèn)題具有代表其主題的標(biāo)簽，用戶可以跟隨標(biāo)簽查看有關(guān)特定主題的問(wèn)題。用戶有一個(gè)新聞源，該新聞源從其關(guān)注的標(biāo)簽和相關(guān)主題中突出顯示了常見問(wèn)題。

必備功能：

• 用戶必須能夠創(chuàng)建公共帖子并應(yīng)用標(biāo)簽
• 帖子必須按標(biāo)簽排序
• 其他用戶必須能夠?qū)崟r(shí)發(fā)布評(píng)論。
• 數(shù)據(jù)庫(kù)必須在每個(gè)帖子上存儲(chǔ)數(shù)據(jù)(觀看次數(shù)，贊等)
• 新聞源必須顯示來(lái)自跟隨標(biāo)簽的帖子以及用戶希望的其他標(biāo)簽的帖子。
• 必須支持高流量的觀眾和新帖子。

常見問(wèn)題：

• 我們的產(chǎn)品僅需要在網(wǎng)絡(luò)上運(yùn)行嗎?
• 用戶上傳的圖像/鏈接存儲(chǔ)在哪里?
• 系統(tǒng)將如何確定相關(guān)標(biāo)簽?供稿中顯示多少個(gè)來(lái)自未關(guān)注標(biāo)簽的帖子?
• 如何在服務(wù)器網(wǎng)絡(luò)上分配帖子?

需要考慮的工具：

• 使用SQL數(shù)據(jù)庫(kù)映射關(guān)系數(shù)據(jù)(用戶有帖子，帖子有評(píng)論/喜歡，類別有相關(guān)的帖子，等等)
• 使用多線程和負(fù)載平衡器層可幫助支持更高的流量。
• 使用分片來(lái)破壞系統(tǒng)。考慮按類別分片以將相同標(biāo)簽的帖子存儲(chǔ)在一臺(tái)計(jì)算機(jī)中。
• 使用機(jī)器學(xué)習(xí)和自然語(yǔ)言處理來(lái)查找標(biāo)簽之間的關(guān)系之間的相關(guān)性

[[398999]]

 

6. 設(shè)計(jì)全局文件存儲(chǔ)和共享服務(wù)，例如Dropbox，Google云端硬盤或Google相冊(cè)

對(duì)于這個(gè)問(wèn)題，您將創(chuàng)建一個(gè)同步的跨平臺(tái)存儲(chǔ)系統(tǒng)，例如Dropbox。用戶可以存儲(chǔ)文件和照片并從其他設(shè)備訪問(wèn)它們。

必備功能：

• 用戶應(yīng)該能夠通過(guò)網(wǎng)絡(luò)保存/刪除/更新/共享文件
• 舊版本的文檔應(yīng)保存以進(jìn)行回滾
• 文件更新應(yīng)在多個(gè)設(shè)備上同步

常見問(wèn)題：

• 文件存儲(chǔ)在哪里?
• 您如何處理更新?您是否再次重新上傳整個(gè)文件?
• 小更新需要完整的文件更新嗎?
• 系統(tǒng)如何處理兩個(gè)用戶同時(shí)更新文檔?

需要考慮的工具：

• 使用分塊將文件分成多個(gè)部分。更新僅重新上傳該部分，而不是整個(gè)文件。
• 使用像Amazon S3這樣的云存儲(chǔ)來(lái)處理內(nèi)部數(shù)據(jù)庫(kù)。
• 使客戶端不斷與服務(wù)器核對(duì)以確保應(yīng)用并發(fā)更新。

[[399000]]

7. 設(shè)計(jì)全球視頻流服務(wù)，例如YouTube或Netflix

這個(gè)問(wèn)題要求您創(chuàng)建在線視頻流服務(wù)，例如YouTube。該服務(wù)將存儲(chǔ)和傳輸數(shù)百PB的視頻數(shù)據(jù)。它還必須存儲(chǔ)統(tǒng)計(jì)信息(觀看次數(shù)，喜歡次數(shù)，觀看次數(shù)等)，并允許用戶發(fā)表評(píng)論。

您的解決方案必須具有可擴(kuò)展性，以支持成千上萬(wàn)的并發(fā)用戶。

必備功能：

• 視頻應(yīng)該可以通過(guò)網(wǎng)絡(luò)上傳
• 用戶應(yīng)通過(guò)互聯(lián)網(wǎng)收到不間斷的流
• 視頻統(tǒng)計(jì)信息應(yīng)該存儲(chǔ)并可以訪問(wèn)每個(gè)視頻。
• 評(píng)論必須保存并與視頻一起顯示給其他網(wǎng)友評(píng)論
• 應(yīng)該支持幾千個(gè)用戶的高流量

常見問(wèn)題：

• 您的服務(wù)將如何確保各種互聯(lián)網(wǎng)質(zhì)量上的流暢視頻流?
• 您的服務(wù)如何應(yīng)對(duì)流速度的突然下降(緩沖，質(zhì)量下降等)?
• 視頻如何存儲(chǔ)?

需要考慮的工具：

• 使用云技術(shù)來(lái)存儲(chǔ)和傳輸視頻數(shù)據(jù)。
• 使用機(jī)器學(xué)習(xí)來(lái)建議新的視頻內(nèi)容。
• 防止因連接不一致而造成的卡頓現(xiàn)象。用戶查看了片刻之前的數(shù)據(jù)，而不是輸入數(shù)據(jù)。

[[399001]]

8. 為Firebase或Github等網(wǎng)站設(shè)計(jì)API速率限制器

對(duì)于這個(gè)問(wèn)題，您將創(chuàng)建一個(gè)API速率限制器，以限制服務(wù)在給定時(shí)間段內(nèi)可以接收的API調(diào)用次數(shù)，以避免過(guò)載。

采訪者可以從一臺(tái)機(jī)器到整個(gè)分布式網(wǎng)絡(luò)，以各種規(guī)模提出要求。

必備功能：

• 設(shè)備每小時(shí)限制為10個(gè)請(qǐng)求
• 如果他們的請(qǐng)求被阻止，則限制器必須通知用戶。
• 必須處理適合其規(guī)模的流量。

常見問(wèn)題：

• 您的系統(tǒng)如何衡量每小時(shí)的請(qǐng)求?如果用戶在1:20發(fā)出10個(gè)請(qǐng)求，然后在2:10發(fā)出另外10個(gè)請(qǐng)求，那么盡管小時(shí)數(shù)有所變化，他們還是在同一1小時(shí)窗口中發(fā)出了20個(gè)請(qǐng)求。
• 分布式系統(tǒng)的設(shè)計(jì)與本地系統(tǒng)有何不同?

需要考慮的工具：

• 使用滑動(dòng)時(shí)間窗口以避免每小時(shí)重置一次。
• 保存一個(gè)計(jì)數(shù)器整數(shù)而不是請(qǐng)求本身以節(jié)省空間。

[[399002]]

9. 設(shè)計(jì)一個(gè)類似Yelp或附近的地方/朋友的接近服務(wù)器

對(duì)于最后一個(gè)問(wèn)題，您將設(shè)計(jì)一個(gè)鄰近服務(wù)器，用于存儲(chǔ)并報(bào)告到餐廳等地方的距離。用戶可以按距離或受歡迎程度搜索附近的地點(diǎn)。該數(shù)據(jù)庫(kù)必須存儲(chǔ)全球5億個(gè)位置的數(shù)據(jù)，但延遲低。

必備功能：

• 存儲(chǔ)多達(dá)5億個(gè)位置。
• 位置必須唯一標(biāo)識(shí)，并具有相應(yīng)的數(shù)據(jù)，例如質(zhì)量檢查和服務(wù)時(shí)間。
• 搜索必須以最小的延遲返回結(jié)果。
• 用戶必須能夠按距離或質(zhì)量搜索結(jié)果。

常見問(wèn)題：

• 您如何存儲(chǔ)這么多的位置數(shù)據(jù)?
• 您如何獲得快速搜索結(jié)果?
• 您的系統(tǒng)如何處理不同的人口密度?剛性的緯度/經(jīng)度網(wǎng)格將導(dǎo)致基于密度的變化響應(yīng)。
• 我們?nèi)绾蝺?yōu)化常用搜索位置?

需要考慮的工具：

• 使用關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)位置列表和相關(guān)數(shù)據(jù)。
• 使用緩存存儲(chǔ)最受歡迎位置的數(shù)據(jù)。
• 使用分片可按區(qū)域拆分?jǐn)?shù)據(jù)。
• 在某個(gè)動(dòng)態(tài)網(wǎng)格內(nèi)搜索位置。如果單個(gè)單元格中有500個(gè)以上的位置，請(qǐng)將網(wǎng)格劃分為4個(gè)較小的單元格。重復(fù)直到您只需要搜索少于500個(gè)位置。

[[399003]]

10. 設(shè)計(jì)與搜索引擎相關(guān)的服務(wù)，例如Type-Ahead

該服務(wù)將部分完成搜索查詢，并顯示5條建議以完成查詢。它應(yīng)該實(shí)時(shí)適應(yīng)高度搜索的內(nèi)容，并向其他用戶建議。

例如，將在事件發(fā)生后的幾分鐘內(nèi)建議“海鷹隊(duì)贏得超級(jí)碗”。

必備功能：

• 該服務(wù)應(yīng)將部分查詢與流行查詢匹配。
• 較小的拼寫錯(cuò)誤應(yīng)予以糾正，例如“ dgo→dog”
• 應(yīng)該根據(jù)查詢猜出5個(gè)最可能的選項(xiàng)
• 結(jié)果應(yīng)在編寫查詢時(shí)更新

常見問(wèn)題：

• 您對(duì)拼寫錯(cuò)誤的糾正能力有多強(qiáng)?
• 如何更新選擇而不引起延遲?
• 您如何確定最可能完成的查詢?它適應(yīng)用戶的搜索嗎?
• 如果用戶快速鍵入該怎么辦?建議是否僅在完成后才會(huì)顯示?

需要考慮的工具：

• 使用自然語(yǔ)言處理機(jī)器學(xué)習(xí)算法來(lái)預(yù)測(cè)下一個(gè)字符。
• 使用馬爾可夫鏈對(duì)排名最高的查詢概率進(jìn)行排名。
• 每小時(shí)或每天(而不是實(shí)時(shí))更新ML算法，以減輕負(fù)擔(dān)。

接下來(lái)要學(xué)什么

這些問(wèn)題應(yīng)有助于您理解在系統(tǒng)設(shè)計(jì)面試中將要解決的問(wèn)題類型。練習(xí)解決和解釋此類問(wèn)題是準(zhǔn)備下一次面試的最有效方法。

本文翻譯自The Educative Team的文章《Top 10 System Design Interview Questions》。