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