CN119336251B

CN119336251B - Method for constructing hybrid mapping structure and related device

Info

Publication number: CN119336251B
Application number: CN202411250496.8A
Authority: CN
Inventors: 王嘉品; 吕涛; 张祥平; 陈祥
Original assignee: Shenzhen Dapu Microelectronics Co Ltd
Current assignee: Shenzhen Dapu Microelectronics Co Ltd
Priority date: 2024-09-06
Filing date: 2024-09-06
Publication date: 2025-11-28
Anticipated expiration: 2044-09-06
Also published as: CN119336251A

Abstract

This application relates to the field of data storage technology and discloses a method and related apparatus for constructing a hybrid mapping structure. The method for constructing the hybrid mapping structure includes: obtaining mapping pairs; determining whether logical addresses are continuous non-big-page aligned addresses based on a global bitmap; if the logical addresses are not continuous non-big-page aligned addresses, determining whether the continuity of the logical address segment corresponding to the logical address is greater than a continuity threshold; if the continuity of the logical address segment is greater than the continuity threshold, inserting the mapping pair into a compact array; if the continuity of the logical address segment is less than or equal to the continuity threshold, inserting the mapping pair into a range bucket hash structure. By using a hybrid mapping structure that combines a global bitmap, a compact array, and a range hash bucket structure to store the mapping pairs, the memory overhead of flash memory devices can be optimized, saving memory in pure sequential read/write scenarios and maintaining array performance in pure random read/write scenarios.

Description

Method for constructing hybrid mapping structure and related device

Technical Field

The embodiment of the application relates to the technical field of data storage, in particular to a method for constructing a hybrid mapping structure and a related device.

Background

In modern Solid State Drives (SSD), a mapping table (L2P table) from a logical address to a physical address is an important component of a Flash Translation Layer (FTL), and the L2P table not only directly affects the read-write performance, but also occupies most of the memory resources of the SSD. In addition, the size of the mapping table increases as the capacity of the flash memory increases, but the physical space available for memory particles within the SSD approaches a limit. With the exponential increase of global data volume, the contradiction of shortage of internal memory in the SSD is increasingly highlighted due to the appearance of high-capacity QLC SSDs.

Currently, in order to solve the problem of the shortage of the SSD memory, the prior art scheme includes two types, namely, an array-based mapping table with the widest use range, wherein the subscript of the array represents the logical address (LPA) of the page, and the corresponding element value represents the physical address (PPA) of the page. The structure can save the memory by adjusting the granularity of the page, has higher performance but larger memory consumption if an array taking 4K as one page is taken as a traditional scheme, and can save 75 percent of memory if an array taking 16K as one page is taken as a large page scheme, and has lower performance. The second type is a structure that uses external storage to store mapping tables, including a selective index cache (DFTL) scheme that uses flash memory to store part of the tables in the memory of the SSD, and the rest of the mapping tables in the flash memory or host memory, which can save memory, but has poor performance due to the swap-in and swap-out of flash pages involved. In summary, both of these prior art schemes cannot achieve both performance and memory overhead.

Disclosure of Invention

The embodiment of the application provides a method for constructing a hybrid mapping structure and a related device, wherein the hybrid mapping structure combining three data structures of a global bit chart, a compact array and a range hash bucket structure is adopted to store mapping pairs, so that the memory overhead of flash memory equipment can be optimized, memory can be saved in a pure sequence read-write scene, and the performance of the array can be maintained in a pure random read-write scene.

The embodiment of the application provides the following technical scheme:

in a first aspect, an embodiment of the present application provides a method for constructing a hybrid mapping structure, where the hybrid mapping structure includes a global bitmap, a compact array, and a range bucket hash structure, the method includes:

obtaining a mapping pair, wherein the mapping pair comprises a logic address and a physical address corresponding to the logic address;

judging whether the logic address is a continuous non-large page alignment address according to the global bit diagram;

if the logical address is not a continuous non-large page alignment address, judging whether the continuity of the logical address segment corresponding to the logical address is greater than a continuity threshold value;

If the continuity of the logical address segment is greater than the continuity threshold, inserting the mapping pair into the compact array;

if the continuity of the logical address segment is less than or equal to the continuity threshold, the mapping pair is inserted into the range bucket hash structure.

In some embodiments, the global bitmap is configured to store metadata information corresponding to each logical address segment, the metadata information including continuity, the metadata information further including an allocation bitmap, the allocation bitmap being configured to store a first state of the logical address, the first state including a mapped state and a non-mapped state, the method further comprising:

judging whether the first state corresponding to the logical address is a mapping state or not according to the allocation bitmap;

And if the first state corresponding to the logical address is the non-mapping state, modifying the first state corresponding to the logical address into the mapping state.

In some embodiments, the metadata information further includes a continuous bitmap for storing a second state of the logical address, the second state including a continuous state and a discontinuous state, determining whether the logical address is a continuous non-large page aligned address according to the global bitmap, comprising:

judging whether the logic address is a non-large page alignment address;

if the logical address is a non-large page alignment address, judging whether the logical address is continuous with the logical address in the global bit diagram according to the global bit diagram;

If the logical address is continuous with the logical address in the global bit map, determining the continuous bit map corresponding to the logical address as a continuous state.

In some embodiments, the scope bucket hash structure includes a global scope table, a scope bucket, and a scope array, wherein the global scope table is configured to store mapping pointers corresponding to logical address segments, insert mapping pairs into the scope bucket hash structure, and include:

judging whether a mapping pointer corresponding to the logical address segment points to a range bucket according to the global range table;

If the mapping pointer corresponding to the logical address segment points to the range bucket, inserting the mapping pair into the range bucket;

If the mapping pointer corresponding to the logical address segment does not point to the range bucket, the mapping pair is inserted into the range array.

In some embodiments, after inserting the mapping pairs into the range buckets, the method further comprises:

judging whether the capacity of the range barrel reaches a capacity threshold value or not;

If the capacity of the range bucket reaches the capacity threshold, judging whether the continuity of the range bucket is larger than the continuity threshold;

if the continuity of the range bucket is smaller than or equal to the continuity threshold value, judging whether the density of the range bucket is larger than the density threshold value or not;

if the density of the range bucket is less than or equal to the density threshold, splitting the range bucket into at least two range buckets;

If the density of the range bucket is greater than the density threshold, the range bucket is split into at least two range arrays.

In some embodiments, the method further comprises:

judging whether the continuity of the compact array is smaller than or equal to a continuity threshold value;

If the continuity of the compact array is smaller than the continuity threshold, acquiring all mapping pairs of the established mapping relation in the compact array;

and inserting all mapping pairs with the established mapping relation into a range bucket, and releasing the memory of the compact array to restore the compact array into the range bucket.

In some embodiments, after inserting the mapping pairs into the range array, the method further comprises:

judging whether the density of the range array is smaller than a density threshold value or not;

if the density of the range array is smaller than the density threshold value, acquiring all mapping pairs in the range array;

and inserting all mapping pairs in the range array into the range bucket, and releasing the memory of the range array to restore the range array into the range bucket.

In some embodiments, after inserting the mapping pairs into the range bucket, the method further comprises:

Judging whether the continuity of a certain logic address segment in the range bucket is larger than a continuity threshold value or not;

If the continuity of a certain logic address segment in the range bucket is larger than a continuity threshold value, acquiring the logic address segment and a mapping pair corresponding to the logic address segment;

Establishing a compact array for the logical address field, and moving the mapping pair corresponding to the logical address field from the range bucket to the compact array;

After the mapping pairs corresponding to the logical address segments are moved from the range bucket to the compact array, if the density of the range bucket is less than the density threshold, merging the range bucket with surrounding range buckets into a new range bucket.

In a second aspect, an embodiment of the present application provides a physical address query method based on a hybrid mapping structure, where the hybrid mapping structure includes a global bit map, a compact array, and a range bucket hash structure, the method including:

Obtaining a logic address;

inquiring whether the logic address has established a mapping relation according to the global bit diagram;

If the logic addresses have established a mapping relation, judging whether the logic addresses are continuous or not;

If the logical addresses are continuous, traversing the global bit diagram to obtain the initial logical address of the address segment corresponding to the logical address;

if the initial logical address is a large page alignment address, acquiring a physical address corresponding to the logical address through the compact array;

if the logical addresses are discontinuous, the physical addresses corresponding to the logical addresses are obtained through the range bucket hash structure.

In some embodiments, the range bucket hash structure includes a global range table, a range bucket, and a range array, where the global range table is configured to store a mapping pointer corresponding to a logical address segment, and obtain, through the range bucket hash structure, a physical address corresponding to the logical address, and includes:

If the mapping pointer corresponding to the logical address segment points to the range bucket, acquiring a physical address corresponding to the logical address in the range bucket;

If the mapping pointer corresponding to the logical address segment does not point to the range bucket, the physical address corresponding to the logical address is obtained from the range array.

In some embodiments, the metadata information includes an allocation bitmap for storing a first state of the logical address, the first state including a mapped state and a non-mapped state, the determining whether the logical address has established a mapping relationship, including:

if the first state corresponding to the logical address is a mapping state, determining that the logical address has established a mapping relation;

