渐进式工作Incremental work
把昂贵的整体更新拆成多次有限进度，并维护过渡状态。
- 核心约束
- 更新期间新旧状态并存时，查询和写入必须保持正确语义。
- 适用问题
- 哈希表迁移、后台维护和可中断的数据整理。
- 边界与取舍
- 一批工作仍可能很大；按桶或任务计数的预算不是严格时间上界。
常见操作#
W 为总工作量，b 为每次实际处理量；以 Redis 渐进 rehash 为例。
| 操作 | 时间成本 | 条件与说明 |
|---|---|---|
| 分批推进 | 由本批实际条目和单条工作决定 | 限制桶数、节点数和限制实际耗时是不同预算；一个桶可能含长冲突链。 |
| 处理中间状态 | 维护进度 + 同时支持新旧状态 | 请求在迁移期间仍须获得正确结果，常需额外查询分支。 |
| 完成并清理 | 回收旧结构和重置进度 | 尾声仍可能有非渐进清理工作，需要单独审查。 |
实施成本#
- 时间成本
- 分散单次工作，不必然减少 W 或保证严格时延上界
- 空间成本
- 旧状态 + 新状态 + 进度元数据
适合拆分可中断且可恢复的工作。需要证明中间状态正确、进度不会遗漏，并区分总吞吐与单次暂停。
工程中的应用#
1 个案例 · 附源码Redis 7.2.0 的字典扩缩容保留新旧两张哈希表，逐桶迁移，降低一次性搬迁全部条目的停顿。
附源码片段 · 索引与查找
原始实现与接口资料
Redis 7.2 · Incremental rehashdictRehash 的桶级预算、双表查询和完成清理。