CN117573676A - Address processing method and device based on storage system, storage system and medium - Google Patents

Abstract

The invention provides an address processing method and device based on a storage system, the storage system and a medium, and relates to the field of storage, wherein the method comprises the following steps: acquiring all logical addresses contained in a logical address space in a storage system; generating a B+ tree by using all the logical addresses; all leaf nodes of the B+ tree sequentially store key value pairs corresponding to all logical addresses according to the logical addresses, each leaf node stores the same number of key value pairs, and the key value pairs take the logical addresses as keys; when a key value pair update request is received, replacing a new key value pair containing a mapping relation between a logical address and a physical address with a key value pair with the same key in the B+ tree; the B+ tree can be generated based on all the logical addresses, so that the key value pairs for storing the mapping relation between each logical address and the physical address can be stored in the B+ tree according to the logical address sequence, and the complexity of managing the address mapping relation by using the tree structure can be reduced by replacing the key value pairs when updating the mapping relation.

Description

Storage system-based address processing method, device, storage system and medium

Technical field

The present invention relates to the field of storage, and in particular to an address processing method, device, storage system and medium based on a storage system.

Background technique

There are usually logical addresses and physical addresses in storage systems. The logical address is the address of the data in the application layer or logical volume, and the physical address is the address where the data is actually written to the storage device after passing through the logical layer. There is usually a relationship between the logical address and the physical address. There is a mapping relationship between settings.

In related technologies, a tree structure can usually be introduced to manage the mapping relationship between logical addresses and physical addresses. However, since the mapping relationship between logical addresses and physical addresses is always changing dynamically, the existing tree structure is prone to frequent structural changes, which not only increases the complexity of tree structure updates and queries, but also brings problems to the processor. more burden.

Contents of the invention

The purpose of the present invention is to provide an address processing method, device, storage system and medium based on a storage system, which can reduce the complexity of managing address mapping relationships using a tree structure.

In order to solve the above technical problems, the present invention provides an address processing method based on a storage system, including:

Obtain all logical addresses contained in the logical address space in the storage system;

A B+ tree is generated using all the logical addresses; all leaf nodes of the B+ tree sequentially store key-value pairs corresponding to each logical address according to the logical address, and each leaf node stores the same number of key-value pairs, so The key-value pair uses the logical address as the key;

When a key-value pair update request is received, a new key-value pair containing the mapping relationship between the logical address and the physical address is replaced with the key-value pair having the same key in the B+ tree.

Optionally, using all the logical addresses to generate a B+ tree includes:

Create an initial key-value pair for each logical address; the initial key-value pair uses the logical address as the key and a null value as the value;

The B+ tree is generated using the initial key-value pairs of all logical addresses.

Optionally, also includes:

When a key-value pair deletion request is received, the value of the key-value pair to be deleted corresponding to the key-value pair deletion request in the B+ tree is cleared.

Optionally, before obtaining all logical addresses contained in the logical address space in the storage system, it also includes:

The logical address space in the storage system is divided, and based on each divided logical address space, the step of obtaining all logical addresses contained in the logical address space in the storage system is entered.

Optionally, after using all the logical addresses to generate a B+ tree, it also includes:

Load the B+ tree from the storage device of the storage system into the memory device of the storage system;

Sort each tree node according to its position in the B+ tree, and record the memory address corresponding to each tree node in sequence according to the arrangement order of each tree node;

Replacing the new key-value pair containing the mapping relationship between the logical address and the physical address with the key-value pair having the same key in the B+ tree includes:

Search the memory address of the leaf node to be updated to which the new key-value pair belongs according to the key of the new key-value pair, the logical address range recorded by each leaf node and the arrangement order of each leaf node;

According to the memory address of the leaf node to be updated, the new key-value pair is replaced with a key-value pair having the same key in the leaf node to be updated.

Optionally, recording the memory addresses corresponding to each tree node in sequence according to the arrangement order of each tree node includes:

Generate corresponding arrays for each layer of the B+ tree, and record the memory addresses corresponding to the tree nodes of each layer into the arrays corresponding to each layer in turn according to the arrangement order of the tree nodes;

Searching for the memory address of the leaf node to be updated to which the new key-value pair belongs based on the key of the new key-value pair, the logical address range recorded by each leaf node and the arrangement order of each leaf node includes: :

Determine the sequence number of the leaf node to be updated to which the new key-value pair belongs in the array according to the key of the new key-value pair and the logical address range recorded by each leaf node;

Obtain the memory address of the leaf node to be updated from the array according to the sequence number.

Optionally, also includes:

When a key-value pair query request is received, based on the logical address of the key-value pair to be queried and the logical address range recorded by each leaf node, it is determined that the leaf node to be queried to which the key-value pair to be queried belongs is in the array. the serial number in;

Obtain the memory address of the leaf node to be queried from the array according to the sequence number, and obtain the key-value pair to be queried in the leaf node to be queried according to the memory address.

