Hybrid Logical Clock

Written
  • This one combines the advantages of physical time with a logical counter to make it more resilient.
  • Sources:
  • The clock starts out storing the current physical time and also a counter of 0.
  • Most of the time they store a node ID too as a tie breaker in case of identical timestamps and counters.
  • When an event occurs locally:
    • If the current time is greater than the one in the clock, update it and set the counter back to 0.
    • Otherwise increment the counter.
  • When receiving an event from somewhere else, update the clock as follows:
    • Look at the current physical time, the clock’s physical time, and the incoming event’s physical time.
    • If the current physical time is the greatest, use it and reset the counter.
    • If the incoming event’s physical time is the greatest, use it and also use the incoming event’s counter.
    • If the clock’s physical time is equal to the incoming event’s, use the higher logical clock value between the two (plus 1).
  • To compare two HLC timestamps, just compare the physical clock, then the logical counter, then the node ID.
  • So basically the physical time gets set to the highest seen from any other node when anything happens. This fixes the problem where various nodes are running at different times since all the nodes quickly get updated to the latest clock value.
  • You still want to do some sort of checking around nodes being too far in the future, since setting the physical time really far ahead effectively reduces this timestamp to a Lamport timestamp.

Thanks for reading! If you have any questions or comments, please send me a note on Twitter. And if you enjoyed this, I also have a newsletter where I send out interesting things I read and the occasional nature photo.

You can check out a recent issue, or enter your email below to subscribe.