More Web Proxy on the site http://driver.im/

research-article

Using restricted transactional memory to build a scalable in-memory database

Authors:

Haibo ChenAuthors Info & Claims

EuroSys '14: Proceedings of the Ninth European Conference on Computer Systems

Article No.: 26, Pages 1 - 15

https://doi.org/10.1145/2592798.2592815

Published: 14 April 2014 Publication History

Abstract

The recent availability of Intel Haswell processors marks the transition of hardware transactional memory from research toys to mainstream reality. DBX is an in-memory database that uses Intel's restricted transactional memory (RTM) to achieve high performance and good scalability across multi-core machines. The main limitation (and also key to practicality) of RTM is its constrained working set size: an RTM region that reads or writes too much data will always be aborted. The design of DBX addresses this challenge in several ways. First, DBX builds a database transaction layer on top of an underlying shared-memory store. The two layers use separate RTM regions to synchronize shared memory access. Second, DBX uses optimistic concurrency control to separate transaction execution from its commit. Only the commit stage uses RTM for synchronization. As a result, the working set of the RTMs used scales with the meta-data of reads and writes in a database transaction as opposed to the amount of data read/written. Our evaluation using TPC-C workload mix shows that DBX achieves 506,817 transactions per second on a 4-core machine.

References

[1]

D. Batoory, J. Barnett, J. F. Garza, K. P. Smith, K. Tsukuda, B. Twichell, and T. Wise. GENESIS: An extensible database management system. IEEE Transactions on Software Engineering, 14(11):1711--1730, 1988.

Digital Library

[2]

C. Blundell, E. C. Lewis, and M. M. Martin. Subtleties of transactional memory atomicity semantics. Computer Architecture Letters, 5(2):17--17, 2006.

Digital Library

[3]

P. A. Boncz. Monet; a next-Generation DBMS Kernel For Query-Intensive Applications. 2002.

[4]

S. Chaudhry, R. Cypher, M. Ekman, M. Karlsson, A. Landin, S. Yip, H. Zeffer, and M. Tremblay. Rock: A high-performance SPARC CMT processor. Micro, IEEE, 29(2): 6--16, 2009.

Digital Library

[5]

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In Proc. SoCC, pages 143--154. ACM, 2010.

Digital Library

[6]

L. Dalessandro, F. Carouge, S. White, Y. Lev, M. Moir, M. L. Scott, and M. F. Spear. Hybrid norec: A case study in the effectiveness of best effort hardware transactional memory. In Proc. ASPLOS, pages 39--52, 2011.

Digital Library

[7]

C. Diaconu, C. Freedman, E. Ismert, P.-A. Larson, P. Mittal, R. Stonecipher, N. Verma, and M. Zwilling. Hekaton: SQL Servers memory-optimized OLTP engine. In Proc. SIGMOD, 2013.

Digital Library

[8]

D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Distributed Computing, pages 194--208. Springer, 2006.

Digital Library

[9]

D. Dice, Y. Lev, M. Moir, D. Nussbaum, and M. Olszewski. Early experience with a commercial hardware transactional memory implementation. In Proc. ASPLOS, 2009.

Digital Library

[10]

D. Dice, Y. Lev, V. J. Marathe, M. Moir, D. Nussbaum, and M. Olszewski. Simplifying concurrent algorithms by exploiting hardware transactional memory. In Proc. SPAA, pages 325--334. ACM, 2010.

Digital Library

[11]

D. Dice, Y. Lev, Y. Liu, V. Luchangco, and M. Moir. Using hardware transactional memory to correct and simplify and readers-writer lock algorithm. In Proc. PPoPP, pages 261--270, 2013.

Digital Library

[12]

K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Comm. of the ACM, 19(11):624--633, 1976.

Digital Library

[13]

M. Fomitchev and E. Ruppert. Lock-free linked lists and skip lists. In Proc. PODC, 2004.

Digital Library

[14]

H. Garcia-Molina and K. Salem. Main memory database systems: An overview. IEEE Transactions on Knowledge and Data Engineering, 4(6):509--516, 1992.

Digital Library

[15]

T. E. Hart, P. E. McKenney, and A. D. Brown. Making lockless synchronization fast: Performance implications of memory reclamation. In Proc. IPDPS. IEEE, 2006.

Digital Library

[16]

M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proc. ISCA, 1993.

Digital Library

[17]

IBM. IBM solidDB. http://www-01.ibm.com/software/data/soliddb/.

[18]

R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and B. Falsafi. Shore-MT: a scalable storage manager for the multicore era. In Proc. EDBT, pages 24--35. ACM, 2009.

Digital Library

[19]

