以下文章來源于公眾號碼海 灾测，作者碼海

前言

今天够话，我們來談?wù)勅绾卧O(shè)計一個高性能短鏈系統(tǒng)尿褪，短鏈系統(tǒng)設(shè)計看起來很簡單肄程，但每個點都能展開很多知識點锣吼，也是在面試中非常適合考察侯選人的一道設(shè)計題选浑，本文將會結(jié)合我們生產(chǎn)上穩(wěn)定運行兩年之久的高性能短鏈系統(tǒng)給大家簡單介紹下設(shè)計這套系統(tǒng)所涉及的一些思路，希望對大家能有一些幫助玄叠。

本文將會從以下幾個方面來講解古徒，每個點包含的信息量都不少，相信大家看完肯定有收獲

• 短鏈有啥好處读恃，用長鏈不香嗎
• 短鏈跳轉(zhuǎn)的基本原理
• 短鏈生成的幾種方法
• 高性能短鏈的架構(gòu)設(shè)計

注：里面涉及到不少布隆過濾器隧膘，snowflake 等技術(shù)，由于不是本文重點狐粱，所以建議大家看完后再自己去深入了解舀寓，不然展開講篇幅會很長

短鏈有啥好處，用長鏈不香嗎

來看下以下極客時間發(fā)我的營銷短信肌蜻，點擊下方藍色的鏈接（短鏈）

image

瀏覽器的地址欄上最終會顯示一條如下的長鏈互墓。

image

那么為啥要用短鏈表示，直接用長鏈不行嗎蒋搜，用短鏈的話有如下好外

1篡撵、鏈接變短，在對內(nèi)容長度有限制的平臺發(fā)文豆挽，可編輯的文字就變多了

最典型的就是微博育谬，限定了只能發(fā) 140 個字，如果一串長鏈直接懟上去帮哈，其他可編輯的內(nèi)容就所剩無幾了膛檀，用短鏈的話，鏈接長度大大減少娘侍，自然可編輯的文字多了不少咖刃。

再比如一般短信發(fā)文有長度限度，如果用長鏈憾筏，一條短信很可能要拆分成兩三條發(fā)嚎杨，本來一條一毛的短信費變成了兩三毛，何苦呢氧腰。另外用短鏈在內(nèi)容排版上也更美觀枫浙。

2、我們經(jīng)常需要將鏈接轉(zhuǎn)成二維碼的形式分享給他人古拴，如果是長鏈的話二維碼密集難識別箩帚，短鏈就不存在這個問題了,如圖示

image

3、鏈接太長在有些平臺上無法自動識別為超鏈接

如圖示斤富，在釘釘上膏潮，就無法識別如下長鏈接，只能識別部分满力，用短地址無此問題

image

短鏈跳轉(zhuǎn)的基本原理

從上文可知焕参，短鏈好處多多轻纪，那么它是如何工作的呢。我們在瀏覽器抓下包看看

image

可以看到請求后叠纷，返回了狀態(tài)碼 302（重定向）與 location 值為長鏈的響應(yīng)刻帚，然后瀏覽器會再請求這個長鏈以得到最終的響應(yīng),整個交互流程圖如下

image

主要步驟就是訪問短網(wǎng)址后重定向訪問 B，那么問題來了涩嚣，301 和 302 都是重定向崇众，到底該用哪個，這里需要注意一下 301 和 302 的區(qū)別

