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

The Potential Dangers of Causal Consistency and...

pbailis
October 12, 2012

The Potential Dangers of Causal Consistency and an Explicit Solution

pbailis

October 12, 2012
Tweet

More Decks by pbailis

Other Decks in Technology

Transcript

  1. the potential dangers of causal consistency and an explicit solution

    Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica SOCC 2012
  2. “Sally’s in a coma!” “Sally’s in a coma!” A Story

    “Great news!” “Sally’s okay!”
  3. “Sally’s in a coma!” “Sally’s in a coma!” A Story

    “Great news!” “Sally’s okay!”
  4. 1978 “Time, Clocks, and the Ordering of Events in a

    Distributed System” by Leslie Lamport
  5. 1978 “Time, Clocks, and the Ordering of Events in a

    Distributed System” by Leslie Lamport 1994 “Causal Memory” by Ahamad et al.
  6. 1978 “Time, Clocks, and the Ordering of Events in a

    Distributed System” by Leslie Lamport 1994 “Causal Memory” by Ahamad et al. 2011-12
  7. 2011-12 IEEE CAP SOSP: COPS Texas: CAC There are many

    hard, trade-offs, but causal consistency can work well and it’s the best you can do*!
  8. If you wish to make an apple pie from scratch,

    you must first invent the universe. -Carl Sagan
  9. “Great news!” “Sally’s okay!” “Great picture!” “Rad party!” “Lol!” “Can’t

    wait for SOCC!” “Want to go skiing?” “I hope my paper gets in.” “You who?” “I love Tahoe!” “Coming tonight?
  10. “Great news!” “Sally’s okay!” “Great picture!” “Rad party!” “Lol!” “Can’t

    wait for SOCC!” “Want to go skiing?” “Snow rocks!” “I hear the PC is great!” “You.” “Hello, “I hope my paper gets in.” “You who?” “I love Tahoe!” “Coming tonight?
  11. “Great news!” “Sally’s okay!” “Great picture!” “Rad party!” “Lol!” “Can’t

    wait for SOCC!” “Want to go skiing?” “Snow rocks!” “I hear the PC is great!” “You.” “Hello, “Who’s there?” “Are you submitting?” “Have you met Larry?” “Great food here” “I hope my paper gets in.” “You who?” “I love Tahoe!” “Coming tonight?
  12. “Great news!” “Sally’s okay!” “Great picture!” “Rad party!” “Lol!” “Can’t

    wait for SOCC!” “Want to go skiing?” “Snow rocks!” “I hear the PC is great!” “You.” “Hello, “Who’s there?” “Are you submitting?” “Have you met Larry?” “Great food here” “Knock, knock.” “I hope my paper gets in.” “You who?” “I love Tahoe!” “Coming tonight?
  13. “Great news!” “Sally’s okay!” “Great picture!” “Rad party!” “Lol!” “Can’t

    wait for SOCC!” “Want to go skiing?” “Snow rocks!” “I hear the PC is great!” “You.” “Hello, “Who’s there?” “Are you submitting?” “Have you met Larry?” “Great food here” “Knock, knock.” “I hope my paper gets in.” “You who?” “I love Tahoe!” “Coming tonight?
  14. DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! Adding DCs

    doesn’t help slowest site Sustained throughput limited to slowest DC
  15. DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! During partitions/failures,

    sustainable throughput is zero writes/s zero Sustained throughput limited to slowest DC
  16. DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! During partitions/failures,

    sustainable throughput is zero writes/s zero Metadata garbage collection stalls stalls
  17. DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! During partitions/failures,

    sustainable throughput is zero writes/s zero Metadata garbage collection stalls stalls
  18. DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! DANGER! During partitions/failures,

    sustainable throughput is zero writes/s zero Metadata garbage collection stalls stalls
  19. r e c a p potential danger Write throughput limited

    to slowest DC Violation 㱺 arbitrarily high visibility latency Adding DCs does not increase throughput
  20. Explicit Causality app-defined “happens-before” transitivity enforced subset of potential causality

    not a new idea (e.g., Cheriton and Skeen SOSP 1993, Ladin et al. PODC 1990) but...
  21. Explicit Matters Twitter 28% of Tweets in conversations 69% of

    convos are depth two average depth is 10.7 [Ye and Wu SocInfo 2010, Ritter et al. HLT 2010]
  22. Explicit Matters Twitter 28% of Tweets in conversations 69% of

    convos are depth two average depth is 10.7 [Ye and Wu SocInfo 2010, Ritter et al. HLT 2010] reply-to degree and depth are limited
  23. Explicit Matters Twitter 28% of Tweets in conversations 69% of

    convos are depth two average depth is 10.7 [Ye and Wu SocInfo 2010, Ritter et al. HLT 2010] reply-to degree and depth are limited 109 smaller graph for a year of Tweets
  24. put_after(key, value, deps) Explicit API track what matters frequently in

    data model already (possibly empty) set of references to other writes
  25. put_after(key, value, deps) Explicit API track what matters frequently in

    data model already can simulate fencing (possibly empty) set of references to other writes
  26. put_after(key, value, deps) Explicit API track what matters frequently in

    data model already can simulate fencing (possibly empty) set of references to other writes won’t track non-explicit references
  27. potential dangers huge causality graphs explicit causality semantic context to

    the rescue consider modern apps helps with #1, indirectly with #2 throughput scalability limited