Small correction: the magic of record-replay is that you don't have to record every piece of data read/written, only the non-deterministic events (interrupts, accesses to devices, and a couple instructions like `rdtsc`). This lets the overhead during recording stay low, while still getting all the benefits of a full execution trace. This is why we're able to store the Spotify trace [1] in only 263.1 MB.

[1] http://www.rrshare.org/detail/28/