More Like this

1. Beating the I/O bottleneck: a case for log-structured virtual disks

   https://doi.org/10.1145/3492321.3524271  

   Hajkazemi, Mohammad Hossein; Aschenbrenner, Vojtech; Abdi, Mania; Kaynar, Emine Ugur; Mossayebzadeh, Amin; Krieger, Orran; Desnoyers, Peter (March 2022, EuroSys '22: Proceedings of the Seventeenth European Conference on Computer Systems)

   With the increasing dominance of SSDs for local storage, today's network mounted virtual disks can no longer offer competitive performance. We propose a Log-Structured Virtual Disk (LSVD) that couples log-structured approaches at both the cache and storage layer to provide a virtual disk on top of S3-like storage. Both cache and backend store are order-preserving, enabling LSVD to provide strong consistency guarantees in case of failure. Our prototype demonstrates that the approach preserves all the advantages of virtual disks, while offering dramatic performance improvements over not only commonly used virtual disks, but the same disks combined with inconsistent (i.e. unsafe) local caching. 

   more » « less
2. Baleen: ML Admission & Prefetching for Flash Caches

   Wong, Daniel Lin-Kit; Wu, Hao; Molder, Carson; Gunasekar, Sathya; Lu, Sathya; Khandkar, Snehal; Sharma, Abhinav; Berger, Daniel S; Beckmann, Nathan; Ganger, Gregory R (February 2024, Usenix)

   Flash caches are used to reduce peak backend load for throughput-constrained data center services, reducing the total number of backend servers required. Bulk storage systems are a large-scale example, backed by high-capacity but low-throughput hard disks, and using flash caches to provide a more cost-effective storage layer underlying everything from blobstores to data warehouses. However, flash caches must address the limited write endurance of flash by limiting the long-term average flash write rate to avoid premature wearout. To do so, most flash caches must use admission policies to filter cache insertions and maximize the workload-reduction value of each flash write. The Baleen flash cache uses coordinated ML admission and prefetching to reduce peak backend load. After learning painful lessons with our early ML policy attempts, we exploit a new cache residency model (which we call episodes) to guide model training. We focus on optimizing for an end-to-end system metric (Disk-head Time) that measures backend load more accurately than IO miss rate or byte miss rate. Evaluation using Meta traces from seven storage clusters shows that Baleen reduces Peak Disk-head Time (and hence the number of backend hard disks required) by 12% over state-of-the-art policies for a fixed flash write rate constraint. Baleen-TCO, which chooses an optimal flash write rate, reduces our estimated total cost of ownership (TCO) by 17%. Code and traces are available at https://www.pdl.cmu.edu/CILES/. 

   more » « less
3. Disco: A Compact Index for LSM-trees

   https://doi.org/10.1145/3709683  

   Zhong, Wenshao; Chen, Chen; Wu, Xingbo; Eriksson, Jakob (February 2025, Proceedings of the ACM on Management of Data)

   Many key-value stores and database systems use log-structured merge-trees (LSM-trees) as their storage engines because of their excellent write performance. However, the read performance of LSM-trees is suboptimal due to the overlapping sorted runs. Most existing efforts rely on filters to reduce unnecessary I/Os, but filters fundamentally do not help locate items and often become the bottleneck of the system. We identify that the lack of efficient index is the root cause of subpar read performance in LSM-trees. In this paper, we propose Disco: a compact index for LSM-trees. Disco indexes all the keys in an LSM-tree, so a query does not have to search every run of the LSM-tree. It records compact key representations to minimize the number of key comparisons so as to minimize cache misses and I/Os for both point and range queries. Disco guarantees that both point queries and seeks issue at most one I/O to the underlying runs, achieving an I/O efficiency close to a B⁺-tree. Disco improves upon REMIX's pioneering multi-run index design with additional compact key representations to help improve read performance. The representations are compact so the cost of persisting Disco to disk is small. Moreover, while a traditional LSM-tree has to choose a more aggressive compaction policy that slows down write performance to have better read performance, a Disco-indexed LSM-tree can employ a write-efficient policy and still have good read performance. Experimental results show that Disco can save I/Os and improve point and range query performance by up to 220% over RocksDB while maintaining efficient writes. 

   more » « less
4. Geometric Hitting Set for Line-Constrained Disks

   https://doi.org/10.1007/978-3-031-38906-1_38  

   Liu, Gang; Wang, Haitao (August 2023, Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023))

   Given a set P of n weighted points and a set S of m disks in the plane, the hitting set problem is to compute a subset 𝑃′ of points of P such that each disk contains at least one point of 𝑃′ and the total weight of all points of 𝑃′ is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line ℓ. We present an 𝑂((𝑚+𝑛)log(𝑚+𝑛)+𝜅log𝑚) time algorithm for the problem, where 𝜅 is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to 𝑂((𝑛+𝑚)log(𝑚+𝑛)). In addition, we solve the problem in 𝑂((𝑚+𝑛)log(𝑚+𝑛)) time in the 𝐿∞ and 𝐿1 metrics, in which a disk is a square and a diamond, respectively. 

   more » « less
5. GearDB: A GC-free Key-Value Store on HM-SMR Drives with Gear Compaction

   Yao, T; Wan, J; Huang, P; Zhang, Y; Liu, Z; Xie, C; He, X. (April 2019, 19th USENIX Conf. on File and Storage Technologies (FAST))

   Host-managed shingled magnetic recording drives (HMSMR) give a capacity advantage to harness the explosive growth of data. Applications where data is sequentially written and randomly read, such as key-value stores based on Log-Structured Merge Trees (LSM-trees), make the HMSMR an ideal solution due to its capacity, predictable performance, and economical cost. However, building an LSMtree based KV store on HM-SMR drives presents severe challenges in maintaining the performance and space efficiency due to the redundant cleaning processes for applications and storage devices (i.e., compaction and garbage collections). To eliminate the overhead of on-disk garbage collections (GC) and improve compaction efficiency, this paper presents GearDB, a GC-free KV store tailored for HMSMR drives. GearDB proposes three new techniques: a new on-disk data layout, compaction windows, and a novel gear compaction algorithm. We implement and evaluate GearDB with LevelDB on a real HM-SMR drive. Our extensive experiments have shown that GearDB achieves both good performance and space efficiency, i.e., on average 1:71 faster than LevelDB in random write with a space efficiency of 89.9%. 

   more » « less