Hybrid Clock

Use a combination of system timestamp and logical timestamp to have versions as date and time, which can be ordered

Problem

When Lamport Clock is used as a version in Versioned Value, clients do not know the actual date-time when the particular versions are stored. It's more convenient for clients to access versions using date and time like 01-01-2020 instead of an integer like 1, 2, 3.

Solution

Hybrid logical clock provides a way to have a version which is monotonically increasing just like a simple integer, but also has relation to the actual date and time. Hybrid clocks are used in practice by databases like MongoDB or CockroachDB.

It maintains the latest time as an instance of the hybrid timestamp, which is constructed from the system time and an integer counter.

class HybridTimestamp…

  public class HybridTimestamp implements Comparable<HybridTimestamp> {
      private final long wallClockTime;
      private final int ticks;
  
      public HybridTimestamp(long systemTime, int ticks) {
          this.wallClockTime = systemTime;
          this.ticks = ticks;
      }
  
      public static HybridTimestamp fromSystemTime(long systemTime) {
          //initializing with -1 so that addTicks resets it to 0
          return new HybridTimestamp(systemTime, -1);
      }
  
      public HybridTimestamp max(HybridTimestamp other) {
          if (this.getWallClockTime() == other.getWallClockTime()) {
              return this.getTicks() > other.getTicks()? this:other;
          }
          return this.getWallClockTime() > other.getWallClockTime()?this:other;
      }
  
      public long getWallClockTime() {
          return wallClockTime;
      }
  
      public HybridTimestamp addTicks(int ticks) {
          return new HybridTimestamp(wallClockTime, this.ticks + ticks);
      }
  
      public int getTicks() {
          return ticks;
      }
  
      @Override
      public int compareTo(HybridTimestamp other) {
          if (this.wallClockTime == other.wallClockTime) {
              return Integer.compare(this.ticks, other.ticks);
          }
          return Long.compare(this.wallClockTime, other.wallClockTime);
      }

Hybrid clocks can be used exactly the same way as the Lamport Clock versions. Every server holds an instance of a hybrid clock.

for more details go to Chapter 23 of the online ebook at oreilly.com

This pattern is part of Patterns of Distributed Systems

23 November 2023