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 階。每一階只用前面講過的東西。

  1. 1QPS每秒收幾件
  2. 2API寄放、領回兩個窗口
  3. 3redirect「去 3 號櫃拿」
  4. 4cache / CDN抄在手背上
  5. 5hash table登記簿
  6. 6hash function文字的指紋
  7. 7base 6262 個符號排列
  8. 8collision生日撞日
  9. 9bloom filter打洞卡
  10. 10auto-increment1、2、3 流水號
  11. 11atomic查和寫一口氣做完
  12. 12TTL / stampede小抄過期那一刻

第 1–4 階 · 寄放與領回

要回答:點一下短網址,發生了什麼事?

第 5–7 階 · 號碼牌怎麼編

要回答:為什麼 7 個字就夠用十年?

第 8–10 階 · 兩種編法的代價

要回答:會撞號、會被猜,各怎麼辦?

第 11–12 階 · Triton 的追問

要回答:兩人同時來、一萬人同時來,撐得住嗎?

全程只用一個情境:餐廳門口的寄物處

大衣 = 長網址號碼牌 = 短網址寄放、領回兩個窗口 = API櫃台的登記簿 = database手邊的小抄 = cache巷口分店 = CDN

數學只用乘法、開根號和「數有幾個零」。每爬 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
短網址可以刪除或更新嗎?為了簡化,假設不能刪除、不能更新

📖 原書 系統設計面試題故意是開放式的,問澄清問題是關鍵。

📖 原書 基本使用案例

  1. URL shortening:給一個長 URL → 回傳短很多的 URL
  2. URL redirecting:給一個短 URL → 導向原始 URL
  3. 高可用、可擴展、容錯(high availability, scalability, fault tolerance)

白話:alias=別名;high availability=隨時都能用;scalability=人變多也撐得住;fault tolerance=壞掉一台不會全倒。

寄物處版:一天收 1 億件大衣;號碼牌越小越好;號碼只能寫數字和英文字母;寄了就不能換、也不能取消。

🗣️ Triton 「不能刪除」這個假設,第 34 頁會看到它對 HTTP status code 的影響(404 還是 410)。

延伸基礎第 1 階 · QPS懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

一天收 1 億件大衣,櫃台每秒要收幾件?

① 先想像

寄物處從早開到晚。要知道櫃台忙不忙,得把「一天幾件」換成「每秒幾件」。

你猜猜看:一天約 10 萬秒(86,400)。一天收 1 億件,平均每秒大約幾件?

③ 這叫做 QPS、storage

QPS:每秒進來幾個 request。storage:存了幾年之後,倉庫要多大。

④ 跟這章的關係

下一頁原書就用這兩個數字估規模。完整的估算法在 第 2 章簡報第 23–25 頁。

② 動手玩:一天收幾件?

1,157每秒寄放(寫入)11,574每秒領回(讀取,假設 10 倍)

一件大衣只寄一次,卻可能被領很多次:一個短網址貼出去,被點上千次。所以「讀」比「寫」多。

原書 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懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. 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懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. 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瀏覽器開發者工具裡的 request 與 response headers(依原書內容重繪;原圖是截圖,alt 只描述了部分 header 的值,沒給的以 … 表示;cf-cache-status 依 alt「dynamic response」寫成 DYNAMIC)

📖 原書 Figure 1 是在瀏覽器輸入 tinyurl 時看到的東西:server 收到 tinyurl request 後,用 301 redirect 把短網址換成長網址。

  1. Client 造訪短網址 https://tinyurl.com/qtj5opu
  2. tinyurl server 回 status code 301,location header 放長網址
  3. 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懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

把「3 號櫃」抄在手背上,或請巷口分店代答

① 先想像

你常來,乾脆把「大衣在 3 號櫃」抄在手背上,下次直接走過去。

你猜猜看:抄在手背之後,你又來了 5 次。櫃台總共被你問了幾次?

③ 這叫做 cache、CDN

cache:手邊的小抄,拿得快,正本在別處。CDN:開在客人附近的分店,替總店回答大家都一樣的問題。

④ 跟這章的關係

301 等於叫瀏覽器自己 cache(下一頁)。完整版見第 1 章簡報 cache(第 18 頁)、CDN(第 21 頁)。

② 動手玩:誰來回答「大衣在哪」?

0總共來領幾次0總店櫃台被問幾次

原書 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=點擊統計:誰、什麼時候、從哪裡點了連結。

動手玩:同一個短網址點十次

0使用者點了幾次
0短網址 server 收到
0分析報表看到的點擊

