System Design

Causality: Transaction A could happen before B, after or concurrently. In the first 2 cases, there is said to be causal connection between the transactions. Cross channel timing dependencies: if there are 2 communication channels between 2 systems, one slow channel can break causality. Causal order is not equal to total order. Linearizability, by definition,gives the latter because it makes the system behave as if there is a single copy of the data. However, has a performance penalty and many systems that pretend to require linearizability, in reality, only require causality. Lamport clocks. How are they different from version vectors?

Physical clocks aren’t reliable in a distributed system. (Basically, assume that each server has different timestamps all the time.) Therefore, logical clocks help. Two main algorithms: Lamport clocks. Version vectors. (Somewhat related to but different from “version clocks”. Haven’t dug into details though.) What are “events”? Server receives a message or request from a client. Inter-server communication (i.e. when a server receives message from another server). On differences, I won’t describe how the two algorithms work as that would be too much stuff to write down. However, I’ll describe key implications of the two. Lamport clocks. If a happened-before b, it implies L(a) < L(b). However, if you are given L(a) and L(b) such that L(a) < L(b), all that means is b did not happen-before a. You can’t deduce anything else. If you have a bunch of events, you can deduce a total order which is consistent with causality. So, if two events had a happened-before relationship, they will be ordered correctly in the result. However, you can’t pick any two events from the order and deduce that the one earlier had happened-before the other. Basically, the total order is some order which is consistent with causality. It is not the actual order in which events occured in physical time. Version vectors. Each data record is associated with a vector. Each element in the vector is associated with a server that had processed that record. a -> b implies V(a) < V(b), both ways. That’s the key difference from Lamport clocks. Given any two events and their version vectors, you can identify whether one of them happened-before the other or they were concurrent. Important note: happens-before has nothing to with whether one event happened before the other in physical time. Instead, it means whether they are causally connected: one caused the other. Helpful resources: ...