TinyURL

──────────────────────────────────────────────────────────────────────

這題的架構其實很單純，一張表、兩個 endpoint 就結束了，所以整題的重量幾乎都壓在同一個地方：短碼要怎麼產生。難的不是產生本身，是要同時滿足唯一、夠短、而且產生的時候不能太慢，這三件事互相拉扯。

Functional and Non-Functional Requirements

功能上只有兩件事：把一個長網址換成短網址，以及用短碼把使用者導回原本的網址。有餘力再談自訂別名和過期時間。

非功能的部分，讀遠遠多於寫，一個短碼寫一次可能被點幾萬次，所以導向那條路徑要快。短碼必須唯一，這是正確性不是效能，撞到就是把使用者送到別人的網址去。

Data Model

一張表就夠了：

欄位	說明
short_code	短碼，或使用者自訂的別名，主鍵
original_url	原始網址
created_at	建立時間
expires_at	過期時間，可選
created_by	誰建的

short_code 上一定要有唯一性約束，後面會講為什麼那不只是保險，而是整個 hash 做法能運作的前提。

API / Access Pattern

寫入是 POST /urls，帶著長網址，回傳短碼。讀取是 GET /{short_code}，查到原始網址之後回一個 302 導向。

用 302 而不是 301 是有理由的。301 是永久轉址，瀏覽器會把它快取起來，之後使用者再點同一個短網址就不會回到你的伺服器，那你既拿不到點擊數，也沒辦法之後改掉這個短碼指向的目標。

Deep Dive：短碼怎麼產生

有兩條路：一條靠隨機性讓碰撞機率夠低，另一條靠建構讓碰撞根本不可能發生。

做法一：hash 之後截斷

把長網址丟進 SHA-256，把輸出用 base62 編碼，取前 8 個字元當短碼。

hash 之前要先正規化網址，把主機名轉小寫、拿掉預設的 port、統一結尾的斜線，不然同一個網址寫法不同就會拿到不同的短碼。

這個做法的特點是它是決定性的，同一個長網址永遠得到同一個短碼。這件事是好是壞要看需求：好處是自動去重，而且不用查資料庫就知道某個網址的短碼是什麼；壞處是如果你希望同一個網址可以有多個短碼（例如不同活動要分開統計），或是不希望別人能猜出某個網址的短碼，那決定性就變成問題，這時候要在 hash 裡混一把祕密的 salt，也就是 HMAC。

這裡有一個常見的說法要修正。很多文章會說「隨機數的熵不夠所以要用 hash」，那是錯的。8 個字元的 base62 就是 47.6 bits，不管你是用 CSPRNG 直接產 8 個字元，還是把 SHA-256 截斷成 8 個字元，熵一模一樣，碰撞行為也一模一樣。兩者真正的差別不是熵，是決定性。

做法二：計數器加 base62

每來一個新網址就把一個計數器加一，再把這個數字用 base62 編碼。因為每個計數器值都不一樣，所以碰撞這件事在建構上就不可能發生，不需要任何檢查。

計數器通常放在 Redis，因為它是單執行緒的，INCR 是原子操作，兩個同時進來的請求一定會拿到不同的值，一個拿到 1000 另一個就是 1001。

代價有兩個。第一是在分散式環境下，所有的伺服器都要跟同一個計數器講話，這是單點也是瓶頸，要擴展就得再想辦法（發號段、多個計數器各自負責不同的餘數之類的）。第二是連號的短碼可以被列舉，有人可以從 0 一路試上去把所有網址挖出來，如果在意的話就在 base62 之前先做一次可逆的變換，例如跟一把祕密金鑰做 XOR。

連號會洩漏規模、隨機不會但可能撞，這個取捨跟主鍵要選自增整數還是 UUID 是同一題，可以參考 Encoding、Hashing、Encryption 裡 UUID 那一節。

碰撞到底多容易發生

如果選了 hash 那條路，這是最值得算清楚的地方，因為直覺會騙人。

8 個字元的 base62 有 ${62}^8\approx 2.18\times {10}^{14}$ 種可能，聽起來完全不用擔心。但那是空間大小，不是你會不會撞到。真正該問的是生日問題：存到幾筆的時候，其中「任意兩筆」撞在一起的機率會過半。

短碼長度	空間	存到幾筆會有 50% 機率出現碰撞
6 字元	$5.7\times {10}^{10}$	約 28 萬
7 字元	$3.5\times {10}^{12}$	約 220 萬
8 字元	$2.2\times {10}^{14}$	約 1740 萬
10 字元	$8.4\times {10}^{17}$	約 10.8 億

