程式設計面試：如何設計可恢復的分批迭代器？

題幹與適用場景

請設計一個迭代器，逐筆遍歷遠端 API 回傳的分頁結果。API 每頁最多 100 筆，使用 pageToken，網路請求可能失敗或重複回傳資料；呼叫方會在任意位置保存游標並稍後恢復。請說明介面、不變量、快取、去重、恢復語意、複雜度與測試。

Iterator 設計是公開面試資料中的常見設計模式題；Java 官方介面把 hasNext() 定義為是否還有元素、next() 定義為回傳下一個元素並在沒有元素時拋出例外。本文把普通記憶體迭代擴展為可恢復的分批遠端迭代，重點考察狀態邊界。

面試官考察點

普通回答只寫一個陣列索引。強回答會區分頁面 token、頁內索引、已發出元素與已確認保存的游標，並說明網路重試不會跳過或重複回傳元素。面試官還會追問 API 回傳重複頁、資料在翻頁期間變化、呼叫方在 hasNext() 後崩潰，以及迭代器是否允許並發呼叫。

核心訊號是用不變量控制外部副作用，而不是把遠端分頁誤當成本地陣列。

回答前需要釐清的問題

• 排序是否穩定？ 本題假設 API 按不可變的 (createdAt, id) 鍵穩定排序；沒有穩定排序就無法承諾恢復後的精確遍歷。
• 恢復是至少一次還是恰好一次？ 本題選擇至少一次讀取並允許呼叫方按穩定 ID 去重；遠端服務不提供跨請求交易。
• 資料是否允許刪除或插入？ 本題假設快照版本或讀一致性 token 固定結果集；否則只能承諾近似遍歷。
• 是否允許並發呼叫？ 預設單執行緒呼叫；並發使用要顯式加鎖或回傳狀態錯誤。
• 失敗後能否繼續？ 網路錯誤可有限重試；認證、參數和快照過期等永久錯誤應立即傳遞。

30 秒回答框架

「我把游標拆成快照版本、下一頁 token 和頁內索引。迭代器只在本地快取目前頁，hasNext() 不推進遠端狀態，next() 才消費一個元素；頁面載入成功後才替換快取。持久化游標代表最後一個已交付且呼叫方確認的穩定 ID，恢復時從該位置重新讀取，因此是至少一次，呼叫方用 ID 去重。分頁 API 必須有穩定排序和快照，否則只能說明弱一致語意。所有網路錯誤都有上限重試，永久錯誤原樣拋出。」

分步驟深入解答

第一步：定義狀態和介面契約

介面可以是 hasNext()、next()、checkpoint() 和 close()。hasNext() 只能檢查目前快取或預取下一頁，不能把元素標記為已交付；next() 回傳一個元素並推進 index。checkpoint() 產生可序列化 token，但是否視為已確認進度要由呼叫方明確保存。

第二步：建立核心不變量

0 <= index <= len(buffer)
next() 只回傳 buffer[index]，然後 index += 1
只有整頁請求成功，才替換 buffer 和 pageToken
恢復 token 只代表呼叫方已確認的前綴
永久錯誤不會被重試迴圈吞掉

如果請求下一頁時失敗，舊快取必須保留，重試不會改變已交付位置。若新頁載入成功但程序在保存 checkpoint 前崩潰，恢復會重複最後一段；這符合至少一次語意。若先保存 checkpoint 再交付，崩潰可能造成跳過，不能把兩者順序寫反。

第三步：實作按頁讀取和有限重試

class ResumableIterator:
    def __init__(self, client, checkpoint=None, page_size=100):
        self.client = client
        self.page_size = page_size
        self.snapshot = checkpoint.snapshot if checkpoint else None
        self.token = checkpoint.page_token if checkpoint else None
        self.index = checkpoint.index if checkpoint else 0
        self.buffer = []
        self.done = False

    def has_next(self):
        self._ensure_buffer()
        return self.index < len(self.buffer)

    def next(self):
        self._ensure_buffer()
        if self.index == len(self.buffer):
            raise StopIteration
        item = self.buffer[self.index]
        self.index += 1
        return item

    def checkpoint(self):
        return Checkpoint(self.snapshot, self.token, self.index)

ensurebuffer() 負責在目前頁耗盡時請求下一頁，並使用指數退避和最大次數。超時後的重試可能對應伺服器已成功的請求，因此請求必須帶 snapshot/token，伺服器也應保證同一 token 回傳穩定頁，或回傳可檢測的重複邊界。

第四步：處理重複、插入和刪除

僅依賴頁面 token 不一定能防止伺服器重試回傳重複資料。若 API 回傳穩定 id，迭代器可以在恢復邊界丟棄 id <= lastId 的前綴；若排序鍵是複合鍵，則比較完整 (createdAt, id) 游標。去重集合不能無限增長，最好讓伺服器提供快照和邊界 token，把去重限制在恢復窗口。