If the first state corresponding to the logical address is a non-mapping state, determining that the logical address does not establish a mapping relationship, and outputting a query failure result.

In some embodiments, the metadata information further includes a continuous bitmap for storing a second state of the logical address, the second state including a continuous state and a discontinuous state, determining whether the logical address is continuous, including:

judging whether the second state corresponding to the logical address is a continuous state or not according to the continuous bitmap;

if the second state corresponding to the logical address is a continuous state, determining the logical address as a continuous logical address;

and if the second state corresponding to the logic address is a discontinuous state, determining the logic address as the discontinuous logic address.

In some embodiments, before the physical address corresponding to the logical address is obtained by the compact array, the method further comprises:

judging whether the address segment has established a compact array;

if the address field has established a compact array, acquiring a physical address corresponding to the logical address through the compact array;

If the address segment does not establish the compact array, the physical address corresponding to the logical address is obtained through the range bucket hash structure.

In a third aspect, an embodiment of the present application provides a flash memory device controller, including:

at least one processor, and

A memory communicatively coupled to the at least one processor, wherein,

The memory stores instructions executable by the at least one processor to enable the at least one processor to perform the method of building a hybrid mapping structure as in the first aspect, or the method of querying a physical address based on a hybrid mapping structure of the second aspect.

In a fourth aspect, an embodiment of the present application provides a flash memory device, including:

a flash memory device controller as in the third aspect;

at least one flash memory medium in communication with the flash memory device controller.

The method has the advantages that the method is different from the situation in the prior art, the hybrid mapping structure comprises a global bit chart, a compact array and a range bucket hash structure, the method comprises the steps of obtaining a mapping pair, judging whether the logic address is a continuous non-large page aligned address according to the global bit chart, judging whether the continuity of a logic address segment corresponding to the logic address is larger than a continuity threshold value if the logic address is not the continuous non-large page aligned address, inserting the mapping pair into the compact array if the continuity of the logic address segment is larger than the continuity threshold value, inserting the mapping pair into the range bucket hash structure if the continuity of the logic address segment is smaller than or equal to the continuity threshold value, storing the mapping pair by adopting the hybrid mapping structure combining the three data structures of the global bit chart, the compact array and the range hash bucket structure, and saving memory cost of the flash memory device under pure sequence reading and writing and maintaining the performance of the array under a pure random reading and writing scene.

Drawings

One or more embodiments are illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements, and in which the figures of the drawings are not to scale, unless expressly stated otherwise.

Fig. 1 is a schematic structural diagram of a hybrid mapping structure according to an embodiment of the present application;

FIG. 2 is a schematic diagram of a relationship between a range hash bucket structure according to an embodiment of the present application;

FIG. 3 is a schematic flow chart of a method for constructing a hybrid mapping structure according to an embodiment of the present application;

FIG. 4 is a flowchart illustrating a method for determining whether a first state corresponding to a logical address is a mapping state according to an embodiment of the present application;

FIG. 5 is a flowchart of determining whether a logical address is a consecutive non-large page aligned address according to an embodiment of the present application;

fig. 6 is a schematic diagram of a refinement flow of step S305 in fig. 3;

FIG. 7 is a schematic flow chart of determining whether the capacity of a range bucket reaches a capacity threshold according to an embodiment of the present application;

FIG. 8 is a flow chart of determining whether the continuity of the compact array is less than or equal to a continuity threshold value according to an embodiment of the present application;

FIG. 9 is a flow chart of determining whether the density of the range array is less than a density threshold according to an embodiment of the present application;

FIG. 10 is a flowchart illustrating a method for determining whether a continuity of a logical address segment in a range bucket is greater than a continuity threshold according to an embodiment of the present application;

FIG. 11 is an overall flow diagram of a method for constructing a hybrid mapping structure according to an embodiment of the present application;

Fig. 12 is a flow chart of a physical address query method based on a hybrid mapping structure according to an embodiment of the present application;

Fig. 13 is a schematic diagram of a refinement flow of step S1202 in fig. 12;

fig. 14 is a schematic diagram of a refinement flow of step S1204 in fig. 12;

fig. 15 is a schematic diagram of a refinement flow of step S1205 in fig. 12;

FIG. 16 is a flow chart of determining whether an address field has established a compact array according to an embodiment of the present application;

FIG. 17 is a schematic overall flow diagram of a physical address query method based on a hybrid mapping structure according to an embodiment of the present application;

FIG. 18 is a schematic diagram of a flash memory controller according to an embodiment of the present application;

fig. 19 is a schematic structural diagram of a flash memory device according to an embodiment of the present application.

Reference numerals illustrate:

Reference numerals	Name of the name	Reference numerals	Name of the name
				100	Flash memory device	200	Host machine
110	Flash memory medium	180	Flash memory device controller
				181	Processor and method for controlling the same	182	Memory device

Detailed Description

The technical scheme of the application is specifically described below with reference to the accompanying drawings of the specification:

referring to fig. 1, fig. 1 is a schematic structural diagram of a hybrid mapping structure according to an embodiment of the present application;

As shown in fig. 1, the hybrid mapping structure is stored in a memory space of the flash memory device, and the hybrid mapping structure includes a global bit map, a compact Array, and a Range Bucket hash table (RBHT, range Bucket Hash Tab l e), where the Range hash Bucket structure includes a global Range table (GRT, G l oba l Range Tab l e), a Range Bucket (RB, range Bucket), and a Range Array (RA, range Array), in some embodiments, the Range Array structure in the Range Bucket hash structure is swapped to the host memory along with the shortage of the SSD memory, and the rest of the Array storage structures are all located in the SSD, and it can be understood that the three structures of the global bit map, the compact Array, and the Range Bucket hash table can exist at the same time, and can be converted with each other according to a load condition, so as to dynamically adjust a ratio of each data storage structure. By adopting a mixed mapping structure combining three data structures of a global bit chart, a compact array and a range hash bucket structure to store mapping pairs, the application can optimize the memory overhead of the flash memory device, realize memory saving in a pure sequence read-write scene and maintain the performance of the array in a pure random read-write scene.

Referring to fig. 2, fig. 2 is a schematic diagram of a relationship between a range hash bucket structure according to an embodiment of the present application;

As shown in FIG. 2, the global bit map comprises metadata information, the global bit map is composed of a plurality of address segments, each address segment corresponds to continuity, each address segment comprises a plurality of logic addresses, the mapping table is dynamically converted according to the continuity, each mapping table structure dynamically occupies memory, each address segment stores the mapping table address through a pointer, each logic address corresponds to a continuous bitmap and an allocation bitmap, wherein the allocation bitmap represents whether each logic address has established a mapping relation with a physical address, and delay cost caused by failure of mapping table query can be avoided by querying the allocation bitmap in advance. The continuity refers to the sum of numbers of continuous states of continuous bitmaps in each address segment, if the continuity is larger than a continuity threshold value, the continuity of the address segment is better, a compact array is selected for mapping, and if the continuity is smaller than or equal to the continuity threshold value, the continuity of the segment is poorer, and an application range hash bucket structure is selected for mapping. In the embodiment of the application, in order to facilitate the management of the logical address, the logical address with a fixed address length is set as an address field, where the fixed address length may be set according to actual needs, for example, the address length is set to 4096. In some embodiments, to avoid excessive look-ahead, the present application groups every 8 logical addresses LPA, with the bits of the 8-byte aligned address fixed to 0. And the compact array records 8 the physical address PPA of the aligned address, only 1/8 mapping table item is needed to be recorded, and the memory space is saved.

The compact array is divided into a plurality of arrays according to the size of an address field, 512 compact array table entries are arranged when the address field length is 4096, and each table entry occupies 2048 Bytes in total. When the FTL builds the compact array table, the FTL applies for the memory with the size of 2KB per block. When the continuity of the address field drops beyond a threshold, the FTL will convert the compact array into a range bucket, releasing the original memory.

The scope bucket hash table consists of a global scope table, a scope bucket, and a scope array. The global range table is used for recording the mapping table address corresponding to each section of logical address range (logical address section) and storing the mapping pointer corresponding to the logical address section. It should be noted that the ranges in the global range table are of indefinite length, and the ranges thereof dynamically change according to the splitting and merging of the range buckets and the range arrays, wherein the global range table stores the start address of each range, and the start address of the next range is also the end address of the last range. The range bucket is a hash table structure, and has a fixed size, and is used for storing a mapping pair from a logical address LPA to a physical address PPA in a range, wherein the mapping pair consists of two fields of the LPA and the PPA. The range bucket is more suitable for storing sparse mapping pairs than the array structure. When the density of the range bucket reaches the upper limit of one range bucket storage mapping pair, namely the capacity of the range bucket reaches the capacity threshold value, the range bucket is split, and the range bucket can be split into two range buckets, or a plurality of range arrays, or a combination of the range arrays and the range bucket according to practical situations. The range array is a fixed length array that is organized in accordance with the structure of a conventional array scheme, storing a range of PPAs. The base address of each range array is recorded in a global range table, and the number of valid mappings in the range array is reduced to be reconverted into a range bucket. The insertion and inquiry performances of the range array are higher than those of the range bucket, and the range array is more suitable for being stored in the memory of a host. In some embodiments, linear probing may result in multiple accesses, as range bucket queries may encounter hash collisions. The PPA can be obtained by only one access of the range array, and the PC ie request times can be reduced when the PPA is placed in the host memory, so that in some embodiments, when a random scene generates a large number of range arrays, the application reduces SSD memory pressure by placing the range arrays in the host memory.

