More Like this

1. The LSM RUM-Tree: A Log Structured Merge R-Tree for Update-intensive Spatial Workloads

   https://doi.org/10.1109/ICDE51399.2021.00238  

   Shin, Jaewoo; Wang, Jianguo; Aref, Walid G. (April 2021, 2021 IEEE 37th International Conference on Data Engineering (ICDE))

   null (Ed.)

   Many applications require update-intensive work-loads on spatial objects, e.g., social-network services and shared-riding services that track moving objects (devices). By buffering insert and delete operations in memory, the Log Structured Merge Tree (LSM) has been used widely in various systems because of its ability to handle insert-intensive workloads. While the focus on LSM has been on key-value stores and their optimizations, there is a need to study how to efficiently support LSM-based secondary indexes. We investigate the augmentation of a main-memory-based memo structure into an LSM secondary index structure to handle update-intensive workloads efficiently. We conduct this study in the context of an R-tree-based secondary index. In particular, we introduce the LSM RUM-tree that demonstrates the use of an Update Memo in an LSM-based R-tree to enhance the performance of the R-tree's insert, delete, update, and search operations. The LSM RUM-tree introduces novel strategies to reduce the size of the Update Memo to be a light-weight in-memory structure that is suitable for handling update-intensive workloads without introducing significant over-head. Experimental results using real spatial data demonstrate that the LSM RUM-tree achieves up to 9.6x speedup on update operations and up to 2400x speedup on query processing over the existing LSM R-tree implementations. 

   more » « less
2. Verifying Lock-Free Search Structure Templates

   https://doi.org/10.4230/LIPIcs.ECOOP.2024.30  

   Patel, Nisarg; Shasha, Dennis; Wies, Thomas (September 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aldrich, Jonathan; Salvaneschi, Guido (Ed.)

   We present and verify template algorithms for lock-free concurrent search structures that cover a broad range of existing implementations based on lists and skiplists. Our linearizability proofs are fully mechanized in the concurrent separation logic Iris. The proofs are modular and cover the broader design space of the underlying algorithms by parameterizing the verification over aspects such as the low-level representation of nodes and the style of data structure maintenance. As a further technical contribution, we present a mechanization of a recently proposed method for reasoning about future-dependent linearization points using hindsight arguments. The mechanization builds on Iris' support for prophecy reasoning and user-defined ghost resources. We demonstrate that the method can help to reduce the proof effort compared to direct prophecy-based proofs. 

   more » « less
3. Towards flexibility and robustness of LSM trees

   https://doi.org/10.1007/s00778-023-00826-9  

   Huynh, Andy; Chaudhari, Harshal_A; Terzi, Evimaria; Athanassoulis, Manos (January 2024, The VLDB Journal)

   Abstract Log-structured merge trees (LSM trees) are increasingly used as part of the storage engine behind several data systems, and are frequently deployed in the cloud. As the number of applications relying on LSM-based storage backends increases, the problem of performance tuning of LSM trees receives increasing attention. We consider bothnominaltunings—where workload and execution environment are accurately known a priori—androbusttunings—which consideruncertaintyin the workload knowledge. This type of workload uncertainty is common in modern applications, notably in shared infrastructure environments like the public cloud. To address this problem, we introduceEndure, a new paradigm for tuning LSM trees in the presence of workload uncertainty. Specifically, we focus on the impact of the choice of compaction policy, size ratio, and memory allocation on the overall performance.Endureconsiders a robust formulation of the throughput maximization problem and recommends a tuning that offers near-optimal throughput when the executed workload is not the same, instead in aneighborhoodof the expected workload. Additionally, we explore the robustness of flexible LSM designs by proposing a new unified design called K-LSM that encompasses existing designs. We deploy our robust tuning system,Endure, on a state-of-the-art key-value store, RocksDB, and demonstrate throughput improvements of up to 5$$\times $$ $\times$in the presence of uncertainty. Our results indicate that the tunings obtained byEndureare more robust than tunings obtained under our expanded LSM design space. This indicates that robustness may not be inherent to a design, instead, it is an outcome of a tuning process that explicitly accounts for uncertainty. 

   more » « less
4. A Shared-Memory Algorithm for Updating Tree-Based Properties of Large Dynamic Networks

   https://doi.org/10.1109/TBDATA.2018.2870136  

   Srinivasan, Sriram; Pollard, Samuel; Das, Sajal K.; Norris, Boyana; Bhowmick, Sanjukta (September 2018, IEEE Transactions on Big Data)

   In this paper, we present a network-based template for analyzing large-scale dynamic data. Specifically, we present a novel shared-memory parallel algorithm for updating treebased structures, including connected components (CC) and the minimum spanning tree (MST) on dynamic networks. We propose a rooted tree-based data structure to store the edges that are most relevant to the analysis. Our algorithm is based on updating the information stored in this rooted tree.In this paper, we present a network-based template for analyzing large-scale dynamic data. Specifically, we present a novel shared-memory parallel algorithm for updating tree-based structures, including connected components (CC) and the minimum spanning tree (MST) on dynamic networks. We propose a rooted tree-based data structure to store the edges that are most relevant to the analysis. Our algorithm is based on updating the information stored in this rooted tree. 

   more » « less
5. Write-Optimized Skip Lists

   https://doi.org/10.1145/3034786.3056117  

   Bender, Michael; Farach-Colton, Martin; Johnson, Rob; Mauras, Simon; Mayer, Tyler; Phillips, Cynthia; Xu, Helen (January 2017, PODS '17 Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems)

   The skip list is an elegant dictionary data structure that is com- monly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(logN) operations with high probability (w.h.p.) and range queries returning K elements in O(log N + K) operations w.h.p. A seemingly natural way to generalize the skip list to external memory with block size B is to “promote” with probability 1/B, rather than 1/2. However, there are practical and theoretical obsta- cles to getting the skip list to retain its efficient performance, space bounds, and high-probability guarantees. We give an external-memory skip list that achieves write- optimized bounds. That is, for 0 < ε < 1, range queries take O(logBε N + K/B) I/Os w.h.p. and insertions and deletions take O((logBε N)/B1−ε) amortized I/Os w.h.p. Our write-optimized skip list inherits the virtue of simplicity from RAM skip lists. Moreover, it matches or beats the asymptotic bounds of prior write-optimized data structures such as Bε trees or LSM trees. These data structures are deployed in high-performance databases and file systems. 

   more » « less