Low-Water Mark (LWM) (Design Pattern of Distributed Systems)

The Low-Water Mark (LWM) pattern is a method used in distributed systems to achieve fault tolerance, consistency, and recovery. It helps track the minimum progress of a set of distributed processes or nodes, enabling decisions based on the slowest or least advanced participant.

Concept

The Low-Water Mark represents the minimum value among a set of tracked metrics or states across all participants in a distributed system. These metrics often relate to:

• Progress in a log or sequence (e.g., message offsets in a queue).
• Acknowledgements of processed data.
• Transaction completeness in replicated databases.

The pattern ensures safe decisions (e.g., committing data, reclaiming resources) by only proceeding when all nodes or processes have surpassed the Low-Water Mark.

Applications

1. Message Queues (e.g., Kafka)

In systems like Apache Kafka, offsets indicate the position of consumers in processing messages. Kafka uses LWM to decide when messages can be deleted from a log.

• Producers add messages to the log.
• Consumers process messages at their own pace.
• The Low-Water Mark is the minimum offset acknowledged by all consumers in a consumer group.

Kafka purges messages up to the LWM, ensuring no unprocessed data is lost.

2. Checkpointing in Distributed Databases (e.g., Raft, Paxos)

In consensus protocols like Raft or Paxos, checkpoints ensure system recovery.

• Example: Raft nodes replicate logs. To safely truncate logs, a node uses the LWM to identify the earliest log entry committed by all nodes.

3. Garbage Collection in Distributed Systems

In distributed garbage collection, objects are only deleted when they are no longer referenced by any process or node.

• The Low-Water Mark is the earliest timestamp up to which all nodes have acknowledged references.

4. Snapshot Recovery

Systems like Google's Chandy-Lamport Snapshot Algorithm for global states use a variant of the LWM to determine when all processes have captured a consistent state.

Advantages

1. Ensures safety in data retention and resource reclamation.
2. Provides a consistent view of progress or state across distributed participants.
3. Prevents premature deletion of critical data.

Challenges

1. Synchronization Overhead: Calculating the LWM requires regular communication across nodes.
2. Stragglers: Slow nodes can hold back progress if their state determines the LWM.
3. Scalability: As the number of nodes increases, calculating and maintaining the LWM becomes more complex.

Example

Distributed Logging System:

• A distributed logging system has three nodes (A, B, and C) processing log entries.
• A processes up to entry 10, B up to 15, and C up to 12.
• The Low-Water Mark for this system is 10, meaning log entries ≤10 can be safely truncated or marked as completed, as all nodes have processed them.

By focusing on the slowest node, the system maintains consistency while optimizing for safety.