Referring to fig. 3, fig. 3 is a flow chart of a method for constructing a hybrid mapping structure according to an embodiment of the present application;

In the embodiment of the application, the hybrid mapping structure comprises a global bit chart, a compact array and a range bucket hash structure, wherein the global bit chart is used for storing metadata information corresponding to each logic address segment, the metadata information comprises continuity, the compact array is used for storing logic addresses with continuity larger than a continuity threshold value and aligned in large pages and physical addresses corresponding to the logic addresses, and the range bucket hash structure is used for storing the logic addresses which are not stored in the compact array and the physical addresses corresponding to the logic addresses.

As shown in fig. 3, the flow of the method for constructing the hybrid mapping structure includes:

Step 301, a mapping pair is obtained, wherein the mapping pair comprises a logic address and a physical address corresponding to the logic address;

Specifically, a mapping pair to be inserted into the hybrid mapping structure is obtained, where the mapping pair includes a logical address and a physical address corresponding to the logical address, and it should be noted that a mapping relationship exists between the logical address and the physical address corresponding to the logical address.

In the embodiment of the application, after the mapping pair is obtained, the mapping relation between the logical address and the physical address in the mapping pair is required to be recorded in the allocation bitmap of the global bitmap, so that whether the mapping relation exists between the logical address and the physical address is conveniently inquired through the global bitmap, and the inquiry efficiency of the physical address is improved.

Referring to fig. 4 again, fig. 4 is a flowchart illustrating a method for determining whether a first state corresponding to a logical address is a mapping state according to an embodiment of the present application;

Step S401, acquiring a global bit chart;

Specifically, a global bitmap is obtained, where the global bitmap is used to store metadata information corresponding to each logical address segment, where the metadata information includes continuity, an allocation bitmap, and a continuous bitmap, in this embodiment of the present application, the allocation bitmap is used to store a first state of a logical address, where the first state includes a mapping state and a non-mapping state, the mapping state refers to a mapping relationship established between a logical address and a physical address, the non-mapping state refers to a mapping relationship not established between a logical address and a physical address, the continuous bitmap is used to store a second state of a logical address, where the second state includes a continuous state and a non-continuous state, the continuous state refers to that a current logical address is continuous with a logical address recorded in the global bitmap, the non-continuous state refers to a sum of numbers of continuous states corresponding to a logical address of a certain address segment, for example, a certain address segment includes 10 logical addresses, where a continuity of 6 logical addresses is continuous state, and a continuity of 4 logical addresses is discontinuous state, and the continuity of the segment is 6 bitmap.

Step S402, judging whether a first state corresponding to a logic address is a mapping state according to an allocation bitmap;

Specifically, the global bitmap is used to query the allocation bitmap corresponding to the logical address, obtain the first state corresponding to the logical address, further determine whether the first state corresponding to the logical address is a mapping state, enter step S403 if the first state corresponding to the logical address is a non-mapping state, and enter step S404 if the first state corresponding to the logical address is a mapping state.

Step S403, modifying the first state corresponding to the logical address into a mapping state;

Specifically, if the first state corresponding to the logical address is the non-mapping state, which indicates that the mapping relationship between the logical address and the physical address is not recorded in the global bitmap, that is, the current first state of the logical address is the non-mapping state, the allocation bitmap in the global bitmap is modified, the first state corresponding to the logical address is modified to the mapping state, for example, if the mapping state is 1 and the non-mapping state is 0, the first state is modified from 0 to 1, so that the mapping relationship between the logical address and the physical address is recorded in the global bitmap, and after the first state corresponding to the logical address is modified to the mapping state, step S404 is entered.

Step S404, inserting the mapping pair into a mixed mapping structure;

Specifically, if the first state corresponding to the logical address is a mapping state, which indicates that the mapping relationship between the logical address and the physical address is recorded in the global bitmap, the mapping pair is inserted into the hybrid mapping structure according to steps S302 to S306.

Referring to fig. 5 again, fig. 5 is a flowchart illustrating a method for determining whether a logical address is a continuous non-large page aligned address according to an embodiment of the present application;

As shown in fig. 5, the process of determining whether the logical address is a consecutive non-large page aligned address includes:

step S501, obtaining a logic address;

specifically, according to the mapping pair, the logical address in the mapping pair is obtained.

Step S502, judging whether the logic address is a non-large page alignment address;

In the embodiment of the application, large page alignment (LARGE PAGE AL IGNMENT) refers to allocating or mapping a memory to a memory block larger than a standard page size (such as 4 KB), the large page alignment address refers to a coarse-grained page, i.e. a large page comprises a plurality of 4KB pages, the large page alignment can ensure that data can be continuously and efficiently read or written, for example, the large page alignment can reduce the number of page table entries, thereby reducing memory occupation and improving memory access speed, and reducing memory fragmentation, so that memory management is more efficient, the non-large page alignment address refers to an integer multiple of the number of bytes of a data unit, the large page alignment address is usually called a large page (LARGE PAGES), the large page alignment address refers to a page with a coarse granularity, i.e. a large page comprises a plurality of 4KB pages, the large page alignment can ensure that data can be continuously and efficiently read or written, for example, the large page alignment can reduce the number of page table entries, thereby reducing memory occupation and improving memory access speed, and reducing memory fragmentation, and the non-large page alignment address refers to a starting address of data is not an integer multiple of the bytes of a data unit, the large page alignment address is not limited to the size of a byte, but is not limited to 8 bytes, and the large page alignment address is not limited to 8 bytes, and the logical address is 8 bytes is not limited to the whole number byte is calculated, if the logical address is 8 bytes is 8 byte-8 byte alignment and represents the remainder is not equal to the logical byte address and represents the logical byte alignment, and the logical address 8 byte alignment address is 8 byte.

Step S503, judging whether the logic address is continuous with the logic address in the global bit diagram according to the global bit diagram;

Specifically, if the logical address is a non-large page aligned address, determining whether the logical address is continuous with the logical address in the global bitmap according to the global bitmap, where the global bitmap includes a continuous bitmap, and the continuous bitmap includes a second state and a discontinuous state, if the logical address is continuous with the logical address in the global bitmap, determining the continuous bitmap corresponding to the logical address as the continuous state, and entering step S505, and if the logical address is discontinuous with the logical address in the global bitmap, determining the continuous bitmap corresponding to the logical address as the discontinuous state, and entering step S504.

Step S504, judging whether the continuity of the logic address segment corresponding to the logic address is larger than a continuity threshold value;

Specifically, when the logical address is a large page aligned address or the logical address is discontinuous with the logical address in the global bitmap, it is determined whether the continuity of the logical address segment corresponding to the logical address is greater than a continuity threshold, where the continuity refers to the sum of the numbers of the continuity states in the address segment corresponding to the logical address, if the continuity of the logical address segment corresponding to the logical address is greater than the continuity threshold, step S506 is entered, and if the continuity of the logical address segment corresponding to the logical address is less than or equal to the continuity threshold, step S507 is entered, where in the embodiment of the present application, the continuity threshold may be set according to actual needs, for example, the continuity threshold is set to 7, and it is assumed that the address segment corresponding to the logical address includes 10 logical addresses, where the continuity bitmap of 8 logical addresses is in the continuity state and the continuity bitmap of 2 logical addresses is in the non-continuity state, and if the continuity of the address segment is 8, it is determined that the continuity of the address segment is greater than the continuity threshold.

Step S505, determining the continuous bitmap corresponding to the logical address as a continuous state;

Specifically, if the logical address is a non-large page aligned address and the logical address is continuous with the logical address in the global bitmap, that is, if the logical address is a continuous non-large page aligned address, the continuous bitmap corresponding to the logical address is determined to be in a continuous state, which represents that the logical address is continuous with the previous logical address. In the embodiment of the application, the current logical address and the last logical address can be judged whether to be continuous or not without storing the logical address in a memory space but through a continuous bitmap in a global bit chart, and it can be understood that for continuous addresses, the method can save the memory space of the flash memory device and improve the query efficiency of the physical address by only recording the initial address of each address segment in the global bit chart and recording the second state of other addresses to the continuous bitmap and only knowing the physical address of the last address when the logical address is continuous in the process of querying the physical address, and can realize the compression of the memory by adding 1.

Step S506, inserting the mapping pairs into a compact array;

specifically, if the continuity of the logical address segment corresponding to the logical address is greater than the continuity threshold, the mapping pair corresponding to the logical address is inserted into the compact array to construct the compact array.

Step S507, inserting mapping pairs into a range hash bucket structure;

Specifically, if the continuity of the logical address segment corresponding to the logical address is less than or equal to the continuity threshold, the mapping pair corresponding to the logical address is inserted into the range hash bucket structure to construct the range hash bucket structure.

