I could be wrong, but personally I think it’s unlikely that a replay comes from the server, as that’s not a very elegant way to implement it.
I think it’s more likely that they store a history of the game for a set length of time, as your client saw it, and then play it back client-side.
If I had to guess, they probably serialize the game state periodically, and then store network messages that change the state of the game for actors that they care about, until the next serializable frame.
Messages like “this guy threw a grenade”, “the grenade exploded”, “this guy took damage”, etc.
So when a request to playback the replay comes in, they restore the game state to the closest fully serialized frame, and then play back all the state change messages at the appropriate time.
Alternatively, I guess you could just store all the network messages over a set period of time and reverse their effect, then play them back again.
Some games store the player’s previous positions and rotations for a set period of time, so that they can rewind time a few seconds for latency compensation purposes. I think Source engine works that way… possibly Unreal too, it’s been a while since I’ve looked at the player replication code.