如何優(yōu)雅的設(shè)計(jì)一套高性能短網(wǎng)址服務(wù)

文 |?豆豆

來(lái)源：Python 技術(shù)「ID: pythonall」

得益于移動(dòng)互聯(lián)網(wǎng)的蓬勃發(fā)展，自媒體日益火爆的同時(shí)其門檻也越來(lái)越低，可以說(shuō)是全民自媒體。其中內(nèi)容創(chuàng)作平臺(tái)尤為火爆，比如微信公眾號(hào)、微博、知乎、頭條等。隨之而來(lái)的就是各種「奇葩」需求，比如將長(zhǎng)鏈接轉(zhuǎn)換為短鏈接。

相信大家也都見過下面這種短信，極客時(shí)間的營(yíng)銷短信，就是短鏈接，點(diǎn)擊之后會(huì)跳轉(zhuǎn)到下面這個(gè)長(zhǎng)鏈接，那么為啥要那么麻煩轉(zhuǎn)換成短鏈接呢，直接用原始鏈接不就好了么。

https://shop18793264.m.youzan.com/v2/feature/pqzBz4KeGT?dc_ps=2663040806184605700.200001

其實(shí)之所以需要短鏈接其一是因?yàn)槌杀靖汀Ｎ覀兌贾蓝绦攀怯凶謹(jǐn)?shù)限制的，所以用長(zhǎng)鏈接的話運(yùn)營(yíng)商有可能將短信拆分為兩條或者多條來(lái)發(fā)送，成本增加一倍。

其二是因?yàn)樾Ч谩：帽任⒉┮彩怯凶謹(jǐn)?shù)限制的，如果如我們想在微博發(fā)一個(gè)引流文，引導(dǎo)用戶點(diǎn)擊我們的注冊(cè)鏈接，但因?yàn)槲⒉┯?140 字的限制，我們的注冊(cè)鏈接又比較長(zhǎng)，如果我們可以將長(zhǎng)鏈接轉(zhuǎn)換為短鏈接的話，那豈不是就可以編輯更多的文字來(lái)吸引用戶了么。

另外，有時(shí)候是不方便直接放鏈接的，比如微信公眾號(hào)是不允許放外鏈的，那么我們就可以將鏈接轉(zhuǎn)換為二維碼引導(dǎo)用戶掃描二維碼即可，短鏈接比長(zhǎng)鏈接轉(zhuǎn)換出來(lái)的二維碼更清晰易識(shí)別。

那么如果讓你來(lái)設(shè)計(jì)一套短鏈接服務(wù)，你會(huì)怎么設(shè)計(jì)呢，同時(shí)這也是一道用來(lái)考察候選人基本功的常用面試題。

最糟糕的設(shè)計(jì)

首先我們梳理下需求，即我們想要讓網(wǎng)址變短之后依然不影響使用。

那么我們是否可以設(shè)計(jì)一個(gè)算法，將長(zhǎng)鏈接和短鏈接一一對(duì)應(yīng)呢。該算法接收一個(gè)長(zhǎng)鏈接的參數(shù)，輸出其對(duì)應(yīng)的短鏈接，當(dāng)服務(wù)器收到短鏈接的請(qǐng)求后，再通過逆運(yùn)算將短鏈接變成長(zhǎng)鏈接，這樣一來(lái)不不就很容易實(shí)現(xiàn)長(zhǎng)鏈接變短鏈接的需求了么。

只是這里有個(gè)問題我們可能忽略了，事實(shí)上世界上的長(zhǎng)鏈接個(gè)數(shù)是趨于正無(wú)窮的，有限長(zhǎng)度的字符串只能表示有限個(gè)短鏈接，假設(shè)短鏈接的長(zhǎng)度為 20 位，那么最多只能表示 62 的 20 次方個(gè)短鏈接，無(wú)法做到和正無(wú)窮個(gè)長(zhǎng)鏈接一一對(duì)應(yīng)。

次糟糕的設(shè)計(jì)

回到原點(diǎn)，我們只不過是想將長(zhǎng)網(wǎng)址變短而已，變短不就是數(shù)據(jù)壓縮嗎，簽名算法可以不，比如 MD5、SHA 等散列算法。這些算法可以將任何長(zhǎng)度的字符串壓縮到固定長(zhǎng)度。

