Order and It's Guarantees
Causality gives a partial order: an event must follow the events that caused it, while unrelated events may have no meaningful order.
Linearizability goes further by making all operations appear in one real-time-respecting order.
#sequencenumberordering
Tracking every causal dependency is expensive. A sequence number is an increasing counter; a logical timestamp is one produced by the system rather than a wall clock. In single-leader replication, the leader's log gives followers one total order of writes.
#noncausalsequencenumbering
Non causal sequence numbering is used in leaderless/multileader replication/partitioned applications but there are some used metods in practice:
- number being generated by a range by node. ex: odd and even between two node.
- attaching timestamp, which might be sufficiente for total ordering of events.
- preallocation on a block of numbers
All these three methods are inconsistent with causality.
#lamporttimestamp #lamport #timestamps
- its key composed by the N operations processed by the node and the node ID.
If you have the same amount of operations, the one with the greater ID is the greater timestamp.
This idea by itself doesnt make it totally casually consistent; the key idea behing Lamport timestamps is:
"Every node and client keeps track of the maximum counter value it has seen so far, and includes that maximum on every request. When a node receiver a req o resp with a maximum greater than its own counter value, it immediatelly increases its own to this maximum"
Lamport Timestamps ARE NOT Version Vectors. They seem similar, but have different purposes: version vector can tell wether two operations are concurrent or whether one is causally dependent on the another operation.
Lamport Timestamps enforce TOTAL ORDERING.
Total ordering alone does not ensure unique values unless every participant uses the same order. Total-order broadcast, also called atomic broadcast, provides that shared delivery order.
Total-order broadcast provides two guarantees:
- Reliable Delivery: no messages are lost. if delivered, they are all delivered to all nodes.
- Totally Ordered Delivery: all nodes receive the message in the same order
Examples of services that implement Total Order Broadcast. ZooKeeper and etcd.
If every replica applies the same ordered writes, they reach the same state. This is state-machine replication.
Total-order broadcast can implement fencing tokens: each lock request is appended to the log and gets a sequence number. The sequence itself can reject stale writers; ZooKeeper calls its transaction sequence zxid.
#distributedtransactions