The present invention also provides an address processing device based on a storage system, including:

The acquisition module is used to obtain all logical addresses contained in the logical address space in the storage system;

A generation module, configured to generate a B+ tree using all the logical addresses; all leaf nodes of the B+ tree sequentially store key-value pairs corresponding to each logical address according to the logical address, and each leaf node stores the same number of A key-value pair with the logical address as the key;

An update module, configured to, when receiving a key-value pair update request, replace the new key-value pair containing the mapping relationship between the logical address and the physical address with the key-value pair having the same key in the B+ tree.

The invention also provides a storage system, including:

The first memory is used to store user data;

a second memory for storing computer programs;

A processor, configured to implement the above-mentioned storage system-based address processing method when executing the computer program.

The present invention also provides a computer-readable storage medium. Computer-executable instructions are stored in the computer-readable storage medium. When the computer-executable instructions are loaded and executed by a processor, the storage system-based storage system as described above is implemented. Address handling methods.

The present invention provides an address processing method, which includes: obtaining all logical addresses contained in the logical address space in the storage system; using all the logical addresses to generate a B+ tree; and storing all leaf nodes of the B+ tree in sequence according to the logical addresses. Key-value pairs corresponding to each logical address, each leaf node stores the same number of key-value pairs, and the key-value pairs use the logical address as a key; when a key-value pair update request is received, it will contain The new key-value pair of the mapping relationship between the logical address and the physical address is replaced with the key-value pair with the same key in the B+ tree.

It can be seen that the present invention can first obtain all logical addresses in the logical address space in the storage system, and use all logical addresses to generate a B+ tree, in which all leaf nodes of the B+ tree save the key values corresponding to each logical address in sequence according to the logical address. Yes, each leaf node stores the same number of key-value pairs, and the key-value pairs use logical addresses as keys. Obviously, the B+ tree in the present invention can cover all logical addresses in the logical address space, and the key-value pairs of each logical address are regularly saved in the B+ tree. In this way, when the present invention receives a key-value pair update request, it only needs to compare the new key-value pair containing the mapping relationship between the logical address and the physical address with the key with the same key in the B+ tree based on the key of the new key value. The value pairs can be replaced without changing the structure of the B+ tree. This can avoid the problem of frequent tree structure changes caused by dynamic changes in the mapping relationship between logical addresses and physical addresses, thereby effectively reducing the use of tree structure management. The complexity of the mapping relationship between logical addresses and physical addresses. The present invention also provides an address processing device, a storage system and a computer-readable storage medium based on a storage system, which have the above beneficial effects.

Description of the drawings

In order to explain the embodiments of the present invention or the technical solutions in the prior art more clearly, the drawings needed to be used in the description of the embodiments or the prior art will be briefly introduced below. Obviously, the drawings in the following description are only These are embodiments of the present invention. For those of ordinary skill in the art, other drawings can be obtained based on the provided drawings without exerting creative efforts.

Figure 1 is a flow chart of an address processing method based on a storage system provided by an embodiment of the present invention;

Figure 2 is a schematic structural diagram of a B+ tree provided by an embodiment of the present invention;

Figure 3 is a schematic diagram of using an array to record a B+ tree provided by an embodiment of the present invention;

Figure 4 is a structural block diagram of an address processing device based on a storage system provided by an embodiment of the present invention;

Figure 5 is a structural block diagram of a storage system provided by an embodiment of the present invention.

Detailed ways

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, rather than all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts fall within the scope of protection of the present invention.

There are usually logical addresses and physical addresses in storage systems. The logical address is the address of the data in the application layer or logical volume, and the physical address is the address where the data is actually written to the storage device after passing through the logical layer. There is usually a relationship between the logical address and the physical address. There is a mapping relationship between settings. In related technologies, a tree structure can usually be introduced to manage the mapping relationship between logical addresses and physical addresses. However, since the mapping relationship between logical addresses and physical addresses is always changing dynamically, the existing tree structure is prone to frequent structural changes, which not only increases the complexity of updating and querying the tree structure, but also brings problems to the processor. Comes more burdens. In view of this, the present invention can provide an address processing method based on a storage system, which can generate a B+ tree based on all logical addresses in the logical address space, so that the key-value pairs used to save the mapping relationship between each logical address and the physical address can be It is stored in the B+ tree according to the logical address sequence, and then when updating the above mapping relationship, only the key-value pairs need to be replaced. There is no need to adjust the structure of the tree, which can reduce the complexity of using the tree structure to manage the address mapping relationship.

