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

  1. 1page size一盤端幾道
  2. 2offset / cursor記第幾道 vs 夾書籤
  3. 3library中央廚房的醬料包
  4. 4callback取餐呼叫器
  5. 5prefetch快吃完就去端
  6. 6cache桌邊推車
  7. 7memory / disk推車 vs 倉庫
  8. 8eviction推車滿了收哪盤
  9. 9priority在等的先出
  10. 10invalidation冷了、改了就作廢
  11. 11index照順序排的電話簿

第 1–3 階 · 一盤一盤端

要回答:一盤幾道?下一盤從哪接?

第 4–5 階 · 端菜不卡住

要回答:等菜時能做別的嗎?何時先去端?

第 6–8 階 · 推車和倉庫

要回答:端過的盤子放哪?滿了收哪盤?

第 9–11 階 · 廚房那一端

要回答:誰先出?何時作廢?DB 怎麼找得快?

全程只用一家店:阿美熱炒(虛構)

一道菜 = 一則貼文/訊息一盤 = 一頁(page)服務生跑一趟 = 一個 request桌邊推車 = 記憶體快取後面倉庫 = 磁碟快取廚房 = server + DB書籤 = cursor

每爬 2–3 階,有一頁「到這裡你已經會了」。

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

  1. page size
  2. offset / cursor
  3. library
  4. callback
  5. prefetch
  6. cache
  7. memory / disk
  8. eviction
  9. priority
  10. invalidation
  11. index

桌上一眼看得到 8 道菜,服務生一盤該端幾道?

① 先想像

客人的桌子(手機螢幕)一眼看得到 8 道菜。服務生每跑一趟,不管端幾道,都要先花 2 秒。

你猜猜看:客人想看 40 道,一盤端 10 道,服務生要跑幾趟?

③ 這叫做 pagination、page size

pagination(分頁):長長的清單,一次只拿一段。page size:一段拿幾筆,就是一盤端幾道。

④ 跟這章的關係

原書的 fetch(key, pageSize) 讓呼叫的人自己決定。至少要比一個螢幕多,不然一打開就得再跑一趟。

② 動手玩:一盤幾道?

4服務生跑幾趟–第一個螢幕要等–白做的菜

示意:每趟 2 秒,每道多 0.1 秒。

延伸基礎第 2 階 · offset / cursor懂的人可以跳過

  1. page size
  2. offset / cursor
  3. library
  4. callback
  5. prefetch
  6. cache
  7. memory / disk
  8. eviction
  9. priority
  10. invalidation
  11. index

端完上面 4 道,下一盤從哪一道接?

① 先想像

菜單照時間排,最新的在最上面。服務生端完上面 4 道,記下「下次從第 5 道開始」。這時廚房在最上面又加了 2 道新菜。

你猜猜看:下一盤的「第 5 道」是哪一道?

③ 這叫做 offset、cursor

offset:記「從第幾道開始」,像看書記「看到第 N 頁」。cursor:夾書籤,記「最後一道是哪一道」,例如它的時間。03-sdi 11 章的版本

④ 跟這章的關係

原書的 key 兩種都能放。Triton 的講義用時間戳當書籤;offset 連「刪掉」都會出事(第 42 頁)。

