Does fork not use copy-on-write? I would expect it to add overhead to all overlapped memory operations going forward, but am really surprised if it literally duplicated the entire memory contents.
It does, but the kernel must still copy the page tables in full. For a very large process on a 64-bit machine, the amount of copying can be substantial.
There can be fast differences in fork times between different virtualization schemes, even if your code is CoW-friendly (and Redis's is).
Actually duplicating the memory contents would be slower still, I'm sure. What seems to be going on here is simply a consequence of paravirtualization needing to implement certain functions in software that would otherwise be taken care of in hardware when using HVM or bare metal.
Memory fragmentation seems to play a role too. Even if you have (barely) enough free RAM, machines can start swapping and a Redis server in that state is bound to wake you up at night... :(
If you run a server with anything but "swapoff -a" you're doing it wrong. (or even having any swap partition in /etc/fstab).
If the server has to swap, get more RAM or scale your stuff out but never swap.