It should be noted that the embodiment of the present invention is not limited to a specific storage system, which can be selected according to actual application requirements. For example, it can be a SAN (Storage Area Network, storage area network) storage system. It can be understood that a storage system usually contains multiple storage devices, and these storage devices can usually provide external storage services in the form of arrays. The embodiments of the present invention are not limited to the type (such as solid state drive, mechanical hard disk), quantity, and array form of the storage devices in the storage system (such as RAID1, RAID5, RAID6, RAID, Redundant Arrays of Independent Disks, disk array). , can be set according to actual application requirements.

Please refer to Figure 1, which is a flow chart of a storage system-based address processing method provided by an embodiment of the present invention. The method may include:

S101. Obtain all logical addresses contained in the logical address space in the storage system.

It should be noted that in the storage system, the logical address (LBA, Logical Block Address, logical block address) is set in the logical address space, and the physical address (PBA, Physical Block Address, physical block address) is set in the physical address space. The above two The address spaces correspond to each other through the mapping relationship between logical addresses and physical addresses. In the actual storage process, for the user, the data can be stored in the logical address space and can be accessed through the logical address; while for the storage device, the data will be stored in the physical address space after passing through the logical layer, and Access via physical address. Since there is a mapping relationship between the logical address and the physical address, when the user uses the logical address to access the logical address space, the corresponding physical address can be further determined based on the mapping relationship, and the corresponding user data can be obtained from the storage device based on the physical address. Obviously, the mapping relationship between logical addresses and physical addresses belongs to the metadata required to support the logical address space. Normally, the above mapping relationship (logical address is the key, physical address is the value) can be stored based on the form of key-value pair (KV pair, Key-Value), and the tree structure is used to save the key-value pair; in addition, in order to facilitate the key-value pair Search, when inserting key-value pairs into the tree structure, the storage location of each key-value pair in the tree structure can be adjusted according to the key. However, in the related art, the corresponding key-value pair is inserted into the tree structure only when it is determined that there is a mapping relationship between the logical address and the physical address; and because the mapping relationship changes frequently, this will cause the tree structure to change at any time. It may be necessary to adjust the storage location of each key-value pair in the tree structure, which may bring about major structural adjustments to the tree structure and introduce more query and write operations to metadata management, which is not conducive to efficient metadata management. . Therefore, the present invention can first obtain all logical addresses contained in the logical address space in the storage system, and generate a tree structure based on all logical addresses before using the logical address space, so that the tree structure stores each logical address in sequence according to the logical address. The key-value pair corresponding to the address. This not only ensures that the tree structure can completely cover all logical addresses in the logical address space, but also makes it easy to find the key-value pairs corresponding to each logical address in the tree structure, and subsequently creates a mapping relationship between logical addresses and physical addresses. , it is only necessary to update and replace the key-value pairs in the tree structure provided in this embodiment, and there is no need to adjust the branch structure of the tree structure.

It should be noted that the embodiment of the present invention is not limited to a specific tree structure, which can be set according to actual application requirements. For example, it can be a binary tree, a multi-tree (such as a B+ tree), etc. The embodiment of the present invention does not limit the specific size of the logical address space, which can be set according to actual application requirements. It should be noted here that the size of the tree structure (such as depth) may increase as the size of the logical address space increases, and a larger size tree structure is not conducive to fast search of key-value pairs. In order to effectively control the size of the tree structure, embodiments of the present invention can also divide a larger-sized logical address space, and create a corresponding smaller-sized tree structure for each divided logical address space.

Based on this, before obtaining all logical addresses contained in the logical address space in the storage system, you can also include:

Step 11: Divide the logical address space in the storage system, and proceed to the step of obtaining all logical addresses contained in the logical address space in the storage system based on each divided logical address space.

S102. Generate a B+ tree using all the logical addresses; all leaf nodes of the B+ tree sequentially store key-value pairs corresponding to each logical address according to the logical address, and each leaf node stores the same number of key-value pairs. , the key-value pair uses the logical address as a key.

Specifically, this embodiment of the present invention will store key-value pairs based on the B+ tree structure, where the B+ tree is a self-balancing search tree that is widely used in databases and file systems. B+ trees are characterized by storing a certain number of keywords on each internal node and dividing the nodes into multiple subtrees. Each keyword appears only once in the tree, and all leaf nodes are at the same level. These properties of the B+ tree enable it to maintain efficient performance during insertion, deletion, and search operations. In the related technology, the logical address and the physical address are managed in the existing way based on the B+ tree form (that is, only when it is determined that there is a mapping relationship between the logical address and the physical address, the corresponding key-value pair is inserted into the tree structure) If there is a mapping relationship between them, the structure of the same B+ tree will always change with the order and number of key-value pairs inserted. This can easily lead to: 1. The utilization rate of each node is not high, and there is a waste of free space in the node. For example, when inserting key-value pairs, if a node exceeds the maximum capacity, the node will be split into two nodes. At this time Only about half of the space of each node is valid, and the other half of the space is free, causing waste; 2. Increase the frequency of cache modification and update. This is because the B+ tree structure is constantly changing dynamically, causing the cache structure to also need to be updated on the disk. Structural changes are constantly adjusted to maintain the consistency of cache and on-disk data.

