System Design - Short URL System

用途與需求

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
• 資安