Managing compressed data in a storage system

• US 9,569,357 B1
• Filed: 01/08/2015
• Issued: 02/14/2017
• Est. Priority Date: 01/08/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Shalev, Ori, Karr, Ronald S., Zhang, Wei
• Primary Examiner(s): Patel, Kaushikkumar
• Application Number:
  US14/592,336
• Time in Patent Office: 768 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 2212/1041 Resource optimization
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Systems, methods, and computer readable storage mediums for optimistically managing compressed data in a storage system. When possible, multiple input blocks are compressed into a buffer and stored in a single physical block on a storage device. The metadata of the multiple input blocks can be managed separately. A fingerprint of the compressed buffer can be generated and used as an index to the single physical block. Alternatively, fingerprints of the uncompressed input blocks can be generated, and reference counts can be maintained to track the number of input blocks which reference the compressed buffer.

Claims

1. A system comprising:

a storage device; and

a storage controller coupled to the storage device, wherein the storage controller is configured to;

generate at least a first fingerprint and a second fingerprint for first input data, wherein a size of the first input data is greater than a size of a single physical storage block;

compress the first input data to a size less than or equal to the size of a single physical storage block;

generate, for the compressed first input data, a third fingerprint;

store references from the first, second, and third fingerprints to a first physical storage block storing the compressed first input data; and

free the first physical storage block if there are no remaining references to the first physical storage block.

2. The system as recited in claim 1, wherein the storage controller is configured to maintain a physical address reference count to track a number of different fingerprints which reference the first physical storage block, and free the first physical storage block via garbage collection when the physical address reference count is zero.

3. The system as recited in claim 2, wherein the storage controller is configured to increase the physical address reference count by an amount equal to a number of fingerprints generated for the first input data.

4. The system as recited in claim 1, wherein the storage controller is configured to free the first physical storage block using a mark and sweep algorithm.

5. The system as recited in claim 1, wherein the storage controller is configured to discard the first and second fingerprints responsive to determining the first input data can be compressed to a size less than or equal to the size of a single physical storage block and responsive to determining that neither of the first and second fingerprints match any existing fingerprints.

6. The system as recited in claim 1, wherein the first input data comprises a plurality of adjacent input data blocks within an input data stream, and wherein a size of each adjacent input data block is greater than or equal to a size of a single physical storage block on the storage device.

7. A method comprising:

generating at least a first fingerprint and a second fingerprint for first input data, wherein a size of the first input data is greater than a size of a single physical storage block;

compressing the first input data to a size less than or equal to the size of a single physical storage block;

generating, for the compressed first input data, a third fingerprint;

storing references from the first, second, and third fingerprints to a first physical storage block storing the compressed first input data; and

freeing the first physical storage block if there are no remaining references to the first physical storage block.

8. The method as recited in claim 7, further comprising:

maintaining a physical address reference count to track a number of different fingerprints which reference the first physical storage block; and

freeing the first physical storage block via garbage collection when the physical address reference count is zero.

9. The method as recited in claim 8, further comprising increasing the physical address reference count by an amount equal to a number of fingerprints generated for the first input data.

10. The method as recited in claim 7, further comprising freeing the first physical storage block using a mark and sweep algorithm.

11. The method as recited in claim 7, further comprising discarding the first and second fingerprints responsive to determining the first input data can be compressed to a size less than or equal to the size of a single physical storage block and responsive to determining that neither of the first and second fingerprints match any existing fingerprints.

12. The method as recited in claim 7, wherein the first input data comprises a plurality of adjacent input data blocks within an input data stream, and wherein a size of each adjacent input data block is greater than or equal to a size of a single physical storage block on the storage device.

13. A non-transitory computer readable storage medium storing program instructions, wherein the program instructions are executable by a processor to:

generate at least a first fingerprint and a second fingerprint for first input data, wherein a size of the first input data is greater than a size of a single physical storage block;

compress the first input data to a size less than or equal to the size of a single physical storage block;

generate, for the compressed first input data, a third fingerprint

store references from the first, second, and third fingerprints to a first physical storage block storing the compressed first input data; and

free the first physical storage block if there are no remaining references to the first physical storage block.

14. The non-transitory computer readable storage medium as recited in claim 13, wherein the program instructions are executable by a processor to:

maintain a physical address reference count to track a number of different fingerprints which reference the first physical storage block; and

free the first physical storage block via garbage collection when the physical address reference count is zero.

15. The non-transitory computer readable storage medium as recited in claim 14, wherein the program instructions are executable by a processor to increase the physical address reference count by an amount equal to a number of fingerprints generated for the first input data.

16. The non-transitory computer readable storage medium as recited in claim 13, wherein the first input data comprises a plurality of input data blocks, and wherein the program instructions are executable by a processor to free the first physical storage block using a mark and sweep algorithm.

17. The non-transitory computer readable storage medium as recited in claim 13, wherein the program instructions are executable by a processor to discard the first and second fingerprints responsive to determining the first input data can be compressed to a size less than or equal to the size of a single physical storage block and responsive to determining that neither of the first and second fingerprints match any existing fingerprints.