MySQL and the CAP theorem: relevance & misconceptions

Transcript

1. MySQL and the CAP theorem:
   relevance & misconceptions
   Dissecting, affirming and refuting CAP assumptions in
   real production systems.
   Shlomi Noach
   GitHub
   FOSDEM 2019
   

   View Slide

2. About me
   @github/database-infrastructure
   Author of orchestrator, gh-ost, freno, ccql
   and others.
   Blog at http://openark.org
   

   github.com/shlomi-noach

   @ShlomiNoach
   

   View Slide

3. GitHub

   Built for developers
   Largest open source hosting
   100M+ repositories, 31M+ developers, 

   2.1M+ organizations
   Supplier of octocat T-Shirts and stickers
   

   View Slide

4. Incentive
   

   View Slide

5. Incentive
   People frequently cite CAP theorem by way of:
   • Modelling a system (as AP/CP).
   • Projecting that it is impossible to achieve some desired
   setup.
   

   View Slide

6. CAP Conjecture
   Suggested by Eric Brewer, 1998-1999
   Terms:
   • [atomic] Consistency
   • [high] Availability
   • Partition tolerance
   

   View Slide

7. CAP Theorem
   Mathematically proved (hence “theorem”) by Seth Gilbert &
   Nancy Lynch, MIT.
   Using different terms than those coined by Brewer.
   In Math, a theorem only holds as long as its terms & conditions
   are met.
   

   View Slide

8. CAP Theorem
   Terms, according to Gilbert & Lynch:
   - Consistency
   - Availability
   - Partition tolerance
   

   View Slide

9. CAP Theorem: Consistency
   Once a write is successful on a node, any read on any node must
   reflect that write or any later write.
   aka Atomic Consistency, aka Linear consistency, aka
   Linearizability.
   

   View Slide

10. CAP Theorem: Availability
    Every non-crashed node must respond to requests in a finite
    amount of time.
    There is no constraint on the actual amount of time.
    Though it is not specified, it is implied that response must be
    valid, non-error.
    Contrast with Brewer’s definiton of High availability: consumer
    always has access to data via at least one replica.
    

    View Slide

11. CAP Theorem: Partition Tolerance
    The system is able to operate on network partitioning.
    Partition tolerance is considered as a given condition, since
    network partitioning can and does take place regardless of a
    system’s design.
    

    View Slide

12. CAP Theorem
    A distributed data store [web service] cannot provide more than
    two out of the three properties. Better illustrated as:
    • If the network is good, you may achieve both Availibility and
    Consistency.
    • If the network is partitioned, you must choose between
    Availability and Consistency.
    

    View Slide

13. Proof of CAP theorem
    Simplified, not by much.
    Given two nodes replicating from each other
    ! !
    n1 n2
    

    View Slide

14. Proof of CAP theorem
    We partition the network between the two nodes to an infinite
    amount of time.
    ! !
    n1 n2
    

    View Slide

15. Proof of CAP theorem
    We write data to one node. If the system is Available, the write
    compeltes in a finite amount of time.
    ! !
    n1 n2
    

    View Slide

16. Proof of CAP theorem
    We read data from the other node. If the system is Available
    that read completes in a finite mount of time.
    ! !
    n1 n2
    

    View Slide

17. Proof of CAP theorem
    During that finite time the network was partitioned, hence our
    read could not reflect changes made by the write.
    QED
    ! !
    n1 n2
    

    View Slide

18. CAP is mathematical
    As engineers we have different production objectives.
    

    View Slide

19. CAP is binary
    The theorem has nothing to say of 99.95% Availability with
    99.99% Consistency
    Tradeoffs and partial availability & consistency are discussed in
    both Brewer’s Conjecture paper and Gilbert & Lynch’s Theorem
    paper, but have no part in the proof.
    

    View Slide

20. CAP does not discuss
    Disaster Recovery
    Failover
    Latency (see PACELC)
    Durability, node recovery
    SLA, uptime, nines
    Scalability, capacity
    

    View Slide

21. CAP & MySQL in production
    

    View Slide

22. Standard MySQL replication
    Single master, multiple replicas, asynchronous replication
    ! !
    !
    !
    !
    !
    

    View Slide

23. Standard MySQL replication:

    CAP properties
    Not Consistent: asynchronous replication, replication lag.
    Not Available:
    • Replica nodes are unable to serve writes (return with error).
    • If master crashes, no server to be able to take writes.
    • CAP does not discuss failovers/SLA.
    ! !
    !
    !
    !
    !
    

    View Slide

24. Standard MySQL replication:

    consistency in practice
    Read from master?
    Scalability/capacity
    ! !
    !
    !
    !
    !
    

    View Slide

25. Standard MySQL replication:

    consistency in practice
    ProxySQL GTID casual reads:
    • Applies to same connection only.
    • If master within hostgroup, can failback to master
    • Not CAP Consistent. A proxy isn’t a known component in CAP
    Theorem.
    

    https://proxysql.com/blog/proxysql-gtid-causal-reads
    ! !
    !
    !
    !
    !
    "
    

    View Slide

26. Standard MySQL replication:

    consistency in practice
    ! !
    !
    !
    !
    !
    freno to monitor replication lag:
    • Suggests when replicas are up to date
    • HAProxy routes queries to replicas, offloading traffic from
    master
    • Not CAP Consistent. Not part of CAP.
    

    https://githubengineering.com/mitigating-replication-lag-and-reducing-read-load-with-freno/
    "
    

    View Slide