8 個字元的空間有兩百兆，但一千七百多萬筆就會開始撞，中間差了七個數量級。所以碰撞不是罕見意外，是規模一上來就必然發生的常態。

那要怎麼處理？靠資料庫。short_code 上放唯一性約束，寫入撞到就重試，重試的時候在 hash 裡加一個隨機的 salt 換一個結果，重試次數要設上限（三到五次），超過就當作失敗回錯誤而不是無限迴圈。

也可以看單筆的角度：已經存了 $n$ 筆時，下一筆撞到的機率大約是 $n/|S|$。以 8 字元、已存十億筆來說大約是 $4.6\times {10}^{-6}$，也就是每二十幾萬次寫入會撞一次。單看很小，但那代表重試這條路徑一定會被走到，不能當成不會發生的例外來寫。

為什麼是 base62

因為 base64 的 + 和 / 不能用在網址裡，/ 是路徑分隔符，+ 在 query string 會被解讀成空白。拿掉這兩個字元就是 base62。

而且這個取捨幾乎不用付代價，base62 和 base64 的長度差不多（每個 byte 分別是 1.344 和 1.333 個字元）。詳細的比較在 Encoding、Hashing、Encryption。

短碼要幾個字元

計數器那條路可以直接反算。十億筆網址用 base62 編出來是 15ftgG，六個字元。到 ${62}^6$ 也就是大約 568 億筆才需要進位到七個字元，而七個字元可以裝三兆五千億筆。所以就算做到很大，短碼也還是很短。

hash 那條路不能這樣算，要用上面那張生日表回推。想撐到十億筆而且不要一直重試的話，八個字元是不夠的，得往十個字元走，或者接受重試並且把唯一性約束做好。

這其實是兩條路最實際的差別：計數器的長度隨資料量緩慢成長而且可以精準預測，hash 的長度必須一開始就照最終規模抓好，抓小了就得一直重試。

Deep Dive：導向要怎麼變快

導向這條路徑就是拿短碼查原始網址，所以整段是一連串越推越前面的快取：先讓資料庫查得快，再讓大部分請求不用碰資料庫，最後讓大部分請求連伺服器都不用碰。

先加索引

沒有索引的話，查一個短碼要掃過整張表。加上索引之後資料庫可以用二分的方式找，B-tree 索引是 $O(\log n)$，幾億筆也只是十幾次比較的事。

更直接的做法是把 short_code 設成主鍵，這樣索引和唯一性約束一次拿到，而唯一性約束正是前面 hash 那條路重試機制的靠山。

這裡有一個跟前一節扣起來的細節。如果 short_code 是主鍵，那短碼是怎麼產生的就會影響寫入效能：hash 產出來的碼是隨機的，每次插入都落在索引的隨機位置，會造成頁面分裂；計數器產出來的碼是遞增的，永遠插在尾端。這跟主鍵選 UUID v4 還是 v7 是完全一樣的問題，Encoding、Hashing、Encryption 那篇的 UUID 那節有寫。

流量算一下

索引解決的是「一次查詢要多久」，但沒有解決「一秒要查幾次」。

假設 100M DAU、每人每天點 5 次，就是每天 5 億次導向，平均下來大約 5,800 QPS。但流量不會平均分布在一天之內，尖峰要另外抓。原文抓 100 倍變成大約 58 萬 QPS，那是很保守的抓法，實務上尖峰對平均大概是 2 到 10 倍，也就是 1.2 萬到 5.8 萬 QPS。真正的數字要看你的使用情境，但無論抓哪一個，單一台資料庫都會很吃力。

加一層記憶體快取

在應用伺服器和資料庫之間放一層 Redis 或 Memcached，key 是短碼、value 是原始網址。請求進來先查快取，命中就直接回，沒命中才查資料庫，查完再寫回快取。

會有效是因為這件事本質上是把磁碟換成記憶體：

	存取時間	大約能撐多少次讀取
記憶體	100 ns	每秒數百萬
SSD	0.1 ms	約 10 萬 IOPS
HDD	10 ms	約 100 到 200 IOPS

記憶體比 SSD 快一千倍，比 HDD 快十萬倍。這幾個數字在 Jeff Dean Numbers 那篇有更完整的表。

而且短網址的存取分布非常偏，少數幾個熱門連結佔掉絕大部分流量，這正是快取最有利的形狀。

