您現在的位置: 网站首頁 / 網站建設 / 正文

短URL系統是怎麽設計的?

作者: admin 发布: 2015-6-4 14:10:5 分类: 網站建設 閱讀: 次 查看評論

  URL系统 网站优化 网站地址优化 301跳转

  最爛的回答

  實現一個算法,將長地址轉成短地址。實現長和短一一對應。然後再實現它的逆運算,將短地址還能換算回長地址。

  這個回答看起來挺完美的,然後候選人也會說現在時間比較短,如果給我時間我去找這個算法就解決問題了。但是稍微有點計算機或者信息論常識的人就能發現,這個算法就跟永動機一樣,是永遠不可能找到的。即使我們定義短地址是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系统做发号器。不停的自增就行了。第一个使用这个服务的人得到的短地址是 http://xx.xx/0 第二个是 http://xx.xx/1 第11个是 http://xx.xx/a 第依次往后,相当于实现了一个62进制的自增字段即可。

  幾個子問題

  1. 62进制如何用数据库或者KV存储来做?

  其實我們並不需要在存儲中用62進制,用10進制就好了。比如第10000個長地址,我們給它的短地址對應的編號是9999,我們通過存儲自增拿到9999後,再做一個10進制到62進制的轉換,轉成62進制數即可。這個10~62進制轉換,你完全都可以自己實現。

  2. 如何保证同一个长地址,每次转出来都是一样的短地址

  上面的发号原理中,是不判断长地址是否已经转过的。也就是说用拿着百度首頁地址来转,我给一个http://xx.xx/abc 过一段时间你再来转,我还会给你一个 http://xx.xx/xyz。这看起来挺不好的,但是不好在哪里呢?不好在不是一一对应,而一长对多短。这与我们完美主义的基因不符合,那么除此以外还有什么不对的地方?

  有人說它浪費空間,這是對的。同一個長地址,産生多條短地址記錄,這明顯是浪費空間的。那麽我們如何避免空間浪費,有人非常迅速的回答我,建立一個長對短的KV存儲即可。嗯,聽起來有理,但是。。。這個KV存儲本身就是浪費大量空間。所以我們是在用空間換空間,而且貌似是在用大空間換小空間。真的劃算嗎?這個問題要考慮一下。當然,也不是沒有辦法解決,我們做不到真正的一一對應,那麽打個折扣是不是可以搞定?

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

  我的方案是:用key-value存儲,保存“最近”生成的長對短的一個對應關系。注意是“最近”,也就是說,我並不保存全量的長對短的關系,而只保存最近的。比如采用一小時過期的機制來實現LRU淘汰。

  這樣的話,長轉短的流程變成這樣:

  在這個“最近”表中查看一下,看長地址有沒有對應的短地址

  有就直接返回,並且將這個key-value對的過期時間再延長成一小時

  如果沒有,就通過發號器生成一個短地址,並且將這個“最近”表中,過期時間爲1小時

  所以當一個地址被頻繁使用,那麽它會一直在這個key-value表中,總能返回當初生成那個短地址,不會出現重複的問題。如果它使用並不頻繁,那麽長對短的key會過期,LRU機制自動就會淘汰掉它。

  當然,這不能保證100%的同一個長地址一定能轉出同一個短地址,比如你拿一個生僻的url,每間隔1小時來轉一次,你會得到不同的短地址。但是這真的有關系嗎?

  3. 如何保证发号器的大并发高可用

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

  4. 具体存储如何选择

  這個問題就不展開說了,各有各道,主要考察一下對存儲的理解。對緩存原理的理解,和對市面上DB、Cache系統可用性,並發能力,一致性等方面的理解。

  5. 跳转用301还是302

  這也是一個有意思的話題。首先當然考察一個候選人對301和302的理解。浏覽器緩存機制的理解。然後是考察他的業務經驗。301是永久重定向,302是臨時重定向。短地址一經生成就不會變化,所以用301是符合http語義的。同時對服務器壓力也會有一定減少。

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

  來源:SEO搜尋引擎優化 - SEO自學網 轉載注明出處!

? 上一篇下一篇 ?   本文關鍵詞: URL  

評論列表:

站長SEO學院
第一節:百度搜索引擎工作原理
第二節:建設對搜索引擎友好的站點
第三節:如何進行網站內容建設
第四節:整體優化、結構優化、網頁優化
第五節:移動搜索-明確移動搜索優化標准
百度SEO資料文檔
百度搜索引擎優化指南2.0
百度移動搜索優化指南2.0
網站分析白皮書(站長版)
移動站點該如何優化
建設對百度友好的站點
百度搜索引擎網頁質量白皮書
石榴算法-綠蘿算法-冰桶算法
新搜索時代下的優化策略
更多百度SEO資料文檔
站長推薦
DIV+CSS布局實例教程-Web標准
网站SEO優化常见问题汇总
SEO優化推广方案该如何写
SEO優化方案步骤
影響網站關鍵詞排名因素總結
影響谷歌搜索引擎排名的因素調查
手機移動端站點適配優化
最近發表