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

Papers We Love SF - Sagas

Papers We Love SF - Sagas

A talk about Sagas https://www.cs.cornell.edu/andru/cs711/2002fa/reading/sagas.pdf

And the application of them in Distributed Systems

Caitie McCaffrey

March 18, 2016
Tweet

More Decks by Caitie McCaffrey

Other Decks in Technology

Transcript

  1. Sagas
    Papers We Love SF

    View full-size slide

  2. Caitie McCaffrey
    Distributed Systems Engineer
    @Caitie
    CaitieM.com

    View full-size slide

  3. • Why Sagas?
    • Sagas Paper
    • Distributed Sagas
    • Sagas in Halo 4

    View full-size slide

  4. Systems Used to Be Simple

    View full-size slide

  5. Serializability &
    ACID

    View full-size slide

  6. SOA/Microservices

    View full-size slide

  7. Two Phase Commit

    View full-size slide

  8. 2PC: Prepare Phase

    View full-size slide

  9. 2PC: Commit Phase

    View full-size slide

  10. 2PC Doesn’t Scale
    • O(n^2) Messages
    • Coordinator: Single Point of Failure
    • Reduced Throughput

    View full-size slide

  11. Spanner
    Google’s Globally-Distributed Database
    Corbett et. al.

    View full-size slide

  12. –Corbett et al.
    “Spanner is Google’s scalable, multi-version,
    globally distributed, and synchronously-
    replicated database. It is the first system to
    distribute data at global scale and support
    externally-consistent distributed
    transactions.”

    View full-size slide

  13. “The key enabler of these
    properties is a new TrueTime API
    and its implementation…using
    multiple modern clock references
    (GPS and atomic clocks).”
    –Corbett et al.

    View full-size slide

  14. Spanner is Expensive & Proprietary
    • Custom Hardware & Data-Centers
    • Synchronization Not Solved

    View full-size slide

  15. Distributed Transactions
    are Hard & Expensive

    View full-size slide

  16. Can We Do
    Better?

    View full-size slide

  17. Can We Do
    Better?

    View full-size slide

  18. Sagas
    Hector Garcia-Molina, Kenneth Salem
    Princeton University 1987

    View full-size slide

  19. Sagas are Long
    Lived Transactions

    View full-size slide

  20. “A Saga is a Long Lived Transaction that
    can be written as a sequence of
    transactions that can be interleaved.
    All transactions in the sequence complete
    successfully or compensating transactions
    are ran to amend a partial execution.”

    View full-size slide

  21. A Saga is a Collection of
    Sub-Transactions
    T1, T2 … Tn

    View full-size slide

  22. Each Sub-Transaction has a
    Compensating Transaction
    C1, C2 … Cn

    View full-size slide

  23. Cn
    Semantically Undoes Tn

    View full-size slide

  24. Saga Guarantee
    Either
    • T1, T2 … Tn or
    • T1, T2 … Tj, Cj, … C2, C1

    View full-size slide

  25. Trade-Off: Atomicity
    for Availability

    View full-size slide

  26. Sagas are a Failure
    Management Pattern

    View full-size slide

  27. Large Single Transaction

    View full-size slide

  28. • Book Hotel (T1
    )
    • Book Car (T2
    )
    • Book Flight (T3
    )
    • Cancel Hotel (C1
    )
    • Cancel Car (C2
    )
    • Cancel Flight (C3
    )
    Sagas

    View full-size slide

  29. Saga Execution
    Coordinator
    (SEC)

    View full-size slide

  30. Saga Log
    • Begin Saga
    • End Saga
    • Abort Saga
    • Begin Ti
    • End Ti
    • Begin Ci
    • End Ci

    View full-size slide

  31. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  32. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  33. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  34. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  35. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  36. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  37. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  38. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    End Book Car Rental (T2
    )
    Start Book Flight (T3
    )
    End Book Flight (T3
    )
    End Saga
    Successful Saga

    View full-size slide

  39. Unsuccessful Saga
    Backwards Recovery

    View full-size slide

  40. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  41. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  42. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  43. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  44. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  45. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  46. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  47. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  48. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  49. Begin Saga
    Start Book Hotel (T1
    )
    End Book Hotel (T1
    )
    Start Book Car Rental (T2
    )
    Abort Saga
    Start Compensate Car Rental (C2
    )
    End Compensate Car Rental (C2
    )
    Start Compensate Book Hotel (C1
    )
    End Compensate Book Hotel (C1
    )
    End Saga
    Unsuccessful Saga

    View full-size slide

  50. –Molina et. al
    “Due to space limitations, we only
    discuss Sagas in a centralized
    System, although clearly they can
    be implemented in a distributed
    database system.”
    Sagas in Distributed Systems

    View full-size slide

  51. SOA/Microservices

    View full-size slide

  52. \
    • Book Hotel (T1
    )
    • Book Car (T2
    )
    • Book Flight (T3
    )
    • Cancel Hotel (C1
    )
    • Cancel Car (C2
    )
    • Cancel Flight (C3
    )
    Requests instead of Transactions

    View full-size slide

  53. A Distributed Saga is a Collection of
    Sub-Requests
    Each Sub-Request has a
    Compensating Request
    T1, T2 … Tn
    C1, C2 … Cn

    View full-size slide

  54. Begin Saga
    Start Book Hotel Request (T1
    )
    End Book Hotel Request (T1
    )
    Start Book Car Rental Request (T2
    )
    End Book Car Rental Request (T2
    )
    Start Book Flight Request (T3
    )
    End Book Flight Request (T3
    )
    End Saga
    Successful Distributed Saga

    View full-size slide

  55. Saga Log
    Durable & Distributed

    View full-size slide

  56. Saga Execution Coordinator (SEC)
    • Interprets & Writes to Saga Log
    • Applies Saga Sub-Requests
    • Applies Saga Compensating Requests
    when Necessary

    View full-size slide

  57. Apply Compensating Requests
    • Aborted Saga Response
    • Start Request Fails
    • SEC Crashes (non-safe state)

    View full-size slide

  58. What Happens when
    Compensating
    Requests Fail?

    View full-size slide

  59. Compensating
    Requests Must Be
    Idempotent &
    Commutative

    View full-size slide

  60. What Happens
    when SEC Fails?

    View full-size slide

  61. Safe States
    • All Executed Sub-Requests are Complete
    (Start Ti
    & End Ti
    both logged)
    • Saga has been Aborted, Proceed with
    Compensating Transactions

    View full-size slide

  62. Un-Safe State
    • Start Ti logged, no End Ti logged
    Abort Saga
    Start Compensating Requests

    View full-size slide

  63. Request Messaging Semantics
    • Sub-Requests (Ti): At Most Once
    • Compensating Requests (Ci): At Least Once

    View full-size slide

  64. Distributed Saga Guarantee
    Either
    • T1, T2 … Tn or
    • T1, T2 … Tj, Cj, … C2, C1

    View full-size slide

  65. Distributed Sagas
    • Distributed/Durable Saga Log
    • SEC Process
    • Compensating Requests: Idempotent &
    Commutative

    View full-size slide

  66. Sagas
    • Long Lived / Distributed Transactions
    • Trade Atomicity for Availability
    • Failure Management Pattern

    View full-size slide