矽谷之路37：如何設計TinyURL

查看完整視頻：http://www.bittiger.io/classes

這是一道經典的系統設計面試題，是對SNAKE原則的深度應用，包含了系統設計的方方面面。最初的需求分析發現「長到短」和「短到長」兩個基本介面，讓我們又一次理解了「讀與寫是系統設計的基礎」。根據日活躍一百萬用戶進行的QPS估算，讓我們理解了什麼是「用數字說話」。從最符合直覺的hash映射演算法，到簡單有效的整數累加演算法讓我們理解了什麼是「不要過度設計」。從數字編碼，到字母編碼，甚至表情編碼，讓我們看到了短鏈接的種種變體的來源。最後對存儲的估算，讓我們看到了貌似複雜的功能，居然占不了什麼空間。

做個總結：

隨機演算法防衝突 。

什麼是Tiny URL？就是把長URL變短。這有什麼用呢？主要是便於分享。比如微博twitter一共才一百多個字，一個URL就佔一大半，還怎麼玩兒呢。

我們用SNAKE原則來設計：

首先考慮應用場景（Scenario），應用場景有兩個：將長的URL變短並存儲；查找短的URL還原。抽象一下就是兩個介面。

然後考慮限制性條件（Necessary），假設我們有一百萬日活用戶，分別計算插入和查找的每日請求次數。假設使用插入功能的日活用戶有1%，一個用戶插十次，平均到秒，每秒才1.2次，好低的，隨便就滿足了。一年我們會新生成36,500,000個短URL。但是查找就不同啦，100%要使用，不然怎麼知道這個短URL是什麼頁面呢，算一下每秒35次。

然後我們就可以考慮演算法實現（Algorithm）。做法很簡單，使用兩個map，一個存儲長URL到短URL的映射，一個存儲短URL到長URL的映射。

大家可能比較困惑GenerateShortURL()這個函數怎麼實現，有很多種方法，一種就是對長URL哈希；可是還有一種更簡單的方法，就是累加，只要返回map的大小就可以。

我們已經計算出一年會生成36,500,000個短URL，如果我們用上面累加的方式來表示（只用數字編碼），要8位數，加上前綴可能有點長，怎麼變短呢？可以引入a到z和A到Z的字母（相當於62進位），這樣長度就縮短到5位。

然後考慮數據存儲（Kilobit），百萬用戶聽起來很嚇人，然而數據真的很多嗎？來算一算：假設長URL的長度為100B，短URL使用我們上面的演算法可以用int來表示，就是4B，假設我們還需要存儲state（比如超時過期等）也用int型。這樣每天有10.8M的數據，一年就是4GB。才4GB而已哎，兩個map也才8GB，可以全放在內存里，並沒有很嚇人。

以上我們就用SNAKE原則設計了一個Tiny URL的服務，棒不棒。

本文整理作者：Mengying Tian，查看完整視頻：http://www.bittiger.io/classes

更多內容，請訪問：BitTiger.io， 掃描下面二維碼，關注微信公眾賬號「論碼農的自我修養」

http://weixin.qq.com/r/v0MnP17ERQM6rRpc9xat (二維碼自動識別)