Compression and formatting of data for data storage systems

• US 9,448,738 B2
• Filed: 05/24/2013
• Issued: 09/20/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Horn, Robert L.
• Primary Examiner(s): Verbrugge, Kevin
• Assistant Examiner(s): GRULLON, FRANCISCO A
• Application Number:
  US13/902,504
• Publication Number:
  US 20140281146A1
• Time in Patent Office: 1,215 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/217 Hybrid disk, e.g. using both magnetic and solid state storage devices
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/281 Single cache
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11B 20/0021 involving encryption or decryption of contents recorded on or reproduced from a record carrier
• CPC Class Codes: G11B 20/10527 Audio or video recording; Data buffering arrangements G11B20/12 - G11B20/18 take precedence
• CPC Class Codes: G11B 20/1217 on discs

Abstract

Embodiments of compression and formatting of data for data storage systems are disclosed. In some embodiments, a data storage system can compress fixed sized data before storing it on a media and format obtained variable sized compressed data for storing on the media that typically has fixed size storage granularity. One or more modules compress the incoming host data and create an output stream of fixed sized storage units that contain compressed data. The storage units are stored on the media. Capacity, reliability, and performance are thereby increased.

Claims

1. A data storage system comprising:

non-volatile memory (NVM) configured to store a plurality of memory data units, a memory data unit being a unit of storage in the NVM; and

a controller configured to;

in response to a write data command received from a host system, the command associated with a plurality of host data units associated with a plurality of logical addresses;

compress the plurality of host data units to obtain a compressed payload, wherein a size of the compressed payload is smaller than or equal to a size of the plurality of host data units;

assemble the compressed payload into a compressed mapping unit;

assemble the compressed mapping unit along with one or more additional compressed mapping units into a storage unit, wherein a size of the storage unit is aligned with the size of the memory data unit;

generate a storage unit metadata portion indicating a position in the storage unit of at least one of the compressed mapping unit or the one or more additional compressed mapping units;

include the metadata portion in the storage unit; and

store the storage unit in the NVM.

2. The data storage system of claim 1, wherein the plurality of host data units are associated with a plurality of consecutive logical addresses.

3. The data storage system of claim 1, wherein the controller is further configured to encrypt the compressed payload.

4. The data storage system of claim 1, wherein the compressed mapping unit comprises a compressed mapping unit metadata portion indicating the plurality of logical addresses associated with data of the compressed payload.

5. The data storage system of claim 4, wherein the compressed mapping unit metadata portion is not compressed.

6. The data storage system of claim 4, wherein the compressed mapping unit metadata portion is not compressed and is not encrypted.

7. The data storage system of claim 6, wherein the controller is further configured to encrypt the compressed payload.

8. The data storage system of claim 7, wherein the controller is further configured to repack, using the compressed mapping unit metadata portion, the compressed payload without decrypting the compressed payload.

9. The data storage system of claim 7, wherein the repacking is associated with the controller performing at least one of defragmentation of data stored in the NVM, garbage collection of data stored in the NVM, or assembling of the compressed payload into another storage unit of a different size than the size of the storage unit.

10. The data storage system of claim 1, wherein the one or more additional compressed mapping units in the storage unit comprise host data units associated with one or more additional write data commands.

11. The data storage system of claim 1, wherein the controller is further configured to include filler data in the storage unit, a size of the filler data selected such that the size of the storage unit is aligned with the size of the memory data unit.

12. The data storage system of claim 1 further comprising a buffer, wherein the controller is further configured to use the buffer to:

compress the plurality of host data units to obtain the compressed payload;

assemble the compressed payload into the compressed mapping unit;

assemble the compressed mapping unit along with the one or more additional compressed mapping units into the storage unit; and

transfer the storage unit from the buffer to the NVM.

13. The data storage system of claim 1, wherein the controller comprises one or more hardware modules configured to:

compress the plurality of host data units to obtain the compressed payload;