Step S302, judging whether the logic address is a continuous non-large page alignment address according to the global bit diagram;

Specifically, the non-large page alignment address includes a non-8 byte alignment address, a first state corresponding to the logical address is obtained according to the global bitmap, and the logical address is divided by 8 and the remainder is taken, if the first state corresponding to the logical address is a continuous state and the remainder corresponding to the logical address is not equal to 0, it is determined that the logical address is a continuous non-large page alignment address, step S303 is entered, and otherwise, it is determined that the logical address is not a continuous non-large page alignment address, step S304 is entered.

Step S303, modifying the global bit map to record the logic address in the global bit map;

specifically, if the logical address is a continuous non-large page alignment address, the global bit map is modified, and the second state corresponding to the logical address is modified to be a continuous state, so that the logical address is recorded in the global bit map.

Step S304, judging whether the continuity of the logic address segment corresponding to the logic address is larger than a preset threshold value;

Specifically, it is determined whether the continuity of the logical address segment corresponding to the logical address is greater than a continuity threshold, where the continuity refers to a sum of numbers of continuous states in the address segment corresponding to the logical address, if the continuity of the logical address segment corresponding to the logical address is greater than the continuity threshold, step S306 is entered, and if the continuity of the logical address segment corresponding to the logical address is less than or equal to the continuity threshold, step S305 is entered.

Step S305, inserting the mapping pairs into a range bucket hash structure;

specifically, referring to fig. 6 again, fig. 6 is a schematic diagram of a refinement flow of step S305 in fig. 3;

as shown in fig. 6, step S305, inserting the mapping pair into the range bucket hash structure includes:

step S351, obtaining a global range table;

Specifically, the scope hash bucket structure comprises a global scope table, a scope array and a scope bucket, and the global scope table is obtained, wherein the global scope table is used for storing a mapping pointer corresponding to a logical address segment, and the mapping pointer points to the scope bucket or the scope array.

Step S352, judging whether a mapping pointer corresponding to a logical address segment points to a range bucket according to the global range table;

Specifically, according to the global scope table, it is determined whether the mapping pointer corresponding to the logical address segment points to the scope bucket, if the mapping pointer corresponding to the logical address segment points to the scope bucket, step S354 is performed, and if the mapping pointer corresponding to the logical address segment points to the scope array, step S353 is performed.

Step S353, inserting the mapping pairs into the range array;

specifically, if the mapping pointer corresponding to the logical address segment points to the range array, the mapping pair is inserted into the range array.

Step S354, inserting the mapping pairs into a range bucket;

Specifically, if the mapping pointer corresponding to the logical address segment points to the range bucket, the mapping pair is inserted into the range bucket.

Step S306, inserting the mapping pairs into a compact array;

Specifically, if the continuity of the logical address segment corresponding to the logical address is greater than the continuity threshold, the mapping pair is inserted into the compact array.

Referring to fig. 7 again, fig. 7 is a flow chart for determining whether the capacity of the range bucket reaches the capacity threshold according to an embodiment of the present application;

as shown in fig. 7, the process of determining whether the capacity of the range bucket reaches the capacity threshold includes:

Step S701, after the mapping pair is inserted into the range barrel, the capacity of the range barrel is obtained;

Specifically, after inserting the mapping pairs into the range bucket, the capacity of the range bucket is obtained, where the capacity of the range bucket refers to the number of mapping pairs stored in the range bucket at present/the total number of mapping pairs that the range bucket is capable of storing at most.

Step S702, judging whether the capacity of the range barrel reaches a capacity threshold value or not;

Specifically, it is determined whether the capacity of the range bucket reaches the capacity threshold, if the capacity of the range bucket reaches the capacity threshold, the step S704 is entered, and if the capacity of the range bucket does not reach the capacity threshold, the step S703 is entered, where in the embodiment of the present application, the capacity threshold may be set according to actual needs, for example, the capacity threshold is set to 95%.

Step S703, not splitting the range bucket;

specifically, if the capacity of the range bucket does not reach the capacity threshold, it means that the current range bucket does not need to be split into other data storage structures in the present application, and therefore, the range bucket is not split.

Step S704, judging whether the continuity of the range bucket is larger than a continuity threshold value;

Specifically, if the capacity of the range bucket reaches the capacity threshold, it is further determined whether the continuity of the range bucket is greater than the continuity threshold, if the continuity of the range bucket is greater than the continuity threshold, step S705 is performed, and if the continuity of the range bucket is less than or equal to the continuity threshold, step S706 is performed.

Step S705, the mapping pairs in the range bucket are moved to a compact array;

Specifically, if the continuity of the range bucket is greater than the continuity threshold, the condition of constructing the compact array is satisfied, all mapping pairs in the range bucket are acquired, the mapping pairs are moved to the compact array, and the memory space of the range bucket is released.

Step S706, judging whether the density of the range barrel is larger than a density threshold value;

Specifically, the density of the range bucket is obtained, where the density of the range bucket=the number of valid mapping pairs in the range bucket/the address range of the range bucket, whether the density of the range bucket is greater than a density threshold is determined, if the density of the range bucket is greater than the density threshold, the step S707 is entered, and if the density of the range bucket is less than or equal to the density threshold, the step S708 is entered. In the embodiment of the application, the density threshold may be set according to actual needs, for example, the density threshold is set to be 50%.

Step S707, splitting the range bucket into at least two range arrays;

Specifically, if the density of the range bucket is greater than the density threshold, the range bucket is split into at least two range arrays.

Step S708, splitting the range bucket into at least two range buckets;

specifically, if the density of the range bin is less than or equal to the density threshold, splitting the range bin into at least two range bins.

In the embodiment of the application, when the continuity of the address segments in the range bucket is lower than the continuity threshold, if the density of the range bucket is higher than the density threshold, the current mapping is considered to be the mapping under the random write load, the application adopts the mapping pair corresponding to the address segments which are stored in the range bucket and sparsely allocated, and the mapping pair corresponding to the random write load which is densely allocated is stored in the range array, wherein the sparse allocation refers to the mapping pair with the density smaller than or equal to the density threshold, the dense allocation refers to a mapping pair with density greater than a density threshold, and in the steps S701 to S708, the present application can adaptively change the storage structure of data according to the capacity of the data structure or the density of the mapping pair, and implement conversion among a range bucket, a range array and a compact array, thereby saving the memory space of the flash memory device and improving the memory utilization.

Referring to fig. 8 again, fig. 8 is a schematic flow chart for determining whether the continuity of the compact array is less than or equal to the continuity threshold according to an embodiment of the present application;

as shown in fig. 8, the process of determining whether the continuity of the compact array is less than or equal to the continuity threshold value includes:

Step S801, after mapping pairs are inserted into a compact array, acquiring continuity of the compact array;

specifically, after the mapping pair is inserted into the compact array, the continuity of the current compact array is obtained, wherein the continuity refers to the sum of the numbers of continuous states in the address field corresponding to the compact array.

Step S802, judging whether the continuity of the compact array is smaller than or equal to a continuity threshold value;

specifically, it is determined whether the continuity of the compact array is less than or equal to the continuity threshold, if the continuity of the compact array is less than or equal to the continuity threshold, the step S804 is performed, and if the continuity of the compact array is greater than the continuity threshold, the step S803 is performed.

Step 803, not processing the compact array;

Specifically, if the continuity of the compact array is greater than the continuity threshold, it indicates that the continuity of the compact array meets the conditions for building the compact array, without converting the compact array into other data storage structures, and without processing the compact array.

Step S804, obtaining all mapping pairs of the established mapping relation in the compact array;

specifically, if the continuity of the compact array is less than or equal to the continuity threshold, the current continuity of the compact array does not meet the condition of constructing the compact array, and all mapping pairs with established mapping relationships in the compact array are obtained so as to facilitate the subsequent movement of the mapping pairs.

Step S805, inserting all mapping pairs with established mapping relation into a range bucket, and releasing the memory of the compact array to restore the compact array into the range bucket;

specifically, because when the address segment of the compact array decreases in continuity as a new mapping pair is inserted, the segment may be considered to transition from sequential write load to random write load, it is necessary to store the mapping pair into a range bucket for storing the mapping of random write load, i.e., to insert all mapping pairs for which a mapping relationship has been established into the range bucket, and to free up the memory of the compact array to restore the compact array to the range bucket.

Referring to fig. 9 again, fig. 9 is a flow chart of determining whether the density of the range array is smaller than the density threshold according to an embodiment of the application;

As shown in fig. 9, the process of determining whether the density of the range array is less than the density threshold includes:

Step S901, after inserting the mapping pairs into the range array, obtaining the density of the range array;

specifically, after inserting the mapping pairs into the range array, the density of the range array is obtained, wherein the density of the range array=the number of valid mapping pairs, which refer to the mapping pairs whose first state is the mapping state, per the range of the range array.

Step S902, judging whether the density of the range array is smaller than a density threshold value;

Specifically, it is determined whether the density of the range array is less than a density threshold, if the density of the range array is less than the density threshold, the step S904 is performed, and if the density of the range array is greater than or equal to the density threshold, the step S903 is performed, where the density threshold may be set according to actual needs, for example, the density threshold is set to 50%.

Step S903, not processing the range array;

specifically, if the density of the range array is greater than or equal to the density threshold, it means that the range array does not need to be converted into other data storage structures, and the range array is not processed.

Step S904, obtaining all mapping pairs in the range array;

specifically, if the density of the range array is smaller than the density threshold, the range array satisfies the condition of converting into the range bucket, and all mapping pairs in the range array are acquired, so that the mapping pairs in the range array can be moved to the range bucket later.

Step S905, inserting all mapping pairs in the range array into a range bucket, and releasing the memory of the range array to restore the range array into the range bucket;

Specifically, since the range bucket is used for storing the mapping pairs corresponding to the sparsely allocated address segments, and the range array is used for storing the mapping of the densely allocated random write loads, when the density of the range array is reduced below the density threshold, all the mapping pairs in the range array need to be inserted into the range bucket, and the memory of the range array is released, so that the range array is restored to the range bucket.

Referring to fig. 10 again, fig. 10 is a flowchart illustrating a process of determining whether a continuity of a certain logical address segment in a range bucket is greater than a continuity threshold according to an embodiment of the present application;

as shown in fig. 10, the process of determining whether there is a continuity of a certain logical address segment in the range bucket that is greater than a continuity threshold includes:

Step S1001, after the mapping pair is inserted into the range barrel, obtaining the continuity of the logic address segment in the range barrel;

Specifically, after the mapping pair is inserted into the range bucket, the continuity of each logic address segment in the range bucket is obtained, wherein the continuity is the sum of the numbers of continuous states corresponding to the logic addresses of the logic address segments.

Step S1002, judging whether the continuity of a certain logic address segment in a range bucket is larger than a continuity threshold value;

Specifically, according to the continuity of each logical address segment in the range bucket, it is determined whether the continuity of a certain logical address segment in the range bucket is greater than the continuity threshold, if the continuity of a certain logical address segment in the range bucket is greater than the continuity threshold, the step S1004 is entered, and if the continuity of a certain logical address segment in the range bucket is not greater than the continuity threshold, the step S1003 is entered.

Step S1003, not processing the range bucket;

Specifically, if the continuity of a certain logical address segment in the range bucket is not greater than the continuity threshold, the range bucket is not required to be converted into other data storage structures, and the range bucket is not processed.

Step S1004, obtaining a mapping pair corresponding to the logical address segment;

specifically, if the continuity of a certain logical address segment in the range bucket is greater than the continuity threshold, the logical address segment and a mapping pair corresponding to the logical address segment are obtained.

Step S1005, establishing a compact array for the logical address field, and moving the mapping pair corresponding to the logical address field from the range bucket to the compact array;

Specifically, because the continuity of the logical address segment in the current range bucket meets the condition of constructing the compact array, the compact array is established for the logical address segment, the mapping pair corresponding to the logical address segment is moved from the range bucket to the compact array, and after the movement is completed, the memory space occupied by the range bucket is released.

Step S1006, after the mapping pair corresponding to the logical address segment is moved from the range bucket to the compact array, judging whether the density of the range bucket is smaller than a density threshold;

Specifically, after the mapping pair corresponding to the logical address field is moved from the range bucket to the compact array, the density of the range bucket needs to be further acquired to determine whether the density of the range bucket is less than the density threshold, if the density of the range bucket is less than the density threshold, the step S1008 is entered, and if the density of the range bucket is greater than or equal to the density threshold, the step S1007 is entered, wherein the total number of the mapping pairs of the density=effective number of the range bucket/the maximum capacity of the range bucket.

Step S1007, not processing the range bucket;

Specifically, if the density of the range bin is greater than or equal to the density threshold, the range bin is not processed.

Step S1008, merging the range bucket and the surrounding range buckets into a new range bucket;

specifically, if the density of the range bucket is smaller than the density threshold, it indicates that the density of the current range bucket is too low, and the range bucket needs to be combined, i.e. the range bucket and the surrounding range buckets are combined into a new range bucket.

Referring to fig. 11 again, fig. 11 is an overall flow chart of a method for constructing a hybrid mapping structure according to an embodiment of the present application;

as shown in fig. 11, the overall flow of the method for constructing the hybrid mapping structure includes:

step 1101, obtaining a mapping pair;

Step 1101, judging whether the first state corresponding to the logical address is a mapping state according to the allocation bitmap;

Specifically, the global bitmap is used to query the allocation bitmap corresponding to the logical address, obtain the first state corresponding to the logical address, further determine whether the first state corresponding to the logical address is a mapping state, enter step S1103 if the first state corresponding to the logical address is a non-mapping state, and enter step S1104 if the first state corresponding to the logical address is a mapping state.

Step S1103, modifying the first state corresponding to the logical address into a mapping state;

Specifically, if the first state corresponding to the logical address is the non-mapping state, which indicates that the mapping relationship between the logical address and the physical address is not recorded in the global bitmap, that is, the current first state of the logical address is the non-mapping state, the allocation bitmap in the global bitmap is modified, the first state corresponding to the logical address is modified to the mapping state, for example, if the mapping state is 1 and the non-mapping state is 0, the first state is modified from 0 to 1, so that the mapping relationship between the logical address and the physical address is recorded in the global bitmap, and after the first state corresponding to the logical address is modified to the mapping state, step S1104 is entered.

Step S1104, judging whether the logic address is a continuous non-large page alignment address;

Specifically, it is determined whether the logical address is a continuous non-large page aligned address, if the logical address is a continuous non-large page aligned address, the step S1105 is entered, and if the logical address is not a continuous non-large page aligned address, the step S1106 is entered.

Step S1105, modifying the continuous bitmap corresponding to the logical address into a continuous state;

Specifically, if the logical address is a continuous non-large page aligned address, the continuous bitmap corresponding to the logical address is determined to be in a continuous state, which means that the logical address is continuous with the previous logical address.

Step S1106, judging whether the address segment corresponding to the logical address has established a compact array;

Specifically, if the logical address is not a continuous non-large page aligned address, it is determined whether the address segment corresponding to the logical address has already established a compact array, and step S1107 is entered if the address segment corresponding to the logical address has already established a compact array, and step S1108 is entered if the address segment corresponding to the logical address has not established a compact array.

Step S1107, inserting the mapping pair into a compact array;

specifically, if the address segment corresponding to the logical address has already established a compact array, the mapping pair is directly inserted into the compact array corresponding to the logical address.

Step S1108, judging whether the continuity of the address segment corresponding to the logical address is larger than a continuity threshold value;

Specifically, if the address segment corresponding to the logical address does not establish the compact array, it is determined whether the continuity of the address segment corresponding to the logical address is greater than the continuity threshold, if the continuity of the address segment corresponding to the logical address is greater than the continuity threshold, step S1109 is entered, and if the continuity of the address segment corresponding to the logical address is less than or equal to the continuity threshold, step S1110 is entered.

Step S1109, establishing a compact array for the address field corresponding to the logical address, and inserting the mapping pair into the compact array;

Specifically, if the continuity of the address segment corresponding to the logical address is greater than the continuity threshold, a compact array is established for the address segment corresponding to the logical address, and the mapping pair is inserted into the compact array.

Step S1110, judging whether a mapping pointer corresponding to a logical address segment points to a range bucket according to a global range table;

Specifically, if the continuity of the address segment corresponding to the logical address is less than or equal to the continuity threshold, it is determined according to the global range table whether the mapping pointer corresponding to the logical address segment points to the range bucket, step S1112 is entered if the mapping pointer corresponding to the logical address segment points to the range bucket, and step S1111 is entered if the mapping pointer corresponding to the logical address segment does not point to the range bucket.

Step S1111, inserting the mapping pair into the range array;

Specifically, if the mapping pointer corresponding to the logical address segment does not point to the range bucket, the mapping pair is inserted into the range array.

Step S1112, inserting the mapping pairs into a range bucket;

Step S1113, judging whether the capacity of the range bucket is larger than a capacity threshold;

Specifically, after the mapping pair is inserted into the range bucket, it is determined whether the capacity of the range bucket is greater than a capacity threshold, if the capacity of the range bucket is greater than the capacity threshold, the step S1114 is entered, and if the capacity of the range bucket is less than or equal to the capacity threshold, it indicates that the insertion of the mapping pair is completed.

Step S1114, judging whether the continuity of the range bucket is larger than a continuity threshold value;

specifically, if the capacity of the range bucket is greater than the capacity threshold, it is necessary to further determine whether the continuity of the range bucket is greater than the continuity threshold, if the continuity of the range bucket is greater than the continuity threshold, step S1115 is entered, and if the continuity of the range bucket is less than or equal to the continuity threshold, step S1116 is entered.

Step S1115, establishing a compact array for the logical address field, and moving the mapping pair corresponding to the logical address field from the range bucket to the compact array;

specifically, if the continuity of the range bucket is greater than the continuity threshold, a compact array is established for the logical address segment, and the mapping pair corresponding to the logical address segment is moved from the range bucket to the compact array corresponding to the logical address segment.

Step S1116, judging whether the density of the range barrel is greater than a density threshold value;

specifically, if the continuity of the range bucket is less than or equal to the continuity threshold, it is necessary to further determine whether the density of the range bucket is greater than the density threshold, if the density of the range bucket is greater than the density threshold, the process proceeds to step S1117, and if the density of the range bucket is less than or equal to the density threshold, the process proceeds to step S1118.

Step S1117, splitting a range bucket into a range array;

specifically, if the density of the range bucket is greater than the density threshold, the range bucket is split into a range array.

Step S1118, splitting the range bucket into two range buckets;

Specifically, if the density of the range bin is less than or equal to the density threshold, the range bin is split into two range bins.

The embodiment of the application provides a construction method of a hybrid mapping structure, which comprises a global bit chart, a compact array and a range bucket hash structure, and the method comprises the steps of obtaining a mapping pair, judging whether a logic address is a continuous non-large page alignment address according to the global bit chart, judging whether the continuity of a logic address section corresponding to the logic address is greater than a continuity threshold value if the logic address is not the continuous non-large page alignment address, inserting the mapping pair into the compact array if the continuity of the logic address section is greater than the continuity threshold value, and inserting the mapping pair into the range bucket hash structure if the continuity of the logic address section is less than or equal to the continuity threshold value.

Referring to fig. 12 again, fig. 12 is a flow chart of a physical address query method based on a hybrid mapping structure according to an embodiment of the present application;

as shown in fig. 12, the flow of the physical address query method based on the hybrid mapping structure includes:

step S1201, obtaining a logic address;

Specifically, a logical address is obtained, and the logical address is used for querying a physical address corresponding to the logical address in the hybrid mapping structure.

Step S1202, inquiring whether a logic address has established a mapping relation according to the global bit diagram;

specifically, referring to fig. 13 again, fig. 13 is a schematic diagram of a refinement flow of step S1202 in fig. 12;

as shown in fig. 13, step S1202 of querying whether the logical address has established a mapping relationship according to the global bit map includes:

Step S1221, inquiring an allocation bitmap in the global bitmap to acquire a first state corresponding to the logical address;

Specifically, the hybrid mapping structure includes a global bitmap, where the global bitmap is used to store metadata information corresponding to each logical address segment, the metadata information includes an allocation bitmap, and the allocation bitmap in the global bitmap is queried to obtain a first state corresponding to the logical address, where the first state includes a mapping state and a non-mapping state.

Step S1222, judging whether the first state corresponding to the logic address is a mapping state according to the allocation bitmap;

Specifically, according to the allocation bitmap, whether the first state corresponding to the logical address is a mapping state is judged, wherein the mapping state indicates that a mapping relationship exists between the logical address and a physical address corresponding to the logical address, and the non-mapping state indicates that a mapping relationship does not exist between the logical address and the physical address corresponding to the logical address. If the first state corresponding to the logical address is the mapping state, the process proceeds to step S1214, and if the first state corresponding to the logical address is the non-mapping state, the process proceeds to step S1223.

Step S1223, determining that the logical address does not establish a mapping relation, and outputting a query failure result;

Specifically, if the first state corresponding to the logical address is a non-mapping state, it is determined that a mapping relationship is not established between the logical address and the physical address, and a query failure result is output.

In the embodiment of the application, whether the logic address and the physical address establish the mapping relation or not is firstly inquired through the global bit diagram, when the mapping relation is not established between the logic address and the physical address, the result of inquiry failure is directly output, and the inquiry efficiency of the physical address can be improved, so that a great deal of time is consumed for inquiry when the mapping relation is not established between the logic address and the physical address.

Step S1214, determining that the logical address has established a mapping relationship;

specifically, if the first state corresponding to the logical address is a mapping state, it is determined that a mapping relationship has been established between the logical address and the physical address, and the query steps from S1204 to S1208 are continuously performed.

Step S1203, determining that the logical address does not establish a mapping relationship, and outputting a query failure result;

Specifically, if the first state corresponding to the logical address is a non-mapping state, determining that a mapping relationship is not established between the logical address and the physical address, and outputting a query failure result.

Step S1204, judging whether the logic addresses are continuous;

specifically, referring to fig. 14 again, fig. 14 is a detailed flow chart of step S1204 in fig. 12;

as shown in fig. 14, step S1204, determining whether the logical addresses are consecutive, includes:

step S1241, inquiring a continuous bitmap in the global bitmap to acquire a second state corresponding to the logical address;

Specifically, after the mapping relation between the logical address and the physical address is determined through the allocation bitmap in the global bitmap, the continuous bitmap in the global bitmap is queried according to the global bitmap to obtain a second state corresponding to the logical address, wherein the second state comprises a continuous state or a discontinuous state.

Step S1242, judging whether the second state corresponding to the logic address is a continuous state according to the continuous bitmap;

Specifically, according to the continuous bitmap, it is determined whether the second state corresponding to the logical address is a continuous state, if the second state corresponding to the logical address is a continuous state, step S1244 is performed, and if the second state corresponding to the logical address is a discontinuous state, step S1243 is performed.

Step S1243, determining the logical addresses as discontinuous logical addresses;

specifically, if the second state corresponding to the logical address is a discontinuous state, the second state indicates that the logical address is discontinuous from the previous logical address, and the logical address is determined to be a discontinuous logical address.

Step S1244, determining the logical addresses as continuous logical addresses;

specifically, if the second state corresponding to the logical address is a continuous state, the logical address is continuous with the last logical address, and the logical address is determined as a continuous logical address.

Step S1205, obtaining a physical address corresponding to the logical address through a range bucket hash structure;

Specifically, referring to fig. 15 again, fig. 15 is a schematic diagram of the refinement flow of step S1205 in fig. 12;

As shown in fig. 15, step S1205 includes obtaining, by the range bucket hash structure, a physical address corresponding to the logical address, including:

step S1251, obtaining a global range table;

Step S1252, judging whether a mapping pointer corresponding to a logical address segment points to a range bucket according to the global range table;

Specifically, according to the global range table, it is determined whether the mapping pointer corresponding to the logical address segment points to the range bucket, if the mapping pointer corresponding to the logical address segment points to the range bucket, step S1254 is performed, and if the mapping pointer corresponding to the logical address segment points to the range array, step S1253 is performed.

Step S1253, obtaining the physical address corresponding to the logical address in the range array;

Specifically, if the mapping pointer corresponding to the logical address segment points to the range array, the mapping pointer indicates that the physical address corresponding to the logical address is stored in the range array, and the physical address corresponding to the logical address is obtained in the range array.

Step S1254, obtaining the physical address corresponding to the logical address in the range bucket;

specifically, if the mapping pointer corresponding to the logical address segment points to the range bucket, the mapping pointer indicates that the physical address corresponding to the logical address is stored in the range bucket, and the physical address corresponding to the logical address is obtained in the range bucket.

Step S1206, traversing the global bit diagram to obtain a start logic address of an address segment corresponding to the logic address;

specifically, if the logical addresses are continuous, the global bit map is traversed forward according to the logical addresses, so as to obtain the initial logical address of the address segment corresponding to the logical address.

Step S1207, judging whether the initial logical address is a large page alignment address;

Specifically, it is determined whether the initial logical address is a large page aligned address, if the initial logical address is a large page aligned address, the step S1208 is entered, if the initial logical address is not a large page aligned address, the step S1205 is entered, in which in the embodiment of the present application, the large page aligned address is an integer multiple of the number of bytes of the data unit, so that the data can be read or written continuously and efficiently, whereas the non-large page aligned address is an integer multiple of the number of bytes of the data unit, the large page aligned address includes but is not limited to an 8-byte aligned address, for example, if it is determined whether the logical address is an 8-byte aligned address, the logical address is divided by 8, and a remainder is obtained, if the remainder is not equal to 0, the logical address is a non-8-byte aligned address, and if the remainder is equal to 0, the logical address is represented as an 8-byte aligned address.

Step S1208, obtaining a physical address corresponding to the logical address through the compact array;

Specifically, if the initial logical address is a large page alignment address, the physical address corresponding to the logical address is obtained through the compact array.

Referring to fig. 16 again, fig. 16 is a flowchart illustrating a method for determining whether an address field has established a compact array according to an embodiment of the present application;

as shown in fig. 16, the process of determining whether the address field has established a compact array includes:

step S1601, obtaining an address field corresponding to the logical address;

Specifically, before the physical address is queried through the compact array, an address segment corresponding to the logical address is acquired according to the logical address.

Step S1602, judging whether the address field has established a compact array;

Specifically, it is determined whether the compact array has been established in the logical address segment corresponding to the logical address, if the compact array has been established in the logical address segment corresponding to the logical address, the step S1604 is performed, and if the compact array has not been established in the logical address segment corresponding to the logical address, the step S1603 is performed.

Step S1603, obtaining a physical address corresponding to the logical address through a range bucket hash structure;