• 301航厚，代表 永久重定向顷歌，也就是說第一次請求拿到長鏈接后，下次瀏覽器再去請求短鏈的話幔睬，不會向短網(wǎng)址服務(wù)器請求了眯漩，而是直接從瀏覽器的緩存里拿，這樣在 server 層面就無法獲取到短網(wǎng)址的點擊數(shù)了麻顶，如果這個鏈接剛好是某個活動的鏈接赦抖，也就無法分析此活動的效果。所以我們一般不采用 301辅肾。
• 302队萤，代表 臨時重定向，也就是說每次去請求短鏈都會去請求短網(wǎng)址服務(wù)器（除非響應(yīng)中用 Cache-Control 或 Expired 暗示瀏覽器緩存）,這樣就便于 server 統(tǒng)計點擊數(shù)矫钓，所以雖然用 302 會給 server 增加一點壓力要尔，但在數(shù)據(jù)異常重要的今天，這點代碼是值得的新娜，所以推薦使用 302盈电！

短鏈生成的幾種方法

1、哈希算法

怎樣才能生成短鏈杯活，仔細觀察上例中的短鏈，顯然它是由固定短鏈域名 + 長鏈映射成的一串字母組成熬词，那么長鏈怎么才能映射成一串字母呢旁钧，哈希函數(shù)不就用來干這事的嗎，于是我們有了以下設(shè)計思路

image

那么這個哈希函數(shù)該怎么取呢互拾，相信肯定有很多人說用 MD5歪今，SHA 等算法，其實這樣做有點殺雞用牛刀了颜矿，而且既然是加密就意味著性能上會有損失寄猩，我們其實不關(guān)心反向解密的難度，反而更關(guān)心的是哈希的運算速度和沖突概率骑疆。

能夠滿足這樣的哈希算法有很多田篇，這里推薦 Google 出品的 MurmurHash 算法替废，MurmurHash 是一種非加密型哈希函數(shù)，適用于一般的哈希檢索操作泊柬。與其它流行的哈希函數(shù)相比椎镣，對于規(guī)律性較強的 key，MurmurHash 的隨機分布特征表現(xiàn)更良好兽赁。非加密意味著著相比 MD5状答，SHA 這些函數(shù)它的性能肯定更高（實際上性能是 MD5 等加密算法的十倍以上），也正是由于它的這些優(yōu)點刀崖，所以雖然它出現(xiàn)于 2008惊科，但目前已經(jīng)廣泛應(yīng)用到 Redis、MemCache亮钦、Cassandra馆截、HBase、Lucene 等眾多著名的軟件中或悲。

畫外音：這里有個小插曲孙咪，MurmurHash 成名后，作者拿到了 Google 的 offer巡语，所以多做些開源的項目翎蹈，說不定成名后你也能不經(jīng)意間收到 Google 的 offer ^_。

MurmurHash 提供了兩種長度的哈希值男公，32 bit荤堪，128 bit，為了讓網(wǎng)址盡可通地短枢赔，我們選擇 32 bit 的哈希值澄阳，32 bit 能表示的最大值近 43 億，對于中小型公司的業(yè)務(wù)而言綽綽有余踏拜。對上文提到的極客長鏈做 MurmurHash 計算碎赢，得到的哈希值為 3002604296，于是我們現(xiàn)在得到的短鏈為 固定短鏈域名+哈希值 = http://gk.link/a/3002604296

如何縮短域名速梗？

有人說人這個域名還是有點長肮塞，還有一招，3002604296 得到的這個哈希值是十進制的姻锁，那我們把它轉(zhuǎn)為 62 進制可縮短它的長度枕赵，10 進制轉(zhuǎn) 62 進制如下：

image

于是我們有 (3002604296)₁₀ = (3hcCxy)₁₀，一下從 10 位縮短到了 6 位位隶！于是現(xiàn)在得到了我們的短鏈為 http://gk.link/a/3hcCxy

畫外音：6 位 62 進制數(shù)可表示 568 億的數(shù)拷窜，應(yīng)付長鏈轉(zhuǎn)換綽綽有余

如何解決哈希沖突的問題？

既然是哈希函數(shù)，不可避免地會產(chǎn)生哈希沖突（盡管概率很低）篮昧，該怎么解決呢赋荆。

