Consensus Algorithms

8 posts · Aug 2020 – Jul 2022

What this trail covers

This series explores consensus algorithms, focusing on durability at scale. Part 1 introduces the core problems consensus algorithms solve: distributed durability, availability, and automation. It emphasizes the need for flexible algorithms that can adapt to complex cloud provider topologies and pricing structures, contrasting this with rigid traditional algorithms like Paxos and Raft. The approach taken is engineering-focused, using terminology and an objective-based, top-down methodology to identify and separate concerns, enabling better trade-offs and more flexible implementations. The series aims to demonstrate how these objectives can be achieved, with a specific focus on Vitess and vanilla MySQL.

All PlanetScale trails

Jul 2022Consensus algorithms at scale: Part 7 - Propagating requestsThis post details the challenges of propagating completed requests during leadership changes in distributed systems, especially in the presence of failures. It outlines requirements for discovering completed requests, introduces versioning of decisions (e.g., using timestamps or proposal numbers) to handle conflicting requests, and discusses anti-flapping rules to prevent rapid leadership changes. It also briefly mentions how MySQL binlogs (GTIDs) and Vitess's VTorc incorporate these principles.
Jun 2022Consensus algorithms at scale: Part 6 - Completing requestsThis post introduces a two-phase protocol for completing requests in consensus systems, distinguishing between tentative, durable, and complete request states. It details how leaders transmit requests and followers acknowledge them to achieve durability, and discusses the trade-offs in timing client responses. The post also points out limitations in MySQL's semi-sync protocol and potential issues with primary restarts after crashes.
Apr 2022Consensus algorithms at scale: Part 5 - Handling racesThis post introduces the concepts of 'elector' and 'candidate' in distributed systems for leadership changes. It contrasts lock-based and lock-free approaches to resolving race conditions during leadership transitions. The lock-based approach is favored for its ability to provide a stable leader, simplifying operations and enabling efficient consistent reads, though it requires careful management of lock timeouts. The lock-free approach naturally supports forward progress but complicates consistent reads by necessitating quorum reads. The post recommends lock-based systems for large-scale consensus.
Apr 2022Consensus algorithms at scale: Part 4 - Establishment and revocationThis post introduces the separation of leadership establishment and revocation as distinct concerns in consensus algorithms. It explains how traditional algorithms conflate these actions and proposes analyzing them individually. The post details how proposal numbers are used in traditional algorithms for establishment and revocation, and then explores alternatives like using replication mechanisms (e.g., MySQL semi-sync) when proposal numbers are not used. It also discusses the importance of knowing the current leader and the concept of direct leader demotion, using Vitess's PlannedReparentShard and EmergencyReparentShard as examples. The interchangeability of different revocation approaches is also discussed.
Oct 2020Pitfalls of isolation levels in distributed databasesThis post explains the trade-offs of different isolation levels (Serializable, RepeatableRead, SnapshotRead/MVCC, ReadCommitted, ReadUncommitted) in distributed databases. It uses bank and retail use cases to illustrate the practical implications of each level, particularly concerning contention, deadlocks, and scalability. The post highlights that while Serializable offers theoretical purity, it's often impractical for scalable systems. SnapshotRead (MVCC) is presented as beneficial for read-only workloads, while ReadCommitted with explicit locking is suggested as a practical approach for write-heavy transactions. It also touches upon the complexities of distributed transactions and the overhead of two-phase commit (2PC).
Advertisement
Sep 2020Consensus algorithms at scale: Part 3 - Use casesThis post details various production use cases for consensus algorithms, moving beyond strict majority quorums. It explains how flexible configurations of leader-capable nodes and data centers can be used to achieve specific durability and availability goals. The reasoning behind this flexibility is attributed to the independent operation of request and election algorithms, both guided by a shared durability constraint. It also discusses worst-case scenarios and practical balances, emphasizing the performance impact of durability settings on request execution and tail latency.
Sep 2020Consensus algorithms at scale: Part 2 - Rules of consensusThis post defines a generalized set of rules for leader-based consensus systems, abstracting away from specific implementations like Paxos and Raft. It emphasizes single-leader designs and outlines four core rules: 1. A leader's job is to fulfill requests by satisfying mandated durability requirements. 2. To elect a new leader, the previous leadership must be terminated, necessary nodes recruited, and previously completed requests propagated to satisfy the new leader's durability requirements. 3. Forward Progress: If a leader election fails, a subsequent re-attempt should have a path to success. 4. Race: If concurrent attempts are made to elect a leader, at most one leader must prevail. These rules are presented as intentionally generic to allow for creative implementations and deviate from traditional requirements like majority quorums and proposal numbers.
Aug 2020Consensus algorithms at scale: Part 1 - IntroductionThis post serves as an introduction to a series on consensus algorithms at scale. It defines the fundamental problems that consensus algorithms address: distributed durability, availability, and automation. It also critiques traditional algorithms like Paxos and Raft for their rigidity in the face of evolving cloud infrastructures and introduces an engineering-focused, objective-based approach to dissecting and building more flexible consensus systems, with a preview of how Vitess will achieve these objectives.