Stories

Detail Return Return

ByteByteGo學習筆記：URL短鏈服務設計 - Stories Detail

引言

在互聯網技術日新月異的今天，URL短鏈服務已經成為日常網絡生活中不可或缺的一部分。每當想要分享一個冗長的網頁鏈接，或者需要在對字符數量敏感的平台（如社交媒體、短信等）發佈鏈接時，URL短鏈服務都能將長長的URL地址精簡成短小、易於傳播的鏈接。例如，將冗長的 https://www.systeminterview.com/q=chatsystem&c=loggedin&v=3&i=long 縮短為 https://tinyurl.com/y7keocwj，這不僅提升了用户體驗，也方便了鏈接的分享和管理。

需求分析

對於URL短鏈服務而言，其核心需求看似簡單，即將長URL轉換為短URL，並將短URL重定向回原始的長URL。然而，在實際設計過程中，需要考慮更多細節和約束條件。

1. 功能性需求

首先，需要明確URL短鏈服務的基本功能。

  • URL縮短功能: 接收一個長URL，生成並返回一個短URL。例如，用户輸入 https://www.example.com/very/long/path/to/resource?param1=value1&param2=value2，系統應返回 https://tinyurl.com/shortCode 這樣的短鏈接。
  • URL重定向功能: 當用户訪問短URL時，服務能夠將其重定向到原始的長URL。例如，用户訪問 https://tinyurl.com/shortCode，瀏覽器應自動跳轉到 https://www.example.com/very/long/path/to/resource?param1=value1&param2=value2。

2. 非功能性需求

除了基本功能，非功能性需求同樣重要，它們直接關係到系統的性能、可靠性和可擴展性。

  • 流量預估: 每日產生1億個URL縮短請求。這是一個相當大的量級，意味着系統需要具備高吞吐量和低延遲的處理能力。

    • 寫入QPS (Queries Per Second): 1億 / (24小時 * 3600秒) ≈ 1160 QPS。這意味着系統平均每秒需要處理約1160個URL縮短請求。
    • 讀取QPS: 假設讀操作（短URL重定向）與寫操作的比例為10:1，則讀取QPS約為 1160 * 10 = 11600 QPS。實際應用中，讀取操作可能會遠高於寫入操作，因為一個短URL可能會被多次點擊訪問。
  • 短URL長度: 儘可能短。 用户期望短URL足夠簡潔，易於記憶和分享。
  • 短URL字符集: 允許使用數字 (0-9) 和字符 (a-z, A-Z) 的組合。 這定義了構成短URL的字符範圍，共計 10 + 26 + 26 = 62 個字符。
  • 短URL更新與刪除: 為了簡化設計，假設短URL一旦生成，不可刪除或更新。 這是一個重要的簡化假設，實際系統中可能需要考慮URL失效、更新等機制。

  • 持久性存儲: URL短鏈服務需要長期運行，假設為10年。 這意味着需要考慮數據存儲的容量和持久性。

    • 總記錄數: 1億 URL/天 365 天/年 10 年 = 3650億條記錄。
    • 存儲容量估算: 假設平均URL長度為100字節（包括短URL和長URL），則10年總存儲需求為 3650億 * 100 字節 = 36.5 TB。 這是一個相當可觀的數據量，需要選擇合適的存儲方案。
  • 高可用性、可擴展性、容錯性: 作為一項基礎服務，URL短鏈服務必須具備高可用性（7x24小時穩定運行）、可擴展性（能夠應對未來流量增長）和容錯性（在部分組件故障時仍能正常服務）。

3. 封底估算

在系統設計初期進行封底估算（Back-of-the-Envelope Estimation）非常關鍵。它幫助我們快速評估系統規模，識別潛在瓶頸，並指導後續的設計方向。上述的流量和存儲容量估算就是典型的封底估算。

高層設計：架構藍圖

在明確了需求和範圍之後，進入高層設計階段，勾勒出系統的整體架構藍圖。

1. API 端點設計

API (Application Programming Interface) 是客户端與服務器交互的橋樑。對於URL短鏈服務，需要設計簡潔、易用的API端點。採用 RESTful API 設計風格是一個不錯的選擇。RESTful API 以資源為中心，使用標準的HTTP方法（GET, POST, PUT, DELETE 等）進行操作。

  • URL縮短 API (POST /api/v1/data/shorten):

    • 請求方法: POST
    • 請求路徑: /api/v1/data/shorten
    • 請求參數: longURLString (長URL字符串)，通常放在請求體 (Request Body) 中。
    • 響應: 返回生成的短URL。

  • URL重定向 API (GET /api/v1/shorten/{shortURL}):

    • 請求方法: GET
    • 請求路徑: /api/v1/{shortURL}，其中 {shortURL} 是短URL的路徑部分，例如 y7keocwj。
    • 響應: 返回原始的長URL。

