Design And Implementation Of Storage System Based On The Log-Structured Merge-Tree

With the rapid development of the Internet,all aspects of people's lives are inseparable from the Internet.While enjoying the convenience of the Internet,people also make the Internet data grow rapidly.How to quickly query and store huge amounts of data has become the focus of people's research,which makes the NoSql database develop rapidly.A typical stored form of Nosql data is Key-Value Store,that is one key corresponds to one value.A Key-Value storage system can be understood as a hash table with large capacity that can be persisted.The most important part of the storage system is the storage engine.In this thesis,the research is mainly on the most polular storage engine of Key-Value Store which is the LSM-Tree storage engine.The core idea of the storage engine based on the LSM-Tree is sequential writing,and the modified data is sorted and stored in the memory.After reaching a certain scale,the modified data in the memory is written to the disk in batches,and in the process of writing.The existing disk data is merged,and the old Key-Value data is discarded during the merging process.The most serious problem with the LSMTree is that the disk I/O overhead generated by the merging operation greatly affects the writing performance.In severe cases,the writing speed depends on the merging speed.The purpose of this thesis is to solve the problem of writing amplification of the LSMTree,improve the merging efficiency,and improve the writing performance of the LSMTree.Compared with the traditional implementation of LSM-Tree,this thesis adds a layer of index and sotres key and value separately.The key is followed by the address where the value is located,which is called the value index,so as to avoid the value participating in the merging and compressing,thereby reducing the disk I/O overhead caused by the merging and improving the merging speed.The key and value are stored separately under the premise of sacrificing some reading performance,which greatly reduces the disk I/O overhead caused by the mergeing operation and greatly improves the writing performance.Based on the LSM-Tree,this thesis sotres key and value separately,adds the index layer,creates an unique recovery algorithm of the old data,and designs and implements a Key-Value storage system.Compared with the LevelDB which adopts traditional LSMTree storage engine,this storage system has better writing performance,especially in the case where the value is large and the writing pressure is huge,the performance advantage is more obvious.