Applying the Saga Pattern

As we build larger more complex applications and solutions that need to do collaborative processing the traditional ACID transaction model using coordinated 2-phase commit is often no longer suitable. More frequently we have long lived transactions or must act upon resources distributed across various locations and trust boundaries. The Saga Pattern is a useful model for long lived activities and distributed transactions without coordination.

Sagas split work into a set of transactions whose effects can be reversed even after the work has been performed or committed. If a failure occurs compensating transactions are performed to rollback the work. So at its core the Saga is a failure Management Pattern, making it particularly applicable to distributed systems.

In this talk, I'll discuss the fundamentals of the Saga Pattern, and how it can be applied to your systems. In addition we'll discuss how the Halo 4 Services successfully made use of the Saga Pattern when processing game statistics, and how we implemented it in production.

Transcript

1. Applying the Saga Pattern Caitie McCafffrey
2. Caitie McCaffrey! Distributed Systems Engineer @Caitie CaitieM.com
4. • Why Sagas? • Sagas Paper • Distributed Sagas • Sagas in Halo 4
5. Systems Used to Be Simple
6. Serializability & ACID
7. SOA/Microservices
8. Two Phase Commit
9. 2PC: Prepare Phase
10. 2PC: Commit Phase
11. 2PC Doesn’t Scale • O(n^2) Messages • Coordinator: Single Point of Failure • Reduced Throughput
12. Spanner Google’s Globally-Distributed Database Corbett et. al.
13. –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.”
14. “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.
15. Spanner is Expensive & Proprietary • Custom Hardware & Data-Centers • Synchronization Not Solved
16. Distributed Transactions are Hard & Expensive
17. Can We Do Better?
18. Can We Do Better?
19. Sagas Hector Garcia-Molina, Kenneth Salem Princeton University 1987
20. Sagas are Long Lived Transactions
21. “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.”
22. A Saga is a Collection of Sub-Transactions T1, T2 … Tn
23. Each Sub-Transaction has a Compensating Transaction C1, C2 … Cn
24. Cn Semantically Undoes Tn
25. Saga Guarantee Either • T1, T2 … Tn or • T1, T2 … Tj, Cj, … C2, C1
26. Trade-Off: Atomicity for Availability
27. Sagas are a Failure Management Pattern
28. Large Single Transaction
29. • Book Hotel (T1 ) • Book Car (T2 ) • Book Flight (T3 ) • Cancel Hotel (C1 ) • Cancel Car (C2 ) • Cancel Flight (C3 ) Sagas
30. Saga Execution Coordinator (SEC)
31. Saga Log • Begin Saga • End Saga • Abort Saga • Begin Ti • End Ti • Begin Ci • End Ci
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
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
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
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
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
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
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
39. 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
40. Unsuccessful Saga Backwards Recovery
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
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
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
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
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
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
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
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
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
50. 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
51. –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
52. SOA/Microservices
53. \ • Book Hotel (T1 ) • Book Car (T2 ) • Book Flight (T3 ) • Cancel Hotel (C1 ) • Cancel Car (C2 ) • Cancel Flight (C3 ) Requests instead of Transactions
54. A Distributed Saga is a Collection of Sub-Requests Each Sub-Request has a Compensating Request T1, T2 … Tn C1, C2 … Cn
55. 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
56. Saga Log Durable & Distributed
57. Saga Execution Coordinator (SEC) • Interprets & Writes to Saga Log • Applies Saga Sub-Requests • Applies Saga Compensating Requests when Necessary
67. Apply Compensating Requests • Aborted Saga Response • Start Request Fails • SEC Crashes (non-safe state)
71. What Happens when Compensating Requests Fail?
72. Compensating Requests Must Be Idempotent
73. What Happens when SEC Fails?
74. Safe States • All Executed Sub-Requests are Complete (Start Ti & End Ti both logged) • Saga has been Aborted, Proceed with Compensating Transactions
75. Un-Safe State • Start Ti logged, no End Ti logged Abort Saga Start Compensating Requests
76. Request Messaging Semantics • Sub-Requests (Ti): At Most Once • Compensating Requests (Ci): At Least Once
77. Distributed Saga Guarantee Either • T1, T2 … Tn or • T1, T2 … Tj, Cj, … C2, C1
78. Distributed Sagas • Distributed/Durable Saga Log • SEC Process • Compensating Requests: Idempotent
80. Halo Statistics
81. Halo Statistics Service
82. Halo Statistics Service with Sagas
83. Forward-Recovery
84. Store Stats Player One Store Stats Player Two Store Stats Player Three Store Stats Player Four Game Grain / SEC
85. Forward Recovery Sub-Requests Must Also Be Idempotent
86. Store Stats Player One Store Stats Player Two Store Stats Player Three Store Stats Player Four Game Grain / SEC
87. Store Stats Player One Store Stats Player Two Store Stats Player Three Store Stats Player Four Game Grain / SEC
88. Sagas • Long Lived / Distributed Transactions • Trade Atomicity for Availability • Failure Management Pattern
89. Thank You • @pbailis • @randommood • @tsantero • @aphyr • @jmhodges • @clemnsv
90. Questions? Please remember to evaluate via the GOTO Guide App @Caitie