到這裡你已經會了小結 1 / 4

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

到這裡你已經會了:點一下短網址,發生了什麼事

下一階要解決的問題

號碼牌要怎麼編?先看櫃台怎麼用號碼牌找到大衣:一本登記簿。

延伸基礎第 5 階 · hash table懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

給一個號碼,直接翻到那一格

① 先想像

櫃台有一本登記簿:左欄號碼牌、右欄大衣在哪。客人遞號碼來,櫃台要找到那一行。

你猜猜看:登記簿 1 萬行,沒照號碼排好。最壞要翻幾行才找到?

③ 這叫做 hash table、key / value

hash table:「key → value」的對照表,給 key 一次就找到。key 是號碼牌,value 是大衣在哪。

④ 跟這章的關係

原書的 redirect 就是 hashTable.get(shortURL)。表大到記憶體放不下,就改放 database(第 1 章第 8 頁)。

② 動手玩:找一張號碼牌

找:
0翻了幾行

延伸基礎第 6 階 · hash function懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. 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 頁)。

📖 原書 Figure 3longURL 經過 ƒ(x) hash 成短網址(依原書內容重繪;alt 提到圖下方有一行「Viewer does not support full SVG」,那是原圖顯示的瑕疵,不畫)

原書 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。

📖 原書 Figure 4url 表:id(PK)、shortURL、longURL(依原書內容重繪)

寄物處版:櫃台的腦袋記不住一億件大衣放哪,所以準備一本登記簿,每一行寫「流水號、號碼牌、大衣是哪一件」。

🗣️ Triton 「不能不見的data,我一定存到RDBMS」,見第 42 頁。

延伸基礎第 7 階 · base 62懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

每一格有 62 種寫法,7 格排得出幾種號碼?

① 先想像

行李箱的密碼鎖,每一格轉盤是 0–9。1 格有 10 種,2 格有 100 種。

你猜猜看:每格 0–9 的密碼鎖,3 格有幾種組合?

③ 這叫做 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

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

到這裡你已經會了:號碼牌要編幾格

下一階要解決的問題

指紋太長,砍成 7 個字。砍短之後,兩件大衣會不會拿到同一個號碼?

延伸基礎第 8 階 · collision懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

班上 23 個人,就很可能有兩人同一天生日

① 先想像

一年有 365 天。班上同學越多,越可能有兩個人同一天生日。

你猜猜看:至少要幾個人,「有兩人同一天生日」的機會就超過一半?

③ 這叫做 hash collision、生日問題

hash collision:兩件不同的大衣拿到同一個號碼。生日問題:號碼種類「開根號」那麼多件,就差不多會撞。

④ 跟這章的關係

原書做法一把指紋砍成 7 個字,一定會撞,所以要「撞到就重來」(下一頁)。

② 動手玩:抽一班看看

51%有人同一天生日的機會—這一班撞了幾對

換成號碼牌:號碼有 N 種,大約寄幾件就有一半機會撞?

原書 Step 3Hash + collision resolution · Table 2 · Figure 5

做法一:拿現成 hash,砍到 7 個字,撞到就重來

這一步要解決的問題現成的指紋太長;砍成 7 個字一定會撞號(第 21 頁),撞了怎麼辦?

📖 原書 Figure 5hash + collision resolution 的流程(依原書內容重繪;「longURL + predefi..」依 alt 保留截斷,內文是「附加一個預先定義的字串」)

算一下(原書沒寫):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 functionHash value (Hexadecimal)
CRC325cb54054
MD55a62509a84df9ee03fe1230b9df8b84e
SHA-10eeae7916c06853901d9ccbefbfcaf4de57ed85b

📖 原書 用 CRC32、MD5、SHA-1 這類知名 hash,最短的 CRC32 也超過 7 個字元。第一種縮短法:取前 7 個字元,但會 hash collision。解法:遞迴地附加一個預先定義的字串,直到不再碰撞。

📖 原書 這能消除碰撞,但每個 request 都查一次 DB 確認 shortURL 存不存在很貴。Bloom filter(參考資料 [2])可以改善:一種省空間的機率性技術,用來測試一個元素是不是集合的成員。

延伸基礎第 9 階 · bloom filter懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

一張打洞卡:只會說「一定沒有」或「可能有」

① 先想像

每發一個號碼,櫃台用公式算出卡上 2 個格子,各打一個洞。卡很小,放得進口袋,不用翻厚厚的登記簿。

你猜猜看:查一個新號碼,它的 2 個格子有 1 個沒打洞。這個號碼?

