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 full-size slide

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

    View full-size slide

  3. Service Service
    Service
    Monoliths

    View full-size slide

  4. Microservices & NoSQL

    View full-size slide

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

    View full-size slide

  6. Reserve a Hotel
    Front End

    View full-size slide

  7. Reserve a Hotel
    Front End
    Feral Concurrency
    Control Mechanisms

    View full-size slide

  8. Reserve a Hotel
    Front End
    Feral Concurrency
    Control Mechanisms

    View full-size slide

  9. Reserve a Car
    Front End

    View full-size slide

  10. Reserve a Flight
    Front End

    View full-size slide

  11. Trips
    Front End

    View full-size slide

  12. Trips
    Front End
    Trips

    View full-size slide

  13. Trips
    Front End
    Trips
    Feral Concurrency
    Control Mechanisms

    View full-size slide

  14. Trips
    Front End
    Trips
    Feral Concurrency
    Control Mechanisms

    View full-size slide

  15. Trips
    Front End
    Trips
    Feral Concurrency
    Control Mechanisms

    View full-size slide

  16. Front End
    Trips
    Architecture

    View full-size slide

  17. Death Star Architectures

    View full-size slide

  18. Can We Do Better
    than Feral Concurrency Control?

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  21. Two Phase Commit

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  26. 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 full-size slide

  27. Distributed Sagas
    A Protocol for Coordinating Microservices

    View full-size slide

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

    View full-size slide

  29. 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 full-size slide

  30. Distributed Sagas
    A Protocol for Coordinating Microservices

    View full-size slide

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

    View full-size slide

  32. 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 full-size slide

  33. 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 full-size slide

  34. Distributed Saga
    Requests

    View full-size slide

  35. Requests
    Can Abort
    Book Car

    View full-size slide

  36. Requests
    Can Abort
    Book Car

    View full-size slide

  37. Requests
    Must Be Idempotent
    Book Car

    View full-size slide

  38. Requests
    Must Be Idempotent
    Book Car

    View full-size slide

  39. Requests
    Must Be Idempotent
    Book Car

    View full-size slide

  40. Requests
    Must Be Idempotent
    Book Car

    View full-size slide

  41. Requests
    Must Be Idempotent
    Book Car

    View full-size slide

  42. Requests
    Must Be Idempotent
    Book Car
    Timeout

    View full-size slide

  43. Requests
    Must Be Idempotent
    Book Car

    View full-size slide

  44. Requests
    Must Be Idempotent
    Book Car

    View full-size slide

  45. Distributed Saga
    Compensating Requests

    View full-size slide

  46. Compensating Requests
    Semantically undoes the effect of a request

    View full-size slide

  47. Cancel Car
    Compensating
    Requests
    Cannot Abort

    View full-size slide

  48. Cancel Car
    Compensating
    Requests
    Can Not Abort

    View full-size slide

  49. Cancel Car
    Compensating
    Requests
    Must Be Idempotent

    View full-size slide

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

    View full-size slide

  51. Compensating
    Requests
    Book Car
    Must Be Commutative
    with Requests

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  58. 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 full-size slide

  59. 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 full-size slide

  60. 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 full-size slide

  61. 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 full-size slide

  62. Distributed Saga
    defining a

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  66. Distributed Saga Log
    fault-tolerant & highly available

    View full-size slide

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

    View full-size slide

  68. Distributed Saga
    Executing a

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  80. 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 full-size slide

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

    View full-size slide

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

    View full-size slide

  83. 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 full-size slide

  84. 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 full-size slide

  85. 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 full-size slide

  86. 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 full-size slide

  87. 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 full-size 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
    End Payment
    End Flight
    Start Payment
    Payment
    Response

    View full-size 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
    End Flight
    Start Payment
    End Payment
    Done

    View full-size 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
    End Flight
    Start Payment
    End Payment
    End Saga

    View full-size 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
    End Flight
    Start Payment
    End Payment
    Done
    End Saga

    View full-size 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 Flight
    Start Payment
    End Payment
    End Saga

    View full-size slide

  93. Distributed Saga
    Failure of a

    View full-size slide

  94. 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 full-size slide

  95. 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 full-size slide

  96. 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 full-size slide

  97. 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 full-size slide

  98. 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 full-size slide

  99. 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 full-size slide

  100. 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 full-size slide

  101. 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 full-size slide

  102. 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 full-size slide

  103. 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 full-size slide

  104. 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 full-size slide

  105. 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 full-size slide

  106. 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 full-size slide

  107. 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 full-size slide

  108. 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 full-size slide

  109. 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 full-size slide

  110. 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 full-size slide

  111. 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 full-size slide

  112. 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 full-size slide

  113. 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 full-size slide

  114. 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 full-size slide

  115. 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 full-size slide

  116. 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 full-size slide

  117. 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 full-size slide

  118. 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 full-size slide

  119. Saga Execution Coordinator
    Recovering from
    Failure

    View full-size slide

  120. Front End
    SEC
    Start Saga
    End Saga
    Saga Log

    View full-size slide

  121. Front End
    SEC
    Start Saga
    End Saga
    Saga Log

    View full-size slide

  122. Front End
    SEC
    Start Saga
    End Saga
    Saga Log

    View full-size slide

  123. Front End
    SEC
    Saga Log
    Start Saga
    End Saga

    View full-size slide

  124. 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 full-size slide

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

    View full-size slide

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

    View full-size slide

  127. Distributed Sagas Makes
    Building & Modifying
    Microservices Easier

    View full-size slide

  128. Thank you
    @caitie

    View full-size slide