Performant almost-latch-free data structures using epoch protection in more depth
Multi-core scalability presents a major implementation challenge for data system designers today. Traditional methods such as latching no longer scale in today’s highly parallel architectures. While the designer can make use of techniques such as latch-free programming to painstakingly design specia...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Science and Business Media LLC
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155305 |
| _version_ | 1824458204413689856 |
|---|---|
| author | Li, Tianyu Chandramouli, Badrish Madden, Samuel |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Li, Tianyu Chandramouli, Badrish Madden, Samuel |
| author_sort | Li, Tianyu |
| collection | MIT |
| description | Multi-core scalability presents a major implementation challenge for data system designers today. Traditional methods such as latching no longer scale in today’s highly parallel architectures. While the designer can make use of techniques such as latch-free programming to painstakingly design specialized, highly-performant solutions, such solutions are often intricate to build and difficult to reason about. Of particular interest to data system designers is a class of data structures we call almost-latch-free; such data structures can be made scalable in the common case, but have rare complications (e.g., dynamic resizing) that prevent full latch-free implementations. In this work, we present a new programming framework called Epoch-Protected Version Scheme (EPVS) to make it easy to build such data structures. EPVS makes use of epoch protection to preserve performance in the common case of latch-free operations, while allowing users to specify critical sections that execute under mutual exclusion for the rare, non-latch-free operations. We showcase the use of EPVS-based concurrency primitives in a few practical systems to demonstrate its competitive performance and intuitive guarantees. EPVS is available in open source as part of Microsoft’s FASTER project (Epoch Protected Version Scheme (source code) 2022; Microsoft FASTER 2022). |
| first_indexed | 2024-09-23T13:11:28Z |
| format | Article |
| id | mit-1721.1/155305 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:22:10Z |
| publishDate | 2024 |
| publisher | Springer Science and Business Media LLC |
| record_format | dspace |
| spelling | mit-1721.1/1553052025-01-07T04:40:41Z Performant almost-latch-free data structures using epoch protection in more depth Li, Tianyu Chandramouli, Badrish Madden, Samuel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Multi-core scalability presents a major implementation challenge for data system designers today. Traditional methods such as latching no longer scale in today’s highly parallel architectures. While the designer can make use of techniques such as latch-free programming to painstakingly design specialized, highly-performant solutions, such solutions are often intricate to build and difficult to reason about. Of particular interest to data system designers is a class of data structures we call almost-latch-free; such data structures can be made scalable in the common case, but have rare complications (e.g., dynamic resizing) that prevent full latch-free implementations. In this work, we present a new programming framework called Epoch-Protected Version Scheme (EPVS) to make it easy to build such data structures. EPVS makes use of epoch protection to preserve performance in the common case of latch-free operations, while allowing users to specify critical sections that execute under mutual exclusion for the rare, non-latch-free operations. We showcase the use of EPVS-based concurrency primitives in a few practical systems to demonstrate its competitive performance and intuitive guarantees. EPVS is available in open source as part of Microsoft’s FASTER project (Epoch Protected Version Scheme (source code) 2022; Microsoft FASTER 2022). 2024-06-25T20:44:26Z 2024-06-25T20:44:26Z 2024-06-17 2024-06-23T03:16:37Z Article http://purl.org/eprint/type/JournalArticle 1066-8888 0949-877X https://hdl.handle.net/1721.1/155305 Li, T., Chandramouli, B. & Madden, S. Performant almost-latch-free data structures using epoch protection in more depth. The VLDB Journal (2024). PUBLISHER_CC en 10.1007/s00778-024-00859-8 The VLDB Journal Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Science and Business Media LLC Springer Berlin Heidelberg |
| spellingShingle | Li, Tianyu Chandramouli, Badrish Madden, Samuel Performant almost-latch-free data structures using epoch protection in more depth |
| title | Performant almost-latch-free data structures using epoch protection in more depth |
| title_full | Performant almost-latch-free data structures using epoch protection in more depth |
| title_fullStr | Performant almost-latch-free data structures using epoch protection in more depth |
| title_full_unstemmed | Performant almost-latch-free data structures using epoch protection in more depth |
| title_short | Performant almost-latch-free data structures using epoch protection in more depth |
| title_sort | performant almost latch free data structures using epoch protection in more depth |
| url | https://hdl.handle.net/1721.1/155305 |
| work_keys_str_mv | AT litianyu performantalmostlatchfreedatastructuresusingepochprotectioninmoredepth AT chandramoulibadrish performantalmostlatchfreedatastructuresusingepochprotectioninmoredepth AT maddensamuel performantalmostlatchfreedatastructuresusingepochprotectioninmoredepth |