Enhancing Concurrency in Distributed Transactions

Explore the challenges and solutions in achieving higher concurrency levels in distributed transactions, focusing on techniques such as optimistic concurrency control and two-phase locking. The importance of maintaining serializability to prevent angry customers and the impact of contention on scalability and throughput are examined.

• Distributed transactions
• Concurrency control
• Serializability
• Optimistic concurrency
• Scalability

riad659 Follow

Uploaded on Oct 03, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Rococo: Extract more concurrency from distributed transactions Shuai Mu, Yang Cui, Yang Zhang, Wyatt Lloyd, Jinyang Li Tsinghua University, New York University, University of Southern California, Facebook 1

2. What Large Web Sites Need 36.8 million sold/day 170 million sold/day $169 billion trade/day Scalable Storage w/ Transactions! 2

3. What is a Distributed Transaction BEGIN_TX if (iphone > 0) { iphone--; } if (case > 0) { case--; } END_TX Item iPhone 6 Plus iPhone Case Stock 1 1 if (iphone > 0) { iphone--; } Transactions should be strictly serializable! Otherwise if (case > 0) { case--; } iPhone=1 Case=1 3

4. Loss of serializability = angry customer 4

5. Serializability is Costly under Contention Two-Phase Locking (2PL) Optimistic Concurrency Control (OCC) Throughput transaction/s # of concurrent transactions 5

6. OCC Aborts Contended Transactions if (iphone > 0) { iphone--; } if (case > 0) { case--; } if (iphone > 0) { iphone--; } if (case > 0) { case--; } Two-Phase Commit Execute (2PC) if (case > 0) { case--; } If (iphone > 0) { iphone--; } iPhone=1 Case=1 if (case > 0) { case--; } If (iphone > 0) { iphone--; } 6

7. 2PL Blocks Contended Transactions if (iphone > 0) { iphone--; } if (case > 0) { case--; } 2PC if (iphone > 0) { iphone--; } if (case > 0) { case--; } Execute If (iphone > 0) { iphone--; } if (case > 0) { case--; } iPhone=1 Case=1 If (iphone > 0) { iphone--; } if (case > 0) { case--; } 7

8. Achieve serializability w/o aborting or blocking* * for common workloads 8

9. Rococos Approach if (iphone > 0) { iphone--; } if (case > 0) { case--; } if (iphone > 0) { iphone--; } if (case > 0) { case--; } if (case > 0) { case--; } If (iphone > 0) { iphone--; } iPhone=1 Case=1 if (case > 0) { case--; } If (iphone > 0) { iphone--; } Defer piece execution to enable reordering 9

10. Rococo Overview: Key techniques Enable piece reordering for serializability 1. Two-phase protocol Most pieces are executed at the second (commit) phase 2. Decentralized dependency tracking Servers track pieces arrival order Identify non-serializable orders Deterministically reorder pieces Avoid aborts for common workloads 3. Offline workload checking Identifies safe workloads (common) Identifies small parts that need traditional approaches (rare) 10

11. #1 Two-phase protocol Commit Phase Start Phase Send pieces to servers w/o executing them Establish a final order and execute pieces Set up a provisional order Reorder for serializability 11

12. #2 Dependency Tracking: Start Phase dep dep T2: T1: T2 T1 if ...iphone-- if ... iphone-- if ... case-- if ... case-- T1 T1 T2 T2 dep dep T2 if ... iphone-- if ... case-- T1 T1 if ... iphone-- if ... case-- T2 Case=1 iPhone=1 12

13. #2 Dependency Tracking: Commit Phase dep dep T2 T1 T1 T2 Sort the cycle by any deterministic order T2 T2 dep dep T1 T1 if ... case-- T2 T1 if ... iphone-- T1 T1 if ... case-- if ... iphone-- T1 T2 T2 T2 Case=1 iPhone=1 13

14. Problem: Not Every Piece is Deferrable oid = next_oid ++ if ... iphone-- Intermediate Results Calls for Immediate Execution if ... case-- orderline.insert(oid, ) next_oid orderline iPhone Case orderline.insert( oid = next_oid ++ if ... iphone-- if ... case-- oid oid, ) 14

