Logarithmically-Spaced Snapshots

Logarithmically-Spaced Snapshots

摘要

在处理一系列更新时，保留中间的快照有助于追踪历史版本。由于存储空间有限，快照密度需随时间递减，近期快照更密集，早期则稀疏。本文提出一种简单算法，通过对数间隔保留快照，仅需 2 log2(n) 个快照，无需复杂记录，每次更新仅需 O(1) 时间。算法核心是每次更新后添加新快照，并删除特定旧快照，快照密度可通过参数 d 调整。