CN-121996626-A - Key value storage method based on key value separation log structure merge tree under separate memory

CN121996626ACN 121996626 ACN121996626 ACN 121996626ACN-121996626-A

Abstract

The invention belongs to the technical field of key value storage under a separated memory environment, and particularly relates to a key value storage method based on a key value separation log structure merging tree under a separated memory, which comprises the steps of organizing value data into a value data table which can be accessed and operated by a remote direct memory, adopting a fine-granularity garbage recycling mode, not moving all key value data positions, and identifying and recycling remote memory space where each failure value data is positioned by utilizing compression operation on SST; the method comprises the steps of designing a space reuse write strategy, writing value data into the recovered fragment memory space to improve space utilization rate and avoid serialization of the value data, constructing a null data space collector to manage and record a value data table written in an MN end, collecting the fragment space of the value data table by using the fragment space reorganizer and reorganizing the fragment space into a plurality of sets to receive the value data of the CN end, and effectively utilizing the fragment space of the value data table through splitting and brushing operation.

Inventors

Duan Zhuohui
GUO HANFEI
LIU HAIKUN
LIAO XIAOFEI

Assignees

华中科技大学

Dates

Publication Date: 20260508
Application Date: 20260114

Claims (9)

1. The key value storage method based on the key value separation log structure merging tree under the separation type memory is characterized by comprising the following steps: In the process of compressing and merging SST files of a sequencing string table of a computing node, generating a file iterator for each layer to trigger key value pair iterators of the SST files in the layer in sequence, generating a key value pair iterator for each SST of each layer to assist in accessing key value pair data in the SST in sequence, accessing all SST files of each layer, and in the accessing process: The method comprises the steps of (1) comparing a key value pair pointed by a key value pair iterator at the current time of a first layer with a key value pair pointed by a key value pair iterator at the current time of a second layer, if the keys are different, turning (2), if the keys are the same, turning (3), if the key value pair of a certain layer is completely read, and the other layer is left, writing the left key value pair into a new SST file in sequence to complete compression operation, (2) writing the key value pair with a larger key value pair into the new SST file without moving the key value pair iterator, writing the key value pair with a smaller key value pair into the new SST file, turning (1) the iterator with the key value pair pointed by the iterator to the next key value pair, and comparing the sequence numbers of the two key value pairs next time, wherein the key value pair with the smaller sequence number is invalid data, finding the corresponding to the address data table ID of the key value pair in a invalid data space collector at a computing node, wherein the key value pair is the invalid data corresponding to the two key value pairs, and the value pair is written into the corresponding data in the corresponding data space of the corresponding bit pair from the computing node, and the corresponding data is written in the new bit space of the corresponding bit pair with the corresponding value pair of the value pair, and the corresponding value pair is written in the corresponding bit 1, and the corresponding data is written in the corresponding bit space of the corresponding bit data to the value pair of the value pair, and the corresponding value pair is written in the corresponding bit 1; The method comprises the steps of adopting a fragment space reorganizer to scan the bit map corresponding to each value data table in an invalid data space collector to obtain available fragment continuous memory areas in the value data table, setting the double bit of the corresponding position in the bit map of the value data table where each fragment continuous memory area is located to be 10 to indicate that the data node space in the corresponding table is recovered but not used; And (3) value data brushing, namely splitting a value data table in a computing node into a plurality of pieces according to the size of each piece of continuous memory area in each set, then initiating a plurality of remote direct memory access writing operations, writing the split plurality of value data tables into the plurality of pieces of continuous memory areas recorded in the set in parallel, realizing space reuse brushing, and modifying metadata information of the value data table in an invalid data space collector corresponding to the set.
2. The method for storing key values based on a key value separation log structure merge tree in a separate memory according to claim 1, wherein the fragment space reorganizer is specifically configured to: Scanning each metadata item in the invalid data space collector, and generating a plurality of pieces of available fragment space information according to the starting address information of each item and the bit map representing the validity of each value data, wherein each piece of information is expressed as < start_addr, offset_start and size >, the offset_start represents the position of the starting invalid value data of a certain piece of fragment continuous memory area in a value data table taking the start_addr as the starting address, and the size represents the number of invalid value data in the block continuous memory area; recording each piece of available space information as an entry of a piece space reorganizer, and setting a double bit of a corresponding position in a bit map of a value data table where each piece of continuous memory area is located to be 10; And combining the fragment continuous memory areas according to the plurality of available fragment space information to generate a plurality of sets with the capacity of the preset value data table size.
3. The method for storing key values based on a key value separating log structure merge tree in a separate memory according to claim 1, wherein when the split plurality of value data tables are written in parallel into the plurality of fragmented continuous memory areas recorded in the set, the method further comprises: calculating the position of the current value data in a certain fragment in the current set as a remote memory address of the value data, wherein the calculation mode is as follows: Calculating and determining a position j in a local temporary value data table pointed to by a value address of a current key value pair in memtable of the computing nodes, namely: wherein, the method comprises the steps of, Representing the initial address of a temporary value data table where the current value data in the computing node is located; representing the address of the current value data in the computing node in the temporary value data table; representing the size of the value data in the value data table; from the current set, find the satisfaction of Is a k-th fragment of the continuous memory area, Representing each fragment contiguous memory region in a current set Is a function of the number of receivable value data, Obtaining the modified correct address : ; In the formula, Indicating the start address of the kth fragmented continuous memory area, 。
4. The method for storing key values based on a key value separation log structure merge tree in a separate memory according to claim 1, wherein when the fragmented continuous memory areas are combined, the fragmented continuous memory areas in the entries are combined in order from big to small.
5. The method for storing key values based on a key value separation log structure merge tree in a separate memory according to claim 1, wherein when a space exceeding a first threshold value in the data written in the memory node becomes invalid, the chip space reorganizer is triggered to start scanning bit map information in the invalid data space collector, a plurality of chip sets are generated, and the chip sets are added to the queue to be used.
6. The method for storing key values based on a key value separation log structure merge tree in a separate memory according to claim 1, wherein the value data swiping is divided into direct swiping and space reuse swiping, specifically: when the value data of the computing node to the memory node is initially executed, adopting a direct brushing mode under a continuous memory area of the memory node; When the space exceeding the second threshold value in the written data of the memory node is invalid, the data brushing module of the computing node starts to provide a fragment set consisting of discontinuous space from the to-be-used queue, and the brushing mode of the computing node is changed into a space reuse brushing mode.
7. An electronic device comprising a memory and a processor, the memory storing a computer program, characterized in that the processor implements the steps of the method according to any one of claims 1 to 6 when the computer program is executed.
8. A computer readable storage medium, characterized in that the computer readable storage medium comprises a stored computer program, wherein the computer program, when run by a processor, controls a device in which the storage medium is located to perform the steps of the method according to any one of claims 1 to 6.
9. A computer program product comprising a computer program or instructions which, when executed by a processor, carries out the steps of the method according to any one of claims 1 to 6.

