Tymofii
  1. Notes
  2. Designing Data-Intensive Applications
  3. Chapter 10

ddia/ch10.md - DDIA

Linearizability vs serializability

  • Linearizability
    • Concept from distributed systems
      • Often used interchangeably with strong consistency
    • Guarantees that writes appear to be instantaneous. Once a write completes, all later reads (where “later” is defined by wall-clock start time) should return the value of that write or the value of a later write. Once a read returns a particular value, all later reads should return that value or the value of a later write.
      • No non-monotonic reads => no need for hacks like read-your-writes.
      • In other words, it a recency guarantee
    • "I have a log of requests and responses that clients observed. Could a correct single-node system have produced exactly this log?"
      • Yes => linearizable. This also means that all operations on single-node are linearizable
      • No => not linearizable.
    • SSI is not linearizable! Because you do not necessarily see the most recent write
      • Unlike SSI, 2PL and serial execution ARE linearizable, because you put locks on resources and read cannot happen
      • enforcing linearizability would reduce the level of concurrency that the database can offer
  • Serializability
    • Concept from databases
    • Guarantees that the complete history of all concurrent transactions must be equivalent to some sequential execution of those same transactions
  • Strict Serializability = Linearizability + Serializability
    • Note that global linearizability DOES NOT imply serializability! Because linearizability is about single-object and serializability can be violated by anomalies such as write skew which operate over multiple objects.

When we need linearizability?

  • Split brain danger: leader election, single-leader replication, etc.
  • Distributed locks in storages. If you have a a service that grants locks, it MUST be linearizable, otherwise conflicts on write, corrupted data, etc.
    • (kinda split brain problem, or "unsync knowledge")
  • Constraints. (generalization of above case^^)
    • Think of it as ensuring the "critical section" is executed only by 1 node.
    • Examples: uniqueness

How to implement linearizability?

  • Simplest: have single copy of the data
  • Single-leader replication:
    • always read and write from the leader. never from the followers
    • solve the split-brain problem
      • example: multiple nodes but only a single leader for routing all requests. we then decide for a failover but the old node still thinks it's a leader. if the client is directly connected to the old leader, the old leader might continue to serve requests.
  • Consensus:
    • Read/write goes to node N1.
    • N1 asks other nodes "Am I still a leader"?
      • Yes => serve from local storage
      • No => don't serve
  • Multi-leader replication: not linearizable
  • Leaderless replication
    • Not linearizable by default
    • If the new value is written only to nodes that do not become part of the quorum during later read, then it's possible to miss this new value (and preceding read would be able to see the new value, if its quorum includes new nodes)
  • Other

Why drop linearizability?

  • Not fault tolerance, but performance.

CAP

  • It's limited - consider only 1 fault type (partitions) and 1 consistency guarantee (linearizability)
  • Don't take too seriously.

References/TODO:

  • https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
  • What can go wrong in distributed system? What is impossible? https://groups.csail.mit.edu/tds/papers/Lynch/podc89.pdf
  • Dive into deeper, more precise results on CAP https://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2036.pdf https://www.cs.tau.ac.il/~mad/publications/podc2015-replds.pdf