CN103049388B - Compression management method and device for paging memory device - Google Patents

Abstract

The invention is suitable for the technical field of memories, and provides a compression management method and a device of a paging memory device, wherein the method comprises the following steps: establishing a dictionary by taking a page as a unit, wherein page data, feature codes corresponding to the page data and physical page addresses written by the page data are recorded in the dictionary; acquiring a write command, wherein the write command comprises page data to be written and a logical page address written by the page data to be written; acquiring feature codes of page data to be written, and judging whether feature codes identical to the acquired feature codes exist in the dictionary or not; if not, executing the write command, and writing the page data to be written according to the logical page address written by the page data to be written; if so, not executing the write command, and pointing the logical page address written by the page data to be written to the physical page address written by the page data with the same feature code as the page data to be written. The invention can effectively solve the management problem of the memory device taking the page as the minimum memory unit.

Description

Compression management method and device for paging memory device

technical field

The invention belongs to the technical field of memory, and in particular relates to a compression management method and device for a paging memory device.

Background technique

The current common data compression methods include lossless data compression and lossy data compression, such as compression technology based on statistical model and compression technology based on dictionary model are lossless data compression technology; multimedia data compression includes audio compression, image compression, video compression, etc. Most of them are lossy data compression techniques; for storage devices, lossless data compression methods must be used.

Existing lossless data compression methods include:

One, the dictionary type data compression method, as shown in table 1:

Index String 1 Prince 2 love 3 Princess 4 Forever

Table 1

For example, need to compress Yes! PrincelovePrincessforever gets the compression result according to the dictionary provided in Table 1:

Yes! &1&2&3&4 (where & is a special symbol, if you need to output &, the compressed data is &&)

Disadvantages: The size and quality of the dictionary directly affect the compression results. A large dictionary has a large overhead, and a small dictionary cannot meet the compression requirements. For example, the dictionary compression Iamhappytoday! provided in Table 1 cannot be compressed at all.

2. Run-length encoding data compression method

The basic principle of run-length encoding is to replace consecutive symbols with the same value by a symbol value or string length (consecutive symbols constitute a continuous "run"), so that the symbol length is less than the length of the original data. When the code of each row or column of data changes, the code and the number of repetitions of the same code are recorded at one time, so as to realize data compression.

For example: 5555557777733322221111111

The run-length encoding is: (5, 6) (7, 5) (3, 3) (2, 4) (1, 7). It can be seen that the number of bits of the run-length encoding is far less than that of the original string.

However, not all run-length encodings have far fewer digits than the original string, for example: 555555 is 6 characters, and (5,6) is 5 characters, which also has a problem with the amount of compression. In addition, the compressed encoding of random data by run-length encoding may be larger than that without compression.

3. Huffman-type data compression method

The existing Huffman-type data compression method needs to construct a Huffman tree when performing data compression, and the space overhead is too large. Moreover, the length after compression is a variable value, which is not convenient for storage devices with pages as the minimum storage unit. For example, when compressing 8k data, it may be 7.5k after compression. For storage devices with pages as the minimum storage unit Say, if its page size is 8k, the remaining 0.5k after compression is basically unusable.

To sum up, the existing data compression methods have the following problems: (1) The computational overhead is too large or the storage space requirements are too high; (2) The compression effect cannot be guaranteed; (3) The compression result is not easy to use as a page. Storage device management of the smallest storage unit.

Contents of the invention

The purpose of the embodiments of the present invention is to provide a compression management method for a paging storage device, so as to solve the problem that the existing compression management method requires too much computing overhead or too high storage space requirements, the compression effect cannot be guaranteed, and the compression result is not easy to use A problem of memory device management in which a page is the smallest memory unit.

The embodiment of the present invention is implemented in this way, a compression management method of a paging storage device, the method comprising:

Step A, establish a dictionary with the page as a unit, and record page data, the feature code corresponding to the page data, and the physical page address where the page data is written in the dictionary;

Step B, obtain a write command, the write command includes the page data to be written and the logical page address of the page data to be written; obtain the feature code of the page data to be written, and determine whether the dictionary contains There is a feature code identical to the acquired feature code; if not, execute the write command, write the page data to be written according to the logical page address written in the page data to be written; if so, do not execute the The write command directs the logical page address of the page data to be written to the physical page address of the page data having the same feature code as the page data to be written.

Another object of the embodiments of the present invention is to provide a compression management device for a paging storage device, the device comprising:

A dictionary building unit, configured to create a dictionary in units of pages, where page data, feature codes corresponding to the page data, and physical page addresses where the page data is written are recorded in the dictionary;

A processing unit, configured to obtain a write command, the write command includes the page data to be written and the logical page address of the page data to be written; obtain the feature code of the page data to be written, and judge the dictionary Whether there is the same feature code as the acquired feature code in the system; if not, execute the write command, and write the page data to be written according to the logical page address written by the page data to be written; if so, do not Executing the write command, pointing the logical page address of the page data to be written to the physical page address of the page data having the same feature code as the page data to be written.

It can be seen from the above technical solutions that the smallest unit of data compression in the embodiment of the present invention is a page, the data in the page is not compressed and decompressed, and the writing and reading of data is also based on the page, so the embodiment of the present invention provides The compression management method is very suitable for paging storage devices with insufficient computing power or low cost. Moreover, in the compression management method provided by the embodiment of the present invention, if the data to be written in the current write command has been stored in the dictionary, the data will not be written, so the data writing efficiency of the paging storage device can be effectively improved, and the writing of data can be reduced. The number of entries, thereby reducing the wear and tear of paging memory devices.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the following will briefly introduce the accompanying drawings that need to be used in the descriptions of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only of the present invention. For some embodiments, those of ordinary skill in the art can also obtain other drawings based on these drawings without paying creative efforts.

FIG. 1 is a flow chart for realizing the compression management method of a paging storage device provided by Embodiment 1 of the present invention;