R. Kallman, H. Kimura, J. Natkins, A. Pavlo, A. Rasin, S. Zdonik, E. P. Jones, S. Madden, M. Stonebraker, Y. Zhang, et al. H-store: a high-performance, distributed main memory transaction processing system. Proc. VLDB, 1(2):1496--1499, 2008.

Digital Library

[20]

A. Kemper and T. Neumann. HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. In Proc. ICDE, pages 195--206, 2011.

Digital Library

[21]

H.-T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM TODS, 6(2):213--226, 1981.

Digital Library

[22]

P.-Å. Larson, S. Blanas, C. Diaconu, C. Freedman, J. M. Patel, and M. Zwilling. High-performance concurrency control mechanisms for main-memory databases. In Proc. VLDB, pages 298--309, 2011.

Digital Library

[23]

P. L. Lehman et al. Efficient locking for concurrent operations on B-trees. ACM TODS, 6(4):650--670, 1981.

Digital Library

[24]

V. Leis, A. Kemper, and T. Neumann. Exploiting Hardware Transactional Memory in Main-Memory Databases. In Proc. ICDE, 2014.

[25]

B. Lindsay, J. McPherson, and H. Pirahesh. A data management extension architecture. In Proc. SIGMOD, pages 220--226, 1987.

Digital Library

[26]

R. Liu and H. Chen. SSMalloc: A Low-latency, Locality-conscious Memory Allocator with Stable Performance Scalability. In Proc. APSys, 2012.

Digital Library

[27]

M. Mammarella, S. Hovsepian, and E. Kohler. Modular data storage with Anvil. In Proc. SOSP, pages 147--160, 2009.

Digital Library

[28]

Y. Mao, E. Kohler, and R. T. Morris. Cache craftiness for fast multicore key-value storage. In Proc. EuroSys, pages 183--196, 2012.

Digital Library

[29]

A. Matveev and N. Shavit. Reduced hardware transactions: a new approach to hybrid transactional memory. In Proc. SPAA, pages 11--22. ACM, 2013.

Digital Library

[30]

C. Mohan. ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. In Proc. VLDB, pages 392--405, 1990.

Digital Library

[31]

A. Pavlo, C. Curino, and S. Zdonik. Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. In Proc. SIGMOD, pages 61--72. ACM, 2012.

Digital Library

[32]

R. Rajwar and J. R. Goodman. Speculative lock elision: Enabling highly concurrent multithreaded execution. In Proc. MICRO, pages 294--305, 2001.

Digital Library

[33]

R. Sears and E. Brewer. Stasis: flexible transactional storage. In Proc. OSDI, pages 29--44, 2006.

Digital Library

[34]

S. Sen and R. E. Tarjan. Deletion without rebalancing in balanced binary trees. In Proc. SODA, pages 1490--1499, 2010.

Digital Library

[35]

