System Design Interview · 第 8 章Triton 覆蓋度:🟡 中Triton 線
Design A URL Shortener
把一件大衣換成一張號碼牌
原書設計一個像 tinyurl 的服務:長網址換成 7 個字元的短碼,點下去再導回原網址。重點是 301 還是 302、hash 還是 base 62。Triton 沒有寫過短網址專文,但他對這章用到的每一塊都有話說:status code 要跟好,CDN 才能幫你擋讀取;流水號 ID 會讓對手數出你的業務量。
給文組
全程只用「餐廳寄物處的號碼牌」,一階一階爬 12 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
第 4–30 頁完整講原書(8 張圖全部重繪),後面是 Triton 的觀點,最後一頁列出所有出處(materials/core)。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📅 2026 補充
先用生活理解寄物處
大衣太大帶不進去,換一張號碼牌
餐廳門口的寄物處:你把一件很佔位子的大衣交出去,拿回一張小小的號碼牌。吃完飯拿號碼牌回來,櫃台把同一件大衣還給你。
這一章的比喻
- 大衣 = 長網址
https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long - 號碼牌 = 短網址
tinyurl.com/y7keocwj - 拿牌換大衣 = redirect:點短網址,被送回長網址
- 號碼牌怎麼編 = 這章的核心:hash 還是流水號
動手玩:號碼牌要怎麼編?
先選「流水號」按「隔壁同業來寄兩次」,再換「隨機號碼」比較。答案在第 35 頁。
學習地圖本章的概念階梯
今天爬 12 階。每一階只用前面講過的東西。
- 1QPS每秒收幾件
- 2API寄放、領回兩個窗口
- 3redirect「去 3 號櫃拿」
- 4cache / CDN抄在手背上
- 5hash table登記簿
- 6hash function文字的指紋
- 7base 6262 個符號排列
- 8collision生日撞日
- 9bloom filter打洞卡
- 10auto-increment1、2、3 流水號
- 11atomic查和寫一口氣做完
- 12TTL / stampede小抄過期那一刻
第 1–4 階 · 寄放與領回
要回答:點一下短網址,發生了什麼事?
第 5–7 階 · 號碼牌怎麼編
要回答:為什麼 7 個字就夠用十年?
第 8–10 階 · 兩種編法的代價
要回答:會撞號、會被猜,各怎麼辦?
第 11–12 階 · Triton 的追問
要回答:兩人同時來、一萬人同時來,撐得住嗎?
全程只用一個情境:餐廳門口的寄物處
數學只用乘法、開根號和「數有幾個零」。每爬 3–4 階,有一頁「到這裡你已經會了」。
原書 Step 1理解問題、確立設計範圍
面試一開始:先問清楚要做多大的寄物處
這一步要解決的問題要做多大?號碼牌要多短、能寫哪些字?沒問清楚,後面每個數字都會算錯。
| 應徵者問 | 面試官答 |
|---|---|
| 可以舉個例子說明 URL shortener 怎麼運作嗎? | 原始網址 https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long,服務產生一個比較短的別名 https://tinyurl.com/y7keocwj。點別名,就被導回原網址。 |
| 流量多大? | 每天產生 1 億個 URL |
| 短網址要多短? | 越短越好 |
| 短網址可以用哪些字元? | 數字 0-9 和字母 a-z、A-Z |
| 短網址可以刪除或更新嗎? | 為了簡化,假設不能刪除、不能更新 |
📖 原書 系統設計面試題故意是開放式的,問澄清問題是關鍵。
📖 原書 基本使用案例
- URL shortening:給一個長 URL → 回傳短很多的 URL
- URL redirecting:給一個短 URL → 導向原始 URL
- 高可用、可擴展、容錯(high availability, scalability, fault tolerance)
白話:alias=別名;high availability=隨時都能用;scalability=人變多也撐得住;fault tolerance=壞掉一台不會全倒。
寄物處版:一天收 1 億件大衣;號碼牌越小越好;號碼只能寫數字和英文字母;寄了就不能換、也不能取消。
🗣️ Triton 「不能刪除」這個假設,第 34 頁會看到它對 HTTP status code 的影響(404 還是 410)。
延伸基礎第 1 階 · QPS懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
一天收 1 億件大衣,櫃台每秒要收幾件?
① 先想像
寄物處從早開到晚。要知道櫃台忙不忙,得把「一天幾件」換成「每秒幾件」。
你猜猜看:一天約 10 萬秒(86,400)。一天收 1 億件,平均每秒大約幾件?
1 億有 8 個零,10 萬有 5 個零,相除剩 3 個零:1,000。精算是 1,157,原書寫 1160。
③ 這叫做 QPS、storage
QPS:每秒進來幾個 request。storage:存了幾年之後,倉庫要多大。
④ 跟這章的關係
下一頁原書就用這兩個數字估規模。完整的估算法在 第 2 章簡報第 23–25 頁。
② 動手玩:一天收幾件?
一件大衣只寄一次,卻可能被領很多次:一個短網址貼出去,被點上千次。所以「讀」比「寫」多。
原書 Step 1Back of the envelope estimation
一天 1 億個網址,十年要存多少?
這一步要解決的問題寫多少、讀多少、存多少?這三個數字決定後面要不要 cache、要不要資料庫。
📖 原書 估算
- 寫入:每天產生 1 億個 URL
- 每秒寫入:100 million / 24 / 3600 = 1160
- 讀取:假設讀寫比 10 : 1,每秒讀取 1160 × 10 = 11,600
- 服務跑 10 年:100 million × 365 × 10 = 365 billion 筆紀錄
- 假設平均 URL 長度 100
- 10 年的儲存:365 billion × 100 bytes = 36.5 TB
白話:100 million=1 億;365 billion=3650 億;byte=存一個英文字母的空間;TB=一兆 bytes。
「和面試官一起走過假設與計算,讓雙方對齊」很重要。
動手算:改一個假設看看
延伸基礎第 2 階 · API懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
寄物處只開兩個窗口:寄放、領回
① 先想像
寄放窗口:交出大衣,拿回號碼牌。領回窗口:交出號碼牌,拿回大衣。
你猜猜看:到「領回」窗口,你要交給櫃台什麼?
領回時你手上只有號碼牌,櫃台靠它找到大衣。點短網址也一樣:你只給它短短幾個字。
③ 這叫做 API、POST / GET
API:店家公開的窗口和規矩。POST:「我要交東西給你」;GET:「我要拿東西」。
④ 跟這章的關係
原書的短網址服務就只有這兩支 API(下一頁)。request 是什麼,見 第 4 章簡報第 4 頁。
② 動手玩:走到哪個窗口?
下面那格是電腦版的寫法(示意)。
原書 Step 2Propose high-level design · API endpoints
只要兩支 API:一支寄放、一支領回
這一步要解決的問題客人和伺服器要用什麼格式溝通?寄放和領回各要帶什麼?
📖 原書 本節討論 API endpoints、URL redirecting 和 URL shortening 流程。API endpoints 讓 client 和 server 溝通;原書用 REST 風格設計(不熟 RESTful API 可以看參考資料 [1])。
白話:REST=用網址指名「哪個東西」、用 POST / GET 說「要做什麼」的一套寫法;parameter=隨 request 一起交出去的資料。
1 · URL shortening
client 發 POST,只帶一個參數:原始長網址。
POST api/v1/data/shorten
- request parameter: {longUrl: longURLString}
- return: shortURL
2 · URL redirecting
client 發 GET,把短網址導回對應的長網址。
GET api/v1/shortUrl - return: longURL for HTTP redirection
寄物處版
POST = 把大衣交給櫃台,拿回號碼牌。GET = 拿號碼牌回來,櫃台指給你大衣在哪。
動手玩:送一個 request
回應的格式是本簡報依原書內文補的示意(原書只寫 return shortURL / longURL)。
🗣️ Triton 他對 URL 裡的動詞 shorten 有意見,見第 34 頁。
延伸基礎第 3 階 · redirect懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
櫃台不遞大衣給你,而是說「在 3 號櫃,自己去拿」
① 先想像
你交出號碼牌。櫃台回你一張紙條:上面一個三位數號碼,和一句「去 3 號櫃拿」。
你猜猜看:紙條寫「永久搬到 3 號櫃」。下次你還要先排隊問櫃台嗎?
「永久」就是以後都在那裡。你記住了,櫃台輕鬆了,但櫃台也不知道你又來過。
③ 這叫做 status code、redirect
status code:回覆紙條上的三位數號碼。redirect:回你「去別處拿」,新地址寫在 location。
④ 跟這章的關係
下一頁原書的 Figure 1 就是一張 301 紙條;再下一頁比較 301 和 302。
② 動手玩:櫃台可能回你的四種紙條
status code 在 第 4 章簡報第 7 頁介紹過(200、429、503)。
原書 Step 2URL redirecting · Figure 1–2
點下短網址的那一瞬間發生了什麼
這一步要解決的問題短網址服務手上沒有網頁,要怎麼叫瀏覽器自己去長網址那邊拿?
📖 原書 Figure 1 是在瀏覽器輸入 tinyurl 時看到的東西:server 收到 tinyurl request 後,用 301 redirect 把短網址換成長網址。
- Client 造訪短網址
https://tinyurl.com/qtj5opu - tinyurl server 回 status code 301,
locationheader 放長網址 - Client 自動跟著 redirect,去 Amazon server 造訪長網址
重點只有兩個 header
Status Code: 301:告訴瀏覽器「這個網址搬家了」。
location:新家地址 https://www.amazon.com/dp/B017V4NTFA?pLink=63eaef76-979c-4d&ref=adblp13nvvxx_0_2_im
白話:header=回覆單最上面那幾行小標籤;Cloudflare=一家賣 CDN 的公司(CDN 見第 11 頁)。
🔭 注意圖上的 cf-ray、cf-cache-status:這個 response 經過 Cloudflare。CDN 擋在短網址服務前面,第 33 頁會用到。
延伸基礎 · 複習第 4 階 · cache / CDN懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
把「3 號櫃」抄在手背上,或請巷口分店代答
① 先想像
你常來,乾脆把「大衣在 3 號櫃」抄在手背上,下次直接走過去。
你猜猜看:抄在手背之後,你又來了 5 次。櫃台總共被你問了幾次?
只有第一次問過,之後都看手背。櫃台輕鬆,但也數不到你來了幾次:這就是 301 的取捨。
③ 這叫做 cache、CDN
cache:手邊的小抄,拿得快,正本在別處。CDN:開在客人附近的分店,替總店回答大家都一樣的問題。
④ 跟這章的關係
301 等於叫瀏覽器自己 cache(下一頁)。完整版見第 1 章簡報 cache(第 18 頁)、CDN(第 21 頁)。
② 動手玩:誰來回答「大衣在哪」?
原書 Step 2301 redirect vs 302 redirect
301 省伺服器,302 留得住點擊數據
這一步要解決的問題同一個短網址被點一萬次,伺服器要接一萬次嗎?少接幾次,又會少知道什麼?
📖 原書 301:「永久」搬家
請求的 URL 被「永久」移到長網址。因為是永久的,瀏覽器會快取這個回應,之後同一個 URL 的 request 不會再送到短網址服務,而是直接去長網址的 server。
📖 原書 302:「暫時」搬家
URL「暫時」移到長網址,之後同一個 URL 的 request 還是會先送到短網址服務,再被導到長網址的 server。
📖 原書 怎麼選
各有優缺點。優先減輕 server 負載 → 301,因為同一個 URL 只有第一次 request 會到短網址 server。重視分析(analytics)→ 302,比較容易追蹤點擊率和點擊來源。
白話:analytics=點擊統計:誰、什麼時候、從哪裡點了連結。
動手玩:同一個短網址點十次
到這裡你已經會了小結 1 / 4
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
到這裡你已經會了:點一下短網址,發生了什麼事
- 一天 1 億個網址 ≈ 每秒寫入 1,160、讀取 11,600(QPS);十年要存 36.5 TB。
- 整個服務只有兩支 API:POST 寄放長網址、GET 用短網址領回。
- 領回時伺服器回 redirect:301 讓瀏覽器 cache,省力但數不到點擊;302 每次都回來問。
下一階要解決的問題
號碼牌要怎麼編?先看櫃台怎麼用號碼牌找到大衣:一本登記簿。
延伸基礎第 5 階 · hash table懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
給一個號碼,直接翻到那一格
① 先想像
櫃台有一本登記簿:左欄號碼牌、右欄大衣在哪。客人遞號碼來,櫃台要找到那一行。
你猜猜看:登記簿 1 萬行,沒照號碼排好。最壞要翻幾行才找到?
沒排好只能從頭翻,最壞翻到最後一行。照號碼分格放好,伸手就到:這就是 hash table。
③ 這叫做 hash table、key / value
hash table:「key → value」的對照表,給 key 一次就找到。key 是號碼牌,value 是大衣在哪。
④ 跟這章的關係
原書的 redirect 就是 hashTable.get(shortURL)。表大到記憶體放不下,就改放 database(第 1 章第 8 頁)。
② 動手玩:找一張號碼牌
延伸基礎第 6 階 · hash function懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
每一段文字,都有自己的「指紋」
① 先想像
一台蓋章機:任何一段文字放進去,都蓋出一串 8 個字的指紋。同一段文字,每次蓋出來都一樣。
你猜猜看:長網址只改了一個字母,指紋會?
好的指紋公式,差一點點就整串大變。所以也沒辦法從指紋倒推回原文。右邊改一個字試試。
③ 這叫做 hash function、hash value
hash function:把任意長的文字壓成固定長度指紋的公式。hash value:蓋出來的那串指紋。
④ 跟這章的關係
原書的 ƒ(x) 就是它(下一頁)。這裡用 CRC32;原書 Table 2 還有 MD5、SHA-1。
② 動手玩:蓋一個指紋
原書 Step 2Hash table · URL shortening · Figure 3
最直覺的做法:一張 hash table 加一個 f(x)
這一步要解決的問題領回時,怎麼用號碼牌找到大衣?寄放時,號碼牌從哪裡來?
📖 原書 Redirect 用 hash table
hash table 存 <shortURL, longURL> 配對,redirect 就是:
longURL = hashTable.get(shortURL) // 拿到 longURL 之後,做 URL redirect
📖 原書 Shortening 要一個 hash function
假設短網址長這樣:www.tinyurl.com/{hashValue}。要找到一個 hash function fx,把長網址對應到 hashValue。它必須滿足:
- 每個 longURL 都要 hash 成一個 hashValue
- 每個 hashValue 都要能對應回 longURL
hash function 的細節在 deep dive(第 19–27 頁)。
原書 Step 3Design deep dive · Data model · Figure 4
記憶體放不下,就放進關聯式資料庫
這一步要解決的問題3650 億筆對照,全放在記憶體裡的 hash table,放得下嗎?
📖 原書 Deep dive 要談四件事:資料模型、hash function、URL shortening、URL redirecting。
📖 原書 為什麼不只用 hash table
高階設計把所有東西放在 hash table,是好的起點;但真實系統的記憶體有限而且貴,不可行。比較好的做法是把 <shortURL, longURL> 對應存在關聯式資料庫。簡化版的表只有 3 個欄位:id、shortURL、longURL。
白話:記憶體(RAM)=桌上攤開的白板,快但貴、斷電就沒;關聯式資料庫(RDBMS)=資料排成一張張表格、存在硬碟的帳本;PK(primary key)=每一行獨一無二的編號。
動手算:36.5 TB 全放記憶體要幾台?
只算第 6 頁的 36.5 TB 長網址本身,不含 hash table 的額外開銷與 replica。
寄物處版:櫃台的腦袋記不住一億件大衣放哪,所以準備一本登記簿,每一行寫「流水號、號碼牌、大衣是哪一件」。
🗣️ Triton 「不能不見的data,我一定存到RDBMS」,見第 42 頁。
延伸基礎第 7 階 · base 62懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
每一格有 62 種寫法,7 格排得出幾種號碼?
① 先想像
行李箱的密碼鎖,每一格轉盤是 0–9。1 格有 10 種,2 格有 100 種。
你猜猜看:每格 0–9 的密碼鎖,3 格有幾種組合?
每多一格,種類就乘 10:10 × 10 × 10 = 1,000。不是加,是乘。
③ 這叫做 base 62、62ⁿ
base 62:每一格用 62 種符號寫數字(0–9、a–z、A–Z)。62ⁿ:n 格總共排得出幾種。
④ 跟這章的關係
下一頁原書的 Table 1,就是在找「幾格才排得下 3650 億個網址」。
② 動手玩:號碼牌有幾格、每格幾種符號
原書 Step 3Hash function · Hash value length · Table 1
62 個字元,要幾位才裝得下 3650 億?
這一步要解決的問題號碼牌越短越好,但最少要幾格,才夠十年用?
📖 原書 Table 1 hashValue 長度與可支援的 URL 數
📖 原書 hashValue 由 [0-9, a-z, A-Z] 組成,共 10 + 26 + 26 = 62 個字元。找最小的 n 讓 62n ≥ 365 billion。n = 7 時約 3.5 trillion,遠超過 3650 億,所以 hashValue 長度是 7。
動手算:62n 計算機
7
原書預設:每天 1 億、10 年 = 3650 億筆。切到 hex 看看:第 22 頁「取 hash 值前 7 個字元」的空間其實是 167。
到這裡你已經會了小結 2 / 4
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
到這裡你已經會了:號碼牌要編幾格
- 登記簿就是 hash table:給 key 一次查到 value。3650 億筆放不進記憶體,就改放 database。
- hash function 把長網址蓋成固定長度的指紋:同一段文字永遠同一串,改一個字就整串變。
- 每格 62 種符號(base 62),7 格 = 62⁷ ≈ 3.5 兆種,裝得下十年的 3650 億。
下一階要解決的問題
指紋太長,砍成 7 個字。砍短之後,兩件大衣會不會拿到同一個號碼?
延伸基礎第 8 階 · collision懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
班上 23 個人,就很可能有兩人同一天生日
① 先想像
一年有 365 天。班上同學越多,越可能有兩個人同一天生日。
你猜猜看:至少要幾個人,「有兩人同一天生日」的機會就超過一半?
不是比「你和我」,是任何兩人都算。23 人可以配出 253 對,每一對都有機會撞。
③ 這叫做 hash collision、生日問題
hash collision:兩件不同的大衣拿到同一個號碼。生日問題:號碼種類「開根號」那麼多件,就差不多會撞。
④ 跟這章的關係
原書做法一把指紋砍成 7 個字,一定會撞,所以要「撞到就重來」(下一頁)。
② 動手玩:抽一班看看
換成號碼牌:號碼有 N 種,大約寄幾件就有一半機會撞?
原書 Step 3Hash + collision resolution · Table 2 · Figure 5
做法一:拿現成 hash,砍到 7 個字,撞到就重來
這一步要解決的問題現成的指紋太長;砍成 7 個字一定會撞號(第 21 頁),撞了怎麼辦?
算一下(原書沒寫):Table 2 的值是 16 進位。取前 7 個 hex 字元只有 167 = 268,435,456 種,裝不下 3650 億;要用滿第 19 頁的 627,得先把 hash 值轉成 base 62 再取 7 位。
📖 原書 Table 2 三種 hash 的結果
輸入:https://en.wikipedia.org/wiki/Systems_design
| Hash function | Hash value (Hexadecimal) |
|---|---|
| CRC32 | 5cb54054 |
| MD5 | 5a62509a84df9ee03fe1230b9df8b84e |
| SHA-1 | 0eeae7916c06853901d9ccbefbfcaf4de57ed85b |
📖 原書 用 CRC32、MD5、SHA-1 這類知名 hash,最短的 CRC32 也超過 7 個字元。第一種縮短法:取前 7 個字元,但會 hash collision。解法:遞迴地附加一個預先定義的字串,直到不再碰撞。
📖 原書 這能消除碰撞,但每個 request 都查一次 DB 確認 shortURL 存不存在很貴。Bloom filter(參考資料 [2])可以改善:一種省空間的機率性技術,用來測試一個元素是不是集合的成員。
延伸基礎第 9 階 · bloom filter懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
一張打洞卡:只會說「一定沒有」或「可能有」
① 先想像
每發一個號碼,櫃台用公式算出卡上 2 個格子,各打一個洞。卡很小,放得進口袋,不用翻厚厚的登記簿。
你猜猜看:查一個新號碼,它的 2 個格子有 1 個沒打洞。這個號碼?
發過的號碼,兩格一定都打過洞。只要有一格沒洞,就一定沒發過,不用翻登記簿。
③ 這叫做 bloom filter、false positive
bloom filter:只會答「一定沒有」或「可能有」的打洞卡。false positive(誤報):卡說可能有,翻了登記簿才發現沒有。
④ 跟這章的關係
原書用它減少「查 DB 看號碼用過沒」的次數。下一頁用 509 格的大卡實際跑一次。
② 動手玩:16 格的打洞卡,每個號碼打 2 個洞
原書 · 動手玩截短的 hash 會撞 · bloom filter 幫你少查 DB
號碼牌只剩 3 位,很快就會兩件大衣同號
這一步要解決的問題截得越短越容易撞;每次都翻登記簿確認又太慢。打洞卡能省掉幾次?
Bloom filter:m = 509 個 bit、k = 3
文組版
Bloom filter 是櫃台口袋裡一張打洞卡:每發一張號碼牌,就在卡上 3 個位置打洞。新號碼要發之前先看卡:3 個洞有一個沒打 → 這號碼一定沒發過,不用翻登記簿;3 個洞都打了 → 「可能發過」,才去翻登記簿確認。
模擬規則:照 Figure 5,撞到就在 longURL 後面附加預先定義的字串 # 再 hash。m 選質數 509 是向第 38 頁 Triton 的設定致敬。
延伸基礎第 10 階 · auto-increment懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
1、2、3……的號碼牌,永遠不會撞
① 先想像
另一種發法:不算指紋,照順序發 1 號、2 號、3 號……永遠不會兩人同號。
你猜猜看:早上你拿到 105 號,晚上再來拿到 1,305 號。今天中間大約寄了幾件?
1,305 − 105 = 1,200。流水號不會撞,但誰拿兩次號碼一減,就知道你生意多好。
③ 這叫做 auto-increment、unique ID generator
auto-increment:資料庫自動發的流水號。unique ID generator:保證不重複的發號機(原書第 7 章)。
④ 跟這章的關係
原書做法二:把流水號換成 base 62(下一頁)。不會撞,但長度會變、猜得到下一張。
② 動手玩:流水號 → base 62 號碼牌
原書 Step 3Base 62 conversion · Figure 6
做法二:把流水號 ID 換成 62 進位
這一步要解決的問題不算指紋了,改用流水號:怎麼把 11157 這種數字寫成 62 進位的號碼牌?
📖 原書 進位轉換把同一個數字換成另一種表示法。hashValue 有 62 種字元,所以用 base 62。對應:0-0, …, 9-9, 10-a, 11-b, …, 35-z, 36-A, …, 61-Z。
1115710 = 2 × 622 + 55 × 621 + 59 × 620 = [2, 55, 59] → [2, T, X],短網址是 https://tinyurl.com/2TX。
動手玩:base 62 編碼器
原書 Step 3Comparison of the two approaches · Table 3
兩種號碼牌,各有代價
這一步要解決的問題算指紋(做法一)和流水號(做法二),各自犧牲了什麼?
📖 原書 Table 3
| Hash + collision resolution | Base 62 conversion |
|---|---|
| 短網址長度固定 | 長度不固定,隨 ID 變大而變長 |
| 不需要 unique ID generator | 依賴 unique ID generator |
| 可能碰撞,需要解決 | 不可能碰撞,因為 ID 是唯一的 |
| 猜不出下一個可用的短網址,因為它不依賴 ID | 如果新紀錄的 ID 每次加 1,很容易猜出下一個短網址。這可能是安全疑慮。 |
📖 原書 原書的設計選 base 62 conversion(下一頁)。
動手玩:猜下一張號碼牌
原書例子的 ID 是 2009215674938 → zn9edcu。按「下一位客人」:
寄物處版:流水號的號碼牌,下一位客人拿到幾號你閉著眼都猜得到,把號碼 +1 就能去領別人的大衣。原書把這件事放在表格最後一格輕輕帶過。
🗣️ Triton 他在後端自我檢測題目裡專門問了這件事,見第 35 頁。
原書 Step 3URL shortening deep dive · Figure 7 · Table 4
原書的縮網址流程:先查有沒有,沒有才發新號
這一步要解決的問題新網址進來,一步一步怎麼發號?同一個網址又送來一次怎麼辦?
| id | shortURL | longURL |
|---|
📖 原書 這是系統的核心,希望流程邏輯簡單、能用。設計採用 base 62。
- longURL 是輸入
- 系統檢查 longURL 在不在資料庫
- 在:之前轉過了,從 DB 取出 shortURL 回傳給 client
- 不在:這是新的 longURL,由 unique ID generator 產生新的唯一 ID(primary key)
- 用 base 62 把 ID 轉成 shortURL
- 用 ID、shortURL、longURL 建一筆新的資料庫紀錄
📖 原書 具體例子 · Table 4
longURL https://en.wikipedia.org/wiki/Systems_design,ID generator 回傳 2009215674938,base 62 轉成 zn9edcu,存進 DB(左下表就是 Table 4)。
📖 原書 分散式 unique ID generator
它產生全域唯一的 ID 來做 shortURL。高度分散的環境下很難做,第 7 章「Design A Unique ID Generator in Distributed Systems」討論過幾種解法。
原書 Step 3URL redirecting deep dive · Figure 8
讀比寫多十倍,所以 redirect 前面加一層 cache
這一步要解決的問題每秒 11,600 次領回,怎麼讓它又快、又不把登記簿翻爛?
📖 原書 讀比寫多,所以 <shortURL, longURL> 對應存在 cache 裡提升效能。流程:
- 使用者點短網址
https://tinyurl.com/zn9edcu - Load balancer 把 request 轉給 web servers
- shortURL 已經在 cache:直接回傳 longURL
- 不在 cache:從資料庫拿 longURL。資料庫也沒有,多半是使用者輸入了無效的 shortURL
- 把 longURL 回傳給使用者
白話:load balancer=帶位員,把客人分給不同的櫃台;web server=櫃台人員(第 1 章第 12 頁)。
寄物處版:櫃台桌上放一張「最近常被問的號碼」小抄(cache)。小抄上有就直接回答;沒有才翻登記簿(DB)。登記簿也沒有,就是客人拿了一張假號碼牌。
🗣️ Triton 這個「先查 cache、沒有再查 DB」的寫法,Triton 說在高流量下會出事,見第 40 頁。
原書 Step 4Wrap up · 參考資料
面試還有時間的話:五個可以多聊的點
這一步要解決的問題主體設計完了,面試官常問:還有哪些配套和延伸?
📖 原書 本章談了 API 設計、資料模型、hash function、URL shortening 和 URL redirecting。如果面試最後還有時間:
1 · Rate limiter
惡意使用者可能送超大量的縮網址 request。Rate limiter 依 IP 或其他規則過濾(見第 4 章)。
2 · Web server scaling
Web tier 是 stateless,增減 web server 就能擴展。
3 · Database scaling
Database replication 和 sharding 是常見技術。
4 · Analytics
資料對商業越來越重要。整合分析方案,回答「多少人點了連結?什麼時候點?」
5 · Availability, consistency, reliability
任何大型系統成功的核心,第 1 章「Scale From Zero To Millions Of Users」詳細談過。
白話:stateless=櫃台不記客人,誰去哪個窗口都一樣(第 1 章第 24 頁);replication=把登記簿抄一份到別台(第 14 頁);sharding=登記簿太厚,拆成好幾本(第 34 頁)。
「Congratulations on getting this far! Now give yourself a pat on the back. Good job!」原書的結尾就是這句。
📖 原書 參考資料
[1] A RESTful Tutorial: https://www.restapitutorial.com/index.html
[2] Bloom filter: https://en.wikipedia.org/wiki/Bloom_filter
到這裡你已經會了小結 3 / 4
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
到這裡你已經會了:原書的完整設計
- 截短的指紋一定會撞(collision,生日問題),撞到就加字串重來;bloom filter 幫你少查 DB。
- 流水號(auto-increment)換 base 62 不會撞,但長度會變、猜得到下一張。原書選這個。
- 領回的路:load balancer → web server → cache → DB;寄放的路:先查有沒有,沒有才發新號。
下一階要解決的問題
兩個 request 同一瞬間送來、一萬個 request 同一瞬間點同一個連結,原書的流程撐得住嗎?換 Triton。
換 Triton 上場覆蓋度:中
Triton 沒寫過短網址,但這章每一塊他都講過
| 原書的零件 | Triton 有講的 | 出處 | 頁 |
|---|---|---|---|
| 301 / 302、Figure 1 的 headers | 沒有直接談 301 vs 302;談的是status code 要跟好,CDN 才能只看 header 就決定 cache | 167、146、166 | 33 |
| REST API、無效短碼 | URL 是名詞不是動詞、POST 重送、404 / 410 / 304 | 027、028 | 34 |
| Base 62 of ID、Table 3 的安全疑慮 | auto-increment 會讓競爭對手猜到業務量;auto-inc 的效能與跳號 | 113、010、094 | 35 |
| Figure 5 / 7 的「先查再寫」、bloom filter | atomic check-and-set;他自己在 production 用 bloomfilter 的經驗 | 164、089、011 | 37–38 |
| Figure 8 的 cache | cache stampede 要上鎖再查一次、一定設 TTL、預熱、不可變的資料 | 087、088 | 40–41 |
| Wrap up 五點 | per-IP 限流交給 Cloudflare、stateless AS、先 scale up 再 sharding、統計資料可以掉 | 059、028、106、064、117 | 42 |
🔭 讀法 這章的 Triton 頁面,引號裡的是他的原話(附檔名);把原話套到短網址上的那一步,一律標 🔭。materials/core 裡沒有任何一份 Triton 的文章提到 tinyurl、短網址或 base 62。
Triton 補充status code 不只是給瀏覽器看的
跟好 status code,CDN 才幫得上忙
你猜猜看:短網址服務前面隔了一層 CDN。找不到的短碼也回 200,只在 body 裡寫「not found」。CDN 會怎樣?
CDN 只看 header,200 就是成功;要它看懂 body,每個 request 都得多做一次 parsing。原話在下面。
「跟好response status code當然比較好啊。試想一下如果你的Application server和User之間還隔了一層CDN。 CDN正常應該只去cache成功的request的。如果你是單用response body來存是否成功的,那麼你的CDN就要對你的每一個request都做parsing……而你跟好HTTP status code的,CDN只用看HTTP header部分就好。這其中CDN CPU用量的差別,是差了一整個量級的。」🗣️ Triton 本人說 167-有人問到底要不要跟好http status code.md
「設定好CDN(像是Fastly / cloudflare),設定好你的HTTP header的cache相關的。」🗣️ Triton 146 · C10K 以下應該首先要做的第 1 點
「Write不能用CDN,Read可以。」🗣️ Triton 166-有人問一個系統的server cost要用上多少錢。.md
動手玩:CDN 擋在短網址服務前面
🔭 推論 情境是依 167 的機制演出的示意。最後一個陷阱是 base 62 流水號特有的:今天不存在的短碼,明天會被發出去,CDN 若把今天的「找不到」當成功 cache 起來,明天的新連結就壞了。原書 Figure 1 的 response 正好經過 Cloudflare(cf-ray、cf-cache-status)。
Triton 補充RESTful API 講義對照原書的兩支 API
URL 是名詞,POST 會重送,找不到要說清楚
你猜猜看:有人亂打一個不存在的短碼。原書沒說要回什麼,你覺得該回哪個 status code?
404 就是「這個東西不存在」。回 200,CDN 和瀏覽器都會以為成功了(上一頁)。Triton 的 RESTful 講義寫得更細,見下面第三張卡。
URL 是名詞
「「資源」一定是名詞!」「所有 URL都應該基於物件,而不是行動」「再次強調:所有的 API 一定是名詞/動名詞」🗣️ Triton 本人說 027 / 028-RESTful API Design-tw · 淺談 HTTP 資源、統一介面、API 設計重點
🔭 推論 原書的 POST api/v1/data/shorten 是動詞。照 Triton 的規則會像 POST /v1/shortUrls(建立一個短網址物件,回傳它的 id)。不過 Triton 也說「統一介面…是相對上最死不了人的,別為這吵架太久」。
POST 會重送
「延伸思考:在不穩定網路下,用戶建立一份資源時,卻發出了二次的 POST,怎麼辦?」「雖然原始 HTTP POST 定義是 non-idempotent,但是他沒禁止你自行解決 idempotent 問題」🗣️ Triton 027 / 028 · HTTP method-POST
🔭 推論 原書 Figure 7 第 2 步「longURL in DB?」剛好讓重送拿回同一個短碼,等於順手做了 idempotency。代價是 longURL 也要能查得快(3650 億筆、平均 100 bytes 的另一個 index),而且兩個 request 同時到還是會重複,見第 37 頁。
找不到要說清楚
- 「404(Not Found) – 請求的資源不存在」
- 「410(Gone) – 一個資源曾經存在,但現在不再存在 – 大部份懶人會用 404」028
- 304:「如果客戶端版本是最新的,便回答 304」;「系統內的所有東西都必須定義能否使用快取」「不常變動的物件適合設定為可快取」
🗣️ Triton 本人說 027 / 028 · 常用 HTTP 回答碼、能夠利用快取機制增進性能
🔭 推論 原書第 29 頁只說「多半是無效的 shortURL」,沒說回什麼。照講義:無效短碼回 404;如果哪天允許刪除,被刪的回 410。短網址對應永遠不變,正是「不常變動、適合快取」的那一類。
Triton 補充Table 3 最後一格的「security concern」
流水號換成 base 62,對手還是數得出你的業務量
「15 你知道使用auto-increment,但又不讓競爭對手猜到你的業務量的方法嗎?」🗣️ Triton 本人說 113-喵的 backend 測驗.md · 安全篇(同一份的效能篇第 14 題:「你知道auto-increment在系統效能的隱憂嗎?」)
auto-increment 本身(同一系列的文章)
- 「Auto-Increment的改動是不被包在TX內的」「RDBMS是每次要改動HDD內的auto-increment數值時,都是一次地跳動20個號碼的」「auto-increment沒法保證你的PK是從1開始,中間完全不會跳號碼。」010
- 「auto-inc insert在PK的B+ tree index中,只會動到最右邊的那個leaf node。」「越近期被加入database的資料,就越有可能被拿出來改動。用auto-inc下,所有近期的資料全在PK-index的右邊,所以右邊忙死然後左邊空閒。」094
🗣️ Triton 010-喵談 RDBMS PK Auto-Increment(只引 Triton 本人段落,檔尾「AI」段不引)· 094-triton 談 pg index uuid 與 auto-inc
🔭 推論 短網址的 row 寫了就不改(原書假設不能更新),094 擔心的「近期資料常被改動」在這裡比較不嚴重;010 的跳號只會讓對手的估計有一點點誤差。洩漏業務量才是 base 62 流水號的主要問題。
🔭 推論 113 是題目表,沒有附答案。「打亂」這裡用乘上一個和 627 互質的大數再取餘數,只是示意:知道那個數字就能還原,它擋的是「看號碼就知道」,不是真正的加密。也可以回到原書的做法一(hash),或用隨機短碼加 unique constraint。
你猜猜看:短碼是流水號直接換 base 62。對手今天、明天各建一個連結,把兩個短碼換回數字一減,得到什麼?
base 62 只是換個寫法,換回數字就是流水號。兩個流水號一減,就是中間發出去的號碼數,跟第 25 頁的 105 號、1,305 號一樣。
動手玩:競爭對手的小實驗
延伸基礎第 11 階 · atomic懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
兩位櫃台同時看到「42 號沒人用」
① 先想像
兩位櫃台人員同時翻登記簿,都看到 42 號空著,各自把 42 號發給自己的客人。
你猜猜看:兩人都是「先看、再寫」。最後幾位客人拿到 42 號?
兩人看的時候都還沒人寫。「看」和「寫」中間的空檔被插隊,就是第 4 章講過的 race condition。
③ 這叫做 atomic、unique constraint
atomic:「查」和「寫」一口氣做完,中間沒人能插隊。unique constraint:資料庫規定這一欄不能重複,第二筆直接被拒絕。
④ 跟這章的關係
原書 Figure 5、7 都是「先查再寫」(下一頁)。race condition 完整版見 第 4 章簡報第 26 頁。
② 動手玩:你來決定誰先動
Triton 補充Figure 5 / 7 的「先查再寫」
「先查有沒有,再寫進去」中間有一個縫
你猜猜看:Figure 7 第 2 步「longURL 在 DB 嗎?」。同一個新網址在同一瞬間被送了兩次,結果?
兩個 request 查的時候都還不存在,就各自發了新 ID。上一頁的 42 號,在這裡換成了同一個網址。
動手玩:兩個 request 同時算出同一個 hash
「如果updated record為1,則代表用戶成功保留了這座位,否則他便被同一時間按下「選擇」的用戶Y搶走了票。」「使用了atomic check-and-set來防止race condition」🗣️ Triton 本人說 164 · 戲院售票系統
🔭 推論 把「檢查」和「寫入」合成資料庫的一個原子動作(unique constraint 擋重複),跟 164 用一句 UPDATE … WHERE 搶座位是同一個原則。Figure 7 的「longURL in DB?」也一樣:兩個 request 同時送同一個新網址,會各拿一個 ID。
Triton 補充bloom filter 實戰
Triton 自己在 production 用過 bloomfilter
你猜猜看:短網址的 bloom filter 誤報了一次(卡說「可能有」,其實沒有)。會出什麼事?
卡說「可能有」,櫃台就去翻登記簿確認;翻了發現沒有,照樣可以發。代價只是多查一次。Triton 的說法在右邊。
🔭 推論 在短網址裡,誤報 = 多查一次 DB,不會發錯號碼,符合 089 的「Little false positive doesn't matter」。短網址不能刪除,所以 bloomfilter 沒有過期機制也剛好沒差。多台 server 各有一份時,可以像 089 那樣用 bitwise OR 合併。但記得:原書最後選了 base 62,就根本不需要碰撞檢查,bloom filter 只屬於做法一。
089 · 用 bloomfilter 算 active user
「Test(string s) bool – Test if string s exists – may return false positive」「Little false positive doesn't matter」「Merge use bitwise OR operation on byte array」「Bloomfilter has no “expiration” mechanism」「Algorithm and data structure has practical use – DO NOT SLEEP IN UNIVERSITY COURSES」🗣️ Triton 本人說 089-redis-ratelimit.pdf.md · 用 bloomfilter 算 active user
「我寫bloomfilter時,就直接在config內寫m = 1000003」「但是,你覺得AI會知道這地方是代表需要一個質數嗎」🗣️ Triton 011-喵談 質數 bloomfilter(只引開頭三句;後面的質數與實驗長文是 AI 產生,不引)
延伸基礎第 12 階 · TTL / stampede懂的人可以跳過
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
小抄要定時作廢,作廢的那一刻最危險
① 先想像
櫃台的小抄每 10 分鐘作廢、重抄一次,免得抄錯的一直留著。剛作廢的那一刻,小抄是空的。
你猜猜看:小抄空了,翻登記簿要 5 秒,每秒有 2 位客人來問同一個號碼。幾位會跑去翻登記簿?
第一位還沒抄回來,後面的人看到小抄也是空的,全都跑去翻:5 秒 × 每秒 2 位 = 10 位。
③ 這叫做 TTL、cache stampede
TTL(time to live):小抄放多久就自動作廢。cache stampede:小抄剛作廢,一大群 request 一窩蜂衝進 DB。
④ 跟這章的關係
原書 Figure 8 的 cache 沒提這兩件事。Triton 的寫法在下一頁:第一位上鎖,其他人等一下再看小抄。
② 動手玩:小抄作廢的那一刻
Triton 補充Figure 8 的 cache 在爆紅連結下
一個連結爆紅、cache 剛好過期的那 80 毫秒
你猜猜看:一個爆紅連結每秒被點 1000 次,cache 剛好過期,DB 回應要 80ms。照原書的寫法,幾個 request 會衝進 DB?
跟第 39 頁一樣相乘:每秒 1000 個 × 0.08 秒 = 80 個。Triton 的原話在下面。
原書的寫法 = Triton 說的「一般」caching
「1 從 Redis拿資料X;如有則直接回傳 2 從主資料拿資料X 3 把資料X放回 Redis 4 把資料X回傳 … 如果資料X的 QPS是 1000…… 如果主資料庫需要 80ms回傳資料X,那麼便有 80個 request進了主資料庫」🗣️ Triton 本人說 087-redis-2019.pdf.md · 第 12–13 頁
「2 拿到資料X的鎖(在離開時釋放)3 再次從 Redis拿資料X;如有則直接回傳」🗣️ Triton 087 · 第 14 頁「高流量下的 caching」
動手算:cache miss 那一刻有幾個 request 衝進 DB
Triton 補充Figure 8 的 cache · 其他提醒
對應永遠不變,cache 還是要設 TTL
你猜猜看:原書假設短網址不能更新、不能刪除。那 cache 可以乾脆不設 TTL 嗎?
Triton 說不設 TTL「後果更嚴重」。下面是他在 087、088 列的 cache 常犯錯誤。
🔭 推論 原書假設短網址不能更新、不能刪除,對應永遠不變,就是 087 說的「永遠不會改動的資料」:放進 AS 的 local cache 也不怕舊。另外,亂打的無效短碼每次都 cache miss、直進 DB;可以把「找不到」也 cache 一小段時間,或在前面放 bloom filter。
其他 cache 常犯錯誤
- 「有笨蛋會設 cache TTL = 一年 – 不設 TTL後果更嚴重,唉~」087 p.17
- 「別使用mod( md5(cacheKey), n )來決定某一 keyValue 位置」「請學習 consistent hash」087 p.15
- 「在 C1K,你是需要用 redis作 cache」088:原書每秒讀 11,600,確實要
- 「snapshot是永遠不會改動的資料 所以,其 localcache TTL應該跟 Redis 相同的」087 p.28
Triton 補充原書 wrap up 五點 × Triton
原書收尾的五點,Triton 各有一句
你猜猜看:同一個短網址服務裡,哪一種資料掉一點也死不了人?
對應掉了,印在海報上的連結就死了;點擊數少算幾次,報表差一點而已。Triton 對這兩種資料的說法在第 3、4 張卡。
1 · Rate limiter
「Per-IP limiting 請找 cloudflare 之類的供應商,別自己來」「Read-only request 請善用 CDN」🗣️ Triton 059-ecom-system design · ratelimiting
原書說「依 IP 過濾」。Triton 完整的限流觀點見第 4 章簡報。
2 · Web server scaling
「Application Server 和 Connection必須是無狀態」🗣️ Triton 028 · 通訊協定具有無狀態性
和原書一致。028 也提醒:「RESTful 只要求 Application Server 是 stateless,Server Side 其他部份可以 stateful」。
3 · Database scaling
「不能不見的data,我一定存到RDBMS」「我還不如走傳統的sharding路線」🗣️ Triton 106-喵 data.md
🔭 先「了解 N(像是 QPS / user count / data size)」064:36.5 TB 是十年後的 N,第一年只有十分之一。短碼本身是 natural key,要 shard 時可直接依短碼分。
4 · Analytics
「到底這份data是否錯一點也沒所謂的?」「UserStatistics不見了一點點是死不了人的」🗣️ Triton 117-喵看Data 的思維.md
🔭 選 302 換來的點擊數就是這種資料:117 建議先 buffer 在 AS 的 local memory、背景 flush,不必每次點擊同步寫進主資料庫(但「沒10K RPS前別做這種事」)。
5 · Availability…
Triton 對 HA 的定義和「4 個 9」的批評,見第 1、2 章簡報。
🔭 短網址對應掉了,印在海報上的連結就全死了:屬於 106 說的「不能不見的data」。redirect 是純讀取,讀取可以走 CDN(166),CDN 也替源站擋掉一部分故障。
📅 2026 補充原書 301 / 302 說法的限制
誰能 cache 多久,其實是 header 說了算
你猜猜看:原書說 301 會被瀏覽器 cache。如果 301 的回覆上還寫了 Cache-Control: no-store(請不要存)呢?
status code 只是預設值;Cache-Control 這個 header 明講「存多久、能不能存」時,照它的。下面是規範的細節。
📅 2026 補充 301 預設可快取,302 要明講
現行 HTTP 規範(RFC 9110 / 9111):301 屬於「heuristically cacheable」,沒有明確指示時快取可以自己決定存多久;302 沒有這個預設,要有 Cache-Control 或 Expires 才會被快取。所以 301 也可以配 Cache-Control: no-store 或很短的 max-age,302 也可以配長 max-age。原書把「瀏覽器會不會快取」完全綁在 status code 上,是簡化。
📅 2026 補充 307 / 308
307 Temporary Redirect 和 308 Permanent Redirect 是後來補上的版本,規定瀏覽器不可以改掉原本的 method(301 / 302 歷史上允許把 POST 改成 GET)。使用者點短網址都是 GET,所以原書的 301 / 302 選擇仍然成立。
🔭 依 Triton 原則推論 這代表什麼
167 的重點是「CDN只用看HTTP header部分就好」。header 不只 status code,還有 cache 相關的那幾個;146 說的「設定好你的HTTP header的cache相關的」就是這件事。301 還是 302 只是第一步,max-age 設多久才決定 analytics 漏掉多少。
到這裡你已經會了小結 4 / 4
- QPS
- API
- redirect
- cache / CDN
- hash table
- hash function
- base 62
- collision
- bloom filter
- auto-increment
- atomic
- TTL / stampede
到這裡你已經會了:Triton 的追問
- 「先查再寫」中間有縫:交給資料庫的 unique constraint,查和寫一口氣做完(atomic)。
- cache 一定要設 TTL;過期那一刻,第一位上鎖再查一次,避免 stampede。
- status code 跟好,CDN 才能只看 header 替你擋讀取;流水號要先打亂,才不洩漏業務量。
12 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
號碼牌要短、要猜不到;
領大衣的路,讓 CDN 和 cache 幫你擋。
原書對的地方
- 估算 → 627 ≈ 3.5 兆 → 7 個字元
- 301 省負載、302 留數據
- 對應存 RDBMS,讀取路徑加 cache
- Table 3 自己點出流水號的安全疑慮
Triton 會追問的地方
- status code 跟好了沒?CDN 能不能只看 header?(167)
- 流水號 base 62,對手算得出業務量(113)
- 「先查再寫」不是原子動作(164 的原則)
- cache miss 時有沒有上鎖再查、有沒有 TTL(087)
帶回家的做法
- redirect 是讀取:CDN + 正確的 cache header
- 短碼不要直接用 auto-increment
- 唯一性交給 unique constraint
- 對應永不改變 → 放心多層 cache;點擊統計可以 buffer
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)與原書對照
Triton 本人的講義 / 文章
- 167-有人問到底要不要跟好http status code.md — CDN 只 cache 成功的 request、只看 header、CPU 差一個量級、status code 是最難還的 tech debt(檔尾「application error 自定義狀態碼」那段是留言者語氣,不引)
- 027 / 028-RESTful API Design-tw-2.1 / 2.2.pdf.md — 資源是名詞、POST 重送與 idempotent、404、410(028)、304 與「定義能否使用快取」、stateless AS
- 113-喵的 backend 測驗.md — 第 15 題 auto-increment 與競爭對手猜業務量、第 14 題效能隱憂(題目,無答案)
- 010 auto-inc 不在 TX 內、一次跳 20、會跳號(檔尾 AI 段不引)· 094 B+tree 右邊 leaf、近期資料集中在右邊
- 087-redis-2019.pdf.md — 一般 vs 高流量 caching、80 個 request、TTL、consistent hash、immutable snapshot 的 local cache · 088 C1K 要 redis cache、cache without TTL
- 089-redis-ratelimit.pdf.md — bloomfilter 的 Test/Merge、Little false positive doesn't matter、沒有 expiration · 011 只引「m = 1000003」與 AI 那三句
- 164 atomic check-and-set · 146 設定好 CDN 與 cache header · 166 Write 不能用 CDN · 059 per-IP 找 Cloudflare · 106 RDBMS、sharding · 064 了解 N · 117 統計資料可以 buffer · 065(講者備註)2018 年可租 3904 GB RAM
不引用:011 與 010 的 AI 段落;040(Clarence 的 RESTful 心得,第三方)。materials/core 沒有任何 Triton 談短網址、301/302 或 base 62 的原文,相關頁全部標 🔭。
原書對照
Alex Xu, System Design Interview Vol.1 Ch.8。開頭與 Step 1 問答、use cases(第 4 頁);Back of the envelope estimation(6);Step 2 API endpoints(8);URL redirecting 與 Figure 1–2(10);301 vs 302(12);hash table 與 URL shortening、Figure 3(16);Step 3 Data model 與 Figure 4(17);Hash value length 與 Table 1(19);Hash + collision resolution、Table 2、Figure 5、bloom filter(22–24);Base 62 conversion 與 Figure 6(26);Comparison 與 Table 3(27);URL shortening deep dive、Figure 7、Table 4、unique ID generator(28);URL redirecting deep dive 與 Figure 8(29);Step 4 Wrap up 與參考資料(30)。原書 8 張圖都依圖說與 alt 描述重繪,不是原圖;Figure 1 原本是瀏覽器截圖,重繪成文字面板。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 12 階:QPS(5)、API(7)、redirect(9)、cache / CDN(11)、hash table(14)、hash function(15)、base 62(18)、collision(21)、bloom filter(23)、auto-increment(25)、atomic(36)、TTL / stampede(39);小結(13、20、31、44);名詞小卡(46)。QPS、cache、CDN、database、race condition 連到第 1、2、4 章簡報的延伸基礎頁。寄物處是示範情境;生日、打洞卡、里程表的小數字是示意。
一個可以直接問自己的問題
你的服務對「找不到」回的是什麼 status code?CDN 看到它,會不會把它當成功 cache 起來?