For this reason, before using the logical address space, the embodiment of the present invention will generate a B+ tree based on all logical addresses in the space to ensure that all leaf nodes of the B+ tree save the key values corresponding to each logical address in sequence according to the logical address. pairs, and ensure that each leaf node stores the same number of key-value pairs. Obviously, the embodiment of the present invention can ensure that the B+ tree completely covers all logical addresses in the logical address space from the beginning. In this way, when subsequently creating a mapping relationship between logical addresses and physical addresses, only the corresponding key values in the B+ tree need to be Just update and replace them, and there is no need to adjust the branch structure of the B+ tree. Moreover, the embodiment of the present invention can ensure that each leaf node stores the same number of key-value pairs, and can allocate the size of each leaf node in advance according to the number of key-value pairs, so as to ensure that each leaf node can be filled up, and thus can also This achieves the effect of improving node utilization and reducing storage resource waste.

It should be noted that when the B+ tree is created, since no corresponding physical address is assigned to each logical address, the values contained in all key-value pairs in the B+ tree are initial values. The embodiment of the present invention does not limit the specific initial value, which can be set according to actual application requirements, as long as it can ensure that the storage system can determine that the corresponding logical address has not been assigned a physical address based on the initial value. In one possible case, the initial value can be null.

Based on this, generating a B+ tree using all the logical addresses may include:

Step 21: Create an initial key-value pair for each logical address; the initial key-value pair uses the logical address as the key and a null value as the value;

Step 22: Generate the B+ tree using the initial key-value pairs of all logical addresses.

Furthermore, since the size of the logical address space will directly affect the size of the B+ tree, in order to avoid the size of the B+ tree being too large, embodiments of the present invention can also divide the logical address space according to the specified size of the B+ tree. Specifically, the logical address space can be divided according to the size of the B+ tree. The preset maximum depth and the preset maximum number of key-value pairs that can be saved by leaf nodes in the B+ tree determine the logical address range that the B+ tree can cover, and then the logical address space in the storage system is divided based on the logical address range. To ensure that the size of the divided logical address space is suitable for the specified B+ tree size.

Based on this, dividing the logical address space in the storage system may include:

Step 31: Determine the logical address range that the B+ tree can cover based on the preset maximum depth of the B+ tree and the preset maximum number of key-value pairs that can be saved by the leaf nodes in the B+ tree;

Step 32: Divide the logical address space in the storage system according to the logical address range.

For ease of understanding, please refer to Figure 2, which is a schematic structural diagram of a B+ tree provided by an embodiment of the present invention. When building a tree structure, embodiments of the present invention may adopt a certain balancing strategy to ensure that each tree contains the same number of keys and that the keys of each tree are distributed within a certain fixed range. As shown in Figure 2, each leaf node contains all key values of the fixed range class, and the key values recorded in each leaf node are consecutive integers within a fixed range. At this time, since the number of key-value pairs and the distribution of key-value pairs are known, the structure of the B+ tree can be preset in advance according to the B+ tree parameter configuration, for example, in the order of keys from small to large, from left to right. Populate each leaf node with the maximum number of key-value pairs in sequence. After the leaf nodes are determined, the key-value pair distribution of each layer of tree nodes can be determined from bottom to top, up to the root node. What should be pointed out here is that, except for leaf nodes, the key-value pairs in other tree nodes are used to record the pointers of their lower nodes. After completing the construction of the B+ tree, the embodiment of the present invention can use the B+ tree as a base tree, and when updating the key-value pairs, the key-value pair replacement operation can be directly performed according to the base tree structure. No matter how the number of key-value pairs and the order of their updates change, the structure of the tree on the disk always remains unchanged, and the relative positional relationship between key-value pairs also remains unchanged. It is this structural invariance and the invariance of relative position relationships that makes it possible to design an efficient cache structure.

S103. When receiving a key-value pair update request, replace the new key-value pair containing the mapping relationship between the logical address and the physical address with the key-value pair having the same key in the B+ tree.

As mentioned above, when a key-value pair update request is received, the new key-value pair containing the mapping relationship between the logical address and the physical address can be simply replaced with the key-value pair with the same key in the B+ tree. Similarly, when receiving a key-value pair deletion request that represents the clearing of the mapping relationship between the logical address and the physical address, in order to maintain the invariance of the relative position relationship between the key-value pairs, the embodiment of the present invention can combine the B+ tree with all the key-value pairs. The value of the key-value pair to be deleted corresponding to the key-value pair deletion request is cleared to restore the key-value pair to be deleted to its initial state without removing the key-value pair to be deleted.

Based on this, this method may also include:

Step 41: When receiving a key-value pair deletion request, clear the value of the key-value pair to be deleted corresponding to the key-value pair deletion request in the B+ tree.

