系統設計學習筆記 - URL Shortener (短網址產生器) - (1)

Posted on In
介紹如何設計短網址產生器

短網址產生器是用別名來代替原始 URL，即短網址，瀏覽短網址會重新導向到原始 URL。

優點

  • 易於分享

  • 節省儲存空間

缺點

  • 無法直接識別原始服務的 Domain

  • 會受到短網址服務的運行狀態影響，導致短網址失效

資源估算

假設條件

  • Shortening:redirection request ratio 為 1:100

  • 每月產生 200 million 個新的短網址

  • 每個短網址需要 500 bytes 的儲存空間

  • 過期時間為五年，不支援更新、刪除

  • Daily Active Users (DAU) 為 100 million

Storage

每月 200 million 個 shortening request，共 5 年

200 million/month × 12 months/year × 5 years = 12 billion

每個短網址 500 bytes

12 billion × 500 bytes = 6 TB

Query rate

Shortening:redirection request ratio 為 1:100，每月 redirection request

200 million × 100 = 20 billion

接下來估算 Queries Per Second (QPS)，每月平均 30.42 天

30.42 days × 24 hours × 60 minutes × 60 seconds = 2628288 seconds

Shortening request

200 million / 2628288 seconds = 76 URLs/s

Redirection request

100 × 76 URLs/s = 7.6K URLs/s

Bandwidth

Shortening request

76 × 500 bytes × 8 bits = 304 Kbps

Redirection request

7.6K × 500 bytes × 8 bits = 30.4 Mbps

Memory

快取頻繁存取的 redirection request，假設進來的流量符合 80/20 法則，20% 的 redirection request 產生 80% 的流量，則每日

7.6K × 3600 seconds × 24 hours = 0.66 billion

0.2 × 0.66 billion × 500 bytes = 66 GB

Server 數量

假設每台 server 的 Requests Per Second (RPS) 為 64000，peak load times 為 100 million RPS

100 million / 64000 = 1562.5 ≈ 1.6K servers

高階設計

API Endpoints

使用 RESTful API，需要兩個端點，一個產生短網址，一個做重新導向

  1. URL shortening

    POST api/v1/data/shorten

    • Request parameter: {longUrl: longURLString}

    • Return shortURL

  2. URL redirecting

    GET api/v1/shortUrl

    • Return longURL for HTTP redirection

URL redirecting

Server 收到 request 後，使用 301 或 302 redirect，重新導向短網址到原始 URL

  • 301 redirect

    瀏覽器快取 response 後，相同 URL 的 request 不會再送到短網址服務

  • 302 redirect

    相同 URL 的 request 會再送到短網址服務

301 redirect 可以減少 server load，而 302 redirect 可以追蹤點擊率和點擊來源

URL shortening

使用 Base 62 轉換，產生短網址如 www.tinyurl.com/{shortURL}

深入設計

URL shortening

  1. 假設 input longURL 為 https://en.wikipedia.org/wiki/Systems_design

  2. 產生 unique ID: 2009215674938

  3. 使用 Base 62 將 ID (2009215674938) 轉換為 zn9edcu

  4. 儲存到資料庫

    ID shortURL longURL
    2009215674938 zn9edcu https://en.wikipedia.org/wiki/Systems_design

URL redirecting

  1. User 點擊短網址 https://tinyurl.com/zn9edcu

  2. Load balancer 轉送 request 到 web server

  3. 如果 shortURL 在 cache 裡，直接回傳 longURL

  4. 如果 shortURL 不在 cache 裡，從 DB 取得 longURL。如果 longURL 不在 DB 裡，user 可能輸入錯誤

  5. 回傳 longURL 給 user

References