你知道短URL服務是怎麼設計的嗎？

前言

想必大家也經常收到垃圾短信吧... 短信中的連結一般都是短連結, 類似于下圖這樣:

為什麼這裡面的 url 都是短的呢? 有什麼好處呢? 怎麼做到的呢?

短 url 的好處有:

短. 短信和許多平台 (微網誌) 有字數限制, 太長的連結加進去都沒有辦法寫正文了.

好看. 比起一大堆不知是以的參數, 短連結更加簡潔友好.

友善做一些統計. 你點了連結會有人記錄然後分析的.

安全. 不暴露通路參數.

這就是為什麼我們現在收到的垃圾短信大多數都是短 URL 的原因了.

那麼短 URL 是怎麼做到的呢?

短 URL 基礎原理

短 URL 從生成到使用分為以下幾步.

有一個服務, 将要發送給你的長 URL 對應到一個短 URL 上. 例如 <code>www.baidu.com-&gt;www.t.cn/1</code>

把短 url 拼接到短信等的内容上發送.

使用者點選短 URL, 浏覽器用 301/302 進行重定向, 通路到對應的長 URL.

展示對應的内容.

本文主要集中于第一步, 即如何将一個長 URL 對應到短 URL 上.

服務設計

如果你在往長短 URL 真實的對應關系上想, 那麼就走遠了.

最理想的情況是: 我們用一種算法, 對每一個長 URL, 唯一的轉換成短 URL. 還能保持反向轉換的能力.

但是這是不可能的, 如果有這樣的算法, 世界上的所有壓縮算法都可以原地去世了.

正确的思路是建立一個發号器, 每次有一個新的長 URL 進來, 我們就增加一, 并且将新的數值傳回. 第一個來的 url 傳回 "www.x.cn/0", 第二個傳回 "www.x.cn/1".

接下來以 QA 形式寫幾個小問題:

這個對應資料肯定是要落盤的, 不能每次系統重新開機就重新排号, 是以可以采用 mysql 等資料庫來存儲. 而且如果資料量小且 qps 低, 直接使用資料庫的自增主鍵就可以實作.

按照上面的發号器政策, 是不能保證長短連結的一一對應的, 你連續用同一個 URL 請求兩次, 結果值都是不一樣的.

為了實作長短連結一一對應, 我們需要付出很大的空間代價, 尤其是為了快速響應, 我們可以需要在記憶體中做一層緩存, 這樣子太浪費了.

但是可以實作一些變種的, 來實作部分的一一對應, 比如将最近 / 最熱門的對應關系存儲在 K-V 資料庫中, 這樣子可以節省空間的同時, 加快響應速度.

我們傳回的短 URL 一般是将數字轉換成 32 進制, 這樣子可以更加有效的縮短 URL 長度, 那麼 32 進制的數字對計算機來說隻是字元串, 怎麼存儲呢? 直接存儲字元串對等值查找好找, 對範圍查找等太不友好了.

其實可以直接存儲 10 進制的數字, 這樣不僅占用空間少, 對查找的支援較好, 同時還可以更加友善的轉換到更多 / 更少的進制來進一步縮短 URL.

如果直接存儲在 MySQL 中, 當并發請求增大, 對資料庫的壓力太大, 可能會造成瓶頸, 這時候是可以有一些優化的.

緩存

上面保證長短連結一一對應中也提到過緩存, 這裡我們是為了加快程式處理速度. 可以将熱門的長連結 (需要對長連結進來的次數進行計數), 最近的長連結(可以使用 redis 儲存最近一個小時的) 等等進行一個緩存, 儲存在記憶體中或者類似 redis 的記憶體資料庫中, 如果請求的長 URL 命中了緩存, 那麼直接擷取對應的短 URL 進行傳回, 不需要再進行生成操作.

批量發号

每一次發号都需要通路一次 MySQL 來擷取目前的最大号碼, 并且在擷取之後更新最大号碼, 這個壓力是比較大的.

我們可以每次從資料庫擷取 10000 個号碼, 然後在記憶體中進行發放, 當剩餘的号碼不足 1000 時, 重新向 MySQL 請求下 10000 個号碼. 在上一批号碼發放完了之後, 批量進行寫入.