Based on the above embodiments, the present invention can first obtain all logical addresses in the logical address space in the storage system, and use all logical addresses to generate a B+ tree, in which all leaf nodes of the B+ tree save the corresponding logical addresses in sequence according to the logical addresses. Each leaf node stores the same number of key-value pairs, and the key-value pairs use logical addresses as keys. Obviously, the B+ tree in the present invention can cover all logical addresses in the logical address space, and the key-value pairs of each logical address are regularly saved in the B+ tree. In this way, when the present invention receives a key-value pair update request, it only needs to compare the new key-value pair containing the mapping relationship between the logical address and the physical address with the key with the same key in the B+ tree based on the key of the new key value. The value pairs can be replaced without changing the structure of the B+ tree. This can avoid the problem of frequent tree structure changes caused by dynamic changes in the mapping relationship between logical addresses and physical addresses, thereby effectively reducing the use of tree structure management. The complexity of the mapping relationship between logical addresses and physical addresses.

Based on the above embodiments, since the embodiment of the present invention specially sets up a B+ tree and can ensure that the distribution of key-value pairs in the leaf nodes of the B+ tree is known and regular, the embodiment of the present invention can further improve the search based on this feature. Efficiency of key-value pairs. Based on this, after using all the logical addresses to generate the B+ tree, it may also include:

S201. Load the B+ tree from the storage device of the storage system into the memory device of the storage system.

S202: Sort each tree node according to its position in the B+ tree, and record the memory address corresponding to each tree node in sequence according to the arrangement order of each tree node.

It should be noted that in order to facilitate users to obtain data, when using logical address space, the tree structure can usually be loaded from the storage device of the storage system to the memory device of the storage system to directly determine in the memory device where the user data is located on the storage device. location in. However, in related technologies, the tree structure is usually stored using a hash table, and during the query process, it is necessary to query downwards layer by layer starting from the top of the tree structure. Taking the B+ tree structure as an example, in the existing method, since the distribution of key-value pairs in the B+ tree is not fixed, the leaf nodes where the key-value pairs are located need to be determined layer by layer from the top of the B+ tree. Furthermore, due to the structure of the B+ tree, in the existing method, every time a key-value pair is queried, the same number of search operations as the depth of the B+ tree must be performed, which reduces the query efficiency of the key-value pair. In the embodiment of the present invention, since the key-value pairs are arranged in an orderly manner in the B+ tree provided in this embodiment, and the position of each key-value pair in the B+ tree never changes, the embodiment of the present invention only requires According to the arrangement order of each tree node, the memory address corresponding to each tree node is recorded sequentially, so that when performing a key-value pair query, the key of the key-value pair to be queried, the order of each leaf node, and the records of each leaf node can be used. Within the logical address range, executing one query can determine the leaf node where the key value to be queried is located, and the key value pair to be queried can be quickly queried, which can significantly improve the query efficiency of the key value pair.

Correspondingly, replacing the new key-value pair containing the mapping relationship between the logical address and the physical address with the key-value pair having the same key in the B+ tree includes:

S203. Search the memory address of the leaf node to be updated to which the new key-value pair belongs according to the key of the new key-value pair, the logical address range recorded by each leaf node, and the arrangement order of each leaf node.

It should be noted that the leaf node to be updated is the leaf node described in the new key-value pair. It should also be noted that the embodiment of the present invention does not limit the form used to record the memory address of each tree node. For example, it can be recorded in list form or in array form. In order to facilitate index search, embodiments of the present invention may use an array form to record the memory address of each tree node. Specifically, corresponding arrays can be generated for each layer of the B+ tree, and the memory addresses corresponding to the tree nodes of each layer can be sequentially recorded into the arrays corresponding to each layer according to the arrangement order of the tree nodes. In this way, during subsequent queries, you only need to determine the sequence number of the leaf node to be updated to which the new key-value pair belongs in the array based on the key of the new key-value pair and the logical address range recorded by each leaf node, and retrieve the sequence number from the array based on the sequence number. Just get the memory address of the leaf node to be updated.

Based on this, recording the memory addresses corresponding to each tree node in sequence according to the arrangement order of each tree node may include:

Step 51: Generate corresponding arrays for each layer of the B+ tree, and record the memory addresses corresponding to the tree nodes of each layer into the arrays corresponding to each layer in sequence according to the arrangement order of the tree nodes;

Searching for the memory address of the leaf node to be updated to which the new key-value pair belongs according to the key of the new key-value pair, the logical address range recorded by each leaf node and the arrangement order of each leaf node may be include:

Step 52: Determine the sequence number of the leaf node to be updated to which the new key-value pair belongs in the array according to the key of the new key-value pair and the logical address range recorded by each leaf node;

Step 53: Obtain the memory address of the leaf node to be updated from the array according to the sequence number.