Description

Key value storage method based on key value separation log structure merge tree under separate memory Technical Field The invention belongs to the technical field of key value storage under a separate memory environment, and particularly relates to a key value storage method based on a key value separation log structure merging tree under a separate memory. Background In recent years, split memory (DISAGGREGATED MEMORY, DM) has become a big hot spot in the storage area. On servers in traditional data centers, computing resources (such as CPUs) and memory resources (such as DRAMs) are tightly coupled modes, and with the development of hardware and software technology, memory resources become bottlenecks in the performance of data-intensive computing systems, exposing problems in that there is under-utilization of memory resources on data center servers, which results in an increase in total ownership costs (Total Cost of Ownership, TCO), and in that traditional monolithic server boundaries limit the shared use of free memory, and in that the demands for memory capacity for large data applications and cloud services are now increasing, and in that the increase in memory capacity is insufficient to keep pace with the increase in computing capacity, and so on. The separated memory is used for decoupling and separating the calculation and the memory resources, so that independent and elastic expansion on the calculation and the memory resources can be realized respectively, and the calculation and the memory resources are communicated through a quick network connection. Thus, the server's local memory and remote memory constitute its total physical memory, the server uses fast local memory to guarantee its high performance, while remote memory is mainly used to provide capacity expansion due to higher access latency than local. The main implementation of the current split memory architecture is dependent on remote direct memory access (Remote Direct Memory Access, RDMA) connection technology or (Compute Express Link, CXL) connection technology. In a split memory system based on RDMA, a large amount of data is stored in a remote memory end with larger capacity, and a local memory capacity of a computing end is smaller and only a part of hot data is stored, so how to efficiently access the data of the memory end by the computing end is a critical problem in the split memory, namely how to realize split memory index, which is also a prop problem in a database system. There have been some studies on the implementation form of data index under split memory architecture. The method mainly comprises the steps of adjusting the structure of a HASH table aiming at RDMA connection technology based on an extensible adjustment HASH index to enable the HASH table to be more suitable for a separated memory, reducing RDMA access times required by searching, inserting, deleting and updating operations, realizing concurrent execution of index requests in a lock-free mode, further supporting range query by a separated memory index method based on a B+ tree and an adaptive radix tree (Adaptive Radix Tree, ART), realizing concurrent access operation, and improving the performance of read-write operation by utilizing a local cache based on a data index of a traditional Log Structured combining tree (Log Structured MERGE TREE, LSM). The LSM tree regards the insertion, update and deletion operations of data as insertion (writing) operations, buffers the data in a memory and records the data in the form of a memory table, and the memory table is asynchronously written to a disk in batch sequence to realize efficient writing performance. When the amount of written data reaches a set threshold of the memory table (Memtable), a new memory table is generated to accept the subsequent writing operation, and the full memory table becomes an invariable memory table, the invariable memory table no longer accepts the writing operation, then the invariable memory table is serialized to generate a file called a sort string table (Sorted String Table, or SST) and written into the hard disk, and the data in the SST file is generally composed of key value pairs, index metadata, filters and the like. The key value storage based on the log structure merging tree is constructed on the separated memory architecture, meanwhile, the efficient writing characteristic of the log structure merging tree and the high bandwidth characteristic under the RDMA-based separated memory architecture are utilized, the compression operation is realized by using the computing resources on the memory nodes to unload the computing operation, so that the transmission of SST file data required by the compression operation is avoided, and the efficient writing performance is realized. However, the key value storage design based on the traditional LSM tree is constructed under the split memory, the data storage mode of the ordered character string table is still adopted in the re