tags : Representing Time and Date, Distributed Systems, crdt, Consensus Protocols
Overview
- Time & State: https://queue.acm.org/detail.cfm?id=2745385 (There is No Now)
- Logical clocks, vector clocks, hybrid logical clocks, snapshots
- They form the basis of
- crdt
- version vectors in NoSQL databases
- snapshot reads and commits in distributed SQL databases build upon.
- They form the basis of
FAQ
About state and Time
To read
- “relativity means there is no such thing as simultaneity” used as an argument that synchronized clocks cannot exist.
- This is a misunderstanding
- the equations of special and general relativity provide exact equations for time transformations, and it is possible to define any number of sensible, globally-synchronized time clocks.
- Consistency constraints that refer to these clocks will depend on the choice of clock
- e.g. depending on one’s reference frame, a system might or might not provide linearizability. See Concurrency Consistency Models
- The good news is that
- For all intents and purposes, clocks on earth are so close to each other’s velocities and accelerations that errors are much smaller than side-channel latencies
- Many of the algorithms for ensuring real-time bounds in asynchronous networks use causal messages to enforce a real-time order, and the resulting order is therefore invariant across all reference frames.
- This is a misunderstanding
Monotonic?
Lamport Clocks (Total order)
Vector Clocks (Partial order)
Timestamps and Databases
- I can’t find the original post now, but there’s a good suggestion that booleans should usually be timestamps
- UPDATE orders SET deletion_timestamp = CURRENT_TIMESTAMP() WHERE deletion_timestamp IS NULL
- See Database Locks
- See Bug story: Sorting by timestamp | Hacker News