M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era:(it's time for a complete rewrite). In Proc. VLDB, pages 1150--1160, 2007.

Digital Library

[36]

T. Subasu and J. Alonso. Database engines on multicores, why parallelize when you can distribute. In Proc. Eurosys, 2011.

Digital Library

[37]

The Transaction Processing Council. TPC-CBenchmark (Revision 5.9.0). http://www.tpc.org/tpcc/, 2007.

[38]

A. Thomson and D. J. Abadi. Modularity and Scalability in Calvin. IEEE Data Engineering Bulletin, page 48, 2013.

[39]

C. TimesTen Team. In-memory data management for consumer transactions the timesten approach. ACM SIGMOD Record, 28(2):528--529, 1999.

Digital Library

[40]

K. Q. Tran, S. Blanas, and J. F. Naughton. On Transactional Memory, Spinlocks, and Database Transactions. In Proc. Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures, 2010.

[41]

S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy Transactions in Multicore In-Memory Databases. In Proc. SOSP, 2013.

Digital Library

[42]

L. VoltDB. Voltdb technical overview, 2010.

[43]

Z. Wang, H. Qian, H. Chen, and J. Li. Opportunities and pitfalls of multi-core scaling using hardware transaction memory. In Proc. Apsys. ACM, 2013.

Digital Library

Cited By

Chen RWei XXie XChen H(2024)Locality-Preserving Graph Traversal With Split Live MigrationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.343682835:10(1810-1825)Online publication date: Oct-2024
https://doi.org/10.1109/TPDS.2024.3436828
Qiao PZhang ZLi YYuan YWang SWang GYu J(2024)AStore: Uniformed Adaptive Learned Index and Cache for RDMA-enabled Key-Value StoreIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.3355100(1-18)Online publication date: 2024
https://doi.org/10.1109/TKDE.2024.3355100
Zhang BZheng SNie LQi ZHuang LMei H(2024)Exploiting Persistent CPU Cache for Scalable Persistent Hash Index2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00295(3851-3864)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00295
Show More Cited By

Recommendations

Transactional memory: from semantics to silicon
IWMSE '08: Proceedings of the 1st international workshop on Multicore software engineering

Multi-core architectures bring parallel programming into the mainstream. Parallel programming poses many new challenges to the developer, one of which is synchronizing concurrent access to shared memory by multiple threads. Programmers have ...
Unbounded page-based transactional memory
Proceedings of the 2006 ASPLOS Conference

Exploiting thread level parallelism is paramount in the multicore era. Transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. Virtualized transactions (unbounded in space and time) are ...
Stretching transactional memory
PLDI '09

Transactional memory (TM) is an appealing abstraction for programming multi-core systems. Potential target applications for TM, such as business software and video games, are likely to involve complex data structures and large transactions, requiring ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '14: Proceedings of the Ninth European Conference on Computer Systems

April 2014

388 pages

ISBN:9781450327046

DOI:10.1145/2592798

General Chairs:
Dick Bultermann
CWI
,
Herbert Bos
Vrije Universiteit Amsterdam
,
Program Chairs:
Ant Rowstron
Microsoft Research Cambridge
,
Peter Druschel
MPI SWS

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 April 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

National Research Foundation-Prime Minister's office, Republic of Singapore
Division of Computer and Network Systems
Intel Corporation
Changjiang Scholar Program of Chinese Ministry of Education
Author of National Excellent Doctoral Dissertation of PR China foundation
National Natural Science Foundation of China
Science and Technology Commission of Shanghai Municipality

Conference

EuroSys 2014

Sponsor:

SIGOPS

EuroSys 2014: Ninth Eurosys Conference 2014

April 14 - 16, 2014

Amsterdam, The Netherlands

Acceptance Rates

EuroSys '14 Paper Acceptance Rate 27 of 147 submissions, 18%;

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
1,029
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)5

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen RWei XXie XChen H(2024)Locality-Preserving Graph Traversal With Split Live MigrationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.343682835:10(1810-1825)Online publication date: Oct-2024
https://doi.org/10.1109/TPDS.2024.3436828
Qiao PZhang ZLi YYuan YWang SWang GYu J(2024)AStore: Uniformed Adaptive Learned Index and Cache for RDMA-enabled Key-Value StoreIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.3355100(1-18)Online publication date: 2024
https://doi.org/10.1109/TKDE.2024.3355100
Zhang BZheng SNie LQi ZHuang LMei H(2024)Exploiting Persistent CPU Cache for Scalable Persistent Hash Index2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00295(3851-3864)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00295
Han SZhang MJiang DXiong JGilad YKostic DMoatti YBiran O(2023)Exploiting Hybrid Index Scheme for RDMA-based Key-Value StoresProceedings of the 16th ACM International Conference on Systems and Storage10.1145/3579370.3594768(49-59)Online publication date: 5-Jun-2023
https://dl.acm.org/doi/10.1145/3579370.3594768
Zhu BHua YLong ZLiu X(2023)CATS: A Computation-Aware Transaction Processing System with Proactive Unlocking2023 IEEE/ACM 31st International Symposium on Quality of Service (IWQoS)10.1109/IWQoS57198.2023.10188780(1-10)Online publication date: 19-Jun-2023
https://doi.org/10.1109/IWQoS57198.2023.10188780
Zhang RBond MZhang YEgger BSmith A(2022)Cape: compiler-aided program transformation for HTM-based cache side-channel defenseProceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction10.1145/3497776.3517778(181-193)Online publication date: 19-Mar-2022
https://dl.acm.org/doi/10.1145/3497776.3517778
Shen WKhanna AAngel SSen SMu SBromberg YKermarrec AKozyrakis C(2022)RolisProceedings of the Seventeenth European Conference on Computer Systems10.1145/3492321.3519561(69-84)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1145/3492321.3519561
Yao ZChen RZang BChen H(2022)Wukong+G: Fast and Concurrent RDF Query Processing Using RDMA-Assisted GPU Graph ExplorationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.312156833:7(1619-1635)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TPDS.2021.3121568
Huang YQian WKohler ELiskov BShrira L(2022)Opportunities for optimism in contended main-memory multicore transactionsThe VLDB Journal10.1007/s00778-021-00719-931:6(1239-1261)Online publication date: 11-Jan-2022
https://doi.org/10.1007/s00778-021-00719-9
Wei XChen RChen HZang B(2021) XStore: Fast RDMA-Based Ordered Key-Value Store Using Remote Learned CacheACM Transactions on Storage10.1145/346852017:3(1-32)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1145/3468520
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents