Performance Optimization Of KV Storage Based On LSM-tree

Key-Value store based on the Log-Structure Merge-tree provides service for dataintensive applications.LSM-tree achieves high write performance because it takes advantage of the fact that the sequential write speed of the disk is higher than the random write speed.LSM-tree is a multi-level structure that requires compaction to organize its data.However,compaction causes the cache invalidation because data addresses are changed on the disk.In addition,the compaction also causes write amplification,which severely affects the write performance of the LSM-tree.This article proposes the following solutions to the above two problems:1)The dual-grained cache is proposed to alleviate the jitter of read performance caused by compaction.The compaction changes the addresses of data on the disk,which makes the data stored in the cache invalid,resulting in the jitter of read performance.However,the compaction is the key operation to maintain LSM-tree and recycle the old key value pairs.This paper analyzes the frequency of compaction in different levels of the LSM-tree and uses a dual-grained cache to alleviate the jitter of read performance.The dual-grained cache is divided into a coarse-grained cache and a fine-grained cache,which cache different grained data respectively.The coarse-grained cache caches the data blocks.The fine-grained cache caches recently accessed key value pairs.Performance evaluation shows that the dual-grained cache can greatly improve the read performance of LSM-tree by 25% to 200%.2)We build a read-write buffer using NVM's characteristics of byte addressable,non-volatile and large capacity.An LSM-tree contains multiple levels and the size of each level increases exponentially with its depth,so the cost of compaction in different levels is also different.If the update operation is completed in the upper level of LSMtree as mush as possible,the amount of data written to the lower level can be reduced.The read-write buffer can take advantage of the skew feature of the workload to complete the update operation in NVM.In addition,the data in the read-write buffer is separated by the Sketch algorithm to keep the frequently updated key value pairs in the read-write buffer.This method effectively reduces the write amplification.Experiments show that the read-write buffer and Sketch algorithm can improve the write performance by 30%.