什么是短url

短url， 顧名思義，就是將長網(wǎng)址縮短到一個很短的網(wǎng)址，用戶訪問這個短網(wǎng)址可以重定向到原本的長網(wǎng)址（還原）。這樣可以達(dá)到易于記憶、轉(zhuǎn)換的目的，還有隱藏鏈接參數(shù)，利于短信推廣的作用，常用于有字?jǐn)?shù)限制的短信、微博、二維碼等場景。

錯誤答案

這個實現(xiàn)的思路真的是天花亂墜，此處總結(jié)幾種錯誤的實現(xiàn)方式來避坑。

1. 實現(xiàn)一個算法，可以直接把一百個字符左右的長網(wǎng)址縮短到10位以內(nèi)，并可以原樣還原，即可逆

不可能的。為所有可能存在的長鏈接實現(xiàn)一一對應(yīng),本身是不可能的,會出現(xiàn)碰撞,多個長鏈接對應(yīng)一個短鏈接，所以不會可逆。

2. 實現(xiàn)算法將長地址轉(zhuǎn)短地址,不實現(xiàn)逆運(yùn)算,將短長對應(yīng)關(guān)系存數(shù)據(jù)庫中

不可能的。沒有改變本質(zhì)(長鏈接數(shù)量遠(yuǎn)多于長鏈接),只要長鏈接夠多,必然會碰撞

3. 用一個hash算法,生成的短鏈接碰撞后,在短鏈接后面加1,2,3

物理邏輯上可行，生產(chǎn)應(yīng)用不可行。效率會不可控的降低，通過算法算出來短url之后,hash碰撞后生成多個xx1,xx2,xx3…xx20…的短url，長短對應(yīng)數(shù)量不可控，查找效率會降低。

4. 隨機(jī)生成一個短地址,去數(shù)據(jù)庫查找是否用過,用過就再隨機(jī),直到隨機(jī)到一個沒用過的短地址,存數(shù)據(jù)庫

物理邏輯上可行，生產(chǎn)應(yīng)用不可行。每次生成都有必要的全量查詢操作，肯定是不OK的。

5. 維護(hù)一個超級大的全量數(shù)據(jù)，預(yù)先生成超越實際生產(chǎn)使用的短url，接口調(diào)用直接頒發(fā)，同步修改短url使用狀態(tài)。

物理邏輯上可行，生產(chǎn)應(yīng)用低可用。具體是在redis還是db里批量生成其實是截然不同的兩種實現(xiàn)。

若是redis, 那么里面要放入全量的短url么？否則怎么知道這個短url到底是不是唯一的？如果全量，那對redis的可用性就要嚴(yán)格保證，為了高可用，就需要多節(jié)點同步維持全量數(shù)據(jù)，這個過程要做好不是那么的容易； 若是db, 那么就要有大量的并發(fā)鎖定，意味著大量讀寫，這個對數(shù)據(jù)庫也是個考驗。

正確答案

建立一個發(fā)號器,每次有一個新的長URL進(jìn)來,我們就增加一,并且將新的數(shù)值返回.第一個來的url返回"www.x.cn/0",第二個返回"www.x.cn/1".

細(xì)節(jié)問題

短url的還原跳轉(zhuǎn)用301還是302？

301是永久重定向，302是臨時重定向。

短地址一經(jīng)生成就不會變化，所以用301是符合http語義的。同時瀏覽器會對301請求保存一個比較長期的緩存，這樣就減輕對服務(wù)器的壓力；而且301對于網(wǎng)址的SEO有一定的提升。但是很多情況下我們需要對接口點擊或者用戶行為進(jìn)行一些業(yè)務(wù)監(jiān)控處理的時候，301明顯就不合適了（瀏覽器直接按照緩存數(shù)據(jù)跳轉(zhuǎn)了）, 所以很多業(yè)務(wù)場景下還是采用302比較合適。

字符超長問題

即使到了10億(Billion)轉(zhuǎn)換而成的62進(jìn)制也無非是6位字符，所以長度基本不在考慮范圍內(nèi)，這個范圍足夠使用了。

對應(yīng)關(guān)系如何存儲?

這個對應(yīng)數(shù)據(jù)肯定是要落盤的,不能每次系統(tǒng)重啟就重新排號,所以可以采用mysql等數(shù)據(jù)庫來存儲.而且如果數(shù)據(jù)量小且qps低,直接使用數(shù)據(jù)庫的自增主鍵就可以實現(xiàn).

如何保證長短鏈接一一對應(yīng)?

按照上面的發(fā)號器策略,是不能保證長短鏈接的一一對應(yīng)的,你連續(xù)用同一個URL請求兩次,結(jié)果值都是不一樣的.

為了實現(xiàn)長短鏈接一一對應(yīng),我們需要付出很大的空間代價,尤其是為了快速響應(yīng),我們可以需要在內(nèi)存中做一層緩存,這樣子太浪費(fèi)了.

但是可以實現(xiàn)一些變種的,來實現(xiàn)部分的一一對應(yīng), 比如將最近/最熱門的對應(yīng)關(guān)系存儲在K-V數(shù)據(jù)庫中,這樣子可以節(jié)省空間的同時,加快響應(yīng)速度.

短URL的存儲

我們返回的短URL一般是將數(shù)字轉(zhuǎn)換成62進(jìn)制,這樣子可以更加有效的縮短URL長度,那么62進(jìn)制的數(shù)字對計算機(jī)來說只是字符串,怎么存儲呢?直接存儲字符串對等值查找好找,對范圍查找等太不友好了.

其實可以直接存儲10進(jìn)制的數(shù)字,這樣不僅占用空間少,對查找的支持較好,同時還可以更加方便的轉(zhuǎn)換到更多/更少的進(jìn)制來進(jìn)一步縮短URL.

短碼安全問題

按照算法從0-61都是1位字符，然后2位、3位…這樣的話很容易被人發(fā)現(xiàn)規(guī)律并進(jìn)行攻擊，當(dāng)然防御手段很多，請求簽名之類的安全驗證手段不在本文討論范圍內(nèi)。

首先計數(shù)器可以從一個比較大的隨機(jī)中間值開始，比如從10000開始計數(shù)，他的62進(jìn)制是 2Bi 3位的字符串；

然后采用一些校驗位算法(比如Luhn改進(jìn)一下)，計算出1位校驗位拼接起來，4位短碼，這樣可以排除一定的安全風(fēng)險；

再加點安全料的話，可以在62進(jìn)制的轉(zhuǎn)換過程中把排序好的62個字母數(shù)字隨機(jī)打亂，比如ABCD1234打亂成1BC43A2D, 轉(zhuǎn)換的62進(jìn)制也就更難hack了；

最后如果仍不放心，還可以在某些位置（比如1，3，5）插入隨機(jī)數(shù)，讓人無法看出規(guī)律來也可以達(dá)到良好的效果。

同一長網(wǎng)址短url是否應(yīng)該相同問題

發(fā)號策略中,是不判斷長地址是否已轉(zhuǎn)過,所以造成結(jié)果就是一長對多短,有人說浪費(fèi)空間,建立一個長對短的map存儲即可,但是用map存儲本身就是浪費(fèi)大量空間,甚至是用大空間換小空間,這就要考慮是否真有必要做一一對應(yīng),不能一對多;

最簡單方案:建一個長對短的map,空間換空間,

更好的方案:用map存儲"最近"生成的長對短關(guān)系,一小時過期機(jī)制實現(xiàn)LRU淘汰

長對短流程:

這個“最近”表中查看一下，看長地址有沒有對應(yīng)的短地址

有就直接返回，并且將這個key-value對的過期時間重置為一小時

如果沒有，就通過發(fā)號器生成一個短地址，并且將這個“最近”表中，過期時間為1小時

當(dāng)一個地址被頻繁使用，那么它會一直在這個key-value表中，總能返回當(dāng)初生成那個短地址，不會出現(xiàn)重復(fù)的問題。如果它使用并不頻繁，那么長對短的key會過期，LRU機(jī)制自動就會淘汰掉它。

這樣在空間和發(fā)號數(shù)量之間取得了一個平衡，此處也應(yīng)該看具體的業(yè)務(wù)需求來，是否會存在一對多的情況。比如下單未支付，給用戶發(fā)短信召回，短信內(nèi)的短url里面存在用戶昵稱，訂單號等個性化信息，即不需要增加這一邏輯環(huán)節(jié)了。

高并發(fā)

如果直接存儲在MySQL中,當(dāng)并發(fā)請求增大,對數(shù)據(jù)庫的壓力太大,可能會造成瓶頸,這時候是可以有一些優(yōu)化的.

緩存

上面保證長短鏈接一一對應(yīng)中也提到過緩存,這里我們是為了加快程序處理速度.

可以將熱門的長鏈接(需要對長鏈接進(jìn)來的次數(shù)進(jìn)行計數(shù)),最近的長鏈接(可以使用redis保存最近一個小時的)等等進(jìn)行一個緩存,保存在內(nèi)存中或者類似redis的內(nèi)存數(shù)據(jù)庫中,如果請求的長URL命中了緩存,那么直接獲取對應(yīng)的短URL進(jìn)行返回,不需要再進(jìn)行生成操作.

批量發(fā)號

每一次發(fā)號都需要訪問一次MySQL來獲取當(dāng)前的最大號碼,并且在獲取之后更新最大號碼,這個壓力是比較大的.

我們可以每次從數(shù)據(jù)庫獲取10000個號碼,然后在內(nèi)存中進(jìn)行發(fā)放,當(dāng)剩余的號碼不足1000時,重新向MySQL請求下10000個號碼.在上一批號碼發(fā)放完了之后,批量進(jìn)行寫入.

這樣可以將對數(shù)據(jù)庫持續(xù)的操作移到代碼中進(jìn)行,并且異步進(jìn)行獲取和寫入操作,保證服務(wù)的持續(xù)高并發(fā).

分布式

上面設(shè)計的系統(tǒng)是有單點的,那就是發(fā)號器是個單點,容易掛掉.

可以采用分布式服務(wù),分布式的話,如果每一個發(fā)號器進(jìn)行發(fā)號之后都需要同步給其他發(fā)號器,那未必也太麻煩了.

換一種思路,可以有兩個發(fā)號器,一個發(fā)單號,一個發(fā)雙號,發(fā)號之后不再是遞增1,而是遞增2.

類比可得,我們可以用1000個服務(wù),分別發(fā)放0-999尾號的數(shù)字,每次發(fā)號之后遞增1000.這樣做很簡單,服務(wù)互相之間基本都不用通信,做好自己的事情就好了.

轉(zhuǎn)自

https://www.kancloud.cn/martist/be_new_friends/1901998
歡迎關(guān)注哦

總結(jié)

以上是生活随笔為你收集整理的答面试官问：如何设计短url服务的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。