A key-value storage method based on log-structure merged tree

Abstract

The invention discloses a key value storage method based on a log-structured merged tree. The method comprises: 1, setting a cache component in a memory for each data storage component, setting a Bloom filter for each cache component, and setting a Bloom filter for each data block of each SSTable; 2, carrying out jump judgment on each key value pair of current data blocks of to-be-merged data storage components Ci stage by stage by adopting the corresponding Bloom filter, wherein if the key value pair jumps to a C<i+M>, no version of key value pair corresponding to keys exists in the C<i+M> and each stage of component in the front of the C<i+M>, a B<i+M+1> comprises a corresponding version of key value pair and then the key value pair is set into a B<i+M>, and if the key value pair is jumped to a B<i+N>, no version of key value pair corresponding to keys in the B<i+N> and each stage of component in the front of the B<i+N> and a C<i+N> comprises a corresponding version of key value pairs; and 3, processing the to-be-merged key value pairs in the Bi by adopting a similarity method.

Description

Technical field [0001] The invention belongs to the technical field of computer software and relates to a key value storage method based on a log structure merge tree. Background technique [0002] In current data centers, key-value storage systems have become the core of large-scale data-intensive network applications. Many researches are devoted to designing high-performance and high-scalability key-value storage systems. Log-Structured Merge-tree (LSM-tree) is widely used in current emerging Internet applications because of its simultaneous support for incremental writing, low writing latency, and range-based scanning. However, the LSM-tree-based key-value storage system has serious write amplification. In order to improve the write performance of the system, bLSM adopts a replacement selection sort algorithm to reduce the frequency of sorting and merging (R.Sears and R. Ramakrishnan.bLSM: A General Purpose) Log Sturctured MergeTree.in SIGMOD'2012), PCP proposes a pipelined ...

AI Technical Summary

Problems solved by technology

This layer-by-layer flow mechanism leads to severe write amplification

The research of bLSM and PCP focuses on reducing the frequency of sorting and merging or speeding up writing, but ignores the layer-by-layer flow of key-value pairs that is the root cause of severe write amplification

Images