我們知道既然訪問訪問短鏈能跳轉(zhuǎn)到長鏈，那么兩者之前這種映射關(guān)系一定是要保存起來的恋谭，可以用 Redis 或 Mysql 等糠睡，這里我們選擇用 Mysql 來存儲。表結(jié)構(gòu)應(yīng)該如下所示

CREATE TABLE `short_url_map` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `lurl` varchar(160) DEFAULT NULL COMMENT '長地址',
  `surl` varchar(10) DEFAULT NULL COMMENT '短地址',
  `gmt_create` int(11) DEFAULT NULL COMMENT '創(chuàng)建時間',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

于是我們有了以下設(shè)計思路疚颊。

1. 將長鏈（lurl）經(jīng)過 MurmurHash 后得到短鏈狈孔。
2. 再根據(jù)短鏈去 short_url_map 表中查找看是否存在相關(guān)記錄，如果不存在材义，將長鏈與短鏈對應(yīng)關(guān)系插入數(shù)據(jù)庫中均抽，存儲。
3. 如果存在其掂，說明已經(jīng)有相關(guān)記錄了油挥，此時在長串上拼接一個自定義好的字段，比如「DUPLICATE」款熬，然后再對接接的字段串「lurl + DUPLICATE」做第一步操作深寥，如果最后還是重復(fù)呢，再拼一個字段串啊贤牛，只要到時根據(jù)短鏈取出長鏈的時候把這些自定義好的字符串移除即是原來的長鏈惋鹅。

以上步驟顯然是要優(yōu)化的，插入一條記錄居然要經(jīng)過兩次 sql 查詢（根據(jù)短鏈查記錄殉簸，將長短鏈對應(yīng)關(guān)系插入數(shù)據(jù)庫中）闰集，如果在高并發(fā)下，顯然會成為瓶頸般卑。

畫外音：一般數(shù)據(jù)庫和應(yīng)用服務(wù)（只做計算不做存儲）會部署在兩臺不同的 server 上武鲁，執(zhí)行兩條 sql 就需要兩次網(wǎng)絡(luò)通信，這兩次網(wǎng)絡(luò)通信與兩次 sql 執(zhí)行是整個短鏈系統(tǒng)的性能瓶頸所在蝠检！

所以該怎么優(yōu)化呢

1. 首先我們需要給短鏈字段 surl 加上唯一索引
2. 當(dāng)長鏈經(jīng)過 MurmurHash 得到短鏈后沐鼠，直接將長短鏈對應(yīng)關(guān)系插入 db 中，如果 db 里不含有此短鏈的記錄叹谁，則插入迟杂，如果包含了，說明違反了唯一性索引本慕，此時只要給長鏈再加上我們上文說的自定義字段「DUPLICATE」,重新 hash 再插入即可，看起來在違反唯一性索引的情況下是多執(zhí)行了步驟侧漓，但我們要知道 MurmurHash 發(fā)生沖突的概率是非常低的锅尘，基本上不太可能發(fā)生，所以這種方案是可以接受的。

當(dāng)然如果在數(shù)據(jù)量很大的情況下藤违，沖突的概率會增大浪腐，此時我們可以加布隆過濾器來進行優(yōu)化。

用所有生成的短網(wǎng)址構(gòu)建布隆過濾器顿乒，當(dāng)一個新的長鏈生成短鏈后议街，先將此短鏈在布隆過濾器中進行查找，如果不存在璧榄，說明 db 里不存在此短網(wǎng)址特漩，可以插入！

畫外音：布隆過濾器是一種非常省內(nèi)存的數(shù)據(jù)結(jié)構(gòu)骨杂，長度為 10 億的布隆過濾器涂身，只需要 125 M 的內(nèi)存空間。

綜上搓蚪，如果用哈希函數(shù)來設(shè)計蛤售，總體的設(shè)計思路如下

image

用哈希算法生成的短鏈其實已經(jīng)能滿足我們的業(yè)務(wù)需求，接下來我們再來看看如何用自增序列的方式來生成短鏈

