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

  • 2019 年 10 月 7 日
  • 筆記

前言

想必大家也經常收到垃圾簡訊吧… 簡訊中的鏈接一般都是短鏈接, 類似於下圖這樣:

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

短 url 的好處有:

  1. 短. 簡訊和許多平台 (微博) 有字數限制, 太長的鏈接加進去都沒有辦法寫正文了.
  2. 好看. 比起一大堆不知所以的參數, 短鏈接更加簡潔友好.
  3. 方便做一些統計. 你點了鏈接會有人記錄然後分析的.
  4. 安全. 不暴露訪問參數.

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

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

短 URL 基礎原理

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

  1. 有一個服務, 將要發送給你的長 URL 對應到一個短 URL 上. 例如 www.baidu.com->www.t.cn/1
  2. 把短 url 拼接到簡訊等的內容上發送.
  3. 用戶點擊短 URL, 瀏覽器用 301/302 進行重定向, 訪問到對應的長 URL.
  4. 展示對應的內容.

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

服務設計

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

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

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

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

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

對應關係如何存儲?

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

如何保證長短鏈接一一對應?

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

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

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

短 URL 的存儲

我們返回的短 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.

package util;    import redis.clients.jedis.Jedis;    /**   * Created by pfliu on 2019/06/23.   */  public class ShortUrlUtil {        private static final String SHORT_URL_KEY = "SHORT_URL_KEY";      private static final String LOCALHOST = "http://localhost:4444/";      private static final String SHORT_LONG_PREFIX = "short_long_prefix_";      private static final String CACHE_KEY_PREFIX = "cache_key_prefix_";      private static final int CACHE_SECONDS = 1 * 60 * 60;        private final String redisConfig;      private final Jedis jedis;        public ShortUrlUtil(String redisConfig) {          this.redisConfig = redisConfig;          this.jedis = new Jedis(this.redisConfig);      }        public String getShortUrl(String longUrl, Decimal decimal) {          // 查詢快取          String cache = jedis.get(CACHE_KEY_PREFIX + longUrl);          if (cache != null) {              return LOCALHOST + toOtherBaseString(Long.valueOf(cache), decimal.x);          }            // 自增          long num = jedis.incr(SHORT_URL_KEY);          // 在資料庫中保存短-長URL的映射關係,可以保存在MySQL中          jedis.set(SHORT_LONG_PREFIX + num, longUrl);          // 寫入快取          jedis.setex(CACHE_KEY_PREFIX + longUrl, CACHE_SECONDS, String.valueOf(num));          return LOCALHOST + toOtherBaseString(num, decimal.x);      }        /**       * 在進位表示中的字符集合       */      final static char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8',              '9', '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', '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'};        /**       * 由10進位的數字轉換到其他進位       */      private String toOtherBaseString(long n, int base) {          long num = 0;          if (n < 0) {              num = ((long) 2 * 0x7fffffff) + n + 2;          } else {              num = n;          }          char[] buf = new char[32];          int charPos = 32;          while ((num / base) > 0) {              buf[--charPos] = digits[(int) (num % base)];              num /= base;          }          buf[--charPos] = digits[(int) (num % base)];          return new String(buf, charPos, (32 - charPos));      }        enum Decimal {          D32(32),          D64(64);            int x;            Decimal(int x) {              this.x = x;          }      }        public static void main(String[] args) {            for (int i = 0; i < 100; i++) {              System.out.println(new ShortUrlUtil("localhost").getShortUrl("www.baidudu.com", Decimal.D32));              System.out.println(new ShortUrlUtil("localhost").getShortUrl("www.baidu.com", Decimal.D64));          }      }  }

作者：呼延十 https://juejin.im/post/5d10ecab518825795a4d380e

-END-

VirMach 便宜 VPS

QNews

QNews