I wrote a similar snapshot system for our deterministic trading engine. It's hard to imagine a system that doesn't do that unless you actually enforce every single event in your log to be reversible/non-destructive/non-aliasing. Even then, you still want snapshots to jump to a point in time. The only annoying thing is the case where you want to step back one, meaning a naive implementation would jump back to the last snapshot and play forward.An 80% solution is to keep the last N states in memory. Snapshots compress well within a small time frame, so whenever we "paused" the playback, we could stash deltas from the pause point to reconstruct stuff (I sadly never got around to implementing this part before I left since it wasn't high enough priority).
mark_undoio|1 year ago
At Undo.io we use similar techniques to time travel debug C/C++ (and other languages).
> An 80% solution is to keep the last N states in memory.
We use a slightly more specialised version of what you describe - we maintain a set of snapshots at wide spacings throughout history (for big time jumps the user might want to do) and ones just a small gap before the "current time" the user is viewing, so small steps backwards can be fast too.
It's been a complex process figuring out an algorithm that balances these concerns without using up unreasonable amounts of RAM.
The other way to tackle slowness - though this is for larger jumps in history - is to search the timeline in parallel. Since you've got deterministic re-execution you can play several chunks of history at once while looking for a key event. It can't help for small jumps in time but if you are looking far into the past it can be a significant speed-up.