這樣可以将對資料庫持續的操作移到代碼中進行, 并且異步進行擷取和寫入操作, 保證服務的持續高并發.

上面設計的系統是有單點的, 那就是發号器是個單點, 容易挂掉.

可以采用分布式服務, 分布式的話, 如果每一個發号器進行發号之後都需要同步給其他發号器, 那未必也太麻煩了.

換一種思路, 可以有兩個發号器, 一個發單号, 一個發雙号, 發号之後不再是遞增 1, 而是遞增 2.

類比可得, 我們可以用 1000 個服務, 分别發放 0-999 尾号的數字, 每次發号之後遞增 1000. 這樣做很簡單, 服務互相之間基本都不用通信, 做好自己的事情就好了.

實作

由于我懶得寫 JDBC 代碼, 更懶得弄 Mybatis, 是以代碼中使用到 MySQL 的地方都使用了 Redis.

<code>package util;</code>

<code>import redis.clients.jedis.Jedis;</code>

<code>/**</code>

<code>* Created by pfliu on 2019/06/23.</code>

<code>*/</code>

<code>public class ShortUrlUtil {</code>

<code>private static final String SHORT_URL_KEY = "SHORT_URL_KEY";</code>

<code>private static final String LOCALHOST = "http://localhost:4444/";</code>

<code>private static final String SHORT_LONG_PREFIX = "short_long_prefix_";</code>

<code>private static final String CACHE_KEY_PREFIX = "cache_key_prefix_";</code>

<code>private static final int CACHE_SECONDS = 1 * 60 * 60;</code>

<code>private final String redisConfig;</code>

<code>private final Jedis jedis;</code>

<code>public ShortUrlUtil(String redisConfig) {</code>

<code>this.redisConfig = redisConfig;</code>

<code>this.jedis = new Jedis(this.redisConfig);</code>

<code>}</code>

<code>public String getShortUrl(String longUrl, Decimal decimal) {</code>

<code>// 查詢緩存</code>

<code>String cache = jedis.get(CACHE_KEY_PREFIX + longUrl);</code>

<code>if (cache != null) {</code>

<code>return LOCALHOST + toOtherBaseString(Long.valueOf(cache), decimal.x);</code>

<code>// 自增</code>

<code>long num = jedis.incr(SHORT_URL_KEY);</code>

<code>// 在資料庫中儲存短-長URL的映射關系,可以儲存在MySQL中</code>

<code>jedis.set(SHORT_LONG_PREFIX + num, longUrl);</code>

<code>// 寫入緩存</code>

<code>jedis.setex(CACHE_KEY_PREFIX + longUrl, CACHE_SECONDS, String.valueOf(num));</code>

<code>return LOCALHOST + toOtherBaseString(num, decimal.x);</code>

<code>* 在進制表示中的字元集合</code>

<code>final static char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8',</code>

<code>'9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',</code>

<code>'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',</code>

<code>'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};</code>

<code>* 由10進制的數字轉換到其他進制</code>

<code>private String toOtherBaseString(long n, int base) {</code>

<code>long num = 0;</code>

<code>if (n &lt; 0) {</code>

<code>num = ((long) 2 * 0x7fffffff) + n + 2;</code>

<code>} else {</code>

<code>num = n;</code>

<code>char[] buf = new char[32];</code>

<code>int charPos = 32;</code>

<code>while ((num / base) &gt; 0) {</code>

<code>buf[--charPos] = digits[(int) (num % base)];</code>

<code>num /= base;</code>

<code>return new String(buf, charPos, (32 - charPos));</code>

<code>enum Decimal {</code>

<code>D32(32),</code>

<code>D64(64);</code>

<code>int x;</code>

<code>Decimal(int x) {</code>

<code>this.x = x;</code>

<code>public static void main(String[] args) {</code>

<code>for (int i = 0; i &lt; 100; i++) {</code>

<code>System.out.println(new ShortUrlUtil("localhost").getShortUrl("www.baidudu.com", Decimal.D32));</code>

<code>System.out.println(new ShortUrlUtil("localhost").getShortUrl("www.baidu.com", Decimal.D64));</code>

https://mp.weixin.qq.com/s/9VhSKI2eoRf6UatKInfE9A