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

PWLSF#10 => Peter Bailis on Managing Update Con...

Papers_We_Love
December 17, 2014

PWLSF#10 => Peter Bailis on Managing Update Conflicts in Bayou

Peter Bailis presents the "Managing Update Conflicts in Bayou, A Weakly Connected Replicated Storage System" paper by Doug Terry, Marvin Theimer, Karin Petersen, Alan J. Demers, Mike J. Spreitzer, and Carl H. Hauser in SOSP 1995. http://db.cs.berkeley.edu/cs286/papers/bayou-sosp1995.pdf

Peter tells us: "A perennial challenge in managing shared, mutable state in distributed systems is the ability to permit concurrent writes while maintaining some degree of application "correctness." Bayou is an excellent and early example of an "optimistic" strategy for handling the concurrent update problem. Many of the techniques in Bayou---such as dependency tracking, application-specific merge procedures, and log shipping---are increasingly popular, can be found in systems like Dynamo, and help understand when and why mechanisms like CRDTs are useful."

Peter's Bio:
Peter (@pbailis) is a Ph.D. candidate at UC Berkeley, where he studies data management and distributed systems. Peter likes fast databases but likes fast and correct databases even more. You can find more information at: http://bailis.org/

The video of this talk is up!! https://www.youtube.com/watch?v=tg7zvyWm_NE&feature=youtu.be

Papers_We_Love

December 17, 2014
Tweet

More Decks by Papers_We_Love

Other Decks in Research

