Don't Persist All : Efficient Persistent Data Structures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918112703545344 |
|---|---|
| author | Mahapatra, Pratyush Hill, Mark D. Swift, Michael M. |
| author_facet | Mahapatra, Pratyush Hill, Mark D. Swift, Michael M. |
| contents | Data structures used in software development have inbuilt redundancy to improve software reliability and to speed up performance. Examples include a Doubly Linked List which allows a faster deletion due to the presence of the previous pointer. With the introduction of Persistent Memory, storing the redundant data fields into persistent memory adds a significant write overhead, and reduces performance. In this work, we focus on three data structures - Doubly Linked List, B+Tree and Hashmap, and showcase alternate partly persistent implementations where we only store a limited set of data fields to persistent memory. After a crash/restart, we use the persistent data fields to recreate the data structures along with the redundant data fields. We compare our implementation with the base implementation and show that we achieve speedups around 5-20% for some data structures, and up to 165% for a flush-dominated data structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1905_13011 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Don't Persist All : Efficient Persistent Data Structures Mahapatra, Pratyush Hill, Mark D. Swift, Michael M. Databases Hardware Architecture Data Structures and Algorithms Performance Data structures used in software development have inbuilt redundancy to improve software reliability and to speed up performance. Examples include a Doubly Linked List which allows a faster deletion due to the presence of the previous pointer. With the introduction of Persistent Memory, storing the redundant data fields into persistent memory adds a significant write overhead, and reduces performance. In this work, we focus on three data structures - Doubly Linked List, B+Tree and Hashmap, and showcase alternate partly persistent implementations where we only store a limited set of data fields to persistent memory. After a crash/restart, we use the persistent data fields to recreate the data structures along with the redundant data fields. We compare our implementation with the base implementation and show that we achieve speedups around 5-20% for some data structures, and up to 165% for a flush-dominated data structure. |
| title | Don't Persist All : Efficient Persistent Data Structures |
| topic | Databases Hardware Architecture Data Structures and Algorithms Performance |
| url | https://arxiv.org/abs/1905.13011 |