Timestamps

this article provides a detailed overview of the various timestamps the big peer uses to enforce causal consistency and high availability ust a unique universally stable timestamp ( ust ) indicates its order in the sequence of events, causal relationship to other events, and conflict resolution mechanisms to handle concurrency conflicts and enable non blocking reads the ust maintains its value and consistency over time so event ordering remains intact and reliable computing ust regardless of the view of the ust, the big peer reflects a causally consistent version of the database that can be read by small peers this is due to each small peer committing their highest (maximum) transactions to local storage once committed, they gossip their committed maximums across peers each small peer computes the ust by determining the lowest transaction among the set — the lowest common denominator, if you will which is then considered to be the upper limit and therefore represents the ust of the various maximums that have been committed, the minimum refers to the lowest transaction among the set — the lowest common denominator, if you will simple three node cluster example to further explain, consider the following scenario of a three node cluster server a commits transaction 10 server b commits transaction 5 server c commits transaction 7 given this scenario, the ust is 5 each server may have a different transactional view of the ust, depending on the duration of time required for them to finish gossiping their transactions with each other a transactional view is the snapshot of data that a transaction observes during execution complex three node cluster example in a concurrent, multi user environment, conflicting transactions can run simultaneously at any point as a result, each transaction receives its individual data view to guarantee consistency and isolation for example, consider the following complex scenario within a three node cluster, as indicated by servers a, b, and c in the graphic event 1 event 2 event 3 server a commits transaction 10 server b gossips to server a that it has committed transaction 4 server c gossips to server a that it has committed transaction 6 server a computes the ust as 4 server b commits transaction 5 server a gossips to server b that it has committed transaction 7 server c gossips to server b that it has committed transaction 6 server b computes the ust as 5 server c commits transaction 7 server a gossips to server c it has committed transaction 9 server b gossips to server c it has committed transaction 2 server c computes the ust as 3 given this scenario, all three servers retain a causally consistent version of the database that remains readable this remains true even though each server maintains a distinct view of the ust ust behaviors the ust changes on every storage node in the cluster depending on the state of the big peer when actively processing transactions, the ust increments when quiescent and inactive, the ust reflects the last transaction produced by the transaction log and does not increment garbage collection timestamps the big peer uses the gc timestamp to determine which data are candidates for purging across the distributed database, while storage nodes use local gc timestamps to determine which data to purge from its local environment similar to ust, the gc timestamp represents the lowest transaction timestamp in the cluster — all versions within the cluster that fall below the gc timestamp get rolled up or merged, re writing them as a single value calculating gc timestamp the gc timestamp is calculated based on the minimum active read transaction timestamp across the entire cluster the local gc timestamp is the highest transaction below the minimum read transaction after the query is completed, the read transaction is purged from memory, allowing the gc timestamp to increase the ust and the gc work together to form a sliding window of versions over the database this window represents the timestamp versions at which a causally consistent query can execute assigning queries predetermined timestamps the coordinator assigns a predetermined timestamp to the query for each partition typically, this timestamp matches the ust at the coordinator's location but can fall between the cluster wide garbage collection (gc) timestamps and the ust when a node coordinates a read transaction, it maintains certain metadata in memory, indicating the ust's value at the transaction's start this data helps calculate the local gc timestamp that the node shares during gossip when a node is not actively executing a read transaction, to ensure continuous progress, it continues to gossip its view of the ust as the gc timestamp in a quiet cluster with no ongoing reads, the gc timestamp matches the ust, resulting in only one version of each data item