Distributed Systems and Consistency Models
43 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What issue arises if the file storage service is not linearizable?

  • Faster upload speeds
  • Inconsistent data between full-size and resized images (correct)
  • Improved image quality
  • No impact on processing times

    • Linearizability can help avoid race conditions when communicating between different services.

    True

    What is one common approach to making a system fault-tolerant?

    Replication

    The message queue and the file storage represent two different ______ in the system.

    <p>communication channels</p> Signup and view all the answers

    Match each replication type with its description:

    <p>Single-leader replication = One primary leader manages updates Multi-leader replication = Multiple leaders handle updates and conflicts Leaderless replication = Any node can accept updates Consensus algorithms = Achieve agreement among distributed nodes</p> Signup and view all the answers

    What is a potential drawback of linearizability?

    <p>It leads to high response times for reads and writes.</p> Signup and view all the answers

    A linearizable system has a total order of operations.

    <p>True</p> Signup and view all the answers

    What does causality impose on events?

    <p>An ordering where cause comes before effect.</p> Signup and view all the answers

    A causally consistent system obeys the ordering required by __________.

    <p>causality</p> Signup and view all the answers

    Which of the following statements is true regarding linearizability and causality?

    <p>Linearizability implies causality.</p> Signup and view all the answers

    Match the following terms with their definitions:

    <p>Linearizability = Behaves as if there is only one copy of the data Causality = Imposes an ordering on events Total Order = For any two operations, we can say which one happened first Partial Order = Some operations are ordered while some are incomparable</p> Signup and view all the answers

    Causal order is considered a total order.

    <p>False</p> Signup and view all the answers

    What must be true in a linearizable datastore regarding concurrent operations?

    <p>There are no concurrent operations.</p> Signup and view all the answers

    What is the primary guarantee of serializability?

    <p>Guarantees that transactions behave as if executed in some serial order</p> Signup and view all the answers

    Linearizability is an isolation property of transactions.

    <p>False</p> Signup and view all the answers

    What is strict serializability?

    <p>The combination of both serializability and linearizability.</p> Signup and view all the answers

    Serializability snapshot isolation is _____ linearizable.

    <p>not</p> Signup and view all the answers

    Match the following concepts with their descriptions:

    <p>Linearizability = A recency guarantee of individual operations Serializability = An isolation property of transactions Two-phase locking = A technique used for ensuring serializability Leader election = A process to determine the active node in a distributed system</p> Signup and view all the answers

    Which of the following scenarios is an application of linearizability?

    <p>Electing a leader in a distributed system</p> Signup and view all the answers

    Implementations of serializability based on two-phase locking can be linearizable.

    <p>True</p> Signup and view all the answers

    What is the purpose of using consensus algorithms in services like Apache ZooKeeper?

    <p>To implement linearizable operations in a fault-tolerant way.</p> Signup and view all the answers

    What is linearizability primarily concerned with?

    <p>Preserving causality automatically</p> Signup and view all the answers

    A system can be causally consistent without being linearizable.

    <p>True</p> Signup and view all the answers

    What is the primary purpose of total order broadcast in database replication?

    <p>To deliver messages in a fixed order</p> Signup and view all the answers

    Total order broadcast provides a guarantee on when messages will be delivered.

    <p>False</p> Signup and view all the answers

    What do Lamport timestamps consist of?

    <p>(counter, nodeID)</p> Signup and view all the answers

    Every operation has a unique sequence number and we can use these sequence numbers to order __________.

    <p>events</p> Signup and view all the answers

    What is the main advantage of linearizability over total order broadcast?

    <p>Linearizability provides a recency guarantee.</p> Signup and view all the answers

    In a two-phase commit algorithm, the first phase is known as the vote ______.

    <p>request</p> Signup and view all the answers

    Which of the following statements is true regarding total order broadcast?

    <p>Messages are delivered reliably and in the same order to all nodes.</p> Signup and view all the answers

    In a distributed transaction, what does the term 'atomic commit' refer to?

    <p>Rolling back all transactions or committing all transactions</p> Signup and view all the answers

    The total order of operations can be determined before collecting all operations.

    <p>False</p> Signup and view all the answers

    If any prepare request fails in a two-phase commit, the coordinator will proceed with the commit.

    <p>False</p> Signup and view all the answers

    What does a node do when it sees a value larger than its current counter in Lamport timestamps?

    <p>It bumps up its counter to match the larger value.</p> Signup and view all the answers

    What happens if a commit request fails in the two-phase commit protocol?

    <p>The coordinator retries the commit request indefinitely.</p> Signup and view all the answers

    What must happen if the coordinator fails after all participants reply 'yes' in Phase 1?

    <p>Participants must wait for the coordinator to recover.</p> Signup and view all the answers

    The termination property of consensus algorithms ensures that nodes will always reach a decision, even if some nodes fail.

    <p>True</p> Signup and view all the answers

    Name one of the best-known consensus algorithms.

    <p>Paxos</p> Signup and view all the answers

    Consensus algorithms must satisfy properties such as integrity, validity, and __________.

    <p>termination</p> Signup and view all the answers

    What does the validity property ensure in a consensus algorithm?

    <p>If a node decides value v, then v was proposed by some node.</p> Signup and view all the answers

    Viewstamped Replication (VSR) and Raft are examples of consensus algorithms.

    <p>True</p> Signup and view all the answers

    Match the following consensus algorithms with their characteristics:

    <p>Paxos = Assumes majority of nodes are available Raft = Focuses on understandability and practical implementations Zab = Used in ZooKeeper for leader election Viewstamped Replication = A method for fault-tolerant replication</p> Signup and view all the answers

    Total order broadcast requires messages to be delivered exactly once, in the same order, to __________.

    <p>all nodes</p> Signup and view all the answers

    Study Notes

    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.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Week 10/11 Consistency and Consensus PDF

    Description

    This quiz tests your knowledge on distributed systems, focusing on concepts like linearizability, causality, and fault tolerance. Answer questions about the properties and guarantees of different consistency models in system design.

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser