Real-Time LSM-Trees for HTAP Workloads

Real-time analytics systems employ hybrid data layouts in which data are stored in different formats throughout their lifecycle. Recent data are stored in a row-oriented format to serve OLTP workloads and support high insert rates, while older data are transformed to a column-oriented format for OLAP access patterns. We observe that a Log-Structured Merge (LSM) Tree is a natural fit for a lifecycle-aware storage engine due to its high write throughput and level-oriented structure, in which records propagate from one level to the next over time. To build a lifecycle-aware storage engine using an LSM-Tree, we make a crucial modification to allow different data layouts in different levels, ranging from purely row-oriented to purely column-oriented, leading to a Real-Time LSM-Tree. We give a cost model and an algorithm to design a Real-Time LSM-Tree that is suitable for a given workload, followed by an experimental evaluation of LASER -a prototype implementation of our idea built on top of the RocksDB key-value store.

• We propose the Real-Time LSM-Tree, which extends the traditional LSM-Tree with the ability to store data in a row-oriented or a column-oriented format in each level.

• We characterize the design space of possible Real-Time LSM-Trees. To navigate this design space, we provide a cost model to select good designs for a given workload.

• We develop and evaluate LASER, a Lifecycle-Aware Storage Engine for Real-time analytics based on Real-Time LSM-Trees. We implement LASER using RocksDB, which is a popular opensource key-value store based on LSM-Trees.

Compared to traditional read-optimized data structures such as B-trees, LSM-Trees focus on high write throughput while allowing indexed access to data [26]. LSM-Trees have two components: an in-memory piece that buffers inserts and a secondary storage piece.