2妒潭、自增序列算法

我們可以維護一個 ID 自增生成器悴能，比如 1，2雳灾，3 這樣的整數(shù)遞增 ID漠酿，當(dāng)收到一個長鏈轉(zhuǎn)短鏈的請求時，ID 生成器為其分配一個 ID佑女，再將其轉(zhuǎn)化為 62 進制记靡，拼接到短鏈域名后面就得到了最終的短網(wǎng)址，那么這樣的 ID 自增生成器該如何設(shè)計呢团驱。如果在低峰期發(fā)號還好摸吠，高并發(fā)下，ID 自增生成器的的 ID 生成可能會系統(tǒng)瓶頸嚎花，所以它的設(shè)計就顯得尤為重要寸痢。

主要有以下四種獲取 id 的方法

1、類 uuid

簡單地說就是用 UUID uuid = UUID.randomUUID(); 這種方式生成的 UUID紊选，UUID(Universally Unique Identifier)全局唯一標識符,是指在一臺機器上生成的數(shù)字啼止，它保證對在同一時空中的所有機器都是唯一的，但這種方式生成的 id 比較長兵罢，且無序献烦，在插入 db 時可能會頻繁導(dǎo)致頁分裂，影響插入性能卖词。

2巩那、Redis

用 Redis 是個不錯的選擇，性能好，單機可支撐 10 w+ 請求即横，足以應(yīng)付大部分的業(yè)務(wù)場景噪生，但有人說如果一臺機器扛不住呢，可以設(shè)置多臺嘛东囚，比如我布置 10 臺機器跺嗽，每臺機器分別只生成尾號0，1页藻，2桨嫁，... 9 的 ID, 每次加 10 即可，只要設(shè)置一個 ID 生成器代理隨機分配給發(fā)號器生成 ID 就行了惕橙。

image

不過用 Redis 這種方案瞧甩，需要考慮持久化（短鏈 ID 總不能一樣吧），災(zāi)備弥鹦，成本有點高肚逸。

3、Snowflake

用 Snowflake 也是個不錯的選擇彬坏，不過 Snowflake 依賴于系統(tǒng)時鐘的一致性朦促。如果某臺機器的系統(tǒng)時鐘回撥，有可能造成 ID 沖突栓始，或者 ID 亂序务冕。

4、Mysql 自增主鍵

這種方式使用簡單幻赚，擴展方便禀忆，所以我們使用 Mysql 的自增主鍵來作為短鏈的 id。簡單總結(jié)如下：

image

那么問題來了落恼，如果用 Mysql 自增 id 作為短鏈 ID箩退，在高并發(fā)下，db 的寫壓力會很大佳谦，這種情況該怎么辦呢戴涝。

考慮一下，一定要在用到的時候去生成 id 嗎钻蔑，是否可以提前生成這些自增 id ?

方案如下：

設(shè)計一個專門的發(fā)號表啥刻，每插入一條記錄，為短鏈 id 預(yù)留 （主鍵 id * 1000 - 999） 到 (主鍵 id * 1000) 的號段咪笑，如下

發(fā)號表：url_sender_num

image

如圖示：tmp_start_num 代表短鏈的起始 id可帽，tmp_end_num 代表短鏈的終止 id。

當(dāng)長鏈轉(zhuǎn)短鏈的請求打到某臺機器時窗怒，先看這臺機器是否分配了短鏈號段映跟，未分配就往發(fā)號表插入一條記錄钝满，則這臺機器將為短鏈分配范圍在 tmp_start_num 到 tmp_end_num 之間的 id。從 tmp_start_num 開始分配申窘，一直分配到 tmp_end_num，如果發(fā)號 id 達到了 tmp_end_num孔轴，說明這個區(qū)間段的 id 已經(jīng)分配完了剃法，則再往發(fā)號表插入一條記錄就又獲取了一個發(fā)號 id 區(qū)間。

畫外音：思考一下這個自增短鏈 id 在機器上該怎么實現(xiàn)呢路鹰， 可以用 redis, 不過更簡單的方案是用 AtomicLong贷洲，單機上性能不錯，也保證了并發(fā)的安全性晋柱，當(dāng)然如果并發(fā)量很大优构，AtomicLong 的表現(xiàn)就不太行了，可以考慮用 LongAdder雁竞，在高并發(fā)下表現(xiàn)更加優(yōu)秀钦椭。

整體設(shè)計圖如下

image

解決了發(fā)號器問題，接下來就簡單了碑诉，從發(fā)號器拿過來的 id 彪腔，即為短鏈 id，接下來我們再創(chuàng)建一個長短鏈的映射表即可进栽， 短鏈 id 即為主鍵德挣，不過這里有個需要注意的地方，我們可能需要防止多次相同的長鏈生成不同的短鏈 id 這種情況快毛，這就需要每次先根據(jù)長鏈來查找 db 看是否存在相關(guān)記錄格嗅，一般的做法是給長鏈加索引，但這樣的話索引的空間會很大唠帝，所以我們可以對長鏈適當(dāng)?shù)膲嚎s屯掖，比如 md5，再對長鏈的 md5 字段做索引没隘，索引就會小很多懂扼。這樣只要根據(jù)長鏈的 md5 去表里查是否存在相同的記錄即可。所以我們設(shè)計的表如下

CREATE  TABLE  `short_url_map` (
  `id` int(11) unsigned  NOT  NULL AUTO_INCREMENT COMMENT '短鏈 id',
  `lurl` varchar(10) DEFAULT  NULL  COMMENT '長鏈',
  `md5` char(32) DEFAULT  NULL  COMMENT '長鏈md5',
  `gmt_create` int(11) DEFAULT  NULL  COMMENT '創(chuàng)建時間',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB  DEFAULT  CHARSET=utf8;

當(dāng)然了右蒲，數(shù)據(jù)量如果很大的話阀湿，后期就需要分區(qū)或分庫分表了。

高性能短鏈的架構(gòu)設(shè)計

在電商公司瑰妄，經(jīng)常有很多活動陷嘴，秒殺，搶紅包等等间坐，在某個時間點的 QPS 會很高灾挨，考慮到這種情況邑退，我們引入了 openResty，它是一個基于 Nginx 與 Lua 的高性能 Web 平臺劳澄，由于 Nginx 的非阻塞 IO 模型地技，使用 openResty 可以輕松支持 100 w + 的并發(fā)數(shù)，一般情況下你只要部署一臺即可秒拔，不過為了避免單點故障莫矗，兩臺為宜，同時 openResty 也自帶了緩存機制砂缩，集成了 redis 這些緩存模塊作谚，也可以直接連 mysql。不需要再通過業(yè)務(wù)層連這些中間件庵芭，性能自然會高不少

image

如圖示妹懒，使用 openResty 省去了業(yè)務(wù)層這一步，直達緩存層與數(shù)據(jù)庫層双吆，也提升了不少性能眨唬。

總結(jié)

本文對短鏈設(shè)計方案作了詳細地剖析，旨在給大家提供幾種不同的短鏈設(shè)計思路伊诵，文中涉及到挺多像布隆過濾器单绑，openResty 等技術(shù)，文中沒有展開講曹宴，建議大家回頭可以再詳細了解一下搂橙。再比如文中提到的 Mysql 頁分裂也需要對底層使用的 B+ tree 數(shù)據(jù)結(jié)構(gòu)，操作系統(tǒng)按頁獲取等知識有比較詳細地了解笛坦，相信大家各個知識點都吃透后會收獲不小区转。

巨人的肩膀

https://www.cnblogs.com/rjzheng/p/11827426.html

https://time.geekbang.org/column/article/80850