高性能短鏈設計

前言

今天，我們來談談如何設計一個高性能短鏈系統，短鏈系統設計看起來很簡單，但每個點都能展開很多知識點，也是在面試中非常適合考察侯選人的一道設計題，本文將會結合我們生產上穩定運行兩年之久的高性能短鏈系統給大家簡單介紹下設計這套系統所涉及的一些思路，希望對大家能有一些幫助。

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

注：裏面涉及到不少布隆過濾器，snowflake 等技術，由於不是本文重點，所以建議大家看完後再自己去深入瞭解，不然展開講篇幅會很長

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

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

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

那麼爲啥要用短鏈表示，直接用長鏈不行嗎，用短鏈的話有如下好外

1、鏈接變短，在對內容長度有限制的平臺發文，可編輯的文字就變多了

最典型的就是微博，限定了只能發 140 個字，如果一串長鏈直接懟上去，其他可編輯的內容就所剩無幾了，用短鏈的話，鏈接長度大大減少，自然可編輯的文字多了不少。

再比如一般短信發文有長度限度，如果用長鏈，一條短信很可能要拆分成兩三條發，本來一條一毛的短信費變成了兩三毛，何苦呢。另外用短鏈在內容排版上也更美觀。

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

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

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

短鏈跳轉的基本原理

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

可以看到請求後，返回了狀態碼 302（重定向）與 location 值爲長鏈的響應，然後瀏覽器會再請求這個長鏈以得到最終的響應, 整個交互流程圖如下

主要步驟就是訪問短網址後重定向訪問 B，那麼問題來了，301 和 302 都是重定向，到底該用哪個，這裏需要注意一下 301 和 302 的區別

短鏈生成的幾種方法

1、哈希算法

怎樣才能生成短鏈，仔細觀察上例中的短鏈，顯然它是由固定短鏈域名 + 長鏈映射成的一串字母組成，那麼長鏈怎麼才能映射成一串字母呢，哈希函數不就用來幹這事的嗎，於是我們有了以下設計思路

那麼這個哈希函數該怎麼取呢，相信肯定有很多人說用 MD5，SHA 等算法，其實這樣做有點殺雞用牛刀了，而且既然是加密就意味着性能上會有損失，我們其實不關心反向解密的難度，反而更關心的是哈希的運算速度和衝突概率。

能夠滿足這樣的哈希算法有很多，這裏推薦 Google 出品的 MurmurHash 算法，MurmurHash 是一種非加密型哈希函數，適用於一般的哈希檢索操作。與其它流行的哈希函數相比，對於規律性較強的 key，MurmurHash 的隨機分佈特徵表現更良好。非加密意味着着相比 MD5，SHA 這些函數它的性能肯定更高（實際上性能是 MD5 等加密算法的十倍以上），也正是由於它的這些優點，所以雖然它出現於 2008，但目前已經廣泛應用到 Redis、MemCache、Cassandra、HBase、Lucene 等衆多著名的軟件中。

畫外音：這裏有個小插曲，MurmurHash 成名後，作者拿到了 Google 的 offer，所以多做些開源的項目，說不定成名後你也能不經意間收到 Google 的 offer ^^。_

MurmurHash 提供了兩種長度的哈希值，32 bit，128 bit，爲了讓網址儘可通地短，我們選擇 32 bit 的哈希值，32 bit 能表示的最大值近 43 億，對於中小型公司的業務而言綽綽有餘。對上文提到的極客長鏈做 MurmurHash 計算，得到的哈希值爲 3002604296，於是我們現在得到的短鏈爲 固定短鏈域名 + 哈希值 = http://gk.link/a/3002604296

如何縮短域名？

有人說人這個域名還是有點長，還有一招，3002604296 得到的這個哈希值是十進制的，那我們把它轉爲 62 進制可縮短它的長度，10 進制轉 62 進制如下：

於是我們有 (3002604296)10 = (3hcCxy)10，一下從 10 位縮短到了 6 位！於是現在得到了我們的短鏈爲 http://gk.link/a/3hcCxy

畫外音：6 位 62 進制數可表示 568 億的數，應付長鏈轉換綽綽有餘

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

既然是哈希函數，不可避免地會產生哈希衝突（儘管概率很低），該怎麼解決呢。

我們知道既然訪問訪問短鏈能跳轉到長鏈，那麼兩者之前這種映射關係一定是要保存起來的，可以用 Redis 或 Mysql 等，這裏我們選擇用 Mysql 來存儲。表結構應該如下所示

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 '創建時間',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

於是我們有了以下設計思路。

  1. 將長鏈（lurl）經過 MurmurHash 後得到短鏈。

  2. 再根據短鏈去 short_url_map 表中查找看是否存在相關記錄，如果不存在，將長鏈與短鏈對應關係插入數據庫中，存儲。

  3. 如果存在，說明已經有相關記錄了，此時在長串上拼接一個自定義好的字段，比如「DUPLICATE」，然後再對接接的字段串「lurl + DUPLICATE」做第一步操作，如果最後還是重複呢，再拼一個字段串啊，只要到時根據短鏈取出長鏈的時候把這些自定義好的字符串移除即是原來的長鏈。

以上步驟顯然是要優化的，插入一條記錄居然要經過兩次 sql 查詢（根據短鏈查記錄，將長短鏈對應關係插入數據庫中），如果在高併發下，顯然會成爲瓶頸。

畫外音：一般數據庫和應用服務（只做計算不做存儲）會部署在兩臺不同的 server 上，執行兩條 sql 就需要兩次網絡通信，這兩次網絡通信與兩次 sql 執行是整個短鏈系統的性能瓶頸所在！

