Data storage device in a key-value storage architecture with data compression, and non-volatile memory control method

1. A data storage device, comprising:

a non-volatile memory; and

a controller, coupled to the non-volatile memory, and configured to perform garbage collection on the non-volatile memory,

wherein:

during the garbage collection, the controller compresses valid pieces of key-value data to generate a piece of compressed data;

each piece of key-value data is in a key-value format; and

the controller codes the piece of compressed data to generate a first piece of compressed key-value data that is also in key-value format, and programs the first piece of compressed key-value data into the non-volatile memory;

wherein:

the key-value format includes a mark field;

in the first piece of compressed key-value data, a mark field is filled with a compression symbol;

in the collected pieces of key-value data, every mark field is filled with an uncompressed symbol;

the key-value format further includes a prefix field, a key field, and a responding-value field; and

in the first piece of compressed key-value data, a key field is filled with a dummy key, and the responding-value field is filled with the piece of compressed data.

2. The data storage device as claimed in claim 1 , wherein:

the controller arranges the collected pieces of key-value data according to a special format to generate a piece of special-format data;

the special-format data further includes position information indicating locations of the collected pieces of key-value data arranged in the special-format data.

3. The data storage device as claimed in claim 2 , wherein:

in a mapping information translation layer, the controller manages mapping information that maps a plurality of keys to the non-volatile memory;

the first piece of compressed key-value data is programmed into the non-volatile memory as indicated by a first physical address; and

the controller updates the mapping translation layer to record the first physical address as mapping information of keys of the collected pieces of key-value data.

4. The data storage device as claimed in claim 3 , wherein:

one key among the keys of the collected pieces of key-value data is a target key;

in response to a read request for a target responding value corresponding to the target key, the controller obtains the first physical address from the mapping information translation layer, reads the first piece of compressed key-value data from the non-volatile memory according to the first physical address, recognizes the compression symbol in the mark field of the first piece of compressed key-value data, decompresses the compressed data contained in the first piece of compressed key-value data to get the special-format data, and extracts the target responding value from the special-format data.

5. The data storage device as claimed in claim 4 , wherein:

according to the position information contained in the special-format data, the controller obtains the collected pieces of key-value data from the special-format data, compares the keys recorded in the collected pieces of key-value data with the target key to obtain a matching key, and regards a responding value corresponding to the matching key as the target responding value.

6. The data storage device as claimed in claim 4 , wherein:

for each key of the collected pieces of key-value data, an index value is recorded in the mapping information translation layer; and

the controller checks the position information contained in the special-format data according to an index value that is recorded in the mapping information translation layer for the target key, and thereby obtains a location for a target piece of key-value data in the special-format data; and

the controller extracts the target responding value from the target piece of key-value data.

7. The data storage device as claimed in claim 4 , wherein:

length of the compressed data corresponding to the collected pieces of key-value data is recorded in the mapping information translation layer; and

the controller decompresses the compressed data due to the length having a non-zero value.

8. The data storage device as claimed in claim 1 , wherein:

a first compression algorithm is annotated in the responding-value field of the first piece of compressed key-value data.

9. The data storage device as claimed in claim 8 , wherein:

as annotated in the responding field of the first piece of compressed key-value data, decompression corresponding to the first compression algorithm is performed, and a piece of source key-value data is obtained from the decompression;

the piece of source key-value data is combined with some other pieces of source key-value data, and then compressed according to a second compression algorithm for an update from the first compression algorithm to the second compression algorithm, and then coded to generate a second piece of compressed key-value data that is in key-value format, and then programmed into the non-volatile memory as indicated by a second physical address for garbage collection; and

the second compression algorithm is annotated in the responding-value field of the second piece of compressed key-value data.

10. A non-volatile memory control method, comprising:

performing garbage collection on a non-volatile memory; and

during the garbage collection, compressing valid pieces of key-value data to generate a piece of compressed data, coding the piece of compressed data to generate a first piece of compressed key-value data that is in key-value format, and programming the first piece of compressed key-value data into the non-volatile memory,

wherein each piece of key-value data is in key-value format,

wherein:

the key-value format includes a mark field;

in the first piece of compressed key-value data, a mark field is filled with a compression symbol;

in the collected pieces of key-value data, every mark field is filled with an uncompressed symbol;

the key-value format further includes a prefix field, a key field, and a responding-value field; and

in the first piece of compressed key-value data, a key field is filled with a dummy key, and the responding-value field is filled with the piece of compressed data.

11. The non-volatile memory control method as claimed in claim 10 , further comprising:

arranging the collected pieces of key-value data according to a special format to generate a piece of special-format data,

wherein the special-format data further includes position information indicating the locations of the collected pieces of key-value data arranged in the special-format data.

12. The non-volatile memory control method as claimed in claim 11 , further comprising:

managing mapping information in a mapping information translation layer to map a plurality of keys to the non-volatile memory; and

when the first piece of compressed key-value data is programmed into the non-volatile memory as indicated by a first physical address, updating the mapping translation layer to record the first physical address as mapping information of keys of the collected pieces of key-value data.

13. The non-volatile memory control method as claimed in claim 12 , wherein:

one key among the keys of the collected pieces of key-value data is a target key; and

in response to a read request for a target responding value corresponding to the target key, the first physical address is obtained from the mapping information translation layer, the first piece of compressed key-value data is read from the non-volatile memory according to the first physical address, the compression symbol in the mark field of the first piece of compressed key-value data is recognized, the compressed data contained in the first piece of compressed key-value data is decompressed to get the special-format data, and the target responding value is extracted from the special-format data.

14. The non-volatile memory control method as claimed in claim 13 , further comprising:

according to the position information contained in the special-format data, obtaining the collected pieces of key-value data from the special-format data, comparing the keys recorded in the collected pieces of key-value data with the target key to obtain a matching key, and regarding a responding value corresponding to the matching key as the target responding value.

15. The non-volatile memory control method as claimed in claim 13 , wherein:

for each key of the collected pieces of key-value data, an index value is recorded in the mapping information translation layer; and

the position information contained in the special-format data is checked according to an index value that is recorded in the mapping information translation layer for the target key, and thereby the location of a target piece of key-value data in the special-format data is obtained; and

the target responding value is extracted from the target piece of key-value data.

16. The non-volatile memory control method as claimed in claim 13 , wherein:

the length of the compressed data corresponding to the collected pieces of key-value data is recorded in the mapping information translation layer; and

the compressed data is decompressed due to the non-zero value of the length.

17. The non-volatile memory control method as claimed in claim 10 ,

wherein:

a first compression algorithm is annotated in the responding-value field of the first piece of compressed key-value data.

18. The non-volatile memory control method as claimed in claim 17 , wherein:

as annotated in the responding field of the first piece of compressed key-value data, decompression corresponding to the first compression algorithm is performed, and a piece of source key-value data is obtained from the decompression;

the piece of source key-value data is combined with some other pieces of source key-value data, and then compressed according to a second compression algorithm for an update from the first compression algorithm to the second compression algorithm, and then coded to generate a second piece of compressed key-value data that is in key-value format, and then programmed into the non-volatile memory as indicated by a second physical address for garbage collection; and

the second compression algorithm is annotated in the responding-value field of the second piece of compressed key-value data.