Distributed Systems and Consistency Models

Consistency and Consensus

• Consistency and consensus are key principles in data-intensive systems, specifically in replicated databases.
• Replication lag can lead to problems with eventual consistency, creating situations where a read from a stale replica returns an outdated value.
• To avoid this anomaly, read-after-write consistency is needed.
• Most replicated databases use eventual consistency. This means eventually all read requests will return the same value after a period of time.
• The problem is determining exactly when this consistency will happen, as it's not specified. This isn't a strong guarantee for a database.
• Stronger consistency guarantees can lead to better performance or less fault tolerance when compared to systems with weaker guarantees and can be difficult to use properly.

Consistency Guarantees

• Transaction isolation is about preventing race conditions due to concurrent transactions.
• Distributed consistency is about coordinating the state of replicas in the face of delays and failures.

Linearizability

• Linearizability provides the illusion of a single replica by abstracting away implementation details.
• It guarantees that any read or write operation will produce the same results as if all operations were executed in a specific, predetermined order.
• Operations can appear linear in time.
• As soon as a client completes a write, all other clients reading from the database must be able to see the new value at some point in time. Implies recency.

Linearizability - Example

• If there is a read concurrent with a write, during that time it may appear either as if the read was performed before the write, or after it.

What Makes a System Linearizable?

• The basic concept behind linearizability is to make a system appear as if there is only a single copy of the data.
• At some point in time during a write operation, the value changes atomically.
• If a client's read returns the new value, all subsequent reads must also return the new value, regardless of when other operations are processed.

Linearizable? -- Example

• If a read occurs concurrently with a write, the read may return either the old or new value.
• The read may also see the value flip back and forth between old and new several times.

What Makes a System Linearizable?

• In a linearizable system, an operation must be performed at some point in time during the operation's duration.
• If a client's read returns the new value, all subsequent reads must also return the new value. This guarantees data integrity and consistency.

Linearizability Versus Serializability

• Serializability is an isolation property of transactions that ensures transactions behave as if they had been executed in a serial order.
• Linearizability guarantees recency of individual objects, without necessarily grouping operations into transactions.
• Linearizability does not prevent issues like write skew or phantoms.

Linearizability Versus Serializability

• A database can offer both serializability and linearizability, potentially called strict serializability or strong one-copy serializability.
• Implemented serial executions based on two-phase locking or actual serial execution can be linearizable.
• Serializable snapshot isolation is not guaranteed to be linearizable.
• Reads from snapshots are not typically linearizable.

Relying on Linearizability

• Linearizability is useful in various scenarios, such as locking, leader election. constraints, and uniqueness guarantees, as well as cross-channel timing dependencies.

Relying on Linearizability: Locking and Leader Election

• A system that uses a single leader for replication must ensure there is only one leader.
• Leader election can often use a lock.
• A lock must be linearizable --all nodes must agree which node owns the lock. This is crucial for the system's correctness.

Relying on Linearizability: Locking and Leader Election - Examples

• Using a service like Apache ZooKeeper or etcd to implement distributed locks or leader elections.

Relying on Linearizability: Constraints and Uniqueness Guarantees

• Enforcing unique usernames (e.g., one user per account).
• Preventing two people from simultaneously reserving the same seat on a flight.
• Hard uniqueness constraint (common in relational databases) requires linearizability.

Relying on Linearizability: Cross-channel Timing Dependencies

• Example use case that has a read write cycle involving files and a message queue.
• The resizing could happen before the message or after if there is a network error.

Relying on Linearizability: Cross-channel Timing Dependencies

• If the file storage service isn't linearizable, there is a risk of a race condition.
• Message queue could be faster than internal replication leading to the resizer fetching older versions of the image.

Implementing Linearizable Systems

• Common approach to fault tolerance is replication (e.g., single leader replication, multi-leader replication or headless replication).
• Single-leader replication is often described as potentially linearizable.
• Consensus algorithms are a technique that implements linearizable operations.

Implementing Linearizable Systems

• Single-leader replication is potentially linearizable.
• Reads from the leader or synchronously updated followers are also commonly linearizeable.
• In contrast, multi-leader replication (concurrency on multiple nodes) and headless replication typically do not produce results that can be used for linearizability.