2. URL 重定向機制

當用户在瀏覽器中輸入短URL（例如 https://tinyurl.com/y7keocwj）並訪問時，瀏覽器會向URL短鏈服務發起一個GET請求。服務器接收到請求後，需要將短URL解析，找到其對應的長URL，並進行重定向。

這裏，需要選擇合適的HTTP重定向狀態碼：

  • 301 永久重定向 (Moved Permanently): 301 重定向表示請求的URL已永久移動到新的URL（即長URL）。瀏覽器在接收到301響應後，會緩存這個重定向關係。後續對同一短URL的請求，瀏覽器將直接從緩存中讀取長URL，並直接跳轉，而不會再次請求URL短鏈服務。

    • 優點: 減輕服務器壓力，提升性能，因為只有首次請求會到達服務器。
    • 適用場景: 當短URL與長URL的映射關係長期穩定不變時，適合使用301重定向。

  • 302 臨時重定向 (Found): 302 重定向表示請求的URL只是臨時移動到新的URL。瀏覽器不會緩存302重定向響應。每次訪問短URL，瀏覽器都會先請求URL短鏈服務，服務器再返回302重定向到長URL。

    • 優點: 便於進行點擊統計和分析。每次短URL被訪問，服務器都能記錄到。
    • 缺點: 服務器壓力較大，性能相對較低，因為每次請求都需要經過URL短鏈服務。
    • 適用場景: 當需要追蹤點擊量、分析用户行為（例如點擊來源、時間等）時，可以使用302重定向。

對於 tinyurl.com 這樣的URL短鏈服務，301 重定向通常是更合適的選擇。因為其主要目標是提供高效的URL縮短和重定向服務，減少服務器負載，提升用户訪問速度。如果需要進行詳細的點擊分析，可以考慮其他方案，例如在重定向前，先通過消息隊列異步記錄點擊事件。

image
(展示了用户訪問短URL tinyurl.com 時的重定向流程：瀏覽器發送請求到服務器，服務器查找短URL對應的長URL，並使用301重定向返回給瀏覽器。)

3. 短URL生成 (URL Shortening) 流程

如何將長URL映射為短URL？一個初步的想法是使用哈希表（Hash Table）。可以將短URL作為鍵（Key），長URL作為值（Value）存儲在哈希表中。當需要重定向時，根據短URL在哈希表中查找對應的長URL。

然而，僅僅使用哈希表作為數據存儲方案是不夠的，主要有以下幾個原因：

  • 內存限制: 哈希表通常存儲在內存中，而內存容量有限且昂貴。對於需要存儲數千億條URL映射關係的服務來説，內存是無法滿足需求的。
  • 持久性需求: 內存中的數據是非持久化的，一旦服務重啓或宕機，數據就會丟失。URL短鏈服務需要持久化存儲URL映射關係，以便長期穩定運行。

因此，需要更合適的持久化存儲方案，例如關係型數據庫（如MySQL, PostgreSQL）或NoSQL數據庫（如Redis, Cassandra, HBase 等）。在詳細設計中，將深入探討數據模型和短URL生成算法。

核心組件

在高層設計的基礎上，進一步深入到核心組件的設計細節，包括數據模型、哈希函數、URL縮短算法和URL重定向的具體實現。

1. 數據模型：關係型數據庫設計

考慮到數據持久性、事務支持和成熟的技術生態，關係型數據庫是存儲URL映射關係的良好選擇。可以設計一個簡單的數據庫表，例如命名為 URL_MAPPING。

image
(圖4 展示了一個簡化的數據庫表 URL_MAPPING 設計，包含三列：id (主鍵，自增ID), shortURL (短URL字符串), longURL (原始長URL字符串)。)

  • id (BIGINT, Primary Key, Auto Increment): 作為主鍵，使用自增的BIGINT類型，保證唯一性和高效索引。它不僅是表的主鍵，也將作為生成短URL的基礎。
  • shortURL (VARCHAR(255), Unique Index): 存儲短URL字符串，例如 "y7keocwj"。設置為唯一索引，確保短URL的唯一性，並加速根據短URL查找長URL的查詢。
  • longURL (TEXT): 存儲原始的長URL，使用TEXT類型可以存儲較長的URL字符串。

2. 哈希函數與短URL生成算法

