You don't necessarily need to write log entries in the order they are committed, nor do you need to store all of the entries in a single log, you could shard the log writing too - as long as you maintained, somewhere, the order information. So yes, you would still need to lock and sort out the order somewhere, but you already have to if you're ACID any way.
Right on the money. We every log record contains LSN (log sequence number) that allows us to reconstitute the order. Then as at the recovery time you need to merge sort by LSN from the shared log servers