FIG. 2 is a flow chart for realizing the compression management method of the paging storage device provided by Embodiment 2 of the present invention;

Fig. 3 is a flow chart of realizing the compression management method of the paging storage device provided by the third embodiment of the present invention;

FIG. 4 is a structural diagram of an apparatus for managing compression of a paging storage device according to Embodiment 4 of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

In order to illustrate the technical solutions of the present invention, specific examples are used below to illustrate.

Embodiment one:

Fig. 1 shows the implementation flow of the paging storage device compression management method provided by Embodiment 1 of the present invention, and the process of the method is described in detail as follows:

In step S101, a page is used as a unit to establish a dictionary, and information such as page data, a feature code corresponding to the page data, and a physical page address in which the page data is written is recorded in the dictionary.

In this embodiment, the paged storage device is a storage device with a page as the smallest storage unit, that is, a storage device that is erased by block and read and written by page, such as a flash memory device. The page data is data stored in the page.

In step S102, a write command is acquired, and the write command includes information such as page data to be written and a logical page address to be written into the page data to be written.

In step S103, the feature code of the page data to be written is obtained, and it is judged whether there is a feature code identical to the acquired feature code in the dictionary, if the judgment result is "Yes", step S105 is executed, If the result is "no", execute step S104.

In this embodiment, the feature code of the page data to be written is acquired, the acquired feature code is compared with all the feature codes in the dictionary, and it is judged whether there is a feature code identical to the acquired feature code in the dictionary. If the feature code is yes, it means that the page data to be written in the current write command has been stored in the dictionary, and step S105 is executed; if not, step S104 is executed.

In this embodiment, the feature codes of the page data to be written and the feature codes of the page data in the dictionary can be obtained using the same algorithm. Preferably, it is obtained through a hash algorithm. Of course, other algorithms can also be used to obtain, which is not used to limit the present invention.

Hash (Hash) algorithm belongs to the message extraction of a large data, to obtain the feature code of the data, mainly used for password verification and data integrity verification, but also can be used to quickly determine whether two pieces of data are the same.

Take the MD5 hash algorithm as an example, such as the following pieces of data in Table 2:

page data MD5 value 1234567890abcdefg 7206ddfa511b6ab05734b603c1b88be6 2234567890abcdefg 628cb0947d31075fa305699029ddfecc 0234567890abcdefg df9e94f848b6608dd2af317b693744ba 1234567890abcdefgh ad91a28a12e83ce4999b23260f7785c3 1234567890abcdef 996ce17f6abc9fe126b57aa5f1d8c92c 1234567890abcdefg 7206ddfa511b6ab05734b603c1b88be6

Table 2

As can be seen from Table 2, even if the page data changes only a little, the feature code calculated by the hash algorithm will change greatly. Therefore, using the hash algorithm to calculate the feature code can reduce the repetition rate.

In step S104, the write command is executed, and the page data to be written is written according to the logical page address written by the page data to be written, that is, the page data to be written is stored in the logical address corresponding physical address.

In step S105, the write command is not executed, and the logical page address of the page data to be written is pointed to the physical page address of the page data having the same feature code as the page data to be written.

In this embodiment, when the page data to be written in the write command has been written before, that is, when it already exists in the paging storage device, the write command is not executed, and only the page data to be written The written logical page address points to the physical page address written by the page data having the same feature code as the page data to be written, and reminds the user that the data has been written, so the data writing of the paging memory device can be effectively improved Efficiency, reducing the number of data writes, thereby reducing the wear and tear of paging storage devices.

It should be noted that the page data address recorded in the dictionary described in this embodiment is a physical page address, but it can also be a logical page address, and the page data to be written in the write command has been written out of date before, and only the current The write logical page address of the page data to be written in the write command may point to the logical page address of the original data with the same feature code. In addition, when a logical page address is recorded, it is necessary to convert the logical page address into a physical page address when reading data.

As another preferred embodiment of the present invention, in order to reduce the code repetition rate, the feature code of the page data to be written in the write command is obtained, and it is judged whether there is a feature code identical to the acquired feature code in the dictionary; if No, execute the write command, write the page data to be written according to the logical page address written in the page data to be written; if so, do not execute the write command, write the page data to be written The imported logical page address points to the physical page address written into the page data having the same feature code as the page data to be written specifically includes:

When the paging storage device supports a variety of hash algorithms, perform multiple message excerpts on the page data to be written in the current write command, obtain the feature code after each message excerpt, and judge whether there is a corresponding feature code in the dictionary The feature code after each message excerpt is the same feature code, if not, execute the current write command, and write the page data to be written according to the logical page address of the page data to be written in the current write command; if , the write command is not executed, and the logical page address of the page data to be written in the current write command is pointed to the physical page address of the page data having the same feature code as the page data to be written, wherein the The dictionary records the feature code after multiple message excerpts of the page data;

Or, when the paging storage device supports a hash algorithm, multiple message excerpts with different offsets are performed on the page data to be written in the current write command, and the feature code after each excerpted message with different offsets is obtained, Judging whether there is a feature code in the dictionary that is the same as the feature code extracted from each different offset message, if not, execute the current write command, and write the logical page according to the page data to be written in the current write command The address is written to the page data to be written; if so, the write command is not executed, and the logical page address to be written in the page data to be written in the current write command is directed to the same feature code as the page data to be written The address of the physical page where the page data is written, wherein the dictionary records the feature code after extracting multiple different offset messages of the page data;

Or, when the paging storage device supports error checking and correcting ECC codes, obtain the ECC codes of the page data to be written in the current write command and the feature codes after message excerpts, and judge whether the ECC codes and ECC codes exist in the dictionary at the same time. The feature code after the message is extracted, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if not, do not execute the write command, Point the logical page address written in the page data to be written in the current write command to the physical page address written in the page data having the same feature code as the page data to be written, wherein the ECC of the page data is recorded in the dictionary Code and message excerpted feature code;

