{"id":15,"date":"2020-06-29T12:39:18","date_gmt":"2020-06-29T16:39:18","guid":{"rendered":"http:\/\/blogs.bu.edu\/mathan\/?p=15"},"modified":"2020-07-01T14:13:58","modified_gmt":"2020-07-01T18:13:58","slug":"lets-talk-about-deletes","status":"publish","type":"post","link":"https:\/\/blogs.bu.edu\/mathan\/2020\/06\/29\/lets-talk-about-deletes\/","title":{"rendered":"Let’s talk about deletes!"},"content":{"rendered":"

In the recent SIGMOD, we presented our work on a delete-aware LSM-based system<\/a> called Lethe<\/em><\/a>. In this post, I would like to share a few details that could not make it to the talk along with some thoughts based on the feedback we received during the conference.<\/p>\n

First, this year is probably the first time that deletes<\/strong><\/em> were discussed as a key research challenge,\u00a0as part of database systems offering privacy through deletion. <\/strong>Specifically,\u00a0Mike Stonebraker<\/a>\u00a0discussed it during the very interesting panel “The Next 5 Years: What Opportunities Should the Database Community Seize to Maximize its Impact?<\/em>“. Along with our work on deletes for LSM-trees, this is probably the first time that deleting data<\/em><\/strong> becomes a first-class citizen. Up to now, we mostly worried about how to keep all the data we collected or generated. <\/strong>Today, we also have to worry about how to efficiently delete<\/strong> them if we have to (e.g., because of GDPR<\/a>).<\/p>\n

When studying the delete operator of modern data stores, we realized that virtually all deletes are out-of-place<\/strong>, even in the so-called in-place systems. For example, even when deleting in a B+ Tree or a heap file (which uses slotted pages) the most common approach is to invalidate the entry via a valid bit<\/strong>\u00a0and\u00a0leave the invalid data there for future “cleaning”. To highlight this point, consider that\u00a0often practical implementations of B+ Trees in full-blown relational systems do not even perform the merge after the case of underflowing due to a delete, because they expect new inserts to grow the tree in the future. Of course, this approach is further pronounced in LSM trees<\/strong> where a delete is implemented by design via\u00a0out-of-place invalidation<\/strong>. In other words, in systems up to now, deletes are an afterthought, something that we may have to do, but we don’t really worry too much about optimizing it (notable exceptions about optimizing the latency of bulk deletes are “Efficient Bulk Deletes for Multi-Dimensional Clustered Tables in DB2<\/a>“, “Efficient bulk deletes in relational databases<\/a>” and “Online Bulk Deletion<\/a>“, however, they still do not focus on\u00a0other aspects of deletes like privacy and space amplification).\u00a0In addition to the efficiency of deletion<\/strong>\u00a0and privacy<\/strong>, the\u00a0new ubiquitous use of the cloud for data management\u00a0poses a space management challenge<\/strong>. If one owns a disk, then invalidating data does not cause extra costs unless they have to buy new disks. On the other hand, if one rents storage from a cloud provider, keeping around invalidated data for long leads to unnecessary storage costs.<\/p>\n

Moving back to performing out-of-place deletes, we observe that essentially, the purging of the data (which we call persistent deletion<\/strong>) is left as a task for later which will be undertaken by a compaction<\/strong>\/garbage collection<\/strong>\/defragmentation<\/strong> process depending on the exact system used. Leaving the persistent deletion for later may lead to a significant increase of space amplification and may expose sensitive deleted data (which technically should not be accessible after their deletion) increasing the privacy risk. These risks and costs are further pronounced in LSM systems where the garbage collection process is part of the original design.<\/p>\n

Diving into more details about deletes on LSM-based data stores<\/strong> (LSM was originally introduced by ONeil in 1996<\/a>, popularized by Google’s Bigtable<\/a> and LevelDB<\/a>, as well as Facebook’s RocksDB<\/a>\u00a0– a LevelDB fork, and since then is being used by a\u00a0variety of systems – a\u00a0great survey is available by Luo and Carey<\/a>), we first realized that an LSM can receive four\u00a0different types of deletes:<\/p>\n