assemble the compressed payload into the compressed mapping unit; and

assemble the compressed mapping unit along with the one or more additional compressed mapping units into the storage unit.

14. The data storage system of claim 1, wherein the NVM comprises at least one of a solid-state memory array or magnetic recording media.

15. The data storage system of claim 14, wherein the solid-state memory array is configured to store a plurality of memory data units of a first size and the magnetic recording media is configured to store a plurality of a memory data units of a second size, and the size of the storage unit is aligned with the first size or the second size based at least in part on whether the storage unit is to be stored in the solid-state memory array or the magnetic recording media.

16. The data storage system of claim 15, wherein the controller is further configured to pad the storage unit with filler data, a size of the filler data selected such that the size of the storage unit is aligned with the first size or the second size.

17. The data storage system of claim 1, wherein the controller is further configured to:

in response to a read data command received from the host system, the command associated with a range of logical addresses corresponding to a memory data unit comprising a plurality of host data units;

identify and retrieve one or more storage units stored in the NVM that include the plurality of host data units associated with the read data command;

identify one or more compressed mapping units of the retrieved one or more storage units, wherein combined compressed payloads of the one or more compressed mapping units comprise at least the plurality of host data units associated with the read data command;

decompress the compressed payloads of the identified one or more compressed mapping units; and

return the plurality of host data units obtained from the decompressed payloads to the host system.

18. The data storage system of claim 17, wherein each compressed mapping unit comprises a compressed mapping unit metadata portion indicating a plurality of logical addresses associated with host data of the compressed payload, and the controller is further configured to identify the one or more compressed mapping units using their compressed mapping unit metadata portions.

19. The data storage system of claim 18, wherein compressed mapping unit metadata portions for each compressed mapping unit are not compressed.

20. The data storage system of claim 18, wherein each compressed mapping unit comprises an uncompressed and unencrypted metadata portion.

21. The data storage system of claim 18, wherein the controller is further configured to skip, within the retrieved one or more storage units, an unrelated compressed mapping unit having a compressed mapping unit metadata portion that does not indicate that the compressed mapping unit includes host data units that correspond to any of logical addresses in the logical address range associated with the read data command.

22. The data storage system of claim 1, wherein the controller is further configured to store a first portion of the compressed mapping unit into a first storage unit and store a second portion of the compressed mapping unit into a second storage unit.

23. The data storage system of claim 1, wherein the controller is further configured to store the plurality of host data units into the compressed mapping unit, and store a first portion of the compressed mapping unit into a first storage unit and store a second portion of the compressed mapping unit into second storage unit.

24. The data storage system of claim 1, wherein the write data command is associated with a plurality of error correction and detection codes corresponding to the plurality of host data units, and the controller is further configured to generate an aggregate error correction and detection code corresponding to the plurality of host data units, a size of the aggregate error correction and detection code data being smaller than a combined size of the one or more error correction and detection codes.

47. The data storage system of claim 1, wherein the size of the storage unit is an integer multiple of the size of the memory data unit.

25. A method of storing data in a non-volatile storage system comprising a non-volatile memory (NVM) configured to store a plurality of memory data units, a memory data unit being a unit of storage in the NVM, the method comprising:

in response to receiving a write data command from a host system, the command associated with a plurality of host data units associated with a plurality of logical addresses;

compressing the plurality of host data units to obtain a compressed payload, wherein a size of the compressed payload is smaller or equal to a size of the plurality of host data units;

assembling the compressed payload into a compressed mapping unit;

assembling the compressed mapping unit along with one or more additional compressed mapping units into a storage unit, wherein a size of the storage unit is aligned with the size of the memory data unit;

generating a storage unit metadata portion indicating a position in the storage unit of at least one of the compressed mapping unit or the one or more additional compressed mapping units;

including the metadata portion in the storage unit; and

storing the storage unit in the NVM,

