短URL系統(tǒng)是怎么設(shè)計的？

■田鵬晨

短URL系統(tǒng)是怎么設(shè)計的？

■田鵬晨

實現(xiàn)一個算法，將長地址轉(zhuǎn)成短地址。實現(xiàn)長和短一一對應(yīng)。然后再實現(xiàn)它的逆運算，將短地址還能換算回長地址。

這個回答看起來挺完美的，然后候選人也會說現(xiàn)在時間比較短，如果給我時間我去找這個算法就解決問題了。但是稍微有點計算機或者信息論常識的人就能發(fā)現(xiàn)，這個算法就跟永動機一樣，是永遠不可能找到的。即使我們定義短地址是100位。那么它的變化是62的100次方。62=10數(shù)字+26大寫字母+26小寫字母。無論這個數(shù)多么大，他也不可能大過世界上可能存在的長地址。所以實現(xiàn)一一對應(yīng)，本身就是不可能的。

正確的原理是通過發(fā)號策略，給每一個過來的長地址，發(fā)一個號即可，小型系統(tǒng)直接用mysql的自增索引就搞定了。如果是大型應(yīng)用，可以考慮各種分布式key-value系統(tǒng)做發(fā)號器。不停的自增就行了。第一個使用這個服務(wù)的人得到的短地址是http://xx.xx/0第二個是http://xx.xx/1第11個是http: //xx.xx/a第依次往后，相當(dāng)于實現(xiàn)了一個62進制的自增字段即可。

幾個子問題

1.62進制如何用數(shù)據(jù)庫或者KV存儲來做

其實我們并不需要在存儲中用62進制，用10進制就好了。比如第10000個長地址，我們給它的短地址對應(yīng)的編號是9999，我們通過存儲自增拿到9999后，再做一個10進制到62進制的轉(zhuǎn)換，轉(zhuǎn)成62進制數(shù)即可。這個10～62進制轉(zhuǎn)換，你完全都可以自己實現(xiàn)。

2.如何保證同一個長地址，每次轉(zhuǎn)出來都是一樣的短地址

上面的發(fā)號原理中，是不判斷長地址是否已經(jīng)轉(zhuǎn)過的。也就是說用拿著百度首頁地址來轉(zhuǎn)，我給一個http://xx.xx/abc過一段時間你再來轉(zhuǎn)，我還會給你一個http://xx.xx/xyz。這看起來挺不好的，但是不好在哪里呢？不好在不是一一對應(yīng)，而一長對多短。這與我們完美主義的基因不符合，那么除此以外還有什么不對的地方？

有人說它浪費空間，這是對的。同一個長地址，產(chǎn)生多條短地址記錄，這明顯是浪費空間的。那么我們?nèi)绾伪苊饪臻g浪費，有人非常迅速的回答我，建立一個長對短的KV存儲即可。嗯，聽起來有理，但是......這個KV存儲本身就是浪費大量空間。所以我們是在用空間換空間，而且貌似是在用大空間換小空間。真的劃算嗎？這個問題要考慮一下。當(dāng)然，也不是沒有辦法解決，我們做不到真正的一一對應(yīng)，那么打個折扣是不是可以搞定？

這個問題的答案太多種，各有各招。這個方案最簡單的是建立一個長對短的hashtable，這樣相當(dāng)于用空間來換空間，同時換取一個設(shè)計上的優(yōu)雅（真正的一對一）。實際情況是有很多性價比高的打折方案可以用，這個方案設(shè)計因人而異了。那就說一下我的方案吧。

我的方案是：用key-value存儲，保存“最近”生成的長對短的一個對應(yīng)關(guān)系。注意是“最近”，也就是說，我并不保存全量的長對短的關(guān)系，而只保存最近的。比如采用一小時過期的機制來實現(xiàn)LRU淘汰。

這樣的話，長轉(zhuǎn)短的流程變成這樣：

在這個“最近”表中查看一下，看長地址有沒有對應(yīng)的短地址，有就直接返回，并且將這個key-value對的過期時間再延長成一小時。如果沒有，就通過發(fā)號器生成一個短地址，并且將這個“最近”表中，過期時間為1小時。

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

當(dāng)然，這不能保證100%的同一個長地址一定能轉(zhuǎn)出同一個短地址，比如你拿一個生僻的url，每間隔1小時來轉(zhuǎn)一次，你會得到不同的短地址。但是這真的有關(guān)系嗎？

3.如何保證發(fā)號器的大并發(fā)高可用

上面設(shè)計看起來有一個單點，那就是發(fā)號器。如果做成分布式的，那么多節(jié)點要保持同步加1，多點同時寫入，這個嘛，以CAP理論看，是不可能真正做到的。其實這個問題的解決非常簡單，我們可以退一步考慮，我們是否可以實現(xiàn)兩個發(fā)號器，一個發(fā)單號，一個發(fā)雙號，這樣就變單點為多點了？依次類推，我們可以實現(xiàn)1000個邏輯發(fā)號器，分別發(fā)尾號為0到999的號。每發(fā)一個號，每個發(fā)號器加1000，而不是加1。這些發(fā)號器獨立工作，互不干擾即可。而且在實現(xiàn)上，也可以先是邏輯的，真的壓力變大了，再拆分成獨立的物理機器單元。1000個節(jié)點，估計對人類來說應(yīng)該夠用了。如果你真的還想更多，理論上也是可以的。