LSM-tree Storage Engine Write Optimization Design And Implementation Based On LevelDB

With the development of information technology,more data is now being generated every day across industries and applications than ever before.For such massive data,the traditional relational database has been unable to provide efficient services for it,so more and more enterprises use No SQL database to support the data storage and access services of their upper applications.Key-value database is the most common No SQL database,and LSM-tree（Log Structured merge-tree）is the most common storage architecture of key-value database,which is especially good in the scenario of frequent write.However,compared with the b-tree storage architecture of relational database,the read performance is mediocre,and the write amplification problem is more serious due to the merge operation.Aiming at the problem of write magnification,the LSM-tree consolidation scheme was studied and its different optimization methods were analyzed.Based on the common Leveling consolidation scheme and Tiering consolidation scheme,A new Log structured Merge and Append-tree（LSMA-Tree）is proposed.The main idea is to combine the reading advantage of leveling scheme with the writing advantage of tiering scheme.On the one hand,each layer of LSM-tree is like the leveling scheme.The whole key order is maintained by pressing files,that is,the files overlap each other without the scope of keys.On the other hand,when the actual merge occurs,the files at the upper level are "appended" rather than "reorganized",so there is no need to read or write the files at the lower level,thus ensuring that the amount of disk I/O generated by the merge is similar to that of tiering.In order to verify the effectiveness of LSMA,it is implemented on Level DB,Google’s classic LSM-Tree storage engine.A new sstable file structure is designed to match the proposed LSMA,which consists of several original Level DB’s sstable to meet the " appended" feature of LSMA.At the same time,in order to avoid concurrent reading and writing conflicts between the reader and merge threads on the new sstable file,a header is introduced for mutually exclusive access of the index,and the internal structure of the Sstable is improved.And based on the new sstable structure design new read and write mode,cache management,version iteration and so on.Finally,Level DB’s built-in DB＿Bench was used to run a series of comparison tests.Experimental results show that compared with original Level DB,the proposed LSMA scheme can effectively reduce write magnifying and improve the random write performance of storage engine to more than 50% with the increase of storage engine data volume,while the impact on read performance is less than 5%.