Hybrid Clock

Multiversion storage with Hybrid Clock

A hybrid timestamp can be used as a version when the value is stored in a key value store. The values are stored as discussed in Versioned Value.

class HybridClockReplicatedKVStore…

  private Response applySetValueCommand(VersionedSetValueCommand setValueCommand) {
      mvccStore.put(setValueCommand.getKey(), setValueCommand.timestamp, setValueCommand.value);
      Response response = Response.success(setValueCommand.timestamp);
      return response;
  }

class HybridClockMVCCStore…

  ConcurrentSkipListMap<HybridClockKey, String> kv = new ConcurrentSkipListMap<>();

  public void put(String key, HybridTimestamp version, String value) {
      kv.put(new HybridClockKey(key, version), value);
  }

class HybridClockKey…

  public class HybridClockKey implements Comparable<HybridClockKey> {
      private String key;
      private HybridTimestamp version;
  
      public HybridClockKey(String key, HybridTimestamp version) {
          this.key = key;
          this.version = version;
      }
  
      public String getKey() {
          return key;
      }
  
      public HybridTimestamp getVersion() {
          return version;
      }
  
      @Override
      public int compareTo(HybridClockKey o) {
          int keyCompare = this.key.compareTo(o.key);
          if (keyCompare == 0) {
              return this.version.compareTo(o.version);
          }
          return keyCompare;
      }

The values are read exactly as discussed in the Ordering of the versioned keys. The versioned keys are arranged in such a way as to form a natural ordering by using hybrid timestamps as a suffix to the key. This implementation enables us to get values for a specific version using the navigable map API.

class HybridClockMVCCStore…

  public Optional<String> get(String key, HybridTimestamp atTimestamp) {
      Map.Entry<HybridClockKey, String> versionKeys = kv.floorEntry(new HybridClockKey(key, atTimestamp));
      getLogger().info("Available version keys " + versionKeys + ". Reading@" + versionKeys);
      return (versionKeys == null)? Optional.empty(): Optional.of(versionKeys.getValue());
  }

Converting hybrid timestamp to date time

A hybrid clock can be converted into an actual timestamp value by merging the system timestamp and the logical clicks number. As discussed in the [hybrid-clock] paper, the first 48 bits of the system time can be preserved, and lower order 16 bits can be replaced by the logical counter.

class HybridTimestamp…

  
      public LocalDateTime toDateTime() {
          return LocalDateTime.ofInstant(Instant.ofEpochMilli(epochMillis()), ZoneOffset.UTC);
      }
  
      public long epochMillis() {
          //Compact timestamp as discussed in https://cse.buffalo.edu/tech-reports/2014-04.pdf.
          return (wallClockTime >> 16 << 16) | (ticks << 48 >> 48);
      }

Assigning timestamp to distributed transactions

Databases like MongoDB and CockroachDB use a Hybrid Clock to maintain causality with distributed transactions. With distributed transactions, it's important to note that, all the values stored as part of the transaction should be stored at the same timestamp across the servers when the transaction commits. The requesting server might know about a higher timestamp in the later write requests. So the requesting server communicates with all the participating servers about the highest timestamp it received when the transaction commits. This fits very well with the standard [two-phase-commit] protocol for implementing transactions.

Following is the example of how the highest timestamp is determined at transaction commit. Assume that there are three servers. Server Blue stores names and Server Green stores titles. There is a separate server which acts as a coordinator. As can be seen, each server has a different local clock value. This can be a single integer or hybrid clock. The server acting as a coordinator starts writing to server Blue with the clock value known to it, which is 1. But Blue's clock is at 2, so it increments that and writes the value at timestamp 3. Timestamp 3 is returned to the coordinator in the response. For all subsequent requests to other servers, the coordinator uses timestamp of 3. Server Green, receiving the timestamp value 3 in the request, but it's clock is at 4. So it picks up the highest value, which is 4. Increments it and writes the value at 5 and returns timestamp 5 to the coordinator. When the transaction commits, the coordinator uses the highest timestamp it received to commit the transaction. All the values updated in the transaction will be stored at this highest timestamp.

Figure 1: Propagating commit timestamp across servers

A very simplified code for timestamp handling with transactions looks like this:

class TransactionCoordinator…

  public Transaction beginTransaction() {
      return new Transaction(UUID.randomUUID().toString());
  }

  public void putTransactionally() {
      Transaction txn = beginTransaction();
      HybridTimestamp coordinatorTime = new HybridTimestamp(1);
      HybridTimestamp server1WriteTime
              = server1.write("name", "Alice", coordinatorTime, txn);

      HybridTimestamp server2WriteTime = server2.write("title", "Microservices", server1WriteTime, txn);

      HybridTimestamp commitTimestamp = server1WriteTime.max(server2WriteTime);
      commit(txn, commitTimestamp);
  }

  private void commit(Transaction txn, HybridTimestamp commitTimestamp) {
      server1.commitTxn("name", commitTimestamp, txn);
      server2.commitTxn("title", commitTimestamp, txn);
  }

Transaction implementation can also use the prepare phase of the two phase commit protocol to learn about the highest timestamp used by each participating server.