【系統設計】設計一個短連結系統
短連結系統可以把比較長的 URL 網址轉換成簡短的網址字串，短連結的優勢是方便傳播。適合在一些對字串長度有要求的場景中使用，比如簡訊，微博等，比如
https://www.cnblogs.com/myshowtime/p/16227260.html
轉換成短連結為
設計要求
根據面試的要求，你需要設計一個短連結系統， 連結的長度儘量比較短，每天生成 1 億個URL，服務要執行 10 年。
首先，我們看一下短連結的工作原理。
工作原理
在 Chrome 上輸入短連結，會發生什麼？
開啟開發者工具， 可以看到， 伺服器收到請求後，會把短連結轉換成長連結，然後返回瀏覽器，進行 301 重定向，請求到長連結地址。
另外一個問題，如何把長連結轉換成短連結？
能否使用一些加密演演算法呢？明顯是行不通的，因為字串加密後會變的更長。
雜湊演演算法
實際上，我們可以使用雜湊演演算法和雜湊表實現，如下
長連結經過雜湊演演算法後， 會生成固定長度的雜湊值 key，也就是短連結的值，並儲存到雜湊表中。
使用短連結查詢長連結時，只需要查詢雜湊表即可。
上面是常見的雜湊演演算法，最少也要8位元。
那我們需要多少位的短連結呢？根據上面的要求，一天生成一個億的短連結，執行10年，1億 * 365 * 10 = 3650 億。
短連結的字元在 [0-9,a-z,A-Z] 之間，總共 62 個不同的字元，可以計算出下面的資料。
可以看出，要滿足系統要求的話，短連結的長度最少為 7 位。在實際中，很多短連結系統的長度也是 7 位。有興趣的同學還可以看一下，米勒定律 7±2 法則。
上面的 CRC32 演演算法，最少也是 8 位。不過我們可以擷取前 7 位，最後一位丟棄。但是這樣可能會出現雜湊衝突的問題，我們可以給長連結遞迴地拼接一個值，直到不再發現衝突，當然也可以用其他的雜湊衝突解決方法。
Base 62 轉換
這是另外一種常見的方法，Base 62 字元由大寫字母 A-Z、小寫字母 a-z 和數位 0-9 組成, 總共 62 位，如下
base 62 和 base 64 相比，只不過少了2個字元 + 和 /，大家可以想一下，這裡我們為什麼不用 base 64。
Base 62 和上面的雜湊演演算法的思路是不一樣的，雜湊演演算法是根據長連結計算雜湊值，然後儲存到雜湊表中。而 base 62 需要給每條長連結生成一個唯一的數位 ID，如下
那麼如何計算短連結 ShortURL 呢? 因為 Id 是唯一的 10 進位制數位，我們只需要把它轉成 62 進位制即可， 這裡和從2進位制轉換到10進位制是一樣的。
假如有一個 ID 為 11157, 轉換的過程如下
最終得到的短連結的值為 https://xxx.com/2TX。
總結
在本文中，介紹了兩種實現短連結的方法，分別是雜湊演演算法和 base 62。
雜湊演演算法的特點是，固定的短連結長度，不需要生成唯一ID，可能會出現雜湊衝突。
base 62 轉換的特點是，長度不固定，取決於 ID 的大小，1000 轉換後是 G8, 1000 億 轉換後是 1l9Zo9o。另外還需要生成唯一數位 ID，沒有雜湊衝突的問題。
希望對您有用！
譯：等天黑
作者：Alex Xu
來源：《System Design Interview》
簡介: Alex Xu 是一位經驗豐富的軟體工程師, 曾在 Twitter, Apple 和 Oracle 任職，來自CS名校卡內基梅隆大學，熱衷於系統設計。
