编程面试：如何设计一个可恢复的分批迭代器？

题干与适用场景

请设计一个迭代器，逐条遍历远程 API 返回的分页结果。API 每页最多 100 条，使用 pageToken，网络请求可能失败或重复返回数据；调用方会在任意位置保存游标并稍后恢复。请说明接口、不变量、缓存、去重、恢复语义、复杂度和测试。

Iterator 设计是公开面试资料中的常见设计模式题；Java 官方接口把 hasNext() 定义为是否还有元素、next() 定义为返回下一个元素并在没有元素时抛出异常。本文把普通内存迭代扩展为可恢复的分批远程迭代，重点考察状态边界。

面试官考察点

普通回答只写一个数组下标。强回答会区分页令牌、页内索引、已发出元素和已确认保存的游标，并说明网络重试不会跳过或重复返回元素。面试官还会追问 API 返回重复页、数据在翻页期间变化、调用方在 hasNext() 后崩溃，以及迭代器是否允许并发调用。

核心信号是用不变量控制外部副作用，而不是把远程分页误当成一个本地数组。

回答前需要澄清的问题

• 排序是否稳定？ 本题假设 API 按不可变的 (createdAt, id) 键稳定排序；没有稳定排序就无法承诺恢复后的精确遍历。
• 恢复是至少一次还是恰好一次？ 本题选择至少一次读取并允许调用方按稳定 ID 去重；远程服务不提供跨请求事务。
• 数据是否允许删除或插入？ 本题假设快照版本或读一致性令牌固定结果集；否则只能承诺近似遍历。
• 是否允许并发调用？ 默认单线程调用；并发使用要显式加锁或返回状态错误。
• 失败后能否继续？ 网络错误可有限重试；认证、参数和快照过期等永久错误应立即传播。

30 秒回答框架

“我把游标拆成快照版本、下一页 token 和页内索引。迭代器只在本地缓存当前页，hasNext() 不推进远程状态，next() 才消费一个元素；页加载成功后才替换缓存。持久化游标表示最后一个已交付且调用方确认的稳定 ID，恢复时从该位置重新读取，因此是至少一次，调用方用 ID 去重。分页 API 必须有稳定排序和快照，否则只能说明弱一致语义。所有网络错误都有上限重试，永久错误原样抛出。”

分步骤深入解答

第一步：定义状态和接口契约

接口可以是 hasNext()、next()、checkpoint() 和 close()。hasNext() 只能检查当前缓存或预取下一页，不能把元素标记为已交付；next() 返回一个元素并推进 index。checkpoint() 生成可序列化令牌，但是否视为已确认进度要由调用方显式保存。

第二步：建立核心不变量

0 <= index <= len(buffer)
next() 只返回 buffer[index]，然后 index += 1
只有整页请求成功，才替换 buffer 和 pageToken
恢复令牌只代表调用方已确认的前缀
永久错误不会被重试循环吞掉

如果请求下一页时失败，旧缓存必须保留，重试不会改变已交付位置。若新页加载成功但进程在保存 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) 游标。去重集合不能无限增长，最好让服务端提供快照和边界令牌，把去重限制在恢复窗口。

如果结果集没有快照，新插入数据可能出现在当前页之前，删除也可能让下一页跳过元素。此时只能承诺“按当时可见结果的尽力遍历”，不能声称恰好一次或强一致。面试中应主动降低承诺，或要求 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 当成数组，用一个整数 index 恢复 → 失败原因 → 服务端页边界和数据变化会使 index 指向不同元素 → 修正方法 → 保存 snapshot、token、页内索引和稳定 ID。
• 错误表现 → hasNext() 先推进 token → 失败原因 → 调用方只检查未消费，崩溃后会跳过元素 → 修正方法 → 只有 next() 交付后才推进本地进度。
• 错误表现 → 网络超时后直接换下一页 → 失败原因 → 可能丢失整页或重复服务端已成功的请求 → 修正方法 → 重试同一 token，并用稳定 ID 处理重复。
• 错误表现 → 声称迭代器提供 exactly-once → 失败原因 → checkpoint 保存与业务副作用不是一个原子事务 → 修正方法 → 明确至少一次，并让下游幂等或使用事务。
• 错误表现 → 无限预取和无限重试 → 失败原因 → 慢消费者会耗尽内存，故障会永久阻塞 → 修正方法 → 限制缓存、重试次数、超时和快照 TTL。

追问及应对

如果服务端没有 snapshot token，只给 page number 呢？

要求按稳定复合键改成 cursor，或明确只能提供弱一致遍历。page number 在插入和删除后会移动，不能用来证明无跳过、无重复。

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

迭代器无法独立保证 exactly-once。需要把读取进度、业务写入和 checkpoint 放入同一事务，或让下游提供幂等写入；否则应把“可能重复”写入契约。

如果某一页长期超时怎么办？

保留旧 buffer，不推进 token；达到重试上限后抛出可分类错误并让调用方决定暂停、跳过或重新开始。跳过必须记录缺口，不能静默进入下一页。