Specifically, the scope hash bucket structure comprises a global scope table, a scope array and a scope bucket, and the global scope table is obtained, wherein the global scope table is used for storing a mapping pointer corresponding to a logical address segment, and the mapping pointer points to the scope bucket or the scope array. Judging whether a mapping pointer corresponding to a logic address segment points to a range bucket according to a global range table, if the mapping pointer corresponding to the logic address segment points to the range bucket, inquiring a physical address corresponding to the logic address through the range bucket, and if the mapping pointer corresponding to the logic address segment points to a range array, inquiring the physical address corresponding to the logic address through the range array.

Step S1604, obtaining a physical address corresponding to the logical address through the compact array;

Specifically, if the compact array is established in the logical address segment corresponding to the logical address, the physical address corresponding to the logical address is obtained through the compact array.

Referring to fig. 17 again, fig. 17 is an overall flow chart of a physical address query method based on a hybrid mapping structure according to an embodiment of the present application;

As shown in fig. 17, the overall flow of the physical address query method based on the hybrid mapping structure includes:

Step S1701, obtaining a logic address;

Step S1702, inquiring whether a logic address has established a mapping relation according to a global bit chart;

specifically, according to the allocation bitmap in the global bitmap, whether the logical address has established a mapping relationship is queried, if the logical address has established a mapping relationship, the step S1704 is entered, and if the logical address has not established a mapping relationship, the step S1703 is entered.

Step S1703, determining that the logical address does not establish a mapping relation, and outputting a query failure result;

Specifically, if the logical address does not establish the mapping relationship, determining that the logical address does not establish the mapping relationship, and outputting a query failure result.

Step S1704, judging whether the logic addresses are continuous;

Specifically, if the logical address has established a mapping relationship, it is further determined whether the logical address is consecutive to the previous logical address, if the logical address is consecutive to the previous logical address, the step S1705 is entered, and if the logical address is not consecutive to the previous logical address, the step S1708 is entered.

Step S1705, traversing the global bit diagram to obtain a starting logical address of an address segment corresponding to the logical address;

Specifically, if the logical address is continuous with the last logical address, the global bit map is traversed to obtain the initial logical address of the address segment corresponding to the logical address.

Step S1706, judging whether the initial logical address is a large page alignment address;

specifically, it is determined whether the initial logical address is a large page alignment address, where the large page alignment address includes an 8-byte alignment address, if the initial logical address is a large page alignment address, the step S1707 is entered, and if the initial logical address is not a large page alignment address, the step S1708 is entered.

Step S1707, obtaining a physical address corresponding to the logical address through the compact array;

Step S1708, obtaining a global range table;

specifically, when the logical address is discontinuous with the last logical address or the initial logical address is not a large page alignment address, a global range table is obtained to inquire a physical address corresponding to the logical address through a range hash bucket structure.

Step S1709, judging whether a mapping pointer corresponding to a logical address segment points to a range bucket according to the global range table;

Specifically, according to the global scope table, it is determined whether the mapping pointer corresponding to the logical address segment points to the scope bucket, if the mapping pointer corresponding to the logical address segment points to the scope bucket, step S1710 is performed, and if the mapping pointer corresponding to the logical address segment does not point to the scope bucket, step S1711 is performed.

Step S1710, obtaining a physical address corresponding to the logical address in the range bucket;

specifically, if the mapping pointer corresponding to the logical address segment points to the range bucket, the physical address corresponding to the logical address is obtained in the range bucket.

Step S1711, obtaining a physical address corresponding to the logical address in the range array;

Specifically, if the mapping pointer corresponding to the logical address segment does not point to the range bucket, the physical address corresponding to the logical address is obtained in the range array.

In the embodiment of the application, by providing a physical address query method based on a hybrid mapping structure, the hybrid mapping structure comprises a global bit chart, a compact array and a range bucket hash structure, the method comprises the steps of obtaining a logic address; according to the global bit diagram, whether the logic addresses have a mapping relation is inquired, if the logic addresses have the mapping relation, whether the logic addresses are continuous is judged, if the logic addresses are continuous, the global bit diagram is traversed to obtain initial logic addresses of address segments corresponding to the logic addresses, if the initial logic addresses are large page alignment addresses, physical addresses corresponding to the logic addresses are obtained through a compact array, and if the logic addresses are discontinuous, physical addresses corresponding to the logic addresses are obtained through a range bucket hash structure.

In the embodiment of the application, the implementation main bodies of the construction method of the hybrid mapping structure and the physical address query method based on the hybrid mapping structure are flash memory devices, and specifically, the flash memory device controller controls the flash memory devices to execute the construction method of the hybrid mapping structure or each method step in the physical address query method based on the hybrid mapping structure, the flash memory devices comprise solid state disks or other storage devices taking flash memory media as storage media, and the flash memory device controller comprises controllers of the solid state disks or other storage devices taking the flash memory media as storage media.

Referring to fig. 18 again, fig. 18 is a schematic structural diagram of a flash memory controller according to an embodiment of the present application;

as shown in fig. 18, the flash controller 180 includes one or more processors 181 and memory 182. In fig. 18, a processor 181 is taken as an example.

The processor 181 and memory 182 may be connected by a bus or otherwise, for example in fig. 18.

The processor 181 is configured to provide computing and control capabilities to control the flash memory controller 180 to perform corresponding tasks, for example, control the flash memory controller 180 to perform the method for constructing a hybrid mapping structure in any of the method embodiments described above, where the hybrid mapping structure includes a global bit map, a compact array, and a range bucket hash structure, and the method includes obtaining a mapping pair, where the mapping pair includes a logical address and a physical address corresponding to the logical address, determining whether the logical address is a continuous non-large page aligned address according to the global bit map, determining whether a continuity of a logical address segment corresponding to the logical address is greater than a continuity threshold if the logical address is not the continuous non-large page aligned address, inserting the mapping pair into the compact array if the continuity of the logical address segment is greater than the continuity threshold, and inserting the mapping pair into the range bucket hash structure if the continuity of the logical address segment is less than or equal to the continuity threshold, and obtaining a logical address based on the physical address query method of the hybrid mapping structure, where the hybrid mapping structure includes the global bit map, the compact array, and the range bucket hash structure, determining whether the logical address is a continuous non-large page aligned address according to the global bit map, determining whether the logical address is a continuous non-large page aligned address, determining whether the logical address is obtained by the logical address corresponding to the logical address if the logical address has been established when the logical address has been obtained by the logical address, and if the logical address has been obtained by the logical address corresponding to the logical address, and if the logical address has been established by the logical address.

The application can store the mapping pairs by adopting a mixed mapping structure combining three data structures of a global bit chart, a compact array and a range hash bucket structure, can optimize the memory overhead of the flash memory device, can save the memory under a pure sequence read-write scene, can keep the performance of the array under a pure random read-write scene, and can query the physical address corresponding to the logical address by adopting the mixed mapping structure, thereby improving the query efficiency of the physical address.

The processor 181 may be a general purpose processor including a central processing unit (Centra lProcess I ng Un it, CPU), a network processor (Network Processor, NP), a hardware chip, or any combination thereof, a digital signal processor (DI GITA L SI GNA lProcess I ng, DSP), an application specific integrated circuit (APP L I CAT I on SPEC I F I C I NTEGRATED CI rcu it, AS ic), a programmable logic device (programmab l e l ogi C devi ce, PLD), or a combination thereof. The PLD may be a complex programmable logic device (comp l ex programmab l el ogi c dev i ce, CPLD), a field programmable gate array (f iel d-programmab L EGATE ARRAY, FPGA), general array logic (GENER I C ARRAY L ogi c, GAL), or any combination thereof.

The memory 182, as a non-transitory computer readable storage medium, may be used to store a non-transitory software program, a non-transitory computer executable program, and a module, such as a program instruction/module corresponding to a method for constructing a hybrid mapping structure or a physical address query method based on the hybrid mapping structure in an embodiment of the present application. The processor 181 may implement the method of constructing the hybrid mapping structure in any of the above method embodiments, or the physical address query method based on the hybrid mapping structure, by running non-transitory software programs, instructions, and modules stored in the memory 182. Specifically, the memory 182 may include volatile memory (vo l at i l e memory, VM), such as random access memory (random access memory, RAM), nonvolatile memory (non-vo l at i l e memory, NVM), such as read-on-l-y memory (ROM), flash memory (f l ash memory), hard disk (HARD D I SK DR I VE, HDD) or solid state disk (so l i d-STATE DR I VE, SSD), or other non-transitory solid state storage device, and the memory 182 may also include combinations of the above types of memory.

The memory 182 may include high-speed random access memory, but may also include non-volatile memory, such as at least one magnetic disk storage device, flash memory device, or other non-volatile solid-state storage device. In some embodiments, memory 182 may optionally include memory located remotely from processor 181, such remote memory being connectable to processor 181 through a network. Examples of such networks include, but are not limited to, the internet, intranets, local area networks, mobile communication networks, and combinations thereof.

One or more modules are stored in the memory 182 that, when executed by the one or more processors 111, perform the method of building a hybrid map structure, or the method of querying a physical address based on a hybrid map structure, of any of the method embodiments described above.

In the embodiment of the present application, the flash memory controller 180 may further have a wired or wireless network interface, a keyboard, an input/output interface, and other components for implementing the functions of the device, which are not described herein.

