Data Compression and Compacting for Memory Devices

• US 20120290798A1
• Filed: 05/09/2012
• Published: 11/15/2012
• Est. Priority Date: 05/10/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell World Trade Limited (Marvell Technology Group Limited)
• Inventors: Au, Siu-Hung Fred, Yang, Xueshi, Huang, ChengKuo, Lee, Sean, Sun, Fei, Chen, Grace Pao Yi, Cheung, Man
• Granted Patent: US 8,949,513 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• 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/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Embodiments of the present disclosure provide apparatuses and methods for determining a compacting arrangement to store logical addressable units, which include compressed data sectors, into hardware addressable units of a storage device. The compacting arrangement is based on compression information associated with the logical addressable units. A write module is used to write the compressed data sectors to the storage device according to the compacting arrangement.

Claims

1. An apparatus, comprising:

a hardware data compressor configured to

compress data sectors received from a computing system, and

determine compression information associated with a plurality of logical addressable units that include corresponding at least one of the compressed data sectors;

a compactor module configured to determine, based on the compression information, a compacting arrangement wherein at least one of the plurality of logical addressable units are compacted into corresponding ones of a plurality of hardware addressable units; and

a write module configured to cause the compressed data sectors to be written, according to the determined compacting arrangement, to a storage device.

2. The apparatus of claim 1, wherein the hardware data compressor is further configured to determine the logical addressable units and their corresponding at least one of the compressed data sectors based at least on logical block addresses of the data sectors.

3. The apparatus of claim 2, wherein the compactor module is further configured to determine, based on bits of the logical block addresses, logical addressable unit addresses.

4. The apparatus of claim 1, further comprising:

an adaptor that includes the hardware data compressor; and

a double data rate device that is operationally situated between the adaptor and the storage device.

5. The apparatus of claim 1, wherein:

the compactor module is further configured to maintain a look-up table;

the look-up table maps, according to the determined compacting arrangement, logical addressable unit addresses associated with the plurality of logical addressable units to corresponding hardware addressable unit addresses associated with corresponding ones of the plurality of hardware addressable units; and

the look-up table indicates a position within a particular hardware addressable unit that includes a particular logical addressable unit.

6. The apparatus of claim 1, wherein:

the compression information indicates reported compression ratios associated with individual ones of the plurality of logical addressable units; and

the compactor module is further configured to determine, based at least on the reported compression ratios, the compacting arrangement.

7. The apparatus of claim 1, wherein:

the compression information indicates reported compression ratios associated with individual ones of the plurality of logical addressable units; and

the hardware data compressor is further configured to determine the reported compression ratios by rounding up actual compression ratios of the individual ones of the plurality of logical addressable units to nearest ones of a schedule of compression ratios.

8. The apparatus of claim 1, wherein:

the write module is further configured to determine headers for the corresponding ones of the plurality of hardware addressable units; and

the headers include numbers of logical addressable units stored in the corresponding ones of the plurality of hardware addressable units.

9. The apparatus of claim 1, further comprising a read module configured to:

perform a look up using a look-up table in order to determine a hardware addressable unit address associated with a target hardware addressable unit that includes a compressed one of a target data sector to be read from the storage device, wherein the look up using the look-up table also determines an identifier that indicates a position within the target hardware addressable unit that includes a particular logical addressable unit associated with the data sector; and

generate a descriptor that includes the hardware addressable unit address and the identifier.

10. The apparatus of claim 9, further comprising:

an error correction circuit; and

sequencer hardware configured to utilize the descriptor to cooperate with the error correction circuit to retrieve at least the particular logical addressable unit associated with the target data sector.

11. The apparatus of claim 1, wherein the storage device is a solid state device.

12. A method, comprising:

compressing a plurality of data sectors received from a host computing device to produce a plurality of compressed data sectors;

based at least on logical block addresses of the plurality of compressed data sectors, determining a plurality of logical addressable units that include corresponding at least one of the plurality of compressed data sectors;

based at least on compression ratios of the plurality of logical addressable units, associating sets of at least one of the plurality of logical addressable units with corresponding hardware addressable units; and

writing the hardware addressable units, including their corresponding sets of at least one of the plurality of logical addressable units, to a storage device.

13. The method of claim 12, wherein the writing is performed as part of one of a program operation of the storage device, a read-modify-write operation of the storage device, or a garbage collection operation of the storage device.

14. The method of claim 12, further comprising maintaining a look-up table that associates logical addressable unit addresses to hardware addressable unit addresses and to positions within the corresponding hardware addressable units.

15. The method of claim 14, wherein the determining the plurality of logical addressable units is further based on a predetermined number of data sectors to be placed into the plurality of logical addressable units.

16. The method of claim 12, further comprising:

receiving a read command to read a target data sector;

performing a look-up using a look-up table that associates logical addressable unit addresses to hardware addressable unit addresses to determine a descriptor that includes a target hardware addressable unit address of a target hardware addressable unit that corresponds to the target data sector, and a mask that indicates a position within the target hardware addressable unit of a target logical addressable unit that corresponds to the target data sector; and

based on the descriptor, retrieving the target data sector from the storage device.

17. The method of claim 12, wherein:

the compression information indicates reported compression ratios associated with individual ones of the plurality of logical addressable units; and

the method further includes, based on sizes of the individual ones of the plurality of logical addressable units determined based at least on the reported compression ratios, determining the sets of at least one of the plurality of logical addressable units.

18. The method of claim 17, further comprising determining the reported compression ratios by rounding up, to ones of a schedule of compression ratios, actual compression ratios of the individual ones of the plurality of logical addressable units.

19. The method of claim 12, wherein the storage device is a solid state device.

20. A method, comprising:

receiving a command from a host computer system to read a target data sector from a storage device, wherein the target data sector has a target logical block address;

based on the target logical block address of the target sector, retrieving, from a hardware addressable unit of the storage device, at least a target logical addressable unit that includes a compressed one of the target data sector and compression information associated with the target logical addressable unit; and

based at least on the compression information, decompressing the compressed one of the target data sector.

21. The method of claim 20, further comprising outputting the decompressed target data sector to the host computer system.

22. The method of claim 20, further comprising, based on the target logical block address, performing a look-up using a look-up table that associates logical addressable unit addresses of a plurality of logical addressable units to hardware addressable unit addresses of a plurality of hardware addressable units in order to determine:

a target hardware addressable unit address of a target hardware addressable unit that includes the target logical addressable unit; and

a relative position of the target logical addressable unit within the target hardware addressable unit.

23. The method of claim 20, wherein the storage device is flash memory.