Record and replay, which records a multithreaded program's execution in one run and reproduces it deterministically in a second run, is useful for program debugging, fault detection and analysis. The key challenge in multithreaded record and replay is ensuring that conflicting, cross-thread accesses to shared variables are properly detected, recorded and reproduced. Numerous solutions have been proposed in both hardware and software to track these cross-thread accesses, but to date all general-purpose software solutions suffer from high overhead or have serious limitations. This paper introduces Roctet, an approach for performing software-only deterministic record and replay. Roctet is built on top of a novel dynamic analysis infrastructure, Octet, which can detect at low overhead any cross-thread dependences during execution by exploiting the fact that most accesses, even of shared objects, are not part of cross-thread dependences. We implement Octet and Roctet in a JVM and show they add low overhead for several multithreaded applications. We also show that our implementation of Roctet can successfully replay recorded executions when it can successfully control or ignore extraneous sources of nondeterminism in the VM, libraries, and system.