# Write-Ahead Logging (WAL) Modern databases need to guarantee that your data is **not lost**, even when things go wrong: crashes, power failures, or abrupt shutdowns. At the heart of this guarantee lies a simple yet powerful mechanism : **Write-Ahead Logging (WAL)**. This blog is the first in a series on **how databases work under the hood**, and we begin by addressing a fundamental challenge: **how can a database ensure durability and consistency in the face of crashes?** --- ## The Problem: Data Loss on Crashes Let’s say you’re building a simple key-value store that writes to disk like this: ```c void put(const char* key, const char* value) { FILE* f = fopen("store.txt", "w"); fprintf(f, "%s=%s\n", key, value); fclose(f); } ``` Every time you `put`, it overwrites the store file. Seems simple, but what happens if your application crashes in the middle of writing? You might end up with: * A partially written file * A corrupted store * Loss of previously stored keys Even with `fsync()` or `fflush()`, things can go wrong. For instance: * What if power is lost before the file is fully written? * What if a write partially succeeds, corrupting the file? Clearly, we need a safer method. --- ## The Need for a Safer Write Path Overwriting the entire store every time is wasteful and risky. Instead, we want a method that: 1. **Does not destroy the current state on each update** 2. **Allows us to recover from crashes** 3. **Can be flushed to disk reliably** This leads us to a design that’s central to database internals: the **append-only log**. --- ## Enter Write-Ahead Logging (WAL) Write-Ahead Logging turns the problem on its head: > Instead of writing directly to the main store, we **first write the update to a separate log file** and only *then* apply it to the in-memory or persistent state. In other words, before mutating any data structure, you record the *intention* to mutate it in a log. ### Example Flow 1. You want to `put("name", "alice")` 2. You first **append** `{"put": {"key": "name", "value": "alice"}}` to a file called `wal.log` 3. You **flush** this file to disk 4. Then you apply the operation to the main key-value store If your program crashes at any point **after step 2**, you can simply replay the log on restart and reconstruct the state. --- ## Why WAL Works The strength of WAL lies in two properties: ### 1. **Append-Only Writes** Log entries are always written at the end of the file. This avoids partial overwrites and allows for atomic disk operations. ### 2. **Replay Capability** Since the log contains the full history of changes, the current state can be rebuilt from scratch at any time by replaying the log. ### 3. **Separation of Concerns** The WAL serves as a durable history of changes. The main store (e.g., a file or in-memory structure) can be optimized for performance and updated asynchronously. > WAL isn’t just for databases. Modern filesystems like XFS and Btrfs use a similar journaling mechanism for reliability, and even Microsoft Word uses a form of WAL to recover your unsaved documents. --- ## Where WAL Is Used Write-Ahead Logging is used in almost every major database: * **PostgreSQL**: Uses WAL to support crash recovery and replication * **LevelDB / RocksDB**: Use WAL before flushing to SSTables * **SQLite**: Switches to WAL mode for performance and durability * **Kafka**: Uses an append-only log as its core design It’s not just a low-level hack, it’s a deliberate design for correctness. --- ## DIY Time - Build Your Own Basic WAL (in C) Let’s roll up our sleeves and build a **minimal Write-Ahead Logging (WAL)** system from scratch in C. We’ll create a simple **key-value database** that: * Logs every `put` operation to an append-only file * Replays the log to recover the latest state * Can survive crashes using the WAL You can replicate this in **Python**, **Rust**, or **Go**, the principles remain the same. --- ## System Components Following are the three core parts of our WAL system: ### 1. **WAL File – `wal.log`** This file captures every write (aka `put`) operation, line by line: ```plaintext name=Alice age=30 ``` * Append-only: Never delete or modify old entries. * Durable: Persisted to disk immediately. This is our **reliable source of truth**, used to **replay** state on recovery. --- ### 2. **State File – `state.txt`** This represents the current snapshot of the database. It is updated every time we call `replay_log()`, which processes all entries in the WAL and writes the **latest value** of each key. * Easy to parse * Rewritten fully on each update (for simplicity) --- ### 3. **Crash Recovery Logic** Simulates recovery after a crash by **reconstructing the full state** from just the WAL file. This is the essence of WAL: > If the app crashes before saving state, the WAL can replay it exactly. --- ## Full C Implementation Here's the code. We'll explain it block by block below: ```c // ------------------------------ // Write-Ahead Log (WAL) in C // ------------------------------ #include #include #include #include #define LOG_FILE "wal.log" #define STATE_FILE "state.txt" #define MAX_LINE 256 ``` These includes and macros set up the environment: * `wal.log`: Our log file * `state.txt`: Our latest state file --- ### `append_log()`: Appending to WAL ```c void append_log(const char *key, const char *value) { FILE *log = fopen(LOG_FILE, "a"); if (!log) { perror("Failed to open WAL"); exit(1); } fprintf(log, "%s=%s\n", key, value); fclose(log); } ``` **What it does:** * Appends a single `key=value` line to the WAL. * Simple and durable. If you `fsync()` after `fclose()`, it becomes crash-resilient. > **Fun Fact:** Almost every database, from SQLite to Postgres, has an equivalent log append function under the hood! --- ### `replay_log()`: Rebuilding the State ```c void replay_log() { FILE *log = fopen(LOG_FILE, "r"); if (!log) { perror("No WAL found. Starting fresh."); return; } FILE *state = fopen(STATE_FILE, "w"); if (!state) { perror("Failed to open state file"); exit(1); } char line[MAX_LINE]; while (fgets(line, sizeof(line), log)) { fprintf(state, "%s", line); // naive overwrite } fclose(log); fclose(state); } ``` **Purpose:** * Reads each log line. * Writes it to the `state.txt` file, **not very smart** yet, since duplicates aren’t removed. > Later, you could replace this with a hashmap to keep only the latest value per key! --- ### `get_value()`: Querying the State File ```c void get_value(const char *key) { FILE *state = fopen(STATE_FILE, "r"); if (!state) { printf("No state available.\n"); return; } char line[MAX_LINE]; while (fgets(line, sizeof(line), state)) { char fkey[64], fval[128]; sscanf(line, "%[^=]=%s", fkey, fval); if (strcmp(fkey, key) == 0) { printf("%s => %s\n", fkey, fval); fclose(state); return; } } printf("Key '%s' not found.\n", key); fclose(state); } ``` **Why it matters:** * Allows querying values from the rebuilt `state.txt`. * Uses `sscanf()` to parse `key=value` strings. * Currently shows the **first match**, which works because we overwrite the whole state each time. --- ### `main()`: Tying It All Together ```c int main() { printf("Replaying WAL to reconstruct state...\n"); replay_log(); // crash recovery char command[10]; char key[64], value[128]; while (1) { printf("\nEnter command (put/get/exit): "); scanf("%s", command); if (strcmp(command, "put") == 0) { printf("Key: "); scanf("%s", key); printf("Value: "); scanf("%s", value); append_log(key, value); replay_log(); // naive checkpointing } else if (strcmp(command, "get") == 0) { printf("Key: "); scanf("%s", key); get_value(key); } else if (strcmp(command, "exit") == 0) { break; } else { printf("Unknown command\n"); } } return 0; } ``` **What's happening:** * On start, we simulate a crash recovery by calling `replay_log()`. * Then we enter a REPL (read-eval-print loop) for `put`, `get`, and `exit`. --- ## What’s Next? Here are some ways to evolve this system: * Use an in-memory map while replaying so only the latest key-values are kept * Add a `delete` command with tombstones (like `key=__deleted__`) * Add a `fsync()` for real durability * Implement **checkpointing** after N writes to flush WAL Thanks for reading! I hope this hands-on introduction to Write-Ahead Logging gave you a solid understanding of how databases handle durability and recovery behind the scenes. Stay tuned and happy coding :)