② 動手玩:兩種記法

    延伸基礎第 3 階 · library懂的人可以跳過

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    中央廚房做好醬料包,分店照同一張點單用

    ① 先想像

    阿美開了三家分店。點單格式早就講好:「要哪一盤、一盤幾道」。至於菜從廚房、冷凍庫,還是練習用的假廚房來,點單不管。

    你猜猜看:今天改從冷凍庫拿菜,不從廚房拿。點單要重寫嗎?

    ③ 這叫做 library、interface

    library:別人寫好、你直接拿來用的工具包(醬料包)。interface:事先講好的點單格式,只說要什麼,不說怎麼做。

    ④ 跟這章的關係

    原書的 Paginator 就是一個 interface。這章的使用者不是滑手機的人,是寫 app 的工程師。

    ② 動手玩:同一張點單,換三個供菜的地方

    
          
    0app 的程式改了幾行0.8 秒這次拿到要多久(示意)

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

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    到這裡你已經會了:一盤一盤端

    下一階要解決的問題

    原書在面試一開始問了什麼?這個工具包要有哪些功能、哪些不做?

    原書開頭為什麼要做一個「可重用」的分頁 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

    0要修幾個地方–三個 app 行為一致嗎

    文組翻譯:三家分店各自寫食譜,鹽放太多要改三本;中央廚房只要改一本,三家的味道也一樣。

    原書 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 階),叫法都一樣。

    📖 原書公開 API 第一版
    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

    📖 原書 三個需求對三個方法:取單一頁(fetch)、取周圍的頁做 prefetch(fetchAround)、從快取清掉特定頁(clear)。方法都是 idempotent:相同輸入重複呼叫,結果相同。

    動手試:同一行 fetch,背後是兩種分頁

    
          

    📖 原書 key 刻意設計成有彈性的 String:offset 分頁時是整數字串,cursor 分頁時是指向下一組資料的 token。不論資料來源用哪一種策略,開發者都用同一個介面。

    💡 原書 Pro tip 把 Paginator 定義成 interface/protocol,不只是入口,也讓測試變容易:開發者可以做 test double 模擬各種情境(第 35 頁)。

    延伸基礎第 4 階 · callback懂的人可以跳過

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    點完餐,站在櫃台前等,還是拿呼叫器?

    ① 先想像

    美食街點完餐,可以站在櫃台前乾等;也可以拿一個呼叫器去找位子,好了它會震。不想吃了,把呼叫器還回去就好。

    你猜猜看:餐要 3 秒才好,你每秒能滑一次手機。站著等能滑幾次?拿呼叫器呢?

    ③ 這叫做 async、callback

    async(非同步):交代完就去做別的,不站著等。callback:事先留給對方的呼叫器,好了它叫你。

    ④ 跟這章的關係

    原書每個方法都帶一個 listener(呼叫器),回傳一個可以 cancel 的 PaginatorExecution(還回呼叫器)。

    ② 動手玩:等餐 3 秒

    0等餐時滑了幾次
    
        

    原書 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)
    }

    動手試:使用者滑到一半就離開畫面

    
          

    📝 原書 Note 開源 library 要小心依賴

    你引入的任何第三方 library,都會變成使用你的 app 的必要依賴。核心功能用語言原生的結構,同時保留擴充性,能和熱門 library 搭配(第 33 頁)。

    📖 原書 內部每個 Paginator instance 有一個 thread-safe 的快取(好幾個工人同時存取也不會亂),通常是一個把 page key 對到資料的 Map,加速存取最近載入的頁(第 26 頁)。

    原書 Step 2Data models · PaginatorPage

    一頁 = 內容 + 自己的 key + 前後頁的 key + 何時過期

    這一步要解決的問題一頁拿回來,除了內容還要帶什麼,app 才知道下一頁從哪接、這一頁何時過期?

    📖 原書 PaginatorPage

    KotlinSwift
    public class PaginatorPage<T>public class PaginatorPage<T>
    content: List<T>content: [T]
    key: Stringkey: 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 裡

    1. 用 CallbackPaginator 建立設定好資料來源的 Paginator instance
    2. 在使用者動作(例如捲動)時呼叫 Paginator 的方法
    3. 把多個 PaginatorPage 合併成一條清單
    4. 監看分頁狀態,判斷何時該載入更多
    5. 處理各種狀態:loading、error、empty

    白話:repository/state holder=app 裡負責「拿資料、記住畫面現在長怎樣」的那一層。

    📖 原書 線性情境(一路往下捲)主要用 fetch 依序載入;非線性情境用 fetchAround 預先抓目標頁周圍。責任分離:Paginator 專心做擷取與快取,app 負責呈現與互動。

    畫面上的那一條清單

    State Holder 手上的 PaginatorPage

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

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    客人吃到剩幾道,服務生就該去端下一盤?

    ① 先想像

    客人每秒吃 1 道,一盤 6 道;服務生端一盤要 3 秒。等盤子見底才出發,客人就要空等。

    你猜猜看:剩幾道時出發,客人剛好不用等?

    ③ 這叫做 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;數字是示意,不是原書的。

    –看到空白畫面的時間–載了沒看的頁–總 request 數

    到這裡你已經會了小結 2 / 5

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    到這裡你已經會了:原書的 API,和端菜不卡住

    下一階要解決的問題

    端回來的盤子放哪?客人回頭要、或明天再來,要不要重跑廚房?

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

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    剛端過的那盤,客人回頭又要

    ① 先想像

    服務生把端過的盤子放在桌邊推車上。客人說「剛剛那盤再給我看一下」,伸手就拿到,不用跑廚房。

    你猜猜看:跑廚房 2 秒、推車 0.1 秒。客人要第 1 盤 3 次(第一次推車是空的),共等幾秒?

    ③ 這叫做 cache、hit/miss

    cache:手邊的暫存區,拿得快,正本在 server。hit/miss:推車上有/沒有,要跑廚房。server 端的版本:03-sdi 01 章

    ④ 跟這章的關係

    原書每個 Paginator 裡都有一台推車:一張「key → 那一頁」的對照表(第 26 頁)。

    ② 動手玩:客人要第幾盤?

    0hit0miss(跑廚房)0 秒總共等了

    延伸基礎第 7 階 · memory / disk懂的人可以跳過

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    推車打烊就收掉,倉庫明天還在

    ① 先想像

    推車就在桌邊,拿得最快,但放不多,打烊就清空。後面的倉庫大,走過去要一點時間,明天開門東西還在。

    你猜猜看:把 app 從背景滑掉再打開。剛剛看過的 3 頁,記憶體裡還在嗎?磁碟裡呢?

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

    動手組:兩個畫面、兩個 instance、兩套設定

    
          

    📝 原書 Note 不用靜態設定 Paginator.init(...)

    有些 library 用全域的靜態設定;但每個 Paginator instance 需要獨立且高度客製的設定,所以選擇 instance 層級的設定。文組翻譯:不是全公司共用一台冷氣的溫度,是每間會議室自己調。

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

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    推車只有 3 格,第 4 盤來了,要先收哪一盤?

    ① 先想像

    推車上放著第 1、2、3 盤,第 3 盤是最後端來的。客人剛剛又夾了第 1 盤一口。現在第 4 盤端來了。

    你猜猜看:收哪一盤,客人最不會想念?

    ③ 這叫做 eviction、LRU

    eviction(淘汰):滿了要騰位子,選一盤收掉。LRU(least recently used):收最久沒被碰的那一盤。

    ④ 跟這章的關係

    原書內建 LRU、FIFO、LIFO,也能自己訂規則(下兩頁)。

    ② 動手玩:點一盤 = 客人夾一口

    第 4 分鐘現在

    原書 Step 2Eviction policies

    推車只放得下幾盤:LRU、FIFO、LIFO,或自己寫規則

    這一步要解決的問題記憶體放不下全部的頁,滿了要先收哪一頁(第 8 階 eviction)?

    
          
    0cache hit0miss(要打網路)

    📖 原書 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、誰負責收盤子?按播放看兩種線。

    📖 原書 Figure 1分頁 library 高階架構:灰底是開發者提供的實作,白底是 library 提供的實作(依原書內容重繪)

    📖 原書 圖例:實線是資料流、虛線是依賴、指向框外的箭頭是對外溝通。結構要優先考慮模組化、可擴展、可維護。

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

    先看推車、再看倉庫、最後才叫廚房:雙層快取的六步

    這一步要解決的問題要一頁時,先看推車(記憶體)、再看倉庫(磁碟),最後才打網路。按播放,一步一步看。

    📖 原書 Figure 2Paginator 在快取未命中時的資料流(依原書內容重繪;步驟順序依內文,alt 把 Validator 寫在前面)
    1. 使用者對 Paginator 呼叫 fetch
    2. 查記憶體快取:有有效的 PaginatorPage 就立刻回傳,延遲最低
    3. 查磁碟快取(可選):記憶體沒有、又設定了 Store,就查磁碟;找到有效頁就提升到記憶體並回傳
    4. 向資料來源擷取:兩層都沒有,PaginatorScheduler 觸發 DataSource 的 fetch
    5. Validator 檢查:PageValidator 驗證新頁(格式、是否過期)
    6. 更新快取:驗證通過,同時寫進記憶體(5.1)與磁碟(5.2,若有設定)
    7. 把新的頁回傳給呼叫端

    📖 原書 分層設計在速度和耐久之間取得平衡:記憶體快,磁碟是可靠的備援。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

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    到這裡你已經會了:推車和倉庫

    下一階要解決的問題

    好幾個 request 同時要送:使用者正在等的那頁,跟先備著的 prefetch,誰先?

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

    1. page size
    2. offset / cursor
    3. library
    4. callback
    5. prefetch
    6. cache
    7. memory / disk
    8. eviction
    9. priority
    10. invalidation
    11. index

    出菜口排了 4 道「先備著的」,客人正在等的那道排第幾?

    ① 先想像

    出菜口一次出一道,每道 1 分鐘。前面排了 4 道先備著的(prefetch)。這時客人點的那道進來了,他正盯著空盤子。

    你猜猜看:照進來的順序出,客人要等幾分鐘?讓他插隊呢?

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

    原書這一版的介面沒有列出 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)

    –使用者的 request 平均等幾格–prefetch 最久等幾格–用了幾個 worker

    每格一個時間單位、每個任務一格。示意模擬,不是原書的數字。

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

        1. page size
        2. offset / cursor
        3. library
        4. callback
        5. prefetch
        6. cache
        7. memory / disk
        8. eviction
        9. priority
        10. invalidation
        11. index

        推車上的菜冷了、或廚房改了配方,還能給嗎?

        ① 先想像

        每盤貼一張標籤「端來後 10 分鐘內有效」。廚房也可能喊「第 2 盤改了」,那盤就算沒過時也不能給。

        你猜猜看:12:05 端來、10 分鐘有效。12:20 客人要,推車上那盤能直接給嗎?

        ③ 這叫做 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 等),保證整組相容。

        動手考:這次改動該升哪一碼?

        0 / 5答對

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

        1. page size
        2. offset / cursor
        3. library
        4. callback
        5. prefetch
        6. cache
        7. memory / disk
        8. eviction
        9. priority
        10. invalidation
        11. index

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

        下一階要解決的問題

        原書幾乎沒談廚房那一端:key 到底長怎樣?為什麼有的 key 一來新資料就全部作廢?DB 怎麼找得快?接下來是 Triton。

        Triton 觀點先說清楚他有講、沒講什麼

        原書寫 library 對開發者的契約;Triton 寫的是 key 對 server 的契約

        原書段落Triton 的資料本簡報
        key 可以是 offset 或 cursor143 order by、087 snapshot、074第 42 頁
        Performance(效能)104 Range Scan on PK、062 PK、009 筆記第 44 頁
        key 的形狀、Invalid page keys062 lastTs/nextPageTs、009 筆記 毫秒、027 400第 45 頁
        快取、PageValidator、expirationTime062 Caching with pagination、009 筆記第 46 頁
        一直在變的清單087 ?ts= snapshot、v1/v2、localcache第 47 頁
        PageFetchDirection FORWARD/BACKWARD078 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 會怎樣?

        「學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懂的人可以跳過

        1. page size
        2. offset / cursor
        3. library
        4. callback
        5. prefetch
        6. cache
        7. memory / disk
        8. eviction
        9. priority
        10. invalidation
        11. 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 就是後者(下一頁)。

        ② 動手玩:要第幾位?

        –數第幾個(OFFSET)4 頁從書籤往下(查目錄 3 層 + 1 頁)

        Triton 補充原書的非功能需求寫了 Performance,但只談 client

        OFFSET 100000:DB 先讀十萬列,再丟掉十萬列

        原書這樣做會出什麼事?滑到第 5,001 頁(每頁 20 則),OFFSET 100000 LIMIT 20。DB 為了回你 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

        每頁 20 則
        
              

        假設每個 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 會怎樣?

        「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 頁要作廢幾頁?

        「在同一個 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 · 非本人原文

        0這次 POST 讓幾個 key 失效0累計失效

        🔭 推論 把 062 的 50 則縮成 5 則方便看;「頁滿時以最後一個 lastTs 建新 cache-page」的細節依投影片第 13–15 頁解讀。套回原書:舊頁永遠不會變,PageValidator 的 expirationTime 只需要給最新那一頁。

        Triton 補充有些清單沒有「時間戳」可以當錨點

        一直在變的排行榜:帶 ?ts=,翻頁翻的是同一張快照

        原書這樣做會出什麼事?排行榜一直在變、不帶 ts。你看完第 1 頁,第 5 名掉到第 7 名。翻第 2 頁會怎樣?

        「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 則,出隧道後最省的補法?

          「用戶要補回離線期間留言 – 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,會怎樣?

          🔭 推論 037 的 cursor 是 Triton 拿來批次統計十億筆資料的 DB 功能,狀態住在那條 DB 連線裡;原書和 Triton 講的 API 分頁「cursor」是一個值,狀態在 client 手上。037 裡 MySQL 的做法「id between startPos and endPos」反而跟 keyset 是同一個想法。

          到這裡你已經會了小結 5 / 5

          1. page size
          2. offset / cursor
          3. library
          4. callback
          5. prefetch
          6. cache
          7. memory / disk
          8. eviction
          9. priority
          10. invalidation
          11. index

          到這裡你已經會了:Triton 補上的廚房那一端

          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)

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

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

          pagination長清單一次只拿一段
          page size一段拿幾筆;至少填滿一個螢幕
          request送出去的一張單子(服務生跑一趟)
          offset記「從第幾筆開始」;有人新增或刪除就會歪
          cursor/keyset夾書籤:記最後一筆的值,下次從它往下
          key原書用來指「哪一頁」的字串:頁碼或書籤
          library別人寫好、你直接拿來用的工具包
          interface事先講好的格式:只說要什麼,不說怎麼做
          generic(泛型)先不說裝什麼,用的時候才決定的便當盒
          instance照設計圖做出來的一個實體
          open source程式碼公開,誰都能用,所以 API 很難改
          UI畫面上的按鈕和清單;這章不做

          給工程師的重點出處與原書對照

          引述來源(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 還是一個位置,不是一個值。

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