面試官：如何設計一個高并發的短鏈系統？
短鏈系統的核心功能，通過將長鏈接轉換為短字符串的方式，提升鏈接的可讀性和傳播性，適用于消息通知、廣告推廣、社交媒體等場景。
如下圖所示：
圖片
短鏈系統的核心功能有兩個，短鏈跳轉和短鏈生成，我們來一一看下具體實現，最后再講講如何實現高并發的短鏈系統。
短鏈跳轉的實現原理
短鏈跳轉有HTTP 302和HTTP 301兩種實現方式，我們來分別講解一下。
永久重定向（301）
瀏覽器會緩存第一次請求短鏈所重定向的長鏈，之后再有相同的短鏈請求，就可以直接從瀏覽器緩存中獲取了，無須再給短鏈服務器發送請求獲取。
StatusCode： 301 Moved Permanently
Location: https://origin.com/long-url?param=value
圖片
臨時重定向（302）
當用戶訪問短鏈接的時候，短鏈服務器會返回原始的長鏈并進行HTTP重定向，將其轉發到長鏈服務器上，這一切對于用戶是無感的。
瀏覽器不會對請求短鏈所重定向的長鏈進行緩存，每次都需要請求短鏈服務器進行獲取。
Status Code： 302 Moved Temporarily
Location: https://origin.com/long-url?param=value
圖片
那問題來了，我們到底應該選擇HTTP 301還是302進行重定向呢？
如果我們的短鏈服務處于高并發場景，優先選擇HTTP 301永久重定向的方式減少對服務的請求數，從而降低服務器的壓力。
反之，在非高并發場景且對訪問短鏈服務有計數訴求，那我們可以選擇HTTP 302臨時重定向。
短鏈生成的實現原理
接下來，我們來講講短鏈生成的實現原理：長鏈哈希、自增序列、隨機字符串和預生成四種方案。
如下圖所示：
圖片
長鏈哈希
（1）目前常見的哈希算法有MD5、SHA1、MurmurHash等，先將長鏈通過這些算法生成一個哈希值。
如：將長鏈“https://www.example.com/very/long/url/with/parameters”進行哈希計算，得到結果“3a6bd3e2560a3d23eea436fcfb7e44c7”。
（2）將生成的結果字符串進行截斷，留下前6位短碼，得到結果“3a6bd3”。
目前，6位短碼已經能夠滿足絕大多數使用場景，因為6位的短碼可以提供568億種的組合。
（3）將截取后得到的短碼和原始的長鏈建立一一映射關系，并存儲在數據庫或緩存中。
這樣，當用戶訪問短碼對應的短鏈時，系統就可以通過查詢映射關系找到原始的長鏈，并進行重定向。
該方案的優點是實現簡單，但存在哈希碰撞的可能性，在碰撞時需要在原來的哈希值上增加隨機數再進行哈希。
自增序列
（1）目前有兩種主流的實現方式，通過雪花算法或數據庫自增ID來生成唯一數字ID。
前者則強依賴機器時鐘，如果機器上時鐘回撥，會導致ID重復。
后者的ID生成涉及到數據庫操作，性能相對不高，且引入數據庫會導致鏈路變長，增加出錯概率。
圖片
（2）以進制轉換的方式將數字ID進行縮短，如：十進制數字1234567890的六十二進制為1l3MoK。
（3）將截取得到的短碼和原始的長鏈建立一一映射關系，并存儲在數據庫或緩存中。
該方案的優點是不存在長鏈哈希的碰撞問題，但如上文所述，也會根據實現方式不同引入其他問題。
隨機字符串
（1）可以通過取UUID前8位字符的方式生成短碼，將實現起來非常簡單。
import java.util.UUID;
public class GenerateUUID {
public static void main(String[] args) {
// 生成一個隨機的 UUID
UUID uuid = UUID.randomUUID();
// 輸出生成的 UUID
String uuidString = uuid.toString();
// 截取前八位
String firstEightChars = uuidString.substring(0, 8);
// 輸出截取的前八位
System.out.println("First eight characters: " + firstEightChars);
}
}（2）以進制轉換的方式將數字ID進行縮短，如：十六進制數字5ca877b6的六十二進制為k3v6bO。
（3）將截取得到的短碼和原始的長鏈建立一一映射關系，并存儲在數據庫或緩存中。
該方案的優點是實現簡單，通過JDK自帶的工具類即可實現，連jar包都不需要引入，但會存在數字ID重復的問題。
預生成
該方案主要解決上述方案中，臨時生成哈希值存在哈希碰撞，或臨時生成數字ID存在重復的問題。
預先生成一批短碼并存儲在數據庫中，當需要生成短鏈時，直接將未使用的短碼與長鏈接進行關聯即可。
當然，該方案相比于其他三種方案，實現起來更復雜一些。
實現高并發的短鏈系統
以阿里、字節、拼多多等互聯網大廠的電商鏈接、短視頻分享為例，每天會產生幾億條短鏈，訪問短鏈的QPS會達到幾百萬。
如此高的并發量，對于短鏈系統承載力是個巨大的考驗。
高并發短鏈系統架構設計如下：
圖片
（1）如上文所說，如果我們的短鏈服務處于高并發場景，優先選擇HTTP 301永久重定向的方式減少對服務的請求數，從而降低服務器壓力。
（2）雪花算法，每個服務器節點理論上可生成4096000個不重復的數字ID，然后再轉換為62進制的短鏈。
由于雪花算法不會出現重復數字ID的情況，可以在代碼中省去短鏈判重步驟，提升生成短鏈的吞吐量。
（3）采用Redis + Caffine雙緩存機制存儲熱點短鏈，由于短鏈不會出現變更的情況，所以不用考慮數據一致性的問題。
（4）每天產生幾億條短鏈，換算下來每秒鐘生成短鏈的峰值TPS可達到幾萬，采用分庫分表的方案來均攤寫操作帶來的性能瓶頸，Sharding Key為短鏈值。
分片算法：
數據庫ID = 短鏈碼哈希值 % 數據庫數量
數據表ID = 短鏈碼哈希值 / 數據庫數量 % 數據表數量
另外，短鏈映射表中的數據是冷熱分明的，可通過三個月或半年進行歸檔的方式降低數據庫的存儲壓力。