Or, obtain the feature code of the page data to be written in the current write command, and when there is a feature code identical to the acquired feature code in the dictionary, judge that the N bytes in the page data to be written are consistent with the Whether the N bytes in the page data corresponding to the same feature code in the dictionary are all the same, if not, execute the current write command, and write the to-be-written Enter the page data; if, do not execute the write command, the logical page address of the page data to be written in the current write command is directed to the physical page written by the page data with the same feature code as the page data to be written address, wherein the N is an integer greater than zero and less than or equal to the size of a page in the paging memory, that is, if the page size in the paging memory is 8k bytes, then the N is less than or equal to 8k bytes. It should be noted that, in order not to affect the data compression efficiency, the above comparison process may be implemented by using a hardware comparator.

Preferably, in order to ensure that the efficiency of data compression can be further improved in the case of a large dictionary, the feature code of the page data to be written in the said acquisition write command is determined to determine whether there is a feature code corresponding to the acquired data in the dictionary. The same feature code of the feature code; if not, execute the write command, write the page data to be written according to the logical page address written in the page data to be written; if not, execute the write command, and write The logical page address written in the page data to be written points to the physical page address written in the page data having the same feature code as the page data to be written specifically includes:

Obtain the feature code of the page data to be written in the current write command, perform message extraction on the feature code to obtain a secondary extraction value, and determine whether the secondary extraction value exists in the dictionary, and if so, determine the dictionary Whether there is the feature code in, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if so, do not execute the write command Pointing the logical page address of the page data to be written in the current write command to the physical page address of the page data having the same feature code as the page data to be written, wherein the dictionary records the corresponding page data The secondary excerpt value of the signature. Wherein, the second extraction value is smaller than the size of the feature code and within the allowable range of the repetition rate.

In this embodiment, a feature code table and a secondary extraction value table are established in advance, and the feature code table and the secondary extraction value table are respectively used to record the feature code of the page data and the secondary extraction value of the feature code. Since it is only necessary to match the secondary extraction value table with a small amount of data at the beginning, only when the same secondary extraction value appears, it is necessary to compare the feature code table with a large amount of data. Therefore, the matching efficiency can be greatly improved, and then the Data compression efficiency.

The following is an example to illustrate in detail:

In the case of a large dictionary, for example, there are 1024 pages, and the signature code generated after using the hash algorithm to extract the message on each page is 32 bytes, and the generated signature table has 1024×32 bytes. Searching within range requires high system hardware. Therefore, the second extraction is performed on the feature code table, and the value after the second extraction is much smaller than 32 bytes, and is within the allowable range of the repetition rate, as shown in Table 3.

Raw data signature value secondary excerpt value 555555555555555555 130668ae34911a14e4288367b071447a 130668ae aaaaaaaaaaaaaaaaaaaaa 22d42eb002cefa81e9ad604ea57bc01d 22d42eb0 000000000000000000 3ea032bf79e8c116b05f4698d5a8e044 3ea032bf ffffffffffffffffffffffffffffffff c78068577ec5dc1d06605f291a79174f c7806857

table 3

In Table 3, the first 4 bytes of the feature code value (MD5 value) are taken as the secondary hash value (secondary excerpt value), which is used to quickly search whether there is a matching secondary excerpt value in the feature code table, if it exists in the dictionary If the value is the same as the second excerpt value of the page data to be written in the current write command, then the feature code value is matched.

The smallest unit of data compression in this embodiment is a page, the data in the page is not compressed and decompressed, and the writing and reading of data is also based on the page, so the compression management method provided by the embodiment of the present invention is very suitable for using computing power Insufficient or low-cost paged memory devices. Moreover, in the compression management method provided by the embodiment of the present invention, if the data to be written in the current write command has been stored in the dictionary, the data will not be written, so the data writing efficiency of the paging storage device can be effectively improved, and the writing of data can be reduced. The number of entries, thereby reducing the wear and tear of paging storage devices.

Embodiment two:

FIG. 2 shows the implementation process of the paging storage device compression management method provided by Embodiment 2 of the present invention, and the process of the method is described in detail as follows:

In step S201, a static dictionary is established with a page as a unit, and the static dictionary records page data whose write times are greater than or equal to the first threshold and/or page data that the user cares about, the feature code corresponding to the page data, and Information such as the physical page address where the page data is written.

In this embodiment, the static dictionary is a dictionary that is fixed in the paging storage device and does not allow updating, and the static dictionary can be created according to the following conditions:

1. According to the storage capacity of the paging storage device, set the dictionary size (storage capacity) that satisfies a certain percentage (such as 1%). For example, when the storage capacity of the paging storage device is 100M, the dictionary size (storage capacity) is 1M;

2. Carry out a large number of samples according to the main application range of the paging storage device, and obtain the best dictionary after statistical analysis; for example, use the data whose writing times are greater than or equal to the first threshold (10 times) as the page data in the dictionary;

3. Set the content of the dictionary according to the user's own needs (that is, the data that the user cares about).

In step S202, a write command is obtained, and the write command includes information such as the page data to be written and the logical page address to be written by the page data to be written;

In step S203, the feature code of the page data to be written is obtained, and it is judged whether there is a feature code identical to the acquired feature code in the dictionary, and if the judgment result is “Yes”, then step S205 is executed, and if it is judged If the result is "no", execute step S204;

Preferably, it is judged whether there is a feature code identical to the acquired feature code in the static dictionary, if the judgment result is "yes", then perform step S205, if the judgment result is "no", then perform step S204;

In step S204, the write command is executed, and the page data to be written is written according to the logical page address written by the page data to be written, that is, the page data to be written is stored in the logical address Corresponding physical address;

In step S205, the write command is not executed, and the logical page address of the page data to be written is pointed to the physical page address of the page data having the same feature code as the page data to be written.