但是它們也是有問題的，首先 MD5 有可能碰撞我們不說(shuō)，單就 MD5 簽名之后的字符串長(zhǎng)度是定長(zhǎng)這一點(diǎn)我們是無(wú)法接受的，有可能能能我們的長(zhǎng)網(wǎng)址都沒有 32 位那么長(zhǎng)，這樣一來(lái)不僅沒有變短，反而變長(zhǎng)了，這設(shè)計(jì)不合理。

另外 MD5 這類函數(shù)通常用于加密，其性能不是很高，我們并不關(guān)心安全性，只關(guān)心轉(zhuǎn)換效率和哈希之后的沖突概率而已。

常規(guī)的設(shè)計(jì)

既然要把長(zhǎng)鏈接映射成短鏈接，哈希算法就是做這個(gè)事情的嘛，只不過上面的設(shè)計(jì)選的哈希算法不好而已。效率高的哈希算法很多，推薦 Murmur 哈希，Murmur 哈希是一種非加密散列函數(shù)，適用于一般的基于散列的查找。非加密意味著效率更高，該哈希算法會(huì)一個(gè) 32 位或者 64 位的值，32 位最多表示 42億+ 個(gè)記錄，對(duì)于常規(guī)業(yè)務(wù)來(lái)講足夠用了。

假設(shè)我么對(duì)一個(gè)網(wǎng)址哈希之后的值是 4003787369，那么生成的短鏈接就是?https://domain/4003787369，其中前面的域名就是我們的短鏈接服務(wù)器域名。如果你覺得域名還是長(zhǎng)，那么可以將十進(jìn)制的 4003787369 轉(zhuǎn)換為 62 進(jìn)制，轉(zhuǎn)換之后的結(jié)果為：4mXtZD，即?https://domain/4mXtZD，從 10 位直接縮短為 6 位。

既然是哈希函數(shù)，肯定會(huì)產(chǎn)生哈希沖突，那如何解決哈希沖突呢？

這里假設(shè)我們將長(zhǎng)鏈接和短鏈接的對(duì)應(yīng)關(guān)系是存儲(chǔ)在數(shù)據(jù)庫(kù)的，該表有四列，分別是：id、long_url、short_url、create_time， 我們可以在?short_url?列建立一個(gè)唯一索引，當(dāng)我們得到一個(gè)長(zhǎng)鏈接和短鏈接的對(duì)應(yīng)關(guān)系后，直接插入數(shù)據(jù)庫(kù)，如果插入失敗說(shuō)明有沖突，這是需要給長(zhǎng)鏈接添加混淆字符串再次求哈希，之后在插入，如果還沖突就重復(fù)剛才的過程，直到插入成功。

事實(shí)上 Murmur 哈希算法的沖突是很低的，基本可以忽略。

最佳設(shè)計(jì)

除了對(duì)長(zhǎng)鏈接進(jìn)行哈希運(yùn)算之后，我們還可以通過發(fā)號(hào)策略，給每一個(gè)長(zhǎng)鏈接發(fā)一個(gè)號(hào)碼，你可以把發(fā)號(hào)策略理解為 ID 生成器。

這樣子，第一個(gè)來(lái)的長(zhǎng)網(wǎng)址對(duì)應(yīng)的短鏈接是?https://domain/1，第二個(gè)長(zhǎng)鏈接對(duì)應(yīng)的短鏈接是?https://domain/2，依次遞增。拿到號(hào)碼之后，我們可以將該號(hào)碼作為主鍵存儲(chǔ)該長(zhǎng)網(wǎng)址記錄，同時(shí)因?yàn)?MySQL 根據(jù)主鍵去獲取記錄的速度是超級(jí)快的，所以這種方式我們不需要擔(dān)心查詢的性能問題。

這里我們唯一需要關(guān)心的就是發(fā)號(hào)策略了，業(yè)務(wù)量不大的話，我們可以直接用 MySQL 的自增序列來(lái)實(shí)現(xiàn)；如果是大型應(yīng)用，就需要考慮高并發(fā)了。我們可以多部署一些節(jié)點(diǎn)，比如部署 1000 個(gè)節(jié)點(diǎn)，每個(gè)發(fā)號(hào)器發(fā)完一個(gè)號(hào)之后不在自增 1 ，而是自增 1000。比如對(duì)于 1 號(hào)發(fā)號(hào)器，其發(fā)送的號(hào)碼依次是：1、1001、2001、3001...，如對(duì)于 2 號(hào)發(fā)號(hào)器，其發(fā)送的號(hào)碼依次是：2、1002、2002、3002...

