The disclosure provides for fault tolerant parallel journaling that speeds up both input/output (I/O) operations and recovery operations. Journal entry writing may occur in parallel with data writing operations. Even if a crash occurs during a data writing operation for which the journal entry has been written, the recovery operation will correctly determine that the journal entry is not valid. Additionally, recovery operations may need to validate fewer journal entries, and yet possibly retain more valid data. Examples include: for each of a plurality of journal entries: receiving incoming data; determining a signature for the incoming data; generating the journal entry for the incoming data; writing the signature in the journal entry; and writing the journal entry and the incoming data to a storage media; and based at least on writing data to the storage media, updating an awaiting index in a journal header.