As another preferred embodiment of the present invention, in order to reduce the code repetition rate, the feature code of the page data to be written in the write command is obtained, and it is judged whether there is a feature code identical to the acquired feature code in the dictionary; if No, execute the write command, write the page data to be written according to the logical page address written in the page data to be written; if so, do not execute the write command, write the page data to be written The imported logical page address points to the physical page address written into the page data having the same feature code as the page data to be written specifically includes:

When the paging storage device supports a variety of hash algorithms, perform multiple message excerpts on the page data to be written in the current write command, obtain the feature code after each message excerpt, and judge whether there is a corresponding feature code in the dictionary The feature code after each message excerpt is the same feature code, if not, execute the current write command, and write the page data to be written according to the logical page address of the page data to be written in the current write command; if , the write command is not executed, and the logical page address of the page data to be written in the current write command is pointed to the physical page address of the page data having the same feature code as the page data to be written, wherein the The dictionary records the feature code after multiple message excerpts of the page data;

Or, when the paging storage device supports a hash algorithm, multiple message excerpts with different offsets are performed on the page data to be written in the current write command, and the feature code after each excerpted message with different offsets is obtained, Judging whether there is a feature code in the dictionary that is the same as the feature code extracted from each different offset message, if not, execute the current write command, and write the logical page according to the page data to be written in the current write command The address is written to the page data to be written; if so, the write command is not executed, and the logical page address to be written in the page data to be written in the current write command is directed to the same feature code as the page data to be written The address of the physical page where the page data is written, wherein the dictionary records the feature code after multiple excerpts of different offset messages of the page data;

Or, when the paging storage device supports error checking and correcting ECC codes, obtain the ECC codes of the page data to be written in the current write command and the feature codes after message excerpts, and judge whether the ECC codes and ECC codes exist in the dictionary at the same time. The feature code after the message is extracted, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if not, do not execute the write command, Point the logical page address written in the page data to be written in the current write command to the physical page address written in the page data having the same feature code as the page data to be written, wherein the ECC of the page data is recorded in the dictionary Code and message excerpted feature code;

Or, obtain the feature code of the page data to be written in the current write command, and when there is a feature code identical to the acquired feature code in the dictionary, judge that the N bytes in the page data to be written are consistent with the Whether the N bytes in the page data corresponding to the same feature code in the dictionary are all the same, if not, execute the current write command, and write the to-be-written Enter the page data; if, do not execute the write command, the logical page address of the page data to be written in the current write command is directed to the physical page written by the page data with the same feature code as the page data to be written address, wherein the N is an integer greater than zero and less than or equal to the size of a page in the paging memory, that is, if the page size in the paging memory is 8k bytes, then the N is less than or equal to 8k bytes. It should be noted that, in order not to affect the data compression efficiency, the above comparison process may be implemented by using a hardware comparator.

Preferably, in order to ensure that the efficiency of data compression can be further improved in the case of a large dictionary, the feature code of the page data to be written in the said acquisition write command is determined to determine whether there is a feature code corresponding to the acquired data in the dictionary. The same feature code of the feature code; if not, execute the write command, write the page data to be written according to the logical page address written in the page data to be written; if not, execute the write command, and write The logical page address written in the page data to be written points to the physical page address written in the page data having the same feature code as the page data to be written specifically includes:

Obtain the feature code of the page data to be written in the current write command, perform message extraction on the feature code to obtain a secondary extraction value, and determine whether the secondary extraction value exists in the dictionary, and if so, determine the dictionary Whether there is the feature code in, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if so, do not execute the write command Pointing the logical page address of the page data to be written in the current write command to the physical page address of the page data having the same feature code as the page data to be written, wherein the dictionary records the corresponding page data The secondary excerpt value of the signature. Wherein, the second extraction value is smaller than the size of the feature code and within the allowable range of the repetition rate.

In this embodiment, a feature code table and a secondary extraction value table are established in advance, and the feature code table and the secondary extraction value table are respectively used to record the feature code of the page data and the secondary extraction value of the feature code. Since it is only necessary to match the secondary extraction value table with a small amount of data at the beginning, only when the same secondary extraction value occurs, it is necessary to compare the feature code table with a large amount of data. Therefore, the matching efficiency can be greatly improved, and then the Data compression efficiency.

In this embodiment, it is judged according to the pre-established static dictionary whether the page data to be written has been written before, since the static dictionary contains frequently written data, the efficiency of judgment can be effectively improved.

Embodiment three:

FIG. 3 shows the implementation process of the paging storage device compression management method provided by Embodiment 3 of the present invention. The process of the method is described in detail as follows:

In step S301, a dynamic dictionary is established with a page as a unit, and information such as page data, a feature code corresponding to the page data, and a physical page address where the page data is written is recorded in the dynamic dictionary.

In this embodiment, the dynamic dictionary is a dictionary that is allowed to be updated.

In step S302, a second threshold (for example, 10 times) is set, and the number of writing times of page data written into the paged memory device is counted.

In step S303, a write command is obtained, the write command includes the page data to be written and the logical page address in which the page data to be written is written.

In step S304, obtain the feature code of the page data to be written, judge whether there is a feature code identical to the acquired feature code in the dynamic dictionary, if the judgment result is "yes", then perform step S305, if If the judgment result is "No", then step S306 is executed.

In step S305, the write command is not executed, and the logical page address of the page data to be written is pointed to the physical page address of the page data having the same feature code as the page data to be written.

In step S306, the write command is executed, and the page data to be written is written according to the logical page address of the page data to be written.

In step S307, it is judged whether the number of write times of the page data to be written has reached the second threshold, if the judgment result is “Yes”, then step S308 is executed, if the judgment result is “No”, then this time is ended operate.

In step S308, the page data to be written is updated into the dynamic dictionary.

Specifically, information including the page data to be written, the feature code corresponding to the page data to be written, and the address of the physical page where the page data to be written is written is updated into the dynamic dictionary.