如此一來(lái)，即保證了我們的發(fā)號(hào)器永遠(yuǎn)不會(huì)發(fā)出重復(fù)的號(hào)碼，也保證了號(hào)碼是遞增的，主鍵遞增對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)太重要了。

那如果遇到相同的長(zhǎng)鏈接如何處理呢，直接查表嗎？

直接查表怕是會(huì)浪費(fèi)太多時(shí)間，我們可以做一個(gè) LRU 緩存，當(dāng)有請(qǐng)求過來(lái)時(shí)，我們只需要判斷該網(wǎng)址是否在 LRU 緩存中即可，若存在，則直接返回，否則直接生成對(duì)應(yīng)關(guān)系后將該記錄加入緩存。

只不過這樣一來(lái)的話，對(duì)于那些不熱門的網(wǎng)址，可能會(huì)生成多個(gè)對(duì)應(yīng)關(guān)系，事實(shí)上我們也沒必要非得做到一一對(duì)應(yīng)，一個(gè)長(zhǎng)鏈接對(duì)應(yīng)多個(gè)短鏈接對(duì)業(yè)務(wù)來(lái)說(shuō)沒什么影響，而且不熱門網(wǎng)址出現(xiàn)頻率本來(lái)就很低，不會(huì)浪費(fèi)多少空間。

短鏈接原理

打開極客時(shí)間發(fā)我給的短鏈接，調(diào)出開發(fā)者工具來(lái)看看網(wǎng)絡(luò)請(qǐng)求。

由上圖我們可以得知，瀏覽器請(qǐng)求短鏈接的時(shí)候服務(wù)器返回了 302 狀態(tài)碼，然后瀏覽器重新發(fā)起了一次請(qǐng)求到長(zhǎng)鏈接，主要原理就是用到了重定向，我們知道 302 狀態(tài)碼和 301 狀態(tài)碼都是表示重定向，那么為啥返回 302 而不是 301 呢。

301 是永久重定向，瀏覽器第一次拿到長(zhǎng)鏈接后，后面再去請(qǐng)求短鏈接都不會(huì)在請(qǐng)求短鏈接服務(wù)器了，而是直接從本地緩存獲取，正常來(lái)說(shuō)短鏈接一經(jīng)生成是不會(huì)在變化的了，那么使用 301 狀態(tài)碼不管在正常邏輯方面還是 http 語(yǔ)義方面都是合情合理的呀，同時(shí)對(duì)短鏈接服務(wù)器的壓力也會(huì)小很多。但是如果使用 301 狀態(tài)碼我們是無(wú)法統(tǒng)計(jì)到該鏈接的點(diǎn)擊次數(shù)的，如果我們想分析活動(dòng)的效果的話，點(diǎn)擊次數(shù)可是一個(gè)很重要的指標(biāo)哦，返回 302 增加點(diǎn)服務(wù)器壓力是值得的。

總結(jié)

關(guān)于以上如何生成短鏈接，我們介紹了四種方案，其中第一種壓根不可行，第二種設(shè)計(jì)不是很合理，第三種對(duì)于業(yè)務(wù)量不大的系統(tǒng)來(lái)說(shuō)足夠了，第四種則是最佳實(shí)踐。

今天我們?cè)敿?xì)闡述了如何設(shè)計(jì)一個(gè)高性能短鏈接服務(wù)，該問題看似簡(jiǎn)單，實(shí)則涉及很多知識(shí)點(diǎn)，像短鏈接跳轉(zhuǎn)原理，301 還是 302，以及如何更快更好的生成短鏈接，希望小伙伴們能有所收獲，下次在遇到這道題時(shí)可以吊打面試官。

PS：公號(hào)內(nèi)回復(fù)「Python」即可進(jìn)入Python 新手學(xué)習(xí)交流群，一起?100 天計(jì)劃！

老規(guī)矩，兄弟們還記得么，右下角的 “在看” 點(diǎn)一下，如果感覺文章內(nèi)容不錯(cuò)的話，記得分享朋友圈讓更多的人知道！

【神秘禮包獲取方式】