The Clockwork of Distributed Systems: A Guide to Timestamping Solutions (Part-1)
This first part of a series explores the fundamental building blocks of timestamping in distributed systems.
Last week, I was reading the paper “Timestamp as a Service”. This mainly focuses on introducing a distributed algorithm called TaaS that computes logical timestamps from a consensusless cluster of clocks. The main idea behind TaaS is to observe multiple clocks simultaneously rather than relying on a distinguished clock.
The author claims that this TaaS algorithm provides highly available and correct time-stamping services for distributed systems. They say that TaaS ensures that timestamps are always computable and increase monotonically over time, even in scenarios where some server clocks may become unobservable. Additionally, the author also states that TaaS is immune to SPOF (Single Point of Failure) and exhibits reasonable performance comparable to existing oracles like TiDB.
In this paper, we’ll focus on existing timestamping solutions. We’ll get in more depth into TaaS (Timestamping as a Service) in the next blog post.
Clocks in Distributed Systems
The concept of timing distributed computations was introduced first by Lamport. Afterwards, it was developed into four different category of clocks that was used for different scenarios. Let’s understand each one of them briefly before getting into TaaS.
Scalar Logical Clocks
This was the original clock by Lamport. It provides a way to linearize the “happened before” relation among events in a distributed system into a total order of timestamps. Each event in the system is assigned a timestamp, and these timestamps are used to establish a partial ordering of events based on causality.
This clock provides a simple and effective way to track the causal relationship between events in a distributed environment, ensuring that events are correctly ordered based on causality.
A timestamping mechanism is considered complete if, for all pairs of events where event 𝜎 “precedes” event 𝜏 in terms of causality (denoted as 𝜎 ≺ 𝜏), the timestamp assigned to event 𝜎 is less than the timestamp assigned to event 𝜏.
Formally, the completeness property can be expressed as: For all events 𝜎 and 𝜏, if event 𝜎 causally precedes event 𝜏, then the timestamp assigned to event 𝜎 is less than the timestamp assigned to event 𝜏.
Let’s take an example, if transaction 𝜎 modifies a data item before transaction 𝜏 reads that data item, the timestamp assigned to transaction 𝜎 should be less than the timestamp assigned to transaction 𝜏 to reflect the causal relationship between the two transactions.
Let P0, P1, and P2 be three processes and a, b, …,k be events. Lamport’s logical clock algorithm assigns a number (timestamp) to each event, allowing us to understand the order in which they occurred. The above figure illustrates how Lamport’s algorithm is used. It can indicate that certain events occurred before others (for example, event a occurred before event b on P0).
However, Lamport’s algorithm has one limitation. Sometimes it assigns the same timestamp to two different events, even if they occurred at different times on different computers. This makes it difficult to determine whether these events are causally related. For example, based solely on timestamps, we cannot determine whether event “a” on P0 occurred before or after event “f” on P2.
To address this issue, another technique known as vector clocks was introduced.
Vector Logical Clocks
Vector clocks, introduced by Mattern, are an extension of scalar clocks in distributed systems that provide a more sophisticated way to capture the causal relationships between events.
Vector clocks extend the idea of scalar logical clocks by associating a vector of logical timestamps with each process in the system. Each process maintains a vector clock where each component of the vector corresponds to a different process in the system. It is used to track the causal relationships between events across different processes more accurately than scalar clocks.
Concept of Soundness: In the context of vector clocks, the concept of timestamp soundness is introduced to ensure that the timestamping mechanism maintains both completeness and soundness properties. Timestamp soundness states that a timestamping mechanism is sound if, for all pairs of events 𝜎 and 𝜏, if the timestamp assigned to event 𝜎 is less than the timestamp assigned to event 𝜏, then event 𝜎 must “precede” event 𝜏 in terms of causality.
In formal words, it can be expressed as: For all events 𝜎 and 𝜏, if the timestamp of event 𝜎 is less than the timestamp of event 𝜏, then event 𝜎 must causally precede event 𝜏.
For example, if we have a distributed system with three processes: Process A, Process B and Process C. Each process here maintains its own vector clock with three components to track the logical timestamps.
Initially, all vector clocks are set to [0, 0, 0] for Process A, B and C.
Event Execution:
- Process A performs an operation and updates its vector clock to [1, 0, 0].
- Process B performs an operation and updates its vector clock to [0, 1, 0].
- Process C performs an operation and updates its vector clock to [0, 0, 1].
Causal Relationship
- Now let’s consider two events X and Y.
- Event X occurs at Process A with a timestamp [2, 0 , 0].
- Event Y occurs at Process C with a timestamp [0, 0, 2].
Comparison using Vector Clocks: To determine the causal relationship between Event X and Event Y, we compare their timestamps using Vector Clocks. Since the timestamp of Event X ([2, 0, 0]) is greater than the timestamp of Event Y ([0, 0, 2]), according to the Vector Clocks, Event X must have happened before Event Y. This comparison helps establish the causal relationship between events across different processes in the distributed system.
Hybrid Logical Clocks
HLC was introduced by Kulkarni et al., It integrate the concept of scalar logical clocks with the system’s physical clock (crystal oscillator) to create a hybrid timestamping mechanism. The key idea behind HLC is to associate timestamps with events that reflect both the logical ordering of events (as in scalar clocks) and the physical time in the real world.
By combining logical and physical timing techniques, HLC aims to provide a more accurate and meaningful representation of event ordering in distributed systems. HLC was implemented by CockroachDB, MongoDB, and YugabyteDB.
HLC ensures that events are not only based on their causal relationships but also with respect to the actual time they occurred in physical world. By synchronizing timestamps with physical time, HLC enables transactions to be coordinated and ordered across different databases or distributed components. HLC addresses the limitations of purely logical clocks by incorporating real-world time synchronization, bridging the gap between logical event ordering and physical time.
Synchronized Clocks
Synchronized clocks aim to address the challenges of managing multiple independent clocks in a distributed system by utilizing a single clock that synchronizes all components. This synchronization can be achieved either physically, through shared like atomic clocks or logically, through a centralized timekeeping mechanism.
TrueTime: TrueTime is a unique clock system used by Google Spanner. It keeps all of the servers in Spanner synchronized with extremely precise timing. This is important because Spanner must understand the exact order in which events occur, even if they occur on different computers. TrueTime achieves this accuracy by utilizing specialized server components that communicate with ultra-precise clocks equipped with atomic components or GPS.
Centralized Timestamping: Instead of each computer in a system keeping its own time, centralized timestamping uses a single source, such as a “timestamp server,” to provide timestamps for all. This is similar to setting all of the clocks in a building to the same time source.
Many databases, including the CORFU sequencer and PolarDB-X TSO, use this approach. It is a simpler and less expensive method of managing timestamps across a network because it eliminates the need for expensive, super-accurate clocks on each machine.
Benefits of Centralized Timestamping:
- Simplicity and Lightweight Design: Centralized timestamping centralizes the process, making it easier to manage multiple clocks on individual machines.
- Performance Optimization: When databases are close together (e.g., in the same datacenter), fetching timestamps from a central server has little impact, resulting in efficient transaction processing.
- A central timestamp source can be a dependable solution because it is a single, managed entity.
My name is Mohit, and I’m a blogger that creates intriguing content that leave readers wanting more. Anyone interested in machine learning, data science and software engineering should check out my blog. My writing is designed to keep you engaged and intrigued with a regular publishing schedule of a new piece every two days. Follow along for in-depth information that will leave you wanting more!
If you liked the article, please clap and follow me since it will push me to write more and better content. I also cited my GitHub account and Portfolio at the bottom of the blog.
You can follow me on Twitter to learn more about this. Every day, I tweet about a variety of subjects here, such as software engineering, system design, deep learning, machine learning, and more.
Thank you for reading my blog post on The Clockwork of Distributed Systems: A Guide to Timestamping Solutions (Part-1). I hope you find it informative and helpful. If you have any questions or feedback, please feel free to leave a comment below.
I also encourage you to check out my portfolio and GitHub. You can find links to both in the description below.
I am always working on new and exciting projects, so be sure to subscribe to my blog so you don’t miss a thing!
Thanks again for reading, and I hope to see you next time!
