Cache optimization method for reading performance of KV storage system based on LSM-tree

Abstract

The invention discloses a cache optimization method for reading performance of a KV storage system based on an LSM-tree, which comprises the following steps of: adding a KeyRange Cache of which the structure is the same as the hierarchical structure of SST (Secure Sockets) on a disk into a memory, so that entries of each layer are in one-to-one correspondence with SST of a corresponding layer on the disk, and each entry caches a corresponding SST key range on the disk; the BF Cache only caches the Bloom filter of the SST containing the hot data; performing cold and hot separation on the data; if the data are judged to be hot data, caching a corresponding Bloom filter into a BFCache, and enabling a BFP pointer to point to the BFCache; otherwise, setting the pointer of the BFP (Basal File Point) to be NULL; querying a specified key k1, sequentially querying the MemTable and the Immersible MenTable, directly returning the value of the k1 if the MemTable and the Immersible MenTable are found, searching the KeyRange Cache layer by layer from low to high if the value of the k1 is not found, judging whether the data are hot data if the key range containing the k1 is found, and then finding the k1 from the corresponding SST in the disk; and if the layer is not found, continuing to search to the next layer. According to the method, layer-by-layer searching on the LSM-tree is not needed, the reading speed is increased, and high reading performance is achieved.

Description

technical field [0001] The invention relates to a caching optimization method for reading performance of an LSM-tree-based KV storage system, which belongs to the technical field of storage systems. Background technique [0002] Nowadays, many KV storage systems are designed based on LSM-tree (Log-Structured-Merge Tree), such as LevelDB and RocksDB. LSM-tree mainly consists of three parts: MemTable, Immutable MemTable, SSTable (ie SST), such as figure 1 shown. MemTable and Immutable MemTable are components that exist in memory. The latest updated data is stored in MemTable, and when MemTable reaches a certain size, it will be converted into ImmutableMemTable. Because the data is temporarily stored in the memory, the memory is not a reliable storage, and the data will be lost if the power is turned off. Therefore, WAL (Write-ahead logging) is usually used to ensure the reliability of the data. Then ImmutableMemTable will be flashed to the disk and become SST on L0. SST (...

AI Technical Summary

Problems solved by technology

Therefore, when more levels are present, the read amplification will be more severe, possibly even exceeding 300 times

Images