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

Availability, Consistency, and Horizontally Sca...

pbailis
February 19, 2014

Availability, Consistency, and Horizontally Scalable Data Management (SF Bay Area ACM)

19 February 2014 SF Bay Area ACM Meetup
http://www.meetup.com/SF-Bay-ACM/events/158437632/

Video available at: http://www.youtube.com/watch?v=JVEwJyTIjcE

pbailis

February 19, 2014
Tweet

More Decks by pbailis

Other Decks in Technology

Transcript

  1. Data Management Availability, Consistency, Peter Bailis! UC Berkeley, AMPLab! @pbailis

    with Alan Fekete, Mike Franklin, Ali Ghodsi, Ion Stoica, Joe Hellerstein and Horizontally Scalable
  2. DISTRIBUTED DATABASES THE END OF THE END OF SCALABLE AND

    CORRECT Peter Bailis! UC Berkeley, AMPLab! @pbailis with Alan Fekete, Mike Franklin, Ali Ghodsi, Ion Stoica, Joe Hellerstein
  3. Users care about the correctness of their applications “usernames should

    be unique” “each patient should have a attending doctor”
  4. Users care about the correctness of their applications “usernames should

    be unique” “each patient should have a attending doctor” “account balances should be positive”
  5. For any two operations to the same data item, if

    at least one is a write, operations might conflict T2 T1 T3 ww(c) rw(a) rw(c) rw(b) T3 T1 T2 Under the hood: ACID (conflict serializability) reasons about low-level read/write traces
  6. For any two operations to the same data item, if

    at least one is a write, operations might conflict T2 T1 T3 ww(c) rw(a) rw(c) rw(b) T3 T1 T2 Under the hood: ACID (conflict serializability) reasons about low-level read/write traces END RESULT:! A MYOPIC APPROACH TO CORRECTNESS
  7. END RESULT:! A MYOPIC APPROACH TO CORRECTNESS COST:! SERIALIZABILITY REQUIRES

    COORDINATION synchronous coordination = stalls during network partitions =
  8. END RESULT:! A MYOPIC APPROACH TO CORRECTNESS COST:! SERIALIZABILITY REQUIRES

    COORDINATION synchronous coordination = stalls during network partitions = RTT latency during operations =
  9. END RESULT:! A MYOPIC APPROACH TO CORRECTNESS COST:! SERIALIZABILITY REQUIRES

    COORDINATION synchronous coordination = stalls during network partitions = RTT latency during operations = possible stall during concurrent access
  10. 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 max 1200 txn/s THE ACID SCALABILITY WALL
  11. +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 THE ACID SCALABILITY WALL
  12. +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 THE ACID SCALABILITY WALL decentralized (optimized) 2PC SERIALIZABILITY REQUIRES COORDINATION decentralized (optimized) 2PC
  13. do not support! SSI/serializability HANA Actian Ingres YES Aerospike NO

    Persistit NO Clustrix NO Greenplum YES IBM DB2 YES IBM Informix YES MySQL YES MemSQL NO MS SQL Server YES NuoDB NO Oracle 11G NO Oracle BDB YES Oracle BDB JE YES Postgres 9.2.2 YES SAP Hana NO ScaleDB NO VoltDB YES 8/18 databases! surveyed did not 15/18 used! weaker models! by default “Highly Available Transactions: Virtues and Limitations,” VLDB 2014
  14. do not support! SSI/serializability HANA Actian Ingres YES Aerospike NO

    Persistit NO Clustrix NO Greenplum YES IBM DB2 YES IBM Informix YES MySQL YES MemSQL NO MS SQL Server YES NuoDB NO Oracle 11G NO Oracle BDB YES Oracle BDB JE YES Postgres 9.2.2 YES SAP Hana NO ScaleDB NO VoltDB YES 8/18 databases! surveyed did not 15/18 used! weaker models! by default “Highly Available Transactions: Virtues and Limitations,” VLDB 2014
  15. synchronous coordination =! stalls during network partitions = RTT latency

    during operations = possible stall during concurrent access
  16. no (or asynchronous) coordination = synchronous coordination =! stalls during

    network partitions = RTT latency during operations = possible stall during concurrent access
  17. no (or asynchronous) coordination = Gilbert and Lynch “High Availability”

    = synchronous coordination =! stalls during network partitions = RTT latency during operations = possible stall during concurrent access
  18. no (or asynchronous) coordination = Gilbert and Lynch “High Availability”

    = low latency (no RTT) = synchronous coordination =! stalls during network partitions = RTT latency during operations = possible stall during concurrent access
  19. no (or asynchronous) coordination = Gilbert and Lynch “High Availability”

    = low latency (no RTT) = indefinite horizontal scaling synchronous coordination =! stalls during network partitions = RTT latency during operations = possible stall during concurrent access
  20. no (or asynchronous) coordination = Gilbert and Lynch “High Availability”

    = low latency (no RTT) = indefinite horizontal scaling (even for a single record; true scalability) synchronous coordination =! stalls during network partitions = RTT latency during operations = possible stall during concurrent access
  21. no (or asynchronous) coordination = Gilbert and Lynch “High Availability”

    = low latency (no RTT) = indefinite horizontal scaling (even for a single record; true scalability) synchronous coordination =! stalls during network partitions = RTT latency during operations = possible stall during concurrent access
  22. no (or asynchronous) coordination = Gilbert and Lynch “High Availability”

    = low latency (no RTT) = indefinite horizontal scaling (even for a single record; true scalability) benefits also apply to concurrent access in single-node systems synchronous coordination =! stalls during network partitions = RTT latency during operations = possible stall during concurrent access
  23. no (or asynchronous) coordination = Gilbert and Lynch “High Availability”

    = low latency (no RTT) = indefinite horizontal scaling (even for a single record; true scalability) benefits also apply to concurrent access in single-node systems synchronous coordination =! stalls during network partitions = RTT latency during operations = possible stall during concurrent access BUT OFTEN GIVE UP CORRECTNESS!!
  24. CORRECTNESS vs. SCALABILITY SERIALIZABILITY Our solution: coordination avoidance Our insight:

    serializability is sufficient for correctness! ! ! ! ! but is not necessary! ! ! !
  25. CORRECTNESS vs. SCALABILITY SERIALIZABILITY Our solution: coordination avoidance Our insight:

    serializability is sufficient for correctness! ! ! ! ! but is not necessary! ! ! ! Only coordinate when necessary
  26. CORRECTNESS vs. SCALABILITY SERIALIZABILITY Our solution: coordination avoidance CORRECTNESS and

    SCALABILITY Our insight: serializability is sufficient for correctness! ! ! ! ! but is not necessary! ! ! ! Only coordinate when necessary
  27. CORRECTNESS vs. SCALABILITY SERIALIZABILITY Our solution: coordination avoidance CORRECTNESS and

    SCALABILITY Our insight: serializability is sufficient for correctness! ! ! ! ! but is not necessary! ! ! ! Only coordinate when necessary
  28. CORRECTNESS vs. SCALABILITY SERIALIZABILITY Our solution: coordination avoidance CORRECTNESS and

    SCALABILITY Our insight: serializability is sufficient for correctness! ! ! ! ! but is not necessary! ! ! ! Only coordinate when necessary Ask applications for invariants
  29. CORRECTNESS vs. SCALABILITY SERIALIZABILITY Our solution: coordination avoidance CORRECTNESS and

    SCALABILITY Our insight: serializability is sufficient for correctness! ! ! ! ! but is not necessary! ! ! ! Only coordinate when necessary Ask applications for invariants Invariants determine:! ! When is coordination needed?! ! How much coordination is required?! !
  30. Invariant: each employee is in a department Operations: add employees

    l_emp = employees.find(id=“louise”) ! Anomaly (to avoid):
  31. Invariant: each employee is in a department Operations: add employees

    l_emp = employees.find(id=“louise”) ! Anomaly (to avoid):
  32. Invariant: each employee is in a department Operations: add employees

    l_emp = employees.find(id=“louise”) ! l_dept = dept.find(l_emp.dept) ! Anomaly (to avoid):
  33. Invariant: each employee is in a department Operations: add employees

    l_emp = employees.find(id=“louise”) ! l_dept = dept.find(l_emp.dept) ! ENORECORD Anomaly (to avoid):
  34. employees = {} dept = {{“ops”:1}, {“dev”:2}} Invariant: each employee

    is in a department Operations: add employees d1 = dept.find(“ops”) employees.add({“Harry”:d1})
  35. employees = {} dept = {{“ops”:1}, {“dev”:2}} Invariant: each employee

    is in a department Operations: add employees d1 = dept.find(“ops”) employees.add({“Harry”:d1})
  36. employees = {} dept = {{“ops”:1}, {“dev”:2}} Invariant: each employee

    is in a department Operations: add employees d2 = dept.find(“dev”) employees.add({“Sue”:d2}) d1 = dept.find(“ops”) employees.add({“Harry”:d1})
  37. employees = {} dept = {{“ops”:1}, {“dev”:2}} Invariant: each employee

    is in a department Operations: add employees d2 = dept.find(“dev”) employees.add({“Sue”:d2}) d1 = dept.find(“ops”) employees.add({“Harry”:d1})
  38. employees = {{“Harry”:1}, {“Sue”:2}} dept = {{“ops”:1}, {“dev”:2}} employees =

    {} dept = {{“ops”:1}, {“dev”:2}} Invariant: each employee is in a department Operations: add employees d2 = dept.find(“dev”) employees.add({“Sue”:d2}) d1 = dept.find(“ops”) employees.add({“Harry”:d1})
  39. employees = {{“Harry”:1}, {“Sue”:2}} dept = {{“ops”:1}, {“dev”:2}} employees =

    {} dept = {{“ops”:1}, {“dev”:2}} Invariant: each employee is in a department Operations: add employees d2 = dept.find(“dev”) employees.add({“Sue”:d2}) d1 = dept.find(“ops”) employees.add({“Harry”:d1}) Invariant holds!
  40. Anomaly (to avoid): Invariant: only one ops on staff at

    a time Operations: change staffing
  41. on_duty = employees.find(staffed=”T”) ! assert(len(on_duty) == 1) ! Anomaly (to

    avoid): Invariant: only one ops on staff at a time Operations: change staffing
  42. on_duty = employees.find(staffed=”T”) ! assert(len(on_duty) == 1) ! ASSERTION FAILS

    Anomaly (to avoid): Invariant: only one ops on staff at a time Operations: change staffing
  43. staff = {“Laura”:T, “Harry”:F, “Gary”:F} staff.set({“Laura”:F}, “Gary”:T}) staff.set({“Laura”:F}, {“Harry”:T}) Invariant

    violated! staff = {“Laura”:F, “Harry”:T, “Gary”:T} Invariant: only one ops on staff at a time Operations: change staffing
  44. I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency,

    availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  45. To maintain consistency... I-confluence is necessary and sufficient for simultaneously

    maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  46. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  47. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  48. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  49. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  50. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  51. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  52. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  53. Sufficient? Necessary? App-Level? Conflict Serializability Yes No No Invariant Confluence

    Yes Yes Yes State-based Commutativity Yes* No Depends To maintain consistency... I-confluence is necessary and sufficient for simultaneously maintaining application-level consistency, availability, convergence, and coordination-freedom Invariant confluence: formal characterization of safe, coordination-free execution
  54. Formal framework for reasoning about application coordination requirements Coordination depends

    on combination of:! - expressiveness of operations! - strength of invariants
  55. Formal framework for reasoning about application coordination requirements Coordination depends

    on combination of:! - expressiveness of operations! - strength of invariants STRENGTH OF INVARIANTS EXPRESSIVENESS OF OPERATIONS *Okay, so this is simplified, and there isn’t really a linear order on either axis (rather, it’s more about equivalence classes), but humor me here...
  56. Formal framework for reasoning about application coordination requirements Coordination depends

    on combination of:! - expressiveness of operations! - strength of invariants STRENGTH OF INVARIANTS EXPRESSIVENESS OF OPERATIONS *Okay, so this is simplified, and there isn’t really a linear order on either axis (rather, it’s more about equivalence classes), but humor me here... COORDINATION! REQUIRED! COORDINATION-FREE
  57. Formal framework for reasoning about application coordination requirements Coordination depends

    on combination of:! - expressiveness of operations! - strength of invariants STRENGTH OF INVARIANTS EXPRESSIVENESS OF OPERATIONS *Okay, so this is simplified, and there isn’t really a linear order on either axis (rather, it’s more about equivalence classes), but humor me here... COORDINATION! REQUIRED! COORDINATION-FREE
  58. Formal framework for reasoning about application coordination requirements Coordination depends

    on combination of:! - expressiveness of operations! - strength of invariants STRENGTH OF INVARIANTS EXPRESSIVENESS OF OPERATIONS *Okay, so this is simplified, and there isn’t really a linear order on either axis (rather, it’s more about equivalence classes), but humor me here... COORDINATION! REQUIRED! COORDINATION-FREE
  59. Formal framework for reasoning about application coordination requirements Coordination depends

    on combination of:! - expressiveness of operations! - strength of invariants STRENGTH OF INVARIANTS EXPRESSIVENESS OF OPERATIONS *Okay, so this is simplified, and there isn’t really a linear order on either axis (rather, it’s more about equivalence classes), but humor me here... COORDINATION! REQUIRED! COORDINATION-FREE
  60. Can apply the I-confluence test to! standard SQL for program

    analysis 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 ???
  61. Can apply the I-confluence test to! standard SQL for program

    analysis 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 ???
  62. Constraint: record IDs are unique DECLARE TABLE users (! ID

    int UNIQUE,! FirstName string,! LastName string )
  63. Constraint: record IDs are unique DECLARE TABLE users (! ID

    int UNIQUE,! FirstName string,! LastName string ) Anomaly! (to avoid):
  64. Constraint: record IDs are unique DECLARE TABLE users (! ID

    int UNIQUE,! FirstName string,! LastName string ) Anomaly! (to avoid):
  65. Constraint: record IDs are unique DECLARE TABLE users (! ID

    int UNIQUE,! FirstName string,! LastName string ) Anomaly! (to avoid):
  66. Constraint: record IDs are unique DECLARE TABLE users (! ID

    int UNIQUE,! FirstName string,! LastName string )
  67. Operation: insert record with specific ID INSERT INTO users (ID,

    firstname, lastname)! VALUES (1, “Leslie”, “Lamport”) Constraint: record IDs are unique DECLARE TABLE users (! ID int UNIQUE,! FirstName string,! LastName string )
  68. NOT C-FREE Operation: insert record with specific ID INSERT INTO

    users (ID, firstname, lastname)! VALUES (1, “Leslie”, “Lamport”) Constraint: record IDs are unique DECLARE TABLE users (! ID int UNIQUE,! FirstName string,! LastName string )
  69. Operation: insert record INSERT INTO users (firstname, lastname)! VALUES (“Leslie”,

    “Lamport”) NOT C-FREE Operation: insert record with specific ID INSERT INTO users (ID, firstname, lastname)! VALUES (1, “Leslie”, “Lamport”) Constraint: record IDs are unique DECLARE TABLE users (! ID int UNIQUE,! FirstName string,! LastName string )
  70. let the DB decide the ID; use node ID or

    UUID C-FREE! Operation: insert record INSERT INTO users (firstname, lastname)! VALUES (“Leslie”, “Lamport”) NOT C-FREE Operation: insert record with specific ID INSERT INTO users (ID, firstname, lastname)! VALUES (1, “Leslie”, “Lamport”) Constraint: record IDs are unique DECLARE TABLE users (! ID int UNIQUE,! FirstName string,! LastName string )
  71. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) )
  72. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string )
  73. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string )
  74. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);!
  75. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);!
  76. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Anomaly (to avoid):
  77. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Anomaly (to avoid): “lamport” has no department! read lamport record; lookup lamport.D_ID returns NULL
  78. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Anomaly (to avoid): “lamport” has no department! read lamport record; lookup lamport.D_ID returns NULL I-confluence insight:! cannot be violated by inserts!
  79. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Anomaly (to avoid): “lamport” has no department! read lamport record; lookup lamport.D_ID returns NULL I-confluence insight:! cannot be violated by inserts! …but be careful about implementation! many ways to use coordination to enforce coordination-free semantics
  80. Foreign key constraints DECLARE TABLE users (! U_ID int UNIQUE,!

    D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);!
  81. users shard department shard Foreign key constraints DECLARE TABLE users

    (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);!
  82. users shard department shard Foreign key constraints DECLARE TABLE users

    (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);!
  83. users shard department shard Foreign key constraints DECLARE TABLE users

    (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers
  84. users shard department shard Foreign key constraints DECLARE TABLE users

    (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers
  85. users shard department shard Foreign key constraints DECLARE TABLE users

    (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers
  86. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers
  87. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers
  88. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (???, 342, “lamport”)
  89. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (402, 342, “lamport”)
  90. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (402, 342, “lamport”)
  91. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (402, 342, “lamport”)
  92. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (402, 342, “lamport”)
  93. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (402, 342, “lamport”)
  94. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (402, 342, “lamport”) 2 RTT writes (prepare and make visible)! Between 1-2 RTTs for reads! Basic idea: store metadata to record sibling writes
  95. users shard department shard (342, “awesome division”) Foreign key constraints

    DECLARE TABLE users (! U_ID int UNIQUE,! D_ID int! UserName string ! FOREIGN KEY (D_ID)! REFERENCES department(D_ID) ) DECLARE TABLE department (! D_ID int UNIQUE,! DeptName string ) NEW_D_ID = INSERT INTO department VALUES (“awesome division”);! INSERT INTO users (D_ID, UserName) VALUES (NEW_D_ID, “lamport”);! Visible to all readers Visible to all readers Not yet visible to all readers Not yet visible to all readers (402, 342, “lamport”) 2 RTT writes (prepare and make visible)! Between 1-2 RTTs for reads! Basic idea: store metadata to record sibling writes Read Atomic Multi-Partition ! Transactions, SIGMOD 2014
  96. 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 ??? Can apply the I-confluence test to! standard SQL for program analysis
  97. 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 Can apply the I-confluence test to! standard SQL for program analysis
  98. Eventual consistency 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 Can apply the I-confluence test to! standard SQL for program analysis
  99. Eventual consistency 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 Abstract data types Can apply the I-confluence test to! standard SQL for program analysis
  100. Eventual consistency 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 RAMP Transaction Abstract data types Can apply the I-confluence test to! standard SQL for program analysis
  101. Remainder: Cannot avoid coordination Eventual consistency 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 RAMP Transaction Abstract data types Can apply the I-confluence test to! standard SQL for program analysis
  102. CREATE TABLE Orders! (! O_ID int AUTO_INCREMENT,! C_ID int,! O_QTY

    int,! DATE datetime NOT NULL! ! PRIMARY KEY (OrderID),! FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID),! CONSTRAINT [O_QTY > 0]! ) CREATE PROCEDURE CreateOrder(@C_ID int, @O_QTY int)! AS! INSERT INTO Orders (C_ID, O_QTY, DATE) VALUES! (C_ID, O_QTY, NOW());! GO Standard SQL with extensions and ! analysis!
  103. > WARNING: Orders.O_ID requires coordination!! INSERT found in CreateOrder! >

    WARNING: CreateOrder requires remote check for @C_ID! CREATE TABLE Orders! (! O_ID int AUTO_INCREMENT,! C_ID int,! O_QTY int,! DATE datetime NOT NULL! ! PRIMARY KEY (OrderID),! FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID),! CONSTRAINT [O_QTY > 0]! ) CREATE PROCEDURE CreateOrder(@C_ID int, @O_QTY int)! AS! INSERT INTO Orders (C_ID, O_QTY, DATE) VALUES! (C_ID, O_QTY, NOW());! GO Standard SQL with extensions and ! analysis!
  104. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] )
  105. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) I-confluence! analysis
  106. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) I-confluence! analysis COORDINATION COST
  107. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) I-confluence! analysis COORDINATION COST
  108. I-confluence in real programs? Benchmark I-confluent invariants TPC-C! 10 of

    12 TPC-E 4 of 4 AuctionMark all but 1 SEATS all but 1 JPAB all TATP all
  109. I-confluence in real programs? Benchmark I-confluent invariants TPC-C! 10 of

    12 TPC-E 4 of 4 AuctionMark all but 1 SEATS all but 1 JPAB all TATP all TRADITIONAL! OLTP! APPLICATIONS! ARE ACHIEVABLE! WITHOUT! (MUCH)! COORDINATION
  110. I-confluence in real programs? Benchmark I-confluent invariants TPC-C! 10 of

    12 TPC-E 4 of 4 AuctionMark all but 1 SEATS all but 1 JPAB all TATP all Still requires coordination-avoiding query plans!! • Appropriate merge (e.g., counter datatype) • Atomic multi-put (e.g., RAMP) • Nested atomic transactions (e.g., New-Order ID assignment) TRADITIONAL! OLTP! APPLICATIONS! ARE ACHIEVABLE! WITHOUT! (MUCH)! COORDINATION
  111. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) I-confluence! analysis COORDINATION COST
  112. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) I-confluence! analysis COORDINATION COST
  113. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner I-confluence! analysis COORDINATION COST
  114. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Application queries I-confluence! analysis COORDINATION COST
  115. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Application queries Query! executor I-confluence! analysis COORDINATION COST
  116. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Storage! manager Application queries Query! executor I-confluence! analysis COORDINATION COST
  117. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Storage! manager Lock! manager Application queries Query! executor I-confluence! analysis COORDINATION COST
  118. DDL with invariants DDL with invariants CREATE TABLE Orders (

    O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Storage! manager Lock! manager Application queries Query! executor I-confluence! analysis STATISTICS COORDINATION COST
  119. COORDINATION COST DDL with invariants DDL with invariants CREATE TABLE

    Orders ( O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Storage! manager Application queries Query! executor I-confluence! analysis STATISTICS Lock! manager
  120. COORDINATION COST DDL with invariants DDL with invariants CREATE TABLE

    Orders ( O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Storage! manager Application queries Query! executor I-confluence! analysis STATISTICS Lock! manager
  121. COORDINATION COST DDL with invariants DDL with invariants CREATE TABLE

    Orders ( O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) Query! planner Storage! manager Application queries Query! executor I-confluence! analysis STATISTICS Lock! manager ONGOING! WORK
  122. COORDINATION COST DDL with invariants DDL with invariants CREATE TABLE

    Orders ( O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) STATIC! PLAN! (manual) Storage! manager Application queries Query! executor I-confluence! analysis STATISTICS Lock! manager
  123. COORDINATION COST DDL with invariants DDL with invariants CREATE TABLE

    Orders ( O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) STATIC! PLAN! (manual) Storage! manager Application queries Query! executor I-confluence! analysis Lock! manager
  124. COORDINATION COST DDL with invariants DDL with invariants CREATE TABLE

    Orders ( O_ID int AUTO_INCREMENT, C_ID int, O_QTY int, DATE datetime NOT NULL PRIMARY KEY (OrderID), FOREIGN KEY (CustomerID) REFERENCES Customers(C_ID), CONSTRAINT [O_QTY > 0] ) STATIC! PLAN! (manual) Storage! manager Application queries Query! executor I-confluence! analysis Lock! manager
  125. TPC-C New-Order Pre-materialized aggregates (e.g., W_YTD=SUM(orders for warehouse)) RAMP transaction

    on counter CRDT warehouse district orders neworders +100 insert! 100
  126. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) RAMP transaction on counter CRDT warehouse district orders neworders
  127. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) RAMP transaction on counter CRDT insert! O_ID warehouse district orders neworders
  128. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) RAMP transaction on counter CRDT insert! O_ID warehouse district orders neworders insert! O_ID
  129. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) RAMP transaction on counter CRDT RAMP transaction across tables insert! O_ID warehouse district orders neworders insert! O_ID
  130. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables insert! O_ID warehouse district orders neworders insert! O_ID
  131. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables insert! O_ID warehouse district orders neworders insert! O_ID assign! new! O_ID
  132. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables insert! O_ID warehouse district orders neworders insert! O_ID assign! new! O_ID
  133. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables insert! O_ID warehouse district orders neworders insert! O_ID deferred atomic incrementAndGet() on commit! assign! new! O_ID
  134. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables insert! O_ID warehouse district orders neworders insert! O_ID deferred atomic incrementAndGet() on commit! assign! new! O_ID tmp ID
  135. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables rewrite FK references to point to temp unique ID! create local index from temp unique ID to sequence ID insert! O_ID warehouse district orders neworders insert! O_ID deferred atomic incrementAndGet() on commit! assign! new! O_ID tmp ID
  136. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables rewrite FK references to point to temp unique ID! create local index from temp unique ID to sequence ID insert! O_ID warehouse district orders neworders insert! O_ID deferred atomic incrementAndGet() on commit! assign! new! O_ID tmp ID
  137. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables rewrite FK references to point to temp unique ID! create local index from temp unique ID to sequence ID insert! O_ID warehouse district orders neworders insert! O_ID deferred atomic incrementAndGet() on commit! assign! new! O_ID tmp ID
  138. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables rewrite FK references to point to temp unique ID! create local index from temp unique ID to sequence ID insert! O_ID warehouse district orders neworders insert! O_ID deferred atomic incrementAndGet() on commit! assign! new! O_ID tmp ID
  139. TPC-C New-Order Foreign key insert (e.g., NewOrder, Orders tables) Pre-materialized

    aggregates (e.g., W_YTD=SUM(orders for warehouse)) Sequence number ID assignment (i.e., D_NEXT_O_ID) RAMP transaction on counter CRDT RAMP transaction across tables rewrite FK references to point to temp unique ID! create local index from temp unique ID to sequence ID insert! O_ID warehouse district orders neworders insert! O_ID deferred atomic incrementAndGet() on commit! assign! new! O_ID tmp ID O NLY SYNCH CO O RDINATIO N! REQ UIRED
  140. Linear Scaling via Coordination Avoidance Coordination need not be a

    bottleneck (if implemented in a coordination-free manner): UC Berkeley database prototype, 100 EC2 CC2.8xlarge instances (thank you AWS folks! currently poor single-node performance, but unimportant if you can scale out [for the time being]), linearizable masters, only blocking coordination: incrementAndGet for “district next order ID” key, CPU-bound on in-memory data; ~2500 lines Java; 120 clients/warehouse, 5 warehouses/machine, no THINK TIME (i.e., more contention than stock configuration)
  141. Linear Scaling via Coordination Avoidance Coordination need not be a

    bottleneck (if implemented in a coordination-free manner): UC Berkeley database prototype, 100 EC2 CC2.8xlarge instances (thank you AWS folks! currently poor single-node performance, but unimportant if you can scale out [for the time being]), linearizable masters, only blocking coordination: incrementAndGet for “district next order ID” key, CPU-bound on in-memory data; ~2500 lines Java; 120 clients/warehouse, 5 warehouses/machine, no THINK TIME (i.e., more contention than stock configuration)
  142. Traditional database systems suffer from! coordination bottlenecks By understanding application

    requirements,! we can avoid coordination unless necessary We can build systems that actually scale! while providing correct behavior
  143. Traditional database systems suffer from! coordination bottlenecks By understanding application

    requirements,! we can avoid coordination unless necessary We can build systems that actually scale! while providing correct behavior Thanks!! ! [email protected]! @pbailis! http://bailis.org/ http://amplab.cs.berkeley.edu/!
  144. Traditional database systems suffer from! coordination bottlenecks By understanding application

    requirements,! we can avoid coordination unless necessary We can build systems that actually scale! while providing correct behavior Thanks!! ! [email protected]! @pbailis! http://bailis.org/ http://amplab.cs.berkeley.edu/! based on “Coordination-Avoiding Database Systems,”! Bailis, Fekete, Franklin, Ghodsi, Hellerstein, Stoica! arXiv:1402.2237 http://arxiv.org/abs/1402.2237