?大家好，我是樹哥。

相信很多小伙伴都使用過短鏈服務(wù)，但如果讓你實現(xiàn)一個短鏈服務(wù)，你知道怎么實現(xiàn)嗎？其實實現(xiàn)短鏈服務(wù)并不是很難，最主要還是需要知道一些設(shè)計思路，還需要有一些基礎(chǔ)技術(shù)知識，例如：哈希算法、全局發(fā)號器等。

短鏈服務(wù)的設(shè)計場景題，也是國內(nèi)很多公司的面試題，很多朋友面試的時候都被問到了。今天一起來學(xué)習(xí)下如何設(shè)計一個短鏈服務(wù)吧！

短鏈的價值

網(wǎng)址大家都知道，很長的一串字符串，很多時候我們還會在后面添加非常多的參數(shù)，用來便于做數(shù)據(jù)統(tǒng)計。下面就是微信公眾號一篇文章的地址，可以看到其特別長，估計將近有幾百個字符。

https://mp.weixin.qq.com/s?__biz=MzA4MjIyNTY0MQ==&mid=2647743787&idx=1&sn=1caec8eb1b81d6ee5dd7ba7fa05ac0f1&chksm=87ad0dadb0da84bb7beb5e4373a14e89fba1130c1bd2a51f4baa8021ec0abe496ce94603b6b4&token=894028224&lang=zh_CN#rd

我們可以用百度的短網(wǎng)址功能，把上面的網(wǎng)址縮短成只有差不多 10 個字符串的長度，如下所示。

http://dwz.cn/iijg

用短鏈代替長鏈，有下面幾個常見的好處：

更加簡潔。比起一長串無意義的問題，只有差不多 10 個字符的字符串顯然更加簡潔。

便于使用。第一，有些平臺對內(nèi)容長度有限制（微博只能發(fā) 140 個字），此時短網(wǎng)址就可以輸入更多內(nèi)容。第二，我們將鏈接轉(zhuǎn)為二維碼時，短鏈接生成的二維碼更容易識別。第三，有些平臺無法識別特殊的長鏈參數(shù)，轉(zhuǎn)為短鏈就沒這個問題。

節(jié)省成本。當(dāng)我們需要發(fā)短信的時候，短信是按照長度計費的，短網(wǎng)址可以節(jié)省成本。

短鏈的原理

短鏈能夠給我們帶來這么多好處，但它是怎么工作的呢？

當(dāng)我們輸入短鏈時，其實訪問的是短鏈服務(wù)器的地址。短鏈服務(wù)器獲取到對應(yīng)的長鏈地址之后，返回一個 302 的 HTTP 響應(yīng)，在響應(yīng)中包含了長鏈接地址。瀏覽器收到響應(yīng)后，轉(zhuǎn)而去請求長鏈接地址。 訪問短鏈的整個流程如下圖所示：

短鏈訪問原理 - 來自網(wǎng)絡(luò)

從上面的流程中可以知道，短鏈涉及到的技術(shù)原理主要有兩點，分別是：HTTP 重定向和短鏈服務(wù)的設(shè)計。

對于 HTTP 重定向來說，301 和 302 都是重定向，那么到底應(yīng)該用哪個呢？

• 301 代表永久重定向。它表示第一次拿到長鏈接之后，下次瀏覽器如果再去請求短鏈的話，不會再向短鏈服務(wù)器請求了，而是直接從瀏覽器的緩存中獲取。
• 302 代表臨時重定向。它表示每次請求短鏈都會去請求短鏈服務(wù)器，不會從瀏覽器緩存中獲取。

如果我們希望統(tǒng)計短鏈接的點擊次數(shù)信息，從而來分析活動的效果的話。那么我們就需要使用 302 重定向碼，這樣才能獲取到每次的請求數(shù)據(jù)。 一般情況下，我們都是需要獲取到請求的數(shù)據(jù)的，因此對于短鏈服務(wù)都是用 302 臨時重定向。

實現(xiàn)思路

讓大家設(shè)計這樣一個系統(tǒng)，大家會有啥思路呢？

我們可以先分析一下整個系統(tǒng)的處理流程：