Implementing Linearizable Systems

• With single-leader replication, reads and writes must be directed to the leader.
• In the event of a network partition, clients on follower nodes cannot make any writes or linearizable reads. However, reads might be possible, but these could be stale.

The CAP Theorem

• The CAP theorem (Consistency, Availability, Partition tolerance) highlights a fundamental trade-off in distributed systems
• Any linearizable database must deal with this tradeoff,
• With high consistency, there's likely much lower availability during a network issue.
• If a system needs high availability during a networking issue, the consistency is much lower.

The CAP Theorem

• If your application requires linearizability and some replicas are disconnected, then those replicas must either wait for the issue to be resolved or otherwise return an error. This results in unavailability in the case of a network interruption.

The CAP Theorem

• If you don't require linearizability, you can build a system where each replica can run independently, and the application can remain available even if network problems occur. The trade-off is that the system's behavior would then not be guaranteed to be linearizable.

The CAP Theorem - The Key

• The CAP theorem shows that in distributed systems, you can achieve at most two of the three characteristics - consistency, availability and partition tolerance-and that in the face of a failure you must sacrifice one of those.

Linearizability and Network Delays

• Linearizability can be slow (high response times), even without a network fault.
• A large part of the reason for this is that linearizable reads and writes are often not used due to the high performance cost that they come with.

Ordering Guarantees

• Linearizability is strongly connected to ordering and consensus.
• This is because when you are thinking about how to enforce proper ordering, you are implicitly thinking about enforcing proper consensus.
• Operations must be performed in an order to satisfy linearizability.

Ordering and Causality

• Ordering is crucial to reflect causality (cause-and-effect relationships between operations).
• A message should be sent before it is received.
• In general, a question should come before an answer.
• Order and causality impose their own order on events.

Ordering and Causality

• A causally consistent system correctly obeys the ordering demanded by causality.
• Previous examples shown in classes indicate that causality is very important for enforcing reliability in distributed systems.
• There are examples in the text that support this idea.

Ordering and Causality

• The concept of causality is linked to how an ordering of operations may be consistent with how the operations occurred as seen from client view points.
• Operations can be causally dependent on previous operations without being totally ordered.
• This is where snapshot isolation examples would be useful.

Ordering and Causality - Key Ideas

• A snapshot reflects operations that took place up to a certain point in time.
• Write skew - a different ordering of operations on a database compared to an idealized ordering that would create issues.
• Consistent prefix reads - if there is a causal dependency between a question and an answer, then they should show up in an order that supports this dependency.

Ordering and Causality: Causal Order Not a Total Order

• Causal order only provides a partial ordering, in contrast to linearizability which provides a total order.
• Total order means every operation can be totally ranked relative to every other operation.
• Partial order means some operations have no guaranteed order relative to others that execute concurrently.

Ordering and Causality - Key Concepts

• There is a single timeline for operations if a totally ordered execution pattern can be used.
• Concurrent operations don't necessarily have a guaranteed total order unless other constraints exist.

Ordering and Causality: Linearizability is Stronger than Causal Consistency

• Linearizability includes the guarantee of causal ordering; no additional mechanisms needed.
• Other approaches for causality consistency (alternative methods) exist that might not have as strong guarantees. This means there is other work that can be done and should be considered.

Sequence Number Ordering

• Sequence numbers or timestamps are commonly used to order events.
• Every operation is assigned a unique sequence number, allowing them to be ordered.
• Sequence numbers enable the development of a consistent total ordering with causality.

Lamport Timestamps

• Lamport timestamps offer a method for generating sequence numbers that is consistent with causality.
• Each node has a unique identifier and a counter.
• Lamport timestamp includes the (counter, nodeID) pair to generate a total order of operations.

Lamport Timestamps

• Timestamps are used for determining a total order from concurrent operations across multiple nodes or processes.
• If counters are the same, NodeID (identifier) is used to compare sequence numbers and generate a total order.

Lamport Timestamps - Key Concepts

