Active/Active Clock Considerations

[achyuthcodes30]

Why does A/A need a clock?

• Timestamps are needed for a few conflict resolution / CRDT algorithms, eg: LWW, RGA

Why wall clocks are not enough

Relying only on wall clock time can be disastrous; NTP syncs can cause time deltas to be negative, causing unexpected behaviour and changing order. This creates the need to have a monotonically increasing clock to prevent this.

Even when clocks are synchronized, nodes can still exhibit nontrivial clock skew due to oscillator drift, network latency, and differences in NTP convergence. In geographically distributed systems, these discrepancies can make timestamp-based comparisons unreliable for determining the true order of events.

Physical timestamps also do not guarantee that causally related events are ordered by their timestamps. If event A happened before event B, it is still possible for timestamp(A) > timestamp(B) due to clock skew or clock adjustments.

What exists in Valkey?

Relevant Source Files - src/util.c, src/monotonic.c

ustime()

• Calls gettimeofday() syscall periodically, while using getMonotonicUs() as a fast path to avoid the syscall.
• NTP corrections can cause backward jumps, as this relies on gettimeofday() ultimately
• Clock skew may cause timestamp ordering to disagree with causal ordering when comparing events across nodes.
• A server clock may also be incorrectly set far into the future. While we cannot generally assume a guaranteed bound on clock skew in a cross-region deployment (like TrueTime and other enterprise solutions), we can implement safeguards to detect and handle anomalous timestamps, such as rejecting, clamping, or quarantining values that exceed reasonable bounds (which is what HLC does).

getMonotonicUs()

• Uses a monotonic clock source (CLOCK_MONOTONIC, x86 TSC calibrated against it, or ARM CNTVCT), so values are monotonic on a given machine.
• Not affected by NTP adjustments, leap seconds, or wall-clock corrections after initialization.
• Values from different nodes are not directly comparable, since they are measured relative to each machine's own monotonic clock epoch rather than a common reference.
• The returned value is not Unix time. It represents elapsed monotonic time (effectively "time since an arbitrary starting point", often close to boot time), not time since the Unix epoch.

Lamport Clocks

https://lamport.azurewebsites.net/pubs/time-clocks.pdf

• A logical counter maintained by each process. The counter is incremented before every local event. When a message with timestamp T is received, the local counter is updated to max(local_counter, T) + 1.
• Independent of physical clocks, so it is unaffected by clock skew, drift, NTP corrections, leap seconds, or other wall-clock anomalies.
• Monotonically increasing and guarantees that causally related events are ordered by their timestamps: if A happened before B, then LC(A) < LC(B).
• The converse is not true: LC(A) < LC(B) does not imply that A caused B. Lamport clocks cannot distinguish causal relationships from concurrent events.
• To obtain a total ordering, timestamps are typically combined with a process or node identifier as a tie-breaker. This deterministically orders concurrent events, but the result can be unintended as the event with a lower node identifier may have happened at a later physical time.

Hybrid Logical Clocks

https://cse.buffalo.edu/tech-reports/2014-04.pdf

• Combines wall time and logical counters.
• Monotonically increasing despite clock skew, drift, NTP corrections, leap seconds, or other wall-clock anomalies.
• Guarantees that causally related events are ordered by their timestamps: if A happened before B, then LC(A) < LC(B).
• Provides resilience against clock anomalies. Self-stabilization and tolerance to arbitrary clock corruptions, allowing HLC state to recover and continue tracking causality even when physical clock synchronization degrades.

Used by CockroachDB -
https://github.com/cockroachdb/cockroach/blob/master/pkg/util/hlc/hlc.go
https://www.cockroachlabs.com/glossary/distributed-db/hybrid-logical-clock-hlc-timestamps/

Vector Clocks

https://www.semanticscholar.org/paper/Timestamps-in-Message-Passing-Systems-That-Preserve-Fidge/e706b8ae2952740cb95c0182c4c44b0d11cc54c1
https://sookocheff.com/post/time/vector-clocks/

• Each node maintains a vector of counters, with one entry per node in the system.
• On a local event, a node increments its own counter.
• Messages carry the sender's vector clock; on receipt, the receiver merges the vectors element-wise and increments its own counter.
• Preserves causality: if A → B, then VC(A) < VC(B) (component-wise comparison).
• Unlike Lamport clocks, can determine whether two events are causally related or concurrent.
• If neither vector dominates the other (some entries are larger and some smaller), the events are concurrent.
• Detects conflicts caused by concurrent updates, but does not define how those conflicts should be resolved.
• Metadata grows with the number of participants (O(N) space and message overhead).