The two approaches are completely different. gdb singlesteps the program and, before each instruction, records the state of registers and memory that will be changed by that instruction --- an undo log. Then you can reverse-execute an instruction by restoring the state from the undo log. This is incredibly slow because singlestepping requires a full context switch for each instruction executed.

rr, on the other hand, intercepts all system calls and other sources of nondeterminism but regular CPU instructions execute normally with no overhead. The details about rr are here: https://arxiv.org/abs/1705.05937