Key value separation storage method and system for delayed garbage collection based on LSM tree

Abstract

The invention discloses a key value separation storage method and system for delayed garbage collection based on an LSM tree, and belongs to the field of computer storage. The method comprises the following specific steps: S1, packaging key value data into key value entries by an upper-layer application, and writing the key value entries into a key value file according to logic blocks for persistent storage; S2, querying a skip list in a memory and a 0-layer sorting character string list in an index module; and S3, enabling the upper-layer application to call a garbage collection interface of the key value storage system for separated storage. According to the method and system, the LSM tree is optimized by adopting a key value separation idea, the query delay is reduced by virtue of an index module, the garbage collection efficiency is improved by adopting a statistical preposition means, and unnecessary resources in a service peak period are reduced by utilizing a delayed garbage collection mechanism; the integrity of the key value storage system in the scene of frequent random reading in the processes of batch writing, rapid deletion and transient storage is improved, and the overall efficiency of the consensus module of the distributed storage system is optimized.

Description

technical field [0001] The invention discloses a key-value separation storage method and system based on delayed garbage collection of an LSM tree, and relates to the technical field of computer storage. Background technique [0002] As a kind of IT basic software for storing data, the traditional stand-alone database is increasingly limited by poor scalability, smooth performance curve and high investment in the era of massive data, and distributed databases emerge as the times require. Distributed databases break the performance bottleneck of traditional stand-alone databases, can be deployed on some relatively cheap machines, and have linear scalability in theory, completely eliminating users' concerns that databases cannot support rapid business development. Distributed databases use computer networks to connect multiple computing and storage units scattered in physical space into a logically integrated database system, which has dispersion in physical space, integrity i...

AI Technical Summary

Problems solved by technology

BadgerDB is suitable for scenarios with large values, and performs poorly for scenarios with small values

After adopting the key-value separation strategy, the sequential search becomes a random read of the disk, which limits the read performance of BadgerDB to a certain extent.

At the same time, after the key value is separated, the deleted value needs to be cleaned up separately. During the cleaning process, the LSM tree needs to be queried according to the key to determine whether to retain the value. Therefore, BadgerDB's garbage collection (Garbage Collection, GC for short) consumes a lot of performance

The GC process of BadgerDB depends to a certain extent on the statistics of the deleted data in the valueLog file during the LSM tree merging process. In the scenario where the key value is large (64KB or more), the LSM tree merging frequency is low (if the merging frequency is high, it will cause higher write amplification) causes the statistical information of deleted data in the valueLog file to lag behind, which in turn affects the efficiency of BadgerDBGC;

Images