If you want a replicated database to be as simple as possible to use, you should make it behave as if it were a consistent single-node database. Then users don’t have to worry…
- 11.01LinearizabilityIf you want a replicated database to be as simple as possible to use, you should make it behave as if it were a consistent single-node database. Then users don’t have to worry…
- 11.02What Makes a System Linearizable?To understand linearizability better, let’s look at more examples. Figure 10-2 shows three clients concurrently reading and writing the same object x in a linearizable…
- 11.03Linearizability Versus SerializabilityLinearizability is easily confused with serializability (see “Serializability”), as both words seem to mean something like “can be arranged in a sequential order.” However,…
- 11.04Relying on LinearizabilityIn what circumstances is linearizability useful? Viewing the final score of a sporting match is perhaps a frivolous example; a result that is outdated by a few seconds is…
- 11.05Implementing Linearizable SystemsNow that we’ve looked at a few examples in which linearizability is useful, let’s think about how we might implement a system that offers linearizable semantics.
- 11.06The Cost of LinearizabilityAs some replication methods can provide linearizability and others cannot, it is interesting to explore the pros and cons of linearizability in more depth.
- 11.07ID Generators and Logical ClocksIn many applications you need to assign some sort of unique ID to database records when they are created, which gives you a primary key for referencing those records. In…
- 11.08Logical ClocksIn “Unreliable Clocks” we discussed time-of-day clocks and monotonic clocks. Both are physical clocks: hardware devices that measure the passing of time (seconds, milliseconds,…
- 11.09Linearizable ID GeneratorsAlthough Lamport clocks and hybrid logical clocks provide useful ordering guarantees, that ordering is still weaker than the linearizable single-node ID generator we talked…
- 11.10ConsensusIn this topic, we have seen several examples of things that are easy when you have only a single node but that get a lot harder if you want fault tolerance:
- 11.11The Impossibility of ConsensusYou may have heard about the FLP result—named after the authors Fischer, Lynch, and Paterson—which proves no algorithm is always able to reach consensus if there is a risk that…
- 11.12The Many Faces of ConsensusConsensus can be expressed in several ways. For example:
- 11.13Consensus in PracticeWe have seen that single-value consensus, CAS, shared logs, and atomic commitment are all equivalent: you can convert a solution to one of these problems into a solution to any…
- 11.14Coordination ServicesConsensus algorithms are useful in any distributed database that wants to offer linearizable operations, and many modern distributed databases use them for replication. But one…
- 11.15Recap: Consistency and ConsensusIn this topic we examined the topic of strong consistency in fault-tolerant systems: what it is and how to achieve it. We looked in depth at linearizability, a popular…