所以該怎麼優化呢

  1. 首先我們需要給短鏈字段 surl 加上唯一索引

  2. 當長鏈經過 MurmurHash 得到短鏈後，直接將長短鏈對應關係插入 db 中，如果 db 裏不含有此短鏈的記錄，則插入，如果包含了，說明違反了唯一性索引，此時只要給長鏈再加上我們上文說的自定義字段「DUPLICATE」, 重新 hash 再插入即可，看起來在違反唯一性索引的情況下是多執行了步驟，但我們要知道 MurmurHash 發生衝突的概率是非常低的，基本上不太可能發生，所以這種方案是可以接受的。

當然如果在數據量很大的情況下，衝突的概率會增大，此時我們可以加布隆過濾器來進行優化。

用所有生成的短網址構建布隆過濾器，當一個新的長鏈生成短鏈後，先將此短鏈在布隆過濾器中進行查找，如果不存在，說明 db 裏不存在此短網址，可以插入！

2、自增序列算法

1、類 uuid

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

2、Redis

用 Redis 是個不錯的選擇，性能好，單機可支撐 10 w+ 請求，足以應付大部分的業務場景，但有人說如果一臺機器扛不住呢，可以設置多臺嘛，比如我佈置 10 臺機器，每臺機器分別只生成尾號 0，1，2，... 9 的 ID, 每次加 10 即可，只要設置一個 ID 生成器代理隨機分配給發號器生成  ID 就行了。

不過用 Redis 這種方案，需要考慮持久化（短鏈 ID 總不能一樣吧），災備，成本有點高。

3、Snowflake

用 Snowflake 也是個不錯的選擇，不過 Snowflake 依賴於系統時鐘的一致性。如果某臺機器的系統時鐘回撥，有可能造成 ID 衝突，或者 ID 亂序。

4、Mysql 自增主鍵

這種方式使用簡單，擴展方便，所以我們使用 Mysql 的自增主鍵來作爲短鏈的 id。簡單總結如下：

那麼問題來了，如果用 Mysql 自增 id 作爲短鏈 ID，在高併發下，db 的寫壓力會很大，這種情況該怎麼辦呢。

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

方案如下：

設計一個專門的發號表，每插入一條記錄，爲短鏈 id 預留  （主鍵 id * 1000 - 999） 到  (主鍵 id  * 1000) 的號段，如下

發號表：url_sender_num

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

當長鏈轉短鏈的請求打到某臺機器時，先看這臺機器是否分配了短鏈號段，未分配就往發號表插入一條記錄，則這臺機器將爲短鏈分配範圍在 tmp_start_num 到 tmp_end_num 之間的 id。從 tmp_start_num 開始分配，一直分配到 tmp_end_num，如果發號 id 達到了 tmp_end_num，說明這個區間段的 id 已經分配完了，則再往發號表插入一條記錄就又獲取了一個發號 id 區間。

畫外音：思考一下這個自增短鏈 id 在機器上該怎麼實現呢， 可以用 redis, 不過更簡單的方案是用 AtomicLong，單機上性能不錯，也保證了併發的安全性，當然如果併發量很大，AtomicLong 的表現就不太行了，可以考慮用 LongAdder，在高併發下表現更加優秀。

整體設計圖如下

解決了發號器問題，接下來就簡單了，從發號器拿過來的 id ，即爲短鏈 id，接下來我們再創建一個長短鏈的映射表即可， 短鏈 id 即爲主鍵，不過這裏有個需要注意的地方，我們可能需要防止多次相同的長鏈生成不同的短鏈 id 這種情況，這就需要每次先根據長鏈來查找 db 看是否存在相關記錄，一般的做法是給長鏈加索引，但這樣的話索引的空間會很大，所以我們可以對長鏈適當的壓縮，比如 md5，再對長鏈的 md5 字段做索引，索引就會小很多。這樣只要根據長鏈的 md5 去表裏查是否存在相同的記錄即可。所以我們設計的表如下

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'創建時間',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

當然了，數據量如果很大的話，後期就需要分區或分庫分表了。

高性能短鏈的架構設計

在電商公司，經常有很多活動，秒殺，搶紅包等等，在某個時間點的 QPS 會很高，考慮到這種情況，我們引入了 openResty，它是一個基於 Nginx 與 Lua 的高性能 Web 平臺，由於 Nginx 的非阻塞 IO 模型，使用 openResty 可以輕鬆支持 100 w + 的併發數，一般情況下你只要部署一臺即可，不過爲了避免單點故障，兩臺爲宜，同時 openResty 也自帶了緩存機制，集成了 redis 這些緩存模塊，也可以直接連 mysql。不需要再通過業務層連這些中間件，性能自然會高不少

如圖示，使用 openResty 省去了業務層這一步，直達緩存層與數據庫層，也提升了不少性能。

總結

本文對短鏈設計方案作了詳細地剖析，旨在給大家提供幾種不同的短鏈設計思路，文中涉及到挺多像布隆過濾器，openResty 等技術，文中沒有展開講，建議大家回頭可以再詳細瞭解一下。再比如文中提到的 Mysql 頁分裂也需要對底層使用的 B+ tree 數據結構，操作系統按頁獲取等知識有比較詳細地瞭解，相信大家各個知識點都喫透後會收穫不小。

巨人的肩膀

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

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

作者：碼海

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/HmcaHUgKb3dy2JCTiILb0w

猜你喜歡