15. Immediate Pieces are Naughty! a = next_a++; a = next_a++; b = next_b++; b = next_b++; ol_a.insert(a, ); ol_a.insert(a, ); ol_b.insert(b, ); ol_b.insert(b, ); next_b = 0 next_a = 0 a = next_a++ b = next_b ++ b = next_b ++ a = next_a++ 1. Common workloads have few immediate pieces 2. Pre-known workload Offline check 15

16. #3: Offline Checking: Basic S(ibling)-edge linking pieces within a transaction T1 T1 T1 T1 Item_Table iphone Item_Table case C(onflict)-edge linking pieces w/ conflicting access An SC-cycle consists of both S-edge and C-edge T2 T2 iphone Item_Table Item_Table case SC-cycles represent potential non-serializable executions that require 2PL/OCC 16

17. #3: Offline Checking: Enhanced T1 OidTable ItemTable ItemTable Deferrable Immediate T2 OidTable ItemTable ItemTable SC-cycles with deferrable pieces can be safely reordered! 17

18. Incorporating Immediate Pieces oid oid Every cycle contains deferrable pieces, ensured by offline checking iphone iphone A cycle with deferrable pieces is safe to reorder case case orderline orderline case orderline oid iphone case orderline iphone oid dep dep dep dep T2 T1 T2 T1 T2 T1 T2 T1 Immediate dependency Deferrable dependency orderline Case iPhone next_oid 18

19. Decentralized Dependency Tracking Offline Checking Deferred Execution Merged Pieces Read-only Transactions Reducing Dep. Size Fault Tolerance Overlapping Trans. 19

20. Evaluation How does Rococo perform under contention? How does Rococo scale? 20

21. Workload: Scaled TPC-C One warehouse, many districts Partitioned by districts - all transactions distributed 5~15 5~15 5~15 5~15 New order (45%) 5~15 5~15 5~15 5~15 Payment (43%) Delivery (4%) Read-only: OrderStatus(4%), StockLevel (4%) 21

22. Rococo Has Higher Throughput 7000 Rococo Throughput-(new-order/s) 6000 Increasing graph size 2PL 5000 OCC 4000 3000 Aborts due to deadlock detection 2000 1000 Aborts due to conflicts in validation 0 0 50 100 Concurrent reqs/server 8 servers, 10 districts per server Main source of contention is next_oid of each district 22

23. Rococo Avoids Aborts 1.2 61~66ms 1 Rococo 2PL OCC 0.8 Commit rate 0.6 0.4 152~392ms 0.2 173~645ms 0 0 20 40 60 80 100 Concurrent reqs/server 23

24. Rococo Scales Out Almost Linear 60000 Throughput-(new-order/s) 50000 Rococo 2PL 40000 OCC 30000 Blocking 20000 10000 0 Aborts 0 20 40 60 80 100 Number of servers 10 districts per server, fixed # of items contention grows slowly 24

25. Decentralized dependency tracking Related Work Isolation Level Concurrency Control Mech. Rococo Strict-Serial. Rococo Calvin [SIGMOD 12] Strict-Serial. Pre-ordered Locking Spanner [OSDI 12] HStore [VLDB 07] Strict-Serial. Strict-Serial. Centralized sequencing layer, difficult to scale 2PL OCC Lynx [SOSP 13] Granola [SIGMOD 10] Percolator [OSDI 10] Walter [SOSP 11] COPS [SOSP 11] Serial. Serial. S.I. P.S.I. Causal Origin Ordering Timestamp based OCC W-W Preclusion Dependency Tracking 25

26. Conclusion Traditional protocols perform poorly w/ contention OCC aborts & 2PL blocks Rococo defers execution to enable reordering Strict serializability w/o aborting or blocking for common workloads Rococo outperforms 2PL & OCC With growing contention Scales out 26

27. Thank you! Questions? https://github.com/msmummy/rococo Poster tonight! 27