Persistent key-value (KV) stores are widely used by cloud services at ByteDance as local storage engines, and RocksDB used to be the de facto implementation since it can be tailored to a variety of workloads and requirements. In this paper, we provide key insights into local storage engine usage at ByteDance, explain why the combination of highly write-intensive workloads and stringent requirements on cost efficiency and point lookup tail latency may pose challenges to a general-purpose local storage engine such as RocksDB, and present the design and implementation of LavaStore , a high-performance cost-effective local storage engine purpose-built to address these challenges. LavaStore achieves its design goals by selectively customizing a few components of a RocksDB-based, general-purpose local storage engine, including a distinct KV separation design that decouples garbage collection from compaction, a specialized engine type for the commonly recurring Write-Ahead-Logging workload, and a customized user-space append-only filesystem. LavaStore has been deployed to production with hundreds of thousands of running instances, storing more than 100 PB of data and serving billions of requests per second, bringing significant performance improvements and cost reductions to customers over their original local storage engines. For example, a ByteDance proprietary distributed OLTP database service has experienced a reduction in average write and read latency by 61% and 16%, respectively, and a ByteDance proprietary caching service has gained an 87% increase in write throughput with no more than 6% space overhead.

The performance of an LSM-tree-based system heavily relies on the compaction strategy employed. Two main categories of compaction strategies exist: leveled and stack-based. Leveled compaction offers several advantages. Firstly, its incremental merge style enables breaking down large compactions into smaller sub-compactions through partitioning. This partitioning enhances parallelism during compaction execution, reduces write stalling, and improves disk utilization. Additionally, for specific workloads like sequential insertions, it allows moving entire files to lower levels without the need for rewriting them, thus saving disk I/O. These moves are known as trivial-moves. On the other hand, stack-based policies typically lack support for these desired properties. Their large compactions either perform no partitioning or rely on naive partitioning methods, resulting in limited opportunities for parallelism and trivial-moves.The goal of this paper is to facilitate the compaction advantages of leveled strategies in stack-based systems, hence creating a hybrid strategy that combines the advantages of both worlds. To achieve this, we propose two novel coordinated partitioning algorithms, namely Local-Range and Global-Range. These algorithms can be applied to any stack-based compaction strategy to enhance parallelism during compactions and create more opportunities for trivial-moves, resulting in improved overall compaction cost. We extend RocksDB to support partitioning on stack-based strategies and conduct a comparative analysis against several baselines using various workloads. The experimental results demonstrate that the Global-Range partitioning method significantly enhances compaction performance with minimal overhead.

The Log-Structured Merge (LSM) Tree has become a popular storage scheme for modern NoSQL and New SQL database systems. The LSM-tree scheme achieves high write throughput by first buffering writes in memory, then flushing them to the disk with sequential I/O. LSM-tree is an out-of-place structure, so the key range of a level in the tree can overlap with those of other levels. This negatively impacts range query performance, as multiple levels have to be scanned. Note that range queries are fundamental operators for other types of queries such as joins or spatiotemporal queries. To improve the read performance of LSM-trees, this paper proposes the Bi-directional LSM-tree, which differs from the classical LSM-tree in that hot records can move to higher levels to improve the overall LSM organization and benefit future range queries. The Bi-directional LSM-tree reuses the work performed during range queries to selectively generate a special type of components, called sentinel components. Our experiments show that the Bi-directional LSM-tree can save more than 10% of disk I/O compared to a standard Leveled LSM-tree.

Abstract Modern NoSQL database systems use log-structured merge (LSM) storage architectures to support high write throughput. LSM architectures aggregate writes in a mutable MemTable (stored in memory), which is regularly flushed to disk, creating a new immutable file called an SSTable. Some of the SSTables are chosen to be periodically merged—replaced with a single SSTable containing their union. A mergepolicy (a.k.a. compaction policy) specifies when to do merges and which SSTables to combine. A bounded depth merge policy is one that guarantees that the number of SSTables never exceeds a given parameter k, typically in the range 3–10. Bounded depth policies are useful in applications where low read latency is crucial, but they and their underlying combinatorics are not yet well understood. This paper compares several bounded depth policies, including representative policies from industrial NoSQL databases and two new ones based on recent theoretical modeling, as well as the standard Tiered policy and Leveled policy. The results validate the proposed theoretical model and show that, compared to the existing policies, the newly proposed policies can have substantially lower write amplification with comparable read amplification.

Spatial indexes in traditional relational databases supported spatial queries in the pre-big data era. However, the volume and ingestion rate of spatial data is increasing rapidly in modern applications. Many big data systems use LSM tree as their storage structure in order to support write-intensive large-volume workloads, which are usually optimized for singledimensional data. Research has studied how to support spatial indexes on LSM systems, but have mainly focused on the local index organization, that is, how data is organized inside a single LSM component. In this paper, we study various aspects of spatial LSM indexing, including spatial merge policies, which determine when and how spatial components are merged. We consider both stack-based and leveled merge policies, which we have implemented on the same big data system. We evaluate the write and read performance on various workloads and discuss our findings and recommendations. A key finding is that Leveled policies are underperforming other merge policies for most types of spatial workloads.

Modern NoSQL databases use log-structured merge (LSM) storage architectures to support high write throughput. LSM architectures aggregate writes in a mutable MemTabte (stored in memory), which is regularly flushed to disk, creating a new immutable file called an SSTable. Periodically, some of the SSTables are chosen to be merged - replaced with a single SSTable containing their union. A merge policy (a.k.a. compaction policy) specifies when to do merges and which SSTables to combine. A bounded depth merge policy is one that guarantees that the number of SSTables never exceeds a given parameter k, typically in the range 3-10. Bounded-depth policies are useful in applications where low read latency is crucial, but they and their underlying combinatorics are not yet well understood. This paper compares several bounded-depth policies, including representative policies from industrial NoSQL databases and two new ones based on recent theoretical modeling. The results validate the proposed theoretical model and show that, compared to the existing policies, the newly proposed policies can have substantially lower write amplification.