1. <tr id="33chb"><label id="33chb"></label></tr>
  2. <pre id="33chb"></pre>
    當前位置:首頁 > 短網址資訊 > 正文內容

    ShortURL(短網址)系統邏輯是怎么設計的?

    個人相關:三年前在公司做過一個短地址服務,目前在線上跑。 而這個問題,也是我現在招聘面試題里面必考的一道,這一道題里面有很多可考的地方,能夠相對綜合的考察候選人的功力。

    最爛的回答 實現一個算法,將長地址轉成短地址。實現長和短一一對應。然后再實現它的逆運算,將短地址還能換算回長地址。這個回答看起來挺完美的,然后候選人也會說現在時間比較短,如果給我時間我去找這個算法就解決問題了。但是稍微有點計算機或者信息論常識的人就能發現,這個算法就跟永動機一樣,是永遠不可能找到的。即使我們定義短地址是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 第二個是 u6.gg/1 第11個是 u6.gg/a 第依次往后,相當于實現了一個62進制的自增字段即可。

    幾個子問題

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

    2. 如何保證同一個長地址,每次轉出來都是一樣的短地址上面的發號原理中,是不判斷長地址是否已經轉過的。也就是說用拿著百度首頁地址來轉,我給一個u6.gg/abc 過一段時間你再來轉,我還會給你一個 u6.gg/xyz。這看起來挺不好的,但是不好在哪里呢?不好在不是一一對應,而一長對多短。這與我們完美主義的基因不符合,那么除此以外還有什么不對的地方? 有人說它浪費空間,這是對的。同一個長地址,產生多條短地址記錄,這明顯是浪費空間的。那么我們如何避免空間浪費,有人非常迅速的回答我,建立一個長對短的KV存儲即可。嗯,聽起來有理,但是。。。這個KV存儲本身就是浪費大量空間。所以我們是在用空間換空間,而且貌似是在用大空間換小空間。真的劃算嗎?這個問題要考慮一下。當然,也不是沒有辦法解決,我們做不到真正的一一對應,那么打個折扣是不是可以搞定?這個問題的答案太多種,各有各招,我這就不說了。(由于實在太多人糾結這個問題,請見我最下方的更新

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

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

    5. 跳轉用301還是302這也是一個有意思的話題。首先當然考察一個候選人對301和302的理解。瀏覽器緩存機制的理解。然后是考察他的業務經驗。301是永久重定向,302是臨時重定向。短地址一經生成就不會變化,所以用301是符合http語義的。同時對服務器壓力也會有一定減少。 但是如果使用了301,我們就無法統計到短地址被點擊的次數了。而這個點擊次數是一個非常有意思的大數據分析數據源。能夠分析出的東西非常非常多。所以選擇302雖然會增加服務器壓力,但是我想是一個更好的選擇。

    大概就是這樣。

    ------端午假期后更新------- 就回答一點大家最糾結的問題吧,就是如何實現同一個長地址多次轉換,出來還是同一個短地址。

    我上面其實講到了,這個方案最簡單的是建立一個長對短的hashtable,這樣相當于用空間來換空間,同時換取一個設計上的優雅(真正的一對一)。

    實際情況是有很多性價比高的打折方案可以用,這個方案設計因人而異了。那我就說一下我的方案吧。

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

    這樣的話,長轉短的流程變成這樣: 1 在這個“最近”表中查看一下,看長地址有沒有對應的短網址 1.1 有就直接返回,并且將這個key-value對的過期時間再延長成一小時 1.2 如果沒有,就通過發號器生成一個短地址,并且將這個“最近”表中,過期時間為1小時

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

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


    掃描二維碼推送至手機訪問。

    版權聲明:本文由短鏈接發布,如需轉載請注明出處。

    本文鏈接:http://www.virginiabusinesslawupdate.com/article_147.html

    分享給朋友:

    相關文章

    【FT12短網址】ES8 新特性一覽

    【FT12短網址】ES8 新特性一覽

    引言感覺這一兩年FT12短網址的發展速度很快,首先最直接的體驗就是短鏈接打開速度成倍的在提升,其次是新增了很多實用的新功能,比如:新增了二維碼生成功能;新增了短鏈接訪問統計功能;新增了短網址生成者的ip記錄功能。這一切都應該歸功于實用了ES...

    微博開源的Motan RPC最新進展:新增跨語言及服務治理支持

    微博開源的Motan RPC最新進展:新增跨語言及服務治理支持

    https://github.com/weibocom/motanMotan 是一個基于 Java 開發的高性能的輕量級 RPC 框架,Motan 提供了豐富的服務治理功能和優秀的擴展能力,可以方便的基于 Motan 進行二次開發。Mota...

    短網址網站對每條短鏈接安全性的檢測方法

    短網址站,顧名思義就是把長網址縮短成很短的短鏈接并提供跳轉服務。當用戶訪問短鏈接時,短網址站會檢索數據庫中此條短鏈接對應的真實網址,并快速跳轉到真實的長網址。世界本來就是一片祥和,但是總有一些不法分子利用短鏈接來隱藏真實網址,然后群發惡意網...

    t.cn短鏈接的今生與前世

    也許是無意之作,t.cn短鏈接就非常突兀的出現在了新浪微博,這個事情還得從新浪微博的發展說起。2010左右,新浪推出了微博并一舉威脅到了騰訊的QQ空間,頓時間無人不刷微博。逐漸的,微博成了人們生活中不可或缺的一個應用,無論是吃飯、睡覺、走路...

    創業者除了沒有性生活,還有這些不為人知的隱疾……

    有一篇名為《最難的時候,劉強東姚勁波是怎么過來的》的文章,生動描述了58同城的姚建波在創業最困難時,在壓力下落淚的故事。美劇《硅谷》第二季中劇中主人公、創始人Richard因為創業的壓力嚴重盜汗、甚至可能小便失禁,這一劇情真實反映了很多創業...

    騰訊推行信用分的背后,或許是小程序電商的鋪墊

    騰訊推行信用分的背后,或許是小程序電商的鋪墊

    前言  最近騰訊信譽分開端進行灰度測驗,引起了相當多的重視?! ∈聦嵣?,騰訊信征早已對外開放,而且推出時刻和芝麻信譽一樣,同樣是2015年?! ≈徊贿^彼時騰訊只推出了信征報告,能夠查詢的內容也比較有限,其給出當前信譽較好、較差,以及當前排名...

    發表評論

    訪客

    ◎歡迎參與討論,請在這里發表您的看法和觀點。
    一本色综合网久久
    1. <tr id="33chb"><label id="33chb"></label></tr>
    2. <pre id="33chb"></pre>