• 用戶訪問短鏈生成頁面，輸入長鏈字符串，短鏈服務(wù)返回生成的短鏈。
• 用戶訪問短鏈，短鏈服務(wù)返回 302 響應(yīng)，用戶瀏覽器跳轉(zhuǎn)到長鏈地址。

如果我們要實現(xiàn)上面的系統(tǒng)流程，我們大致的處理思路是：

• 生成短鏈。生成短鏈時，短鏈服務(wù)獲取到長鏈，隨后生成一個短鏈，并把短鏈與長鏈的映射關(guān)系保存下來，最后將短鏈返回給用戶。
• 找到長鏈。訪問短鏈時，短鏈服務(wù)獲取到短鏈，根據(jù)短鏈去獲取到長鏈，返回返回 302 響應(yīng)。

根據(jù)上面的分析，我們可以知道短鏈系統(tǒng)設(shè)計主要得解決如下兩個問題：

• 如何根據(jù)長鏈生成唯一短鏈？
• 如何保存短鏈與長鏈的映射關(guān)系？

對于第 2 點，保存短鏈與長鏈的映射關(guān)系，考慮到持久性的問題，我們肯定需要落庫，所以使用 MySQL 表保存即可。如果有需要的話，可以在 MySQL 前做一層緩存。因此第 2 點相對來說比較簡單。

對于第 1 點，我們有 2 個思路生成一個唯一短鏈，分別是：

• 使用哈希算法生成唯一值
• 使用分布式唯一 ID 生成作為鍛煉 ID

下面我們針對這兩個方案進(jìn)行詳細(xì)的分析。

哈希算法生成短鏈

要生成一個短鏈，我們可以將原有的長鏈做一次哈希，然后就可以得到一個哈希值，如下面所示。

https://mp.weixin.qq.com/s?__biz=MzA4MjIyNTY0MQ==&mid=2647743787&idx=1&sn=1caec8eb1b81d6ee5dd7ba7fa05ac0f1&chksm=87ad0dadb0da84bb7beb5e4373a14e89fba1130c1bd2a51f4baa8021ec0abe496ce94603b6b4&token=894028224&lang=zh_CN#rd
  ↓
29541341303115543223957290326355

那么我們遇到的第一個問題：使用什么哈希算法？

我們都知道哈希算法是一種摘要算法，它的作用是：對任意一組輸入數(shù)據(jù)進(jìn)行計算，得到一個固定長度的輸出摘要。我們常見的哈希算法有：MD5、SHA-1、SHA-256、SHA-512 算法等。但我們最好還是使用另一種叫做 MurmurHash 的哈希算法。為什么呢？

因為 MD5 和 SHA 哈希算法，它們都是加密的哈希算法，也就是說我們無法從哈希值反向推導(dǎo)出原文，從而保證了原文的保密性。

但對于我們這個場景而言，我們并不關(guān)心安全性，我們關(guān)注的是運算速度以及哈希沖突。而 MurmurHash 算法是一個非加密哈希算法，所以它的速度回更快。

這時候我們會遇到第二個問題：哈希沖突

學(xué)過 HashMap 的同學(xué)都知道，哈希沖突是哈希算法不可避免的問題。而解決哈希沖突的方式有兩種，分別是：鏈表法和重哈希法。HashMap 使用了鏈表法，但我們這里使用的是重哈希法。

所謂的重哈希法，指的是當(dāng)發(fā)生哈希沖突的時候，我們在原有長鏈后面加上固定的特殊字符，后續(xù)拿出長鏈時再將其去掉，如下所示。

原有長鏈：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b
              ↓↓  
           發(fā)生哈希沖突
              ↓↓  
補上特殊字符：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b[SPECIAL-CHARACTER]
              ↓↓  
           再次進(jìn)行哈希

通過這種辦法，我們就可以解決哈希沖突的問題了。如果再次發(fā)生，那么就再進(jìn)行哈希，一直到不沖突位置。一般來說，哈希沖突的可能性微乎其微。

好了，現(xiàn)在我們通過哈希算法得到了一個哈希值：29541341303115543223957290326355?，變成了這樣：http://dwz.com/29541341303115543223957290326355。