wherein the method is performed under control of a controller.

26. The method of claim 25, wherein the plurality of host data units are associated with a plurality of sequential logical addresses.

27. The method of claim 25, further comprising encrypting the compressed payload.

28. The method of claim 25, wherein the compressed mapping unit comprises a compressed mapping unit metadata portion indicating the plurality of logical addresses associated with data of the compressed payload.

29. The method of claim 28, wherein the compressed mapping unit metadata portion is not compressed.

30. The method of claim 28, wherein the compressed mapping unit metadata portion is not compressed and is not encrypted.

31. The method of claim 30, further comprising encrypting the compressed payload.

32. The method of claim 31, further comprising repacking, using the compressed mapping unit metadata portion, the compressed payload without decrypting the compressed payload.

33. The method of claim 31, wherein the repacking is associated with at least one of defragmenting data stored in the NVM, garbage collecting data stored in the NVM, or assembling of the compressed payload into another storage unit of a different size than the size of the storage unit.

34. The method of claim 25, wherein the one or more additional compressed mapping units in the storage unit comprise host data units associated with one or more additional write data commands.

35. The method of claim 25, further including filler data in the storage unit, a size of the filler data selected such that the size of the storage unit is aligned with the size of the memory data unit.

36. The method of claim 25, wherein the NVM comprises at least one of a solid-state memory array and magnetic recording media.

37. The method of claim 36, wherein the solid-state memory array is configured to store a plurality of memory data units of a first size and the magnetic recording media is configured to store a plurality of a memory data units of a second size, and the size of the storage unit is aligned with the first size or the second size based at least in part on whether the storage unit is to be stored in the solid-state memory array or the magnetic recording media.

38. The method of claim 37, further comprising padding the storage unit with filler data, a size of the filler data selected such that the size of the storage unit is aligned with the first size or the second size.

39. The method of claim 25, further comprising:

in response to receiving a read data command from the host system, the command associated with a range of logical addresses corresponding to a memory data unit comprising a plurality of host data units;

identifying and retrieving one or more storage units stored in the NVM that include the plurality of host data units associated with the read data command;

identifying one or more compressed mapping units of the retrieved one or more storage units, wherein combined compressed payloads of the one or more compressed mapping units comprise at least the plurality of host data units associated with the read data command;

decompressing the compressed payloads of the identified one or more compressed mapping units; and

returning the plurality of host data units obtained from the decompressed payloads to the host system.

40. The method of claim 39, wherein each compressed mapping unit comprises a compressed mapping unit metadata portion indicating a plurality of logical addresses associated with host data of the compressed payload, and the controller is configured to identify the one or more compressed mapping units using their compressed mapping unit metadata portions.

41. The method of claim 40, wherein each compressed mapping unit comprises an uncompressed metadata portion.

42. The method of claim 40, wherein compressed mapping unit metadata portions for each compressed mapping unit are not compressed.

43. The method of claim 40, further comprising skipping, within the retrieved one or more storage units, an unrelated compressed mapping unit having a metadata portion that does not indicate that the compressed mapping unit includes host data units that correspond to any of logical addresses in the logical address range associated with the read data command.

44. The method of claim 25, further comprising storing a first portion of the compressed mapping unit into a first storage unit and storing a second portion of the compressed mapping unit into a second storage unit.

45. The method of claim 25, further comprising storing the plurality of host data units into the compressed mapping unit, and storing a first portion of the compressed mapping unit into a first storage unit and storing a second portion of the mapping unit into a second storage unit.

46. The method of claim 25, wherein the write data command is associated with a plurality of error correction and detection codes corresponding to the plurality of host data units, and the method further comprises generating an aggregate error correction and detection code corresponding to the plurality of host data units, a size of the aggregate error correction and detection code data being smaller than a combined size of the one or more error correction and detection codes.

48. The method of claim 25, wherein the size of the storage unit is an integer multiple of the size of the memory data unit.