I've been reading up on logical clocks in distributed systems. I wish to write on it, so I will pitch an impromptu sample here. I find that as I write the same topic again and again, I find better explanations. Here it goes.
Distributed systems are designed to meet the scaling demands of normal applications where running them on a single node, both performantly and reliably, becomes prohibitively expensive. In a distributed system, an application runs on a cluster of nodes connected via a network. Scaling up such systems is as simple as adding a new node. Examples of distributed systems include databases such as Apache Cassandra and message queues such as Apache Kafka.
When an application runs on a single node, all of its operations are executed in a well-defined sequence, providing a deterministic output. However, in a distributed application, operations are executed on different nodes and in different orders. In such scenarios, the nodes need to coordinate with each other to share the state of the system, ensuring the final output remains consistent with that of a single node system.
To achieve this, events occurring on the distributed nodes must be ordered, establishing causality between them. Some events may cause others, while some events may occur concurrently. Without knowing the correct order of events, we cannot analyze the system in the same way as a single node application. If we had access to a perfect clock, we could timestamp all events and establish this order. However, physical clocks are difficult to keep synchronized and tend to drift, making event ordering challenging.
Instead of physical clocks, we can use logical clocks. Lamport proposed in his paper that every node in the system has a logical clock, represented by a simple counter. Each node increments its counter after every event. When a node communicates with another node about an event, it passes its latest timestamp along with the message. The receiver then sets its clock to the maximum of its current timestamp or the received timestamp. By following this simple protocol, all events in the system can be partially ordered, determining if event A happened before event B or if events A and B occurred concurrently.
This concept can be used to devise algorithms for problems in distributed systems. For example, Lamport demonstrated how to write an algorithm for sharing a mutually exclusive resource in a distributed system using logical clocks.
Distributed databases extensively utilize these clocks for various tasks. Riak, for example, uses them to achieve consistency of replicated data across nodes. Voldemort, on the other hand, uses clocks for fault detection in the system, although it employs vector clocks instead of plain Lamport clocks. Vector clocks are an extension of Lamport clocks, where a vector of clocks exists. This vector consists of one counter per node in the system, and each node increments its counter in the vector after every event on that node. The vector is passed along with each message to share the state and achieve consistency among nodes.
I've been reading up on logical clocks in distributed systems. I wish to write on it, so I will pitch an impromptu sample here. I find that as I write the same topic again and again, I find better explanations. Here it goes.
Distributed systems are designed to meet the scaling demands of normal applications where running them on a single node, both performantly and reliably, becomes prohibitively expensive. In a distributed system, an application runs on a cluster of nodes connected via a network. Scaling up such systems is as simple as adding a new node. Examples of distributed systems include databases such as Apache Cassandra and message queues such as Apache Kafka.
When an application runs on a single node, all of its operations are executed in a well-defined sequence, providing a deterministic output. However, in a distributed application, operations are executed on different nodes and in different orders. In such scenarios, the nodes need to coordinate with each other to share the state of the system, ensuring the final output remains consistent with that of a single node system.
To achieve this, events occurring on the distributed nodes must be ordered, establishing causality between them. Some events may cause others, while some events may occur concurrently. Without knowing the correct order of events, we cannot analyze the system in the same way as a single node application. If we had access to a perfect clock, we could timestamp all events and establish this order. However, physical clocks are difficult to keep synchronized and tend to drift, making event ordering challenging.
Instead of physical clocks, we can use logical clocks. Lamport proposed in his paper that every node in the system has a logical clock, represented by a simple counter. Each node increments its counter after every event. When a node communicates with another node about an event, it passes its latest timestamp along with the message. The receiver then sets its clock to the maximum of its current timestamp or the received timestamp. By following this simple protocol, all events in the system can be partially ordered, determining if event A happened before event B or if events A and B occurred concurrently.
This concept can be used to devise algorithms for problems in distributed systems. For example, Lamport demonstrated how to write an algorithm for sharing a mutually exclusive resource in a distributed system using logical clocks.
Distributed databases extensively utilize these clocks for various tasks. Riak, for example, uses them to achieve consistency of replicated data across nodes. Voldemort, on the other hand, uses clocks for fault detection in the system, although it employs vector clocks instead of plain Lamport clocks. Vector clocks are an extension of Lamport clocks, where a vector of clocks exists. This vector consists of one counter per node in the system, and each node increments its counter in the vector after every event on that node. The vector is passed along with each message to share the state and achieve consistency among nodes.