③ 這叫做 bloom filter、false positive

bloom filter:只會答「一定沒有」或「可能有」的打洞卡。false positive(誤報):卡說可能有,翻了登記簿才發現沒有。

④ 跟這章的關係

原書用它減少「查 DB 看號碼用過沒」的次數。下一頁用 509 格的大卡實際跑一次。

② 動手玩:16 格的打洞卡,每個號碼打 2 個洞

0已發號碼0查了幾次0翻登記簿幾次0誤報

原書 · 動手玩截短的 hash 會撞 · bloom filter 幫你少查 DB

號碼牌只剩 3 位,很快就會兩件大衣同號

這一步要解決的問題截得越短越容易撞;每次都翻登記簿確認又太慢。打洞卡能省掉幾次?

0已存網址
0碰撞次數
0查 DB 次數
0bloom 誤報

Bloom filter:m = 509 個 bit、k = 3

文組版

Bloom filter 是櫃台口袋裡一張打洞卡:每發一張號碼牌,就在卡上 3 個位置打洞。新號碼要發之前先看卡:3 個洞有一個沒打 → 這號碼一定沒發過,不用翻登記簿;3 個洞都打了 → 「可能發過」,才去翻登記簿確認。

模擬規則:照 Figure 5,撞到就在 longURL 後面附加預先定義的字串 # 再 hash。m 選質數 509 是向第 38 頁 Triton 的設定致敬。

延伸基礎第 10 階 · auto-increment懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

1、2、3……的號碼牌,永遠不會撞

① 先想像

另一種發法:不算指紋,照順序發 1 號、2 號、3 號……永遠不會兩人同號。

你猜猜看:早上你拿到 105 號,晚上再來拿到 1,305 號。今天中間大約寄了幾件?

③ 這叫做 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 進位的號碼牌?

📖 原書 Figure 611157 反覆除以 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 resolutionBase 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

原書的縮網址流程:先查有沒有,沒有才發新號

這一步要解決的問題新網址進來,一步一步怎麼發號?同一個網址又送來一次怎麼辦?

📖 原書 Figure 7URL shortening 流程(依原書內容重繪;步驟 4–6 的文字依 alt 保留截斷,完整句子見右邊內文)
idshortURLlongURL

📖 原書 這是系統的核心,希望流程邏輯簡單、能用。設計採用 base 62。

  1. longURL 是輸入
  2. 系統檢查 longURL 在不在資料庫
  3. 在:之前轉過了,從 DB 取出 shortURL 回傳給 client
  4. 不在:這是新的 longURL,由 unique ID generator 產生新的唯一 ID(primary key)
  5. 用 base 62 把 ID 轉成 shortURL
  6. 用 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 次領回,怎麼讓它又快、又不把登記簿翻爛?

📖 原書 Figure 8URL redirecting 的詳細設計,編號 1–5 是流程(依原書內容重繪)

📖 原書 讀比寫多,所以 <shortURL, longURL> 對應存在 cache 裡提升效能。流程:

  1. 使用者點短網址 https://tinyurl.com/zn9edcu
  2. Load balancer 把 request 轉給 web servers
  3. shortURL 已經在 cache:直接回傳 longURL
  4. 不在 cache:從資料庫拿 longURL。資料庫也沒有,多半是使用者輸入了無效的 shortURL
  5. 把 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

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

到這裡你已經會了:原書的完整設計

下一階要解決的問題

兩個 request 同一瞬間送來、一萬個 request 同一瞬間點同一個連結,原書的流程撐得住嗎?換 Triton。

換 Triton 上場覆蓋度:中

Triton 沒寫過短網址,但這章每一塊他都講過

原書的零件Triton 有講的出處頁
301 / 302、Figure 1 的 headers沒有直接談 301 vs 302;談的是status code 要跟好,CDN 才能只看 header 就決定 cache167、146、16633
REST API、無效短碼URL 是名詞不是動詞、POST 重送、404 / 410 / 304027、02834
Base 62 of ID、Table 3 的安全疑慮auto-increment 會讓競爭對手猜到業務量;auto-inc 的效能與跳號113、010、09435
Figure 5 / 7 的「先查再寫」、bloom filteratomic check-and-set;他自己在 production 用 bloomfilter 的經驗164、089、01137–38
Figure 8 的 cachecache stampede 要上鎖再查一次、一定設 TTL、預熱、不可變的資料087、08840–41
Wrap up 五點per-IP 限流交給 Cloudflare、stateless AS、先 scale up 再 sharding、統計資料可以掉059、028、106、064、11742