如果結果集沒有快照，新插入資料可能出現在目前頁之前，刪除也可能讓下一頁跳過元素。此時只能承諾「按當時可見結果的盡力遍歷」，不能聲稱恰好一次或強一致。面試中應主動降低承諾，或要求 API 增加 snapshot version。

第五步：明確 checkpoint 和恢復語意

checkpoint 應包含版本、快照、token、頁內索引、最後穩定 ID、過濾條件摘要和過期時間。過濾條件摘要用於拒絕把一個查詢的游標恢復到另一個查詢；過期時間用於避免伺服器清理快照後靜默讀到不同資料。

恢復時從 checkpoint 重建迭代器。若呼叫方在消費 item 後立即保存 checkpoint，重複最多從該 item 開始；下游應以穩定 ID 冪等。若業務必須避免重複，必須把「交付元素」和「保存進度」放進同一交易，或讓下游具備去重表；迭代器自身不能憑空製造 exactly-once。

第六步：複雜度、背壓和關閉

快取空間是 O(pagesize)，每個元素的本地推進是 O(1)；遠端讀取次數約為 ceil(N / pagesize)，不包含重試。hasNext() 可能觸發一次網路請求，因此呼叫方不能把它當作零成本查詢。預取可以隱藏延遲，但要有最多一頁或按位元組的上限，避免慢消費者導致記憶體增長。

close() 取消未完成請求並釋放連線；伺服器快照應在 TTL 後回收。若消費者速度低於生產速度，分頁 API 需要限速或回傳過期錯誤，而不是無限延長快照。並發呼叫要禁止或串行化，否則兩個 next() 可能讀到同一 index。

高品質示範回答

「我會把遠端迭代器建模為一個小狀態機：snapshot、pageToken、buffer、index 和 lastId。hasNext() 只確保快取有元素，next() 才推進 index，checkpoint() 保存呼叫方確認的前綴。只有整頁請求成功才替換快取；網路超時有限重試，永久錯誤直接拋出。

「為了恢復，我要求 API 提供穩定排序和 snapshot token。checkpoint 還包含查詢條件摘要、頁內索引、最後穩定 ID 和過期時間。恢復後可能重複最後一項，所以我承諾至少一次，下游用穩定 ID 冪等；如果沒有快照，插入和刪除會破壞強遍歷承諾，我會明確降級。

「快取是 O(pagesize)，每個 next 是 O(1)，遠端頁數約為 ceil(N/pagesize)。測試包括空頁、重複頁、token 過期、超時後伺服器已成功、checkpoint 崩潰、插入刪除、重複恢復、並發 next、背壓和 close。需要 exactly-once 時把進度和業務結果放進同一交易或增加去重表。」

常見錯誤

• 錯誤表現 → 把遠端 API 當成陣列，用一個整數索引恢復 → 失敗原因 → 伺服器頁面邊界和資料變化會使索引指向不同元素 → 修正方法 → 保存 snapshot、token、頁內索引和穩定 ID。
• 錯誤表現 → hasNext() 先推進 token → 失敗原因 → 呼叫方只檢查未消費，崩潰後會跳過元素 → 修正方法 → 只有 next() 交付後才推進本地進度。
• 錯誤表現 → 網路超時後直接換下一頁 → 失敗原因 → 可能遺失整頁或重複伺服器已成功的請求 → 修正方法 → 重試同一 token，並用穩定 ID 處理重複。
• 錯誤表現 → 聲稱迭代器提供 exactly-once → 失敗原因 → checkpoint 保存與業務副作用不是同一原子交易 → 修正方法 → 明確至少一次，讓下游冪等或使用交易。
• 錯誤表現 → 無限預取和無限重試 → 失敗原因 → 慢消費者會耗盡記憶體，故障會永久阻塞 → 修正方法 → 限制快取、重試次數、逾時和快照 TTL。

追問及應對

如果伺服器沒有 snapshot token，只給 page number 呢？

要求按穩定複合鍵改成 cursor，或明確只能提供弱一致遍歷。page number 在插入和刪除後會移動，不能用來證明無跳過、無重複。

如果下游只能接受一次，不能去重呢？

迭代器無法獨立保證 exactly-once。需要把讀取進度、業務寫入和 checkpoint 放入同一交易，或讓下游提供冪等寫入；否則應把「可能重複」寫入契約。

如果某一頁長期逾時怎麼辦？

保留舊 buffer，不推進 token；達到重試上限後拋出可分類錯誤，讓呼叫方決定暫停、跳過或重新開始。跳過必須記錄缺口，不能靜默進入下一頁。