The Forgotten Operator: Delete Tradeoffs in Data Stores

This lecture delves into the tradeoffs involved in delete operations in modern data stores, focusing on logical deletes in structures like b-trees and LSM-trees. The instructor discusses the implications of delete latency on read performance, data privacy, and persistent delete latency. The talk introduces Lethe, a delete-aware LSM-based storage engine, and explores solutions to the inefficiencies faced by LSM-based data stores with deletes. Key concepts covered include log-structured merge-trees, buffer management, and the Key Weaving storage layout. The lecture concludes by comparing the performance of Lethe with existing designs, highlighting its benefits in terms of write amplification, read performance, and space amplification.