As another preferred embodiment of the present invention, in order to prevent the dynamic dictionary from becoming larger and larger, affecting the efficiency of data compression and search, it also includes:

When the storage capacity of the dynamic dictionary reaches a third threshold, delete invalid entries in the dynamic dictionary or entries that have not been used within a preset time, and the invalid entries are page data stored in the dynamic dictionary The write address has already written other data, which makes the page data invalid; the unused entry within the preset time means that the page data corresponding to the entry has not been written into the paged storage device within the preset time.

Or, continue counting the number of writes of the page data after the number of writes of the page data reaches the second threshold, and delete the dynamic dictionary when the storage capacity of the dynamic dictionary reaches the third threshold Page data whose writing times are less than the fourth threshold. For example, the page data write times of all 0x8f reaches 10 times, then the page data is updated to the dynamic dictionary, but the counting of each page data in the dynamic dictionary is still continuing, when the storage capacity of the dynamic dictionary reaches The third threshold, when the writing times of all 0x8f page data is less than the fourth threshold (for example, 15 times), delete all 0x8f page data from the dynamic dictionary.

As another preferred embodiment of the present invention, in order to reduce the code repetition rate, the feature code of the page data to be written in the write command is obtained, and it is judged whether there is a feature code identical to the acquired feature code in the dictionary; if No, execute the write command, write the page data to be written according to the logical page address written in the page data to be written; if so, do not execute the write command, write the page data to be written The imported logical page address points to the physical page address written into the page data having the same feature code as the page data to be written specifically includes:

When the paging storage device supports a variety of hash algorithms, perform multiple message excerpts on the page data to be written in the current write command, obtain the feature code after each message excerpt, and judge whether there is a corresponding feature code in the dictionary The feature code after each message excerpt is the same feature code, if not, execute the current write command, and write the page data to be written according to the logical page address of the page data to be written in the current write command; if , the write command is not executed, and the logical page address of the page data to be written in the current write command is pointed to the physical page address of the page data having the same feature code as the page data to be written, wherein the The dictionary records the feature code after multiple message excerpts of the page data;

Or, when the paging storage device supports a hash algorithm, multiple message excerpts with different offsets are performed on the page data to be written in the current write command, and the feature code after each excerpted message with different offsets is obtained, Judging whether there is a feature code in the dictionary that is the same as the feature code extracted from each different offset message, if not, execute the current write command, and write the logical page according to the page data to be written in the current write command The address is written to the page data to be written; if so, the write command is not executed, and the logical page address to be written in the page data to be written in the current write command is directed to the same feature code as the page data to be written The address of the physical page where the page data is written, wherein the dictionary records the feature code after extracting multiple different offset messages of the page data;

Or, when the paging storage device supports error checking and correcting ECC codes, obtain the ECC codes of the page data to be written in the current write command and the feature codes after message excerpts, and judge whether the ECC codes and ECC codes exist in the dictionary at the same time. The feature code after the message is extracted, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if not, do not execute the write command, Point the logical page address written in the page data to be written in the current write command to the physical page address written in the page data having the same feature code as the page data to be written, wherein the ECC of the page data is recorded in the dictionary Code and message excerpted feature code;

Or, obtain the feature code of the page data to be written in the current write command, and when there is a feature code identical to the acquired feature code in the dictionary, judge that the N bytes in the page data to be written are consistent with the Whether the N bytes in the page data corresponding to the same feature code in the dictionary are all the same, if not, execute the current write command, and write the to-be-written Enter the page data; if, do not execute the write command, the logical page address of the page data to be written in the current write command is directed to the physical page written by the page data with the same feature code as the page data to be written address, wherein the N is an integer greater than zero and less than or equal to the size of a page in the paging memory, that is, if the page size in the paging memory is 8k bytes, then the N is less than or equal to 8k bytes. It should be noted that, in order not to affect the data compression efficiency, the above comparison process may be implemented by using a hardware comparator.

Preferably, in order to ensure that the efficiency of data compression can be further improved in the case of a large dictionary, the feature code of the page data to be written in the said acquisition write command is determined to determine whether there is a feature code corresponding to the acquired data in the dictionary. The same feature code of the feature code; if not, execute the write command, write the page data to be written according to the logical page address written in the page data to be written; if not, execute the write command, and write The logical page address written in the page data to be written points to the physical page address written in the page data having the same feature code as the page data to be written specifically includes:

Obtain the feature code of the page data to be written in the current write command, perform message extraction on the feature code to obtain a secondary extraction value, and determine whether the secondary extraction value exists in the dictionary, and if so, determine the dictionary Whether there is the feature code in, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if so, do not execute the write command Pointing the logical page address of the page data to be written in the current write command to the physical page address of the page data having the same feature code as the page data to be written, wherein the dictionary records the corresponding page data The secondary excerpt value of the signature. Wherein, the second extraction value is smaller than the size of the feature code and within the allowable range of the repetition rate.

In this embodiment, a feature code table and a secondary extraction value table are established in advance, and the feature code table and the secondary extraction value table are respectively used to record the feature code of the page data and the secondary extraction value of the feature code. Since it is only necessary to match the secondary extraction value table with a small amount of data at the beginning, only when the same secondary extraction value appears, it is necessary to compare the feature code table with a large amount of data. Therefore, the matching efficiency can be greatly improved, and then the Data compression efficiency.

As another preferred embodiment of the present invention, the dictionary can also include both a static dictionary and a dynamic dictionary; the page data in the static dictionary is data whose write times are greater than or equal to the first threshold and/or data that the user cares about ;

Before the step of obtaining the write command, the method also includes:

Setting a second threshold to count the number of write times of page data written into the paging storage device;

The acquisition of the feature code of the page data to be written, and judging whether there is a feature code identical to the acquired feature code in the dictionary specifically includes:

Acquiring the feature code of the page data to be written, judging whether there is a feature code identical to the acquired feature code in the static dictionary, if not, judging according to the number of times the page data to be written is written into the paging storage device Whether the page data to be written needs to be updated to the dynamic dictionary.

Embodiment four:

FIG. 4 shows the composition and structure of the paging storage device compression management apparatus provided by Embodiment 4 of the present invention. For ease of description, only the parts related to the embodiment of the present invention are shown.

The paging storage device compression management device can be applied to storage devices, and can be a software unit, a hardware unit, or a combination of software and hardware running in the storage device, or it can be integrated into the storage device as an independent pendant or run on the storage device. in the application system of the device.

The paging storage device compression management device includes a dictionary establishment unit 41 and a processing unit 42 . Among them, the specific functions of each unit are as follows:

A dictionary building unit 41, configured to create a dictionary in units of pages, where page data, a feature code corresponding to the page data, and a physical page address where the page data is written are recorded in the dictionary;

The processing unit 42 is configured to obtain a write command, the write command includes the page data to be written and the logical page address of the page data to be written; obtain the feature code of the page data to be written, and determine the Whether there is the same feature code as the acquired feature code in the dictionary; If not, execute the write command, write the page data to be written according to the logical page address written by the page data to be written; if so, The write command is not executed, and the logical page address of the page data to be written is pointed to the physical page address of the page data having the same feature code as the page data to be written.

Preferably, the dictionary is a static dictionary, and the page data in the static dictionary is data whose write times are greater than or equal to a first threshold and/or page data that the user cares about.

Preferably, the dictionary is a dynamic dictionary;

The processing unit 42 is further configured to set a second threshold before acquiring the write command, and count the number of write times of the page data written into the paging memory device;

After the processing unit 42 executes the write command and writes the page data to be written according to the logical page address written in the page data to be written, it is further configured to write the page data when the number of write times reaches When the second threshold is reached, update the page data into the dynamic dictionary.

Preferably, the dictionary includes a static dictionary and a dynamic dictionary; the page data in the static dictionary is data whose writing times is greater than or equal to the first threshold and/or data that the user cares about;

The processing unit 42 is further configured to set a second threshold before acquiring the write command, and count the number of write times of the page data written into the paging memory device;

The processing unit 42 is configured to obtain the feature code of the page data to be written, and judge whether there is a feature code identical to the acquired feature code in the static dictionary, and if not, according to the page data to be written The times of writing into the paging storage device determine whether the page data to be written needs to be updated to the dynamic dictionary.

Further, the processing unit 42 is further configured to, when the storage capacity of the dynamic dictionary reaches a third threshold, delete invalid entries in the dynamic dictionary or entries that have not been used within a preset time, and the invalid The entry is the write address of the page data stored in the dynamic dictionary and other data has been written, resulting in the page data being invalid; the entry that is not used within the preset time is the page data corresponding to the entry within the preset time The paged memory device has not been written to; or,

Continue to count the number of writes of the page data after the number of writes of the page data reaches the second threshold, and when the storage capacity of the dynamic dictionary reaches the third threshold, delete the write in the dynamic dictionary page data whose number of times is less than the fourth threshold.

Further, the processing unit 42 is specifically used for:

When the paging storage device supports a variety of hash algorithms, perform multiple message excerpts on the page data to be written in the current write command, obtain the feature code after each message excerpt, and judge whether there is a corresponding feature code in the dictionary The feature code after each message excerpt is the same feature code, if not, execute the current write command, and write the page data to be written according to the logical page address of the page data to be written in the current write command; if , the write command is not executed, and the logical page address of the page data to be written in the current write command is pointed to the physical page address of the page data having the same feature code as the page data to be written, wherein the The dictionary records the feature code after multiple message excerpts of the page data;

Or, when the paging storage device supports a hash algorithm, multiple message excerpts with different offsets are performed on the page data to be written in the current write command, and the feature code after each excerpted message with different offsets is obtained, Judging whether there is a feature code in the dictionary that is the same as the feature code extracted from each different offset message, if not, execute the current write command, and write the logical page according to the page data to be written in the current write command The address is written to the page data to be written; if so, the write command is not executed, and the logical page address to be written in the page data to be written in the current write command is directed to the same feature code as the page data to be written The address of the physical page where the page data is written, wherein the dictionary records the feature code after extracting multiple different offset messages of the page data;

Or, when the paging storage device supports error checking and correcting ECC codes, obtain the ECC codes of the page data to be written in the current write command and the feature codes after message excerpts, and judge whether the ECC codes and ECC codes exist in the dictionary at the same time. The feature code after the message is extracted, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if not, do not execute the write command, Point the logical page address written in the page data to be written in the current write command to the physical page address written in the page data having the same feature code as the page data to be written, wherein the ECC of the page data is recorded in the dictionary Code and message excerpted feature code;

Or, obtain the feature code of the page data to be written in the current write command, and when there is a feature code identical to the acquired feature code in the dictionary, judge that the N bytes in the page data to be written are consistent with the Whether the N bytes in the page data corresponding to the same feature code in the dictionary are all the same, if not, execute the current write command, and write the to-be-written Enter the page data; if, do not execute the write command, the logical page address of the page data to be written in the current write command is directed to the physical page written by the page data with the same feature code as the page data to be written address, wherein the N is an integer greater than zero and less than or equal to the size of a page in the paging memory.

Further, the processing unit 42 is specifically used for:

Obtain the feature code of the page data to be written in the current write command, and then extract the message of the feature code to obtain a secondary excerpt value, and judge whether the secondary excerpt value exists in the dictionary, and if so, then judge the Whether there is the feature code in the dictionary, if not, execute the current write command, write the page data to be written according to the logical page address of the page data to be written in the current write command; if so, do not execute the write Command, point the logical page address of the page data to be written in the current write command to the physical page address of the page data with the same feature code as the page data to be written, wherein the page data is recorded in the dictionary Corresponding to the second excerpt value of the feature code.