🔭 讀法 這章的 Triton 頁面,引號裡的是他的原話(附檔名);把原話套到短網址上的那一步,一律標 🔭。materials/core 裡沒有任何一份 Triton 的文章提到 tinyurl、短網址或 base 62。

Triton 補充status code 不只是給瀏覽器看的

跟好 status code,CDN 才幫得上忙

你猜猜看:短網址服務前面隔了一層 CDN。找不到的短碼也回 200,只在 body 裡寫「not found」。CDN 會怎樣?

「跟好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?

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。對手今天、明天各建一個連結,把兩個短碼換回數字一減,得到什麼?

動手玩:競爭對手的小實驗

延伸基礎第 11 階 · atomic懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

兩位櫃台同時看到「42 號沒人用」

① 先想像

兩位櫃台人員同時翻登記簿,都看到 42 號空著,各自把 42 號發給自己的客人。

你猜猜看:兩人都是「先看、再寫」。最後幾位客人拿到 42 號?

③ 這叫做 atomic、unique constraint

atomic:「查」和「寫」一口氣做完,中間沒人能插隊。unique constraint:資料庫規定這一欄不能重複,第二筆直接被拒絕。

④ 跟這章的關係

原書 Figure 5、7 都是「先查再寫」(下一頁)。race condition 完整版見 第 4 章簡報第 26 頁。

② 動手玩:你來決定誰先動

Triton 補充Figure 5 / 7 的「先查再寫」

「先查有沒有,再寫進去」中間有一個縫

你猜猜看:Figure 7 第 2 步「longURL 在 DB 嗎?」。同一個新網址在同一瞬間被送了兩次,結果?

動手玩:兩個 request 同時算出同一個 hash

按「同時送出」:兩個不同的長網址,截短後剛好得到同一個 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 誤報了一次(卡說「可能有」,其實沒有)。會出什麼事?

🔭 推論 在短網址裡,誤報 = 多查一次 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懂的人可以跳過

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

小抄要定時作廢,作廢的那一刻最危險

① 先想像

櫃台的小抄每 10 分鐘作廢、重抄一次,免得抄錯的一直留著。剛作廢的那一刻,小抄是空的。

你猜猜看:小抄空了,翻登記簿要 5 秒,每秒有 2 位客人來問同一個號碼。幾位會跑去翻登記簿?

③ 這叫做 TTL、cache stampede

TTL(time to live):小抄放多久就自動作廢。cache stampede:小抄剛作廢,一大群 request 一窩蜂衝進 DB。

④ 跟這章的關係

原書 Figure 8 的 cache 沒提這兩件事。Triton 的寫法在下一頁:第一位上鎖,其他人等一下再看小抄。

② 動手玩:小抄作廢的那一刻

10跑去翻登記簿的人

Triton 補充Figure 8 的 cache 在爆紅連結下

一個連結爆紅、cache 剛好過期的那 80 毫秒

你猜猜看:一個爆紅連結每秒被點 1000 次,cache 剛好過期,DB 回應要 80ms。照原書的寫法,幾個 request 會衝進 DB?

原書的寫法 = 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 嗎?

🔭 推論 原書假設短網址不能更新、不能刪除,對應永遠不變,就是 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 各有一句

你猜猜看:同一個短網址服務裡,哪一種資料掉一點也死不了人?

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(請不要存)呢?

📅 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

  1. QPS
  2. API
  3. redirect
  4. cache / CDN
  5. hash table
  6. hash function
  7. base 62
  8. collision
  9. bloom filter
  10. auto-increment
  11. atomic
  12. TTL / stampede

到這裡你已經會了:Triton 的追問

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

本章名詞小卡課後複習用 · 每個名詞一句白話

今天出現的名詞,一句話講完

URL網址;長網址是大衣,短網址是號碼牌
QPS每秒進來幾個 request
storage存了幾年之後,倉庫要多大
讀寫比領回次數 ÷ 寄放次數;原書假設 10 : 1
API店家公開的窗口和規矩
REST用網址指名東西、用 POST / GET 說動作的寫法
POST / GET交東西過去/拿東西回來
status code回覆紙條上的三位數號碼
redirect回你「去別處拿」,新地址寫在 location
301 / 302永久搬家(瀏覽器會記住)/暫時在別處
cache手邊的小抄,拿得快,正本在別處
CDN開在客人附近的分店,替總店回答一樣的問題

給工程師的重點出處與標籤

引述來源(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 起來?

← → 翻頁 · S 講者備註 · D 深/淺色
1 / 1目錄