如何設計一個短鏈服務？
?大家好，我是樹哥。
相信很多小伙伴都使用過短鏈服務，但如果讓你實現一個短鏈服務，你知道怎么實現嗎？其實實現短鏈服務并不是很難，最主要還是需要知道一些設計思路，還需要有一些基礎技術知識，例如：哈希算法、全局發號器等。
短鏈服務的設計場景題，也是國內很多公司的面試題，很多朋友面試的時候都被問到了。今天一起來學習下如何設計一個短鏈服務吧！
短鏈的價值
網址大家都知道，很長的一串字符串，很多時候我們還會在后面添加非常多的參數，用來便于做數據統計。下面就是微信公眾號一篇文章的地址，可以看到其特別長，估計將近有幾百個字符。
https://mp.weixin.qq.com/s?__biz=MzA4MjIyNTY0MQ==&mid=2647743787&idx=1&sn=1caec8eb1b81d6ee5dd7ba7fa05ac0f1&chksm=87ad0dadb0da84bb7beb5e4373a14e89fba1130c1bd2a51f4baa8021ec0abe496ce94603b6b4&token=894028224&lang=zh_CN#rd
我們可以用百度的短網址功能，把上面的網址縮短成只有差不多 10 個字符串的長度，如下所示。
http://dwz.cn/iijg
用短鏈代替長鏈，有下面幾個常見的好處：
更加簡潔。比起一長串無意義的問題，只有差不多 10 個字符的字符串顯然更加簡潔。
便于使用。第一，有些平臺對內容長度有限制（微博只能發 140 個字），此時短網址就可以輸入更多內容。第二，我們將鏈接轉為二維碼時，短鏈接生成的二維碼更容易識別。第三，有些平臺無法識別特殊的長鏈參數，轉為短鏈就沒這個問題。
節省成本。當我們需要發短信的時候，短信是按照長度計費的，短網址可以節省成本。
短鏈的原理
短鏈能夠給我們帶來這么多好處，但它是怎么工作的呢？
當我們輸入短鏈時，其實訪問的是短鏈服務器的地址。短鏈服務器獲取到對應的長鏈地址之后，返回一個 302 的 HTTP 響應，在響應中包含了長鏈接地址。瀏覽器收到響應后，轉而去請求長鏈接地址。 訪問短鏈的整個流程如下圖所示：
短鏈訪問原理 - 來自網絡
從上面的流程中可以知道，短鏈涉及到的技術原理主要有兩點，分別是：HTTP 重定向和短鏈服務的設計。
對于 HTTP 重定向來說，301 和 302 都是重定向，那么到底應該用哪個呢？
- 301 代表永久重定向。它表示第一次拿到長鏈接之后，下次瀏覽器如果再去請求短鏈的話，不會再向短鏈服務器請求了，而是直接從瀏覽器的緩存中獲取。
- 302 代表臨時重定向。它表示每次請求短鏈都會去請求短鏈服務器，不會從瀏覽器緩存中獲取。
如果我們希望統計短鏈接的點擊次數信息，從而來分析活動的效果的話。那么我們就需要使用 302 重定向碼，這樣才能獲取到每次的請求數據。 一般情況下，我們都是需要獲取到請求的數據的，因此對于短鏈服務都是用 302 臨時重定向。
實現思路
讓大家設計這樣一個系統，大家會有啥思路呢？
我們可以先分析一下整個系統的處理流程：
- 用戶訪問短鏈生成頁面，輸入長鏈字符串，短鏈服務返回生成的短鏈。
- 用戶訪問短鏈，短鏈服務返回 302 響應，用戶瀏覽器跳轉到長鏈地址。
如果我們要實現上面的系統流程，我們大致的處理思路是：
- 生成短鏈。生成短鏈時，短鏈服務獲取到長鏈，隨后生成一個短鏈，并把短鏈與長鏈的映射關系保存下來，最后將短鏈返回給用戶。
- 找到長鏈。訪問短鏈時，短鏈服務獲取到短鏈，根據短鏈去獲取到長鏈，返回返回 302 響應。
根據上面的分析，我們可以知道短鏈系統設計主要得解決如下兩個問題：
- 如何根據長鏈生成唯一短鏈？
- 如何保存短鏈與長鏈的映射關系？
對于第 2 點，保存短鏈與長鏈的映射關系，考慮到持久性的問題，我們肯定需要落庫，所以使用 MySQL 表保存即可。如果有需要的話，可以在 MySQL 前做一層緩存。因此第 2 點相對來說比較簡單。
對于第 1 點，我們有 2 個思路生成一個唯一短鏈，分別是：
- 使用哈希算法生成唯一值
- 使用分布式唯一 ID 生成作為鍛煉 ID
下面我們針對這兩個方案進行詳細的分析。
哈希算法生成短鏈
要生成一個短鏈，我們可以將原有的長鏈做一次哈希，然后就可以得到一個哈希值，如下面所示。
https://mp.weixin.qq.com/s?__biz=MzA4MjIyNTY0MQ==&mid=2647743787&idx=1&sn=1caec8eb1b81d6ee5dd7ba7fa05ac0f1&chksm=87ad0dadb0da84bb7beb5e4373a14e89fba1130c1bd2a51f4baa8021ec0abe496ce94603b6b4&token=894028224&lang=zh_CN#rd
↓
29541341303115543223957290326355
那么我們遇到的第一個問題：使用什么哈希算法？
我們都知道哈希算法是一種摘要算法，它的作用是：對任意一組輸入數據進行計算，得到一個固定長度的輸出摘要。我們常見的哈希算法有：MD5、SHA-1、SHA-256、SHA-512 算法等。但我們最好還是使用另一種叫做 MurmurHash 的哈希算法。為什么呢？
因為 MD5 和 SHA 哈希算法，它們都是加密的哈希算法，也就是說我們無法從哈希值反向推導出原文，從而保證了原文的保密性。
但對于我們這個場景而言，我們并不關心安全性，我們關注的是運算速度以及哈希沖突。而 MurmurHash 算法是一個非加密哈希算法，所以它的速度回更快。
這時候我們會遇到第二個問題：哈希沖突
學過 HashMap 的同學都知道，哈希沖突是哈希算法不可避免的問題。而解決哈希沖突的方式有兩種，分別是：鏈表法和重哈希法。HashMap 使用了鏈表法，但我們這里使用的是重哈希法。
所謂的重哈希法，指的是當發生哈希沖突的時候，我們在原有長鏈后面加上固定的特殊字符，后續拿出長鏈時再將其去掉，如下所示。
原有長鏈：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b
↓↓
發生哈希沖突
↓↓
補上特殊字符：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b[SPECIAL-CHARACTER]
↓↓
再次進行哈希
通過這種辦法，我們就可以解決哈希沖突的問題了。如果再次發生，那么就再進行哈希，一直到不沖突位置。一般來說，哈希沖突的可能性微乎其微。
好了，現在我們通過哈希算法得到了一個哈希值：29541341303115543223957290326355?，變成了這樣：http://dwz.com/29541341303115543223957290326355。
原本很長的網址變得比較短了，但整體看起來還是有點長。
有沒有辦法讓網址變得再短一點呢？
我們知道在網址 URL 中，常用的合法字符有 0～9、a～z、A～Z 這樣 62 個字符。如果我們用哈希值與 62 取余，那么余數肯定是在 0-61 之間。
這 62 個數字剛好與 62 個合法網址字符一一對應。接著，我們再用除 62 得到的值，再次與 62 取余，一直到位 0 為止。通過這樣的處理，我們就可以得到一個字符為 62 個字符、長度很短的字符串了。
上面講有點晦澀難懂，我們來舉個例子。假設我們得到的哈希值為 181338494，那么上面的處理流程為：
- 將 181338494 除以 62，得到結果為 2924814，余數為 26，此時余數 26 對應字符為 q。
- 將 2924814 除以 62，得到結果為 47174，余數為 26，此時余數 26 對應字符為 q。
- 將 47174 除以 62，得到結果為 760，余數為 54，此時余數 54 對應字符為 S。
- 省略剩余步驟
整個處理流程如下圖所示：
轉為 16 進制數示意圖 - 來自極客時間
可以看到，我們把 181338494 這個十進制數，轉成了由合法網址字符組成的「62 進制數」—— cgSqq。
到這里，我們不僅生成了短鏈，還將短鏈的長度極大地縮短了。
這就是使用哈希算法生成唯一鍛煉的全部內容了，我們總結一下：首先，使用 MurmurHash 生成哈希值，并且用重哈希法解決哈希沖突的問題。接著，將 10 進制的哈希值轉成 62 進制的合法網址字符，從而縮短網址長度。
分布式 ID 生成短鏈
上面使用哈希算法生成唯一短鏈的方式，相對來說是比較形象的。但其實我們也可以用分布式 ID 的方式，來完成唯一短鏈的生成。
例如第一次請求的長鏈，我們為其生成一個唯一 ID，將其長鏈與唯一 ID 對應起來。第二次請求，我們再為其生成一個唯一 ID，再次將長鏈與唯一 ID 對應起來，如下所示。
第一次請求：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b
↓↓
生成短鏈：https://dwz.com/1021000001
第一次請求：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5ff7b
↓↓
生成短鏈：https://dwz.com/1021000002
因為生成的唯一 ID 也可能非常長，因此我們可以采用上面同樣的方式，將 10 進制的唯一 ID 轉成 62 進制的合法網址字符，從而縮短字符長度。
那么接下來的問題就變成了：如何設計一個全局唯一 ID 發號器了。
對于如何設計一個全局唯一的 ID 發號器，就屬于另外一個話題，我們這里就不深入探討了。
性能優化
看到這里，我們基本上有了一個完整的思路：拿到長鏈地址后，可以用哈希算法或唯一 ID 分號器獲取唯一字符串，從而建立長鏈與短鏈的映射關系。為了縮短短鏈長度，我們還可以將其用 62 進制數表示，整個短鏈生成過程如下圖所示。
短鏈生成示意圖
短鏈生成完，并且已經存到了數據庫中，接下里該使用了。通常的做法是會根據請求的短鏈字符串，從數據庫中找到數據，然后返回 HTTP 重定向原始地址。而在不斷使用過程中，還有一些可能發現的優化點，這里簡單講講。
索引優化
如果使用關系型數據庫的話，對于短鏈字段需要創建唯一索引，從而加快查詢速度。
增加緩存
并發量小的時候，我們都是直接訪問數據庫。但當并發量再次升高時，需要加上緩存抗住熱點數據的訪問。
讀寫分離
短鏈服務肯定是讀遠大于寫的，因此對于短鏈服務，可以做好讀寫分離。
分庫分表
如果是商用的短鏈服務，那么數據量上億是很正常的，更不用說常年累月積累下的量了。這時候可以一開始就做好分庫分表操作，避免后期再大動干戈。
對于分庫分表來說，最關鍵的便是根據哪個字段去作為分庫分表的依據了。對于短鏈服務來說，當然是用轉化后的 62 進制數字做分表依據了，因為它是唯一的嘛。
至于怎么分庫分表，就涉及到分庫分表方面的知識，以及對于系統容量的預估了，這里就不細說了。有機會的話，我們找個時間來深入講講這方面的內容。
防止惡意攻擊
開放到公網的服務，什么事情都可能發生，其中一個可能的點就是被惡意攻擊，不斷循環調用。
一開始我們可以做一下簡單地限流操作，例如：
沒有授權的用戶，根據 IP 進行判斷，1 分鐘最多只能請求 10 次。
沒有授權的用戶，所有用戶 1 分鐘最多只能請求 4000 次，防止更換 IP 進行攻擊。
簡單地說，就是要不斷提高攻擊的成本，使得最壞情況下系統依然可以正常提供服務。
總結
本文首先講了短鏈存在的三個價值：簡潔、易于使用、節省成本，接著講了短鏈的原理是 HTTP 重定向，最后著重講了短鏈服務的設計思路。
在短鏈服務的設計思路上，最重要是解決兩個問題：根據長鏈生成短鏈、根據短鏈找到長鏈。在根據長鏈生成短鏈的思路上，我們講了兩種實現思路，分別是：哈希算法生成短鏈、分布式全局 ID 生成短鏈，其中哈希算法涉及到哈希算法的選擇，以及哈希沖突的處理。
最后我們還列舉了一些短鏈服務后續可能的優化點，包括：如何讓網址變得更短、索引優化、增加熱點數據、讀寫分離、分庫分表、防止惡意攻擊等等。
如何設計一個短鏈服務？
參考資料
- 系統設計系列之如何設計一個短鏈服務_架構_看山_InfoQ 寫作社區
- 挺好！VIP！實戰經驗！高性能短鏈設計 - 掘金
- 【原創】這可能是東半球最接地氣的短鏈接系統設計 - 孤獨煙 - 博客園
- 不錯，這個很全面！VIP！面試官：如何設計一個短鏈接系統 – 小黑說
- 56 | 算法實戰（五）：如何用學過的數據結構和算法實現一個短網址系統？
- 當成一個甜點來吃。短 URL 系統是怎么設計的？- iammutex 的回答 - 知乎
- 哈希算法 - 廖雪峰的官方網站