In this embodiment, the feature code of the page data may be acquired through a hash algorithm.

The paging storage device compression management apparatus provided in this embodiment can be used in the above-mentioned corresponding paging storage device compression management method. For details, refer to the relevant descriptions of Embodiments 1 to 3 of the above-mentioned paging storage device compression management method, which will not be repeated here.

Those of ordinary skill in the art can understand that the various units included in the fourth embodiment above are only divided according to functional logic, but are not limited to the above division, as long as the corresponding functions can be realized; in addition, the specific functions of each functional unit The names are only for the convenience of distinguishing each other, and are not used to limit the protection scope of the present invention.

To sum up, the smallest unit of data compression in the embodiment of the present invention is the page, the data in the page is not compressed and decompressed, and the writing and reading of data is also based on the page, so the compression management provided by the embodiment of the present invention The method is very suitable for adopting paging memory devices with insufficient computing power or low cost. Moreover, in the compression management method provided by the embodiment of the present invention, if the data to be written in the current write command has been stored in the dictionary, the data will not be written, so the data writing efficiency of the paging storage device can be effectively improved, and the writing of data can be reduced. The number of entries, thereby reducing the wear and tear of paging storage devices. In addition, the embodiment of the present invention can effectively reduce the code repetition rate in the comparison process through multiple comparison methods, and can improve matching efficiency and data compression efficiency, and has strong usability and practicability.

The above content is a further detailed description of the present invention in conjunction with specific preferred embodiments, and it cannot be assumed that the specific implementation of the present invention is limited to these descriptions. For those of ordinary skill in the technical field to which the present invention belongs, several equivalent substitutions or obvious modifications are made without departing from the concept of the present invention, and the performance or use is the same, all should be regarded as belonging to the present invention by the submitted claims The scope of patent protection determined by the book.

Claims (16)

1. A method for compression management of a paged storage device, the method comprising:

step A, establishing a dictionary by taking a page as a unit, wherein page data, feature codes corresponding to the page data and physical page addresses written by the page data are recorded in the dictionary, and secondary extraction values of the feature codes corresponding to the page data are also recorded in the dictionary;

step B, acquiring a write command, wherein the write command comprises page data to be written and a logical page address written by the page data to be written; acquiring feature codes of the page data to be written, and judging whether feature codes identical to the acquired feature codes exist in the dictionary or not; if not, executing the write command, and writing the page data to be written according to the logical page address written by the page data to be written; if so, not executing the write command, and pointing the logical page address written by the page data to be written to a physical page address written by page data with the same feature code as the page data to be written;

the step B specifically comprises the following steps:

acquiring a feature code of page data to be written in a current writing command, extracting a message of the feature code to obtain a secondary extracted value, judging whether the secondary extracted value exists in the dictionary, if so, judging whether the feature code exists in the dictionary, if not, executing the current writing command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current writing command; if so, the write command is not executed, and the logical page address written by the page data to be written in the current write command points to the physical page address written by the page data with the same feature code as the page data to be written.

2. The method of claim 1, wherein the dictionary is a static dictionary, and the page data in the static dictionary is data written a number of times greater than or equal to a first threshold.

3. The method of claim 1, wherein the dictionary is a dynamic dictionary, the dynamic dictionary being a dictionary that is allowed to be updated;

the method further comprises, before the step of obtaining a write command:

setting a second threshold value, and counting the writing times of the page data written into the paged memory device;

after the step of executing the write command and writing the page data to be written according to the logical page address written by the page data to be written, the method further comprises the following steps:

and updating the page data to be written into the dynamic dictionary when the writing times of the page data to be written reach the second threshold value.

4. The method of claim 1, wherein the dictionary comprises a static dictionary and a dynamic dictionary; the page data in the static dictionary is data with the writing times larger than or equal to a first threshold, and the dynamic dictionary is a dictionary allowed to be updated;

the method further comprises, before the step of obtaining a write command:

setting a second threshold value, and counting the writing times of the page data written into the paged memory device;

the step of acquiring the feature codes of the page data to be written and judging whether the feature codes identical to the acquired feature codes exist in the dictionary specifically comprises the following steps:

and acquiring the feature codes of the page data to be written, judging whether the feature codes identical to the acquired feature codes exist in the static dictionary, and if not, judging whether the page data to be written needs to be updated to the dynamic dictionary according to the times of writing the page data to be written into the paging memory device.

5. The method of claim 3 or 4, further comprising:

when the storage capacity of the dynamic dictionary reaches a third threshold value, deleting an invalid entry or an unused entry in the dynamic dictionary within a preset time, wherein the invalid entry is that other data have been written in a write address of page data stored in the dynamic dictionary, so that the page data is invalid; the unused entry in the preset time is that the page data corresponding to the entry is not written into the paged memory device in the preset time.

6. The method of claim 3 or 4, further comprising:

and continuing to count the writing times of the page data after the writing times of the page data reach the second threshold, and deleting the page data with the writing times smaller than a fourth threshold in the dynamic dictionary when the storage capacity of the dynamic dictionary reaches a third threshold.

7. The method of claim 1, wherein step B further comprises:

when the paging memory device supports various hash algorithms, performing message extraction on page data to be written in a current write command for multiple times, acquiring feature codes after message extraction each time, judging whether feature codes identical to the feature codes after message extraction each time exist in the dictionary or not, if not, executing the current write command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein feature codes obtained after extracting a plurality of messages of the page data are recorded in the dictionary;

or when the paging memory device supports a hash algorithm, performing message extraction of different offsets for multiple times on page data to be written in a current write command, acquiring feature codes after message extraction of different offsets each time, judging whether feature codes identical to the feature codes after message extraction of different offsets each time exist in the dictionary or not, if not, executing the current write command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein feature codes obtained by extracting page data from different offset messages for multiple times are recorded in the dictionary;