For ease of understanding, please refer to FIG. 3 , which is a schematic diagram of using an array to record a B+ tree according to an embodiment of the present invention. It can be seen that since the embodiment of the present invention generates a base tree based on the B+ tree structure, and the key-value pair data will be stored according to the base tree structure, and the distribution of each key-value pair in the base tree is very regular, therefore based on this rule, By specifying any key, the embodiment of the present invention can calculate which node in the leaf layer the value corresponding to the key falls on and the position in the node. At the same time, the embodiment of the present invention can also easily calculate the parent node corresponding to the leaf node, the position of the ancestor node in each layer and the position within the node. When caching in this way, the base tree structure can be mapped by constructing a cache array, and the B+ tree nodes of the base tree on the disk are mapped to the cache array according to rules, thereby achieving fast search and positioning based on the array index. As shown in Figure 3, first, corresponding to each layer of the base tree on the disk, there is a corresponding array in the cache array, which is used to store the pointers of the tree nodes in this layer in memory. Secondly, the size of the array at each level is equal to the number of nodes contained in that level in the base tree. In this way, according to the key-value pair to be queried and the storage rules of the key-value pair, we can know which node in the leaf layer the leaf node where the key-value pair is located falls on, and the storage location within the node, so that we can quickly query, insert or delete it. required value. In this way, compared with the original need to search step by step downwards from the root node, and each layer also needs to perform binary search and hash table search, the number of operations is greatly reduced, and the query efficiency is significantly improved.

S204. According to the memory address of the leaf node to be updated, replace the new key-value pair with a key-value pair having the same key in the leaf node to be updated.

It can be understood that after querying the memory address of the leaf node to be updated, the key-value pair can be replaced in the memory. After completing the update and replacement of the key-value pairs of the leaf nodes to be updated, they can be updated to the storage device to persist the update results.

Furthermore, for a simple key-value pair query request, the embodiment of the present invention can use the same method to quickly query the required key-value pair. Specifically, when a key-value pair query request is received, the location of the leaf node to be queried in the array to which the key-value pair belongs can be determined based on the logical address of the key-value pair to be queried and the logical address range recorded by each leaf node. Serial number, and obtain the memory address of the leaf node to be queried from the array according to the sequence number, thereby obtaining the key-value pair to be queried in the leaf node to be queried based on the memory address.

Based on this, this method may also include:

Step 61: When receiving a key-value pair query request, determine the location of the leaf node to be queried to which the key-value pair to be queried is based on the logical address of the key-value pair to be queried and the logical address range recorded by each leaf node. The serial number in the array;

Step 62: Obtain the memory address of the leaf node to be queried from the array according to the sequence number, and obtain the key-value pair to be queried in the leaf node to be queried according to the memory address.

Based on the above embodiments, this method can be simply summarized into two steps, namely:

1. First, in the metadata update and save stage, abandon the traditional method of dynamically constructing a disk brush tree based on B+ tree. Instead, directly insert and delete key-value pairs according to the base tree structure, and then save to disk. This can ensure the success of the disk save. Key-value pairs are stored strictly according to the preset base tree structure.

2. In the metadata read cache, for each base tree, a corresponding cache array is constructed, and the nodes in the base tree are stored in the cache array. When checking the cache, the location of the node is calculated according to certain rules through the query key. If it hits, the value is read directly; if it does not hit, the physical addresses of the parent and ancestor nodes are searched in sequence, and then the disk read operation is triggered.

The storage system-based address processing device, storage system and computer-readable storage medium provided by the embodiments of the present invention are introduced below. The storage system-based address processing device, storage system and computer-readable storage medium described below are the same as those described above. The address processing methods based on the storage system can correspond to each other.

Please refer to Figure 4, which is a structural block diagram of an address processing device based on a storage system provided by an embodiment of the present invention. The device may include:

The acquisition module 401 is used to acquire all logical addresses contained in the logical address space in the storage system;

The generation module 402 is used to generate a B+ tree using all the logical addresses; all leaf nodes of the B+ tree sequentially store key-value pairs corresponding to each logical address according to the logical address, and each leaf node stores the same number. A key-value pair, the key-value pair uses the logical address as the key;

The update module 403 is configured to, when receiving a key-value pair update request, replace the new key-value pair containing the mapping relationship between the logical address and the physical address with the key-value pair having the same key in the B+ tree.

Optionally, the generation module 402 may include:

The key-value pair initialization submodule is used to create an initial key-value pair for each of the logical addresses; the initial key-value pair uses the logical address as the key and a null value as the value;

The B+ tree creation submodule is used to generate the B+ tree using the initial key-value pairs of all logical addresses.

Optionally, the device may also include:

A deletion module, configured to clear the value of the key-value pair to be deleted corresponding to the key-value pair deletion request in the B+ tree when receiving a key-value pair deletion request.

Optionally, the device may also include:

