Wall clocks versus logical clocks

When a distributed database like Cassandra or Riak operates in last-write-wins (LWW) mode, the ordering of writes is determined by timestamps. Most such systems rely on wall clocks—the time reported by the operating system via calls like gettimeofday(), typically synchronized with NTP and expressed in POSIX time or UTC. The alternative is logical clocks, such as Lamport clocks or vector clocks, which track causality through monotonically increasing counters rather than wall time.

The fundamental problem is that wall clocks are not monotonic. A clock can jump forward or backward due to hardware faults, misconfigured or unreachable NTP servers, virtualization quirks, or NTP's own corrective jumps. Even a perfectly synchronized POSIX clock is not monotonic: leap seconds can cause the clock to skip or double-count a second, producing timestamps that either refer to no real time or to two distinct moments. Google's "leap smear" approach—spreading the leap second across the day—preserves monotonicity but is not universally deployed.

When clocks go backward, consistency guarantees in LWW systems break down in subtle ways. The database is not buggy; it is faithfully applying its ordering rules to timestamps that no longer reflect the actual order of operations.

Session consistency in practice

Consider a typical TCP service architecture: clients connect to stateless application servers, which persist shared state in a distributed database. Cassandra claims to provide session consistency—meaning a process in a session reads its latest write or one with a higher timestamp. The catch is that this guarantee only applies within a Cassandra session; writes from other nodes are not guaranteed visible to a given reader. Application sessions need to be engineered so they stay bound to a specific app server and, transitively, to a specific Cassandra node.

Even then, session consistency is fragile. Cassandra derives timestamps from System.getCurrentTimeMillis(), which is backed by the non-monotonic system clock. If a client writes w1 just before a leap second and w2 just after, w2 can carry a lower timestamp than w1. The database will reject w2 on any node that has already seen w1, effectively guaranteeing the write is not visible. The monotonicity guarantee operates in reverse.

The remedy is to enforce monotonicity within sessions: both the database and any client code generating timestamps should detect backwards movement and delay timestamp generation until the clock catches up. Higher latency or a client-side exception is far better than silently discarding a write.

Monotonic reads and writes fail without coordination

Cassandra also claims monotonic read consistency: once a client has seen a particular value for a key, it will never read an older value. But if writes themselves are not monotonic, reads cannot be either. A single process can write w1 with timestamp t=2, then write w2 with timestamp t=1, and then read w1 when it expects w2.

Worse, this failure does not require a clock to go backwards. It can happen whenever two clients' clocks are not tightly synchronized:

  1. Process A writes w1 with timestamp t=2
  2. Process B reads w1
  3. Process B writes w2 with timestamp t=1
  4. Process B reads w1, but expected w2

This is not a temporary inconsistency. The later write w2 is permanently lost—it may survive briefly on an isolated node, but LWW reconciliation will eventually destroy it in favor of the earlier write. If a client considers a successfully written value as "seen," this scenario also violates monotonic reads.

The root cause is the mismatch between the wall-clock causality model and the application's mental model. LWW treats timestamps as authoritative ordering, but the timestamps were never a faithful record of causal order.

Tombstones and the delete problem

Deletes in Cassandra and Riak are implemented with tombstone records carrying timestamps. Any write with a lower timestamp is silently suppressed until garbage collection removes the tombstone—which can take days to weeks. A single client with an aggressive clock can therefore erase all writes to a record for an extended period:

  1. Process A deletes a row with t=100000000
  2. Process B writes w1 with timestamp t=1
  3. Process B reads null, but expected w1

This happens routinely in LWW systems at smaller scales: every delete or CQL collection clear suppresses subsequent writes for however long it takes the slowest node's clock to catch up. This is why rapid create/delete cycles in automated tests against Riak are so troublesome without vector clocks. Tombstone behavior violates strong, eventual, causal, read-your-writes, and monotonic write consistency, and can violate monotonic reads depending on how "seen" is defined.

Practical mitigations

LWW timestamps are fundamentally unsafe as ordering constructs. NTP does not solve the problem; it reduces skew but does not make clocks monotonic or globally synchronized. To maintain consistency guarantees, one of the following approaches is required:

  • Coordinated timestamps: Use a strong coordinator such as an atomic counter in Zookeeper. This imposes latency and availability trade-offs, but contention can be reduced by partitioning the problem—for instance, coordinating timestamps only when needed and scoping them to specific rows or objects.
  • Rigorous time discipline: Run NTP against TAI or GPS sources rather than POSIX time or UTC, measure clock skew regularly, and consider running a local NTP pool that smears leap seconds over longer intervals.
  • Logical clocks: Use a database that supports vector clocks or dotted version vectors for operations where safety matters, and reserve wall clocks for cases where fuzzy ordering is acceptable.

The choice of ordering mechanism should follow the consistency requirements of each operation. For critical paths, logical clocks offer causality-based ordering that cannot be violated by clock discontinuities. For everything else, wall clocks are faster and adequate—provided the risk of skewed ordering is understood and accepted.