Flutist: Parallelizing Transaction Processing for LSM-Tree-Based Relational Database

Log-structured merge tree (LSM-tree) is a promising structure. LSM-tree-based relational databases gain wide popularity in production environments to serve web and big data applications. We take MyRocks for study and explore how to optimize it in handling transactions that concurrent clients issue. Our quantitative study shows that MyRocks severely suffers from the sequential commits of transactions with RocksDB. We accordingly propose an algorithm named Flutist. Flutist employs a holistic strategy to explicitly encode and pass the committing order information across layers of MyRocks. Leveraging such information, Flutist parallelizes transaction processing through concurrent commits with RocksDB and preserves a desired committing order. Experiments confirm that Flutist achieves high performance and portability. Its throughput is up to 5.1 \(\times \) and 5.4 \(\times \) that of MyRocks and state-of-the-art PASV, respectively.