An Overview of Databases — Part 8: Clocks

Part 1: DBMS Flow
Part 2: Non-Relational DB vs Relational
Part 3: CAP and BASE Theorem
Part 4: How to choose a Database?
Part 5: Different Solutions for Different Problems
Part 6: Concurrency Control
Part 7: Distributed DBMS
>> Part 7.1: Distributed DBMS (Apache Spark, Parquet + Pyspark + Node.js)
Part 8: Clocks
>> Part 8.1: Clocks (Causal Consistency With MongoDB)
>> Part 8.2: Clocks (MongoDB Replica and Causal Consistency)
Part 9: DB Design Mastery
Part 10: Vector DB
Part 11: An interesting case, coming soon!

What we are going to discuss in this post:

1. Clocks
2. The Problem With Clocks
3. What is Causal Consistency?
4. Lamport VS Vector
5. CLOCK DRIFT can cause unexpected results

Clocks

Clocks in distributed systems are essential for coordinating and synchronizing events. There are two main types of clocks: physical clocks and logical clocks.

Physical Clocks

Physical Clocks are based on real-world time and usually rely on hardware clocks present in each node of the distributed system. The primary goal is to keep all physical clocks synchronized as closely as possible to the true Coordinated Universal Time (UTC).

So basically A physical clock is a device that indicates what time it is. A distributed system can have many physical clocks, and in general they will not agree.

Key Points:

• Real-Time Synchronized: Physical clocks aim to represent actual chronological time.
• Synchronization Protocols: Techniques such as the Network Time Protocol (NTP), NTP is a networking protocol for clock synchronization between computer systems and it is the most common protocol used to synchronies the clocks of network devices to a time source such as an atomic clock.
• Clock Skew: Physical clocks can drift apart due to differences in clock speeds, requiring periodic synchronization to correct deviations. The difference between the time on two clocks is called clock skew.
• Clock Drift: Refers to several related phenomena where a clock does not run at exactly the same rate as a reference clock.
• Use Cases: Suitable for events that involve real-world interaction times, such as logging events, time-stamping transactions, and scheduling tasks.

Logical Clocks

Logical Clocks are designed to track the order of events within a distributed system without necessarily maintaining a direct correlation to the real-world time. The main purpose of logical clocks is to ensure causality, ordering events to maintain consistency across distributed nodes.

While physical clocks aim for synchronization with real-world time, logical clocks focus on the relative ordering of events. Two major types of logical clocks are Lamport Timestamps and Vector Clocks.

The Problem With Clock

There is no single global clock in a distributed system, no two clocks would ever be exactly the same in terms of measuring time. In some scenarios availability is more important than consistency. Some constraints:

• If a network partition happens.
• If different concurrent clients update the same key in different replicas at the same time.
• If a node loses some data or somehow data corruption happens

Then it goes out of sync with other replicas.

What is Causal Consistency?

In distributed databases, causal consistency is a way to balance between availability and consistency, which is discussed in the CAP theorem. The CAP theorem explains that in a distributed datastore, we must choose between availability and consistency.

Availability means the database can quickly respond to queries. Consistency means that the data we read is predictable and up-to-date.

There are two extremes of consistency:

1. Strict Consistency: We always read the latest data, regardless of which replica we access. All readers see updates in the same order.
2. Eventual Consistency: We might read outdated data, and the order of updates is not guaranteed.

Databases with strict consistency have lower availability than those with eventual consistency.

Causal Consistency is a balance between these two. It ensures that the order of related operations is maintained across sessions. It does not consider the order of unrelated operations.

For instance, in a chat app, if user A sends a message and user B replies, we expect to see A’s message before B’s. An eventually consistent database may not preserve this order, violating causal consistency.

Causal consistency ensures the following:

• Read-Your-Writes Consistency: If you write something, you will read that data in future queries.
• Monotonic-Reads Consistency: If you read data, any future reads will return that data or newer.
• Monotonic-Writes Consistency: Writes follow a logical order.
• Writes-Follow-Reads Consistency: Writes done after a read will be seen by subsequent reads.

Causal consistency offers a middle path between strict and eventual consistency by maintaining the causal order of operations while sacrificing some availability.

Solution is Logical Clocks

A logical clock is the result of a distributed algorithm so that all parties can agree on the order of events. A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system.

Key Points:

