?大家好，我是樹(shù)哥。

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

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

短鏈的價(jià)值

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

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 個(gè)字符串的長(zhǎng)度，如下所示。

http://dwz.cn/iijg

用短鏈代替長(zhǎng)鏈，有下面幾個(gè)常見(jiàn)的好處：

更加簡(jiǎn)潔。比起一長(zhǎng)串無(wú)意義的問(wèn)題，只有差不多 10 個(gè)字符的字符串顯然更加簡(jiǎn)潔。

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

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

短鏈的原理

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

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

短鏈訪(fǎng)問(wèn)原理 - 來(lái)自網(wǎng)絡(luò)

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

對(duì)于 HTTP 重定向來(lái)說(shuō)，301 和 302 都是重定向，那么到底應(yīng)該用哪個(gè)呢？

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

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

實(shí)現(xiàn)思路

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

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

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

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

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

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

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

對(duì)于第 2 點(diǎn)，保存短鏈與長(zhǎng)鏈的映射關(guān)系，考慮到持久性的問(wèn)題，我們肯定需要落庫(kù)，所以使用 MySQL 表保存即可。如果有需要的話(huà)，可以在 MySQL 前做一層緩存。因此第 2 點(diǎn)相對(duì)來(lái)說(shuō)比較簡(jiǎn)單。

對(duì)于第 1 點(diǎn)，我們有 2 個(gè)思路生成一個(gè)唯一短鏈，分別是：

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

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

哈希算法生成短鏈

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

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

那么我們遇到的第一個(gè)問(wèn)題：使用什么哈希算法？

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

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

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

這時(shí)候我們會(huì)遇到第二個(gè)問(wèn)題：哈希沖突

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

所謂的重哈希法，指的是當(dāng)發(fā)生哈希沖突的時(shí)候，我們?cè)谠虚L(zhǎng)鏈后面加上固定的特殊字符，后續(xù)拿出長(zhǎng)鏈時(shí)再將其去掉，如下所示。

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

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

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

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

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

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

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

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

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

整個(gè)處理流程如下圖所示：

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

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

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

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

分布式 ID 生成短鏈

上面使用哈希算法生成唯一短鏈的方式，相對(duì)來(lái)說(shuō)是比較形象的。但其實(shí)我們也可以用分布式 ID 的方式，來(lái)完成唯一短鏈的生成。

例如第一次請(qǐng)求的長(zhǎng)鏈，我們?yōu)槠渖梢粋€(gè)唯一 ID，將其長(zhǎng)鏈與唯一 ID 對(duì)應(yīng)起來(lái)。第二次請(qǐng)求，我們?cè)贋槠渖梢粋€(gè)唯一 ID，再次將長(zhǎng)鏈與唯一 ID 對(duì)應(yīng)起來(lái)，如下所示。

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

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

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

那么接下來(lái)的問(wèn)題就變成了：如何設(shè)計(jì)一個(gè)全局唯一 ID 發(fā)號(hào)器了。

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

性能優(yōu)化

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

短鏈生成示意圖

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

索引優(yōu)化

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

增加緩存

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

讀寫(xiě)分離

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

分庫(kù)分表

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

對(duì)于分庫(kù)分表來(lái)說(shuō)，最關(guān)鍵的便是根據(jù)哪個(gè)字段去作為分庫(kù)分表的依據(jù)了。對(duì)于短鏈服務(wù)來(lái)說(shuō)，當(dāng)然是用轉(zhuǎn)化后的 62 進(jìn)制數(shù)字做分表依據(jù)了，因?yàn)樗俏ㄒ坏穆铩?/p>

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

防止惡意攻擊

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

一開(kāi)始我們可以做一下簡(jiǎn)單地限流操作，例如：

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

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

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

總結(jié)

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

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

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

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

參考資料

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