代價的部分，快取失效在這題其實不太痛，因為短碼幾乎不會被改；比較實際的是冷啟動時要一段時間才會熱起來，以及記憶體有限所以要決定容量和淘汰策略，一般用 LRU。

再往前推到 CDN 邊緣

還可以更前面。把短網址的網域掛在 CDN 上，讓各地的 PoP 快取短碼到原始網址的對應，再用 Cloudflare Workers 或 Lambda@Edge 這種邊緣運算把導向邏輯本身也放上去。

這樣熱門的短碼在離使用者最近的節點就被導走了，根本不會回到你的伺服器。省下來的不只是查詢時間，還有一整段跨洲的往返。

代價是快取要在全球所有節點之間保持一致會變複雜、邊緣函式在執行時間和可用套件上有限制、成本會上升，而且分散在各地的環境要 debug 和監控比集中式難得多。這一段是拿成本和複雜度換延遲，值不值得要看流量規模和對使用者體驗的要求。

Deep Dive：怎麼撐到 10 億筆網址、100M DAU

讀取那邊在上一節已經處理掉大半了，這節主要是寫入和整體規模。

資料量其實不大

一列大概是短碼 8 bytes、原始網址 100 bytes、建立時間 8 bytes、自訂別名 100 bytes、過期時間 8 bytes，加起來約 200 bytes。抓寬一點算 500 bytes 好留給其他 metadata。

10 億筆就是 500 GB。這個量對現代 SSD 來說完全不成問題，單一台 Postgres 就裝得下。而且網址總數的成長是有上限的，不會無限膨脹，真的撞到硬體天花板再考慮分片就好。

那該用什麼資料庫

寫入量比想像中低很多。假設每天新增 10 萬筆網址，那是每秒 1.16 筆。跟讀取那邊的 5,800 QPS 相比，讀寫比大約是 5000 比 1。

所以重的讀取已經被快取吸走，剩下的寫入又只有每秒一筆多，這種負載幾乎任何資料庫都做得到。面試的時候挑你最熟的講就好，沒有經驗的話選 Postgres。

這題真正的重點是能講出「為什麼這裡不需要特別的選型」，而不是背出一個聽起來很厲害的答案。

資料庫掛掉怎麼辦

複製是最直接的作法，用支援 replication 的資料庫做出幾份一模一樣的複本放在不同機器，一台掛了就導到另一台。代價是應用端要能處理任何一個複本，包括複製延遲造成的讀取不一致。

另外還是要有定期備份放在別的地方，複製防的是機器掛掉，備份防的是資料被寫壞或被誤刪，兩者防的不是同一件事。

讀寫分開擴展

既然讀寫比是 5000 比 1，把它們拆成兩個服務就很自然：Read Service 負責導向，Write Service 負責建立短網址，各自照自己的需求水平擴展。導向那邊可能要幾十台，建立那邊一兩台就夠了。

但計數器只有一個

如果短碼是用計數器產生的，水平擴展 Write Service 馬上會踩到一個問題：所有的實例都必須對「下一個號碼是多少」有共識，否則就會發出重複的短碼。

作法是把計數器放在一個集中的 Redis，INCR 是原子的，兩個同時進來的請求一定拿到不同的值。

那多一次網路往返會不會太慢？其實不會，網路往返跟其他步驟比起來根本不算什麼。真的在意的話可以用批次領號：每個 Write Service 實例一次跟 Redis 要一批（例如 1000 個），Redis 一次把計數器加 1000 然後回傳這批的起點，實例就在本地用完這 1000 個再回去要下一批。

批次領號的副作用是號碼不再嚴格按時間順序發出，因為 A 實例手上握著 1000 到 1999 的時候，B 實例可能已經在用 2000 之後的號碼了。這題不在意這件事，但如果你的設計有依賴短碼的先後順序就要注意。

計數器自己掛了呢

用 Redis Sentinel 或 Redis Cluster 做自動故障轉移。單一台 Redis 就能撐每秒十萬次以上的操作，遠遠超過這題的寫入量，配上批次領號更是綽綽有餘。

萬一 Redis 在複製最新的計數器值之前就掛了，可能會少掉幾個號碼，但這沒關係，我們要的是唯一而不是連續，跳號無所謂。而且資料庫上 short_code 的唯一性約束是最後一道保險。

跨區

多區域部署的時候不要讓兩個區域去搶同一個計數器，直接把號碼空間切開，例如 A 區用 0 到 10 億、B 區用 10 億到 20 億，這樣寫入都打在自己區域的 Redis，完全不用跨區協調。讀取那邊本來就靠分散式快取在各地服務，不受影響。