Write-Ahead Log (WAL)

The primary purpose of a WAL is to provide a deterministic recovery path after a system crash. Because changes are durably written to the log first, the system can replay the log's sequence of operations upon restart to reconstruct the exact state of the database up to the last committed transaction. This prevents data corruption and partial writes from leaving the database in an inconsistent state.

• Redo Logging: Reapplies all committed transactions recorded in the log.
• Undo Logging: Rolls back any uncommitted transactions that were in progress at the time of the crash.

WAL files are written sequentially and are append-only. This pattern is significantly faster than random disk I/O, which is required for updating data pages in-place. Sequential writes maximize throughput on both traditional hard drives and SSDs.

• Performance: Eliminates the seek time penalty of random writes.
• Durability: A single fsync() call can ensure multiple transactions are persisted, improving efficiency compared to syncing each data page individually.
• Log Segments: Logs are often managed in fixed-size segments; once a segment is full, a new one is created, and old segments can be archived or deleted after checkpoints.

A checkpoint is a periodic operation that synchronizes the in-memory state of the database with the persistent data files and truncates the WAL. It marks a point where all prior transactions have been fully applied to the main storage, making the log before that point redundant for recovery.

• Log Truncation: Prevents the WAL from growing indefinitely.
• Faster Recovery: After a crash, recovery only needs to replay transactions from the last checkpoint forward.
• Performance Trade-off: Checkpoints can be I/O-intensive, so systems tune their frequency (e.g., based on time or log size) to balance recovery time with runtime overhead.

WAL is the engine behind the Atomicity and Durability guarantees in the ACID transaction model.

• Atomicity: All operations of a transaction are recorded in the log as a single unit. If the transaction commits, the entire log entry is persisted; if it aborts, the log provides the information needed to roll back.
• Durability: Once a transaction's commit record is written to the durable WAL, the transaction is guaranteed to survive a crash, even if the actual data pages haven't been updated yet. This mechanism ensures transactional integrity across system failures.

The WAL serves as the single source of truth for the order of write operations. It serializes concurrent transactions into a strict, global sequence (a log sequence number - LSN). This serialization order defines the official timeline of state changes.

• Concurrency Control: Systems like Multi-Version Concurrency Control (MVCC) often use the WAL's LSN to determine transaction visibility and resolve conflicts.
• Replication: The serialized log is ideal for feeding change data capture (CDC) streams to replicas, ensuring they apply changes in the same order as the primary.

WAL is not exclusive to SQL databases. It's a ubiquitous pattern in modern infrastructure:

• PostgreSQL: Uses PG_WAL segments for crash recovery and point-in-time recovery (PITR).
• Apache Kafka: The commit log is the primary storage, making it a massive, distributed WAL.
• etcd/Raft Consensus: The Raft log is a WAL that ensures state machine replication across a cluster.
• Vector Databases: Used to ensure that inserted or updated vectors are not lost before they are indexed and persisted to disk, maintaining embedding integrity.

Replication is the process of creating and maintaining multiple copies of data across different nodes in a distributed system. It works in tandem with the WAL to ensure data availability and fault tolerance.

• Synchronous Replication: The WAL entry must be durably written to replicas before the write is acknowledged to the client, guaranteeing strong consistency.
• Asynchronous Replication: The primary node acknowledges the write once its local WAL is persisted, and replicas are updated from the WAL stream in the background for lower latency.
• In vector databases, replication ensures that embeddings and their indexes are available on multiple nodes, allowing queries to be served even if a primary node fails.

Strong consistency is a model where any read operation returns the value from the most recent write. The WAL is a critical enforcer of this guarantee in distributed systems.

• When a write is received, it is first appended to the WAL. This log becomes the single source of truth for the order of operations.
• Replicas apply WAL entries in the exact same sequence as the primary node. This ensures all nodes converge to the same state.
• For vector database operations—like inserting a new batch of embeddings—strong consistency via the WAL guarantees that a subsequent similarity search will include those new vectors.

Idempotency is the property of an operation whereby applying it multiple times produces the same result as applying it once. WAL-based recovery relies on idempotent operations to guarantee correctness after a crash.

• During crash recovery, the database replays the WAL from the last checkpoint. Operations like "increment counter" are not idempotent and could cause data corruption if replayed.
• Vector database operations are often designed to be idempotent. For example, "upsert vector with ID X" will result in the same final state whether executed once or multiple times.
• This property is essential for exactly-once semantics in distributed data pipelines feeding into a vector database.

Checkpointing is the process of periodically saving the in-memory state of a database to persistent storage and truncating the WAL. It is a performance and recovery optimization mechanism.

• Without checkpoints, the WAL would grow indefinitely, and system recovery would require replaying the entire log history, which could take hours.
• A checkpoint creates a recovery point. On restart, the system loads the last checkpoint and only replays WAL entries created after it.
• In a vector database, a checkpoint must persist the state of complex in-memory index structures (like HNSW or IVF), not just raw vector data.

Leader election is a process in distributed systems where nodes collectively choose one node to act as the coordinator or primary node responsible for managing writes.

• The primary node is the only one that accepts writes and appends them to its WAL. This prevents conflicting write sequences.
• If the primary node fails, a new leader is elected. The new primary must determine the most up-to-date state, often by examining WAL sequence numbers from replicas.
• This process ensures the single-writer principle, which is crucial for maintaining a coherent, linearizable WAL across the cluster in systems like etcd or ZooKeeper, which are often used to coordinate vector database clusters.

Event sourcing is an architectural pattern where state changes are stored as a sequence of immutable events. A WAL is a low-level implementation of this pattern at the storage engine level.

• Instead of storing only the current value of a record, every change (e.g., "vector inserted," "metadata updated") is stored as an event in the log.
• The current state is derived by replaying all events. This provides a complete audit trail and enables features like temporal queries (querying the state of the vector index at a previous point in time).
• While a WAL is typically truncated after checkpointing, a full event-sourcing system retains the entire log indefinitely as the primary data store.