# Distributed Clocks


![left](./student-guide/diagram/11-Clock-01-01.png)
------------------------------------------------------------

In the paper “A Critique of ANSI SQL Isolation Levels”, a general scheme of Snapshot Isolation is proposed:
  1. The read operation of the transaction reads data from the committed snapshot. The snapshot time can be any time before the first read operation of the transaction, and is recorded as StartTimestamp.
  2. When the transaction is ready to commit, get a commitTimestamp, which needs to be larger than the existing startTimestamp and commitTimestamp.
  3. A transaction is checked for conflicts when it is committed. If no other transaction submits data that intersects with its own WriteSet in the [StartTS, commitTS] interval, this transaction can be committed; the Lost Update exception is prevented here.
  4. SI allows transaction to be executed with very old StartTs so that they are not blocked by any write or read a history; of course, if committed with an old CommitTS, it will most likely be Abort.

From the above scenario, the core needs an incremental sequence number to implement StartTS and CommitTS, and distributed storage systems usually have two schemes in order to implement incremental serial numbers: global issuer and clock. Since there is no absolute time agreement in distributed systems, two schemes are differentiated: absolute time and relative time, where absolute time is the scheme. It is mainly Google's TrueTime scheme, and relative time includes physical clocks (Physical Clocks), Logic Clocks (Logic Clocks), Vector Clocks (Vector Clocks), and Hybrid Logic Clocks (Hybrid Logic Clocks).

There are three main types of clocking schemes that typically implement Snapshot Isolation: global issuer schemes, TrueTime schemes, and mixed-logic clock schemes. Among them, Percolator and TiDB adopted a global issuer scheme; Spanner pioneered and used a TrueTime scheme based on atomic clocks and GPS; and MongoDB, CockroachDB, and YugabyteDB adopted a hybrid logic clock scheme. The following table briefly lists typical implement of the three scenarios:
  - TrueTime, TrueTime is the way Google Spanner uses, but it requires hardware GPS+ atomic clock support, and it is difficult to implement it yourself outside.
  - HLC, HLC is a hybrid logic clock that uses Physical Time and Logical Clock to determine the order of events. HLC is already used in some applications, but HLC relies on NTP, if the NTP precision error is large, it is likely to affect the commit wait time. The error in the network environment is within 500ms.
  - TSO, which is a global timer that directly allocates time using a single point of service. TSO is simple, but there is a single point of failure, and a single point of failure may also have performance issues.