• Timestamps generated by Lamport's algorithm will always result in a consistent order of operations
• Timestamps are used for generating sequence numbers and for generating consistent ordering within a distributed system. The algorithm used will ensure that any conflicts between sequence numbers due to concurrent events or activities are resolved in a consistent manner.

Total Order Broadcast

• Total order broadcast is a protocol for exchanging messages in distributed systems.
• It ensures that every node receives messages in a consistent, predetermined order.
• Messages can be delayed but eventually delivered to all nodes with the intended ordering.

Using Total Order Broadcast

• Total order broadcast can be used to reliably replicate data in distributed systems. Ensuring the same writes are received and processed in the same order across all data replicas/ copies guarantees consistent integrity between copies, even with temporary lags.
• It can be used to create a log, effectively appending messages in order to the log.

Total Order Broadcast - Key Concepts

• Total order broadcasting, in practice, means consistent total ordering in situations where there is message delay or failure.

Distributed Transactions and Consensus

• Consensus is fundamental in distributed systems; it guarantees the agreement on values across multiple nodes.
• Leader election, and atomic commit are examples of areas requiring consensus.

Distributed Transactions and Consensus

• Atomic commits means that either every node is committed or every node must be rolled back,
• A Transaction may succeed at some nodes and fail at others; resulting in inconsistent data between copies/replicas.

Distributed Transactions and Two-Phase Commit

• Two-Phase Commit (2PC) is a consensus algorithm for atomic commits.
• It has two phases (prepare and commit) for a coordinated commit or abort.

Atomic Commit and Two-Phase Commit

• Two Phase Commit (2PC) - coordinator sends a message prepare to nodes that it is ready to commit
• If every node responds ok, the Coordinator sends a commit or abort response.
• Failures in either phase often involve repeating (re-attempting) messages until success.

Atomic Commit and Two-Phase Commit - Key Concepts

• Two-Phase Commit (2PC) is a key tool that can be used to create a consistent state between replicas/ copies of data in distributed systems that may experience failures. A failure in one step/phase during a 2PC operation could result in an inconsistent data state between copies unless the messages are repeated until the 2PC operation is completed successfully.

Atomic Commit and Two-Phase Commit

• Node and coordinator failures can lead to problems in 2PC operations
• Coordinator failure can affect the transaction unless the log is recovered.
• Recovery mechanisms may be needed to properly recover a replicated database's data.

Fault-Tolerant Consensus

• The goals of fault-tolerant consensus include guaranteeing the uniform agreement, integrity of the decision (a single decision and choice) and guaranteeing a eventual decision among nodes.
• There is a limit on how many nodes can fail. Usually this limit is something less than half of the total.

Fault-Tolerant Consensus

• Fault-tolerant consensus ensures nodes agree on a decision even with failures.
• Methods such as viewstamped replication (VSR), Paxos, Raft, Zab are common consensus algorithms.
• Consensus algorithms often use similar high level ideas for solving problems arising from failures or network issues to solve these issues in a consistent manner.

Fault-Tolerant Consensus: Single-Leader Replication and Consensus

• Automatic leader election/ failover requires a consensus algorithm,
• Selecting a new leader correctly and avoiding issues during failures requires a consensus algorithm.
• The leader has consistent knowledge to apply writes to the system's other replicas.

Fault-Tolerant Consensus: Epoch Numbering and Quorum

• Consensus algorithms use epoch numbering to maintain order and ensure the correct leader.
• Quorum ensures that enough nodes participate to guarantee the decision.
• Quorums provide a technique that improves robustness by distributing writes/ data across many members of a quorum.

Membership and Coordination Services

• Services like ZooKeeper or etcd provide high-performance coordination for distributed applications.
• They often implement consensus algorithms and handle system configuration.

Membership and Coordination Services - Use Cases

• Selecting leaders for single-leader databases, or for selecting partitions for use in distributed replicated systems.

Membership and Coordination Services - Use Cases

• Often used in the background to coordinate activities across different systems and members of a distributed system.
• ZooKeeper or etcd is frequently used for distributed locks and leases. This is because they are consistent with concurrency controls across multiple replicas of data.