短網(wǎng)址 顧名思義，就是將長網(wǎng)址縮短到一個(gè)很短的網(wǎng)址，用戶訪問這個(gè)短網(wǎng)址可以重定向到原本的長網(wǎng)址（還原）戳护。這樣可以達(dá)到易于記憶、轉(zhuǎn)換的目的瀑焦，常用于有字?jǐn)?shù)限制的微博腌且、二維碼等場景。
開篇先拋出幾個(gè)問題蝠猬，如果大家自己去實(shí)現(xiàn)會(huì)怎么實(shí)現(xiàn)這個(gè)看似很簡單的服務(wù)呢切蟋？
是否有什么算法可以直接把一百個(gè)字符左右的長網(wǎng)址縮短到10位以內(nèi)，并可以原樣還原榆芦，即可逆柄粹。
10倍的壓縮比在無損壓縮算法領(lǐng)域誰介紹下？當(dāng)然這個(gè)比例是基于多樣數(shù)據(jù)而不是特定的文本匆绣，否則文本只有一個(gè)字符a驻右，那壓縮比想多少有多少。只實(shí)現(xiàn)字符壓縮/hash崎淳，不需要做到可逆堪夭，然后存儲(chǔ)到數(shù)據(jù)庫中，恢復(fù)時(shí)只需要查詢數(shù)據(jù)庫拣凹。
從壓縮的角度和第一條說明沒有區(qū)別森爽，不可能無損壓縮，那就有可能出現(xiàn)hash碰撞嚣镜。不同的長網(wǎng)址縮短成了同一個(gè)短網(wǎng)址爬迟，那也做不到還原了。接著第二條菊匿，出現(xiàn)碰撞了可以后面再加隨機(jī)字符付呕。
隨機(jī)字符可以緩解碰撞問題计福，但是無法根治。另外徽职，增加幾位字符呢才可靠呢象颖？這種概率事件無法通過測試來回答，通過運(yùn)維監(jiān)控不斷的調(diào)整也是一件頭疼和折磨人的事姆钉。預(yù)先在redis/db里異步生成一批短碼说订，每次從列表里面取不就好了。
具體是在redis還是db里批量生成其實(shí)是截然不同的兩種實(shí)現(xiàn)育韩。 若是redis, 那么里面要放入全量的短碼么克蚂？否則怎么知道這個(gè)短碼到底是不是唯一的？如果全量筋讨，那對(duì)redis的可用性就要嚴(yán)格保證，否則它掛了摸恍，就必須全量的預(yù)熱悉罕，這個(gè)過程要做好不是那么的容易； 若是db, 那么就要有大量的并發(fā)鎖定立镶，意味著大量讀寫壁袄，這個(gè)對(duì)數(shù)據(jù)庫也是個(gè)考驗(yàn)。短網(wǎng)址的還原跳轉(zhuǎn)用301還是302呢媚媒？
301是永久重定向嗜逻，302是臨時(shí)重定向。短地址一經(jīng)生成就不會(huì)變化缭召，所以用301是符合http語義的栈顷。同時(shí)瀏覽器會(huì)對(duì)301請(qǐng)求保存一個(gè)比較長期的緩存，這樣就減輕對(duì)服務(wù)器的壓力嵌巷；而且301對(duì)于網(wǎng)址的SEO有一定的提升萄凤。但是很多情況下我們需要對(duì)接口點(diǎn)擊或者用戶行為進(jìn)行一些業(yè)務(wù)監(jiān)控處理的時(shí)候，301明顯就不合適了（瀏覽器直接按照緩存數(shù)據(jù)跳轉(zhuǎn)了）, 所以很多業(yè)務(wù)場景下還是采用302比較合適搪哪。
請(qǐng)結(jié)合上述問題后的描述思考5分鐘靡努，然后我們開始正文
首先聲明本文設(shè)計(jì)思路也只是取自己業(yè)務(wù)場景可以容忍的情況，而有所取舍.
沒有完美的系統(tǒng)只有適用的系統(tǒng)晓折。
縮短網(wǎng)址的算法
# 初期選型算法
對(duì)于算法本人也算是踩了不少的坑惑朦，最開始采用的是網(wǎng)上流傳甚廣的微博短網(wǎng)址算法(原理類似16進(jìn)制與62進(jìn)制的轉(zhuǎn)換)，加了些許改進(jìn)：
- 將"原始鏈接（長鏈接）+ key(隨機(jī)字符串,防止算法泄漏)"MD5后得到32位的一個(gè)字符串A
- 將上面的A字符串分為4段處理漓概， 每段的長度為8 漾月， 比如四段分別為 M、N垛耳、O栅屏、P
- 將M字符串當(dāng)作一個(gè)16進(jìn)制格式的數(shù)字來處理飘千， 將其轉(zhuǎn)換為一個(gè)Long類型。 比如轉(zhuǎn)換為L
- 此時(shí)L的二進(jìn)制有效長度為32位栈雳， 需要將前面兩位去掉护奈，留下30位 ， 可以 & 0x3fffffff 進(jìn)行位與運(yùn)算得到想要的結(jié)果哥纫。（30位才能轉(zhuǎn)換62進(jìn)制霉旗，否則超出）
- 此時(shí)L的二進(jìn)制有效長度為30位， 分為6段處理蛀骇， 每段的長度為5位
- 依次取出L的每一段（5位）厌秒，進(jìn)行位操作 & 0x0000003D 得到一個(gè) <= 61的數(shù)字，來當(dāng)做index
- 根據(jù)index 去預(yù)定義的62進(jìn)制字符表里面去取一個(gè)字符擅憔， 最后能取出6個(gè)字符鸵闪，然后拼裝這6個(gè)字符成為一個(gè)6位字符串，作為短鏈接碼
- 拿出第②步剩余的三段暑诸，重復(fù)3-7 步
- 這樣總共可以獲得 4 個(gè)6位字符串蚌讼，取里面的任意一個(gè)就可作為這個(gè)長鏈接的短網(wǎng)址
- 串碼添加校驗(yàn)位checksum，用于簡單校驗(yàn)个榕。所以總共7位碼
算法其實(shí)并不太復(fù)雜篡石，大家自行解讀。這個(gè)算法在服務(wù)量不大的情況下hash碰撞的概率尚可以接受西采，一定量的壓測效果也還算理想凰萨。因?yàn)橛?個(gè)hash可選項(xiàng)，即使碰撞到了還有其他3次機(jī)會(huì)去避免械馆。但是如果作為基礎(chǔ)服務(wù)胖眷，在使用方調(diào)用量級(jí)無法估量無法保證短鏈接絕對(duì)可用的情況下，這個(gè)算法還是有很大的隱患狱杰！
# 改進(jìn)算法
只要有hash就有碰撞的可能瘦材，要一勞永逸就得拋棄hash算法。這里我們就用全局自增長的10進(jìn)制序號(hào) -> 62進(jìn)制實(shí)現(xiàn)仿畸。這里繼續(xù)拋出問題來了：
1. 字符超長問題
即使到了10億(Billion)轉(zhuǎn)換而成的62進(jìn)制也無非是6位字符食棕，所以長度基本不在考慮范圍內(nèi)，這個(gè)范圍足夠使用了错沽。
2. 短碼安全問題
按照算法從0-61都是1位字符簿晓，然后2位、3位...這樣的話很容易被人發(fā)現(xiàn)規(guī)律并進(jìn)行攻擊千埃，當(dāng)然防御手段很多憔儿，請(qǐng)求簽名之類的安全驗(yàn)證手段不在本文討論范圍內(nèi)。
首先計(jì)數(shù)器可以從一個(gè)比較大的隨機(jī)中間值開始放可，比如從10000開始計(jì)數(shù)谒臼，他的62進(jìn)制是 2Bi 3位的字符串朝刊；
然后采用一些校驗(yàn)位算法(比如Luhn改進(jìn)一下)，計(jì)算出1位校驗(yàn)位拼接起來蜈缤，4位短碼拾氓，這樣可以排除一定的安全風(fēng)險(xiǎn)；
再加點(diǎn)安全料的話底哥，可以在62進(jìn)制的轉(zhuǎn)換過程中把排序好的62個(gè)字母數(shù)字隨機(jī)打亂咙鞍，比如ABCD1234打亂成1BC43A2D, 轉(zhuǎn)換的62進(jìn)制也就更難hack了；
最后如果仍不放心趾徽，還可以在某些位置（比如1续滋，3，5）插入隨機(jī)數(shù)孵奶，讓人無法看出規(guī)律來也可以達(dá)到良好的效果疲酌。
3. 同一長網(wǎng)址短碼是否應(yīng)該相同問題
這個(gè)問題按照碼農(nóng)的完美主義原則，基本上回答是Yes拒课。做到也不麻煩徐勃，比如對(duì)長網(wǎng)址進(jìn)行sha1生成的hash值存入hashtable或者redis，在縮短之前進(jìn)行hash值比對(duì)早像，如果相同就查詢出之前生成的短碼即可。
但是緩存內(nèi)預(yù)熱多少sha1值讓其比對(duì)肖爵，多少會(huì)穿透到數(shù)據(jù)庫進(jìn)行比對(duì)卢鹦，就是你自己需要對(duì)熱點(diǎn)數(shù)據(jù)如何預(yù)熱和緩存命中的問題了，這里不展開劝堪。
4. 自增算法是否完美無缺
相比上面的hash分段算法冀自，自增算法能已經(jīng)基本可以保證碼唯一、同址同碼的目標(biāo)了秒啦。但是它也有缺陷熬粗，那就是隨著序號(hào)的自增，碼越來越長余境，到了很大的數(shù)值后沒有辦法循環(huán)往復(fù)驻呐，讓碼重新變短！而hash分段就沒有這個(gè)問題芳来。
所以這兩個(gè)算法其實(shí)各有優(yōu)劣含末，如果業(yè)務(wù)所需的短網(wǎng)址有效期相對(duì)較短，通過批處理定期清洗掉即舌，那第一種算法不失為一種可選方案佣盒；
而自增算法對(duì)于無差別的業(yè)務(wù)短網(wǎng)址，可以保證任何的請(qǐng)求量都不會(huì)出現(xiàn)沖突顽聂，權(quán)衡下來不失為最佳之選肥惭。碼無非分為永久碼或臨時(shí)碼盯仪，結(jié)合業(yè)務(wù)的話其實(shí)大部分的碼都是臨時(shí)碼，只是或長或短而已蜜葱，所以甚至可以設(shè)計(jì)永久的碼序號(hào)區(qū)間是0-10000全景，0-5天的碼10001-20000，5-30天的碼20001-30000笼沥，30天+的碼30001-無窮蚪燕。這樣就可以實(shí)現(xiàn)序號(hào)的重復(fù)使用了。當(dāng)然如果你對(duì)自己設(shè)定的區(qū)間沒有自信的話（溢出）奔浅，請(qǐng)千萬不要這么做馆纳。
Redis/DB 如何設(shè)計(jì)
# DB設(shè)計(jì)
只需要一張表，存放短碼與原網(wǎng)址的映射關(guān)系汹桦，其他一些屬性比如原網(wǎng)址的sha1碼鲁驶，過期時(shí)間等保存好即可。當(dāng)然短碼和sha1字段都要加上唯一索引舞骆，保證唯一性的同時(shí)提高查詢效率钥弯。
# Redis設(shè)計(jì)
若想短鏈接服務(wù)達(dá)到低延遲高并發(fā)的目標(biāo)，Redis在很多環(huán)節(jié)都可以起到關(guān)鍵作用督禽。
1. 自增長序列
通過Redis的 incr 方法可以很容易的實(shí)現(xiàn)全局自增長序列脆霎，但前提是Redis的高可用，如果Redis掛了序列從哪里開始呢狈惫？當(dāng)然是從DB中拿咯睛蛛，怎么拿？
方式一：DB表中新增一個(gè)字段胧谈，存入最新的短碼基于的序號(hào)值忆肾，然后Redis在此基礎(chǔ)上+1即可。這部分代碼務(wù)必做好同步菱肖； 方式二：直接從DB中獲取最新的短碼客冈，然后逆向計(jì)算出序號(hào)值，+1后繼續(xù)稳强；
2. 長網(wǎng)址的Hash表
在Redis中存入熱點(diǎn)網(wǎng)址的hash映射數(shù)據(jù)场仲，注意，這里說的是熱點(diǎn)網(wǎng)址而且不是全量網(wǎng)址键袱，實(shí)現(xiàn)者需要有所取舍燎窘。或者沒有命中的就產(chǎn)生新的短碼（會(huì)導(dǎo)致同址不同碼）蹄咖，或者沒有命中就到數(shù)據(jù)庫查詢褐健，保證強(qiáng)一致的同址同碼。
3. 短碼與長網(wǎng)址的映射表
同樣，在Redis中存入熱點(diǎn)網(wǎng)址的映射蚜迅，在短網(wǎng)址還原的請(qǐng)求處理中可以快速的查詢到原網(wǎng)址舵匾。所以這個(gè)點(diǎn)的緩存是必須的。
其他一些說明
- 原網(wǎng)址的Hash方法文中是sha1是選擇之一谁不，類似Murmur64等更快更優(yōu)的hash算法坐梯，可以自行采納
- 類似的服務(wù)已經(jīng)有比較成熟的開源解決方案，比如YOURLS刹帕，不想重復(fù)造輪子的同學(xué)可以直接拿來用
- 如果要對(duì)短鏈接做一些監(jiān)控吵血，比如訪問量，可以通過Redis自行實(shí)現(xiàn)偷溺。目前公司應(yīng)用集成了點(diǎn)評(píng)開源CAT蹋辅，所以訪問量監(jiān)控都不是問題
文終。
任何疏漏或者意見挫掏，歡迎討論侦另。
