短鍊服務的鼻祖是 TinyURL，是最早提供短鍊服務的網站，目前國内也有很多短鍊服務：新浪（t.cn）、百度（dwz.cn）、騰訊（url.cn）等等。
不得不問一句，為什麼要用短鍊？這個問題的另外一層意思是，短鍊服務有必要存在嗎？
套用萬金油答案：存在即合理。
短鍊服務存在的合理性
我們先說說短鍊服務存在的合理性。
短鍊唯一的一個優點是短。
微網誌的早期使用者都知道，每條微網誌隻能限制在 140 個字以内，如果想要分享一個連結，就需要減少描述的文字。
同樣，如果想要在營銷短信中放入一個連結，就需要考慮成本問題。如果是早期的手機，還需要考慮使用者可能接收到三條斷開的短信，嚴重影響短信觸達和點選。
這個情況下，如果連結足夠短，那其他内容就可以更加豐富了。但是我們可能根據不同業務定義不同長度的連結，而且為了滿足其他需求（比如，統計營銷資料），還會在普通連結上增加參數。是以短鍊由此而生，通過重定向跳轉，通過一個很短的連結代替一條其他連結，比如隻需要通過
http://t.cn/A6ULvJho 這種 20 個字元的連結，就可以重定向到長度為 146 個字元的原始連結 https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html?spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989。
上面的兩個例子證明了短鍊有存在的價值，我們總結幾個短鍊的附加用處：
發送營銷短信，更省錢：連結變短，短信長度就變小，所需要支付的短信費用就減少了，比如上面短鍊 20 個字元，原始連結 146 個字元，差出來的都是錢啊。
轉為二維碼，可識别度更高，比如下面兩個二維碼的圖檔，相同尺寸，因為内容數量的不同，單元格的密度也就随之不同
靈活可配置，因為短鍊跳轉原始連結經過了一次重定向，如果在某個時間發現原始連結中有問題，或者需要跳轉到其他地方，可以通過修改重定向的目标位址就可以了。這點對于線下物料投放非常有利，比如已經投放了二維碼物料，這個時候發現期望跳轉到其他網站或者活動，隻需要修改短鍊的目标位址就行，而不需要全部替換已經投放的物料。
短鍊的原理
其實前面已經提到，短鍊是通過伺服器重定向到原始連結實作的。我們來觀察下新浪微網誌的短鍊，控制台執行指令curl -i
，結果如下：HTTP/1.1 302 Found
Date: Thu, 30 Jul 2020 13:59:13 GMT
Content-Type: text/html;charset=UTF-8
Content-Length: 328
Connection: keep-alive
Set-Cookie: aliyungf_tc=AQAAAJuaDFpOdQYARlNadFi502DO2kaj; Path=/; HttpOnly
Server: nginx
Location: https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html??spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989
<HTML>
<HEAD>
<TITLE>Moved Temporarily</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000">
<H1>Moved Temporarily</H1>
The document has moved <A HREF="https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html??spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989">here</A>.
</BODY>
</HTML>
從上面的資訊可以看出來，新浪做了 302 跳轉，同時為了相容性，還傳回用于手動調整的 HTML 内容。整個互動流程如下：
短鍊生成方式
根據 網頁數量統計 資訊，目前全球有 58 億的網頁，Java 中 int 取值最多是 2^32 = 4294967296 < 43 億 < 58 億，long 取值是 2^64 > 58 億。是以如果是用數字的話，int 勉強能夠支撐（畢竟不是所有網址都會調用短鍊服務建立短鍊），使用 long 就比較保險，但會造成空間浪費，具體使用哪種類型，需要根據業務自己判斷了。
新浪微網誌使用 8 位字元串表示原始連結，這種字元串可以了解為數字的 62 進制表示，62^8 = 3521614606208 > 3521 億 > 58 億，也就是可以解決目前全球已知的網址。62 進制就是由 10 個數字 + (a-z)26 個小寫字母 + (A-Z)26 個大寫字母組成的數。
生成方式1：Hash
對原始連結取 Hash 值，是一種比較簡單的思路。有很多現成的算法可以實作，但是有個避不開的問題就是：Hash 碰撞，是以選一個碰撞率低的算法比較重要。
推薦 MurmurHash 算法，這種算法是一種非加密型哈希函數，适用于一般的哈希檢索操作，目前 Redis，Memcached，Cassandra，HBase，Lucene 都在用這種算法。
借助 Guava 中的 MurmurHash 實作：
final String url = "https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html?spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989";
final HashFunction hf = Hashing.murmur3_128();
final HashCode hashCode = hf.newHasher().putString(url, Charsets.UTF_8).hash();
final int hashCodeAsInt = hashCode.asInt();// 這裡選擇傳回 int 值，也可以選擇傳回 long 值
System.out.println(hashCodeAsInt);// 輸出的結果是：1810437348，轉換成 62 進制是：1Ywpso
對于碰撞問題，最簡單的一種思路是，如果發生碰撞，就給原始 URL 附加上特殊字元串，直到躲開碰撞為止。具體操作如下圖：
生成方式2：統一發号器
這個就是不管來的是什麼，通過集中的統一發号器，配置設定一個 ID，這個 ID 就是短鍊的内容，比如第一個來的就是
https://tinyurl.com/1，第二個就是
https://tinyurl.com/2，以此類推。當然可能一些分布式ID算法上來就是很長的一個序号了。為了擷取更短路，還可以将其轉為 62 進制字元串。
Redis 自增：Redis性能好，單機就能支撐10W+請求，如果作為發号器，需要考慮Redis持久化和災備。
MySQL 自增主鍵：這種方案和Redis的方案類似，是利用資料庫自增主鍵的提醒實作，保證ID不重複且連續自動建立。
Snowflake：這是一種目前應用比較廣的ID序列生成算法，美團的Leaf是對這種算法的封裝更新服務。但是這個算法依賴于伺服器時鐘，如果有時鐘回撥，可能會有ID沖突。（有人會較真毫秒中的序列值是這個算法的瓶頸，話說回來了，這個算法隻是提供了一種思路，如果覺得序列長度不夠，自己加就好，但是每秒百萬級的服務真的又這麼多嗎？）
等等。。。
後續會有一篇單獨介紹統一發号器的文章，完後會修改這裡，并附上連結，或者你也可以關注我（微信号：看山的小屋），擷取第一手資料。
對于統一發号器這種方式，還需要解決的一個問題是：如果同一個原始連結，應該傳回相同的短鍊還是不同的短鍊？
答案是根據使用者、地點等次元，相同的原始連結，傳回不同的短鍊。如果判斷次元都相同，則傳回相同短鍊。這樣做的好處是，我們可以根據短鍊的點選、請求資訊，做資料統計。對于短鍊，我們犧牲的隻是一些存儲和運算，但是收集的資訊卻是無價的。
存儲短鍊
一般這種資料的存儲無非就兩種：關系型資料庫或NoSQL資料庫。有了上面的建立邏輯，存儲就是水到渠成的了。下面給出MySQL存儲的建表語句：
CREATE TABLE IF NOT EXISTS tiny_url
(
sid INT AUTO_INCREMENT PRIMARY KEY,
create_time DATETIME DEFAULT CURRENT_TIMESTAMP NULL,
update_time TIMESTAMP DEFAULT CURRENT_TIMESTAMP NULL ON UPDATE CURRENT_TIMESTAMP,
version INT DEFAULT 0 NULL COMMENT '版本号',
tiny_url VARCHAR(10) NULL COMMENT '短鍊',
original_url TEXT NOT NULL COMMENT '原始連結',
# 其他附加資訊
creator_ip INT DEFAULT 0 NOT NULL,
creator_user_agent TEXT NOT NULL,
# 使用者其他資訊，用于後續統計，對于這些資料，隻要存儲影響建立短鍊的必要字段就行，其他的都可以直接發送到資料服務中
instance_id INT DEFAULT 0 NOT NULL,
# 建立短鍊服務執行個體ID
state TINYINT DEFAULT 1 NULL COMMENT '-1無效 1有效'
);
再啰嗦一句，存儲需要考慮資料量級，提前規劃是否需要分表分庫。
短鍊請求
存儲完成後，接下來就該使用了。
通常的做法是會根據請求的短鍊字元串，從存儲中找到資料，然後傳回HTTP重定向到原始位址。如果存儲使用關系型資料庫，對于短鍊字段一般需要建立索引，而且為了避免資料庫成為瓶頸，資料庫前面還會通過緩存鋪路。而且為了提高緩存合理使用，一般通過LRU算法淘汰非熱點短鍊資料。流程如下圖：
圖中的布隆過濾器是為了防止緩存擊穿，造成伺服器壓力過大。
這裡還有一個問題：HTTP傳回重定向編碼時使用301還是302，為什麼新浪微網誌會傳回302，而不是更加符合語義的 301 跳轉？（對于 HTTP 狀态碼不太了解的同學，可以從 《HTTP 狀态碼總結》 獲得更多資訊）
301，代表永久重定向。也就是說，浏覽器第一次請求拿到重定向位址後，以後的請求，都是直接從浏覽器緩存中擷取重定向位址，不會再請求短鍊服務。這樣可以有效減少服務請求數，降低伺服器負載，但是因為後續浏覽器不再向後端發送請求，是以擷取不到真實的點選數。
302，代表臨時重定向。也就是說，每次浏覽器都會向伺服器發起請求擷取新的位址，雖然會給伺服器增加壓力，但在硬體過剩的今天，這點壓力比起資料簡直不值一提。是以，302 重定向才是短鍊服務的首選。
總結
短鍊服務其實比較簡單，沒有太多的業務邏輯，主要考察對于分布式系統常用設計的了解，也是經常被用在面試過程中的一道題。這裡隻是提供大家一些設計思路，文中涉及到的發号器（分布式ID）、布隆過濾器、MurmurHash等都沒有太過深入，因為每一個都不是三言兩語可以說明白的，需要大家自行解決了。