原本很長的網(wǎng)址變得比較短了，但整體看起來還是有點長。

有沒有辦法讓網(wǎng)址變得再短一點呢？

我們知道在網(wǎng)址 URL 中，常用的合法字符有 0～9、a～z、A～Z 這樣 62 個字符。如果我們用哈希值與 62 取余，那么余數(shù)肯定是在 0-61 之間。

這 62 個數(shù)字剛好與 62 個合法網(wǎng)址字符一一對應(yīng)。接著，我們再用除 62 得到的值，再次與 62 取余，一直到位 0 為止。通過這樣的處理，我們就可以得到一個字符為 62 個字符、長度很短的字符串了。

上面講有點晦澀難懂，我們來舉個例子。假設(shè)我們得到的哈希值為 181338494，那么上面的處理流程為：

• 將 181338494 除以 62，得到結(jié)果為 2924814，余數(shù)為 26，此時余數(shù) 26 對應(yīng)字符為 q。
• 將 2924814 除以 62，得到結(jié)果為 47174，余數(shù)為 26，此時余數(shù) 26 對應(yīng)字符為 q。
• 將 47174 除以 62，得到結(jié)果為 760，余數(shù)為 54，此時余數(shù) 54 對應(yīng)字符為 S。
• 省略剩余步驟

整個處理流程如下圖所示：

轉(zhuǎn)為 16 進(jìn)制數(shù)示意圖 - 來自極客時間

可以看到，我們把 181338494 這個十進(jìn)制數(shù)，轉(zhuǎn)成了由合法網(wǎng)址字符組成的「62 進(jìn)制數(shù)」—— cgSqq。

到這里，我們不僅生成了短鏈，還將短鏈的長度極大地縮短了。

這就是使用哈希算法生成唯一鍛煉的全部內(nèi)容了，我們總結(jié)一下：首先，使用 MurmurHash 生成哈希值，并且用重哈希法解決哈希沖突的問題。接著，將 10 進(jìn)制的哈希值轉(zhuǎn)成 62 進(jìn)制的合法網(wǎng)址字符，從而縮短網(wǎng)址長度。

分布式 ID 生成短鏈

上面使用哈希算法生成唯一短鏈的方式，相對來說是比較形象的。但其實我們也可以用分布式 ID 的方式，來完成唯一短鏈的生成。

例如第一次請求的長鏈，我們?yōu)槠渖梢粋€唯一 ID，將其長鏈與唯一 ID 對應(yīng)起來。第二次請求，我們再為其生成一個唯一 ID，再次將長鏈與唯一 ID 對應(yīng)起來，如下所示。

第一次請求：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b
              ↓↓  
生成短鏈：https://dwz.com/1021000001

第一次請求：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5ff7b
              ↓↓  
生成短鏈：https://dwz.com/1021000002

因為生成的唯一 ID 也可能非常長，因此我們可以采用上面同樣的方式，將 10 進(jìn)制的唯一 ID 轉(zhuǎn)成 62 進(jìn)制的合法網(wǎng)址字符，從而縮短字符長度。

那么接下來的問題就變成了：如何設(shè)計一個全局唯一 ID 發(fā)號器了。

對于如何設(shè)計一個全局唯一的 ID 發(fā)號器，就屬于另外一個話題，我們這里就不深入探討了。

性能優(yōu)化

看到這里，我們基本上有了一個完整的思路：拿到長鏈地址后，可以用哈希算法或唯一 ID 分號器獲取唯一字符串，從而建立長鏈與短鏈的映射關(guān)系。為了縮短短鏈長度，我們還可以將其用 62 進(jìn)制數(shù)表示，整個短鏈生成過程如下圖所示。

短鏈生成示意圖

短鏈生成完，并且已經(jīng)存到了數(shù)據(jù)庫中，接下里該使用了。通常的做法是會根據(jù)請求的短鏈字符串，從數(shù)據(jù)庫中找到數(shù)據(jù)，然后返回 HTTP 重定向原始地址。而在不斷使用過程中，還有一些可能發(fā)現(xiàn)的優(yōu)化點，這里簡單講講。

