Partial Tiering: A Hybrid Merge Policy for Log Structured Key-Value Stores

Persistent key-value stores have been widely adopted as a storage engine for modern IT infrastructures because they provide high performance with simple design principles. Moreover, many key-value stores commonly employ LSM-tree as their index structure due to its attractive features such as high write throughput and storage space efficiency. Unfortunately, LSM-tree has critical drawbacks in that it leads to write/read amplification problem. One of the prevalent solutions for remedying the write amplification problem is the tiering merge policy that reduces the number of rewrites by delaying merge operations. However, in spite of this advantage, the tiering merge policy may lead to a side-effect that induces the read amplification that increases search/scan cost for upcoming read operations. In this paper, we concentrate on mitigating the high read amplification problem of the tiering merge policy, while maintaining its low write amplification. To achieve this, we propose Partial Tiering, a novel merge policy which delays merge operations only for the non-read-intensive key-spaces. We have implemented a prototype based on PebblesDB and evaluated the performance benefits of our policy. Experimental results clearly show that our policy improves throughput by up to 1. 50x compared with the conventional policy while maintaining low write amplification.