or, when the paged memory device supports error checking and correcting of ECC codes, acquiring an ECC code of page data to be written in a current write command and a feature code after message extraction, determining whether the ECC code and the feature code after message extraction exist in the dictionary at the same time, if not, executing the current write command, and writing the page data to be written according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein an ECC code of the page data and a feature code after message extraction are recorded in the dictionary;

or acquiring a feature code of page data to be written in the current write command, judging whether N bytes in the page data to be written are all the same as N bytes in page data corresponding to the same feature code in the dictionary when the feature code which is the same as the acquired feature code exists in the dictionary, if not, executing the current write command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein N is an integer which is greater than zero and less than or equal to the size of the page in the paged memory.

8. The method according to any one of claims 1 to 4, wherein the obtaining the feature code of the page data to be written specifically comprises:

and acquiring the feature code of the page data to be written through a Hash algorithm.

9. An apparatus for compression management of a paged storage device, the apparatus comprising:

the dictionary establishing unit is used for establishing a dictionary by taking a page as a unit, wherein page data, feature codes corresponding to the page data and physical page addresses written by the page data are recorded in the dictionary, and secondary extraction values of the feature codes corresponding to the page data are also recorded in the dictionary;

the processing unit is used for acquiring a write command, and the write command comprises page data to be written and a logical page address written by the page data to be written; acquiring feature codes of the page data to be written, and judging whether feature codes identical to the acquired feature codes exist in the dictionary or not; if not, executing the write command, and writing the page data to be written according to the logical page address written by the page data to be written; if so, not executing the write command, and pointing the logical page address written by the page data to be written to a physical page address written by page data with the same feature code as the page data to be written;

the processing unit is specifically configured to,

acquiring a feature code of page data to be written in a current writing command, extracting a message of the feature code to obtain a secondary extracted value, judging whether the secondary extracted value exists in the dictionary, if so, judging whether the feature code exists in the dictionary, if not, executing the current writing command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current writing command; if so, the write command is not executed, and the logical page address written by the page data to be written in the current write command points to the physical page address written by the page data with the same feature code as the page data to be written.

10. The apparatus of claim 9, wherein the dictionary is a static dictionary, and the page data in the static dictionary is data written a number of times greater than or equal to a first threshold.

11. The apparatus of claim 9, wherein the dictionary is a dynamic dictionary, the dynamic dictionary being a dictionary that is allowed to be updated;

the processing unit is further configured to, before the write command is acquired, set a second threshold value to count the number of writes of the page data to the paged memory device;

and after the write command is executed and the page data to be written is written according to the logical page address written by the page data to be written, the processing unit is also used for updating the page data to the dynamic dictionary when the writing frequency of the page data reaches the second threshold value.

12. The apparatus of claim 9, wherein the dictionary comprises a static dictionary and a dynamic dictionary; the page data in the static dictionary is data with the writing times larger than or equal to a first threshold, and the dynamic dictionary is a dictionary allowed to be updated;

the processing unit is further configured to, before the write command is acquired, set a second threshold value to count the number of writes of the page data to the paged memory device;

and the processing unit is used for acquiring the feature codes of the page data to be written, judging whether the feature codes identical to the acquired feature codes exist in the static dictionary, and if not, judging whether the page data to be written needs to be updated to the dynamic dictionary according to the number of times of writing the page data to be written into the paging memory device.

13. The apparatus according to claim 11 or 12, wherein the processing unit is further configured to, when the storage capacity of the dynamic dictionary reaches a third threshold, delete an invalid entry in the dynamic dictionary or an entry that is not used within a preset time, where the invalid entry is that a write address of page data stored in the dynamic dictionary has written other data, resulting in invalidation of the page data; the unused entry in the preset time is that the page data corresponding to the entry is not written into the paged memory device in the preset time.

14. The apparatus of claim 11 or 12, wherein the processing unit is further to,

and continuing to count the writing times of the page data after the writing times of the page data reach the second threshold, and deleting the page data with the writing times smaller than a fourth threshold in the dynamic dictionary when the storage capacity of the dynamic dictionary reaches a third threshold.

15. The apparatus of claim 9, wherein the processing unit is specifically to,

when the paging memory device supports various hash algorithms, performing message extraction on page data to be written in a current write command for multiple times, acquiring feature codes after message extraction each time, judging whether feature codes identical to the feature codes after message extraction each time exist in the dictionary or not, if not, executing the current write command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein feature codes obtained after extracting a plurality of messages of the page data are recorded in the dictionary;

or when the paging memory device supports a hash algorithm, performing message extraction of different offsets for multiple times on page data to be written in a current write command, acquiring feature codes after message extraction of different offsets each time, judging whether feature codes identical to the feature codes after message extraction of different offsets each time exist in the dictionary or not, if not, executing the current write command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein feature codes obtained by extracting page data from different offset messages for multiple times are recorded in the dictionary;

or, when the paged memory device supports error checking and correcting of ECC codes, acquiring an ECC code of page data to be written in a current write command and a feature code after message extraction, determining whether the ECC code and the feature code after message extraction exist in the dictionary at the same time, if not, executing the current write command, and writing the page data to be written according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein an ECC code of the page data and a feature code after message extraction are recorded in the dictionary;

or acquiring a feature code of page data to be written in the current write command, judging whether N bytes in the page data to be written are all the same as N bytes in page data corresponding to the same feature code in the dictionary when the feature code which is the same as the acquired feature code exists in the dictionary, if not, executing the current write command, and writing the page data to be written in according to a logical page address written in the page data to be written in the current write command; if so, not executing the write command, and pointing a logical page address written by the page data to be written in the current write command to a physical page address written by the page data with the same feature code as the page data to be written, wherein N is an integer which is greater than zero and less than or equal to the size of the page in the paged memory.

16. The apparatus according to any one of claims 9 to 12, wherein the processing unit is configured to obtain a feature code of the page data to be written by a hash algorithm.