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

Distributed Sagas: A Protocol for Coordinating Microservices

Distributed Sagas: A Protocol for Coordinating Microservices

Microservices have become the defacto architecture pattern for building services. However separating business logic into small services that operate with a single logical data set has introduced consistency challenges. Previous attempts to solve this problem like two phase commit have not been widely adopted due to availability and liveness issues.

Instead developers implement feral concurrency control mechanism. This technique can be error prone, and often results in “Death Star” architectures which rely on chained calls to enforce application invariants. These architectures become more complicated over time, and are difficult to modify and extend, and often don't correctly handle all failure scenarios.

In this talk I propose a new solution for this problem, Distributed Sagas, a protocol for coordinating requests among multiple micro services, while ensuring application invariants.

Caitie McCaffrey

May 19, 2017
Tweet

More Decks by Caitie McCaffrey

Other Decks in Technology

Transcript

  1. Distributed Sagas
    A Protocol for Coordinating Microservices

    View Slide

  2. Caitie McCaffrey
    Distributed Systems Engineer
    caitiem.com
    @caitie

    View Slide

  3. Service Service
    Service
    Monoliths

    View Slide

  4. Microservices & NoSQL

    View Slide

  5. 2015

    View Slide

  6. 2015
    “Application-level
    Mechanisms for maintaining
    database integrity”

    View Slide

  7. Reserve a Hotel
    Front End

    View Slide

  8. Reserve a Hotel
    Front End
    Feral Concurrency
    Control Mechanisms

    View Slide

  9. Reserve a Hotel
    Front End
    Feral Concurrency
    Control Mechanisms

    View Slide

  10. Reserve a Car
    Front End

    View Slide

  11. Reserve a Flight
    Front End

    View Slide

  12. Trips
    Front End

    View Slide

  13. Trips
    Front End
    Trips

    View Slide

  14. Trips
    Front End
    Trips
    Feral Concurrency
    Control Mechanisms

    View Slide

  15. Trips
    Front End
    Trips
    Feral Concurrency
    Control Mechanisms

    View Slide

  16. Trips
    Front End
    Trips
    Feral Concurrency
    Control Mechanisms

    View Slide

  17. Front End
    Trips
    Architecture

    View Slide

  18. Death Star Architectures

    View Slide

  19. Can We Do Better
    than Feral Concurrency Control?

    View Slide

  20. 2012

    View Slide

  21. 2012
    “Spanner is Google’s scalable, multi-
    version, globally distributed, and
    synchronously-replicated database”

    View Slide

  22. 2015

    View Slide

  23. 2015
    “The biggest barrier…is that
    consistency mechanisms must
    integrate across many
    stateful services”

    View Slide

  24. Two Phase Commit

    View Slide

  25. 2PC: Prepare Front End
    Trips
    Propose Book Hotel
    Propose Book Car
    Propose Book
    Flight

    View Slide

  26. 2PC: Prepare Front End
    Trips
    Vote Book Hotel
    Vote Book Car
    Vote Book
    Flight

    View Slide

  27. 2PC: Commit Front End
    Trips
    Commit/Abort Book Hotel
    Commit/Abort Book Car
    Commit/Abort
    Book Flight

    View Slide

  28. 2PC: Commit Front End
    Trips
    Done
    Done
    Done

    View Slide

  29. 2PC: Commit Front End
    Trips
    Done
    Done
    Done
    Doesn’t Scale
    •O (N^2) Messages in the worst case
    •Coordinator is a Single Point of Failure
    •Reduced Throughput

    View Slide

  30. Distributed Sagas
    A Protocol for Coordinating Microservices

    View Slide

  31. 1987

    View Slide

  32. 1987
    “Sagas are Long Lived Transactions
    [in a single relational Database]”

    View Slide

  33. 1987
    “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 Slide

  34. Distributed Sagas
    A Protocol for Coordinating Microservices

    View Slide

  35. A Distributed Saga is a Collection of Requests
    Book Hotel Book Car Book Flight Charge Money

    View Slide

  36. A Distributed Saga is a Collection of Requests
    Book Hotel Book Car Book Flight Charge Money
    and Compensating Requests
    Cancel Hotel Cancel Car Cancel Flight Refund Money

    View Slide

  37. A Distributed Saga is a Collection of Requests
    Book Hotel Book Car Book Flight Charge Money
    and Compensating Requests
    Cancel Hotel Cancel Car Cancel Flight Refund Money
    that represent a single business level action

    View Slide

  38. Distributed Saga
    Requests

    View Slide

  39. Requests
    Can Abort
    Book Car

    View Slide

  40. Requests
    Can Abort
    Book Car

    View Slide

  41. Requests
    Must Be Idempotent
    Book Car

    View Slide

  42. Requests
    Must Be Idempotent
    Book Car

    View Slide

  43. Requests
    Must Be Idempotent
    Book Car

    View Slide

  44. Requests
    Must Be Idempotent
    Book Car

    View Slide

  45. Requests
    Must Be Idempotent
    Book Car

    View Slide

  46. Requests
    Must Be Idempotent
    Book Car
    Timeout

    View Slide

  47. Requests
    Must Be Idempotent
    Book Car

    View Slide

  48. Requests
    Must Be Idempotent
    Book Car

    View Slide

  49. Distributed Saga
    Compensating Requests

    View Slide

  50. Compensating Requests
    Semantically undoes the effect of a request

    View Slide

  51. Cancel Car
    Compensating
    Requests
    Cannot Abort

    View Slide

  52. Cancel Car
    Compensating
    Requests
    Can Not Abort

    View Slide

  53. Cancel Car
    Compensating
    Requests
    Must Be Idempotent

    View Slide

  54. Compensating
    Requests
    Must Be Commutative
    with Requests
    Book Car
    Cancel Car
    Cancel Car
    Book Car
    is the same as

    View Slide

  55. Compensating
    Requests
    Book Car
    Must Be Commutative
    with Requests

    View Slide

  56. Compensating
    Requests
    Book Car
    Timeout
    Must Be Commutative
    with Requests

    View Slide

  57. Compensating
    Requests
    Book Car
    Book Car
    Must Be Commutative
    with Requests

    View Slide

  58. Compensating
    Requests
    Book Car
    Book Car
    Cancel Car
    Must Be Commutative
    with Requests

    View Slide

  59. Compensating
    Requests
    Book Car
    Book Car
    Cancel Car
    Must Be Commutative
    with Requests

    View Slide

  60. Compensating
    Requests
    Requests
    Idempotent Idempotent
    Commutative
    Can Not Abort
    Can Abort

    View Slide

  61. Distributed Saga Guarantee
    Book Hotel Book Car Book Flight Charge Money
    All requests were completed successfully

    View Slide

  62. Distributed Saga Guarantee
    Book Hotel Book Car Book Flight Charge Money
    All requests were completed successfully
    Or a subset of requests and the corresponding
    compensating requests were executed
    Book Hotel Book Car Cancel Hotel Cancel Car

    View Slide

  63. Distributed Saga Guarantee
    Book Hotel Book Car Book Flight Charge Money
    All requests were completed successfully
    Or a subset of requests and the corresponding
    compensating requests were executed
    Book Hotel Book Car Cancel Hotel Cancel Car
    No Atomicity
    No Isolation

    View Slide

  64. Distributed Saga Guarantee
    Book Hotel Book Car Book Flight Charge Money
    All requests were completed successfully
    Or a subset of requests and the corresponding
    compensating requests were executed
    Book Hotel Book Car Cancel Hotel Cancel Car
    No Atomicity
    No Isolation
    Book Hotel
    Book Car
    Visible before
    Saga Completes

    View Slide

  65. Distributed Saga Guarantee
    Book Hotel Book Car Book Flight Charge Money
    All requests were completed successfully
    Or a subset of requests and the corresponding
    compensating requests were executed
    Book Hotel Book Car Cancel Hotel Cancel Car

    View Slide

  66. Distributed Saga
    defining a

    View Slide

  67. Directed Acyclic Graph
    Distributed Saga Car Flight
    Hotel
    Payment
    Start Saga
    End Saga

    View Slide

  68. Name: Hotel
    Request: Book Hotel
    Compensating Request: Cancel Hotel
    Status: Not Completed
    Vertex
    Distributed Saga

    View Slide

  69. Start & End Vertices
    Distributed Saga
    Start Saga
    End Saga
    Car Flight
    Hotel
    Payment
    Start Saga
    End Saga

    View Slide

  70. Distributed Saga Log
    fault-tolerant & highly available

    View Slide

  71. Saga Execution Coordinator
    SEC
    Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log

    View Slide

  72. Distributed Saga
    Executing a

    View Slide

  73. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Book Trip Request
    SEC

    View Slide

  74. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    SEC
    Saga Log
    Start Saga
    Book Trip Request

    View Slide

  75. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    SEC
    Saga Log
    Done
    Start Saga
    Book Trip Request

    View Slide

  76. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Start Hotel
    Start Saga

    View Slide

  77. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Done
    Start Saga
    Start Hotel

    View Slide

  78. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Book Hotel
    Request
    Start Saga
    Start Hotel

    View Slide

  79. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Book Hotel
    Response
    Start Saga
    Start Hotel

    View Slide

  80. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    End Hotel
    Start Saga
    Start Hotel

    View Slide

  81. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Done
    Start Saga
    Start Hotel
    End Hotel

    View Slide

  82. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Start Car
    Start Saga
    Start Hotel
    End Hotel

    View Slide

  83. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Done
    Book Car
    Request
    Start Saga
    Start Hotel
    End Hotel
    Start Car

    View Slide

  84. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Book Car
    Response
    End Car

    View Slide

  85. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Done
    End Car

    View Slide

  86. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    End Car

    View Slide

  87. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Done
    End Car
    Start Flight Book Flight
    Request

    View Slide

  88. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    Book Flight
    Response
    End Flight

    View Slide

  89. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    Done
    End Flight

    View Slide

  90. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    Start Payment
    End Flight

    View Slide

  91. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    Done
    End Flight
    Start Payment
    Payment
    Request

    View Slide

  92. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    End Payment
    End Flight
    Start Payment
    Payment
    Response

    View Slide

  93. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    End Flight
    Start Payment
    End Payment
    Done

    View Slide

  94. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    End Flight
    Start Payment
    End Payment
    End Saga

    View Slide

  95. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    End Flight
    Start Payment
    End Payment
    Done
    End Saga

    View Slide

  96. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    End Car
    Start Flight
    End Flight
    Start Payment
    End Payment
    End Saga

    View Slide

  97. Distributed Saga
    Failure of a

    View Slide

  98. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    SEC
    Book Car
    Request
    Start Saga
    Start Hotel
    End Hotel
    Start Car
    Start Flight

    View Slide

  99. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Book Car
    Response
    Abort Car
    Start Car
    Start Flight

    View Slide

  100. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Done
    Start Car
    Start Flight
    Abort Car

    View Slide

  101. Car Flight
    Hotel
    Payment
    Start Saga
    End Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Done
    Start Car
    Start Flight
    Abort Car
    Rollback Recovery

    View Slide

  102. Car Flight
    Hotel
    Payment
    End Comp Saga
    Start Comp Saga
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car

    View Slide

  103. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Start Comp Saga
    End Comp Saga

    View Slide

  104. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Payment Log
    Entries?
    Start Car
    Start Flight
    Abort Car
    Start Comp Saga
    End Comp Saga

    View Slide

  105. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    { }
    Start Car
    Start Flight
    Abort Car
    Start Comp Saga
    End Comp Saga

    View Slide

  106. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Car Log
    Entries?
    Start Comp Saga
    End Comp Saga

    View Slide

  107. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    { Start, Abort }
    Start Comp Saga
    End Comp Saga

    View Slide

  108. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Hotel Log
    Entries?
    Start Comp Saga
    End Comp Saga

    View Slide

  109. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    { Start, End }
    Start Comp Saga
    End Comp Saga

    View Slide

  110. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    { Start, End }
    Cancel Hotel
    Request
    Start Comp Saga
    End Comp Saga

    View Slide

  111. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Cancel Hotel
    Response
    Comp Hotel
    Start Comp Saga
    End Comp Saga

    View Slide

  112. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Done
    Comp Hotel
    Start Comp Saga
    End Comp Saga

    View Slide

  113. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    Flight Log
    Entries?
    Start Comp Saga
    End Comp Saga

    View Slide

  114. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    { Start }
    Start Comp Saga
    End Comp Saga

    View Slide

  115. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    { Start }
    Book Flight
    Request
    Start Comp Saga
    End Comp Saga

    View Slide

  116. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    End Flight
    Book Flight
    Response
    Start Comp Saga
    End Comp Saga

    View Slide

  117. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    Done
    Cancel Flight
    Request
    End Flight
    Start Comp Saga
    End Comp Saga

    View Slide

  118. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    Comp Flight
    Cancel Flight
    Response
    Start Comp Saga
    End Comp Saga
    End Flight

    View Slide

  119. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    Done
    Comp Flight
    Start Comp Saga
    End Comp Saga
    End Flight
    Comp Flight

    View Slide

  120. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    End Saga
    Start Comp Saga
    End Comp Saga
    Comp Flight
    End Flight
    Comp Flight

    View Slide

  121. Car Flight
    Hotel
    Payment
    Saga Log
    Start Saga
    SEC
    Start Hotel
    End Hotel
    Start Car
    Start Flight
    Abort Car
    Comp Hotel
    Done
    End Saga
    Start Comp Saga
    End Comp Saga
    Comp Flight
    End Flight
    Comp Flight

    View Slide

  122. Distributed Saga Guarantee
    Book Hotel Book Car Book Flight Charge Money
    All requests were completed successfully
    Or a subset of requests and the corresponding
    compensating requests were executed
    Book Hotel Book Car Cancel Hotel Cancel Car

    View Slide

  123. Saga Execution Coordinator
    Recovering from
    Failure

    View Slide

  124. Front End
    SEC
    Start Saga
    End Saga
    Saga Log

    View Slide

  125. Front End
    SEC
    Start Saga
    End Saga
    Saga Log

    View Slide

  126. Front End
    SEC
    Start Saga
    End Saga
    Saga Log

    View Slide

  127. Front End
    SEC
    Saga Log
    Start Saga
    End Saga

    View Slide

  128. with Distributed Sagas
    Isolation of Complex Code
    Fron
    Tr
    Complex Code
    Lives Everywhere
    Front
    SEC
    Saga Log
    Complex Code
    Lives Here
    Complex Code
    Lives Here

    View Slide

  129. Fron
    Tr
    with Distributed Sagas
    Modular Services
    Front
    SEC
    Saga Log
    Only Flight
    Booking
    Flight Booking &
    Feral Concurrency
    Control Mechanisms

    View Slide

  130. Fron
    Tr
    with Distributed Sagas
    Service Composition
    Front
    SEC
    Saga Log
    Just Add A
    New Saga! New Service &
    Feral Concurrency
    Control Mechanisms

    View Slide

  131. Distributed Sagas Makes
    Building & Modifying
    Microservices Easier

    View Slide

  132. Thank you
    @caitie

    View Slide