Mobile System Design Interview · 第 6 章Triton 覆蓋度:🟢 高(只限 API 契約與後端;library 內部無)Triton 線
Pagination Library
一次端幾盤菜、下一盤從哪裡接
這一章不做 app,做一個給別的工程師用的分頁函式庫:一個泛型的 Paginator<T>、三個方法、兩層快取、一個會排優先順序的 scheduler。原書整章都在 client 端;Triton 沒寫過 client library,但他把「分頁的 key 長什麼樣、為什麼這樣才 cache 得住、DB 那邊為什麼快」講得非常具體。
給文組
全程只用一家熱炒店,一階一階爬 11 個概念:一盤幾道菜 = page size,先備下一盤 = prefetch,桌邊推車 = 記憶體快取,倉庫 = 磁碟快取。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
原書 2 張圖依描述重繪並可播放、Table 1 與所有 Kotlin/Swift 介面照列。offset vs cursor 的入門在第 5 頁;Triton 段落往下挖:刪除造成的漏看、OFFSET 100000 的成本、062 的分頁快取設計。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📝 上課筆記
先用生活理解餐廳上菜
客人點了一百道菜:一次全端上桌,還是一盤一盤端?
一次端一百道:第一口要等很久,桌子放不下,客人吃十道就飽了,剩下九十道白做。一次端一道:服務生跑斷腿,每吃完一道都要空等。分頁就是在找中間那個數字。
- 一盤幾道菜 = pageSize(原書
fetch(key, pageSize),第 12 頁) - 「接著上次那張單」= key:可以是頁碼,也可以是 cursor
- 趁客人還在吃,先備下一盤 = prefetch(
fetchAround,第 18 頁) - 桌邊推車/後面倉庫 = 記憶體快取/磁碟快取(第 27 頁)
假設:每趟固定 2 秒(走過去、點單),每道菜多 0.1 秒;客人每道吃 1 秒。數字是示意,不是原書的。
學習地圖本章的概念階梯
今天爬 11 階。每一階只用前面講過的東西。
- 1page size一盤端幾道
- 2offset / cursor記第幾道 vs 夾書籤
- 3library中央廚房的醬料包
- 4callback取餐呼叫器
- 5prefetch快吃完就去端
- 6cache桌邊推車
- 7memory / disk推車 vs 倉庫
- 8eviction推車滿了收哪盤
- 9priority在等的先出
- 10invalidation冷了、改了就作廢
- 11index照順序排的電話簿
第 1–3 階 · 一盤一盤端
要回答:一盤幾道?下一盤從哪接?
第 4–5 階 · 端菜不卡住
要回答:等菜時能做別的嗎?何時先去端?
第 6–8 階 · 推車和倉庫
要回答:端過的盤子放哪?滿了收哪盤?
第 9–11 階 · 廚房那一端
要回答:誰先出?何時作廢?DB 怎麼找得快?
全程只用一家店:阿美熱炒(虛構)
每爬 2–3 階,有一頁「到這裡你已經會了」。
延伸基礎第 1 階 · page size懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
桌上一眼看得到 8 道菜,服務生一盤該端幾道?
① 先想像
客人的桌子(手機螢幕)一眼看得到 8 道菜。服務生每跑一趟,不管端幾道,都要先花 2 秒。
你猜猜看:客人想看 40 道,一盤端 10 道,服務生要跑幾趟?
40 ÷ 10 = 4 趟。一盤只端 1 道,就要跑 40 趟,光是走路就 80 秒。
③ 這叫做 pagination、page size
pagination(分頁):長長的清單,一次只拿一段。page size:一段拿幾筆,就是一盤端幾道。
④ 跟這章的關係
原書的 fetch(key, pageSize) 讓呼叫的人自己決定。至少要比一個螢幕多,不然一打開就得再跑一趟。
② 動手玩:一盤幾道?
示意:每趟 2 秒,每道多 0.1 秒。
延伸基礎第 2 階 · offset / cursor懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
端完上面 4 道,下一盤從哪一道接?
① 先想像
菜單照時間排,最新的在最上面。服務生端完上面 4 道,記下「下次從第 5 道開始」。這時廚房在最上面又加了 2 道新菜。
你猜猜看:下一盤的「第 5 道」是哪一道?
上面多 2 道,全部往下擠 2 格,第 5 道變成剛端過的蔥爆牛肉。改記「比 12:09 那道更早的」就不會錯。
③ 這叫做 offset、cursor
offset:記「從第幾道開始」,像看書記「看到第 N 頁」。cursor:夾書籤,記「最後一道是哪一道」,例如它的時間。03-sdi 11 章的版本
④ 跟這章的關係
原書的 key 兩種都能放。Triton 的講義用時間戳當書籤;offset 連「刪掉」都會出事(第 42 頁)。
② 動手玩:兩種記法
延伸基礎第 3 階 · library懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
中央廚房做好醬料包,分店照同一張點單用
① 先想像
阿美開了三家分店。點單格式早就講好:「要哪一盤、一盤幾道」。至於菜從廚房、冷凍庫,還是練習用的假廚房來,點單不管。
你猜猜看:今天改從冷凍庫拿菜,不從廚房拿。點單要重寫嗎?
點單只說「要什麼」,不說「去哪拿」。誰來供菜,是另外接上去的零件。右邊切三個地方看看。
③ 這叫做 library、interface
library:別人寫好、你直接拿來用的工具包(醬料包)。interface:事先講好的點單格式,只說要什麼,不說怎麼做。
④ 跟這章的關係
原書的 Paginator 就是一個 interface。這章的使用者不是滑手機的人,是寫 app 的工程師。
② 動手玩:同一張點單,換三個供菜的地方
到這裡你已經會了小結 1 / 5
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
到這裡你已經會了:一盤一盤端
- 長清單一次只拿一段(pagination)。一盤幾道是 page size:太小跑斷腿,太大白做,至少填滿一個螢幕。
- 下一盤從哪接:記「第幾道」(offset)會被新菜擠歪;夾書籤(cursor)不會。
- 這章做的是給工程師用的工具包(library),對外只露出一張點單格式(interface)。
下一階要解決的問題
原書在面試一開始問了什麼?這個工具包要有哪些功能、哪些不做?
原書開頭為什麼要做一個「可重用」的分頁 library
這次的使用者不是滑手機的人,是寫 app 的工程師
這一步要解決的問題每個 app 都自己寫分頁,同一個 bug 要修好幾次。能不能做一份大家共用的工具包(第 3 階 library)?
📖 原書 有效管理大型資料集是行動 app 效能的基石;前面章節在個別 app 裡談過分頁,這章要打造可重用的分頁 library。組織變大時,好的 library 帶來三個好處:各 app 行為一致、減少重複程式碼、效能優化集中在一處。要在彈性與實用性之間取得平衡。
💡 原書 Pro tip 設計 library ≠ 設計 app
App 透過介面和畫面服務終端使用者;library 透過程式碼服務開發者。所謂「使用者體驗」變成:開發者多容易採用、多容易整合進專案、能不能解決他們的分頁需求。
📝 原書 Note 本章假設你已經熟悉 offset-based 與 cursor-based 分頁;複習請看第 10 章 Mobile System Design Building Blocks 的 Pagination 段落。(入門互動在第 5 頁。)
動手試:公司有三個 app,分頁出了一個 bug
文組翻譯:三家分店各自寫食譜,鹽放太多要改三本;中央廚房只要改一本,三家的味道也一樣。
原書 Step 1理解問題、建立設計範圍
面試一開始:應徵者 × 面試官的五個來回
這一步要解決的問題「分頁 library」範圍很大:要不要畫面?要不要快取?要不要開源?先問清楚再畫。
| 應徵者問 | 面試官答 |
|---|---|
| 核心需求:要一個彈性的方案,支援 offset 與 cursor-based 這類常見分頁模式,並能從本地與遠端資料來源分頁。這符合您的想法嗎? | 是,這涵蓋了預期的彈性和範圍。而且它要能處理任何類型的 app 資料。 |
| Library 要包含呈現分頁資料的 UI 元件,還是只專注分頁邏輯與資料管理? | 範圍聚焦在商業邏輯,先不含 UI 元件。 |
| 為了效能,實作快取存放已取得的頁:預設記憶體快取快速存取近期頁面,可選磁碟快取在 app 不同 session 之間保留資料。您覺得呢? | 聽起來很完美! |
| 再加 prefetch:使用者看第 5 頁時,背景自動載入第 6、7 頁,繼續滑時無縫。要不要也支援快速捲動、在大資料集裡快速跳躍? | 包含 prefetch;不含快速捲動,因為我們不處理 UI 元件。 |
| 最後:這個 library 會開源嗎?這會影響 API 設計、文件標準與版本策略。 | 會,我們計畫開源。 |
白話:UI 元件=畫面上的按鈕、清單;快取=桌邊推車(第 20 頁);session=app 從打開到關掉的一段;開源=程式碼公開,誰都能拿去用。
📖 原書 最後一題最關鍵:開源 = 你不認識的人會依賴你的 API,所以後面原書花了很多篇幅在「不要依賴第三方套件」、「用 class 不用 data class」、「SemVer」。
原書 Step 1Requirements
需求清單:點一條,看它在哪一頁被解決
這一步要解決的問題問完之後,把要做和不做的寫成清單。後面每一頁,都在解其中一條。
📖 原書 Functional
- 支援多種 app 資料類型與多種分頁技術
- 可以從不同的本地與遠端資料來源分頁
- 只提供商業邏輯,不提供 UI
- 提供記憶體快取與可設定的磁碟快取
- 使用者可以 prefetch 特定頁面
📖 原書 Non-functional
- Performance:分頁有效率、資源用得省、額外負擔小,並且在多執行緒環境下安全運作
- Reliability:優雅處理網路故障與中斷;不論裝置類型或 OS 版本,行為一致
- Usability:直覺的 API、完整文件、清楚的學習資源
白話:functional=要做哪些事;non-functional=做得多好;多執行緒=好幾個工人(thread)同時做事;OS=手機的作業系統。
📖 原書 Out of scope
- UI 中的分頁支援
- 快速捲動(fast scrolling)
點左邊任一條需求,這裡會告訴你它在第幾頁;再點一次直接跳過去。
原書 Step 2API design · Paginator<T>
一個泛型 Paginator<T>:貼文、訊息、商品共用一份程式
這一步要解決的問題貼文、訊息、商品都要分頁。要替每一種資料各寫一份程式嗎?
📌 原書 Remember Library 的 API 是它的公開面貌:開發者能直接碰到的函式、類別、方法、屬性。好的公開 API 讓人不必懂內部就能用,需要三個特質:清楚的文件、穩定(行為一致可依賴)、直覺(遵循平台慣例)。
💡 原書 Pro tip 先定義核心元素:開發者最常碰的介面、類別、資料模型。設計的核心是 Paginator 介面。
📖 原書 用泛型 <T> 的四個好處
- Flexibility:一個 Paginator 處理任何資料類型,滿足「多種資料類型」需求
- Isolation:多個 instance 共存不衝突,各自管理獨立的快取與分頁流程
- Optimization:每個 instance 只追蹤自己的資料,記憶體精簡
- Reliability:泛型在編譯時強制型別安全,及早抓錯
白話:泛型(generic)=便當盒先不寫裝什麼,用的時候才貼標籤;instance=照設計圖做出來的一個實體;編譯=把程式翻成機器碼的那一步,錯了先擋下。
動手試:三個 instance,互不干擾
📌 原書 不必替貼文、訊息各寫一個 Paginator class;一份實作,減少重複、更好維護。文組翻譯:同一款便當盒,裝排骨或裝雞腿都行,但一個盒子只裝一種,貼了「排骨」就塞不進雞腿。
原書 Step 2Paginator 的三個方法 · key 對分頁技術中立
fetch、fetchAround、clear:key 是頁碼還是 cursor,介面都一樣
這一步要解決的問題開發者最少要能做哪幾件事?而且不管後端記「第幾頁」還是夾書籤(第 2 階),叫法都一樣。
interface Paginator<T> {
fun fetch(key: String, pageSize: Int)
fun fetchAround(
key: String, pageSize: Int,
depthLevel: Int, direction: PageFetchDirection
)
fun clear(key: String)
}
enum class PageFetchDirection
ALL, FORWARD, BACKWARD
protocol Paginator {
associatedtype T
func fetch(key: String, pageSize: Int)
func fetchAround(
key: String, pageSize: Int,
depthLevel: Int, direction: PageFetchDirection
)
func clear(key: String)
}
enum PageFetchDirection
case all, forward, backward
📖 原書 三個需求對三個方法:取單一頁(fetch)、取周圍的頁做 prefetch(fetchAround)、從快取清掉特定頁(clear)。方法都是 idempotent:相同輸入重複呼叫,結果相同。
動手試:同一行 fetch,背後是兩種分頁
📖 原書 key 刻意設計成有彈性的 String:offset 分頁時是整數字串,cursor 分頁時是指向下一組資料的 token。不論資料來源用哪一種策略,開發者都用同一個介面。
💡 原書 Pro tip 把 Paginator 定義成 interface/protocol,不只是入口,也讓測試變容易:開發者可以做 test double 模擬各種情境(第 35 頁)。
延伸基礎第 4 階 · callback懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
點完餐,站在櫃台前等,還是拿呼叫器?
① 先想像
美食街點完餐,可以站在櫃台前乾等;也可以拿一個呼叫器去找位子,好了它會震。不想吃了,把呼叫器還回去就好。
你猜猜看:餐要 3 秒才好,你每秒能滑一次手機。站著等能滑幾次?拿呼叫器呢?
站著等,眼睛和手都被綁在櫃台。拿呼叫器,3 秒都是你的。手機 app 如果站著等網路,畫面就會卡住。
③ 這叫做 async、callback
async(非同步):交代完就去做別的,不站著等。callback:事先留給對方的呼叫器,好了它叫你。
④ 跟這章的關係
原書每個方法都帶一個 listener(呼叫器),回傳一個可以 cancel 的 PaginatorExecution(還回呼叫器)。
② 動手玩:等餐 3 秒
原書 Step 2Data propagation
結果怎麼交回去:原生 callback,加一個可以取消的 PaginatorExecution
這一步要解決的問題拿資料要時間,不能讓畫面卡住;使用者離開畫面了,還要能取消(第 4 階 callback)。
📖 原書 為了輕量、無依賴,用原生 callback 傳結果與錯誤,開發者不必採用某個特定的非同步框架。每個方法回傳 PaginatorExecution,讓使用者需要時取消操作。
interface Paginator<T> { fun fetch( key: String, pageSize: Int, listener: PaginatorFetchListener<T> ): PaginatorExecution fun fetchAround( key: String, pageSize: Int, depthLevel: Int, direction: PageFetchDirection, listener: PaginatorFetchAroundListener<T> ): PaginatorExecution fun clear(key: String) }
protocol Paginator { associatedtype T func fetch( key: String, pageSize: Int, listener: PaginatorFetchListener<T> ) -> PaginatorExecution func fetchAround( key: String, pageSize: Int, depthLevel: Int, direction: PageFetchDirection, listener: PaginatorFetchAroundListener<T> ) -> PaginatorExecution func clear(key: String) }
動手試:使用者滑到一半就離開畫面
📝 原書 Note 開源 library 要小心依賴
你引入的任何第三方 library,都會變成使用你的 app 的必要依賴。核心功能用語言原生的結構,同時保留擴充性,能和熱門 library 搭配(第 33 頁)。
📖 原書 內部每個 Paginator instance 有一個 thread-safe 的快取(好幾個工人同時存取也不會亂),通常是一個把 page key 對到資料的 Map,加速存取最近載入的頁(第 26 頁)。
原書 Step 2Data models · PaginatorPage
一頁 = 內容 + 自己的 key + 前後頁的 key + 何時過期
這一步要解決的問題一頁拿回來,除了內容還要帶什麼,app 才知道下一頁從哪接、這一頁何時過期?
📖 原書 PaginatorPage
| Kotlin | Swift |
|---|---|
public class PaginatorPage<T> | public class PaginatorPage<T> |
content: List<T> | content: [T] |
key: String | key: String |
expirationTime: String? | expirationTime: String? |
prevKey: String? | prevKey: String? |
nextKey: String? | nextKey: String? |
📖 原書 PaginatorPage 同時裝分頁內容和導航用的 metadata:目前的 key、上一頁與下一頁的 key(如果有)。可選的 expirationTime 讓 library 判斷快取何時要更新。文組翻譯:一個餐盒上貼著「這是第幾盒、前一盒和下一盒的編號、幾點前要吃完」。
💡 原書 Pro tip 為什麼這裡用 public class,不用 data class/struct
Kotlin 的 data class 會自動產生 copy、componentN、equals、hashCode;app 開發很方便,但在 library 裡,改屬性就會改到這些自動產生的方法,可能破壞使用者的二進位相容性。Swift 的 struct 是 value type,記憶體配置屬於二進位介面,改 stored property 會影響 ABI 穩定性。改用 class,比較能掌控公開介面、跨版本相容。
白話:二進位相容=用舊版編好的 app,不重新編譯也能接上新版 library;ABI=這個「接頭」的規格。
動手試:v1.1 想多加一個欄位
原書 Step 2How apps implement the Paginator interface
App 那一端:Repository 或 State Holder 把一頁一頁接成一條清單
這一步要解決的問題library 給的是一頁一頁;app 要的是一條可以一直往下滑的清單。誰來接?
📖 原書 使用 library 的 app 通常在 repository 或 UI state holder 裡
- 用
CallbackPaginator建立設定好資料來源的 Paginator instance - 在使用者動作(例如捲動)時呼叫 Paginator 的方法
- 把多個
PaginatorPage合併成一條清單 - 監看分頁狀態,判斷何時該載入更多
- 處理各種狀態:loading、error、empty
白話:repository/state holder=app 裡負責「拿資料、記住畫面現在長怎樣」的那一層。
📖 原書 線性情境(一路往下捲)主要用 fetch 依序載入;非線性情境用 fetchAround 預先抓目標頁周圍。責任分離:Paginator 專心做擷取與快取,app 負責呈現與互動。
畫面上的那一條清單
State Holder 手上的 PaginatorPage
延伸基礎第 5 階 · prefetch懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
客人吃到剩幾道,服務生就該去端下一盤?
① 先想像
客人每秒吃 1 道,一盤 6 道;服務生端一盤要 3 秒。等盤子見底才出發,客人就要空等。
你猜猜看:剩幾道時出發,客人剛好不用等?
剩 3 道時出發,3 秒後客人剛好吃完、新的一盤剛好到。剩 1 道才出發,每盤要空等 2 秒。
③ 這叫做 prefetch、threshold
prefetch(預取):還沒要,就先去拿。threshold(門檻):剩幾道時出發。
④ 跟這章的關係
原書用 fetchAround 的 depthLevel 決定先備幾頁(第 18 頁)。太晚出發會空等,備太多會白做。
② 動手玩:客人吃 4 盤就走
示意數字。第一盤一定要等,不算在內。
原書 Step 2fetchAround · depthLevel · direction
先備幾盤?depthLevel 太小會空等,太大會白做
這一步要解決的問題使用者滑到哪、先備幾頁,才不會看到空白(第 5 階 prefetch)?
📖 原書 需求對話的例子:看第 5 頁時,背景先載入第 6、7 頁,就是 fetchAround(key="5", depthLevel=2, direction=FORWARD)。direction 有 ALL、FORWARD、BACKWARD;非線性情境(例如直接跳到中間)用它預先抓目標頁周圍。
兩種浪費互相拉扯:
空白畫面:手指比網路快,滑到還沒載入的頁。
白做的 request:載了,但使用者在那之前就停了。
原書把快速捲動排除在範圍外:把滑動速度拉到最右邊,你會看到再大的 depthLevel 都追不上。
模擬假設:每頁 10 列、載入一頁 0.8 秒、最多同時 2 個 request;數字是示意,不是原書的。
到這裡你已經會了小結 2 / 5
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
到這裡你已經會了:原書的 API,和端菜不卡住
- 一個泛型的
Paginator<T>、三個方法:fetch、fetchAround、clear;key 放頁碼或書籤都行。 - 結果用 callback 交回去,不卡住畫面;使用者離開了可以 cancel。一頁帶著前後頁的 key 和過期時間。
- 快吃完前就去端(prefetch);
depthLevel決定先備幾頁,太少會空等、太多會白做。
下一階要解決的問題
端回來的盤子放哪?客人回頭要、或明天再來,要不要重跑廚房?
延伸基礎第 6 階 · cache懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
剛端過的那盤,客人回頭又要
① 先想像
服務生把端過的盤子放在桌邊推車上。客人說「剛剛那盤再給我看一下」,伸手就拿到,不用跑廚房。
你猜猜看:跑廚房 2 秒、推車 0.1 秒。客人要第 1 盤 3 次(第一次推車是空的),共等幾秒?
第一次推車上沒有,跑廚房 2 秒;後兩次從推車拿,0.1 + 0.1。沒有推車就是 3 × 2 = 6 秒。
③ 這叫做 cache、hit/miss
cache:手邊的暫存區,拿得快,正本在 server。hit/miss:推車上有/沒有,要跑廚房。server 端的版本:03-sdi 01 章
④ 跟這章的關係
原書每個 Paginator 裡都有一台推車:一張「key → 那一頁」的對照表(第 26 頁)。
② 動手玩:客人要第幾盤?
延伸基礎第 7 階 · memory / disk懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
推車打烊就收掉,倉庫明天還在
① 先想像
推車就在桌邊,拿得最快,但放不多,打烊就清空。後面的倉庫大,走過去要一點時間,明天開門東西還在。
你猜猜看:把 app 從背景滑掉再打開。剛剛看過的 3 頁,記憶體裡還在嗎?磁碟裡呢?
app 一關,它用的記憶體就還給手機了。存進磁碟的檔案,關機都還在。
③ 這叫做 memory、disk
memory(記憶體):推車,快但小,app 一關就清空。disk(磁碟):手機的儲存空間,倉庫,大、慢一點,關掉也還在。03-sdi 02 章的版本
④ 跟這章的關係
原書預設只用記憶體;另外設了 PaginatorStore 才寫磁碟,下次打開 app 還能先拿舊資料。
② 動手玩:關掉 app 再打開
推車:記憶體
倉庫:磁碟
示意:記憶體 0.01 秒、磁碟 0.05 秒、網路 1 秒。
原書 Step 2Creating configurable Paginator instances
CallbackPaginator<T>:四個零件用 dependency injection 裝進去
這一步要解決的問題有的畫面拿遠端、有的拿本地、有的要離線。同一個 Paginator,零件怎麼換?
📖 原書 介面是契約,CallbackPaginator 是 library 附的完整實作
PaginatorDataSource<T>:每一頁實際去哪拿,遠端 API、本地 DB 或兩者混合。把擷取拆出去,CallbackPaginator 專心協調流程PageValidator<T>:快取頁是否仍有效(過期時間、資料完整性);不通過就重新擷取- (可選)
PaginatorStore<T>:把頁存到磁碟供離線使用,減少重複網路請求 PaginatorConfig:併發處理、快取淘汰策略與其他設定
class CallbackPaginator<T>(
dataSource: PaginatorDataSource<T>,
validator: PageValidator<T>,
store: PaginatorStore<T>? = null,
config: PaginatorConfig = DefaultPaginatorConfig(),
) : Paginator<T> { ... }
class PaginatorConfig
threadPool: ExecutorService,
maxParallelCalls: Int? = null,
inMemoryEvictionStrategy: PaginatorEvictionStrategy,
storeEvictionStrategy: PaginatorEvictionStrategy? = null,
...
class CallbackPaginator<T>: Paginator<T> {
init(
dataSource: PaginatorDataSource<T>,
validator: PageValidator<T>,
store: PaginatorStore<T>? = nil,
config: PaginatorConfig = DefaultPaginatorConfig()
) {
// self.field statements
}
}
class PaginatorConfig
dispatchQueue: DispatchQueue,
maxParallelCalls: Int?,
inMemoryEvictionStrategy: PaginatorEvictionStrategy,
storeEvictionStrategy: PaginatorEvictionStrategy?,
...
動手組:兩個畫面、兩個 instance、兩套設定
📝 原書 Note 不用靜態設定 Paginator.init(...)
有些 library 用全域的靜態設定;但每個 Paginator instance 需要獨立且高度客製的設定,所以選擇 instance 層級的設定。文組翻譯:不是全公司共用一台冷氣的溫度,是每間會議室自己調。
延伸基礎第 8 階 · eviction懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
推車只有 3 格,第 4 盤來了,要先收哪一盤?
① 先想像
推車上放著第 1、2、3 盤,第 3 盤是最後端來的。客人剛剛又夾了第 1 盤一口。現在第 4 盤端來了。
你猜猜看:收哪一盤,客人最不會想念?
第 1 盤剛被夾過,第 3 盤剛端來,第 2 盤最久沒人碰。「最久沒用的先收」,通常最不會被想念。
③ 這叫做 eviction、LRU
eviction(淘汰):滿了要騰位子,選一盤收掉。LRU(least recently used):收最久沒被碰的那一盤。
④ 跟這章的關係
原書內建 LRU、FIFO、LIFO,也能自己訂規則(下兩頁)。
② 動手玩:點一盤 = 客人夾一口
原書 Step 2Eviction policies
推車只放得下幾盤:LRU、FIFO、LIFO,或自己寫規則
這一步要解決的問題記憶體放不下全部的頁,滿了要先收哪一頁(第 8 階 eviction)?
📖 原書 Library 內建幾種常見淘汰策略:
- LRU(Least Recently Used):丟掉最久沒被用到的
- FIFO(First In, First Out):丟掉最早放進來的
- LIFO(Last In, First Out):丟掉最後放進來的
📖 原書 開發者也可以自訂:依時間過期(TTL)、記憶體大小上限、最大頁數。這個彈性讓 library 適應各種快取需求與資源限制;記憶體與磁碟各自在 PaginatorConfig 裡設定(inMemoryEvictionStrategy、storeEvictionStrategy)。
文組翻譯:桌邊推車只放得下 3 盤。LRU 是「最久沒人夾的先收」;FIFO 是「最早端來的先收」;LIFO 是「剛端來的先收」。播放那串順序,第 1 頁一直被回頭看:LRU 會留著它,FIFO 會把它收走再重端。
原書 Step 3High-level client architecture · Figure 1
Library 裡面:Paginator 在中間,Scheduler 管 request,Evictor 管快取
這一步要解決的問題把前面的零件組起來:誰負責排隊送 request、誰負責收盤子?按播放看兩種線。
📖 原書 圖例:實線是資料流、虛線是依賴、指向框外的箭頭是對外溝通。結構要優先考慮模組化、可擴展、可維護。
📖 原書 PaginatorScheduler 負責所有 request 相關操作:排隊、排序、處理回應;也管 debouncing、throttling、retry、併發,讓 Paginator 的職責專注精簡。
📖 原書 PaginatorEvictor 管理記憶體與磁碟兩邊的快取效率;拆出來就能換不同的淘汰策略而不影響其他部分。
💡 原書 Pro tip 把功能拆成專責元件有兩個目的:展示你懂模組化設計,並清楚告訴面試官你在處理快取、prefetch 這些具體需求。這個設計讓使用者能接自己的資料來源與儲存,排程與快取管理的複雜度交給 library。
原書 Step 4Deep dives · In-memory caching
快取不只存「有沒有」,存的是每一頁現在的狀態
這一步要解決的問題快取裡某一頁「正在拿」和「還沒拿」要分得清,不然同一頁會被拿兩次。
📖 原書 Deep dive 四個主題:有效的快取策略、API 呼叫的優先順序、模組化 API 設計、失敗處理與版本控制。面試時挖哪裡,看面試官的興趣與系統的挑戰。
📖 原書 快取直接影響效能與體驗。PaginatorInMemoryCache 提供 PaginatorPage 的快速存取,內部是 Map<String, PaginatorPageResult<T>>:
- String key:每頁的唯一識別(offset、頁碼或 cursor)
- PaginatorPageResult<T>:這一頁的生命週期
- key 不在快取:等待第一次擷取
Loading:擷取進行中Success(page: PaginatorPage<T>):已就緒且驗證過Error(message: String):擷取失敗,附診斷細節
📖 原書 明確建模這些狀態的好處:型別安全(編譯時抓錯)、任何時刻頁面狀態都清楚、好除錯、程式碼變大時更好擴展。
動手試:點一格就是 fetch 那一頁
在 Loading 時再點同一格,示範「已經在載入就不重發」;這是有 Loading 狀態才做得到的事(示意,不是原書的程式)。
原書 Step 4How the dual caching system works · Figure 2
先看推車、再看倉庫、最後才叫廚房:雙層快取的六步
這一步要解決的問題要一頁時,先看推車(記憶體)、再看倉庫(磁碟),最後才打網路。按播放,一步一步看。
- 使用者對 Paginator 呼叫
fetch - 查記憶體快取:有有效的 PaginatorPage 就立刻回傳,延遲最低
- 查磁碟快取(可選):記憶體沒有、又設定了 Store,就查磁碟;找到有效頁就提升到記憶體並回傳
- 向資料來源擷取:兩層都沒有,PaginatorScheduler 觸發 DataSource 的 fetch
- Validator 檢查:PageValidator 驗證新頁(格式、是否過期)
- 更新快取:驗證通過,同時寫進記憶體(5.1)與磁碟(5.2,若有設定)
- 把新的頁回傳給呼叫端
📖 原書 分層設計在速度和耐久之間取得平衡:記憶體快,磁碟是可靠的備援。PaginatorEvictor 執行淘汰政策,讓兩層都精簡、不過載。
原書 Step 4Benefits and considerations · Industry insights
快取的兩個前提:key 要對得上 request,存取要 thread-safe
這一步要解決的問題快取能用的兩個前提:key 要對得上 request;好幾個工人同時動推車,不能亂。
📖 原書 雙層快取的好處
- 避免網路呼叫,延遲降低
- 智慧的請求管理,網路用量降低
- 資料更快,體驗更流暢
📖 原書 要注意的實作細節
- 系統假設 cache key 直接對應網路請求;不成立時,要自訂 key 產生邏輯
- Paginator 跑在多執行緒環境,快取存取要 thread-safe、操作要 atomic,避免 race condition 或資料損壞
可設定 analytics 與 logger provider,記錄 cache hit、miss、eviction,讓開發者依需求調校。
🔍 原書 Industry insights
Kotlin Multiplatform 的 Store5 與 iOS 的 Hyperoslo Cache 可以同時寫記憶體與磁碟。Google Jetpack Paging 推薦 network + database 混合:本地 DB 是分頁內容的 single source of truth,RemoteMediator 只在本地資料用完時才去抓新頁進 DB。
動手試:同一個 key "2",兩種排序
先用「最新」fetch 第 2 頁,再切「熱門」fetch 第 2 頁:key 只有 "2" 時,快取會把「最新的第 2 頁」當成「熱門的第 2 頁」回給你。文組翻譯:推車上貼「第 2 盤」,但沒寫是哪一桌的。
到這裡你已經會了小結 3 / 5
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
到這裡你已經會了:推車和倉庫
- 端過的頁放推車(cache):有就 hit,沒有才跑網路。原書快取存的是每一頁的狀態:Loading、Success、Error。
- 記憶體快但 app 一關就清空,磁碟慢一點但下次還在。原書的順序:先記憶體 → 再磁碟 → 最後才打網路。
- 推車滿了要收盤(eviction),LRU 收最久沒碰的;快取 key 要對得上 request,不然會拿錯盤。
下一階要解決的問題
好幾個 request 同時要送:使用者正在等的那頁,跟先備著的 prefetch,誰先?
延伸基礎第 9 階 · priority懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
出菜口排了 4 道「先備著的」,客人正在等的那道排第幾?
① 先想像
出菜口一次出一道,每道 1 分鐘。前面排了 4 道先備著的(prefetch)。這時客人點的那道進來了,他正盯著空盤子。
你猜猜看:照進來的順序出,客人要等幾分鐘?讓他插隊呢?
排隊要等前面 4 道再加自己這道,共 5 分鐘。插隊就是下一個出,1 分鐘。先備著的晚 1 分鐘出,沒人在等。
③ 這叫做 priority、priority queue
priority(優先權):HIGH、MEDIUM、LOW 這種標籤。priority queue:永遠先出標籤最高的那一道。
④ 跟這章的關係
原書替 fetch 加上 priority,排程器用 priority queue(第 31–32 頁)。
② 動手玩:出菜口
原書 Step 4Priorities in API calls
使用者在等的那一頁,要插隊到 prefetch 前面
這一步要解決的問題使用者在等的那頁,跟先備著的 prefetch 同時要送,誰先(第 9 階 priority)?
📖 原書 使用者期待快速回應,library 卻要同時處理很多事,還常受限於裝置資源與網路波動。以下情況優先順序特別重要:
- 並行的 request 搶頻寬或運算
- 背景作業(例如 prefetch)和使用者發起的動作重疊
- 裝置限制:電量低、訊號差
📖 原書 使用者捲動載入新內容要優先於背景 prefetch;fetchAround 裡明確要求的那一頁要先於鄰頁。所以在公開 API 加上優先權:fetch 有 priority;fetchAround 分成 keyPriority(主頁)和 aroundPriority(周圍)。
動手試:fetchAround(key="5", depthLevel=2, ALL) 的執行順序
interface Paginator<T> { fun fetch( key: String, pageSize: Int, listener: PaginatorFetchListener<T>, priority: FetchPriority = FetchPriority.MEDIUM ): PaginatorExecution fun fetchAround( key: String, pageSize: Int, depthLevel: Int, direction: PageFetchDirection, listener: PaginatorFetchAroundListener<T>, keyPriority: FetchPriority = FetchPriority.MEDIUM, aroundPriority: FetchPriority = FetchPriority.LOW ): PaginatorExecution } enum class FetchPriority HIGH, MEDIUM, LOW
protocol Paginator { associatedtype T func fetch( key: String, pageSize: Int, listener: PaginatorFetchListener<T>, priority: FetchPriority ) -> PaginatorExecution func fetchAround( key: String, pageSize: Int, depthLevel: Int, direction: PageFetchDirection, listener: PaginatorFetchAroundListener<T>, keyPriority: FetchPriority, aroundPriority: FetchPriority ) -> PaginatorExecution } enum FetchPriority case high, medium, low
原書這一版的介面沒有列出 clear,應是只列與優先權有關的方法;Kotlin 有預設值、Swift 沒有,照原書。
原書 Step 4Priority-based task scheduling · Table 1
四種排程方式:原書選 Priority Queue
這一步要解決的問題「誰先」有四種做法,各自犧牲了什麼?右邊用同一批 request 比一比。
📖 原書 Table 1 實作優先權排程的取捨
| 選項 | 描述 | 優點 | 缺點 |
|---|---|---|---|
| 每個優先等級一個 queue | 每個 priority 專用 queue,依重要性依序處理 | 好實作好懂、優先權分離清楚;直接控制執行順序 | 等級變多、跨 queue 平衡變複雜時效能下降;記憶體開銷較高 |
| Priority Queue | 單一 queue,用 heap 自動維持優先順序;入列與出列時重排 | 排序有效率、架構簡單只有一個 queue;記憶體較低 | heap 重排可能有開銷;沒有公平性保證,低優先任務可能餓死 |
| 依等級分 ThreadPool | 每個 priority 一個 thread pool,高等級分到更多資源 | 硬體平行、真正的併發,資源利用較好;自然處理等級 | thread pool 管理複雜;資源需求較高 |
| Weighted Round-Robin | 循環處理,高優先任務分到較多執行時間 | 保證每個等級都會被處理、可預測;公平性好 | 權重調整複雜;高優先任務可能被延遲 |
📖 原書 Priority Queue pattern 是這個 library 的強力選擇:排序有效率、確保高優先先執行、實作簡單,適合行動裝置的限制。🔍 Industry insights Google 的 Volley 可以替 request 標 Priority,讓 immediate 的 request 在 queue 裡插隊。
白話:heap=一種自動把最急的放最上面的排法;starvation(餓死)=低優先的一直被插隊;thread pool=事先雇好的一組工人;round-robin=輪流。
動手比:6 個 prefetch(LOW)排隊中,使用者點了 2 下(HIGH)
每格一個時間單位、每個任務一格。示意模擬,不是原書的數字。
原書 Step 4Modular API design · Async framework compatibility layers
核心只用原生 callback;Coroutines、Combine、Rx 做成選配模組
這一步要解決的問題不同 app 用不同的「不站著等」寫法。library 要怎麼不強迫大家換?
📖 原書 設計 library 的兩個重要考量:處理好非同步、讓測試容易。Kotlin Coroutines 或 Swift Combine 都很強,很想整個 library 和公開 API 都建在其中一個上;但這會綁架用別的工具的人:想像一個 RxJava 的 app 為了用你的 library 被迫導入 Coroutines。
🛠️ 原書 平台實作細節
- Android:傳統 callback、Kotlin Coroutines 與 Flow、RxJava、LiveData、Java 的 CompletableFuture
- iOS:closure 完成處理器(callback)、Combine、async/await、delegate pattern、低階併發的 GCD
📖 原書 模組化
paginator-core:核心功能,零外部依賴paginator-coroutines、paginator-combine、paginator-rx:針對特定非同步方案優化
白話:Coroutines/Combine/RxJava=各家的非同步寫法;依賴=用了你,就得連它一起裝;artifact=發佈出去的一個套件檔。
好處:彈性(只裝需要的)、輕量核心(可攜)、原生整合(每個擴充都符合該框架慣例)。
動手試:你的 app 用哪一套?
🛠️ 原書 兩個平台的發佈方式不同
Android:Gradle 內建從同一份 codebase 產出多個 artifact,每個非同步整合發成獨立 artifact。iOS:傳統上一個 framework,但有三種方式做模組化:條件編譯、為不同非同步模式建立可選的擴充檔、用 Swift Package Manager 定義不同的 product 或 target。
這也讓 library 能迎接未來新的非同步範式,而不干擾既有實作。
原書 Step 4同一個 API,換上 Coroutines/async-await 的樣子
fetch 變成 suspend/async,fetchAround 變成一條 stream
這一步要解決的問題用 Coroutines 或 async/await 的 app,看到的 API 長怎樣?
📖 原書 Kotlin 使用 coroutines 與 flow
interface Paginator<T> {
suspend fun fetch(key: String, pageSize: Int): PaginatorPage<T>
fun fetchAround(
key: String, pageSize: Int,
depthLevel: Int, direction: PageFetchDirection
): Flow<PaginatorPage<T>>
suspend fun clear(key: String)
}📖 原書 Swift 使用 async/await
protocol Paginator {
associatedtype T
func fetch(
key: String, pageSize: Int
) async throws -> PaginatorPage<T>
func fetchAround(
key: String, pageSize: Int,
depthLevel: Int, direction: PageFetchDirection
) -> AsyncThrowingStream<PaginatorPage<T>, Error>
func clear(key: String) async throws
}動手試:collect 一次 fetchAround("5", depth 2, ALL)
listener 版本要你寫一個 PaginatorFetchAroundListener;Flow/AsyncThrowingStream 版本是「一條會陸續吐出頁的水管」,五頁依完成順序一頁一頁流出來。
📖 原書 這些都是擴充模組提供的寫法,不是 core 的寫法;core 仍是第 14 頁的 callback 版本。callback 沒了 listener 參數,結果改由回傳值或 stream 傳遞;PaginatorExecution 的取消也交給各框架原生的取消機制。
原書 Step 4Pagination library testing suite
另外發一個「只給測試用」的 artifact:附好 test double
這一步要解決的問題開發者要測「第 3 頁失敗」這種情況,難道要真的把網路弄壞?
📖 原書 介面/protocol 本來就好測試;但可以更進一步,提供專用的 testing-only artifact,內含:
- 預建 test double:模擬
PaginatorDataSource、PaginatorStore、PageValidator,不必自己寫 mock - Helper functions:產生範例分頁資料、模擬網路延遲
- 錯誤模擬:測失敗與 edge case 的處理和復原
白話:test double/mock=測試用的替身(第 6 頁的假廚房);edge case=少見的邊角情況。
📖 原書 對開發者的好處
- 不用自己建、維護客製的測試實作
- test double 自動跟著 library 更新同步
- edge case 好測,覆蓋率更高
- 展現對測試最佳實踐的承諾
📌 原書 Remember 測試 artifact 補足模組化,同時讓核心保持輕量;測試工具可以獨立演進,開發者拿到強大的測試能力,production build 卻不會變胖。
動手比:同三個測試,用 test double vs 打真的 API
🔍 原書 Industry insights
Google Jetpack Paging 3 也是類似做法:一條共用的 PagingData stream,可以依 app 需求變成 LiveData、RxJava Flowable 或 Kotlin Flow。iOS 的 Moya 從設計就考慮測試:每個 API endpoint 可以給 stubbed response 或 sampleData,單元測試不必真的打網路。
延伸基礎第 10 階 · invalidation懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
推車上的菜冷了、或廚房改了配方,還能給嗎?
① 先想像
每盤貼一張標籤「端來後 10 分鐘內有效」。廚房也可能喊「第 2 盤改了」,那盤就算沒過時也不能給。
你猜猜看:12:05 端來、10 分鐘有效。12:20 客人要,推車上那盤能直接給嗎?
12:15 就過期了。推車上有,不代表還能用。
③ 這叫做 invalidation、expiration
invalidation(作廢):把推車上不能再用的那盤丟掉,下次重端。expiration time:標籤上的「幾點前有效」,也常叫 TTL。TTL:03-sdi 11 章
④ 跟這章的關係
原書的頁帶 expirationTime,PageValidator 檢查,clear(key) 手動作廢。Triton 會問:能不能讓舊頁根本不會變(第 46 頁)?
② 動手玩:時間在走,廚房在改
原書 Step 4Handling failure points
五個會壞的地方:壞的時候要優雅降級,不要 crash
這一步要解決的問題網路、DB、快取、併發、key:哪裡會壞?壞了怎麼不讓 app 當掉?
| 失敗點 | 📖 原書的緩解措施 |
|---|---|
| 網路失敗:逾時、斷線、server error | 指數退避的 retry;仍失敗就由 callback 傳詳細錯誤,讓開發者退回快取或顯示友善訊息 |
| 資料庫錯誤:本地查詢失敗、資料損壞 | PaginatorDataSource 內建錯誤處理,經 callback 回報;可設定退回過期的快取資料 |
| 快取不一致:過期或損壞的快取頁 | PageValidator 用過期時間或 checksum 檢查;無效就 invalidate 並重抓;搭配可設定的淘汰策略 |
| 併發問題:多執行緒同時存取 | thread-safe 結構(例如 concurrent map)與同步機制,保護記憶體快取與 Store |
| 無效的 page key:cursor/keyset 分頁裡,資料更新後 key 過期或格式錯 | 處理前先驗證 key,經 callback 回傳清楚的錯誤,引導開發者例如重設到已知起點 |
白話:指數退避=隔 1、2、4、8 秒再試;checksum=內容的指紋,一改指紋就變;invalidate=作廢(第 36 頁);crash=app 當掉閃退。
📖 原書 Last notes 這些措施以使用者體驗優先,失敗時優雅降級;PaginatorConfig 加上 analytics 與 logging 選項,方便在 production 監控與排查。
動手試:進隧道 N 秒,指數退避怎麼 retry
每次等待 1、2、4、8… 秒(base 1 秒、倍數 2),示意,原書沒有給數字。文組翻譯:打電話沒人接,不要每秒狂打,隔 1 分、2 分、4 分再打;真的打不通,就先看手邊那份舊資料。
原書 Step 4Versioning · SemVer · CalVer
開源之後,每一次改動都要說清楚:會不會弄壞你的 app?
這一步要解決的問題開源之後,別人的 app 依賴你。改一行,要怎麼讓他們一眼看出會不會壞?
📖 原書 清楚的版本策略是開發者信任與長期採用的關鍵。採用 SemVer 的 MAJOR.MINOR.PATCH:
- MAJOR(X.y.z):破壞性變更,要改程式。例如修改 Paginator 介面或改變預設快取行為
- MINOR(x.Y.z):新增功能、保持相容。例如增強 PaginatorConfig 而不破壞既有整合
- PATCH(x.y.Z):修 bug、小修補,不改變行為
🛠️ 原書 平台實作細節
iOS 與 Android 都強烈偏好 SemVer。Swift Package Manager 以 SemVer 為依賴解析的基礎,用別的方案會造成相容問題。Android 的 Gradle、Maven 也設計成和 SemVer 無縫合作,自動解版本衝突。沒有 SemVer,就失去這些工具的依賴管理能力。
📖 原書 其他策略:Jetpack Compose 的 CalVer BOM
個別 Compose library(compose-ui、compose-material、compose-foundation…)嚴格用 SemVer;另外提供一個 BOM(Bill of Materials),版本是 CalVer 的 YYYY.MM.PATCH,例如 2025.02.00 對應一組相容版本(compose.animation:1.7.8、compose.material3:1.3.1 等),保證整組相容。
動手考:這次改動該升哪一碼?
原書 Step 5Wrap-up
原書的收尾:還有時間,可以再挑戰這五題
這一步要解決的問題主體設計完,面試官常追問的延伸題。
📖 原書 本章設計的分頁 library 支援
- 任何類型的 app 資料
- 不同分頁技術:offset-based、cursor-based
- 本地與遠端資料來源
定義了公開 API,設計了穩健、可擴展、可延伸的架構,涵蓋快取、API 呼叫優先順序、失敗點、測試與版本控制。
回頭看整章:原書花最多篇幅的是 library 對開發者的契約(泛型、callback、class、模組、SemVer)。它幾乎沒談的是 library 對 server 的契約:key 到底長什麼樣、server 怎麼保證同一個 key 永遠回同一頁。下一段就是 Triton 談的這一半。
📖 原書 進階題(點一題看提示)
- UI 層的分頁支援:整合 table view、collection view、捲動元件
- 快速捲動:在大資料集裡快速移動,像長清單跳過整個區段
- 背景服務:app 閒置或在背景時預取頁面
- 自訂錯誤處理:失敗時的重試、退回快取、警示
- 部分頁面載入:資源有限時只載入一頁的一部分
提示文字是本簡報補充的思考方向,不是原書內容。
到這裡你已經會了小結 4 / 5
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
到這裡你已經會了:原書的完整設計
- 使用者在等的那頁先出(priority)。原書選 Priority Queue;代價是先備著的可能一直被插隊。
- 核心零依賴,Coroutines、Combine、Rx 做成選配模組;另外發測試用的 test double;用 SemVer 告訴別人「會不會壞」。
- 頁會過期或被改(invalidation):PageValidator 用過期時間或 checksum 判斷,無效就丟掉重抓。
下一階要解決的問題
原書幾乎沒談廚房那一端:key 到底長怎樣?為什麼有的 key 一來新資料就全部作廢?DB 怎麼找得快?接下來是 Triton。
Triton 觀點先說清楚他有講、沒講什麼
原書寫 library 對開發者的契約;Triton 寫的是 key 對 server 的契約
| 原書段落 | Triton 的資料 | 本簡報 |
|---|---|---|
| key 可以是 offset 或 cursor | 143 order by、087 snapshot、074 | 第 42 頁 |
| Performance(效能) | 104 Range Scan on PK、062 PK、009 筆記 | 第 44 頁 |
| key 的形狀、Invalid page keys | 062 lastTs/nextPageTs、009 筆記 毫秒、027 400 | 第 45 頁 |
| 快取、PageValidator、expirationTime | 062 Caching with pagination、009 筆記 | 第 46 頁 |
| 一直在變的清單 | 087 ?ts= snapshot、v1/v2、localcache | 第 47 頁 |
PageFetchDirection FORWARD/BACKWARD | 078 minMsgId、062 用戶流程 | 第 48 頁 |
| 「cursor」這個字 | 037(只取 Triton 的短句)、027 stateless、304 | 第 49 頁 |
| 泛型、callback、class vs data class、Scheduler、Evictor、Priority Queue、模組、測試、SemVer | 無 | 照原書講,不硬套 |
怎麼讀接下來幾頁
🗣️ Triton 本人說 是 materials/core 裡 Triton 講義或文章的原文,附檔名。📝 上課筆記 是 Roy 的筆記(009),不是 Triton 原文。🔭 依 Triton 原則推論 是把他的原則套到這章,不是他說過的話。
和 03 News feed app 簡報的分工
那份玩過「新貼文插進來,offset 重複」,也看過 062/087 的引文與「重開 app 要重抓幾頁」(本簡報的入門版在第 5 頁)。這裡往下挖四件事:刪除造成的漏看、DB 為什麼 offset 慢、062 的分頁快取怎麼設計、兩個方向的 cursor。
提醒:常被引用的「若用 page id 會隨著時間回傳內容不同…很難做 cache」出自 009(Roy 的上課筆記),不是 062 講義本身;「lastTs ⇒ lastMs(毫秒)」也只在 009。
Triton 補充原書只說「key 可以是 offset」,沒說 offset 會壞在哪
新增會讓 offset 重複,刪除會讓 offset 漏看
原書這樣做會出什麼事?key 用 offset。你讀完第 1 頁(4 則),有人刪掉其中 2 則。下一頁 OFFSET 4 會怎樣?
後面的全部往前擠 2 格,原本的第 5、6 則被擠進「已讀」的位置,OFFSET 4 直接跳過它們。右邊按「刪掉已讀的 2 則」驗證。
「學SQL的都會知道:用上limit(和offset)時,一定會配上order by clause的。…在沒配上order-by時,其排序是根據底層data storage的排序」🗣️ Triton 本人說 143-喵談一道SQL面試題….md · 第 3 點
「想像一下:你在看一個持續改動中的排名榜 如果沒有 snapshotting,剛好第十名的物品變第十一,然後你拿 Page 2的資料 – 你就會看到重覆的物品」🗣️ 087-redis-2019.pdf.md · 案例 2:data snapshotting
🔭 推論 087 講的是「往後掉一名 → 重複」;反方向一樣成立:已讀範圍裡有東西被刪掉,後面的全部往前擠,第一個沒看過的那一則就被擠進「已讀」的位置,下一頁永遠拿不到它。Keyset(WHERE createTs < :lastTs)的錨點是一個值,不是一個位置,所以兩個問題都沒有。前提是 143 說的:排序要明確、而且唯一(第 45 頁)。
OFFSET
keyset
每頁 4 則,新到舊。紅框 = 重複看到;底下的「漏掉」= 資料還在,但這個分頁方式永遠不會給你。
延伸基礎第 11 階 · index懂的人可以跳過
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
電話簿:找「下一位」很快,找「第 50,001 位」很慢
① 先想像
一本電話簿 1,000 頁、每頁 100 個名字,照姓名排好,最前面有一張「哪個字開頭在第幾頁」的目錄。
你猜猜看:找「第 50,001 個人」要翻過幾頁?找「王小明後面那位」呢?
「第幾個」沒有目錄可查,只能一頁一頁數過去。「某個名字的下一位」查目錄,直接翻到那一頁。
③ 這叫做 index、B+tree
index(索引):照順序排好、附目錄,直接翻到某個值。B+tree:資料庫的多層目錄,走 3 層就到那一頁。B+tree:03-sdi 07 章照 PK 排:11 章
④ 跟這章的關係
OFFSET 是「數到第幾個」;書籤是「從這個值往下」。Triton 說的 Range Scan on PK 就是後者(下一頁)。
② 動手玩:要第幾位?
Triton 補充原書的非功能需求寫了 Performance,但只談 client
OFFSET 100000:DB 先讀十萬列,再丟掉十萬列
原書這樣做會出什麼事?滑到第 5,001 頁(每頁 20 則),OFFSET 100000 LIMIT 20。DB 為了回你 20 列,要讀幾列?
OFFSET 不是「跳過」,是讀了再丟,就像電話簿數到第 100,001 個(第 43 頁)。書籤直接查 index,只讀 20 列。
「MySQL innoDB的底層結構是Index-organized-table,資料是以Primary Key來順序排列的。所以,Range Scan on Primary Key能使用Sequential IO對tablespace作局部掃瞄,效能非常快的。」「Random IO是Sequential IO的1 / 10效能也沒有。」🗣️ Triton 本人說 104-利用Range Scan on Primary Key的好處.md · 第 2、3 點
「一定是 (chatroomId, createTs) – 相同 chatroom 的 message 一定會物理相鄰 而且相同 chatroom 的 message 會以時間來排序」「PostgreSQL 不是好選擇,因為其 table 底層是 heap」🗣️ 062-im-system design.pdf.md · Message Primary Key、Database
「有笨蛋會把整個 resultset放到 application tier,然後把用戶想要的第1-100筆資料傳給用戶 – 絕對別做這種笨事」🗣️ 074-lesson4.pdf.md · Window function背景
白話:IOT=資料照 PK 排在一起(圖書館照書號上架);heap=有空位就放(倉庫),要另一本目錄(secondary index)找(03-sdi 07 章);sequential/random IO=照順序讀/東翻西找。
📝 上課筆記「因為每次拉50的話,中間還是要 offset limit 才能分頁 ? A: lastTs ⇒ lastMs (毫秒」009
假設每個 data page 放 100 列、B+tree 3 層;random IO 用 104 的「1/10」換算成 10 個 sequential IO。數字是示意,方向依 104 與 062。
Triton 補充原書的 key: String 到底該放什麼
key = 上一頁最後一則的毫秒時間戳;同一毫秒就重送
原書沒說書籤要多精確。時間戳只到「秒」,第 4、5 則都是 10:00:03,頁剛好切在中間。下一頁 createTs < 10:00:03 會怎樣?
「比 10:00:03 更早」不包含同一秒的第 5 則,它永遠不會出現。右邊選「精確到秒」按下一頁看看。
「GET /v1/chatrooms/<roomId>/messages – Optional parameter: lastTs – Chronological descending order – 支持 pagination ,返回大約上限 50 個訊息 除了 array of message ,還會有 nextPageTs」🗣️ Triton 本人說 062 · 訊息相關 endpoint
「Q 為什麼不給 msgid 然後用 msgid 當作 api 的參數? 感覺效果和 nextPageTs 一樣? MySQL / HBASe index organize table(IOT) order by key 所以是用 composite key 若為了預防同一秒發 createTs ⇒ ms 若一樣時間 就 failed 掉,再重發 request 晚一秒」📝 上課筆記 009 · Roy 的 MVP IM 課堂筆記,非本人原文
🔭 推論 對到原書:PaginatorPage.nextKey 就是 062 的 nextPageTs,key 就是 lastTs,第一頁 key 為 null。因為 PK 是 (chatroomId, createTs),同一聊天室裡 createTs 唯一,「從這個時間往前 50 則」永遠是同一組,key 不會像 offset 那樣「過期」。原書的 Invalid page key(第 37 頁)就剩格式錯:027 的 400「請求的內容有誤,伺服器拒絕執行 – 例子: Age 這個資料應該是 Integer 的,客戶端卻傳來 ABC123」正好對上 lastTs=abc。
動手試:時間戳只精確到「秒」會怎樣?
Triton 補充原書的 PageValidator 與 expirationTime,在 server 端怎麼做
只有最新那一頁會變:062 的分頁快取
原書這樣做會出什麼事?快取 key 用頁碼。聊天室來了一則新訊息,快取裡的 10 頁要作廢幾頁?
新訊息擠進最前面,每一頁的內容都往後移一格,10 頁全部不對了。062 用 lastTs 當 key:舊頁永遠不變。
「在同一個 chatroom ,所有用戶都應該看到相同 的聊天歷史 – 這明顯是 caching 的好機會」「chatroomId-<id>-pageList – 儲存之前 N 個 cache-page 的 lastTs chatroomId-<id>-now – 最近(最多) 50 個 messages – 上一個 page 的 nextPageTs chatroomId-<id>-<lastTs> – 從 lastTs 往前的 50 個 messages」🗣️ Triton 本人說 062 · Caching with pagination、Cache design
GET:「如果 lastTs parameter 是 null – 直接用 chatroomId-<id>-now 否則,先看看有沒有對應的 chatroomId-<id>-<lastTs> record … 否則,拿 chatroomId-<id>-pageList」POST:「先拿 global lock on chatroomId 看看現在 chatroomId-<id>-now 是否滿 50 messages 如果沒滿, append 進 chatroomId-<id>-now 就好」🗣️ 062 · Cache demo(GET)、Cache demo(POST)
「若用 page id 會隨著時間回傳內容不同,因為下一秒又發新的 msg 這樣很難做 cache, cache 就會 invalidate」📝 上課筆記 009 · 非本人原文
🔭 推論 把 062 的 50 則縮成 5 則方便看;「頁滿時以最後一個 lastTs 建新 cache-page」的細節依投影片第 13–15 頁解讀。套回原書:舊頁永遠不會變,PageValidator 的 expirationTime 只需要給最新那一頁。
Triton 補充有些清單沒有「時間戳」可以當錨點
一直在變的排行榜:帶 ?ts=,翻頁翻的是同一張快照
原書這樣做會出什麼事?排行榜一直在變、不帶 ts。你看完第 1 頁,第 5 名掉到第 7 名。翻第 2 頁會怎樣?
他掉進第 2 頁的範圍,所以重複;原本第 6 名被擠上第 5 名,落在你讀過的第 1 頁,所以漏看。右邊試試看。
「RESTful endpoint: – GET /v1/leaderboard?ts=1561042015」「建立 crontab,每一分鐘從資料庫拿建立新的 snapshot 丟到 redis …DataXXX-<ts>是一個 hashSet – P1是對應第 1 – 50個 items – P2是對應第 51 – 51個 items」🗣️ Triton 本人說 087 · 案例 2、Snapshotting with redis v1(「51 – 51」照原文)
「如果資料長期沒有改動, v1只會建立大量重覆的 snapshots 如果一份 snapshots跟之前相同,它只需把該 ts存起來,而 不用存相同的資料」「snapshot是永遠不會改動的資料 所以,其 localcache TTL應該跟 Redis 相同的」🗣️ 087 · v2、延伸:localcache on snapshot
白話:snapshot=某個時間點拍下來、之後不會變的一份;crontab=定時鬧鐘,每分鐘跑一次;Redis=放在記憶體裡的共用白板(03-sdi 04 章)。
🔭 推論 對到原書:排行榜按分數排、分數一直在變,keyset 的「錨點值」本身會移動,所以改成「錨點是時間」:第一頁回應帶 ts,之後每一頁都帶同一個 ts。這時原書的 key 要包含 ts 和頁碼兩部分;因為快照不變,expirationTime 可以跟快照的保存時間一樣長,這就是 087 說的 localcache TTL。
使用者看到的
Redis 裡的快照
Triton 補充原書的 PageFetchDirection:FORWARD 和 BACKWARD
往上滑拿更舊的(lastTs),重連後補更新的(minMsgId)
原書的 direction 有 FORWARD/BACKWARD。在隧道裡斷線 30 秒、來了 3 則,出隧道後最省的補法?
重抓 50 則,有 47 則是已經有的,斷線太久還補不齊;斷線期間的推送沒人幫你留著。078 用 minMsgId 只拿缺的那一段。
「用戶要補回離線期間留言 – GET /v1/chatrooms/{roomId}/messages?minMsgId=X – 從MariaDB拉回留言」🗣️ Triton 本人說 078-mq-intro.pdf.md · 基於 RESTful design
「– 在 websocket 對 subscription – 把收到的 message 先 buffer 起來 – 拿最近 50 個 messages GET /v1/chatrooms/<roomId>/messages – 把最近 50 個 messsage 和 buffered message 作 sorting + deduplication 然後顯示給用戶」🗣️ 062 · 用戶流程(「messsage」照原文)
🔭 推論 同一條清單有兩個方向的錨點:頂端用 lastTs 往更舊的走(原書的 BACKWARD,也就是 scroll-up),底端用 minMsgId 往更新的走(FORWARD,離線補齊)。兩種 key 都是「值」不是「位置」,所以兩頭同時有人寫入也不會亂。PaginatorPage 的 prevKey/nextKey 剛好放這兩個值。重連補資料和 WebSocket 的去重細節,04 Chat app 簡報已經講過,這裡只看方向。
Triton 補充「cursor」這個字有兩個意思
DB 的 cursor 住在連線裡;API 的 cursor 寫在網址上
「比如我要為10億筆record做統計,而那統計的algorithm不是簡單的sum / count,沒法有效用SQL寫出來 在oracle / pg我用cursors來掃瞄一次便好 在mysql,我要每次拿10000筆筆料(比如說用id between startPos and endPos這樣)…不過想吐嘈:cursor需要db driver +你的orm支持,我用的orm不支持cursor......」🗣️ Triton 本人說 037-Server side cursor.md · 第一段(後面是貼上的 ChatGPT 回答,不引)
「server side 需要 stateless – 正解 1 : HTTP 只要求 protocol 本身是 stateless ,從未要求伺服器是 Stateless – 正解 2 : RESTful 只要求 Application Server 是 stateless , Server Side 其他部份可以 stateful」🗣️ 027-RESTful API Design-tw-2.1.pdf.md · 先談 RESTful謬誤
027 對分頁 API 的三條規則
- 「只有 GET 才應該使用 Query String 的(很重要)」:
?lastTs=只能出現在 GET - 「如果是 GET collection 而沒搜查到滿足條件的物件,是應該返回 200 ,而不是 404 的」:最後一頁之後是 200 + 空陣列
- 304:「客戶端會發出 Conditional-GET ,在 HTTP header 中加入 If-Modified-Since: <某時間>」🔭 最適合
-now那一頁
027 · HTTP method-GET、4xx、3xx
原書這樣做會出什麼事?原書寫 cursor-based。如果真的開一個 DB 的 server-side cursor,第 2 頁被分到另一台 AS,會怎樣?
DB cursor 住在第一台 AS 的那條 DB 連線裡。API 的 cursor(lastTs)寫在網址上,哪一台都能接,AS 保持 stateless(自己不記事,03-sdi 01 章)。
🔭 推論 037 的 cursor 是 Triton 拿來批次統計十億筆資料的 DB 功能,狀態住在那條 DB 連線裡;原書和 Triton 講的 API 分頁「cursor」是一個值,狀態在 client 手上。037 裡 MySQL 的做法「id between startPos and endPos」反而跟 keyset 是同一個想法。
到這裡你已經會了小結 5 / 5
- page size
- offset / cursor
- library
- callback
- prefetch
- cache
- memory / disk
- eviction
- priority
- invalidation
- index
到這裡你已經會了:Triton 補上的廚房那一端
- offset 新增會重複、刪除會漏看;書籤(keyset)的錨點是一個值,不是一個位置。時間戳要精確到毫秒。
- DB 照 PK 排好(index),書籤直接查目錄、順著讀一頁;
OFFSET 100000要讀十萬列再丟掉。 - key 用書籤,舊頁永遠不變,只有最新那頁會作廢;會變的排行榜帶
?ts=快照;兩個方向各一個書籤。
11 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
對開發者:一個 Paginator<T>、三個方法、兩層快取;
對 server:key 是一個值,不是一個位置。
原書的 library
fetch/fetchAround/clear,key 對分頁技術中立- callback +
PaginatorExecution;public class 不用 data class - CallbackPaginator + DataSource/Validator/Store/Config
- 記憶體 → 磁碟 → DataSource;Loading/Success/Error
- Priority Queue、核心零依賴、testing artifact、SemVer
Triton 補上的 server 契約
lastTs/nextPageTs,descending、約 50 則(062)- PK
(chatroomId, createTs),range scan 是 seq IO(062、104) - 舊頁不變、只有
-now會變的分頁快取(062) - 會變的清單用
?ts=snapshot(087);補離線用minMsgId(078)
原書沒談、會被追問
- 刪除造成 offset 漏看(🔭 由 087 推)
OFFSET 100000的成本(104)- 時間戳要毫秒、同一毫秒重送(009 📝)
- DB cursor ≠ API cursor(037、027)
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與原書對照
引述來源(materials/core)與原書段落
Triton 本人的講義/文章
- 062-im-system design.pdf.md — 訊息 endpoint:
lastTs、descending、約 50 則、nextPageTs;Database(heap);Message PK(chatroomId, createTs);Caching with pagination、Cache design、Cache demo(GET/POST);用戶流程 sorting + deduplication - 087-redis-2019.pdf.md — 案例 2 data snapshotting、
GET /v1/leaderboard?ts=1561042015、Snapshotting v1/v2、localcache on snapshot - 078-mq-intro.pdf.md —
GET /v1/chatrooms/{roomId}/messages?minMsgId=X補回離線期間留言 - 104-利用Range Scan on Primary Key的好處.md — IOT、Range Scan on PK 是 sequential IO、random IO 不到 1/10
- 143-喵談一道SQL面試題….md — limit/offset 一定要配 order by
- 074-lesson4.pdf.md — 別把整個 resultset 放到 application tier 再切頁
- 027/028-RESTful API Design — 只有 GET 用 query string、空 collection 回 200、400、304 Conditional-GET、RESTful 謬誤(stateless)
- 037-Server side cursor.md — 只有第一段是 Triton(DB cursor 做批次統計、MySQL 用 id between);後面整段是 ChatGPT,不引
上課筆記(非本人原文):009(Roy 的 MVP IM 筆記:page id 難 cache、lastTs ⇒ lastMs、composite key、同一毫秒失敗重送)。PDF 轉出的「⽤」「⼀」「⾴」等部首字元,引用時寫成一般字;PDF 換行造成的多餘空格(如 074「然 後」)已去掉。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 11 階:page size(4)、offset/cursor(5)、library(6)、callback(13)、prefetch(17)、cache(20)、memory/disk(21)、eviction(23)、priority(30)、invalidation(36)、index(43);小結(7、19、29、40、50);名詞小卡(52)。阿美熱炒是虛構情境,數字是示意;另連到 03-sdi 01、02、04、07、11、12、13 章。
原書對照
Mobile System Design Interview,Chapter 6 Pagination library。開頭與 Pro tip(第 8 頁);Step 1 對話(9)、Requirements(10);Step 2 API design、Paginator 與泛型(11)、三個方法與 key 中立(12)、Data propagation(14)、Data models 與 Pro tip(15)、How apps implement(16)、fetchAround(18)、Creating configurable instances(22)、eviction policies(24);Step 3 Figure 1、Scheduler、Evictor(25);Step 4 In-memory caching(26)、Dual caching 與 Figure 2(27)、Benefits and considerations、Industry insights(28)、Priorities(31)、Table 1(32)、Async compatibility layers(33–34)、Testing suite(35)、Handling failure points(37)、Versioning 與 CalVer(38);Step 5 Wrap-up(39)。原書 2 張圖依 alt 描述重繪,不是原圖;Table 1 與所有 Kotlin/Swift 介面照列。
原書參考資料:[1] Test double · [2] Jake Wharton, Public API Challenges In Kotlin · [3] Swift ABI Stability Manifesto · [4] Swift Library Evolution (SE-0260) · [5] Store5 · [6] Hyperoslo Cache · [7] Jetpack Paging 3 · [8] Priority Queue pattern · [9] Optimizing Android Volley · [10] Moya · [11] Handling network calls with Moya · [12] SemVer · [13] SPM PackageDescription · [14] Jetpack Compose
一個可以直接問自己的問題
有人在你讀第 3 頁的時候刪掉第 1 頁的一則貼文,你的第 4 頁會少誰?如果答案不是「沒有人」,你的 key 還是一個位置,不是一個值。