十大系統(tǒng)設(shè)計面試問題
在Microsoft和Facebook擔(dān)任高級軟件工程師和面試官的10年中，我與數(shù)百名申請人一起工作，因為他們解決了不同的系統(tǒng)設(shè)計問題。
開發(fā)人員傾向于解決SDI問題，因為它們是如此開放，并且通常需要一種在其他編碼面試挑戰(zhàn)中沒有實踐的批判性思維。
盡管SDI問題隨著時間而變化，但其中一些問題在各種頂級公司的訪談中仍然很受歡迎。
今天，我們將探討最常見的10個系統(tǒng)設(shè)計面試問題，每個問題中必須解決的常見問題以及一些可以幫助您完成此任務(wù)的工具。
有關(guān)任何SDI問題的提示
通過陳述您所知道的問題來開始每個問題：列出系統(tǒng)的所有必需功能，此類系統(tǒng)可能遇到的常見問題以及系統(tǒng)希望處理的流量。列出過程使面試官可以在開始解決方案之前查看您的計劃技能并糾正任何可能的誤解。
敘述任何權(quán)衡：每個系統(tǒng)設(shè)計選擇都很重要。在每個決策點，至少列出該選擇的正面和負面影響。
請您的面試官澄清：大多數(shù)系統(tǒng)設(shè)計問題是故意含糊的。提出澄清問題，向面試官展示您如何看待問題以及對系統(tǒng)需求的了解。
討論新興技術(shù)：在每個問題的結(jié)尾都概述了系統(tǒng)如何以及在何處可以從機器學(xué)習(xí)中受益。這將表明您不僅為當(dāng)前的解決方案做好了準(zhǔn)備，而且還為將來的解決方案做好了準(zhǔn)備。
1.設(shè)計一個全球聊天服務(wù)，例如Facebook Messenger或WhatsApp
對于這個問題，您將設(shè)計一種服務(wù)，允許用戶通過Internet彼此聊天。對話可以是一對一的對話，也可以是與許多成員進行的群聊。對話中包含的消息只能訪問這些消息。
必備功能：
- 消息必須通過互聯(lián)網(wǎng)發(fā)送和接收。
- 服務(wù)必須支持一對一和群聊。
- 消息應(yīng)存儲以供以后查看。
- 用戶應(yīng)該能夠發(fā)送圖片和視頻以及短信。
- 郵件在傳輸過程中應(yīng)被加密。
- 消息應(yīng)該以最小的延遲可見。
常見問題：
- 如果在沒有互聯(lián)網(wǎng)連接的情況下發(fā)送郵件會怎樣?恢復(fù)連接后是否發(fā)送?
- 如何在不增加延遲的情況下加密和解密消息?
- 用戶如何接收通知?
- 是將消息從設(shè)備中拉出(如果服務(wù)器正在等待發(fā)送消息，服務(wù)器會定期提示設(shè)備)還是將消息推送到服務(wù)器(設(shè)備會提示服務(wù)器有消息要發(fā)送)?
需要考慮的工具：
- 將數(shù)據(jù)庫模式分為多個表：用戶表(具有用戶ID和聯(lián)系人)，聊天表(具有聊天ID和參與的用戶ID列表)和消息表(過去的消息帶有對聊天ID的引用)。
- 使用WebSocket在設(shè)備和服務(wù)器之間進行雙向連接。
- 使用推式通知來通知成員，即使他們處于脫機狀態(tài)。
2. 設(shè)計類似Uber或Lyft的拼車服務(wù)
該問題要求您創(chuàng)建一種將用戶與附近駕駛員匹配的乘車共享服務(wù)。用戶可以輸入目的地并發(fā)送其當(dāng)前位置，并在幾秒鐘內(nèi)通知附近的駕駛員。
然后，該應(yīng)用程序會跟蹤駕駛員和用戶當(dāng)前位置之間的路線，然后再跟蹤從用戶位置到目的地的路線。
必備功能：
- 系統(tǒng)必須跟蹤所有用戶和驅(qū)動程序的當(dāng)前位置。
- 在運輸過程中，用戶和駕駛員必須接收更新的旅行信息。
- 必須在此過程中的各個階段支持成千上萬的用戶，并相應(yīng)地擴展規(guī)模。
- 驅(qū)動程序和用戶必須始終連接到服務(wù)器。
常見問題：
- 您如何在繁忙時段保持較低的延遲?
- 驅(qū)動程序如何與用戶配對?迭代所有駕駛員以找到歐幾里得距離將是低效的。
- 如果驅(qū)動程序或用戶失去連接會怎樣?
- 您如何存儲所有緩存的位置數(shù)據(jù)?
需要考慮的工具：
- 使用S2Geometry庫將位置拆分為單元格。僅使用與用戶位于同一單元格中的駕駛員來計算駕駛員距離。
- 使用分布式存儲來存儲所有用戶的位置，每個用戶的位置數(shù)據(jù)大約只有1Kb。
- 如果位置數(shù)據(jù)暫停，則設(shè)備在等待重新連接時會繼續(xù)報告其先前的位置。
- 提示最近的駕駛員出行后，請留一個緩沖區(qū)。如果他們拒絕，請轉(zhuǎn)到下一個驅(qū)動程序。
3. 設(shè)計URL短服務(wù)，例如TinyURL或 bit.ly
這個問題要求您創(chuàng)建一個程序來縮短長網(wǎng)址，例如TinyURL或bit.ly。這些程序采用一個長URL并生成一個新的唯一的短URL。他們還可以輸入縮短的URL并返回原始的完整URL。
必備功能：
- 返回比原始網(wǎng)址短的網(wǎng)址
- 必須存儲原始URL
- 新生成的URL必須能夠鏈接到存儲的原始URL
- 縮短的網(wǎng)址應(yīng)允許重定向
- 必須支持自定義短網(wǎng)址
- 必須一次支持許多請求
常見問題：
- 如果兩個用戶輸入相同的自定義URL，該怎么辦?
- 如果用戶數(shù)量超出預(yù)期怎么辦?
- 數(shù)據(jù)庫如何調(diào)節(jié)存儲空間?
需要考慮的工具：
- 使用哈希鏈接原始和新URL
- 使用REST API負載均衡高流量并處理前端客戶端通信
- 使用多線程一次處理多個請求
- 使用NoSQL數(shù)據(jù)庫存儲原始URL(存儲的URL之間沒有關(guān)系)
4. 設(shè)計一個大眾社交媒體服務(wù)，例如Facebook，Twitter或Instagram
對于這個問題，您將設(shè)計一個供Instagram之類的十萬用戶使用的社交媒體服務(wù)。用戶應(yīng)該能夠查看帶有跟隨者帖子的新聞提要，并建議用戶喜歡的新內(nèi)容。
采訪者通常希望聽到您深入討論新聞源。
必備功能：
- 強大的新聞源和推薦系統(tǒng)
- 用戶可以發(fā)表公開帖子
- 其他用戶可以評論或頂帖子
- 必須一次舒適地容納許多用戶
- 系統(tǒng)必須高度可用
常見問題：
- 知名用戶將擁有數(shù)百萬個關(guān)注者，與普通用戶相比，他們將如何處理?
- 系統(tǒng)如何按年齡分配體重?與新帖子相比，舊帖子的瀏覽可能性較小。
- 節(jié)點read與write集中節(jié)點的比率是多少?是否可能會有更多的讀取請求(用戶正在查看帖子)或?qū)懭胝埱?用戶正在創(chuàng)建帖子)?
- 您如何增加可用性?系統(tǒng)如何更新?如果節(jié)點發(fā)生故障會怎樣?
- 您如何有效地存儲帖子和圖像?
需要考慮的工具：
- 使用滾動更新和副本節(jié)點來最大化可用性。
- 使用訓(xùn)練有素的機器學(xué)習(xí)算法來推薦帖子。
- 創(chuàng)建一個數(shù)據(jù)庫架構(gòu)，分別存儲名人和用戶。
- 使用社交圖譜進一步追蹤以下習(xí)慣
5. 設(shè)計一個社交網(wǎng)絡(luò)和留言板服務(wù)，例如Quora，Reddit或HackerNews
對于這個問題，您將設(shè)計一個類似于論壇的系統(tǒng)，用戶可以在其中發(fā)布問題和鏈接。
其他用戶可以查看和評論問題。問題具有代表其主題的標(biāo)簽，用戶可以跟隨標(biāo)簽查看有關(guān)特定主題的問題。用戶有一個新聞源，該新聞源從其關(guān)注的標(biāo)簽和相關(guān)主題中突出顯示了常見問題。
必備功能：
- 用戶必須能夠創(chuàng)建公共帖子并應(yīng)用標(biāo)簽
- 帖子必須按標(biāo)簽排序
- 其他用戶必須能夠?qū)崟r發(fā)布評論。
- 數(shù)據(jù)庫必須在每個帖子上存儲數(shù)據(jù)(觀看次數(shù)，贊等)
- 新聞源必須顯示來自跟隨標(biāo)簽的帖子以及用戶希望的其他標(biāo)簽的帖子。
- 必須支持高流量的觀眾和新帖子。
常見問題：
- 我們的產(chǎn)品僅需要在網(wǎng)絡(luò)上運行嗎?
- 用戶上傳的圖像/鏈接存儲在哪里?
- 系統(tǒng)將如何確定相關(guān)標(biāo)簽?供稿中顯示多少個來自未關(guān)注標(biāo)簽的帖子?
- 如何在服務(wù)器網(wǎng)絡(luò)上分配帖子?
需要考慮的工具：
- 使用SQL數(shù)據(jù)庫映射關(guān)系數(shù)據(jù)(用戶有帖子，帖子有評論/喜歡，類別有相關(guān)的帖子，等等)
- 使用多線程和負載平衡器層可幫助支持更高的流量。
- 使用分片來破壞系統(tǒng)?？紤]按類別分片以將相同標(biāo)簽的帖子存儲在一臺計算機中。
- 使用機器學(xué)習(xí)和自然語言處理來查找標(biāo)簽之間的關(guān)系之間的相關(guān)性
6. 設(shè)計全局文件存儲和共享服務(wù)，例如Dropbox，Google云端硬盤或Google相冊
對于這個問題，您將創(chuàng)建一個同步的跨平臺存儲系統(tǒng)，例如Dropbox。用戶可以存儲文件和照片并從其他設(shè)備訪問它們。
必備功能：
- 用戶應(yīng)該能夠通過網(wǎng)絡(luò)保存/刪除/更新/共享文件
- 舊版本的文檔應(yīng)保存以進行回滾
- 文件更新應(yīng)在多個設(shè)備上同步
常見問題：
- 文件存儲在哪里?
- 您如何處理更新?您是否再次重新上傳整個文件?
- 小更新需要完整的文件更新嗎?
- 系統(tǒng)如何處理兩個用戶同時更新文檔?
需要考慮的工具：
- 使用分塊將文件分成多個部分。更新僅重新上傳該部分，而不是整個文件。
- 使用像Amazon S3這樣的云存儲來處理內(nèi)部數(shù)據(jù)庫。
- 使客戶端不斷與服務(wù)器核對以確保應(yīng)用并發(fā)更新。
7. 設(shè)計全球視頻流服務(wù)，例如YouTube或Netflix
這個問題要求您創(chuàng)建在線視頻流服務(wù)，例如YouTube。該服務(wù)將存儲和傳輸數(shù)百PB的視頻數(shù)據(jù)。它還必須存儲統(tǒng)計信息(觀看次數(shù)，喜歡次數(shù)，觀看次數(shù)等)，并允許用戶發(fā)表評論。
您的解決方案必須具有可擴展性，以支持成千上萬的并發(fā)用戶。
必備功能：
- 視頻應(yīng)該可以通過網(wǎng)絡(luò)上傳
- 用戶應(yīng)通過互聯(lián)網(wǎng)收到不間斷的流
- 視頻統(tǒng)計信息應(yīng)該存儲并可以訪問每個視頻。
- 評論必須保存并與視頻一起顯示給其他網(wǎng)友評論
- 應(yīng)該支持幾千個用戶的高流量
常見問題：
- 您的服務(wù)將如何確保各種互聯(lián)網(wǎng)質(zhì)量上的流暢視頻流?
- 您的服務(wù)如何應(yīng)對流速度的突然下降(緩沖，質(zhì)量下降等)?
- 視頻如何存儲?
需要考慮的工具：
- 使用云技術(shù)來存儲和傳輸視頻數(shù)據(jù)。
- 使用機器學(xué)習(xí)來建議新的視頻內(nèi)容。
- 防止因連接不一致而造成的卡頓現(xiàn)象。用戶查看了片刻之前的數(shù)據(jù)，而不是輸入數(shù)據(jù)。
8. 為Firebase或Github等網(wǎng)站設(shè)計API速率限制器
對于這個問題，您將創(chuàng)建一個API速率限制器，以限制服務(wù)在給定時間段內(nèi)可以接收的API調(diào)用次數(shù)，以避免過載。
采訪者可以從一臺機器到整個分布式網(wǎng)絡(luò)，以各種規(guī)模提出要求。
必備功能：
- 設(shè)備每小時限制為10個請求
- 如果他們的請求被阻止，則限制器必須通知用戶。
- 必須處理適合其規(guī)模的流量。
常見問題：
- 您的系統(tǒng)如何衡量每小時的請求?如果用戶在1:20發(fā)出10個請求，然后在2:10發(fā)出另外10個請求，那么盡管小時數(shù)有所變化，他們還是在同一1小時窗口中發(fā)出了20個請求。
- 分布式系統(tǒng)的設(shè)計與本地系統(tǒng)有何不同?
需要考慮的工具：
- 使用滑動時間窗口以避免每小時重置一次。
- 保存一個計數(shù)器整數(shù)而不是請求本身以節(jié)省空間。
9. 設(shè)計一個類似Yelp或附近的地方/朋友的接近服務(wù)器
對于最后一個問題，您將設(shè)計一個鄰近服務(wù)器，用于存儲并報告到餐廳等地方的距離。用戶可以按距離或受歡迎程度搜索附近的地點。該數(shù)據(jù)庫必須存儲全球5億個位置的數(shù)據(jù)，但延遲低。
必備功能：
- 存儲多達5億個位置。
- 位置必須唯一標(biāo)識，并具有相應(yīng)的數(shù)據(jù)，例如質(zhì)量檢查和服務(wù)時間。
- 搜索必須以最小的延遲返回結(jié)果。
- 用戶必須能夠按距離或質(zhì)量搜索結(jié)果。
常見問題：
- 您如何存儲這么多的位置數(shù)據(jù)?
- 您如何獲得快速搜索結(jié)果?
- 您的系統(tǒng)如何處理不同的人口密度?剛性的緯度/經(jīng)度網(wǎng)格將導(dǎo)致基于密度的變化響應(yīng)。
- 我們?nèi)绾蝺?yōu)化常用搜索位置?
需要考慮的工具：
- 使用關(guān)系數(shù)據(jù)庫存儲位置列表和相關(guān)數(shù)據(jù)。
- 使用緩存存儲最受歡迎位置的數(shù)據(jù)。
- 使用分片可按區(qū)域拆分數(shù)據(jù)。
- 在某個動態(tài)網(wǎng)格內(nèi)搜索位置。如果單個單元格中有500個以上的位置，請將網(wǎng)格劃分為4個較小的單元格。重復(fù)直到您只需要搜索少于500個位置。
10. 設(shè)計與搜索引擎相關(guān)的服務(wù)，例如Type-Ahead
該服務(wù)將部分完成搜索查詢，并顯示5條建議以完成查詢。它應(yīng)該實時適應(yīng)高度搜索的內(nèi)容，并向其他用戶建議。
例如，將在事件發(fā)生后的幾分鐘內(nèi)建議“海鷹隊贏得超級碗”。
必備功能：
- 該服務(wù)應(yīng)將部分查詢與流行查詢匹配。
- 較小的拼寫錯誤應(yīng)予以糾正，例如“ dgo→dog”
- 應(yīng)該根據(jù)查詢猜出5個最可能的選項
- 結(jié)果應(yīng)在編寫查詢時更新
常見問題：
- 您對拼寫錯誤的糾正能力有多強?
- 如何更新選擇而不引起延遲?
- 您如何確定最可能完成的查詢?它適應(yīng)用戶的搜索嗎?
- 如果用戶快速鍵入該怎么辦?建議是否僅在完成后才會顯示?
需要考慮的工具：
- 使用自然語言處理機器學(xué)習(xí)算法來預(yù)測下一個字符。
- 使用馬爾可夫鏈對排名最高的查詢概率進行排名。
- 每小時或每天(而不是實時)更新ML算法，以減輕負擔(dān)。
接下來要學(xué)什么
這些問題應(yīng)有助于您理解在系統(tǒng)設(shè)計面試中將要解決的問題類型。練習(xí)解決和解釋此類問題是準(zhǔn)備下一次面試的最有效方法。
本文翻譯自The Educative Team的文章《Top 10 System Design Interview Questions》。