Transcript

  1. Who am I? Ph.D. candidate, 4th year student at Berkeley

    Study high performance distributed databases » When do we need coordination? » What happens if we don’t coordinate? Graduating 2015! http://bailis.org/
  2. Why Bayou? “NoSQL” before “NoSQL” Learn from our predecessors Rethink

    application, system boundaries Lucid discussion of systems challenges
  3. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  4. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  5. Bayou Goals Storage system for mobile devices: Handle frequent disconnections

    Reason about distribution explicitly Facilitate conflict detection and resolution
  6. How do we build a system that allows update- anywhere

    but allows users to easily build correct applications?
  7. Basic Architecture Optimistically replicated distributed database Update-anywhere; CAP “AP” »

    Guarantees availability » Low latency and scalability! Use anti-entropy to exchange updates » Pick your favorite
  8. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  9. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  10. Example: Peter wants to book Fastly HQ on 12/17 at

    7PM Ines wants to book Fastly HQ on 12/17 at 7PM Peter and Ines are connected to different servers What will happen? Example: Mike wants to give Peter $100 Carol wants to give Peter $100 Mike and Carol are connected to different servers What will happen?
  11. Main problem: “conflicts” It depends on the application! Traditional DB

    (“serializability”): always* matters! Bayou: let the application help us out! What happens if two clients simultaneously update the same piece of data?
  12. Main problem: “conflicts” Bayou writes have three components: » An

    update function: the actual write » A dependency check: conflict detection » A merge function: conflict compensation If dependency check passes: apply update function Else: apply merge function
  13. Example: Booking tonight’s meetup: » Update function: insert 12/17/14, “Fastly

    HQ”, Ines » Dependency check: Is the requested time and location available? » Merge function: try to find another time based on provided alternates
  14. Inside the server: Date Location User Time 12/16 Fastly HQ

    Fred 2:30-5PM 12/18 Fastly HQ Artur 10AM-12PM 12/17 FastlyHQ Inez 6:30-9PM Update function: insert 12/17/14, “Fastly HQ”, Ines Dependency check: Is the requested time and location available?
  15. Another example: Money transfer: » Update function: transfer $100 from

    Jan to Mary » Dependency check: does Jan have $100 in her account? » Merge function: log an error
  16. User Balance Jan $110 Marsha $10 Peter $42 » Update

    function: transfer $100 from Jan to Marsha » Dependency check: does Jan have $100 in her account? » Merge function: log an error Errors
  17. » Update function: transfer $100 from Jan to Marsha »

    Dependency check: does Jan have $100 in her account? » Merge function: log an error » Update function: transfer $100 from Jan to Peter » Dependency check: does Jan have $100 in her account? » Merge function: log an error User Balance Jan $10 Marsha $110 Peter $42 Errors
  18. » Update function: transfer $100 from Jan to Marsha »

    Dependency check: does Jan have $100 in her account? » Merge function: log an error » Update function: transfer $100 from Jan to Peter » Dependency check: does Jan have $100 in her account? » Merge function: log an error Errors Jan->Peter failed! User Balance Jan $10 Marsha $110 Peter $42
  19. Write stability How do we ensure that all servers eventually

    agree? Decide on a “stable” prefix of writes: » Strawman: order writes by timestamp • Drawbacks?
  20. » Update function: transfer $100 from Jan to Marsha »

    Dependency check: does Jan have $100 in her account? » Merge function: log an error » Update function: transfer $100 from Jan to Peter » Dependency check: does Jan have $100 in her account? » Merge function: log an error User Balance Jan $10 Marsha $110 Peter $42 Errors Timestamp 10 Timestamp 2
  21. User Balance Jan $110 Marsha $10 Peter $42 Errors »

    Update function: transfer $100 from Jan to Peter » Dependency check: does Jan have $100 in her account? » Merge function: log an error Timestamp 2
  22. User Balance Jan $10 Marsha $10 Peter $142 » Update

    function: transfer $100 from Jan to Peter » Dependency check: does Jan have $100 in her account? » Merge function: log an error Timestamp 2 » Update function: transfer $100 from Jan to Marsha » Dependency check: does Jan have $100 in her account? » Merge function: log an error Timestamp 10 Errors Jan->Marsha failed!
  23. Write stability How do we ensure that all servers eventually

    agree? Decide on a “stable” prefix of writes: » Strawman: order writes by timestamp » Bayou: uses master to determine ordering
  24. Write stability How do we ensure that all servers eventually

    agree? Decide on a “stable” prefix of writes: » Strawman: order writes by timestamp • Drawbacks? » Bayou: uses master to determine ordering • Benefits? Note: don’t require commutative updates!
  25. Read API Can read from: » Stable storage: only committed

    writes » Tentative storage: all writes seen so far Why read from tentative storage at all?
  26. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  27. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  28. Bayou’s Secret Sauce Push app logic into updates: » Read

    and write are insufficiently expressive!
  29. » Update function: transfer $100 from Jan to Peter »

    Dependency check: does Jan have $100 in her account? » Merge function: log an error » Update function: transfer $100 from Jan to Mary » Dependency check: does Jan have $100 in her account? » Merge function: log an error WRITE: Jan = 10; Peter = 42 WRITE: Jan = 10; Mary = 110 » decrement Jan by $100; increment Peter by 100 » decrement Jan by $100; increment Mary by 100
  30. Bayou’s Secret Sauce Push app logic into updates: » Read

    and write are insufficiently expressive! Capture transaction intent: » Dependency checks encode preconditions » e.g., guarded atomic actions
  31. What does Bayou guarantee? Eventually all updates are applied in

    the same order on all servers » Kind of like serializable/ACID transactions! » Dependency checks enforce invariants » Did we just “beat CAP”? Key: eventually means we have to wait
  32. H-Store, VoltDB, Granola, Calvin, Atomic Broadcast Idea sketch: pre-schedule transactions,

    then execute them sequentially on respective servers Totally ordered outcomes on each replica …but ordering determined up front!
  33. Bayou 㱺 “ACID” 1.) Given transaction T, issue write W:

    » Update function: // do nothing » Dependency check: false » Merge function: execute T 2.) Wait for write W to commit. 3.) Notify success.
  34. What does Bayou guarantee? Eventually all writes are applied in

    the same order on all servers » Kind of like serializable/ACID transactions! » Dependency checks enforce invariants » Did we just “beat CAP”? Key: eventually means we have to wait
  35. “This meeting room scheduling program is intended for use after

    a group of people have already decided that they want to meet in a certain room and have determined a set of acceptable times for the meeting. It does not help them to determine a mutually agreeable place and time for the meeting, it only allows them to reserve the room.”
  36. “This meeting room scheduling program is intended for use after

    a group of people have already decided that they want to meet in a certain room and have determined a set of acceptable times for the meeting. It does not help them to determine a mutually agreeable place and time for the meeting, it only allows them to reserve the room.”
  37. “This meeting room scheduling program is intended for use after

    a group of people have already decided that they want to meet in a certain room and have determined a set of acceptable times for the meeting. It does not help them to determine a mutually agreeable place and time for the meeting, it only allows them to reserve the room.”
  38. When can we avoid “waiting”? Commutative logic need not be

    re-executed in the log! (Paper discusses this.)
  39. A note on commutativity Commutative logic: decisions made in application

    logic are insensitive to ordering Commutative datatypes: operations on datatypes are insensitive to ordering The latter are useful, but won’t ensure correctness! http://www.bailis.org/blog/data-integrity-and-problems-of-scope/
  40. » Update function: transfer $100 from Jan to Peter »

    Dependency check: does Jan have $100 in her account? » Merge function: log an error » Update function: transfer $100 from Jan to Marsha » Dependency check: does Jan have $100 in her account? » Merge function: log an error » decrement Jan by $100; increment Peter by 100 » decrement Jan by $100; increment Marsha by 100 WRITE: Jan = 10; Peter = 42 WRITE: Jan = 10; Marsha = 110
  41. A note on commutativity Commutative logic: decisions made in application

    logic are insensitive to ordering Commutative datatypes: operations on datatypes are insensitive to ordering The latter are useful, but won’t ensure correctness! http://www.bailis.org/blog/data-integrity-and-problems-of-scope/
  42. When can we avoid “waiting”? CALM Theorem: monotonic logic <=>

    determinism despite different orders [CIDR 2011] See also Kuper’s LVars I-confluence: guarantees “safe” tentative reads with convergent and safe outcomes [VLDB 2015] Commutative logic need not be re-executed in the log! (Paper discusses this.)
  43. A note on immutability Bayou’s stable log is “immutable” »

    e.g., event sourcing, Lambda architecture But what guarantees can we make about the outcomes in the log? » “Immutable” writes are the easy part! » Reasoning about outcomes is the challenge
  44. Why have “merge” at all? Why not just ship the

    stored procedures and re-execute them instead? » Update function: transfer $100 from Jan to Peter » Dependency check: does Jan have $100 in her account? If Jan has $100: transfer $100 from Jan to Peter Else: Log an error
  45. a

  46. Durability? In this context, durability and consistency are effectively orthogonal

    » Durability: “survive F faults, need F+1 servers” » Strong consistency: usually requires “majority” Bayou: local updates may not survive faults » But the (arguably) more fundamental part of the system is maintaining updates
  47. Bayou vs. Dynamo Fully replicated Update-one In-order per-server sequenced anti-entropy

    Server-side merge Global stability detection No “strong” consistency Partially replicated Update-N Merkle tree-based anti- entropy Client-side merge No notion of, API for stability Regular registers via majority quorum
  48. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  49. Talk Outline Background and system architecture Conflict detection and resolution

    APIs “Correctness” and ordering Lessons for all of us
  50. Why Bayou? “NoSQL” before “NoSQL” Learn from smart predecessors Rethink

    application, system boundaries Lucid discussion of systems challenges
  51. Bayou Goals Handle frequent disconnections » Embrace replication, update-anywhere Reason

    about distribution explicitly » Require application semantics Facilitate conflict detection and resolution » Use merge and dependency APIs
  52. “Weakly consistent replication has been used previously for availability, simplicity,

    and scalability in a variety of systems [3, 7, 10, 12, 15, 19].”
  53. “Weakly consistent replication has been used previously for availability, simplicity,

    and scalability in a variety of systems [3, 7, 10, 12, 15, 19].”
  54. Simplicity for whom? Architects Systems programmers Operators Application writers? Users?

    Analogous issues in RDBMS design! http://www.bailis.org/blog/understanding-weak- isolation-is-a-serious-problem/
  55. 2.6 Billion Internet users in 2013 7.1 Billion humans on

    planet Earth Who cares about scale? Coordination? Will data keep increasing? Why? Hint: not humans. [Mary Meeker]
  56. Xerox PARC Laser printers Computer-generated bitmap graphics The Graphical user

    interface, featuring windows and icons, operated with a mouse The WYSIWYG text editor The precursor to PostScript Ethernet as a local-area computer network Fully formed object-oriented programming in the Smalltalk programming language and integrated development environment. Model–view–controller software architecture Bayou! [Wikipedia]
  57. What can we learn? 1.) Integrating application logic is key

    to “correct” execution of “AP” distributed systems. R/W is bad. 2.) Lack of app-specific mechanisms in a coordination- free system is a recipe for data corruption. 3.) Merge/repair is a narrow API for developers to express their application conflicts. 4.) Alternatives like commutativity, I-confluence, and research tools like Bloom can help limit overhead.