核心問題是如何將長URL高效、唯一地映射為短URL。內容中探討了兩種主要的哈希函數方法：

  • 方法一：哈希 + 碰撞解決 (Hash + Collision Resolution)

    • 思路: 使用傳統的哈希函數（如 CRC32, MD5, SHA-1）將長URL哈希成一個固定長度的哈希值。然後，截取哈希值的前N個字符作為短URL。

    • 哈希值長度確定: 根據之前估算的10年3650億條URL記錄，需要確定短URL的最小長度。短URL由62個字符 (0-9, a-z, A-Z) 組成。計算不同長度n對應的最大URL數量 (62^n)：

      image
      (表展示了短URL長度 n 與其能支持的最大URL數量的對應關係。當 n=7 時，62^7 ≈ 3.5萬億，足以支持3650億條URL。)

      因此，短URL長度至少需要7位。

    • 碰撞問題與解決: 哈希函數可能產生碰撞（不同的長URL哈希到相同的哈希值）。為了解決碰撞，一種方法是附加前綴字符串重試。
      image
      (圖描述了哈希碰撞解決的流程：首先嚐試使用哈希函數生成短URL，如果短URL已存在（碰撞），則在原始長URL上添加一個前綴字符串，再次進行哈希，重複此過程直到生成一個未被使用的短URL。)

      這種方法雖然可以解決碰撞，但效率較低，每次生成短URL可能需要多次數據庫查詢以檢查碰撞。布隆過濾器 (Bloom Filter) 可以用於優化碰撞檢查過程，減少數據庫查詢次數。布隆過濾器是一種概率型數據結構，可以快速判斷一個元素是否可能在一個集合中。雖然布隆過濾器可能存在誤判（將不存在的元素判斷為存在），但可以大大減少不必要的數據庫查詢。

  • 方法二：基數 62 轉換 (Base 62 Conversion)

    • 思路: 使用一個唯一ID生成器生成全局唯一的ID（例如自增ID或分佈式ID生成器）。然後，將這個ID看作一個十進制數字，將其轉換為 基數 62 表示。基數 62 使用 0-9, a-z, A-Z 這62個字符來表示數字。

    • 基數 62 轉換過程示例: 將十進制數 111571 轉換為基數 62。

      image
      (圖展示了將十進制數 111571 轉換為基數 62 的過程。通過不斷地除以 62 並取餘數，得到基數 62 的表示 [2, 7, 55, 59]，對應基數 62 編碼 "2TXK" (假設 55 對應 'X', 59 對應 'K')。)

      最終得到的基數 62 編碼字符串就是短URL的 Hash Value 部分。例如，ID 2009216747938 轉換為基數 62 為 "zn9edcu"。

    • 優點:

      • 保證唯一性: 由於ID生成器生成的是唯一ID，基數 62 轉換後的短URL也是唯一的，不會發生碰撞。
      • 容易生成下一個短URL: 如果ID是遞增的，可以很容易預測下一個生成的短URL。但這可能帶來安全問題（容易被遍歷）。

    • 缺點:

      • 短URL長度不固定: 短URL的長度取決於ID的大小。ID越大，短URL越長。但通常情況下，ID增長速度是可控的，短URL長度不會過長。
      • 安全性: 如果ID是順序遞增的，攻擊者可能會預測短URL的生成規律，批量生成短URL。可以使用更復雜的ID生成策略，例如 UUID 或 分佈式ID生成器（Snowflake 算法等），提高安全性。
    • 基數 62 轉換方法是更適合URL短鏈服務的方案。 它保證了短URL的唯一性，實現簡單高效，且易於理解和維護。

3. URL 縮短流程詳解 (使用基數 62 轉換)

