Slide 1: Improving In-Memory Database Index Performance with Intel Transactional Synchronization Extensions
Improving In-Memory Database Index Performance with Intel® Transactional Synchronization Extensions Tomas Karnagel (TU Dresden) Roman Dementiev (Intel Corporation) Ravi Rajwar (Intel Corporation) Konrad Lai (Intel Corporation) Thomas Legler (SAP AG) Benjamin Schlegel (TU Dresden) Wolfgang Lehner (TU
Slide 2: Challenge: Implementing Concurrency Control
Challenge: Implementing Concurrency Control High-performance in-memory databases Extensively use low-level synchronization mechanisms Synchronize access to internal in-memory data structures Rich history with numerous proposals and implementations Remains complicated and difficult to verify/de
Slide 3: A Case Study: Two Index Implementations
A Case Study: Two Index Implementations B+Tree Index Delta Storage Index (a common index implementation) (from the SAP HANA® database) 25 20 20 15 speedup speedup 15 no lock no lock 10 10 Spin Lock RW Lock RW Lock 5 Spin Lock 5 0 0 0 20 0 20 Read-Only Queries on Dual Socket Intel® Xeon® E5-2680 Serv
Slide 4: Hardware Trends
Hardware Trends Hardware support for Transactional Synchronization IBM System z CPU (zEC12) 4th Generation Core ™ Processors (codenamed Haswell) Goal Enable development of simple and scalable easy-to-verify implementations Without requiring new programming models and paradigms Question How
Slide 5: Outline
Outline Challenge and Trends Intel Transactional Synchronization Extensions (Intel TSX) Case Study: SAP HANA index implementation Applying Intel TSX Analysis and Transformations Results Lessons and Summary 5
Slide 6: What is Intel TSX?
What is Intel® TSX? Hardware support to enable Lock Elision Focus on lock granularity optimizations Fine grain performance at coarse grain effort Intel® TSX: Instruction Set Extensions for Intel Architecture Transactionally execute lock-protected critical sections Execute without acquiring l
Slide 7: Intel TSX Interfaces for Lock Elision
Intel® TSX Interfaces for Lock Elision Hardware Lock Elision (HLE) – XACQUIRE/XRELEASE Software uses legacy compatible hints to identify critical section. Hints ignored on hardware without TSX Hardware support to execute transactionally without acquiring lock Abort causes a re-execution with
Slide 8: Outline
Outline Challenge and Trends Intel Transactional Synchronization Extensions Case Study: SAP HANA index implementations Applying Intel TSX Analysis and Transformations Results Summary 8
Slide 9: Case Study: Index Tree Implementations
Case Study: Index Tree Implementations SAP HANA Database Read optimized column store database system Two index implementations B+Tree [Data Structure] Common index implementation Smaller foot print Delta Storage Index (B+Tree with a Dictionary) Complex data structure with additional supp
Slide 10: Steps To Apply Intel TSX
Steps To Apply Intel TSX Modify synchronization library to use Intel TSX for lock elision Use either the HLE or RTM interface Application changes not immediately required RTM: Start with good “fallback handler" design Avoid “the lemming effect” Retry appropriately for both conflict and capac
Slide 11: Lemming Effect: Persistent convoy of non-transactional execution
Lemming Effect: Persistent convoy of non- transactional execution XA xbegin; test; xabort; (retry loop when lock is busy) L—U Lock; critical section; Unlock (non-transactional execution) T1 --AL T2 ---A T3 ---A Happens when a thread aborts and acquires the lock And aborts other threads 11
Slide 12: Lemming Effect: Persistent convoy of non-transactional execution
Lemming Effect: Persistent convoy of non- transactional execution XA xbegin; test; xabort; (retry loop when lock is busy) L—U Lock; critical section; Unlock (non-transactional execution) T1 --AL-------- T2 ---AXAXAXAXA T3 ---AXAXAXAXA Happens when a thread aborts and acquires the lock And aborts
Slide 13: Lemming Effect: Persistent convoy of non-transactional execution
Lemming Effect: Persistent convoy of non- transactional execution XA xbegin; test; xabort; (retry loop when lock is busy) L—U Lock; critical section; Unlock (non-transactional execution) T1 --AL------------UXAXAXAXAXAsssssss T2 ---AXAXAXAXAXAsssL------------UXAX T3 ---AXAXAXAXAXAsssssssssssssssssL--
Slide 14: Lemming Effect: Persistent convoy of non-transactional execution
Lemming Effect: Persistent convoy of non- transactional execution XA xbegin; test; xabort; (retry loop when lock is busy) L—U Lock; critical section; Unlock (non-transactional execution) T1 --AL------------UXAXAXAXAXAssssssssssssssssL----------UXAXA T2 ---AXAXAXAXAXAsssL------------UXAXAXAXAXAXAssss
Slide 15: Lemming Effect
Lemming Effect Fix: Don’t retry until the lock is free (test-and-test-&-set) T1 --AL------------UX------- T2 ---AsssssssssssssX------- T3 ---AsssssssssssssX------- 15
Slide 16: Initial Results: B+Tree
Initial Results: B+Tree Intel TSX provides significant gains with no application changes Outperforms RW lock on read-only queries Significant gains with increasing inserts (6x for 50%) 10 9 8 7 relative speedup 6 No Concurrency Control 5 Spin Lock Elision w/ TSX 4 RW Lock 3 Spin Lock 2 1 0 0 20
Slide 17: Initial Results: Delta Storage Index
Initial Results: Delta Storage Index Intel TSX provides gains with no application changes Different profile as compared to B+Tree Spin lock w/ Intel TSX better than RW Lock when > 5% insert Significant gap as compared to no concurrency control Baseline should implement good retry policy on abo
Slide 18: Analysis: Delta Storage Index
Analysis: Delta Storage Index Capacity Aborts Algorithmic level Node/Leaf Search Scan Causes O(n) random lookups Cache Associativity Limits Aborts typically before cache size limits Hyper-threads share the L1 cache Dictionary contributes to larger footprint Data Conflicts Single dict
Slide 19: Software Transformations
Software Transformations Capacity Aborts Node/Leaf Search Scan Causes O(n) random lookups Transformation – Binary Search Causes O(log(n)) random lookups Data Conflicts Single dictionary Global memory allocator Transformation – Multiple Dictionaries, per-thread/core allocators Well Know
Slide 20: Tuned Results: Delta Storage Index
Tuned Results: Delta Storage Index Intel TSX provides significant gains with transformations Restores read-only query performance Spin lock w/ Intel TSX significantly outperforms RW lock (5x for 50% inserts) Close to ‘No Concurrency Control” 7 6 relative performance 5 4 No Concurrency Control
Slide 21: Lessons
Lessons Lemming Effect A common but deadly mistake Simple fixes Capacity Limits Best determined by running actual workloads Transient aborts due to associativity Use Analysis Tools and Iterate Optimizations Extensive infrastructure Can pinpoint areas of interest effectively Retry on Abor
Slide 22: Summary
Summary Atomic read-modify-write operations can limit scalability Even for read only transactions using reader-writer locks An often overlooked performance issue Database data structures compelling candidates for Intel TSX SAP HANA Delta Storage Index B+Tree Intel TSX-based lock elision can