Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Bridging the Gap: Opportunities in Coordination...

pbailis
April 13, 2014

Bridging the Gap: Opportunities in Coordination-Avoiding Database Systems

Talk from Principles and Practice of Eventual Consistency workshop (co-located with EuroSys 2014):
http://eventos.fct.unl.pt/papec/pages/program

pbailis

April 13, 2014
Tweet

More Decks by pbailis

Other Decks in Technology

Transcript

  1. BRIDGING THE GAP: OPPORTUNITIES IN COORDINATION-AVOIDING DATABASE SYSTEMS Peter Bailis,

    Alan Fekete, Mike Franklin, Ali Ghodsi, Joe Hellerstein, Ion Stoica UC Berkeley and University of Sydney
  2. “Designing applications to cope with concurrency anomalies in their data

    is very error-prone, time-consuming, and ultimately not worth the performance gains.” VLDB 2013
  3. “Once you give up serializability, you fall off a cliff.”

    -A Certain Five-Star Wizard of the DB Community Personal communication, 2013
  4. These accounts (and many others) suggest: a.) the benefits of

    EC are misunderstood b.) we underestimate programmability costs c.) some combination of the two OR OR
  5. This talk: • A proposal: coordination-free execution is unifying principle

    behind availability, low latency, scalability • Coordination-avoidance is key: offer tight bound, successful application to high value applications These accounts (and many others) suggest: a.) the benefits of EC are misunderstood b.) we underestimate programmability costs c.) some combination of the two OR OR
  6. Availability “The justification for giving up C is so that

    the A and P can be preserved.” Stonebraker, CACM 2010 Danger: majority availability is often okay for practitioners (cf. F1, Spanner, many NewSQL) Danger: as stated, only applies to failure scenarios
  7. Low Latency Any live replica can respond! Abadi, IEEE Computer

    2013 LAN VS WAN up to 720x faster on EC2 (on average) Bailis et al. VLDB 2014
  8. Efficiency/Scalability Can process requests without coordination, even for individual records

    “CP” distributed throughput: < 1/RTT 1 2 3 4 5 6 7 Number of Items per Transaction Throughput (txns/s) No Conflict Conflict “CP” “AP” “Coordination-Avoiding Database Systems” arXiv:1402.2237
  9. +OR +CA +IR +SP +TO +SI +SY Participating Datacenters (+VA)

    2 4 6 8 10 12 Maximum Throughput (txn/s) 2 4 6 8 10 12 14 16 18 20 Number of Servers in 2PC 0 200 400 600 800 1000 1200 Maximum Throughput (txns/s) LOCAL! DATACENTER MULTI-! DATACENTER! max 1200 txn/s max 12 txn/s decentralized (optimized) 2PC decentralized (optimized) 2PC Implementation-Independent “Coordination-Avoiding Database Systems” arXiv:1402.2237
  10. One core mechanism: COORDINATION-FREE EXECUTION Concurrent operations execute without communicating

    Like executing operations on separate, partitioned replicas “Coordination-Avoiding Databases” arXiv:1402.2237
  11. One core mechanism: COORDINATION-FREE EXECUTION Coordination avoidance becomes goal of

    EC systems and programming Perhaps “just rhetoric” a.) EC benefits are many, but complicated b.) one mechanism captures all benefits c.) it’s implementation-agnostic , but:
  12. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  13. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  14. When is coordination strictly required for correctness? (In both formal

    and practical senses.) Depends on application’s invariants and operations
  15. Convergence (e.g., CRDTs) and confluence (e.g., CALM) provide useful liveness

    guarantees SAFETY correctness always guaranteed LIVENESS database states agree (converge) When is coordination strictly required for correctness?
  16. Convergence (e.g., CRDTs) and confluence (e.g., CALM) provide useful liveness

    guarantees SAFETY correctness always guaranteed LIVENESS database states agree (converge) Invariant Confluence ensures application-level safety properties also hold (in addition to liveness) When is coordination strictly required for correctness? “Coordination-Avoiding Database Systems” arXiv:1402.2237
  17. Invariant Confluence is necessary and sufficient for ensuring safety, convergence,

    availability, and coordination-free execution. Invariant Confluence holds?! A safe, c-free execution strategy exists. Invariant Confluence fails?! No safe, c-free mechanism exists. When is coordination strictly required for correctness? “Coordination-Avoiding Database Systems” arXiv:1402.2237
  18. Invariant Operation C.F. Equality, Inequality Any ??? Generate unique ID

    Any ??? Specify unique ID Insert ??? >! Increment ??? >! Decrement ??? < Decrement ??? < Increment ??? Foreign Key Insert ??? Foreign Key Delete ??? Secondary Indexing Any ??? Materialized Views Any ??? AUTO_INCREMENT Insert ??? Typical DB! operations and ! invariants! (SQL) “Coordination-Avoiding Database Systems” arXiv:1402.2237
  19. Test fails? Cannot avoid coordination Invariant Operation C.F. Equality, Inequality

    Any Y Generate unique ID Any Y Specify unique ID Insert N >! Increment Y >! Decrement N < Decrement Y < Increment N Foreign Key Insert Y Foreign Key Delete Y* Secondary Indexing Any Y Materialized Views Any Y! AUTO_INCREMENT Insert N MANY TRADITIONAL DB APPS OK Typical DB! operations and ! invariants! (SQL) “Coordination-Avoiding Database Systems” arXiv:1402.2237
  20. Applicable to real applications scale to! over 25x! prior best

    0 50 100 150 200 2M 4M 6M 8M 10M 12M 14M Total Throughput (txn/s) 0 50 100 150 200 Number of Servers 0 20K 40K 60K 80K Throughput (txn/s/server) 6-11x faster than serializability 8 16 32 48 64 Number of Warehouses 40K 100K 600K Throughput (txns/s) Coordination-Avoiding Serializable (2PL) 10 of 12 invariants in TPC-C benchmark are I-confluent “Coordination-Avoiding Database Systems” arXiv:1402.2237
  21. Opportunity • I-confluence offers tight bound on when coordination is

    actually required • SQL applications often use invariants already • Many invariants and operations are I-confluent; amenable to coordination-free execution
  22. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  23. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  24. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  25. do not support! SSI/serializability HANA Actian Ingres YES Aerospike NO!

    N Persistit NO! N Clustrix NO! N Greenplum YES IBM DB2 YES IBM Informix YES MySQL YES MemSQL NO! N MS SQL Server YES NuoDB NO! N Oracle 11G NO! N Oracle BDB YES Oracle BDB JE YES Postgres 9.2.2 YES SAP Hana NO! N ScaleDB NO! N VoltDB YES 8/18 databases! surveyed did not 15/18 used! weaker models! by default “Highly Available Transactions: Virtues and Limitations” VLDB 2014
  26. So which require coordination? Implementations typically use coordination (e.g. locking)

    But is this fundamental to the isolation levels? NO! Unavailable Sticky Available Highly Available Legend prevents lost update†! prevents write skew‡! requires recency guarantees⊕ Sticky Available Unavailable Highly Available “Highly Available Transactions: Virtues and Limitations” VLDB 2014
  27. So which require coordination? Implementations typically use coordination (e.g. locking)

    But is this fundamental to the isolation levels? NO! Unavailable Sticky Available Highly Available Legend prevents lost update†! prevents write skew‡! requires recency guarantees⊕ Sticky Available Unavailable Highly Available “Highly Available Transactions: Virtues and Limitations” VLDB 2014 Many popular isolation levels are achievable without coordination
  28. • Weak isolation models are prevalent • Many weak isolation

    models are achievable without coordination • Applications running on weak isolation are excellent candidates for porting to an EC or coordination-free environment Opportunity
  29. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  30. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  31. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  32. ACID Internals Highly concurrent algorithms allow read/write races but hide

    effects from end users Key: well-defined external specification allows flexibility in execution strategy From Srivinvasan and Carey, SIGMOD 1991 End-user semantics unaffected!
  33. Example: RAMP Transactions Atomic visibility is sufficient for correctly maintaining

    foreign key constraints, secondary indexes, materialized views Traditional strategy: use mutual exclusion Coordination-free solution: multi-versioning and metadata C1 PREPARE PREPARE lastCommit[x]=⊥ versions={x1 } x1 , md={y} y1 , md={x} lastCommit[y]=⊥ versions={y1 } COMMIT tsc =1 COMMIT ts c =1 GET i=x, tsreq =⊥ GET lastCommit[x]=1 versions={x1 } GET x1 , md={y} y⊥, md={} y1 , md={x} lastCommit[y]=1 versions={y1 } vlatest ←{x:1, y:1} prepared RESPONSE prepared i=y, tsreq =⊥ i=y, tsreq =1 lastCommit[x]=⊥ versions={} lastCommit[y]=⊥ versions={} BEGIN T1 committed committed BEGIN T2 COMMIT T1 COMMIT T2 resp={x 1 ,y 1 } RESPONSE RESPONSE RESPONSE RESPONSE RESPONSE RESPONSE C2 Px Py [w(x1 ), w(y1 )] [r(x), r(y)] SIGMOD 2014
  34. • Leverage coordination-avoiding techniques in internal database design • End-user

    applications are faster but unaffected • Traditional mechanisms (often) not designed for distribution or partitioned environment Opportunity
  35. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  36. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants
  37. When can we avoid coordination? 3.) ACID databases aren’t built

    using ACID transactions This talk: Three opportunities 1.) I-Confluence offers tight bound/answer 2.) ACID-backed apps aren’t always ACID-backed Directly analyze application invariants Leverage existing use of weak isolation Exploit existing interfaces and system invariants EXISTING PRACTICES RIPE FOR IMPROVEMENT NEW PRINCIPLE FOR OPTIMIZATION
  38. Takeaways • Sole focus on availability, latency, or scale-out is

    myopic: coordination-free execution unifies them • Invariant confluence as tight bound is a powerful measure of optimization potential • Our take: scope for EC can be greatly expanded with study of existing application invariants, use of weak isolation, and well-defined system interfaces