Wednesday, January 12, 2022

Hybrid Clock


Hybrid Logical Clock gives a method to have a model
which is monotonically growing identical to a easy integer, but in addition has relation with the precise date time.
Hybrid clocks are utilized in apply by databases like mongodb
or cockroachdb.

A Hybrid Logical Clock is carried out as follows:

class HybridClock…

  public class HybridClock {
      non-public remaining SystemClock systemClock;
      non-public HybridTimestamp latestTime;
      public HybridClock(SystemClock systemClock) {
          this.systemClock = systemClock;
          this.latestTime = new HybridTimestamp(systemClock.currentTimeMillis(), 0);

It maintains the newest time for example of the hybrid timestamp, which is constructed through the use of system time and an integer counter.

class HybridTimestamp…

  public class HybridTimestamp implements Comparable<HybridTimestamp> {
      non-public remaining lengthy wallClockTime;
      non-public remaining int ticks;
      public HybridTimestamp(lengthy systemTime, int ticks) {
          this.wallClockTime = systemTime;
          this.ticks = ticks;
      public static HybridTimestamp fromSystemTime(lengthy systemTime) {
          return new HybridTimestamp(systemTime, -1); //initializing with -1 in order that addTicks resets it to 0
      public HybridTimestamp max(HybridTimestamp different) {
          if (this.getWallClockTime() == different.getWallClockTime()) {
              return this.getTicks() > different.getTicks()? this:different;
          return this.getWallClockTime() > different.getWallClockTime()?this:different;
      public lengthy getWallClockTime() {
          return wallClockTime;
      public HybridTimestamp addTicks(int ticks) {
          return new HybridTimestamp(wallClockTime, this.ticks + ticks);
      public int getTicks() {
          return ticks;
      public int compareTo(HybridTimestamp different) {
          if (this.wallClockTime == different.wallClockTime) {
              return Integer.evaluate(this.ticks, different.ticks);
          return Lengthy.evaluate(this.wallClockTime, different.wallClockTime);

Hybrid clocks can be utilized precisely the identical means because the Lamport Clock variations.
Each server holds an occasion of a hybrid clock.

class Server…

  HybridClockMVCCStore mvccStore;
  HybridClock clock;

  public Server(HybridClockMVCCStore mvccStore) {
      this.clock = new HybridClock(new SystemClock());
      this.mvccStore = mvccStore;

Each time a worth is written, a hybrid timestamp is related to it.
The trick is to examine if the system time worth goes again in time, in that case
increment one other quantity representing a logical a part of the element to mirror clock progress.

class HybridClock…

  public synchronized HybridTimestamp now() {
      lengthy currentTimeMillis = systemClock.currentTimeMillis();
      if (latestTime.getWallClockTime() >= currentTimeMillis) {
           latestTime = latestTime.addTicks(1);
      } else {
          latestTime = new HybridTimestamp(currentTimeMillis, 0);
      return latestTime;

Each write request {that a} server receives from the consumer carries a timestamp.
The receiving server compares its personal timestamp to that of the request and units it is personal timestamp
to the upper of the 2

class Server…

  public HybridTimestamp write(String key, String worth, HybridTimestamp requestTimestamp) {
      //replace personal clock to mirror causality
      HybridTimestamp writeAtTimestamp = clock.tick(requestTimestamp);
      mvccStore.put(key, writeAtTimestamp, worth);
      return writeAtTimestamp;

class HybridClock…

  public synchronized HybridTimestamp tick(HybridTimestamp requestTime) {
      lengthy nowMillis = systemClock.currentTimeMillis();
      //set ticks to -1, in order that, if that is the max, the following addTicks reset it to zero.
      HybridTimestamp now = HybridTimestamp.fromSystemTime(nowMillis);
      latestTime = max(now, requestTime, latestTime);
      latestTime = latestTime.addTicks(1);
      return latestTime;

  non-public HybridTimestamp max(HybridTimestamp ...occasions) {
      HybridTimestamp maxTime = occasions[0];
      for (int i = 1; i < occasions.size; i++) {
          maxTime = maxTime.max(occasions[i]);
      return maxTime;

The timestamp used for writing the worth is returned to the consumer.
The requesting consumer updates its personal timestamp after which makes use of this timestamp to concern any additional writes.

class Consumer…

  HybridClock clock = new HybridClock(new SystemClock());
  public void write() {
      HybridTimestamp server1WrittenAt = server1.write("key1", "value1",;

      HybridTimestamp server2WrittenAt = server2.write("key2", "value2",;

      assertTrue(server2WrittenAt.compareTo(server1WrittenAt) > 0);

Multiversion storage with Hybrid Clock

A hybrid timestamp can be utilized as a model when the worth is saved in a key worth retailer.
The values are saved as mentioned in Versioned Worth.

class HybridClockReplicatedKVStore…

  non-public Response applySetValueCommand(VersionedSetValueCommand setValueCommand) {
      mvccStore.put(setValueCommand.getKey(), setValueCommand.timestamp, setValueCommand.worth);
      Response response = Response.success(setValueCommand.timestamp);
      return response;

class HybridClockMVCCStore…

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

  public void put(String key, HybridTimestamp model, String worth) {
      kv.put(new HybridClockKey(key, model), worth);

class HybridClockKey…

  public class HybridClockKey implements Comparable<HybridClockKey> {
      non-public String key;
      non-public HybridTimestamp model;
      public HybridClockKey(String key, HybridTimestamp model) {
          this.key = key;
          this.model = model;
      public String getKey() {
          return key;
      public HybridTimestamp getVersion() {
          return model;
      public int compareTo(HybridClockKey o) {
          int keyCompare = this.key.compareTo(o.key);
          if (keyCompare == 0) {
              return this.model.compareTo(o.model);
          return keyCompare;

The values are learn precisely as mentioned within the Ordering of the versioned keys.
The versioned keys are organized in such a means as to type a pure ordering through the use of hybrid timestamps
as a suffix to the important thing.
This implementation allows us to get values for a selected model utilizing the navigable map API.

class HybridClockMVCCStore…

  public Non-compulsory<String> get(String key, HybridTimestamp atTimestamp) {
      Map.Entry<HybridClockKey, String> versionKeys = kv.floorEntry(new HybridClockKey(key, atTimestamp));
      getLogger().data("Obtainable model keys " + versionKeys + ". Studying@" + versionKeys);
      return (versionKeys == null)? Non-compulsory.empty(): Non-compulsory.of(versionKeys.getValue());

Changing hybrid timestamp so far time

A hybrid clock could be transformed into an precise timestamp
worth by merging the system timestamp and the logical clicks quantity.
As mentioned within the [hybrid-clock] paper, the primary 48 bits of the system time could be preserved,
and decrease order 16 bits could be changed by the logical counter.

class HybridTimestamp…

      public LocalDateTime toDateTime() {
          return LocalDateTime.ofInstant(Instantaneous.ofEpochMilli(epochMillis()), ZoneOffset.UTC);
      public lengthy epochMillis()  (ticks << 48 >> 48);

Assigning timestamp to distributed transactions

Databases like [mongodb] and [cockroachdb]
use a Hybrid Clock to take care of causality with distributed transactions.
With distributed transactions, it is vital to notice that,
all of the values saved as a part of the transaction needs to be saved on the similar timestamp throughout the servers
when the transaction commits.
The requesting server would possibly learn about a better timestamp within the later write requests.
So the requesting server communicates with all of the taking part servers in regards to the highest timestamp
it acquired when the transaction commits.
This suits very nicely with the usual [two-phase-commit] protocol for implementing transactions.

Following is the instance of how the best timestamp is set at transaction commit.
Assume that there are three servers. Server Blue shops names and Server Inexperienced shops titles.
There’s a separate server which acts as a coordinator.
As could be seen, every server has a distinct native clock worth. This could be a single integer or hybrid clock.
The server appearing as a coordinator begins writing to server Blue with the clock worth recognized to
it, which is 1.
However Blue’s clock is at 2, so it increments that and writes the worth at timestamp 3.
Timestamp 3 is returned to the coordinator within the response.
For all subsequent requests to different servers, the coordinator makes use of timestamp of three.
Server Inexperienced, receiving the timestamp worth 3 within the request, but it surely’s clock is at 4.
So it picks up the best worth, which is 4. Increments it and writes the worth at 5
and returns timestamp 5 to the coordinator.
When the transaction commits, the coordinator makes use of the best timestamp it acquired to commit the transaction.
All of the values up to date within the transaction will probably be saved at this highest timestamp.

Determine 1: Propagating commit timestamp throughout servers

A really simplified code for timestamp dealing with with transactions seems 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("identify", "Alice", coordinatorTime, txn);

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

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

  non-public void commit(Transaction txn, HybridTimestamp commitTimestamp) {
      server1.commitTxn("identify", commitTimestamp, txn);
      server2.commitTxn("title", commitTimestamp, txn);

Transaction implementation may also use the put together section of the 2 section commit protocol
to study in regards to the highest timestamp utilized by every taking part server.



  1. Its like you read my mind! You seem to know a lot
    about this, like you wrote the book in it or something.
    I think that you could do with some pics to drive the message home a little bit, but instead of that, this is magnificent blog.
    A fantastic read. I’ll definitely be back.

Most Popular

Recent Comments