High-Performance Transactions for Persistent Memories

Explore the optimization of transactions for persistent memories, focusing on ordering constraints, synchronous vs. deferred commit transactions, persistency models, and performance evaluation. The study aims to improve transaction performance in the presence of high persistent memory latencies by minimizing unnecessary ordering constraints and ensuring correct commit order.

• Persistent Memories
• Transaction Optimization
• Data Structures
• Performance Evaluation
• Persistency Models

ivar_80 Follow

Uploaded on Sep 16, 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. High-performance transactions for persistent memories Steven Pelley$ Aasheesh Kolli Peter M. Chen Thomas F. Wenisch Ali Saidi* U. of Michigan Snowflake Computing$ ARM* ASPLOS 16, Atlanta, GA 05/05/2016 1

2. Persistent memory system Core-1 Core-2 Core-3 Core-4 L1 $ L1 $ L1 $ L1 $ LLC Recovery DRAM Persistent Memory (PM) 2

3. Motivation PM in-memory recoverable data structures Recovery relies on ordering updates to PM Persistency models [Pelley 14] Interface to constrain order Academia/Industry [Condit 09, Pelley 14, Joshi 15, Intel 15, ARM 16] Hard to reason about Transactions for users Design transactions w/ persistency models 3

4. Transaction performance Simple transaction design Unnecessary ordering constraints acqLocks prepareUndoLog (P) Performance Constraints mutateData (M) commitTx (C) relLocks Exacerbated by high PM latencies Need to minimize unnecessary ordering constraints 4

5. Contributions Optimize transactions for ordering constraints Synchronous Commit Tx (SCT) acqLocks Deferred Commit Tx (DCT) acqLocks Up to 2.5x speedup! prepareUndoLog (P) prepareUndoLog (P) mutateData (M) mutateData (M) relLocks commitTx (C) Deferred commit commitTx (C) relLocks Challenge: ensure correct commit order 5

6. Outline Background Synchronous commit transactions Deferred commit transactions Compare persistency models Evaluation 6

7. Terminology Persist Act of making a store durable in PM Persist memory order (PMO) Memory events ordered by persistency model Fewer constrains higher performance Better re-ordering, coalescing, scheduling Considering only epoch-based persistency models 7

8. Persistency model Consistency Writeback caching /* Init: a = 0, b=0 a,b are persistent */ Core-1 Core-2 Mem Ctrl reordering Core-1 St a = 1 while (a==0){} Core-2 L1 $ L1 $ Constraints Constraints Performance Performance St b = 1 LLC Constraint: St a <p St b Persistency b PM 8 a

9. Transactions acqLocks . . . prepareUndoLog (P) P2 P1 PN Recoverable . . . mutateData (M) M2 M1 MN . . . commitTx (C) C2 C1 CN relLocks Synchronous Commit Transaction (SCT) 9

10. Epoch persistency [Condit 09, Pelley 14, Joshi 15] Barriers break thread execution into epochs Persists across epochs are ordered No ordering within epoch PMO acqLocks Epoch-1 Barrier P1 P2 Pn prepareUndoLog (P) Epoch-2 mutateData (M) Mn M1 M2 commitTx (C) Epoch-3 C1 C2 Cn 10 relLocks

11. Inter-thread ordering Conflicting accesses establish persist order PMO must match coherence order Else, recovery to inconsistent states /* Init: a = 0, b=0 a,b are persistent */ Core-1 St a = 1 while (a==0){} St b = 1 accesses Core-2 Conflicting BARRIER Constraint: St a <p St b 11

12. Conflicting transactions Thread - 1 acqLocks1 PMO P1 P1 M1 M1 Sufficient. Necessary? C1 C1 Thread - 2 relLocks1 acqLocks2 P2 Conflicting accesses P2 M2 M2 C2 C2 relLocks2 12

13. Necessary PMO constraints Thread - 1 P1 acqLocks1 Memory order (As observed by cores) M1 Core-1 Core-2 P1 C1 P2 M1 L1 $ L1 $ M2 C1 Thread - 2 relLocks1 C2 LLC acqLocks2 Conflicting accesses P1 P2 P2 PMO M1 M2 (Req. for recovery) M2 C1 C2 C2 PMO has fewer constraints relLocks2 13

14. Deferred Commit Transaction (DCT) Defer commit past lock release Breaks persist dependency chain Reduces barriers within transaction Must ensure correct commit order Non-trivial changes to locks, logging Details in the paper Increases executed instructions acqLocks prepareUndoLog (P) mutateData (M) relLocks commitTx (C) 14

15. Inter-thread DCT Thread - 1 acqLocks1 PMO Conflictin g accesses P1 P1 M1 P2 relLocks1 M1 Thread - 2 M2 acqLocks2 C1 C1 C2 P2 DCT incurs minimal inter-thread constraints M2 relLocks2 Explicitly ordered In paper: DCT also reduces intra-thread constraints C2 15

16. Outline Background Synchronous commit transactions Deferred commit transactions Compare persistency models Evaluation 16

17. Eager sync v. Epoch persistency Eager sync (based on [Intel 15]) Ordering + Completion Stronger guarantee Easier to reason Potentially fewer barriers Conservative stalling Completion not always req. Synchronous barrier Epoch persistency [Pelley 14] Ordering only (mostly) Weaker guarantee Harder to reason Potentially more barriers Stall when no buffer space Ordering mostly sufficient Delegation barrier 17

18. Barriers in action Synchronous: Epoch-1 persists before Epoch-2 begins Finish E1 E2 $ Core Time Delegation: Epoch-1 ordered to persist before Epoch-2 > Finish E1 E2 $ Core Time 18

19. Outline Background Synchronous commit transactions Deferred commit transactions Compare persistency models Evaluation 19

20. Methodology For Epoch Persistency Trace-based evaluation Exec time = Max(Inst. latency, Persist latency) Inst. latency = Exec time without persist ordering constrains Persist latency = Time to drain persists to PM Governed by #persists, #barriers, PM access latency For Eager Sync Barrier stalls implemented using rdtscp timer Two benchmarks: Update Location (TATP): Write-intensive, small transactions New Order (TPCC): Write-intensive, large transactions 20

21. DCT v. SCT TATP Better Eager sync Epoch persistency 3 3 2.5 2.5 2 2 1.48x Speedup Speedup 2.56x 1.5 1.5 1 1 SCT DCT SCT DCT 0.5 0.5 0 0 0 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 2.5 3 Avg. persist epoch latency (us) Avg. persist epoch latency (us) *Normalized to SCT 21

22. DCT v. SCT - TPCC Better Eager sync Epoch persistency 2 2 1.5 1.5 1.52x 1.47x Speedup Speedup 1 1 0.5 0.5 SCT DCT SCT DCT 0 0 0 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 2.5 3 Avg. persist epoch latency (us) Avg. persist epoch latency (us) *Normalized to SCT 22

23. In the paper Precise definition of the persistency models More persistency models Strict persistency Strand persistency Detailed analysis of ordering constraints What are necessary ordering constraints? How are they enforced? Especially, commit order tracking for DCT 23

24. Conclusions Minimize ordering constrains for performance Optimize transactions for ordering constrains Deferred Commit Transactions 2.5x speedup Trade-offs between persistency models 24

25. Questions? 25

26. Thank you! 26