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

1. Sagas Papers We Love SF
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 & Commutative
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 & Commutative
79. Sagas • Long Lived / Distributed Transactions • Trade Atomicity for Availability • Failure Management Pattern
80. Thank You