SYSTEMS AND METHODS FOR STORAGE COMPRESSION

• US 20150242309A1
• Filed: 07/17/2014
• Published: 08/27/2015
• Est. Priority Date: 02/24/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: TALAGALA, NISHA, MATHIASEN, TORBEN, DAS, DHANANJOY, FLYNN, DAVID
• Granted Patent: US 9,875,180 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• 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]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A compression manager generates a reduced-size data set for a page. The reduced-size data set is stored on a storage medium by a storage module, and unused portions of the page are identified and/or recorded by the storage module. The reduced-size data set may be generated by compressing the page. The reduced-size data set may be written in response to a request from a client, which provides a message that identifies the unused portion(s) of the page. The page may be stored in a file, and the unused portion may correspond to empty portion(s) within the file. The storage module may maintain an index to map the page to the reduced-size data set, such that portions of the page are unmapped. The storage capacity used by the page may correspond to the mapped portion of the page, and exclude portion(s) of the page that are unmapped.

Claims

1. A method, comprising:

receiving a request to write data of a page to a non-volatile storage medium, wherein the page represents a fixed number of blocks on a storage medium;

directing a storage module to write data of the page on fewer blocks of the storage medium than the fixed number of blocks represented by the page; and

identifying to the storage module, which blocks of the fixed number of storage blocks represented by the page do not contain data of the page.

2. The method of claim 1, further comprising compressing the data of the page, wherein directing the storage module to write the data of the page comprises directing the storage module to write the compressed data of the page.

3. The method of claim 1, wherein the page is designated as a compressed page by a client.

4. The method of claim 1, wherein the page corresponds to a file, and wherein directing the storage module to write the data of the page comprises issuing a request to write the data of the page to the file.

5. The method of claim 4, wherein identifying to the storage module, which blocks of the fixed number of storage blocks represented by the page do not contain data of the page comprises identifying an empty portion of the file.

6. The method of claim 1, wherein identifying to the storage module, which blocks of the fixed number of blocks do not contain data of the page comprises providing a deallocation message to the storage module that identifies blocks that do not contain data of the page.

7. An apparatus, comprising:

a compression manager that receives a request to persist a page, wherein the page is defined to have a fixed amount of storage capacity;

a reduction module that derives a data set from the page, wherein the data set is smaller than the fixed amount of storage capacity;

a file allocation module that issues a request to write the data set to a file associated with the page, and identifies an empty portion of the file to a file system.

8. The apparatus of claim 7, wherein the file allocation module specifies an offset and length of the empty portion of the file.

9. The apparatus of claim 7, wherein the file allocation module identifies unused logical block addresses of the file.

10. The apparatus of claim 7, wherein the reduction module derives the data set by compressing data of the page.

11. A system comprising:

a compression agent that generates compressed data of a page, wherein the page is sized to include a fixed number of sectors on a non-volatile storage medium;

a storage module that writes the compressed data of the page on fewer sectors of the non-volatile storage medium than the fixed number of sectors; and

a metadata management module that records which sectors corresponding to the page are not in use.

12. The system of claim 11, wherein the page is associated with a plurality of identifiers of a logical address space, wherein one or more of the identifiers are assigned to compressed data of the page stored on the non-volatile storage medium, and wherein one or more of the identifiers are unassigned.

13. The system of claim 11, wherein the page comprises a set of logical addresses, the apparatus further comprising a logical address space management module that maintains an index that maps a first subset of the set of logical addresses to storage addresses on the storage medium, such that a second subset of the logical addresses are unmapped.

14. The system of claim 13, further comprising a capacity module that determines a physical storage capacity used by the page based on mappings of the index.

15. The system of claim 13, wherein the metadata management module records which sectors of the page are not in use by removing, from the index, one or more mappings pertaining to the set of logical addresses of the page.

16. The system of claim 11, wherein the metadata management module directs the storage module to write persistent metadata on the non-volatile storage medium, wherein the persistent metadata identifies sectors of the page that are not in use.

17. An apparatus, comprising:

a translation module that maps logical identifiers of a logical address space to storage units on a storage device;

a storage module that writes data of a page associated with a set of logical identifiers of the logical address space to a subset of the logical identifiers associated with the page; and

a logical address space management module that records that one or more of the logical identifiers associated with the page are unmapped.

18. The apparatus of claim 17, wherein the data of the page comprises compressed data, the apparatus further comprising a compression agent that generates the compressed data of the page.

19. The apparatus of claim 17, wherein the translation module assigns the subset of logical identifiers to respective storage units storing the data of the page.

20. The apparatus of claim 19, further comprising a capacity module that determines a storage capacity consumed by the page on the storage device based on the assignments between the subset of logical identifiers and the respective storage units.

21. The apparatus of claim 17, wherein the logical address management module removes a mapping between a particular logical identifier associated with the page and a storage unit on the storage device, and writes persistent metadata on the storage device that indicates that the particular logical identifier unmapped.