Write Ahead Log - WAL
The Write Ahead Log (WAL) is a commonly used technique in database systems to maintain atomicity and durability of writes. The key idea behind the WAL is that before we make any actual modifications to the database state, we have to first log the complete set of actions we wish to have to be atomic and durable to durable storage (e.g. disk).
Durability is provided by writing the intended mutation to the WAL first, before applying the changes to for example, the in-memory representation. By writing to the WAL first, should the database then crash, we will be able to recover the mutation and reapply if necessary.
Atomicity is a little more subtle. Suppose a mutation requires changes A, Band C to happen, but we have no means of atomically applying all of them at once. We could first log