最爛的回答
實(shí)現(xiàn)一個算法,將長地址轉(zhuǎn)成短地址。實(shí)現(xiàn)長和短一一對應(yīng)。然后再實(shí)現(xiàn)它的逆運(yùn)算,將短地址還能換算回長地址。
這個回答看起來挺完美的,然后候選人也會說現(xiàn)在時間比較短,如果給我時間我去找這個算法就解決問題了。但是稍微有點(diǎn)計(jì)算機(jī)或者信息論常識的人就能發(fā)現(xiàn),這個算法就跟永動機(jī)一樣,是永遠(yuǎn)不可能找到的。即使我們定義短地址是100位。那么它的變化是62的100次方。62=10數(shù)字+26大寫字母+26小寫字母。無論這個數(shù)多么大,他也不可能大過世界上可能存在的長地址。所以實(shí)現(xiàn)一一對應(yīng),本身就是不可能的。
再換一個說法來反駁,如果真有這么一個算法和逆運(yùn)算,那么基本上現(xiàn)在的壓縮軟件都可以歇菜了,而世界上所有的信息,都可以壓縮到100個字符。這~可能嗎。
另一個很爛的回答
和上面一樣,也找一個算法,把長地址轉(zhuǎn)成短地址,但是不存在逆運(yùn)算。我們需要把短對長的關(guān)系存到DB中,在通過短查長時,需要查DB。
怎么說呢,沒有改變本質(zhì),如果真有這么一個算法,那必然是會出現(xiàn)碰撞的,也就是多個長地址轉(zhuǎn)成了同一個短地址。因?yàn)槲覀儫o法預(yù)知會輸入什么樣的長地址到這個系統(tǒng)中,所以不可能實(shí)現(xiàn)這樣一個絕對不碰撞的hash函數(shù)。
比較爛的回答
那我們用一個hash算法,我承認(rèn)它會碰撞,碰撞后我再在后面加1,2,3不就行了。
ok,這樣的話,當(dāng)通過這個hash算法算出來之后,可能我們會需要做btree式的大于小于或者like查找到能知道現(xiàn)在應(yīng)該在后面加1,2,或3,這個也可能由于輸入的長地址集的不確定性。導(dǎo)致生成短地址時間的不確定性。同樣爛的回答還有隨機(jī)生成一個短地址,去查找是否用過,用過就再隨機(jī),如此往復(fù),直到隨機(jī)到一個沒用過的短地址。
正確的原理
上面是幾種典型的錯誤回答,下面咱們直接說正確的原理。
正確的原理就是通過發(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)于實(shí)現(xiàn)了一個62進(jìn)制的自增字段即可。
幾個子問題
1. 62進(jìn)制如何用數(shù)據(jù)庫或者KV存儲來做?
其實(shí)我們并不需要在存儲中用62進(jìn)制,用10進(jìn)制就好了。比如第10000個長地址,我們給它的短地址對應(yīng)的編號是9999,我們通過存儲自增拿到9999后,再做一個10進(jìn)制到62進(jìn)制的轉(zhuǎn)換,轉(zhuǎn)成62進(jìn)制數(shù)即可。這個10~62進(jìn)制轉(zhuǎn)換,你完全都可以自己實(shí)現(xiàn)。
2. 如何保證同一個長地址,每次轉(zhuǎn)出來都是一樣的短地址
上面的發(fā)號原理中,是不判斷長地址是否已經(jīng)轉(zhuǎn)過的。也就是說用拿著百度首頁地址來轉(zhuǎn),我給一個http://xx.xx/abc 過一段時間你再來轉(zhuǎn),我還會給你一個 http://xx.xx/xyz。這看起來挺不好的,但是不好在哪里呢?不好在不是一一對應(yīng),而一長對多短。這與我們完美主義的基因不符合,那么除此以外還有什么不對的地方?
有人說它浪費(fèi)空間,這是對的。同一個長地址,產(chǎn)生多條短地址記錄,這明顯是浪費(fèi)空間的。那么我們?nèi)绾伪苊饪臻g浪費(fèi),有人非常迅速的回答我,建立一個長對短的KV存儲即可。嗯,聽起來有理,但是。。。這個KV存儲本身就是浪費(fèi)大量空間。所以我們是在用空間換空間,而且貌似是在用大空間換小空間。真的劃算嗎?這個問題要考慮一下。當(dāng)然,也不是沒有辦法解決,我們做不到真正的一一對應(yīng),那么打個折扣是不是可以搞定?
這個問題的答案太多種,各有各招。這個方案最簡單的是建立一個長對短的hashtable,這樣相當(dāng)于用空間來換空間,同時換取一個設(shè)計(jì)上的優(yōu)雅(真正的一對一)。實(shí)際情況是有很多性價比高的打折方案可以用,這個方案設(shè)計(jì)因人而異了。那我就說一下我的方案吧。
我的方案是:用key-value存儲,保存“最近”生成的長對短的一個對應(yīng)關(guān)系。注意是“最近”,也就是說,我并不保存全量的長對短的關(guān)系,而只保存最近的。比如采用一小時過期的機(jī)制來實(shí)現(xiàn)LRU淘汰。
這樣的話,長轉(zhuǎn)短的流程變成這樣:
在這個“最近”表中查看一下,看長地址有沒有對應(yīng)的短地址
有就直接返回,并且將這個key-value對的過期時間再延長成一小時
如果沒有,就通過發(fā)號器生成一個短地址,并且將這個“最近”表中,過期時間為1小時
所以當(dāng)一個地址被頻繁使用,那么它會一直在這個key-value表中,總能返回當(dāng)初生成那個短地址,不會出現(xiàn)重復(fù)的問題。如果它使用并不頻繁,那么長對短的key會過期,LRU機(jī)制自動就會淘汰掉它。
當(dāng)然,這不能保證100%的同一個長地址一定能轉(zhuǎn)出同一個短地址,比如你拿一個生僻的url,每間隔1小時來轉(zhuǎn)一次,你會得到不同的短地址。但是這真的有關(guān)系嗎?
3. 如何保證發(fā)號器的大并發(fā)高可用
上面設(shè)計(jì)看起來有一個單點(diǎn),那就是發(fā)號器。如果做成分布式的,那么多節(jié)點(diǎn)要保持同步加1,多點(diǎn)同時寫入,這個嘛,以CAP理論看,是不可能真正做到的。其實(shí)這個問題的解決非常簡單,我們可以退一步考慮,我們是否可以實(shí)現(xiàn)兩個發(fā)號器,一個發(fā)單號,一個發(fā)雙號,這樣就變單點(diǎn)為多點(diǎn)了?依次類推,我們可以實(shí)現(xiàn)1000個邏輯發(fā)號器,分別發(fā)尾號為0到999的號。每發(fā)一個號,每個發(fā)號器加1000,而不是加1。這些發(fā)號器獨(dú)立工作,互不干擾即可。而且在實(shí)現(xiàn)上,也可以先是邏輯的,真的壓力變大了,再拆分成獨(dú)立的物理機(jī)器單元。1000個節(jié)點(diǎn),估計(jì)對人類來說應(yīng)該夠用了。如果你真的還想更多,理論上也是可以的。
4. 具體存儲如何選擇
這個問題就不展開說了,各有各道,主要考察一下對存儲的理解。對緩存原理的理解,和對市面上DB、Cache系統(tǒng)可用性,并發(fā)能力,一致性等方面的理解。
5. 跳轉(zhuǎn)用301還是302
這也是一個有意思的話題。首先當(dāng)然考察一個候選人對301和302的理解。瀏覽器緩存機(jī)制的理解。然后是考察他的業(yè)務(wù)經(jīng)驗(yàn)。301是永久重定向,302是臨時重定向。短地址一經(jīng)生成就不會變化,所以用301是符合http語義的。同時對服務(wù)器壓力也會有一定減少。
但是如果使用了301,我們就無法統(tǒng)計(jì)到短地址被點(diǎn)擊的次數(shù)了。而這個點(diǎn)擊次數(shù)是一個非常有意思的大數(shù)據(jù)分析數(shù)據(jù)源。能夠分析出的東西非常非常多。所以選擇302雖然會增加服務(wù)器壓力,但是我想是一個更好的選擇。
轉(zhuǎn)載請保留原文地址: http://biwz.cn/show-405.html