索引優(yōu)化

如果使用關(guān)系型數(shù)據(jù)庫的話，對于短鏈字段需要創(chuàng)建唯一索引，從而加快查詢速度。

增加緩存

并發(fā)量小的時候，我們都是直接訪問數(shù)據(jù)庫。但當(dāng)并發(fā)量再次升高時，需要加上緩存抗住熱點數(shù)據(jù)的訪問。

讀寫分離

短鏈服務(wù)肯定是讀遠(yuǎn)大于寫的，因此對于短鏈服務(wù)，可以做好讀寫分離。

分庫分表

如果是商用的短鏈服務(wù)，那么數(shù)據(jù)量上億是很正常的，更不用說常年累月積累下的量了。這時候可以一開始就做好分庫分表操作，避免后期再大動干戈。

對于分庫分表來說，最關(guān)鍵的便是根據(jù)哪個字段去作為分庫分表的依據(jù)了。對于短鏈服務(wù)來說，當(dāng)然是用轉(zhuǎn)化后的 62 進(jìn)制數(shù)字做分表依據(jù)了，因為它是唯一的嘛。

至于怎么分庫分表，就涉及到分庫分表方面的知識，以及對于系統(tǒng)容量的預(yù)估了，這里就不細(xì)說了。有機(jī)會的話，我們找個時間來深入講講這方面的內(nèi)容。

防止惡意攻擊

開放到公網(wǎng)的服務(wù)，什么事情都可能發(fā)生，其中一個可能的點就是被惡意攻擊，不斷循環(huán)調(diào)用。

一開始我們可以做一下簡單地限流操作，例如：

沒有授權(quán)的用戶，根據(jù) IP 進(jìn)行判斷，1 分鐘最多只能請求 10 次。

沒有授權(quán)的用戶，所有用戶 1 分鐘最多只能請求 4000 次，防止更換 IP 進(jìn)行攻擊。

簡單地說，就是要不斷提高攻擊的成本，使得最壞情況下系統(tǒng)依然可以正常提供服務(wù)。

總結(jié)

本文首先講了短鏈存在的三個價值：簡潔、易于使用、節(jié)省成本，接著講了短鏈的原理是 HTTP 重定向，最后著重講了短鏈服務(wù)的設(shè)計思路。

在短鏈服務(wù)的設(shè)計思路上，最重要是解決兩個問題：根據(jù)長鏈生成短鏈、根據(jù)短鏈找到長鏈。在根據(jù)長鏈生成短鏈的思路上，我們講了兩種實現(xiàn)思路，分別是：哈希算法生成短鏈、分布式全局 ID 生成短鏈，其中哈希算法涉及到哈希算法的選擇，以及哈希沖突的處理。

最后我們還列舉了一些短鏈服務(wù)后續(xù)可能的優(yōu)化點，包括：如何讓網(wǎng)址變得更短、索引優(yōu)化、增加熱點數(shù)據(jù)、讀寫分離、分庫分表、防止惡意攻擊等等。

如何設(shè)計一個短鏈服務(wù)？

參考資料

• 系統(tǒng)設(shè)計系列之如何設(shè)計一個短鏈服務(wù)_架構(gòu)_看山_InfoQ 寫作社區(qū)
• 挺好！VIP！實戰(zhàn)經(jīng)驗！高性能短鏈設(shè)計 - 掘金
• 【原創(chuàng)】這可能是東半球最接地氣的短鏈接系統(tǒng)設(shè)計 - 孤獨煙 - 博客園
• 不錯，這個很全面！VIP！面試官：如何設(shè)計一個短鏈接系統(tǒng) – 小黑說
• 56 | 算法實戰(zhàn)（五）：如何用學(xué)過的數(shù)據(jù)結(jié)構(gòu)和算法實現(xiàn)一個短網(wǎng)址系統(tǒng)？
• 當(dāng)成一個甜點來吃。短 URL 系統(tǒng)是怎么設(shè)計的？- iammutex 的回答 - 知乎
• 哈希算法 - 廖雪峰的官方網(wǎng)站