![[iamge]](https://wenzuojing.oss-cn-beijing.aliyuncs.com/screenshot_173...)
(圖詳細描述了使用基數 62 轉換的 URL 縮短流程。)

  1. 接收長URL: 客户端發送 POST 請求到 /api/v1/data/shorten，攜帶 longURLString。

  2. 檢查長URL是否已存在: 在 URL_MAPPING 表中查詢 longURL 列，檢查該長URL是否已經被縮短過。

    • 如果已存在: 直接從數據庫中獲取已存在的 shortURL 並返回給客户端。避免重複生成短URL，提高效率。
    • 如果不存在: 繼續下一步。
  3. 生成唯一ID: 調用分佈式唯一ID生成器獲取一個新的唯一ID。
  4. 基數 62 轉換: 將生成的唯一ID轉換為基數 62 編碼，得到 hashValue (短URL的後半部分)。
  5. 構建短URL: 將域名 (例如 https://tinyurl.com/) 與 hashValue 拼接，生成完整的短URL。
  6. 保存到數據庫: 在 URL_MAPPING 表中插入一條新記錄，包含 id (唯一ID), shortURL, longURL。
  7. 返回短URL: 將生成的 shortURL 返回給客户端。

4. URL 重定向流程詳解

image
(圖詳細描述了 URL 重定向流程，包括緩存的使用。)

  1. 用户訪問短URL: 用户點擊或輸入短URL (例如 https://tinyurl.com/zn9edcu)。
  2. 負載均衡器 (Load Balancer): 請求首先到達負載均衡器。負載均衡器將請求分發到後端的 Web 服務器集羣中的某一台服務器。
  3. Web 服務器: Web 服務器接收到請求。

  4. 緩存查找 (Cache Lookup): Web 服務器首先在緩存 (Cache) 中查找短URL對應的長URL。

    • 如果緩存命中 (Cache Hit): 直接從緩存中獲取長URL，並進行 301 重定向。緩存提升了讀取性能，減少數據庫壓力。
    • 如果緩存未命中 (Cache Miss): 繼續下一步。

  5. 數據庫查詢 (Database Query): Web 服務器查詢數據庫 URL_MAPPING 表，根據 shortURL 查找 longURL。

    • 如果數據庫中找到: 將 longURL 從數據庫中取出，更新緩存 (Cache Update)，將 <shortURL, longURL> 鍵值對放入緩存，並進行 301 重定向到 longURL。
    • 如果數據庫中未找到: 説明短URL無效或不存在，返回錯誤響應 (例如 HTTP 404 Not Found)。
  6. 返回重定向響應: Web 服務器返回 301 重定向響應，將客户端瀏覽器重定向到長URL。

5. 分佈式唯一ID生成器

在分佈式系統中，生成全局唯一ID是一個常見的挑戰。對於URL短鏈服務，需要一個能夠生成高併發、低延遲、全局唯一ID的組件。常見的分佈式ID生成方案包括：

  • UUID (Universally Unique Identifier): UUID 由算法生成，保證全局唯一性，但UUID通常較長，且無序，不適合作為短URL的一部分，但可以作為數據庫表 id 列的備選方案。
  • 數據庫自增ID: 在單數據庫場景下可行，但在分佈式數據庫或高併發場景下，數據庫自增ID可能成為瓶頸。
  • Snowflake 算法: Twitter 開源的分佈式ID生成算法，生成 64 位的ID，包含時間戳、機器ID、數據中心ID、序列號等信息，保證全局唯一性和趨勢遞增性，性能高，可靠性好。Snowflake 算法是更適合分佈式URL短鏈服務的ID生成方案。
  • Redis INCR/原子計數器: 利用 Redis 的原子遞增操作生成唯一ID。Redis性能高，但需要考慮Redis的可用性和持久化。

總結與擴展

討論了API設計、數據模型、哈希函數選擇、URL縮短和重定向流程，以及分佈式唯一ID生成器等核心組件。

  • 需求分析: 明確功能性和非功能性需求，進行流量和存儲容量估算。
  • 架構設計: 設計API端點，選擇合適的重定向策略 (301 或 302)，初步考慮數據存儲方案。
  • 設計核心組件: 數據庫模型設計、哈希函數 (基數 62 轉換) 選擇、URL縮短和重定向流程、緩存使用、分佈式ID生成器。
  • 性能、可擴展性、可用性: 緩存提升性能，負載均衡和數據庫擴展提高可擴展性，冗餘部署和容錯設計保證可用性。

擴展 :

  • 速率限制 (Rate Limiting): 防止惡意用户或爬蟲 Flood 攻擊，限制IP地址或用户在單位時間內請求URL縮短的頻率。可以使用令牌桶 (Token Bucket) 或 漏桶 (Leaky Bucket) 算法實現速率限制。
  • Web 服務器擴展: Web 服務器層是無狀態的，容易通過水平擴展 (增加服務器數量) 來提高處理能力。可以使用負載均衡器 (Load Balancer) 將請求分發到多台 Web 服務器。
  • 數據庫擴展: 數據庫是瓶頸點。可以採用數據庫複製 (Database Replication) (讀寫分離，提高讀取性能和可用性) 和 數據庫分片 (Database Sharding) (將數據分散到多個數據庫實例，提高寫入性能和存儲容量) 等技術進行擴展。
  • 分析與監控 (Analytics & Monitoring): 集成分析功能，例如統計短URL的點擊量、點擊來源、用户地域分佈等，為運營決策提供數據支持。完善的監控系統對於及時發現和解決問題至關重要。
  • 可用性、一致性、可靠性 (Availability, Consistency, Reliability): 在分佈式環境下，需要權衡 CAP 理論 (一致性、可用性、分區容錯性)，根據業務需求選擇合適的策略。例如，對於URL短鏈服務，可用性通常比強一致性更重要。

參考資料
ByteByteGo

架構 , 學習 , 設計原則 , 後端
user avatar vanve Avatar aipaobudeshoutao Avatar aitibao_shichangyingxiao Avatar java_study Avatar cbuc Avatar lyflexi Avatar emanjusaka Avatar god23bin Avatar yunpan-plus Avatar javalover Avatar kubesphere Avatar kuaidi100api Avatar
Favorites 45 users favorite the story!
Favorites

Add a new Comments

Some HTML is okay.