Compression and formatting of data for data storage systems

• US 10,055,171 B2
• Filed: 08/29/2016
• Issued: 08/21/2018
• 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): Bradley, Matthew
• Assistant Examiner(s): Grullon, Francisco A
• Application Number:
  US15/250,264
• Publication Number:
  US 20160371037A1
• Time in Patent Office: 722 Days
• 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 processing a read data command associated with a range of logical addresses corresponding to a plurality of host data units;

identify and retrieve from the NVM at least one storage unit that includes the plurality of host data units associated with the read data command and a storage unit metadata portion indicating a position in the at least one storage unit of one or more compressed mapping units;

identify, using the position, a plurality of compressed mapping units in the retrieved at least one storage unit, wherein combined compressed payloads of the plurality of 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 plurality of compressed mapping units; and

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

2. The data storage system of claim 1, wherein:

at least one compressed mapping unit of the plurality of compressed mapping units comprises a compressed mapping unit metadata portion indicating a plurality of logical addresses associated with host data units of the compressed payload; and

the controller is further configured to identify the at least one compressed mapping unit using its compressed mapping unit metadata portion.

3. The data storage system of claim 2, wherein the controller is further configured to compare the range of logical addresses associated with the read data command with the plurality of logical addresses of the compressed mapping unit metadata portion of the at least one compressed mapping unit.

4. The data storage system of claim 2, wherein the compressed mapping unit metadata portion associated with the at least one compressed mapping unit is not compressed.

5. The data storage system of claim 2, wherein the at least one compressed mapping unit comprises compressed payload that is encrypted, and the controller is further configured to decrypt the compressed payload.

6. The data storage system of claim 5, wherein the compressed mapping unit metadata portion of the at least one compressed mapping unit is not uncompressed and not encrypted.

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

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

9. The data storage system of claim 8, 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

a size of the at least one storage unit is aligned with the first or second size based at least in part on whether the at least one storage unit is stored in the solid-state memory array or the magnetic recording media.

10. The data storage system of claim 1, wherein the at least one storage unit is padded with filler data of a size selected to permit a size of the at least one storage unit to be aligned with the memory data unit of the NVM.

11. 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 processing a read data command associated with a range of logical addresses corresponding to a plurality of host data units;

identifying and retrieving from the NVM at least one storage unit that includes the plurality of host data units associated with the read data command and a storage unit metadata portion indicating a position in the at least one storage unit of one or more compressed mapping units;

identifying, using the position, a plurality of compressed mapping units in the retrieved at least one storage unit, wherein combined compressed payloads of the plurality of 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 plurality of compressed mapping units; and

providing the plurality of host data units obtained from the decompressed payloads to a host system,

wherein the method is performed under control of a controller.

12. The method of claim 11, wherein:

at least one compressed mapping unit of the plurality of compressed mapping units comprises a compressed mapping unit metadata portion indicating a plurality of logical addresses associated with host data units of the compressed payload; and

the method further comprises identifying the at least one compressed mapping unit using its compressed mapping unit metadata portion.

13. The method of claim 12, further comprising comparing the range of logical addresses associated with the read data command with the plurality of logical addresses of the compressed mapping unit metadata portion of the at least one compressed mapping unit.

14. The method of claim 12, wherein the compressed mapping unit metadata portion associated with the at least one compressed mapping unit is not compressed.

15. The method of claim 12, wherein the at least one compressed mapping unit comprises compressed payload that is encrypted, and the method further comprises decrypting the compressed payload.

16. The method of claim 15, wherein the compressed mapping unit metadata portion of the at least one compressed mapping unit is not uncompressed and not encrypted.

17. The method of claim 11, further comprising skipping, within the retrieved at least one storage unit, an unrelated compressed mapping unit including a compressed mapping unit metadata portion that does not indicate that the unrelated compressed mapping unit includes host data units that correspond to any of logical addresses in the range of logical addresses associated with the read data command.

18. The method of claim 11, wherein the NVM comprises at least one of a solid-state memory array or magnetic recording media.

19. The method of claim 18, 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

a size of the at least one storage unit is aligned with the first or second size based at least in part on whether the at least one storage unit is stored in the solid-state memory array or the magnetic recording media.

20. The method of claim 11, wherein the at least one storage unit is padded with filler data of a size selected to permit a size of the at least one storage unit to be aligned with the memory data unit of the NVM.