Storing data utilizing repeating pattern detection

• US 9,864,769 B2
• Filed: 12/12/2014
• Issued: 01/09/2018
• Est. Priority Date: 12/12/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Sanvido, Marco, Hankins, Richard, Hayes, John, Hodgson, Steve, Wang, Feng, Zhuravlev, Sergey, Kleinerman, Andrew
• Primary Examiner(s): Jami, Hares
• Application Number:
  US14/569,624
• Publication Number:
  US 20160171029A1
• Time in Patent Office: 1,124 Days
• Field of Search: 707693, 707745
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A system and method for efficiently storing data in a storage system. A data storage subsystem includes multiple data storage locations on multiple storage devices in addition to at least one mapping table. A data storage controller determines whether data to store in the storage subsystem has one or more patterns of data intermingled with non-pattern data within an allocated block. Rather than store the one or more pattern on the storage devices, the controller stores information in a header on the storage devices. The information includes at least an offset for the first instance of a pattern, a pattern length, and an identification of the pattern. The data may be reconstructed for a corresponding read request from the information stored in the header.

Claims

1. A computer system comprising:

a data storage device; and

a data storage controller coupled to the data storage device;

wherein the data storage controller is configured to receive a write request to store write data to the data storage device, wherein the write data includes pattern data and non-pattern data; and

in response to receiving the write request,

detect, within the pattern data, whether a number of contiguous instances of a bit pattern is above a predefined threshold;

in response to detecting that the number of contiguous instances of the bit pattern is above the predefined threshold, instead of storing the pattern data within the data storage device, store within a mapping table of the data storage controller, a first entry that includes the bit pattern and the number of contiguous instances of the bit pattern;

store the non-pattern data within the data storage device; and

store, within the mapping table, one or more entries that each include a pointer to a location within the data storage device where the non-pattern data is stored.

2. The computer system as recited in claim 1, wherein a size of a single instance of the bit pattern does not exceed a programmable size threshold.

3. The computer system as recited in claim 1, wherein in response to receiving a read request, the data storage controller is further configured to read the first entry to construct data requested by the read request.

4. The computer system as recited in claim 1, wherein the data storage controller is further configured to store the non-pattern data in the data storage device in contiguous data spaces with no storage for the pattern data in the received write request.

5. The computer system as recited in claim 1, wherein one or more status fields of the entry are set to indicate that the stored data does not include a pointer value.

6. A method for use in a storage system, the method comprising:

by a data storage controller coupled to a data storage device;

receiving a write request to store write data to the data storage device, wherein the write data includes pattern data and non-pattern data; and

in response to receiving the write request,

detecting, within the pattern data, whether a number of contiguous instances of a bit pattern is above a predefined threshold;

in response to detecting that the number of contiguous instances of the bit pattern is above the predefined threshold, instead of storing the pattern data within the data storage device, storing within a mapping table of the data storage controller, a first entry that includes the bit pattern and the number of contiguous instances of the bit pattern;

storing the non-pattern data within the data storage device; and

storing, within the mapping table, one or more entries that each include a pointer to a location within the data storage device where the non-pattern data is stored.

7. The method as recited in claim 6, wherein a size of a single instance of the bit pattern does not exceed a size threshold.

8. The method as recited in claim 6, wherein in response to receiving a read request, the method further comprises reading the first entry to construct the data corresponding to the read request.

9. The method as recited in claim 6, wherein the method further comprises storing the non-pattern data in the data storage device in contiguous data spaces with no storage for the pattern data in the received write request.

10. The method as recited in claim 6, wherein one or more status fields of the entry are set to indicate that the stored data does not include a pointer value.

11. A non-transitory computer readable storage medium storing program instruction executable by a processor to:

by a data storage controller coupled to a data storage device;

receive a write request to store write data to the data storage device, wherein the write data includes pattern data and non-pattern data; and

in response to receiving the write request,

detect, within the pattern data, whether a number of contiguous instances of a bit pattern is above a predefined threshold;

in response to detecting that the number of contiguous instances of the bit pattern is above the predefined threshold, instead of storing the pattern data within the data storage device, store within a mapping table of the data storage controller, a first entry that includes the bit pattern and the number of contiguous instances of the bit pattern;

store the non-pattern data within the data storage device; and

store, within the mapping table, one or more entries that each include a pointer to a location within the data storage device where the non-pattern data is stored.

12. The non-transitory computer readable storage medium as recited in claim 11, wherein a size of a single instance of the bit pattern does not exceed a size threshold.

13. The non-transitory computer readable storage medium as recited in claim 11, wherein in response to receiving a read request, the program instructions are further executable by a processor to read the first entry to construct the data corresponding to the read request.

14. The non-transitory computer readable storage medium as recited in claim 11, wherein one or more status fields of the entry are set to indicate that the stored data does not include a pointer value.