最爛的回答

　　實(shí)現一個(gè)算法，將長(cháng)地址轉成短地址。實(shí)現長(cháng)和短一一對應。然后再實(shí)現它的逆運算，將短地址還能換算回長(cháng)地址。

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

　　再換一個(gè)說(shuō)法來(lái)反駁，如果真有這么一個(gè)算法和逆運算，那么基本上現在的壓縮軟件都可以歇菜了，而世界上所有的信息，都可以壓縮到100個(gè)字符。這～可能嗎。

　　另一個(gè)很爛的回答

　　和上面一樣，也找一個(gè)算法，把長(cháng)地址轉成短地址，但是不存在逆運算。我們需要把短對長(cháng)的關(guān)系存到DB中，在通過(guò)短查長(cháng)時(shí)，需要查DB。

　　怎么說(shuō)呢，沒(méi)有改變本質(zhì)，如果真有這么一個(gè)算法，那必然是會(huì )出現碰撞的，也就是多個(gè)長(cháng)地址轉成了同一個(gè)短地址。因為我們無(wú)法預知會(huì )輸入什么樣的長(cháng)地址到這個(gè)系統中，所以不可能實(shí)現這樣一個(gè)絕對不碰撞的hash函數。

　　比較爛的回答

　　那我們用一個(gè)hash算法，我承認它會(huì )碰撞，碰撞后我再在后面加1，2，3不就行了。西安做網(wǎng)站推薦閱讀>>> 網(wǎng)址URL上使用#號好不好，

　　ok，這樣的話(huà)，當通過(guò)這個(gè)hash算法算出來(lái)之后，可能我們會(huì )需要做btree式的大于小于或者like查找到能知道現在應該在后面加1，2，或3，這個(gè)也可能由于輸入的長(cháng)地址集的不確定性。導致生成短地址時(shí)間的不確定性。同樣爛的回答還有隨機生成一個(gè)短地址，去查找是否用過(guò)，用過(guò)就再隨機，如此往復，直到隨機到一個(gè)沒(méi)用過(guò)的短地址。

　　正確的原理

　　上面是幾種典型的錯誤回答，下面咱們直接說(shuō)正確的原理。

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

　　幾個(gè)子問(wèn)題

　　1. 62進(jìn)制如何用數據庫或者KV存儲來(lái)做？

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

　　2. 如何保證同一個(gè)長(cháng)地址，每次轉出來(lái)都是一樣的短地址

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

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

　　這個(gè)問(wèn)題的答案太多種，各有各招。這個(gè)方案最簡(jiǎn)單的是建立一個(gè)長(cháng)對短的hashtable，這樣相當于用空間來(lái)?yè)Q空間，同時(shí)換取一個(gè)設計上的優(yōu)雅（真正的一對一）。實(shí)際情況是有很多性?xún)r(jià)比高的打折方案可以用，這個(gè)方案設計因人而異了。那我就說(shuō)一下我的方案吧。

　　我的方案是：用key-value存儲，保存“最近”生成的長(cháng)對短的一個(gè)對應關(guān)系。注意是“最近”，也就是說(shuō)，我并不保存全量的長(cháng)對短的關(guān)系，而只保存最近的。比如采用一小時(shí)過(guò)期的機制來(lái)實(shí)現LRU淘汰。西安做網(wǎng)站推薦閱讀>>> URL曝光率與百度收錄關(guān)系的研究，

　　這樣的話(huà)，長(cháng)轉短的流程變成這樣：

　　在這個(gè)“最近”表中查看一下，看長(cháng)地址有沒(méi)有對應的短地址

　　有就直接返回，并且將這個(gè)key-value對的過(guò)期時(shí)間再延長(cháng)成一小時(shí)

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

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

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

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

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

　　4. 具體存儲如何選擇

　　這個(gè)問(wèn)題就不展開(kāi)說(shuō)了，各有各道，主要考察一下對存儲的理解。對緩存原理的理解，和對市面上DB、Cache系統可用性，并發(fā)能力，一致性等方面的理解。西安網(wǎng)站建設推薦閱讀>>> 如何優(yōu)化URL利于網(wǎng)站優(yōu)化？，

　　5. 跳轉用301還是302

　　這也是一個(gè)有意思的話(huà)題。首先當然考察一個(gè)候選人對301和302的理解。瀏覽器緩存機制的理解。然后是考察他的業(yè)務(wù)經(jīng)驗。301是永久重定向，302是臨時(shí)重定向。短地址一經(jīng)生成就不會(huì )變化，所以用301是符合http語(yǔ)義的。同時(shí)對服務(wù)器壓力也會(huì )有一定減少。

　　但是如果使用了301，我們就無(wú)法統計到短地址被點(diǎn)擊的次數了。而這個(gè)點(diǎn)擊次數是一個(gè)非常有意思的大數據分析數據源。能夠分析出的東西非常非常多。所以選擇302雖然會(huì )增加服務(wù)器壓力，但是我想是一個(gè)更好的選擇。