System Design - Short URL System


Posted by StuartHsu on 2022-03-12

用途與需求

  1. 這東西有什麼用
  2. 清楚明確的功能描述
  3. 可能的規模量級與要求的效能
  4. 系統額外需求:效能、可用性、安全性...等等

用途

  • User 層面:
    1. 讓使用者更好分享
    2. 隱藏原始網址,增加安全性
  • Developer 層面:
    1. 可分析各網站流量、廣告表現

功能

  • 給定一個 url,產生一個短 url 能連結到相同網站
  • 客製化短網址名
  • 預設或客製化過期時間
  • 追蹤統計
  • 安全

效能與額外需求

  • 服務必須極高可用性
  • Create 與 Redirect 時間必須足夠短
  • 如何阻止被濫用或攻擊

API

createURL(
  authentication_key,
  original_url,
  custom_alias = None,
  expire_date = None
)

getURL(
  authentication_key,
  shorted_url,
)

deleteURL(
  authentication_key,
  shorted_url,
)

流量預計有多大

  • Traffic: 幾個 request/s
  • Storage: 硬體容量
  • Bandwidth: 幾 byte/s
  • Memory: cache

資料量

  1. 每月寫入 500M 新 url
  2. 寫與讀的比例為 1:100
  3. 保存期限 5 年
  4. 一組 URL 500 Byte

問題

  1. 讀的 QPS 是多少: 500x1000000/(30天x24小時x60分x60秒) ~ 20K /s (其實要需要考慮尖峰值)
  2. 需保存的 url 有幾筆:500M 12月 5年 = 30000M = 30B
  3. 需多少硬碟:30000M * 500byte = 13.6 TB
  4. Cache memory:
    • 一天最熱門的 20%:20K x 3600s x 24小時 = 1.7B
    • 1.7 x 0.2 x 500byte = 170 GB

DB 選擇考量點

  • 資料量達到數十億筆
  • 每筆資料都很小
  • 資料間沒有關聯
  • 讀比寫重很多

Encoding

考量點

  • key 的合適長度?
  • 撞 key 如何處理?

Key 合適長度估計計算

  • Base62:[A-Za-z0-9]
  • 長度 6:62^6 = ~56.8 Billion (5.68e10) => 當快存滿時,每一筆碰撞機率大增
  • 長度 7:62^7 = ~3.5 Trillion (3.5e12)

Key 產生方式的選擇

  1. random 7 碼 base62 code
    • 優點:當有 delete 需求時,即使原網址一樣,短網址也必須不同
  2. 原網址 => MD5 hash => base62 encode => 取前 7 碼
    MD5 產完以後再 encode 取完幾乎也是 random 了
    • 優點:省 db
  • 需考量同網址要不要給同樣的短網址:
    如果允許使用者刪除,那就不能同網址都給出同樣的短網址,如此一來則選用 random 較優
  • 兩方法碰撞率差不多

系統基本設計

DB 選擇

寫只能一台,讀可以分很多台,瓶頸是寫入,該如何提升?

  1. RDBMS:可以 lock table 檢查是否出現過,但不利於擴展。
  2. NoSQL:利於水平擴展,資料型態也合適,但通常沒有 strong-consistence。
    可能解法:
  • Queue: 能不能接受等很久?有塞車問題,比較不適合
  • Redis: 延遲寫入,效率比 DB 高很多,但會有壞掉掉資料的風險,寫入終究還是要等 DB
  • Sharding(分片): 依據產出來的短網址的 key(例如第一碼)去寫入對應的 DB,可以避免 lock 的問題。

撞 key 解決方案:

  1. MongoDB Sharding + putIfAbsent + Indexing
  2. Key Generation Service (KGS):
    因為每次都要問存不存在,可以開一個 key 產生器,預先產好一堆放在 KGS,server 可以一次拿一堆 key 過去(拿了的就註銷掉),這些 key 一定沒用過,用完一坨再去拿,如此可以不用頻繁的每次都問 DB
  3. RDBMS + auto increment counter:
    利用 DB auto increment 出來的 id 作為 sequence no.,接著每一台 server 可以專職負責不同需段的 sequence no.,但會遇到要再次擴展時,如何分配、確認用過的 sequence no. 的問題

寫入效能要求?

真的需要這麼好的寫入效能嗎?

Partition 常見問題

  • Celebrity:有些 key 太常被使用,需要更聰明的分流
  • Join:跨 Partition Join 太慢,需要做 de-normalization

額外需求

  • HA
  • 資料保存
  • 保存期限
  • 客製化 key
  • 資安

#System Design







Related Posts

[Week 2] JavaScript - 變數、陣列、物件、== 與 ===

[Week 2] JavaScript - 變數、陣列、物件、== 與 ===

F2E合作社|分頁導覽列|Bootstrap 5網頁框架開發入門

F2E合作社|分頁導覽列|Bootstrap 5網頁框架開發入門

重新回歸學習程式 - part 1  20230308

重新回歸學習程式 - part 1 20230308


Comments