A dividing module is used to divide the logical address space in the storage system, and enter the step of obtaining all logical addresses contained in the logical address space in the storage system based on each divided logical address space.

Optionally, the dividing module may include:

The coverageable logical address range determination submodule is used to determine the logical address that the B+ tree can cover based on the preset maximum depth of the B+ tree and the preset maximum number of key-value pairs that can be saved by leaf nodes in the B+ tree. scope;

A dividing sub-module is used to divide the logical address space in the storage system according to the logical address range.

Optionally, the device may also include:

A loading module, configured to load the B+ tree from the storage device of the storage system into the memory device of the storage system;

A recording module, configured to sort each tree node according to its position in the B+ tree, and record the memory address corresponding to each tree node in sequence according to the arrangement order of each tree node;

The update module 403 may include:

Query submodule, used to search for the leaf node to be updated to which the new key-value pair belongs based on the key of the new key-value pair, the logical address range recorded by each leaf node, and the arrangement order of each leaf node. memory address;

A replacement submodule, configured to replace the new key-value pair with a key-value pair having the same key in the leaf node to be updated according to the memory address of the leaf node to be updated.

Optionally, the recording module is specifically used for:

Generate corresponding arrays for each layer of the B+ tree, and record the memory addresses corresponding to the tree nodes of each layer into the arrays corresponding to each layer in turn according to the arrangement order of the tree nodes;

The query sub-module may include:

A query unit configured to determine the sequence number in the array of the leaf node to be updated to which the new key-value pair belongs based on the key of the new key-value pair and the logical address range recorded by each leaf node;

An obtaining unit, configured to obtain the memory address of the leaf node to be updated from the array according to the sequence number.

Optionally, the device may also include:

A query request response module, configured to, when receiving a key-value pair query request, determine the key-value pair to be queried according to the logical address of the key-value pair to be queried and the logical address range recorded by each leaf node. Query the serial number of the leaf node in the array;

A query module, configured to obtain the memory address of the leaf node to be queried from the array according to the sequence number, and to obtain the key-value pair to be queried in the leaf node to be queried according to the memory address.

Please refer to Figure 5. Figure 5 is a structural block diagram of a storage system provided by an embodiment of the present invention. An embodiment of the present invention provides a storage system 50, including a processor 51, a first memory 52, and a second memory 53; Among them, the first memory 52 is used to store user data; the second memory 53 is used to save a computer program; and the processor 51 is used to execute the method based on the previous embodiment when executing the computer program. Address processing method of storage system.

Regarding the specific process of the above storage system-based address processing method, reference may be made to the corresponding content provided in the foregoing embodiments, and will not be described again here.

Moreover, the first memory 52 and the second memory 53, as carriers for resource storage, can be read-only memory, random access memory, magnetic disks or optical disks, etc., and the storage method can be short-term storage or permanent storage.

In addition, the storage system 50 also includes a power supply 54, a communication interface 55, an input and output interface 56 and a communication bus 57; wherein the power supply 54 is used to provide operating voltage for each hardware device on the storage system 50, which can be provided by an external Power supply; the communication interface 55 can create a data transmission channel between the storage system 50 and external devices, and the communication protocol it follows is any communication protocol that can be applied to the technical solution of the present invention, which will not be detailed here. Limitation: The input and output interface 56 is used to obtain external input data or output data to the external world. Its specific interface type can be selected according to specific application needs, and is not specifically limited here.

Furthermore, the storage system may include multiple first memories 52 , and a logical address space may be constructed from the storage space composed of multiple first memories 52 ; in addition, the storage system may also include a memory device.

Embodiments of the present invention also provide a computer-readable storage medium. A computer program is stored on the computer-readable storage medium. When the computer program is executed by a processor, the steps of the address processing method based on the storage system of any of the above embodiments are implemented.

Since the embodiments of the computer-readable storage medium portion correspond to the embodiments of the storage system-based address processing method portion, for the embodiments of the computer-readable storage medium portion, please refer to the description of the embodiments of the storage system-based address processing method portion. , we won’t go into details here.

Each embodiment in the specification is described in a progressive manner. Each embodiment focuses on its differences from other embodiments. The same and similar parts between the various embodiments can be referred to each other. As for the device disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple. For relevant details, please refer to the description in the method section.

Those skilled in the art may further realize that the units and algorithm steps of each example described in connection with the embodiments disclosed herein can be implemented by electronic hardware, computer software, or a combination of both. In order to clearly illustrate the possible functions of hardware and software, Interchangeability, in the above description, the composition and steps of each example have been generally described according to functions. Whether these functions are performed in hardware or software depends on the specific application and design constraints of the technical solution. Skilled artisans may implement the described functionality using different methods for each specific application, but such implementations should not be considered to be beyond the scope of the present invention.

