華閱文章網1.短URL 系統是怎么設計的
最爛的回答 實現一個算法，將長地址轉成短地址。
實現長和短一一對應。然后再實現它的逆運算，將短地址還能換算回長地址。
這個回答看起來挺完美的，然后候選人也會說現在時間比較短，如果給我時間我去找這個算法就解決問題了。但是稍微有點計算機或者信息論常識的人就能發現，這個算法就跟永動機一樣，是永遠不可能找到的。
即使我們定義短地址是100位。那么它的變化是62的100次方。
62=10數字+26大寫字母+26小寫字母。無論這個數多么大，他也不可能大過世界上可能存在的長地址。
所以實現一一對應，本身就是不可能的。 再換一個說法來反駁，如果真有這么一個算法和逆運算，那么基本上現在的壓縮軟件都可以歇菜了，而世界上所有的信息，都可以壓縮到100個字符。
這~可能嗎。 另一個很爛的回答 和上面一樣，也找一個算法，把長地址轉成短地址，但是不存在逆運算。
我們需要把短對長的關系存到DB中，在通過短查長時，需要查DB。 怎么說呢，沒有改變本質，如果真有這么一個算法，那必然是會出現碰撞的，也就是多個長地址轉成了同一個短地址。
因為我們無法預知會輸入什么樣的長地址到這個系統中，所以不可能實現這樣一個絕對不碰撞的hash函數。 比較爛的回答 那我們用一個hash算法，我承認它會碰撞，碰撞后我再在后面加1,2,3不就行了。
ok，這樣的話，當通過這個hash算法算出來之后，可能我們會需要做btree式的大于小于或者like查找到能知道現在應該在后面加1,2，或 3，這個也可能由于輸入的長地址集的不確定性。導致生成短地址時間的不確定性。
同樣爛的回答還有隨機生成一個短地址，去查找是否用過，用過就再隨機，如此往復，直到隨機到一個沒用過的短地址。 正確的原理 上面是幾種典型的錯誤回答，下面咱們直接說正確的原理。
正確的原理就是通過發號策略，給每一個過來的長地址，發一個號即可，小型系統直接用mysql的自增索引就搞定了。如果是大型應用，可以考慮各種分布式key-value系統做發號器。
不停的自增就行了。第一個使用這個服務的人得到的短地址是 **0 第二個是 **1 第11個是 **a 第依次往后，相當于實現了一個62進制的自增字段即可。
幾個子問題 1. 62進制如何用數據庫或者KV存儲來做？ 其實我們并不需要在存儲中用62進制，用10進制就好了。比如第10000個長地址，我們給它的短地址對應的編號是9999，我們通過存儲自增拿到9999后，再做一個10進制到62進制的轉換，轉成62進制數即可。
這個10~62進制轉換，你完全都可以自己實現。 2. 如何保證同一個長地址，每次轉出來都是一樣的短地址 上面的發號原理中，是不判斷長地址是否已經轉過的。
也就是說用拿著百度首頁地址來轉，我給一個**abc 過一段時間你再來轉，我還會給你一個 **xyz。這看起來挺不好的，但是不好在哪里呢？不好在不是一一對應，而一長對多短。
這與我們完美主義的基因不符合，那么除此以外還有什么不對的地方？ 有人說它浪費空間，這是對的。同一個長地址，產生多條短地址記錄，這明顯是浪費空間的。
那么我們如何避免空間浪費，有人非常迅速的回答我，建立一個長對短的KV存儲即可。嗯，聽起來有理，但是。
這個KV存儲本身就是浪費大量空間。所以我們是在用空間換空間，而且貌似是在用大空間換小空間。
真的劃算嗎？這個問題要考慮一下。當然，也不是沒有辦法解決，我們做不到真正的一一對應，那么打個折扣是不是可以搞定？ 這個問題的答案太多種，各有各招。
這個方案最簡單的是建立一個長對短的hashtable，這樣相當于用空間來換空間，同時換取一個設計上的優雅（真正的一對一）。實際情況是有很多性價比高的打折方案可以用，這個方案設計因人而異了。
那我就說一下我的方案吧。 我的方案是：用key-value存儲，保存“最近”生成的長對短的一個對應關系。
注意是“最近”，也就是說，我并不保存全量的長對短的關系，而只保存最近的。比如采用一小時過期的機制來實現LRU淘汰。
這樣的話，長轉短的流程變成這樣： 在這個“最近”表中查看一下，看長地址有沒有對應的短地址 有就直接返回，并且將這個key-value對的過期時間再延長成一小時 如果沒有，就通過發號器生成一個短地址，并且將這個“最近”表中，過期時間為1小時 所以當一個地址被頻繁使用，那么它會一直在這個key-value表中，總能返回當初生成那個短地址，不會出現重復的問題。如果它使用并不頻繁，那么長對短的key會過期，LRU機制自動就會淘汰掉它。
當然，這不能保證100%的同一個長地址一定能轉出同一個短地址，比如你拿一個生僻的url，每間隔1小時來轉一次，你會得到不同的短地址。但是這真的有關系嗎？ 3. 如何保證發號器的大并發高可用 上面設計看起來有一個單點，那就是發號器。
如果做成分布式的，那么多節點要保持同步加1，多點同時寫入，這個嘛，以CAP理論看，是不可能真正做到的。其實這個問題的解決非常簡單，我們可以退一步考慮，我們是否可以實現兩個發號器，一個發單號，一個發雙號，這樣就變單點為多點了？依次類推，我們可以實現1000個邏輯發號器，分別發尾號為0到。