Research On SSD-based LSM-Tree Key-Value Storage System

Facing the explosive growth of massive data,key-value storage systems have gradually become a key component to support large-scale applications.On the one hand,flashbased solid-state drive(SSD)has extremely high read and write performance.With the decline in cost,it has gradually replaced traditional mechanical disks and is widely used in data centers.On the other hand,the log-structured merge-tree(LSM-Tree)optimizes writing and is the mainstream data structure of the current key-value engine.However,the LSM-Tree itself is designed for mechanical disks,and the new features of flash memory are difficult to be used effectively.In order to be compatible with the traditional system architecture,SSD hides these features through the Flash Translation Layer(FTL).Deploying the LSM-Tree key-value storage engine directly on a general-purpose SSD has great software redundancy,which leads to cascaded write amplification and poor read performance.To address these issues,the thesis studies the architecture of the key-value storage system,designs and implements a key-value solid-state drive(KVSSD),which embeds the LSM-Tree structure into the SSD device,provides services directly through the key-value interface,and algorithms of FTL are optimized in combination with the characteristics of software and hardware.First,in order to support the key-value interface,a key-value command based on the NVMe protocol is designed,and the communication protocol between the storage device and the host is extended to adapt to the proposed architecture.Then,A LSM-Tree-oriented FTL is proposed,and the related algorithms are optimized by deeply mining the semantic information of LSM-Tree and the inherent characteristics of flash memory:(1)To address the cascaded write amplification problem,a level-aware hot and cold data separation algorithm and a stable greedy victitm block selection algorithm adapted to it are designed.Taking advantage of lifespan of SSTables at different levels in LSM-Tree is very different,data is classified by level and stored in flash memory blocks,and more stable high-level data is preferentially selected for garbage collection?(2)To address the poor read performance problem,an optimization algorithm for SSTable storage structure is designed.Taking advantage of the asymmetric speed of high and low pages of MLC flash memory,the metadata with higher read frequency in the SSTable is allocated to the flash memory pages with higher speed,reducing the overall read latency.Finally,the above system and algorithms are implemented on the simulator.The experimental results show that,compared with the key-value storage system using traditional SSD,the overall throughput of KVSSD is increased by about 2 times under different workloads,and the write amplification is reduced by about 50%.Multiple optimization algorithms in LSM-Tree-oriented FTL can significantly reduce the valid data migration and the read latency,the overall efficiency of the key-value storage system is improved.