The embodiment of the application also provides a computer readable storage medium, such as a memory including program code, where the program code is executable by a processor to complete the method for constructing the hybrid mapping structure in the embodiment, or the method for querying the physical address based on the hybrid mapping structure. For example, the computer readable storage medium may be Read-On l yMemory (ROM), random access Memory (Random Access Memory, RAM), compact disk (Compact Di sc Read-On y Memory, CDROM), magnetic tape, floppy disk, optical data storage device, and the like.

Referring to fig. 19 again, fig. 19 is a schematic structural diagram of a flash memory device according to an embodiment of the application.

As shown in fig. 19, the flash memory device 100 includes a flash memory medium 110 and a flash memory device controller 110 connected to the flash memory medium 110. The flash memory device 100 is in communication connection with the host 200 through a wired or wireless manner, so as to implement data interaction.

Wherein the flash memory device controller 180 includes:

at least one processor 181, and

A memory 182 communicatively coupled to the at least one processor 181, wherein,

The memory 182 is used for storing instructions executable by the at least one processor 181 for enabling the at least one processor to perform the above-described method of constructing a hybrid map structure or the method of querying a physical address based on the hybrid map structure.

The flash memory medium 110, which is a storage medium of the flash memory device 100, is also called a flash memory, an F1 ash memory, or an F1 ash granule, belongs to one type of storage device, is a nonvolatile memory, and can store data for a long time even without current supply, and its storage characteristic is equivalent to a hard disk, so that the flash memory medium 110 becomes a base of storage media of various portable digital devices.

The flash memory medium 110 may be NAND FLASH, NAND FLASH a memory cell using a single transistor as a binary signal, and has a structure very similar to that of a common semiconductor transistor, wherein the single transistor of NAND FLASH is added with a floating gate and a control gate, the floating gate is used for storing electrons, the surface of the floating gate is covered by a layer of silicon oxide insulator and is coupled with the control gate through a capacitor, when negative electrons are injected into the floating gate under the action of the control gate, the storage state of a single crystal of NAND FLASH is changed from "1" to "0", and when the negative electrons are removed from the floating gate, the storage state is changed from "0" to "1", and the insulator covered on the surface of the floating gate is used for trapping the negative electrons in the floating gate, so that data storage is realized. I.e., NAND FLASH are floating gate transistors, which are used to store data in the form of electrical charges. The amount of charge stored is related to the magnitude of the voltage applied by the floating gate transistor.

One NAND FLASH includes at least one Chip, each Chip is composed of a plurality of Bl lock physical blocks, each block physical block includes a plurality of Page pages. The B l lock physical block is the minimum unit for performing the erase operation NAND FLASH, the Page is the minimum unit for performing the read/write operation NAND FLASH, and the capacity of one NAND FLASH is equal to the number of B l lock physical blocks of the B l lock physical block and the number of Page pages contained in the B l lock physical block. Specifically, the flash memory medium 10 can be classified into SLC, MLC, TLC and QLC according to different levels of voltages of memory cells.

The embodiment of the application also provides a non-volatile computer readable storage medium, such as a memory including program code, where the program code is executable by a processor to complete the method for constructing the hybrid mapping structure in the embodiment, or the method for querying the physical address based on the hybrid mapping structure. For example, the non-volatile computer readable storage medium may be a Read-only Memory (ROM), a random access Memory (Random Access Memory, RAM), a Read-only optical disk (Compact Di sc Read-only Memory, CDROM), a magnetic tape, a floppy disk, an optical data storage device, and the like.

Embodiments of the present application also provide a computer program product comprising one or more program codes stored in a non-volatile computer-readable storage medium. The processor of the flash memory device reads the program code from the non-volatile computer readable storage medium, and the processor executes the program code to complete the method of constructing the hybrid map structure or the method steps of the physical address query method based on the hybrid map structure provided in the above-described embodiment. It will be appreciated by those of ordinary skill in the art that all or part of the steps of implementing the above embodiments may be implemented by hardware, or may be implemented by program code related hardware, and the program may be stored in a non-volatile computer readable storage medium, where the storage medium may be a read only memory, a magnetic disk or optical disk, etc.

Claims

1. The utility model provides a method for constructing a hybrid mapping structure, which is characterized in that the hybrid mapping structure comprises a global bit chart, a compact array and a range bucket hash structure, wherein the range bucket hash structure comprises a global range table, a range bucket and a range array, the global range table is used for storing mapping pointers corresponding to logical address segments, and the method comprises the following steps:

if the continuity of the logical address segment is greater than a continuity threshold, inserting the mapping pair into the compact array;

If the continuity of the logical address segment is smaller than or equal to a continuity threshold, inserting the mapping pair into the range bucket hash structure;

the inserting the mapping pair into a range bucket hash structure includes:

Judging whether a mapping pointer corresponding to the logical address segment points to the range bucket according to the global range table;

And if the mapping pointer corresponding to the logical address segment does not point to the range bucket, inserting the mapping pair into the range array.

2. The method of claim 1, wherein the global bitmap is used to store metadata information corresponding to each logical address segment, the metadata information including continuity, the metadata information further including an allocation bitmap, the allocation bitmap being used to store a first state of a logical address, the first state including a mapped state and a non-mapped state, the method further comprising:

And if the first state corresponding to the logical address is a non-mapping state, modifying the first state corresponding to the logical address into a mapping state.

3. The method of claim 2, wherein the metadata information further comprises a continuous bitmap for storing a second state of logical addresses, the second state comprising a continuous state and a discontinuous state, the determining whether the logical addresses are continuous non-large page aligned addresses according to the global bitmap comprising:

Judging whether the logic address is a non-large page alignment address;

And if the logic address is continuous with the logic address in the global bit map, determining the continuous bit map corresponding to the logic address as a continuous state.

4. The method of claim 1, wherein after inserting the mapping pairs into the range bucket, the method further comprises:

if the capacity of the range bucket reaches a capacity threshold, judging whether the continuity of the range bucket is larger than the continuity threshold;

If the continuity of the range bucket is smaller than or equal to the continuity threshold, judging whether the density of the range bucket is larger than a density threshold;

splitting the range bin into at least two range bins if the density of the range bins is less than or equal to the density threshold;

if the density of the range bucket is greater than the density threshold, splitting the range bucket into at least two range arrays.

5. The method according to claim 1, wherein the method further comprises:

And inserting all the mapping pairs with the established mapping relation into the range bucket, and releasing the memory of the compact array to restore the compact array into the range bucket.

6. The method of claim 1, wherein after inserting the mapping pairs into the range array, the method further comprises:

if the density of the range array is smaller than the density threshold, acquiring all mapping pairs in the range array;

7. The method of claim 1, wherein after inserting the mapping pairs into the range bucket, the method further comprises:

If the continuity of a certain logic address segment in the range bucket is larger than the continuity threshold, acquiring the logic address segment and a mapping pair corresponding to the logic address segment;

establishing a compact array for the logical address field, and moving mapping pairs corresponding to the logical address field from the range bucket to the compact array;

8. A physical address query method based on a hybrid mapping structure, wherein the hybrid mapping structure includes a global bitmap, a compact array, and a range bucket hash structure, the range bucket hash structure includes a global range table, a range bucket, and a range array, and the global range table is used for storing mapping pointers corresponding to logical address segments, the method includes:

Obtaining a logic address;

If the logical addresses have established a mapping relation, judging whether the logical addresses are continuous or not;

If the logical addresses are continuous, traversing the global bit chart to obtain the initial logical address of the address segment corresponding to the logical address;

if the logical addresses are discontinuous, acquiring physical addresses corresponding to the logical addresses through the range bucket hash structure;

The obtaining, through the range bucket hash structure, the physical address corresponding to the logical address includes:

And if the mapping pointer corresponding to the logical address segment does not point to the range bucket, acquiring a physical address corresponding to the logical address from the range array.

9. The method of claim 8, wherein the global bitmap is configured to store metadata information corresponding to each logical address segment, the metadata information including an allocation bitmap, the allocation bitmap being configured to store a first state of a logical address, the first state including a mapped state and a non-mapped state, the determining whether the logical address has established a mapping relationship, comprising:

10. The method of claim 9, wherein the metadata information further comprises a continuous bitmap for storing a second state of a logical address, the second state comprising a continuous state and a discontinuous state, the determining whether the logical address is continuous comprising:

and if the second state corresponding to the logic address is a discontinuous state, determining the logic address as a discontinuous logic address.

11. The method of claim 8, wherein prior to obtaining the physical address corresponding to the logical address by the compact array, the method further comprises:

Judging whether the address field has established a compact array;

and if the address segment does not establish a compact array, acquiring a physical address corresponding to the logical address through the range bucket hash structure.

12. A flash memory device controller, comprising:

at least one processor, and

A memory communicatively coupled to the at least one processor, wherein,

The memory stores instructions executable by the at least one processor to enable the at least one processor to perform the method of building a hybrid mapping structure as claimed in any one of claims 1 to 7 or the method of physical address querying based on a hybrid mapping structure as claimed in any one of claims 8 to 11.

13. A flash memory device, comprising:

the flash memory device controller of claim 12;