• Event Ordering: Logical clocks help establish a sense of order between events without relying on physical time synchronization.
• Causality: They capture causality relationships, ensuring that all system nodes can agree on the sequence of related events.
• Use Cases: Ideal for conflict resolution in distributed computing (e.g., distributed databases, version control systems, and distributed debugging).

Types of Logical Clocks:

1. Lamport Timestamps:

• A simple logical clock algorithm used to define a causality order on different events happening in a distributed system. In other words, this algorithm is used in order to synchronize events that don’t have a common reference.
• Mechanism: Each node maintains a counter. Before an event, the counter is incremented and the value is appended to the event as its timestamp. On receiving an event, the node updates its counter to be greater than the received timestamp and its own current counter value.
• Causal Ordering: Lamport timestamps ensure a partial order of events but do not provide information about concurrent events.

2. Vector Clocks:

• A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. More here
• Mechanism: Each node maintains a vector of counters, one for each node in the system. When an event occurs, the node increments its own counter and updates vectors based on messages communicated between nodes.
• Causal Ordering: Vector clocks provide a more nuanced view of events, allowing detection of causality and concurrency. If vector A < B, then event A causally precedes event B.

Lamport VS Vector

Lamport clocks cannot tell us if a message was concurrent, and cannot be used to infer causality between events. Vector clocks are a more sophisticated variant which gives us more guarantees, including knowledge of concurrency & causal history.

Visualization

If msg 1 precedes to msg2, and for some reason msg2 arrives earlier, then the receiver puts it into a buffer to process msg1 before than that.

Reasons that may lead to violation of causal ordering of messages:

• It may happen due to a transmission delay.
• Congestion in the network.
• Failure of a system.

CLOCK DRIFT can cause unexpected results

Causal ordering is very useful in several applications like management of replicated data, resource allocation, and monitoring a distributed system. It is a significant principle in distributed systems, ensuring that events are observed in the causal order they occur, rather than an arbitrary order. By maintaining the causal relationships between events, distributed systems can achieve more coherent and predictable behaviors.

Management of Replicated Data:
Consider a social media platform where users can like and comment on posts. Causal ordering ensures that if User A likes a post before User B, this sequence is maintained equally across all replicas.

Resource Allocation:
In a cloud environment, causal ordering could help manage the allocation of compute resources to different jobs, In the context of software development, Continuous Integration and Continuous Deployment (CI/CD) pipelines are used to automate the process of building, testing, and deploying new code changes. Managing these pipelines in a cloud environment can benefit significantly from causal ordering.

Monitoring a Distributed System:
In an e-commerce platform, understanding the causal relationship between high traffic events and subsequent database load helps a lot to find the root cause of a failure.

Now let’s take a look into some DBMs that solve the Clock issue:

1. Casandra

• casandra uses NTP, It supports only last write wins conflict resolution based on system timestamp.
• Under the hood, every time a piece of data is written to Cassandra, a timestamp is attached. Then, when Cassandra has to deal with conflicting data as in the scenario mentioned earlier, it simply chooses the data with the most recent timestamp (microsecond).
• As Cassandra’s log-based storage is timestamp-driven, it is absolutely critical that all nodes in a cluster have synchronized clocks. To this end, instances running Cassandra should be using NTPD or another time synchronization application to keep all system clocks in a cluster in sync.

2. RIAK

• Riak uses vector clock, Written in Erlang.
• Whatever happens to system time your are fine.
• Behind the scenes, Riak uses vector clocks as an essential element of its active anti-entropy subsystem and of its automatic read repair capabilities.
• Riak-KV is an eventually consistent key-value database that favours write availability. To achieve this, it allows multiple clients to write concurrently, potentially to the same key.
• Riak-KV uses logical clocks to track the history of updates to values, and detect conflicting writes.

3. MongoDB:

• MongoDB uses a Lamport clock to ensure causal consistency, especially in multi-document transactions and read operations.
• When a client performs a write operation, the Lamport timestamp is incremented and stored along with the operation, ensuring that subsequent reads can discern the causal history.
• More on MongoDB docs.

4. Dynamo:

• DynamoDB, inspired by Amazon’s Dynamo, uses vector clocks to maintain object versioning across multiple replicas
• Each object in DynamoDB is associated with a vector clock, which is a list of counters, each corresponding to a node that modifies the object.
• When DynamoDB detects conflicting versions of an object (i.e., versions with non-comparable vector clocks), it uses application-specific logic to merge these versions.
• More on DynamoDB docs.

In the next two articles I will cover some parts of MongoDB that are directly related to Causal Consistency and logical clock.