27. Semi-sync replication
    Single master, multiple replicas, semi-sync to all/subset of
    replicas.
    ! !
    !
    !
    !
    !
    

    View Slide

28. Semi-sync replication:

    CAP properties
    Still not Consistent.
    • Though we get durability.
    Still not Available.
    • semi-sync write Availability depends on configuration; on
    identities of semi-sync replicas.
    ! !
    !
    !
    !
    !
    

    View Slide

29. Hybrid cluster
    Is it CA? Is it CP?
    Depends on geographic location, time, workload.
    ! !
    !
    !
    !
    !
    

    View Slide

30. Vitess
    SQL layes: vttablet, proxy to backend
    MySQL standard replication backend shards
    Suggested configuration:
    • semi-sync
    • only send traffic to master
    " "
    "
    !
    !
    !
    !
    !
    !
    

    View Slide

31. Vitess:
    CAP properties
    Given suggested configuration:
    • Not Consistent
    • Not Available
    " "
    "
    !
    !
    !
    !
    !
    !
    

    View Slide

32. But!
    With failover, we can have the system highly available.
    With reads-on-master or another proxy solution, we can make
    the system highly consistent.
    " "
    "
    !
    !
    !
    !
    !
    !
    

    View Slide

33. CAP != E=MC²
    

    View Slide

34. InnoDB Cluster, single writer
    Single writer node, paxos consensus
    ! !
    !
    < 8.0.14
    

    View Slide

35. InnoDB Cluster, single writer:
    CAP properties
    Not Available: if network partitioned severely, quorum can be
    lost and no leader to accept writes.
    Not Consistent; changes are:
    • propagated to majority of nodes, not all.
    • made durable, not applied.
    ! !
    !
    < 8.0.14
    

    View Slide

36. InnoDB Cluster, single writer:
    availability, consistency in practice
    MySQL Router as Proxy, route traffic to leader.
    ProxySQL for per-connection consistent reads.
    ! !
    !
    "
    < 8.0.14
    

    View Slide

37. InnoDB Cluster, multi writer
    Multi writer nodes, paxos consensus
    ! !
    !
    < 8.0.14
    

    View Slide

38. InnoDB Cluster, multi writer:
    CAP properties
    Not Available, as before.
    • Debatable: are write conflicts compatible with Availability?
    Not consistent, as before.
    ! !
    !
    < 8.0.14
    

    View Slide

39. Galera:
    CAP properties
    wsrep_sync_wait=0
    • Not Available, not Consistent
    wsrep_sync_wait != 0 (e.g. =3)
    • Not Available
    • Consistent up to timeout on isolated nodes: i.e. not
    Consistent.
    ! !
    !
    

    View Slide

40. InnoDB Cluster, >= 8.0.14
    group_replication_consistency= BEFORE_AND_AFTER
    Supports consistent reads, up to timeout on isolated node.
    Not Available, not Consistent.
    STONITH for isolated nodes.
    ! !
    !
    

    View Slide

41. Is there any AP setup?
    

    View Slide

42. AP setups
    Disjoint masters
    ! !
    !
    ! !
    !
    ! !
    !
    ! ! Writable master-master, async replication
    Writable circular [n > 2] master topology, async replication
    

    View Slide

43. Takeaways
    Math and Engineering are not required to agree. Practical
    engneering makes tradeoffs.
    CAP Theorem does not represent complex production systems,
    nor does it meet production requirements.
    CAP Theorem may not even apply to your system. It might not
    be the model we should be looking at.
    Even as CAP says you have to choose A over C in case of P, it
    does not mean you cannot achieve high availability and high
    consistency.
    

    View Slide

44. PACELC
    An extention to CAP:
    - if Partitioned, trade Availability for Consistency.
    - Else, trade Latency for Consistency
    More realistic, still does not meet production needs.
    

    View Slide

45. Harvest, Yield, and Scalable Tolerant Systems, Armando Fox, Eric A. Brewer

    https://pdfs.semanticscholar.org/5015/8bc1a8a67295ab7bce0550886a9859000dc2.pdf
    Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web
    Services, Seth Gilbert, Nancy Lynch

    https://www.glassbeam.com/sites/all/themes/glassbeam/images/blog/10.1.1.67.6951.pdf
    A Critique of the CAP Theorem, Martin Kleppmann

    https://arxiv.org/pdf/1509.05393.pdf
    CAP Twelve Years Later: How the "Rules" Have Changed, Eric Brewer

    https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed
    Please stop calling databases CP or AP, Martin Kleppmann

    https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
    Further reading
    

    View Slide

46. NewSQL database systems are failing to guarantee consistency, and I blame Spanner, Daniel
    Abadi

    http://dbmsmusings.blogspot.com/2018/09/newsql-database-systems-are-failing-to.html
    Problems with CAP, and Yahoo’s little known NoSQL system, Daniel Abadi

    http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html
    PACELC theorem, Wikipedia

    https://en.wikipedia.org/wiki/PACELC_theorem
    Further reading
    

    View Slide

47. CAP theorem is mostly misunderstood, Sugu Sougoumarane

    http://ssougou.blogspot.com/2017/09/cap-theorem-is-mostly-misunderstood.html
    "A Critique of the CAP Theorem”, Julia Evans

    https://jvns.ca/blog/2016/11/19/a-critique-of-the-cap-theorem/
    CAP Theorem, FoundationDB

    https://apple.github.io/foundationdb/cap-theorem.html
    Further reading
    

    View Slide

48. Questions?
    github.com/shlomi-noach
    @ShlomiNoach
    Thank you!
    

    View Slide