Comparison and evaluation of state-of-the-art LSM merge policies
| Autor: | Qizhong Mao, Steven Jacobs, Neal E. Young, Vagelis Hristidis, Vassilis J. Tsotras, Waleed Amjad |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Computer science
Write amplification Distributed computing Aggregate (data warehouse) Merge policy Compaction 020206 networking & telecommunications 02 engineering and technology NoSQL computer.software_genre Data Format Range (mathematics) Hardware and Architecture 020204 information systems 0202 electrical engineering electronic engineering information engineering NoSQL database LSM State (computer science) Distributed Computing Merge (version control) Throughput (business) computer Merge (linguistics) Information Systems |
| Zdroj: | VLDB Journal, vol 30, iss 3 The VLDB Journal, vol 30, iss 3 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|