Show simple item record

dc.contributor.authorSarkar, Subhadeepen_US
dc.contributor.authorPapon, Tarikul Islamen_US
dc.contributor.authorStaratzis, Dimitrisen_US
dc.contributor.authorAthanassoulis, Manosen_US
dc.date.accessioned2021-05-04T18:26:59Z
dc.date.available2021-05-04T18:26:59Z
dc.date.issued2020-06-13
dc.identifierhttp://arxiv.org/abs/2006.04777v4
dc.identifier.citationSubhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Manos Athanassoulis. "Lethe: A Tunable Delete-Aware LSM Engine (Updated Version)." https://arxiv.org/abs/2006.04777.
dc.identifier.urihttps://hdl.handle.net/2144/42468
dc.description.abstractData-intensive applications fueled the evolution of log structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as a second-class citizen. A delete inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion. Further, LSM engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written. We highlight that fast persistent deletion without affecting read performance is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on the right-to-be-forgotten, and (iii) en masse cloud deployment of data systems that makes storage a precious resource. To address these challenges, in this paper, we build a new key-value storage engine, Lethe, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the sort and the delete key order. We show that Lethe supports any user-defined threshold for the delete persistence latency offering higher read throughput (1.17-1.4×) and lower space amplification (2.1-9.8×), with a modest increase in write amplification (between 4% and 25%). In addition, Lethe supports efficient range deletes on a secondary delete key by dropping entire data pages without sacrificing read performance nor employing a costly full tree merge.en_US
dc.language.isoen_US
dc.titleLethe: a tunable delete-aware LSM engine (updated version)en_US
dc.typeArticleen_US
dc.description.versionFirst author draften_US
pubs.elements-sourcearxiven_US
pubs.notesEmbargo: No embargoen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
dc.identifier.orcid0000-0003-1837-0010 (Athanassoulis, Manos)
dc.identifier.mycv562923


This item appears in the following Collection(s)

Show simple item record