A system and method for providing scaleable recovery for a multiplexed transactional log. Unlike a dedicated log that includes log data of only one client, a multiplexed transactional log may include log data from multiple clients. In a multiplexed transactional log, log data from different clients may be multiplexed into the multiplexed transactional log in any order. The multiplexed log is maintained for multiple clients using a scaleable logging process. After a system failure, the multiplexed log is recovered using a scaleable recovery process. The scaleable recovery process includes an end-of-log locating process for locating the end of the multiplexed log and each of the virtual logs with the multiplexed log. The end-of-log locating process is also scaleable.