The steps of the methods or algorithms described in conjunction with the embodiments disclosed herein may be implemented directly in hardware, in software modules executed by a processor, or in a combination of both. Software modules may be located in random access memory (RAM), memory, read-only memory (ROM), electrically programmable ROM, electrically erasable programmable ROM, registers, hard disks, removable disks, CD-ROMs, or anywhere in the field of technology. any other known form of storage media.

The address processing method, device, storage system and medium based on the storage system provided by the present invention have been introduced in detail above. This article uses specific examples to illustrate the principles and implementation methods of the present invention. The description of the above embodiments is only used to help understand the method and the core idea of the present invention. It should be noted that those skilled in the art can make several improvements and modifications to the present invention without departing from the principles of the present invention, and these improvements and modifications also fall within the scope of the claims of the present invention.

Claims (10)

1. An address processing method based on a storage system, characterized by including: Obtain all logical addresses contained in the logical address space in the storage system; A B+ tree is generated using all the logical addresses; all leaf nodes of the B+ tree sequentially store key-value pairs corresponding to each logical address according to the logical address, and each leaf node stores the same number of key-value pairs, so The key-value pair uses the logical address as the key; When a key-value pair update request is received, a new key-value pair containing the mapping relationship between the logical address and the physical address is replaced with the key-value pair having the same key in the B+ tree. 2. The address processing method according to claim 1, characterized in that generating a B+ tree using all the logical addresses includes: Create an initial key-value pair for each logical address; the initial key-value pair uses the logical address as the key and a null value as the value; The B+ tree is generated using the initial key-value pairs of all logical addresses. 3. The address processing method according to claim 2, further comprising: When a key-value pair deletion request is received, the value of the key-value pair to be deleted corresponding to the key-value pair deletion request in the B+ tree is cleared. 4. The address processing method according to claim 1, characterized in that, before obtaining all logical addresses contained in the logical address space in the storage system, it further includes: The logical address space in the storage system is divided, and based on each divided logical address space, the step of obtaining all logical addresses contained in the logical address space in the storage system is entered. 5. The address processing method according to any one of claims 1 to 4, characterized in that, after using all the logical addresses to generate a B+ tree, it further includes: Load the B+ tree from the storage device of the storage system into the memory device of the storage system; Sort each tree node according to its position in the B+ tree, and record the memory address corresponding to each tree node in sequence according to the arrangement order of each tree node; Replacing the new key-value pair containing the mapping relationship between the logical address and the physical address with the key-value pair having the same key in the B+ tree includes: Search the memory address of the leaf node to be updated to which the new key-value pair belongs according to the key of the new key-value pair, the logical address range recorded by each leaf node and the arrangement order of each leaf node; According to the memory address of the leaf node to be updated, the new key-value pair is replaced with a key-value pair having the same key in the leaf node to be updated. 6. The address processing method according to claim 5, characterized in that recording the memory address corresponding to each tree node in sequence according to the arrangement order of each tree node includes: Generate corresponding arrays for each layer of the B+ tree, and record the memory addresses corresponding to the tree nodes of each layer into the arrays corresponding to each layer in turn according to the arrangement order of the tree nodes; Searching for the memory address of the leaf node to be updated to which the new key-value pair belongs based on the key of the new key-value pair, the logical address range recorded by each leaf node and the arrangement order of each leaf node includes: : Determine the sequence number of the leaf node to be updated to which the new key-value pair belongs in the array according to the key of the new key-value pair and the logical address range recorded by each leaf node; Obtain the memory address of the leaf node to be updated from the array according to the sequence number. 7. The address processing method according to claim 6, further comprising: When a key-value pair query request is received, based on the logical address of the key-value pair to be queried and the logical address range recorded by each leaf node, it is determined that the leaf node to be queried to which the key-value pair to be queried belongs is in the array. The serial number in; Obtain the memory address of the leaf node to be queried from the array according to the sequence number, and obtain the key-value pair to be queried in the leaf node to be queried according to the memory address. 8. An address processing device based on a storage system, characterized in that it includes: The acquisition module is used to obtain all logical addresses contained in the logical address space in the storage system; A generation module, configured to generate a B+ tree using all the logical addresses; all leaf nodes of the B+ tree sequentially store key-value pairs corresponding to each logical address according to the logical address, and each leaf node stores the same number of A key-value pair with the logical address as the key; An update module, configured to, when receiving a key-value pair update request, replace the new key-value pair containing the mapping relationship between the logical address and the physical address with the key-value pair having the same key in the B+ tree. 9. A storage system, characterized by including: The first memory is used to store user data; a second memory for storing computer programs; A processor, configured to implement the storage system-based address processing method according to any one of claims 1 to 7 when executing the computer program. 10. A computer-readable storage medium, characterized in that computer-executable instructions are stored in the computer-readable storage medium. When the computer-executable instructions are loaded and executed by a processor, claims 1 to 7 are implemented. The storage system-based address processing method described in any one of the above.